Trie.js

/* Trie implementation in JavaScript
 * @version 0.1
 * Author - Jeff Long
 */

(function() {
  /**
   * Trie(value) Initialize a new tree with base node x.
   *
   * @param {String} value
   * @return {Trie} trie
   */
  var Trie = function(value) {
    var value = value || '';
    this.children = [];
    this.endpoint = false;

    // Add a word if it's passed in
    if (value.length > 1) {
      this.value = '';
      this.add(value);
    } else {
      this.value = value;
    }
    return this;
  };

  Trie.prototype = {

    /**
     * add(word) adds a word to the trie
     *
     * @param {String} word
     * @return {Trie} trie
     */
    add: function(word) {
      if (word.forEach) {
        word.forEach(function(w) {
          this.add(w);
        }.bind(this));
        return this;
      }
      var node = this;
      for (var i in word) {
        var code = word.charCodeAt(i);
        if (node.children[code] !== undefined) {
          node = node.children[code];
        } else {
          node = node.children[code] = new Trie(code);
        }
      }
      node.endpoint = true;
      return this;
    },

    /**
     * getParent(word) returns a parent trie
     * based on the passed word
     *
     * @param {String} word
     * @return {Trie|Boolean} parentNode
     */
    getParent: function(word) {
      var parentNode = this;
      for (var i in word) {
        parentNode = parentNode.children[word.charCodeAt(i)];
        if (node === undefined) {
          return false;
        } else if (parseInt(i) === (word.length - 2)) {
          return parentNode;
        }
      }
      return false;
    },

    /**
     * remove(word) deletes a word from the trie
     *
     * @param {String} word
     * @return {Boolean} success
     */
    remove: function(word) {
      var parent = this.getParent(word);
      var charCode = word.charCodeAt(word.length - 1);
      if (!parent) {
        return false;
      }

      var node = parent.children[charCode];
      if (node.getChildren().length > 0) {
        node.endpoint = false;
      } else {
        delete parent.children[charCode];
      }

      if (parent.getChildren().length === 0) {
        node = parent;
        var level = 1;
        while (node.getChildren().length === 0 && !node.endpoint) {
          parent = this.getParent(word.substr(0, (word.length - level))) || this;
          delete parent.children[node.value];
          node = parent;
          level++;
        }
      }

      return true;
    },

    /**
     * contains(word) determines if a word is in the trie
     *
     * @param {String} word
     * @return {Boolean}
     */
    contains: function(word) {
      var parent = this.getParent(word);
      if (!parent || parent.children.length === 0) {
        return false;
      }
      var node = parent.children[word.charCodeAt(word.length - 1)] || {};
      return node.hasOwnProperty('endpoint') && node.endpoint !== false;
    },


    /**
     * getChildren() returns children of current node.
     * When you push an element to an array in Javascript at position x,
     * all indexes < x are automatically initialized as undefined. This filters
     * them out so we can use character codes for indexes.
     *
     * @return {Array} children
     */
    getChildren: function() {
      return this.children.filter(function(child) { return child !== undefined; });
    },

    /**
     * wordCount() returns a count of words from the trie.
     *
     * @return {Integer} count
     */
    wordCount: function() {
      var count = 0;

      function countWords(node) {
        for (var idx in node.children) {
          if (node.children[idx].endpoint) {
            count++;
          }
          countWords(node.children[idx]);
        }
      }

      countWords(this);
      return count;
    },

    /**
     * getJSON() returns a more readable representation of current data.
     *
     * @return {Object} data
     */
    getJSON: function() {
      var output = {
        wordcount: this.wordCount(),
        words: []
      };

      function getValues(node, depth) {
        for (var i in node.children) {
          var child = node.children[i] || false;
          if (child) {
            output.words.push({ char: String.fromCharCode(child.value),
                                depth: depth,
                                endpoint: child.endpoint });
            getValues(child, (depth + 1));
          }
        }
      }

      getValues(this, 0);
      return output;
    }

  };

  module.exports = Trie;
})();