fast-matcher - npm Package Compare versions

Comparing version 0.2.1 to 0.3.0

fastMatcher.js

@@ -11,9 +11,14 @@ (function() {
   function FastMatcher(list, options) {
-    this.list     = this.wrapList(list);
+    var source    = this.source = this.wrapList(list);
     this.options  = options || {};
     this.matches  = this.options.matches || [];
 
-    var selector = this.selector = this.createSelector();
-    this.list.sort(function(x, y) {
-      return compare(selector(x.val), selector(y.val));
+    var selectors = this.selectors = this.createSelectors();
+    this.lists = selectors.map(function(selector) {
+      var list = source.slice(0);
+      list.sort(function(x, y) {
+        return compare(selector(x.val), selector(y.val));
+      });
+      list.selector = selector;
+      return list;
     });
@@ -25,6 +30,6 @@ }
    * function wrapList(list) {
-   *   return new FastMatcher(list).list;
+   *   return new FastMatcher([]).wrapList(list);
    * }
    *
-   * wrapList([5, 3, 4]); // => [{i:1,val:3},{i:2,val:4},{i:0,val:5}]
+   * wrapList([5, 3, 4]); // => [{i:0,val:5},{i:1,val:3},{i:2,val:4}]
    */
@@ -37,33 +42,36 @@ FastMatcher.prototype.wrapList = function wrapList(list) {
    * @example
-   * function createSelector(property) {
-   *   return new FastMatcher([], { selector: property }).createSelector();
+   * function createSelectors(selector) {
+   *   return new FastMatcher([], { selector: selector }).createSelectors();
    * }
    *
-   * createSelector()('foo');
+   * createSelectors()[0]('foo');
    * // => 'foo'
    *
-   * createSelector('x')({ x: 'bar'});
+   * createSelectors('x')[0]({ x: 'bar'});
    * // => 'bar'
    *
-   * createSelector(function(str) { return str.slice(1); })('foo');
+   * createSelectors(function(str) { return str.slice(1); })[0]('foo');
    * // => 'oo'
+   *
+   * createSelectors(['x', 'y'])[0]({ x: 'foo', y: 'bar' });
+   * // => 'foo'
+   *
+   * createSelectors(['x', 'y'])[1]({ x: 'foo', y: 'bar' });
+   * // => 'bar'
    */
-  FastMatcher.prototype.createSelector = function createSelector() {
-    var baseSelector = this.getBaseSelector(this.options.selector);
+  FastMatcher.prototype.createSelectors = function createSelectors() {
+    var options   = this.options,
+        selectors = options.selector;
 
-    return this.options.caseInsensitive ?
-      function(x) { return baseSelector(x).toLowerCase(); } :
-      baseSelector;
-  };
-
-  FastMatcher.prototype.getBaseSelector = function(selector) {
-    if (typeof selector === 'function') {
-      return selector;
+    if (!(selectors instanceof Array)) {
+      selectors = [selectors];
     }
 
-    if (selector) {
-      return function(x) { return x[selector]; };
-    }
+    return selectors.map(function(selector) {
+      var baseSelector = getBaseSelector(selector);
 
-    return function(x) { return x; };
+      return options.caseInsensitive ?
+        function(x) { return baseSelector(x).toLowerCase(); } :
+        baseSelector;
+    });
   };
@@ -88,2 +96,17 @@
    * // => ['aa', 'ab']
+   *
+   * getMatches([{x:'a',y:'b'},{x:'b',y:'a'}], 'a', { selector: ['x', 'y'] });
+   * // => [{x:'a',y:'b'},{x:'b',y:'a'}]
+   *
+   * getMatches([{x:'a'},{y:'a'}], 'a', { selector: ['x', 'y'] });
+   * // => [{x:'a'},{y:'a'}]
+   *
+   * getMatches([{x:'a',y:'a'}], 'a', { selector: ['x', 'y'] });
+   * // => [{x:'a',y:'a'}]
+   *
+   * getMatches([{x:'a',y:'a'},{x:'a',y:'b'},{x:'b',y:'a'}], 'a', { selector: ['x', 'y'], limit: 3 });
+   * // => [{x:'a',y:'a'},{x:'a',y:'b'},{x:'b',y:'a'}]
+   *
+   * getMatches([{x:'a',y:'a'},{x:'a',y:'b'},{x:'b',y:'a'},{x:'c',y:'a'}], 'a', { selector: ['x', 'y'], limit: 3 });
+   * // => [{x:'a',y:'a'},{x:'a',y:'b'},{x:'b',y:'a'}]
    */
@@ -95,10 +118,10 @@ FastMatcher.prototype.getMatches = function getMatches(prefix) {
 
-    var limit    = Number(this.options.limit || 25),
-        selector = this.selector;
+    var originalLimit = Number(this.options.limit || 25);
 
-    var list    = this.list,
-        index   = this.findIndex(prefix);
+    var limit = originalLimit,
+        lists = this.lists,
+        items = [],
+        list, index, item, itemsAdded;
 
-    var items = [], item;
-    while (index < list.length) {
+    for (var i = 0; i < lists.length; ++i) {
       if (items.length === limit) {
@@ -108,12 +131,29 @@ break;
 
-      item = selector(list[index].val);
-      if (this.options.caseInsensitive) {
-        item = item.toLowerCase();
-      }
+      list = lists[i];
+      index = this.findIndex(list, prefix);
+      itemsAdded = 0;
 
-      if (!startsWith(item, prefix)) {
-        break;
+      while (index < list.length) {
+        if (items.length === limit) {
+          break;
+        }
+
+        item = list.selector(list[index].val);
+        if (this.options.caseInsensitive) {
+          item = item.toLowerCase();
+        }
+
+        if (!startsWith(item, prefix)) {
+          break;
+        }
+
+        items.push(list[index++]);
+        ++itemsAdded;
       }
 
-      items.push(list[index++]);
+      // Say the original limit is 20 and we just found 10 more items. We now
+      // need to increase the effective limit (before removing duplicates) by 10
+      // to account for the maximum possible overlap between the matches found
+      // so far and the matches from the next list.
+      limit += itemsAdded;
     }
@@ -125,3 +165,3 @@
 
-    populate(this.matches, items.map(function(x) { return x.val; }));
+    populate(this.matches, getValues(items, originalLimit));
 
@@ -131,5 +171,4 @@ return this.matches;
 
-  FastMatcher.prototype.findIndex = function findIndex(prefix) {
-    var list     = this.list,
-        selector = this.selector,
+  FastMatcher.prototype.findIndex = function findIndex(list, prefix) {
+    var selector = list.selector,
         lower    = 0,
@@ -160,2 +199,26 @@ upper    = list.length;
    * @example
+   * getBaseSelector()('foo');
+   * // => 'foo'
+   *
+   * getBaseSelector('x')({ x: 'bar'});
+   * // => 'bar'
+   *
+   * getBaseSelector(function(str) { return str.slice(1); })('foo');
+   * // => 'oo'
+   */
+  function getBaseSelector(selector) {
+    if (typeof selector === 'function') {
+      return selector;
+    }
+
+    if (selector) {
+      return function(x) { return x[selector] || ''; };
+    }
+
+    return function(x) { return x; };
+  }
+
+  /**
+   * @private
+   * @example
    * var arr = [];
@@ -178,2 +241,24 @@ *
    * @example
+   * getValues([{i:0,val:'a'},{i:0,val:'a'},{i:1,val:'b'}], 3);
+   * // => ['a', 'b']
+   *
+   * getValues([{i:0,val:'a'},{i:1,val:'b'},{i:2,val:'c'}], 2);
+   * // => ['a', 'b']
+   */
+  function getValues(items, limit) {
+    var indexes = {}, values = [];
+
+    for (var i = 0; values.length < limit && i < items.length; ++i) {
+      if (!indexes[items[i].i]) {
+        indexes[items[i].i] = true;
+        values.push(items[i].val);
+      }
+    }
+
+    return values;
+  }
+
+  /**
+   * @private
+   * @example
    * compare('foo', 'foo'); // => 0
@@ -180,0 +265,0 @@ * compare('foo', 'bar'); // => 1

package.json

 {
   "name": "fast-matcher",
-  "version": "0.2.1",
+  "version": "0.3.0",
   "description": "Find matches fast",
@@ -5,0 +5,0 @@ "main": "fastMatcher.js",

README.md

@@ -35,3 +35,3 @@ # fast-matcher
 var matcher = new FastMatcher(list, {
-  // the property to base matches on (omit for a simple list of strings)
+  // the property, or array of properties, to base matches on
   selector: 'x',
@@ -38,0 +38,0 @@

No alert changes

Improved metrics

Total package byte prevSize

28190842

increased by0.01%

Lines of code

1623

increased by4.98%

No dependency changes