File Explorer

1/* eslint no-constant-condition: 0 */2/**3 * Mnemonist BK Tree4 * ==================5 *6 * Implementation of a Burkhard-Keller tree, allowing fast lookups of words7 * that lie within a specified distance of the query word.8 *9 * [Reference]:10 * https://en.wikipedia.org/wiki/BK-tree11 *12 * [Article]:13 * W. Burkhard and R. Keller. Some approaches to best-match file searching,14 * CACM, 197315 */16var forEach = require('obliterator/foreach');17 18/**19 * BK Tree.20 *21 * @constructor22 * @param {function} distance - Distance function to use.23 */24function BKTree(distance) {25 26  if (typeof distance !== 'function')27    throw new Error('mnemonist/BKTree.constructor: given `distance` should be a function.');28 29  this.distance = distance;30  this.clear();31}32 33/**34 * Method used to add an item to the tree.35 *36 * @param  {any} item - Item to add.37 * @return {BKTree}38 */39BKTree.prototype.add = function(item) {40 41  // Initializing the tree with the first given word42  if (!this.root) {43    this.root = {44      item: item,45      children: {}46    };47 48    this.size++;49    return this;50  }51 52  var node = this.root,53      d;54 55  while (true) {56    d = this.distance(item, node.item);57 58    if (!node.children[d])59      break;60 61    node = node.children[d];62  }63 64  node.children[d] = {65    item: item,66    children: {}67  };68 69  this.size++;70  return this;71};72 73/**74 * Method used to query the tree.75 *76 * @param  {number} n     - Maximum distance between query & item.77 * @param  {any}    query - Query78 * @return {BKTree}79 */80BKTree.prototype.search = function(n, query) {81  if (!this.root)82    return [];83 84  var found = [],85      stack = [this.root],86      node,87      child,88      d,89      i,90      l;91 92  while (stack.length) {93    node = stack.pop();94    d = this.distance(query, node.item);95 96    if (d <= n)97      found.push({item: node.item, distance: d});98 99    for (i = d - n, l = d + n + 1; i < l; i++) {100      child = node.children[i];101 102      if (child)103        stack.push(child);104    }105  }106 107  return found;108};109 110/**111 * Method used to clear the tree.112 *113 * @return {undefined}114 */115BKTree.prototype.clear = function() {116 117  // Properties118  this.size = 0;119  this.root = null;120};121 122/**123 * Convenience known methods.124 */125BKTree.prototype.toJSON = function() {126  return this.root;127};128 129BKTree.prototype.inspect = function() {130  var array = [],131      stack = [this.root],132      node,133      d;134 135  while (stack.length) {136    node = stack.pop();137 138    if (!node)139      continue;140 141    array.push(node.item);142 143    for (d in node.children)144      stack.push(node.children[d]);145  }146 147  // Trick so that node displays the name of the constructor148  Object.defineProperty(array, 'constructor', {149    value: BKTree,150    enumerable: false151  });152 153  return array;154};155 156if (typeof Symbol !== 'undefined')157  BKTree.prototype[Symbol.for('nodejs.util.inspect.custom')] = BKTree.prototype.inspect;158 159/**160 * Static @.from function taking an arbitrary iterable & converting it into161 * a tree.162 *163 * @param  {Iterable} iterable - Target iterable.164 * @param  {function} distance - Distance function.165 * @return {Heap}166 */167BKTree.from = function(iterable, distance) {168  var tree = new BKTree(distance);169 170  forEach(iterable, function(value) {171    tree.add(value);172  });173 174  return tree;175};176 177/**178 * Exporting.179 */180module.exports = BKTree;181