Array within object returning length of 0, even though there are elements present

I am trying to implement a Trie in Javascript, which is easy enough but I seem to have hit a road block with my object.

The nodes are structured as follows:

var node = {
    children: []
}

Children is an array of nodes that is mapped by a letter in a string. So the string "Test" would look like this:

root = {
  children: [
      't' => {
          children: [
              'e' => {
                   children: [
                       's' => {
                            children: [
          开发者_Python百科                       't' => {
                                      children: []
                                  }
                            ]
                        }
                   ]
               }
          ]
      }
  ]
};

So each children array should have a length of 1, but if do something like alert(this._root.children.length); I get zero. Any thoughts on why this is happening?

Here is the rest of my implementation:

function Trie() {
    this._root = {
        children: []
    };
}

Trie.prototype = {

    //restore constructor
    constructor: Trie,

    add: function (str){
        var curr = this._root,
            prev,
            currchar;
        // For each character in the string
        for(var i = 0, j = str.length; i < j; i++) {
            // Insert only lowercase letters for efficiency
            currchar = str.toLowerCase().charAt(i);
            prev = curr;
            curr = prev.children[currchar];
            // Traverse until we hit a non-existant node
            if(typeof(curr) == "undefined") {
                // Make a new node
                prev.children[currchar] = {
                    children: []
                };
                curr = prev.children[currchar];
            }
        }
    }

You are adding properties to the array instance object, not elements to the array. The length property only includes array elements, not properties on the array instance object.

var a = [23, 42];
console.log(a.length); // 2
a['foo'] = 'bar';
console.log(a.length); // 2
a[2] = 1337;
console.log(a.length); // 3

EDITED: You could instead structure the nodes like this:

var node = {
    children: {},
    length: function () {
        var i = 0;
        var k;

        for (k in this.children) {
            if (this.children.hasOwnProperty(k)) {
                i++;
            }
        }
        return i;
    }
};

This is inefficient, of course. You should instead define a Node class with the length method on its prototype. Alternatively, define an add method that updates the length property.

I think that the problem is that you use a javasrcipt array as an associative array (as found in other languages). In javascript "associative" arrays are objects that don't have a length property. Normal arrays have numeric indices.

Irrelevant to the question but you might find this useful.

Maybe you want

str.toLowerCase().charCodeAt(i)

instead of

str.toLowerCase().charAt(i)

If str is "f1", the properties you're adding to the children array are "f" and "1" which should cause an array with property named f and length 0, and another child array with length 2 and property 1.

To get only numeric properties, you should make sure your property names are valid array indices -- positive integers representable in 31 bits.

By using charCodeAt instead of charCode, you would get the property names 102 and 49 instead of "f" and 1.