fast-matcher - npm Package Compare versions

Comparing version 0.1.1 to 0.2.0

fastMatcher.js

@@ -11,3 +11,3 @@ (function() {
   function FastMatcher(list, options) {
-    this.list     = list.slice(0);
+    this.list     = this.wrapList(list);
     this.options  = options || {};
@@ -18,3 +18,3 @@ this.matches  = this.options.matches || [];
     this.list.sort(function(x, y) {
-      return compare(selector(x), selector(y));
+      return compare(selector(x.val), selector(y.val));
     });
@@ -25,2 +25,14 @@ }
    * @example
+   * function wrapList(list) {
+   *   return new FastMatcher(list).list;
+   * }
+   *
+   * wrapList([5, 3, 4]); // => [{i:1,val:3},{i:2,val:4},{i:0,val:5}]
+   */
+  FastMatcher.prototype.wrapList = function wrapList(list) {
+    return list.map(function(e, i) { return { i: i, val: e }; });
+  };
+
+  /**
+   * @example
    * function createSelector(property) {
@@ -70,2 +82,5 @@ *   return new FastMatcher([], { selector: property }).createSelector();
    * // => ['aa', 'AB']
+   *
+   * getMatches(['ac', 'ab', 'b', 'aa'], 'a', { preserveOrder: true });
+   * // => ['ac', 'ab', 'aa']
    */
@@ -84,5 +99,3 @@ FastMatcher.prototype.getMatches = function getMatches(prefix) {
 
-    matches.length = 0;
-
-    var item;
+    var items = [], item;
     while (index < list.length) {
@@ -93,3 +106,3 @@ if (matches.length === limit) {
 
-      item = selector(list[index]);
+      item = selector(list[index].val);
       if (this.options.caseInsensitive) {
@@ -103,5 +116,11 @@ item = item.toLowerCase();
 
-      matches.push(list[index++]);
+      items.push(list[index++]);
     }
 
+    if (this.options.preserveOrder) {
+      items.sort(function(x, y) { return compare(x.i, y.i); });
+    }
+
+    populate(matches, items.map(function(x) { return x.val; }));
+
     return matches;
@@ -120,3 +139,3 @@ };
 
-      value = selector(list[i]);
+      value = selector(list[i].val);
       if (this.options.caseInsensitive) {
@@ -139,2 +158,19 @@ value = value.toLowerCase();
    * @example
+   * var arr = [];
+   *
+   * populate(arr, [1, 2, 3]); // arr == [1, 2, 3]
+   * populate(arr, []);        // arr == []
+   * populate(arr, ['foo']);   // arr == ['foo']
+   */
+  function populate(array, elements) {
+    var count = elements.length;
+    array.length = count;
+    for (var i = 0; i < count; ++i) {
+      array[i] = elements[i];
+    }
+  }
+
+  /**
+   * @private
+   * @example
    * compare('foo', 'foo'); // => 0
@@ -141,0 +177,0 @@ * compare('foo', 'bar'); // => 1

package.json

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

README.md

@@ -7,14 +7,9 @@ # fast-matcher
 
-This library is a simpler and **much faster** "back end" for autocompletes. It isn't as
-full-featured, which means it can make some assumptions for really big perf wins, namely:
+This library is a simpler and **much faster** "back end" for autocompletes. It isn't as full-featured, which means it can make some assumptions for really big perf wins, namely:
 
 1. It only does prefix matching.
 
-In my experience this actually makes perfect sense in a lot of cases. For example suppose your user
-is searching for a company name; they aren't going to type "o" or "e" to search for *Home Depot*. Or
-say they're using a dictionary; they aren't going to type "n" to search for *anagram*.
+In my experience this actually makes perfect sense in a lot of cases. For example suppose your user is searching for a company name; they aren't going to type "o" or "e" to search for *Home Depot*. Or say they're using a dictionary; they aren't going to type "n" to search for *anagram*.
 
-See for yourself how fast this is in practice: the [demo](http://danieltao.com/fast-matcher) uses
-this library to provide autocomplete results from [WordNet](http://wordnet.princeton.edu/), with
-close to 150,000 words. Results are pretty much instantaneous.
+See for yourself how fast this is in practice: the [demo](http://danieltao.com/fast-matcher) uses this library to provide autocomplete results from [WordNet](http://wordnet.princeton.edu/), with close to 150,000 words. Results are pretty much instantaneous.
 
@@ -24,11 +19,11 @@ ## Usage
 ```javascript
-// ----- constructor
+// constructor
 
 var matcher = new FastMatcher(list, options);
 
-// ----- getting matches
+// getting matches
 
 var matches = matcher.getMatches(prefix);
 
-// ----- full example
+// full example
 
@@ -48,2 +43,5 @@ var list = [
 
+  // return matches in their original order
+  preserveOrder: true,
+
   // how many matches to find at a time
@@ -57,4 +55,10 @@ limit: 25
 
+## How does it work?
+
+It's really not complicated. When you construct a `FastMatcher` instance, it creates a copy of the source list, sorted (by the property you specified with the `selector` option, if provided). Then when you call `getMatches` it does a binary search for the given prefix in the sorted list, and just iterates from that spot until (a) reaching the limit or (b) hitting an item that doesn't match.
+
+Binary search is really, really fast.
+
 ## Has this been done before?
 
-Probably. I don't know.
+Maybe. Probably. I don't know.

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

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

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

28188329

increased by215687.56%

Number of package files

29

increased by222.22%

Lines of code

1544

increased by638.76%

Number of lines in readme file

61

increased by7.02%

Worsened metrics

Number of low supply chain risk alerts

3

increased by200%

Number of medium supply chain risk alerts

1

increased byInfinity%

No dependency changes