File Explorer

/proc/self/root/var/runtime/node_modules/@aws-sdk/node_modules/mnemonist

This explorer reads the filesystem of the server it runs on, so /workspace/user isn't present here. Browsing and the terminal still work against this server's own disk from /.

trie-map.js9.8 KB · 478 lines
/** * Mnemonist TrieMap * ================== * * JavaScript TrieMap implementation based upon plain objects. As such this * structure is more a convenience building upon the trie's advantages than * a real performant alternative to already existing structures. * * Note that the Trie is based upon the TrieMap since the underlying machine * is the very same. The Trie just does not let you set values and only * considers the existence of the given prefixes. */var forEach = require('obliterator/foreach'),    Iterator = require('obliterator/iterator'); /** * Constants. */var SENTINEL = String.fromCharCode(0); /** * TrieMap. * * @constructor */function TrieMap(Token) {  this.mode = Token === Array ? 'array' : 'string';  this.clear();} /** * Method used to clear the trie. * * @return {undefined} */TrieMap.prototype.clear = function() {   // Properties  this.root = {};  this.size = 0;}; /** * Method used to set the value of the given prefix in the trie. * * @param  {string|array} prefix - Prefix to follow. * @param  {any}          value  - Value for the prefix. * @return {TrieMap} */TrieMap.prototype.set = function(prefix, value) {  var node = this.root,      token;   for (var i = 0, l = prefix.length; i < l; i++) {    token = prefix[i];     node = node[token] || (node[token] = {});  }   // Do we need to increase size?  if (!(SENTINEL in node))    this.size++;   node[SENTINEL] = value;   return this;}; /** * Method used to update the value of the given prefix in the trie. * * @param  {string|array} prefix - Prefix to follow. * @param  {(oldValue: any | undefined) => any} updateFunction - Update value visitor callback. * @return {TrieMap} */TrieMap.prototype.update = function(prefix, updateFunction) {  var node = this.root,      token;   for (var i = 0, l = prefix.length; i < l; i++) {    token = prefix[i];     node = node[token] || (node[token] = {});  }   // Do we need to increase size?  if (!(SENTINEL in node))    this.size++;   node[SENTINEL] = updateFunction(node[SENTINEL]);   return this;}; /** * Method used to return the value sitting at the end of the given prefix or * undefined if none exist. * * @param  {string|array} prefix - Prefix to follow. * @return {any|undefined} */TrieMap.prototype.get = function(prefix) {  var node = this.root,      token,      i,      l;   for (i = 0, l = prefix.length; i < l; i++) {    token = prefix[i];    node = node[token];     // Prefix does not exist    if (typeof node === 'undefined')      return;  }   if (!(SENTINEL in node))    return;   return node[SENTINEL];}; /** * Method used to delete a prefix from the trie. * * @param  {string|array} prefix - Prefix to delete. * @return {boolean} */TrieMap.prototype.delete = function(prefix) {  var node = this.root,      toPrune = null,      tokenToPrune = null,      parent,      token,      i,      l;   for (i = 0, l = prefix.length; i < l; i++) {    token = prefix[i];    parent = node;    node = node[token];     // Prefix does not exist    if (typeof node === 'undefined')      return false;     // Keeping track of a potential branch to prune    if (toPrune !== null) {      if (Object.keys(node).length > 1) {        toPrune = null;        tokenToPrune = null;      }    }    else {      if (Object.keys(node).length < 2) {        toPrune = parent;        tokenToPrune = token;      }    }  }   if (!(SENTINEL in node))    return false;   this.size--;   if (toPrune)    delete toPrune[tokenToPrune];  else    delete node[SENTINEL];   return true;}; // TODO: add #.prune? /** * Method used to assert whether the given prefix exists in the TrieMap. * * @param  {string|array} prefix - Prefix to check. * @return {boolean} */TrieMap.prototype.has = function(prefix) {  var node = this.root,      token;   for (var i = 0, l = prefix.length; i < l; i++) {    token = prefix[i];    node = node[token];     if (typeof node === 'undefined')      return false;  }   return SENTINEL in node;}; /** * Method used to retrieve every item in the trie with the given prefix. * * @param  {string|array} prefix - Prefix to query. * @return {array} */TrieMap.prototype.find = function(prefix) {  var isString = typeof prefix === 'string';   var node = this.root,      matches = [],      token,      i,      l;   for (i = 0, l = prefix.length; i < l; i++) {    token = prefix[i];    node = node[token];     if (typeof node === 'undefined')      return matches;  }   // Performing DFS from prefix  var nodeStack = [node],      prefixStack = [prefix],      k;   while (nodeStack.length) {    prefix = prefixStack.pop();    node = nodeStack.pop();     for (k in node) {      if (k === SENTINEL) {        matches.push([prefix, node[SENTINEL]]);        continue;      }       nodeStack.push(node[k]);      prefixStack.push(isString ? prefix + k : prefix.concat(k));    }  }   return matches;}; /** * Method returning an iterator over the trie's values. * * @param  {string|array} [prefix] - Optional starting prefix. * @return {Iterator} */TrieMap.prototype.values = function(prefix) {  var node = this.root,      nodeStack = [],      token,      i,      l;   // Resolving initial prefix  if (prefix) {    for (i = 0, l = prefix.length; i < l; i++) {      token = prefix[i];      node = node[token];       // If the prefix does not exist, we return an empty iterator      if (typeof node === 'undefined')        return Iterator.empty();    }  }   nodeStack.push(node);   return new Iterator(function() {    var currentNode,        hasValue = false,        k;     while (nodeStack.length) {      currentNode = nodeStack.pop();       for (k in currentNode) {        if (k === SENTINEL) {          hasValue = true;          continue;        }         nodeStack.push(currentNode[k]);      }       if (hasValue)        return {done: false, value: currentNode[SENTINEL]};    }     return {done: true};  });}; /** * Method returning an iterator over the trie's prefixes. * * @param  {string|array} [prefix] - Optional starting prefix. * @return {Iterator} */TrieMap.prototype.prefixes = function(prefix) {  var node = this.root,      nodeStack = [],      prefixStack = [],      token,      i,      l;   var isString = this.mode === 'string';   // Resolving initial prefix  if (prefix) {    for (i = 0, l = prefix.length; i < l; i++) {      token = prefix[i];      node = node[token];       // If the prefix does not exist, we return an empty iterator      if (typeof node === 'undefined')        return Iterator.empty();    }  }  else {    prefix = isString ? '' : [];  }   nodeStack.push(node);  prefixStack.push(prefix);   return new Iterator(function() {    var currentNode,        currentPrefix,        hasValue = false,        k;     while (nodeStack.length) {      currentNode = nodeStack.pop();      currentPrefix = prefixStack.pop();       for (k in currentNode) {        if (k === SENTINEL) {          hasValue = true;          continue;        }         nodeStack.push(currentNode[k]);        prefixStack.push(isString ? currentPrefix + k : currentPrefix.concat(k));      }       if (hasValue)        return {done: false, value: currentPrefix};    }     return {done: true};  });};TrieMap.prototype.keys = TrieMap.prototype.prefixes; /** * Method returning an iterator over the trie's entries. * * @param  {string|array} [prefix] - Optional starting prefix. * @return {Iterator} */TrieMap.prototype.entries = function(prefix) {  var node = this.root,      nodeStack = [],      prefixStack = [],      token,      i,      l;   var isString = this.mode === 'string';   // Resolving initial prefix  if (prefix) {    for (i = 0, l = prefix.length; i < l; i++) {      token = prefix[i];      node = node[token];       // If the prefix does not exist, we return an empty iterator      if (typeof node === 'undefined')        return Iterator.empty();    }  }  else {    prefix = isString ? '' : [];  }   nodeStack.push(node);  prefixStack.push(prefix);   return new Iterator(function() {    var currentNode,        currentPrefix,        hasValue = false,        k;     while (nodeStack.length) {      currentNode = nodeStack.pop();      currentPrefix = prefixStack.pop();       for (k in currentNode) {        if (k === SENTINEL) {          hasValue = true;          continue;        }         nodeStack.push(currentNode[k]);        prefixStack.push(isString ? currentPrefix + k : currentPrefix.concat(k));      }       if (hasValue)        return {done: false, value: [currentPrefix, currentNode[SENTINEL]]};    }     return {done: true};  });}; /** * Attaching the #.entries method to Symbol.iterator if possible. */if (typeof Symbol !== 'undefined')  TrieMap.prototype[Symbol.iterator] = TrieMap.prototype.entries; /** * Convenience known methods. */TrieMap.prototype.inspect = function() {  var proxy = new Array(this.size);   var iterator = this.entries(),      step,      i = 0;   while ((step = iterator.next(), !step.done))    proxy[i++] = step.value;   // Trick so that node displays the name of the constructor  Object.defineProperty(proxy, 'constructor', {    value: TrieMap,    enumerable: false  });   return proxy;}; if (typeof Symbol !== 'undefined')  TrieMap.prototype[Symbol.for('nodejs.util.inspect.custom')] = TrieMap.prototype.inspect; TrieMap.prototype.toJSON = function() {  return this.root;}; /** * Static @.from function taking an arbitrary iterable & converting it into * a trie. * * @param  {Iterable} iterable   - Target iterable. * @return {TrieMap} */TrieMap.from = function(iterable) {  var trie = new TrieMap();   forEach(iterable, function(value, key) {    trie.set(key, value);  });   return trie;}; /** * Exporting. */TrieMap.SENTINEL = SENTINEL;module.exports = TrieMap;