File Explorer

1/**2 * Mnemonist Trie3 * ===============4 *5 * JavaScript Trie implementation based upon plain objects. As such this6 * structure is more a convenience building upon the trie's advantages than7 * a real performant alternative to already existing structures.8 *9 * Note that the Trie is based upon the TrieMap since the underlying machine10 * is the very same. The Trie just does not let you set values and only11 * considers the existence of the given prefixes.12 */13var forEach = require('obliterator/foreach'),14    TrieMap = require('./trie-map.js');15 16/**17 * Constants.18 */19var SENTINEL = String.fromCharCode(0);20 21/**22 * Trie.23 *24 * @constructor25 */26function Trie(Token) {27  this.mode = Token === Array ? 'array' : 'string';28  this.clear();29}30 31// Re-using TrieMap's prototype32for (var methodName in TrieMap.prototype)33  Trie.prototype[methodName] = TrieMap.prototype[methodName];34 35// Dropping irrelevant methods36delete Trie.prototype.set;37delete Trie.prototype.get;38delete Trie.prototype.values;39delete Trie.prototype.entries;40 41/**42 * Method used to add the given prefix to the trie.43 *44 * @param  {string|array} prefix - Prefix to follow.45 * @return {TrieMap}46 */47Trie.prototype.add = function(prefix) {48  var node = this.root,49      token;50 51  for (var i = 0, l = prefix.length; i < l; i++) {52    token = prefix[i];53 54    node = node[token] || (node[token] = {});55  }56 57  // Do we need to increase size?58  if (!(SENTINEL in node))59    this.size++;60 61  node[SENTINEL] = true;62 63  return this;64};65 66/**67 * Method used to retrieve every item in the trie with the given prefix.68 *69 * @param  {string|array} prefix - Prefix to query.70 * @return {array}71 */72Trie.prototype.find = function(prefix) {73  var isString = typeof prefix === 'string';74 75  var node = this.root,76      matches = [],77      token,78      i,79      l;80 81  for (i = 0, l = prefix.length; i < l; i++) {82    token = prefix[i];83    node = node[token];84 85    if (typeof node === 'undefined')86      return matches;87  }88 89  // Performing DFS from prefix90  var nodeStack = [node],91      prefixStack = [prefix],92      k;93 94  while (nodeStack.length) {95    prefix = prefixStack.pop();96    node = nodeStack.pop();97 98    for (k in node) {99      if (k === SENTINEL) {100        matches.push(prefix);101        continue;102      }103 104      nodeStack.push(node[k]);105      prefixStack.push(isString ? prefix + k : prefix.concat(k));106    }107  }108 109  return matches;110};111 112/**113 * Attaching the #.keys method to Symbol.iterator if possible.114 */115if (typeof Symbol !== 'undefined')116  Trie.prototype[Symbol.iterator] = Trie.prototype.keys;117 118/**119 * Convenience known methods.120 */121Trie.prototype.inspect = function() {122  var proxy = new Set();123 124  var iterator = this.keys(),125      step;126 127  while ((step = iterator.next(), !step.done))128    proxy.add(step.value);129 130  // Trick so that node displays the name of the constructor131  Object.defineProperty(proxy, 'constructor', {132    value: Trie,133    enumerable: false134  });135 136  return proxy;137};138 139if (typeof Symbol !== 'undefined')140  Trie.prototype[Symbol.for('nodejs.util.inspect.custom')] = Trie.prototype.inspect;141 142Trie.prototype.toJSON = function() {143  return this.root;144};145 146/**147 * Static @.from function taking an arbitrary iterable & converting it into148 * a trie.149 *150 * @param  {Iterable} iterable   - Target iterable.151 * @return {Trie}152 */153Trie.from = function(iterable) {154  var trie = new Trie();155 156  forEach(iterable, function(value) {157    trie.add(value);158  });159 160  return trie;161};162 163/**164 * Exporting.165 */166Trie.SENTINEL = SENTINEL;167module.exports = Trie;168