trie-search - npm Package Compare versions

Comparing version 1.0.9 to 1.1.0

package.json

@@ -6,3 +6,3 @@ {
   "description": "A trie implementation that maps keys to objects for rapid retrieval by phrases. Most common use will be for typeahead searches.",
-  "version": "1.0.9",
+  "version": "1.1.0",
   "main": "index.js",
@@ -9,0 +9,0 @@ "url": "https://github.com/joshjung/trie-search",

README.md

@@ -81,3 +81,3 @@ ![](https://nodei.co/npm/trie-search.png?downloads=True&stars=True)
 
-Example 2 (deep key lookup)
+Example 3 (deep key lookup)
 ======================
@@ -103,3 +103,3 @@
 
-Example 3 (options.min == 3)
+Example 4 (options.min == 3)
 ======================
@@ -126,3 +126,3 @@
     
-Example 4 (options.indexField = 'ix')
+Example 5 (options.indexField = 'ix')
 ======================
@@ -149,3 +149,3 @@
 
-Example 5 (get() OR of multiple phrases)
+Example 6 (get() OR of multiple phrases)
 ======================
@@ -172,5 +172,29 @@
 
+Example 7 (get() AND multiple phrases custom reducer / accumulator)
+======================
+
+    var TrieSearch = require('trie-search');
+    
+    var arr = [
+      {name: 'andrew', age: 21, zip: 60600, id: 1}, // person1
+      {name: 'andrew', age: 37, zip: 60601, id: 2}, // person2
+      {name: 'andrew', age: 25, zip: 60602, id: 3}, // person3
+      {name: 'andrew', age: 37, zip: 60603, id: 4}  // person4
+    ];
+
+    var ts = new TrieSearch(['name', 'age', 'zip'], {
+      idFieldOrFunction: 'id' // Required to uniquely identify during union (AND)
+    });
+
+    ts.addAll(arr);
+
+    ts.get(['andrew', '25'], TrieSearch.UNION_REDUCER); // [person3]
+    ts.get(['andrew', '50'], TrieSearch.UNION_REDUCER); // []
+    ts.get(['andrew', '37'], TrieSearch.UNION_REDUCER); // [person2, person4]
+
 Testing
 =======
 
+    npm i -g mocha
+
     >mocha
@@ -182,3 +206,3 @@
 
-      59 passing (25ms)
+      67 passing (25ms)
 
@@ -185,0 +209,0 @@ License

src/TrieSearch.js

@@ -16,2 +16,3 @@ var HashArray = require('hasharray');
   this.options.keepAllKey = this.options.hasOwnProperty('keepAllKey') ? this.options.keepAllKey : 'id';
+  this.options.idFieldOrFunction = this.options.hasOwnProperty('idFieldOrFunction') ? this.options.idFieldOrFunction : undefined;
 
@@ -210,7 +211,12 @@ this.keyFields = keyFields ? (keyFields instanceof Array ? keyFields : [keyFields]) : [];
   },
-  get: function (phrases) {
+  get: function (phrases, reducer) {
     var self = this,
       haKeyFields = this.options.indexField ? [this.options.indexField] : this.keyFields,
-      ret = undefined;
+      ret = undefined,
+      accumulator = undefined;
 
+    if (reducer && !this.options.idFieldOrFunction) {
+      throw new Error('To use the accumulator, you must specify and idFieldOrFunction');
+    }
+
     phrases = (phrases instanceof Array) ? phrases : [phrases];
@@ -220,10 +226,58 @@
     {
-      var temp = this._get(phrases[i]);
-      ret = ret ? ret.addAll(temp) : new HashArray(haKeyFields).addAll(temp);
+      var matches = this._get(phrases[i]);
+
+      if (reducer) {
+        accumulator = reducer(accumulator, phrases[i], matches, this);
+      } else {
+        ret = ret ? ret.addAll(matches) : new HashArray(haKeyFields).addAll(matches);
+      }
     }
-    
-    return ret.all;
+
+    if (!reducer) {
+      return ret.all;
+    }
+
+    return accumulator;
+  },
+  getId: function (item) {
+    return typeof this.options.idFieldOrFunction === 'function' ? this.options.idFieldOrFunction(item) : item[this.options.idFieldOrFunction];
   }
 };
 
+TrieSearch.UNION_REDUCER = function(accumulator, phrase, matches, trie) {
+  if (accumulator === undefined) {
+    return matches;
+  }
+
+  var map = {}, i, id;
+  var maxLength = Math.max(accumulator.length, matches.length);
+  var results = [];
+  var l = 0;
+
+  // One loop, O(N) for max length of accumulator or matches.
+  for (i = 0; i < maxLength; i++) {
+    if (i < accumulator.length) {
+      id = trie.getId(accumulator[i]);
+      map[id] = map[id] ? map[id] : 0;
+      map[id]++;
+
+      if (map[id] === 2) {
+        results[l++] = accumulator[i];
+      }
+    }
+
+    if (i < matches.length) {
+      id = trie.getId(matches[i]);
+      map[id] = map[id] ? map[id] : 0;
+      map[id]++;
+
+      if (map[id] === 2) {
+        results[l++] = matches[i];
+      }
+    }
+  }
+
+  return results;
+};
+
 module.exports = TrieSearch;

test/TrieSearchTest.js

@@ -513,2 +513,88 @@ var assert = require('assert'),
   });
+
+  describe('TrieSearch::get(...) should work with a custom reducer and accumulator', function() {
+    var ts = new TrieSearch('key', {
+        min: 2,
+        idFieldOrFunction: 'key'
+    }),
+      item1 = {key: 'I am red robin!'},
+      item2 = {key: 'I am red cockatiel!'},
+      item3 = {key: 'I am green cardinal!'},
+      item4 = {key: 'I am green owl!'},
+      item5 = {key: 'robin cockatiel cardinal owl!'};
+
+    ts.add(item1);
+    ts.add(item2);
+    ts.add(item3);
+    ts.add(item4);
+    ts.add(item5);
+
+    it('get(\'robin\', [reducer])', function() {
+      let result = ts.get('robin', function(_accumulator, phrase, phraseMatches, trie) {
+        assert(_accumulator === undefined, 'accumulator should be undefined on first pass for first phrase');
+        assert(phrase === 'robin', 'phrase was incorrect');
+        assert(phraseMatches.length === 2, 'phraseMatches length is incorrect');
+        assert(phraseMatches[0] === item5, 'wrong phraseMatches returned');
+        assert(phraseMatches[1] === item1, 'wrong phraseMatches returned');
+        assert(trie === ts, 'Trie did not equal ts');
+
+        _accumulator = _accumulator || [];
+        _accumulator.push(phraseMatches[1]);
+        _accumulator.push(phraseMatches[0]);
+
+        return _accumulator;
+      });
+
+      assert(result.length === 2, 'result has incorrect length: ' + result.length);
+      assert(result[0] === item1, 'result has incorrect items');
+      assert(result[1] === item5, 'result has incorrect items');
+    });
+
+    it('get([\'red\', \'robin\'], TrieSearch.UNION_REDUCER)', function() {
+      let result = ts.get(['red', 'robin'], TrieSearch.UNION_REDUCER);
+
+      assert(result.length, 'result has incorrect length: ' + result.length);
+      assert(result[0] === item1, 'result has incorrect items');
+    });
+
+    it('get([\'green\'], TrieSearch.UNION_REDUCER)', function() {
+      let result = ts.get(['green'], TrieSearch.UNION_REDUCER);
+
+      assert(result.length === 2, 'result has incorrect length');
+      assert(result[0] === item3, 'result has incorrect items');
+      assert(result[1] === item4, 'result has incorrect items');
+    });
+
+    it('get(\'green\', TrieSearch.UNION_REDUCER)', function() {
+      let result = ts.get('green', TrieSearch.UNION_REDUCER);
+
+      assert(result.length === 2, 'result has incorrect length');
+      assert(result[0] === item3, 'result has incorrect items');
+      assert(result[1] === item4, 'result has incorrect items');
+    });
+
+    it('get(\'blue\', TrieSearch.UNION_REDUCER)', function() {
+      let result = ts.get('blue', TrieSearch.UNION_REDUCER);
+
+      assert(result.length === 0, 'result has incorrect length');
+    });
+
+    it('get(\'am\', TrieSearch.UNION_REDUCER)', function() {
+      let result = ts.get('am', TrieSearch.UNION_REDUCER);
+
+      assert(result.length === 4, 'result has incorrect length');
+    });
+
+    it('get([\'owl\', \'card\', \'cock\', \'rob\'], TrieSearch.UNION_REDUCER)', function() {
+      let result = ts.get(['owl', 'card', 'cock', 'rob'], TrieSearch.UNION_REDUCER);
+
+      assert(result.length === 1, 'result has incorrect length: ' + result.length);
+    });
+
+    it('get([\'owl\', \'card\', \'cock\', \'rob\', \'fubar\'], TrieSearch.UNION_REDUCER)', function() {
+      let result = ts.get(['owl', 'card', 'cock', 'rob', 'fubar'], TrieSearch.UNION_REDUCER);
+
+      assert(result.length === 0, 'result has incorrect length: ' + result.length);
+    });
+  });
 });

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

8999276

increased by0.06%

Lines of code

1722

increased by6.82%

Number of lines in readme file

227

increased by11.82%

No dependency changes