/**
 * Trie class
 * 
 * @see http://en.wikipedia.org/wiki/Radix_tree
 * @author Stephan Six <stephan.six@gmail.com>
 * @version 1.0
 */
function Trie() {
  "use strict";

  /**
   * The trie root
   * @var object
   */
  var root = {
    children: {}
  };

  /**
   * count helper
   * 
   * @access private
   * @param object obj
   * @return integer
   */
  function count(obj) {
    var result = 0, key;

    for (key in obj) {
      if (obj.hasOwnProperty(key)) {
        result += 1;
      }
    }

    return result;
  }

  /**
   * forEach helper
   * 
   * @access private
   * @param object obj
   * @param function callback
   * @return void
   */
  function each(obj, callback) {
    var key;
    for (key in obj) {
      if (obj.hasOwnProperty(key)) {
        if (false === callback(key, obj[key], obj)) {
          break;
        }
      }
    }
  }

  /**
   * Collapses a trie
   *
   * @access private
   * @param array trie
   * @param string parentKey
   * @return object
   */
  function collapse(trie, parentKey) {
    var result = {};

    if (count(trie.children) > 0) {
      each(trie.children, function (p, child) {
        each(collapse(child, p), function (q, values) {
          result[parentKey + q] = values;
        });
      });
    }
    
    if (trie.isWord) {
      result[parentKey] = trie.values;
    }

    return result;
  }

  /**
   * Adds a value at key
   *
   * @access public
   * @param string key
   * @param mixed value
   * @return void
   */
  this.add = function (key, value) {
    var parent = root, i = 0, char;

    for (; i < key.length; i += 1) {
      char = key.substr(i, 1);

      if (typeof parent.children[char] === 'undefined') {
        parent.children[char] = {
          children: {},
          values: []
        };
      }

      parent = parent.children[char];
    }

    if (!parent.values) {
      parent.values = [];
    }

    parent.values.push(value);
    parent.isWord = true;
  };

  /**
   * Getter
   *
   * @access public
   * @param string key
   * @return null|object
   */
  this.get = function (key) {
    var parent = root, i = 0, char;

    for (; i < key.length; i += 1) {
      char = key.substr(i, 1);

      if (typeof parent.children[char] !== 'undefined') {
        parent = parent.children[char];
      } else {
        return null;
      }
    }

    return collapse(parent, key);
  };
}