trie-ing - npm Package Compare versions

Comparing version 0.2.0 to 0.3.0

index.js

@@ -19,2 +19,3 @@ Node = require('./lib/node');
  * a .value property that is opaque (and returned by the prefixSearch method)
+ * a .distinct property that is used to distinguish between multiple values that have the same key.
  */
@@ -50,3 +51,3 @@ Trie.prototype.add = function (item) {
     if (node) {
-        node.getSortedResults(opts.limit, results, new PQueue(opts.limit, !!opts.unique));
+        node.getSortedResults(results, opts, new PQueue(opts.limit));
     }
@@ -53,0 +54,0 @@

lib/node.js

@@ -104,3 +104,3 @@ /**
 
-    if (this.tail && this.tail.key.indexOf(key.slice(index)) === 0) {
+    if (this.tail && this.tail.key.slice(index).indexOf(key.slice(index)) === 0) {
         return this;
@@ -126,4 +126,6 @@ }
  */
-Node.prototype.getSortedResults = function (limit, results, pqueue) {
+Node.prototype.getSortedResults = function (results, opts, pqueue) {
 
+    var seenKeys = {};
+
     pqueue.addList([this]);
@@ -146,5 +148,8 @@
         } else {
-            results.push(next.value);
+            if (!opts.unique || !seenKeys[next.key + (next.distinct ? next.distinct : "")]) {
+                seenKeys[next.key] = true;
+                results.push(next.value);
+            }
 
-            if (results.length === limit) {
+            if (results.length === opts.limit) {
                 return;
@@ -151,0 +156,0 @@ }

lib/pqueue.js

@@ -1,3 +0,1 @@
-Node = require('./node')
-
 /* A PQueue with a limited size.
@@ -13,3 +11,2 @@ *
     this.limit = limit;
-    this.unique = unique;
 }
@@ -21,36 +18,31 @@
 
-    var noMoreItems = false;
+    // effectiveLength is the lower bound on the number of
+    // item's we're guaranteed to be able to find in the trie.
+    // In the case that unique is false this is the same as the length,
+    // but in the case unique is true, it's the number of Nodes in the queue
+    // (as items may be discarded).
+    var effectiveLength = 0;
 
-    while (i < this.todo.length && i < this.limit && j < list.length) {
+    while (i < this.todo.length && effectiveLength < this.limit) {
 
-        if (this.todo[i].score < list[j].score) {
-            if (!(noMoreItems && !(list[j] instanceof Node))) {
-                this.todo.splice(i, 0, list[j]);
-                noMoreItems = this.unique;
-                i += 1;
-            }
+        if (j < list.length && this.todo[i].score < list[j].score) {
+            this.todo.splice(i, 0, list[j]);
             j += 1;
-        } else {
-            i += 1;
         }
 
-        if (this.unique && !(list[j] instanceof Node)) {
-            noMoreItems = true;
+        if (this.todo[i] instanceof Node) {
+            effectiveLength += 1;
         }
-    }
 
-    while (this.todo.length < this.limit && j < list.length) {
-        if (!(noMoreItems && !(list[j] instanceof Node))) {
-            this.todo.push(list[j]);
-        }
-        j += 1;
-
-        if (this.unique && !(list[j] instanceof Node)) {
-            noMoreItems = true;
-        }
+        i += 1;
     }
 
-    while (this.todo.length > this.limit) {
+    while (this.todo.length > i) {
         this.todo.pop();
     }
+
+    while (effectiveLength < this.limit && j < list.length) {
+        this.todo.push(list[j]);
+        j += 1;
+    }
 }
@@ -57,0 +49,0 @@

package.json

 {
   "name": "trie-ing",
-  "version": "0.2.0",
+  "version": "0.3.0",
   "description": "The trie from node-autocompleter in a form that can be used in browser",
@@ -5,0 +5,0 @@ "main": "index.js",

test/trie_test.js

@@ -123,3 +123,67 @@ var assert = require('assert');
     });
+
+    it("should be able to prefix match with tails", function () {
+
+        t = new Trie();
+        t.add({
+            key: 'sarah',
+            value: 1,
+            score: 1
+        });
+
+        t.add({
+            key: 'shashi',
+            value: 2,
+            score: 2
+        });
+
+        assert.deepEqual([2], t.prefixSearch("sha"));
+    });
+
+    it("should be able to unique even if multiple values have the same score", function () {
+        t = new Trie()
+
+        t.add({
+            key: "abc",
+            value: 1,
+            score: 1
+        });
+
+        t.add({
+            key: "acc",
+            value: 1,
+            score: 1
+        });
+
+        t.add({
+            key: "abb",
+            value: 1,
+            score: 1
+        });
+
+        assert.deepEqual([1,1,1], t.prefixSearch("a", {unique: true}));
+
+    });
+
+    it("should be able to distinguish between distinct keys", function () {
+        var t = new Trie();
+
+        t.add({
+            key: "aaa",
+            distinct: "b",
+            score: 1,
+            value: 1
+        });
+
+        t.add({
+            key: "aaa",
+            distinct: "c",
+            score: 2,
+            value: 2
+        });
+
+        assert.deepEqual([2,1], t.prefixSearch("a", {unique: true}))
+
+    });
 });
 

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

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

Improved metrics

Total package byte prevSize

7578528

increased by49310.14%

Number of package files

12

increased by33.33%

Lines of code

1424

increased by297.77%

Number of medium supply chain risk alerts

0

decreased by-100%

No dependency changes