@superhuman/trie-ing - npm Package Compare versions

Comparing version 0.5.5 to 0.5.6

lib/node.js

@@ -48,3 +48,3 @@ /**
     for (var i = 0; i < oldValues.length; i++) {
-      var item = oldValues[i],
+      let item = oldValues[i],
         chr = item.key[index];
@@ -179,10 +179,9 @@
 Node.prototype._deleteRecursive = function (key, distinct, index) {
-  if (index === key.length || this.leaf) {
+  if (this.leaf) {
     // If the index matches the key length, we are at the node to be deleted.
     // Remove values associated with the key, where the `distinct` value also matches.
-    this.values = this.values.filter((item) => (item.key !== key && item.distinct !== distinct));
+    this.values = this.values.filter(
+      (item) => !(item.key === key && item.distinct === distinct)
+    );
 
-    // If the node becomes a leaf node, update its status.
-    this.leaf = this.values.length > 0;
-
     // If the node has no values or children, it can be pruned from the tree.
@@ -197,2 +196,9 @@ if (this.values.length === 0 && Object.keys(this.children).length === 0) {
 
+  if (index === key.length) {
+    if (this.children[undefined]) {
+      this.children[undefined]._deleteRecursive(key, distinct, index + 1);
+    }
+    return this;
+  }
+
   const chr = key[index];
@@ -205,3 +211,7 @@ if (!this.children[chr]) {
   // Recursively traverse the tree to find the node to delete.
-  this.children[chr] = this.children[chr]._deleteRecursive(key, distinct, index + 1);
+  this.children[chr] = this.children[chr]._deleteRecursive(
+    key,
+    distinct,
+    index + 1
+  );
 
@@ -211,2 +221,6 @@ // If the child node has no values or children after deletion, remove it.
     delete this.children[chr];
+    const charIdx = this.values.indexOf(chr);
+    if (charIdx >= 0) {
+      this.values.splice(charIdx, 1);
+    }
   }
@@ -231,4 +245,3 @@
 };
-  
 
 module.exports = Node;

package.json

 {
   "name": "@superhuman/trie-ing",
-  "version": "0.5.5",
+  "version": "0.5.6",
   "description": "A fast weighted autocompleter",
@@ -5,0 +5,0 @@ "main": "index.js",

test/trie_test.js

@@ -16,5 +16,5 @@ var assert = require("assert");
 
-    assert.equal(1, t.prefixSearch("o")[0]);
-    assert.equal(1, t.prefixSearch("on")[0]);
-    assert.equal(1, t.prefixSearch("one")[0]);
+    assert.equal(t.prefixSearch("o")[0], 1);
+    assert.equal(t.prefixSearch("on")[0], 1);
+    assert.equal(t.prefixSearch("one")[0], 1);
   });
@@ -86,8 +86,8 @@
     assert.deepEqual(
-      [4, 2, 1],
-      t.prefixSearch("a", { limit: 3, unique: true })
+      t.prefixSearch("a", { limit: 3, unique: true }),
+      [4, 2, 1]
     );
     assert.deepEqual(
-      [4, 3, 2],
-      t.prefixSearch("a", { limit: 3, unique: false })
+      t.prefixSearch("a", { limit: 3, unique: false }),
+      [4, 3, 2]
     );
@@ -106,3 +106,3 @@ });
 
-    assert.deepEqual([], t.prefixSearch("gb"));
+    assert.deepEqual(t.prefixSearch("gb"), []);
   });
@@ -124,3 +124,3 @@
 
-    assert.deepEqual([4], t.prefixSearch("abc", { limit: 1 }));
+    assert.deepEqual(t.prefixSearch("abc", { limit: 1 }), [4]);
   });
@@ -142,3 +142,3 @@
 
-    assert.deepEqual([2], t.prefixSearch("sha"));
+    assert.deepEqual(t.prefixSearch("sha"), [2]);
   });
@@ -167,3 +167,3 @@
 
-    assert.deepEqual([1, 1, 1], t.prefixSearch("a", { unique: true }));
+    assert.deepEqual(t.prefixSearch("a", { unique: true }), [1, 1, 1]);
   });
@@ -188,3 +188,3 @@
 
-    assert.deepEqual([2, 1], t.prefixSearch("a", { unique: true }));
+    assert.deepEqual(t.prefixSearch("a", { unique: true }), [2, 1]);
   });
@@ -216,3 +216,3 @@
 
-    assert.deepEqual([3, 1], t.prefixSearch("a", { unique: true, limit: 2 }));
+    assert.deepEqual(t.prefixSearch("a", { unique: true, limit: 2 }), [3, 1]);
   });
@@ -245,2 +245,3 @@
     assert.deepEqual(
+      results.map((result) => result.email),
       [
@@ -252,4 +253,3 @@ "[e-mail]",
         "[e-mail]"
-      ],
-      results.map((result) => result.email)
+      ]
     );
@@ -259,2 +259,3 @@
     assert.deepEqual(
+      results.map((result) => result.email),
       [
@@ -266,4 +267,3 @@ "[e-mail]",
         "[e-mail]"
-      ],
-      results.map((result) => result.email)
+      ]
     );
@@ -273,2 +273,3 @@
     assert.deepEqual(
+      results.map((result) => result.email),
       [
@@ -280,4 +281,3 @@ "[e-mail]",
         "[e-mail]"
-      ],
-      results.map((result) => result.email)
+      ]
     );
@@ -287,4 +287,4 @@
     assert.deepEqual(
-      ["[e-mail]"],
-      results.map((result) => result.email)
+      results.map((result) => result.email),
+      ["[e-mail]"]
     );
@@ -318,2 +318,3 @@ });
     assert.deepEqual(
+      results.map((result) => result.email),
       [
@@ -325,4 +326,3 @@ "[e-mail]",
         "[e-mail]"
-      ],
-      results.map((result) => result.email)
+      ]
     );
@@ -338,2 +338,3 @@
     assert.deepEqual(
+      results.map((result) => result.email),
       [
@@ -345,4 +346,3 @@ "[e-mail]",
         "[e-mail]"
-      ],
-      results.map((result) => result.email)
+      ]
     );
@@ -352,4 +352,4 @@
     assert.deepEqual(
-      ["[e-mail]", "[e-mail]"],
-      results.map((result) => result.email)
+      results.map((result) => result.email),
+      ["[e-mail]", "[e-mail]"]
     );
@@ -364,4 +364,4 @@
     assert.deepEqual(
-      ["[e-mail]"],
-      results.map((result) => result.email)
+      results.map((result) => result.email),
+      ["[e-mail]"]
     );
@@ -371,2 +371,3 @@
     assert.deepEqual(
+      results.map((result) => result.email),
       [
@@ -378,4 +379,3 @@ "[e-mail]",
         "[e-mail]"
-      ],
-      results.map((result) => result.email)
+      ]
     );
@@ -389,2 +389,3 @@
     assert.deepEqual(
+      results.map((result) => result.email),
       [
@@ -396,4 +397,3 @@ "[e-mail]",
         "[e-mail]"
-      ],
-      results.map((result) => result.email)
+      ]
     );
@@ -403,4 +403,4 @@
     assert.deepEqual(
-      ["[e-mail]"],
-      results.map((result) => result.email)
+      results.map((result) => result.email),
+      ["[e-mail]"]
     );
@@ -414,6 +414,118 @@
     assert.deepEqual(
-      [],
-      results.map((result) => result.email)
+      results.map((result) => result.email),
+      []
     );
   });
+
+  it("should delete values from a narrow and shallow trie", () => {
+    const trie = new Trie({ maxWidth: 3 });
+    trie.add({ key: "a", distinct: "a", score: 1, value: "a" });
+    trie.add({ key: "aa", distinct: "aa", score: 1, value: "aa" });
+    trie.add({ key: "ab", distinct: "ab", score: 1, value: "ab" });
+    trie.add({ key: "ba", distinct: "ba", score: 1, value: "ba" });
+    trie.add({ key: "bb", distinct: "bb", score: 1, value: "bb" });
+    const results = trie.prefixSearch("a");
+    assert.equal(results.length, 3);
+    assert.equal(results.includes("a"), true);
+    assert.equal(results.includes("aa"), true);
+    assert.equal(results.includes("ab"), true);
+
+    trie.delete("a", "a");
+    assert.equal(trie.prefixSearch("a").length, 2);
+    assert.equal(trie.prefixSearch("a").includes("a"), false);
+    trie.delete("ab", "ab");
+    assert.equal(trie.prefixSearch("a").length, 1);
+
+    const alphabet = ["a", "b", "c"];
+    const alphabetSize = alphabet.length + 1;
+    const trie2 = new Trie({ maxWidth: alphabetSize });
+    trie2.add({ key: "a", distinct: "a", score: 1, value: "a" });
+    trie2.add({ key: "aa", distinct: "aa", score: 1, value: "aa" });
+    trie2.add({ key: "ab", distinct: "ab", score: 1, value: "ab" });
+    trie2.add({ key: "ac", distinct: "ac", score: 1, value: "ac" });
+    trie2.add({ key: "ba", distinct: "ba", score: 1, value: "ba" });
+    trie2.add({ key: "bb", distinct: "bb", score: 1, value: "bb" });
+    trie2.add({ key: "bc", distinct: "bc", score: 1, value: "bc" });
+    trie2.add({ key: "ca", distinct: "ca", score: 1, value: "ca" });
+    trie2.add({ key: "cb", distinct: "cb", score: 1, value: "cb" });
+    trie2.add({ key: "cc", distinct: "cc", score: 1, value: "cc" });
+
+    assert.equal(trie2.prefixSearch("a").length, 4);
+    assert.equal(trie2.prefixSearch("a")[0], "a");
+    assert.equal(trie2.prefixSearch("a")[1], "aa");
+    assert.equal(trie2.prefixSearch("a")[2], "ab");
+    assert.equal(trie2.prefixSearch("a")[3], "ac");
+    assert.equal(trie2.prefixSearch("aa").length, 1);
+    assert.equal(trie2.prefixSearch("aa")[0], "aa");
+    assert.equal(trie2.prefixSearch("b").length, 3);
+
+    trie2.delete("bb", "bb");
+    assert.equal(trie2.prefixSearch("bb").length, 0);
+    trie2.delete("cb", "cb");
+    assert.equal(trie2.prefixSearch("cb").length, 0);
+    trie2.add({ key: "bb", distinct: "bb", score: 1, value: "bb" });
+    assert.equal(trie2.prefixSearch("bb").length, 1);
+  });
+
+  it("should delete values from a wide and deep trie", () => {
+    // here, rather than manually constructing a trie and making assertions
+    // we construct an arbitrarily wide and deep tree
+    // that includes every generated string in a given range
+    // we then delete every string with a "b" in it
+    // then, we exhaustively test every string as a prefix, and affirm everything is present
+    // by nature, this test is slower
+
+    const width = 26;
+    const depth = 3;
+
+    const alpha = Array.from(Array(width)).map((e, i) => i + 65);
+    const alphabet = alpha.map((x) => String.fromCharCode(x));
+    const alphabetSize = alphabet.length + 1;
+    const bannedCharacter = alphabet[1];
+
+    const trie = new Trie({ maxWidth: alphabetSize });
+    const add = (email) => {
+      trie.add({
+        key: email,
+        distinct: email,
+        score: 1,
+        value: email
+      });
+    };
+    const forABunchOfStrings = (callback, d = depth) => {
+      if (d > 0) {
+        alphabet.forEach((a) => {
+          callback(`${a}`);
+          forABunchOfStrings((c) => {
+            callback(`${c}${a}`);
+          }, d - 1);
+        });
+      }
+    };
+    forABunchOfStrings((str) => add(str));
+    forABunchOfStrings((str) => {
+      if (str.indexOf(bannedCharacter) >= 0) {
+        trie.delete(str, str);
+      }
+    });
+
+    // search for every string
+    // limit depth, cause we're recursing on a recurse = SLOW
+    forABunchOfStrings((str) => {
+      if (str.indexOf(bannedCharacter) >= 0) {
+        assert.equal(trie.prefixSearch(bannedCharacter).includes(str), false);
+        assert.equal(trie.prefixSearch(str).includes(str), false);
+      } else {
+        let prefix = "";
+        for (let i = 0; i < str.length; i++) {
+          prefix += str[i];
+          assert.equal(trie.prefixSearch(prefix).includes(str), true);
+        }
+      }
+    }, 2);
+
+    assert.equal(trie.prefixSearch("b").length, 0);
+    assert.equal(trie.prefixSearch("bb").length, 0);
+    assert.equal(trie.prefixSearch("bbb").length, 0);
+  });
 });

New alerts

New author

Supply chain risk

A new npm collaborator published a version of the package for the first time. New collaborators are usually benign additions to a project, but do indicate a change to the security surface area of a package.

Found 1 instance in 1 package

Fixed alerts

New author

Supply chain risk

A new npm collaborator published a version of the package for the first time. New collaborators are usually benign additions to a project, but do indicate a change to the security surface area of a package.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

10832808

increased by0.04%

Lines of code

1813

increased by6.77%

No dependency changes