search-trie - npm Package Compare versions

Comparing version 2.1.0 to 3.0.0

dist/es2015/char-trie.d.ts

@@ -1,4 +0,14 @@
-import { SearchCharTrie } from './types';
+import type { SearchTrie } from './types';
 /**
- * builds char based search trie
+ * builds a "char" based search trie.
+ * Optimized for random inputs with unpredictable variation
+ *
+ * pros:
+ * - more stable speed at large sets
+ * - every character matters, you can get the longest prefix available even without value
+ *
+ * cons:
+ * - more operations are required to perform a single search
+ *
+ * - input: array of {key:string, value}
  */
@@ -8,2 +18,2 @@ export declare const buildCharacterTrie: <T>(words: {
     value: T;
-}[], edgeDelimiter?: string) => SearchCharTrie<T>;
+}[], edgeDelimiter?: string) => SearchTrie<string, T>;

dist/es2015/char-trie.js

@@ -31,4 +31,32 @@ import { EMPTY } from './magic';
 };
+var getNearest = function (node, str) {
+    var nextNode;
+    var found = '';
+    for (var _i = 0, str_3 = str; _i < str_3.length; _i++) {
+        var c = str_3[_i];
+        nextNode = node[c];
+        if (!nextNode) {
+            return { node: node, path: found, isComplete: false };
+        }
+        found += c;
+        node = nextNode;
+    }
+    return {
+        node: node,
+        path: str,
+        isComplete: true
+    };
+};
 /**
- * builds char based search trie
+ * builds a "char" based search trie.
+ * Optimized for random inputs with unpredictable variation
+ *
+ * pros:
+ * - more stable speed at large sets
+ * - every character matters, you can get the longest prefix available even without value
+ *
+ * cons:
+ * - more operations are required to perform a single search
+ *
+ * - input: array of {key:string, value}
  */
@@ -48,2 +76,10 @@ export var buildCharacterTrie = function (words, edgeDelimiter) {
         },
+        findNearest: function (word) {
+            var _a = getNearest(root, word), node = _a.node, path = _a.path, isComplete = _a.isComplete;
+            return {
+                value: values.get(node),
+                path: path,
+                isComplete: isComplete
+            };
+        },
         get: function (word) {
@@ -50,0 +86,0 @@ var node = get(root, word);

dist/es2015/index.d.ts

 export { buildCharacterTrie } from './char-trie';
 export { buildWordTrie } from './word-trie';
-export type { SearchCharTrie, SearchWordTrie } from './types';
+export type { SearchTrie } from './types';

dist/es2015/types.d.ts

@@ -1,34 +0,29 @@
-export interface SearchCharTrie<T> {
+export type SearchResult<KEY, T> = {
+    path: KEY;
+    value: T | undefined;
+    isComplete: boolean;
+};
+export interface SearchTrie<KEY, T> {
     /**
      * checks if value exists
      */
-    has(word: string): boolean;
+    has(word: KEY): boolean;
     /**
      * searches trie for the value
-     * @returns {Boolean} exact match was found
+     * @returns {Boolean} if exact match was found
      */
-    get(word: string): T | undefined;
+    get(word: KEY): T | undefined;
     /**
-     * puts a new value into the trie
+     * finds nearest record in the trie
      */
-    put(word: string, value: T): void;
-}
-export declare type SearchResult<T> = {
-    path: string[];
-    value: T | undefined;
-};
-export interface SearchWordTrie<T> {
+    findNearest(word: KEY): SearchResult<KEY, T>;
     /**
-     * checks if value exists
-     */
-    findNearest(word: string[]): SearchResult<T>;
-    /**
      * puts a new value into the trie
      */
-    put(word: string[], value: T): void;
+    put(word: KEY, value: T): void;
 }
-export declare type TrieNode = {
+export type TrieNode = {
     [P in string]: TrieNode;
 };
-export declare type EdgeNodes = Map<TrieNode, string>;
-export declare type EdgeValues = WeakMap<TrieNode, any>;
+export type EdgeNodes = Map<TrieNode, string>;
+export type EdgeValues = WeakMap<TrieNode, any>;

dist/es2015/word-trie.d.ts

@@ -1,5 +0,14 @@
-import { EdgeValues, SearchResult, SearchWordTrie, TrieNode } from './types';
-export declare const searchTrie: <T>(trie: TrieNode, paths: string[], values: EdgeValues) => SearchResult<T>;
+import type { EdgeValues, SearchResult, SearchTrie, TrieNode } from './types';
+export declare const searchTrie: <T>(trie: TrieNode, paths: string[], values: EdgeValues) => SearchResult<string[], T>;
 /**
- * builds a word based search trie
+ * builds a "word" based search trie.
+ * Optimized for long but structured inputs, like directory names
+ *
+ * pros:
+ * - fewer steps to find solution as key name can be long
+ *
+ * cons:
+ * - potentially more keys in single node causing hashmap speed degradation
+ *
+ * - input: array of {key:string[], value}
  */
@@ -9,2 +18,2 @@ export declare const buildWordTrie: <T>(lines: {
     value: T;
-}[]) => SearchWordTrie<T>;
+}[]) => SearchTrie<string[], T>;

dist/es2015/word-trie.js

@@ -19,9 +19,9 @@ import { EMPTY } from './magic';
     var lastValuePath = -1;
-    var valuePath = [];
+    // const valuePath = [];
     for (var i = 0; i < paths.length; ++i) {
-        node = node[paths[i]];
+        var searchPath = paths[i];
+        node = node[searchPath];
         if (!node) {
             break;
         }
-        valuePath.push(paths[i]);
         var value = values.get(node);
@@ -33,9 +33,20 @@ if (value !== undefined) {
     }
+    var lastIndex = lastValuePath + 1;
     return {
         value: lastValue,
-        path: valuePath.slice(0, lastValuePath + 1),
+        path: paths.slice(0, lastIndex),
+        isComplete: lastIndex === paths.length
     };
 };
 /**
- * builds a word based search trie
+ * builds a "word" based search trie.
+ * Optimized for long but structured inputs, like directory names
+ *
+ * pros:
+ * - fewer steps to find solution as key name can be long
+ *
+ * cons:
+ * - potentially more keys in single node causing hashmap speed degradation
+ *
+ * - input: array of {key:string[], value}
  */
@@ -50,2 +61,10 @@ export var buildWordTrie = function (lines) {
     return {
+        get: function (word) {
+            var _a = searchTrie(root, word, values), isComplete = _a.isComplete, value = _a.value;
+            return isComplete ? value : undefined;
+        },
+        has: function (word) {
+            var isComplete = searchTrie(root, word, values).isComplete;
+            return isComplete;
+        },
         findNearest: function (word) {
@@ -56,4 +75,4 @@ return searchTrie(root, word, values);
             put(root, word, value, values);
-        },
+        }
     };
 };

dist/es2019/char-trie.d.ts

@@ -1,4 +0,14 @@
-import { SearchCharTrie } from './types';
+import type { SearchTrie } from './types';
 /**
- * builds char based search trie
+ * builds a "char" based search trie.
+ * Optimized for random inputs with unpredictable variation
+ *
+ * pros:
+ * - more stable speed at large sets
+ * - every character matters, you can get the longest prefix available even without value
+ *
+ * cons:
+ * - more operations are required to perform a single search
+ *
+ * - input: array of {key:string, value}
  */
@@ -8,2 +18,2 @@ export declare const buildCharacterTrie: <T>(words: {
     value: T;
-}[], edgeDelimiter?: string) => SearchCharTrie<T>;
+}[], edgeDelimiter?: string) => SearchTrie<string, T>;

dist/es2019/char-trie.js

@@ -29,4 +29,31 @@ import { EMPTY } from './magic';
 };
+const getNearest = (node, str) => {
+    let nextNode;
+    let found = '';
+    for (const c of str) {
+        nextNode = node[c];
+        if (!nextNode) {
+            return { node, path: found, isComplete: false };
+        }
+        found += c;
+        node = nextNode;
+    }
+    return {
+        node,
+        path: str,
+        isComplete: true
+    };
+};
 /**
- * builds char based search trie
+ * builds a "char" based search trie.
+ * Optimized for random inputs with unpredictable variation
+ *
+ * pros:
+ * - more stable speed at large sets
+ * - every character matters, you can get the longest prefix available even without value
+ *
+ * cons:
+ * - more operations are required to perform a single search
+ *
+ * - input: array of {key:string, value}
  */
@@ -44,2 +71,10 @@ export const buildCharacterTrie = (words, edgeDelimiter = '.') => {
         },
+        findNearest(word) {
+            const { node, path, isComplete } = getNearest(root, word);
+            return {
+                value: values.get(node),
+                path,
+                isComplete
+            };
+        },
         get(word) {
@@ -46,0 +81,0 @@ const node = get(root, word);

dist/es2019/index.d.ts

 export { buildCharacterTrie } from './char-trie';
 export { buildWordTrie } from './word-trie';
-export type { SearchCharTrie, SearchWordTrie } from './types';
+export type { SearchTrie } from './types';

dist/es2019/types.d.ts

@@ -1,34 +0,29 @@
-export interface SearchCharTrie<T> {
+export type SearchResult<KEY, T> = {
+    path: KEY;
+    value: T | undefined;
+    isComplete: boolean;
+};
+export interface SearchTrie<KEY, T> {
     /**
      * checks if value exists
      */
-    has(word: string): boolean;
+    has(word: KEY): boolean;
     /**
      * searches trie for the value
-     * @returns {Boolean} exact match was found
+     * @returns {Boolean} if exact match was found
      */
-    get(word: string): T | undefined;
+    get(word: KEY): T | undefined;
     /**
-     * puts a new value into the trie
+     * finds nearest record in the trie
      */
-    put(word: string, value: T): void;
-}
-export declare type SearchResult<T> = {
-    path: string[];
-    value: T | undefined;
-};
-export interface SearchWordTrie<T> {
+    findNearest(word: KEY): SearchResult<KEY, T>;
     /**
-     * checks if value exists
-     */
-    findNearest(word: string[]): SearchResult<T>;
-    /**
      * puts a new value into the trie
      */
-    put(word: string[], value: T): void;
+    put(word: KEY, value: T): void;
 }
-export declare type TrieNode = {
+export type TrieNode = {
     [P in string]: TrieNode;
 };
-export declare type EdgeNodes = Map<TrieNode, string>;
-export declare type EdgeValues = WeakMap<TrieNode, any>;
+export type EdgeNodes = Map<TrieNode, string>;
+export type EdgeValues = WeakMap<TrieNode, any>;

dist/es2019/word-trie.d.ts

@@ -1,5 +0,14 @@
-import { EdgeValues, SearchResult, SearchWordTrie, TrieNode } from './types';
-export declare const searchTrie: <T>(trie: TrieNode, paths: string[], values: EdgeValues) => SearchResult<T>;
+import type { EdgeValues, SearchResult, SearchTrie, TrieNode } from './types';
+export declare const searchTrie: <T>(trie: TrieNode, paths: string[], values: EdgeValues) => SearchResult<string[], T>;
 /**
- * builds a word based search trie
+ * builds a "word" based search trie.
+ * Optimized for long but structured inputs, like directory names
+ *
+ * pros:
+ * - fewer steps to find solution as key name can be long
+ *
+ * cons:
+ * - potentially more keys in single node causing hashmap speed degradation
+ *
+ * - input: array of {key:string[], value}
  */
@@ -9,2 +18,2 @@ export declare const buildWordTrie: <T>(lines: {
     value: T;
-}[]) => SearchWordTrie<T>;
+}[]) => SearchTrie<string[], T>;

dist/es2019/word-trie.js

@@ -18,9 +18,9 @@ import { EMPTY } from './magic';
     let lastValuePath = -1;
-    const valuePath = [];
+    // const valuePath = [];
     for (let i = 0; i < paths.length; ++i) {
-        node = node[paths[i]];
+        const searchPath = paths[i];
+        node = node[searchPath];
         if (!node) {
             break;
         }
-        valuePath.push(paths[i]);
         const value = values.get(node);
@@ -32,9 +32,20 @@ if (value !== undefined) {
     }
+    const lastIndex = lastValuePath + 1;
     return {
         value: lastValue,
-        path: valuePath.slice(0, lastValuePath + 1),
+        path: paths.slice(0, lastIndex),
+        isComplete: lastIndex === paths.length
     };
 };
 /**
- * builds a word based search trie
+ * builds a "word" based search trie.
+ * Optimized for long but structured inputs, like directory names
+ *
+ * pros:
+ * - fewer steps to find solution as key name can be long
+ *
+ * cons:
+ * - potentially more keys in single node causing hashmap speed degradation
+ *
+ * - input: array of {key:string[], value}
  */
@@ -48,2 +59,10 @@ export const buildWordTrie = (lines) => {
     return {
+        get(word) {
+            const { isComplete, value } = searchTrie(root, word, values);
+            return isComplete ? value : undefined;
+        },
+        has(word) {
+            const { isComplete } = searchTrie(root, word, values);
+            return isComplete;
+        },
         findNearest(word) {
@@ -54,4 +73,4 @@ return searchTrie(root, word, values);
             put(root, word, value, values);
-        },
+        }
     };
 };

dist/es5/char-trie.d.ts

@@ -1,4 +0,14 @@
-import { SearchCharTrie } from './types';
+import type { SearchTrie } from './types';
 /**
- * builds char based search trie
+ * builds a "char" based search trie.
+ * Optimized for random inputs with unpredictable variation
+ *
+ * pros:
+ * - more stable speed at large sets
+ * - every character matters, you can get the longest prefix available even without value
+ *
+ * cons:
+ * - more operations are required to perform a single search
+ *
+ * - input: array of {key:string, value}
  */
@@ -8,2 +18,2 @@ export declare const buildCharacterTrie: <T>(words: {
     value: T;
-}[], edgeDelimiter?: string) => SearchCharTrie<T>;
+}[], edgeDelimiter?: string) => SearchTrie<string, T>;

dist/es5/char-trie.js

@@ -34,4 +34,32 @@ "use strict";
 };
+var getNearest = function (node, str) {
+    var nextNode;
+    var found = '';
+    for (var _i = 0, str_3 = str; _i < str_3.length; _i++) {
+        var c = str_3[_i];
+        nextNode = node[c];
+        if (!nextNode) {
+            return { node: node, path: found, isComplete: false };
+        }
+        found += c;
+        node = nextNode;
+    }
+    return {
+        node: node,
+        path: str,
+        isComplete: true
+    };
+};
 /**
- * builds char based search trie
+ * builds a "char" based search trie.
+ * Optimized for random inputs with unpredictable variation
+ *
+ * pros:
+ * - more stable speed at large sets
+ * - every character matters, you can get the longest prefix available even without value
+ *
+ * cons:
+ * - more operations are required to perform a single search
+ *
+ * - input: array of {key:string, value}
  */
@@ -51,2 +79,10 @@ var buildCharacterTrie = function (words, edgeDelimiter) {
         },
+        findNearest: function (word) {
+            var _a = getNearest(root, word), node = _a.node, path = _a.path, isComplete = _a.isComplete;
+            return {
+                value: values.get(node),
+                path: path,
+                isComplete: isComplete
+            };
+        },
         get: function (word) {
@@ -53,0 +89,0 @@ var node = get(root, word);

dist/es5/index.d.ts

 export { buildCharacterTrie } from './char-trie';
 export { buildWordTrie } from './word-trie';
-export type { SearchCharTrie, SearchWordTrie } from './types';
+export type { SearchTrie } from './types';

dist/es5/types.d.ts

@@ -1,34 +0,29 @@
-export interface SearchCharTrie<T> {
+export type SearchResult<KEY, T> = {
+    path: KEY;
+    value: T | undefined;
+    isComplete: boolean;
+};
+export interface SearchTrie<KEY, T> {
     /**
      * checks if value exists
      */
-    has(word: string): boolean;
+    has(word: KEY): boolean;
     /**
      * searches trie for the value
-     * @returns {Boolean} exact match was found
+     * @returns {Boolean} if exact match was found
      */
-    get(word: string): T | undefined;
+    get(word: KEY): T | undefined;
     /**
-     * puts a new value into the trie
+     * finds nearest record in the trie
      */
-    put(word: string, value: T): void;
-}
-export declare type SearchResult<T> = {
-    path: string[];
-    value: T | undefined;
-};
-export interface SearchWordTrie<T> {
+    findNearest(word: KEY): SearchResult<KEY, T>;
     /**
-     * checks if value exists
-     */
-    findNearest(word: string[]): SearchResult<T>;
-    /**
      * puts a new value into the trie
      */
-    put(word: string[], value: T): void;
+    put(word: KEY, value: T): void;
 }
-export declare type TrieNode = {
+export type TrieNode = {
     [P in string]: TrieNode;
 };
-export declare type EdgeNodes = Map<TrieNode, string>;
-export declare type EdgeValues = WeakMap<TrieNode, any>;
+export type EdgeNodes = Map<TrieNode, string>;
+export type EdgeValues = WeakMap<TrieNode, any>;

dist/es5/word-trie.d.ts

@@ -1,5 +0,14 @@
-import { EdgeValues, SearchResult, SearchWordTrie, TrieNode } from './types';
-export declare const searchTrie: <T>(trie: TrieNode, paths: string[], values: EdgeValues) => SearchResult<T>;
+import type { EdgeValues, SearchResult, SearchTrie, TrieNode } from './types';
+export declare const searchTrie: <T>(trie: TrieNode, paths: string[], values: EdgeValues) => SearchResult<string[], T>;
 /**
- * builds a word based search trie
+ * builds a "word" based search trie.
+ * Optimized for long but structured inputs, like directory names
+ *
+ * pros:
+ * - fewer steps to find solution as key name can be long
+ *
+ * cons:
+ * - potentially more keys in single node causing hashmap speed degradation
+ *
+ * - input: array of {key:string[], value}
  */
@@ -9,2 +18,2 @@ export declare const buildWordTrie: <T>(lines: {
     value: T;
-}[]) => SearchWordTrie<T>;
+}[]) => SearchTrie<string[], T>;

dist/es5/word-trie.js

@@ -22,9 +22,9 @@ "use strict";
     var lastValuePath = -1;
-    var valuePath = [];
+    // const valuePath = [];
     for (var i = 0; i < paths.length; ++i) {
-        node = node[paths[i]];
+        var searchPath = paths[i];
+        node = node[searchPath];
         if (!node) {
             break;
         }
-        valuePath.push(paths[i]);
         var value = values.get(node);
@@ -36,5 +36,7 @@ if (value !== undefined) {
     }
+    var lastIndex = lastValuePath + 1;
     return {
         value: lastValue,
-        path: valuePath.slice(0, lastValuePath + 1),
+        path: paths.slice(0, lastIndex),
+        isComplete: lastIndex === paths.length
     };
@@ -44,3 +46,12 @@ };
 /**
- * builds a word based search trie
+ * builds a "word" based search trie.
+ * Optimized for long but structured inputs, like directory names
+ *
+ * pros:
+ * - fewer steps to find solution as key name can be long
+ *
+ * cons:
+ * - potentially more keys in single node causing hashmap speed degradation
+ *
+ * - input: array of {key:string[], value}
  */
@@ -55,2 +66,10 @@ var buildWordTrie = function (lines) {
     return {
+        get: function (word) {
+            var _a = (0, exports.searchTrie)(root, word, values), isComplete = _a.isComplete, value = _a.value;
+            return isComplete ? value : undefined;
+        },
+        has: function (word) {
+            var isComplete = (0, exports.searchTrie)(root, word, values).isComplete;
+            return isComplete;
+        },
         findNearest: function (word) {
@@ -61,5 +80,5 @@ return (0, exports.searchTrie)(root, word, values);
             put(root, word, value, values);
-        },
+        }
     };
 };
 exports.buildWordTrie = buildWordTrie;

package.json

 {
   "name": "search-trie",
-  "version": "2.1.0",
+  "version": "3.0.0",
   "description": "",
@@ -8,6 +8,2 @@ "author": "Anton Korzunov ([e-mail])",
   "sideEffects": false,
-  "devDependencies": {
-    "@theuiteam/lib-builder": "^0.1.4",
-    "@size-limit/preset-small-lib": "^2.1.6"
-  },
   "repository": {
@@ -46,4 +42,8 @@ "type": "git",
   "dependencies": {
-    "tslib": "^1.9.3"
+    "tslib": "^2.0.0"
   },
+  "devDependencies": {
+    "@theuiteam/lib-builder": "^0.3.0",
+    "@size-limit/preset-small-lib": "^9.0.0"
+  },
   "files": [
@@ -50,0 +50,0 @@ "dist"

README.md

 # search-trie
 
-A simple trie structure to perform search on texts in O(n) time, where n - number of characters in searched word.
+A simple trie structure to perform prefix search on texts in O(n) time, where n - number of characters in searched word.
+> Trie is a basic Tree structure, also known as [prefix tree](https://en.wikipedia.org/wiki/Trie)
+Super simple, Super fast, super compact - less then 0.5kb.
 
-Super simple, Super fast, and just 45 lines long.
 
-### Trie
-
-Trie is a basic Tree structure, also known as suffix tree.
-
 ### Search-trie
 
-Has even more simpler structure, optimized for a single build and a few searches afterwards.
-Search-tree does not compact Tree into the "suffix" Tree, speeding up the build process.
+The single purpose of this package is to find longest match between given strings and the search key.
+For example:
+- given a couple of directories (`/src`, `/src/a`, `/src/b`, `/src/b/c`)
+- find the best match for a given file (`/src/b/c/index.tx` -> `/src/b/c`)
 
 ## Usage
 
-- `buildCharacterTrie` - creates per "character" search.
-- `buildWordTrie` - creates per "word" search
+This package provides two functions to build two different tries:
+- `buildCharacterTrie` - to create "per character" trie. Working great if you need to search something in the compressed json (short names)
+- `buildWordTrie` - to create trie where "word" is a key. Working great if there are many "long keys", for example directories you want to traverse faster
+> one has more smaller nodes, another one has fewer larger ones. It's all about memory locality and algorithm сonvergence. 
 
+They have almost identical API, and if performance matters - you need to benchmark your data to understand which one is more efficient
+
+# Example
+```ts
+import {buildWordTrie} from 'search-trie';
+
+// map package info into trie
+// using word trie as we operate with directory names
+const trie = buildWordTrie(
+    packages.map(pkg => ({key: pkg.dir.split(path.sep), value: pkg})
+);
+    
+// it's always possible to insert new data. But `delete` operation is not defined    
+trie.put({key:'another/package', value: pkg})
+
+// find longest (nearest to the search key) package. It will be a package containing this file
+const getOwnerPackage = (fileName) => trie.findNearest(fileName).value;
+```
+
+# Used in
+- [proxy-equal](https://github.com/theKashey/proxyequal/blob/c0e167b932eb948f9b3fb15b0a56b40e492413bb/src/objectTrie.js) uses `buildCharacterTrie` to understand factual usage of an object.
+- [eslint-plugin-relations](https://github.com/theKashey/eslint-plugin-relations/blob/b80d8a4a6222107d59034bddaa5fe2cb14baab55/src/utils/mapping/mapping.ts#L31) - uses `buildWordTrie` to trim long imports to the nearest allowed
+- [idea-exclude](https://github.com/theKashey/idea-exclude/blob/a5f886a8298b909ef08108efd68e348bd0fb7907/src/utils.ts#L10) uses `buildWordTrie` to remove nested directories, ie creating trie containing shortest versions
+
 # Licence
 
 MIT

No alert changes

Improved metrics

Total package byte prevSize

27163

increased by43.98%

Lines of code

731

increased by39.24%

Number of lines in readme file

49

increased by104.17%

Dependency changes

• + Addedtslib@2.6.2(transitive)

• - Removedtslib@1.14.1(transitive)

• Updatedtslib@^2.0.0