cspell-trie-lib - npm Package Compare versions

Comparing version 4.1.2 to 4.1.4

dist/lib/TrieBuilder.d.ts

@@ -11,2 +11,3 @@ import { Trie } from './trie';
     private lastPath;
+    private tails;
     constructor(words?: Iterable<string>);
@@ -22,2 +23,3 @@ private set _root(value);
     private addChild;
+    private buildTail;
     private _insert;
@@ -24,0 +26,0 @@ insertWord(word: string): void;

dist/lib/TrieBuilder.js

@@ -18,2 +18,3 @@ "use strict";
         this.lastPath = [{ s: '', n: { f: undefined, c: undefined } }];
+        this.tails = new Map([['', this._eow]]);
         this._canBeCached(this._eow); // this line is just for coverage reasons
@@ -63,2 +64,3 @@ this.signatures.set(this.signature(this._eow), this._eow);
             n.c = new Map(c);
+            Object.freeze(n.c);
         }
@@ -97,4 +99,20 @@ return Object.freeze(n);
     }
+    buildTail(s) {
+        if (this.tails.has(s)) {
+            return this.tails.get(s);
+        }
+        const head = s[0];
+        const tail = s.slice(1);
+        const t = this.tails.get(tail);
+        const c = t || this.buildTail(tail);
+        const n = this.addChild({ f: undefined, c: undefined }, head, c);
+        if (!t) {
+            return n;
+        }
+        const cachedNode = this.tryCacheFrozen(Object.freeze(n));
+        this.tails.set(s, cachedNode);
+        return cachedNode;
+    }
     _insert(node, s, d) {
-        var _a, _b, _c;
+        var _a, _b;
         const orig = node;
@@ -112,3 +130,3 @@ if (Object.isFrozen(node)) {
             else {
-                node = Object.isFrozen(node) ? Object.assign({}, node) : node;
+                node = copyIfFrozen(node);
                 node.f = this._eow.f;
@@ -120,3 +138,4 @@ return node;
         const tail = s.slice(1);
-        const child = this._insert((_c = (_b = node.c) === null || _b === void 0 ? void 0 : _b.get(head), (_c !== null && _c !== void 0 ? _c : { f: undefined, c: undefined })), tail, d + 1);
+        const cNode = (_b = node.c) === null || _b === void 0 ? void 0 : _b.get(head);
+        const child = cNode ? this._insert(cNode, tail, d + 1) : this.buildTail(tail);
         node = this.addChild(node, head, child);
@@ -129,5 +148,4 @@ this.storeTransform(orig, s, node);
         var _a;
-        const letters = word.split('');
         let d = 1;
-        for (const s of letters) {
+        for (const s of word.split('')) {
             const p = this.lastPath[d];
@@ -180,2 +198,8 @@ if (((_a = p) === null || _a === void 0 ? void 0 : _a.s) !== s)
 exports.TrieBuilder = TrieBuilder;
+function copyIfFrozen(n) {
+    if (!Object.isFrozen(n))
+        return n;
+    const c = n.c ? new Map(n.c) : undefined;
+    return { f: n.f, c };
+}
 //# sourceMappingURL=TrieBuilder.js.map

dist/lib/util.d.ts

@@ -24,1 +24,3 @@ import { Sequence } from 'gensequence';
 export declare function findNode(node: TrieNode, prefix: string): TrieNode | undefined;
+export declare function countNodes(root: TrieNode): number;
+export declare function isCircular(root: TrieNode): boolean;

dist/lib/util.js

@@ -90,2 +90,44 @@ "use strict";
 exports.findNode = findNode;
+function countNodes(root) {
+    const seen = new Set();
+    function walk(n) {
+        if (seen.has(n))
+            return;
+        seen.add(n);
+        if (n.c) {
+            [...n.c.values()].forEach(n => walk(n));
+        }
+    }
+    walk(root);
+    return seen.size;
+}
+exports.countNodes = countNodes;
+function isCircular(root) {
+    const seen = new Set();
+    const inStack = new Set();
+    function walk(n) {
+        if (seen.has(n))
+            return { isCircular: false, allSeen: true };
+        if (inStack.has(n))
+            return { isCircular: true, allSeen: false };
+        inStack.add(n);
+        let r = { isCircular: false, allSeen: true };
+        if (n.c) {
+            r = [...n.c.values()].reduce((acc, n) => {
+                if (acc.isCircular)
+                    return acc;
+                const r = walk(n);
+                r.allSeen = r.allSeen && acc.allSeen;
+                return r;
+            }, r);
+        }
+        if (r.allSeen) {
+            seen.add(n);
+        }
+        inStack.delete(n);
+        return r;
+    }
+    return walk(root).isCircular;
+}
+exports.isCircular = isCircular;
 //# sourceMappingURL=util.js.map

package.json

 {
   "name": "cspell-trie-lib",
-  "version": "4.1.2",
+  "version": "4.1.4",
   "description": "Trie Data Structure to support cspell.",
@@ -36,4 +36,3 @@ "main": "dist/index.js",
   "dependencies": {
-    "gensequence": "^3.0.1",
-    "js-xxhash": "^1.0.4"
+    "gensequence": "^3.0.1"
   },
@@ -61,3 +60,3 @@ "nyc": {
   },
-  "gitHead": "f0658565489fa4a2fd38e2f31820ce9fbbe9bfba"
+  "gitHead": "92b46011da8467d15c7969aab4572a8639e3f685"
 }

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

73236

increased by2.68%

Dependency count

1

decreased by-50%

Lines of code

1961

increased by3.7%

Dependency changes

• - Removedjs-xxhash@^1.0.4

• - Removedjs-xxhash@1.0.4(transitive)