@navpreetdevpuri/trie-js - npm Package Compare versions

Comparing version 1.0.13 to 1.0.14

lib/index.d.ts

@@ -25,9 +25,16 @@ type TrieNode = {
     private _getPrefix;
-    private _pushAllPossibleNodesForPrefix;
-    _moveToRoundSubtree(queue: [TrieNode, string][], ceil?: boolean): TrieNode;
+    _binarySearchAscending(array: any, value: any): number;
+    _binarySearchDescending(array: any, value: any): number;
+    _findPreorderPredecessorValues(queue: [TrieNode, string][]): TrieNode;
+    _findPreorderSuccessorValues(queue: [TrieNode, string][]): TrieNode;
     _findNode(key: string): TrieNode;
-    getPreorderPredecessorAndSuccessor(key: string): {
-        predecessor: any[];
-        successor: any[];
+    private _getAllPossibleNodesForPrefix;
+    getPreorderPredecessorAndSuccessorForNewkey(key: string): {
+        predecessorValues: any[];
+        successorValues: any[];
     };
+    getPreorderPredecessorAndSuccessorForExistingKey(key: string): {
+        predecessorValues: any[];
+        successorValues: any[];
+    };
     createTrie(nodes: {
@@ -34,0 +41,0 @@ key: string;

lib/index.js

@@ -65,34 +65,65 @@ var __spreadArray = (this && this.__spreadArray) || function (to, from, pack) {
     };
-    Trie.prototype._pushAllPossibleNodesForPrefix = function (prefix, queue) {
-        if (this.caseInsensitive) {
-            prefix = prefix.toLowerCase();
+    Trie.prototype._binarySearchAscending = function (array, value) {
+        var start = 0;
+        var end = array.length - 1;
+        while (start <= end) {
+            var mid = Math.floor((start + end) / 2);
+            if (value < array[mid]) {
+                end = mid - 1;
+            }
+            else if (array[mid] <= value) {
+                start = mid + 1;
+            }
         }
-        var currentNode = this.root;
-        for (var i = 0; i < prefix.length; i++) {
-            var ch = prefix[i];
-            if (!currentNode[ch]) {
-                queue.push([currentNode, ch]);
-                break;
+        return start;
+    };
+    Trie.prototype._binarySearchDescending = function (array, value) {
+        var start = 0;
+        var end = array.length - 1;
+        while (start <= end) {
+            var mid = Math.floor((start + end) / 2);
+            if (value > array[mid]) {
+                end = mid - 1;
             }
-            queue.push([currentNode, ch]);
-            currentNode = currentNode[ch];
+            else if (array[mid] >= value) {
+                start = mid + 1;
+            }
         }
+        return start;
     };
-    Trie.prototype._moveToRoundSubtree = function (queue, ceil) {
-        if (ceil === void 0) { ceil = false; }
-        var resultNode = null;
-        while (resultNode == null && queue.length > 0) {
-            var _a = queue.pop(), currentNode = _a[0], nextCh = _a[1];
-            var searchingCharset = ceil
-                ? this.charsetAscending.slice(this.charsetAscending.indexOf(nextCh) + 1)
-                : this.charsetDescending.slice(this.charsetDescending.indexOf(nextCh) + 1);
+    Trie.prototype._findPreorderPredecessorValues = function (queue) {
+        var predecessorValues = null;
+        var i = queue.length;
+        while (predecessorValues == null && --i >= 0) {
+            var _a = queue[i], currentNode = _a[0], nextCh = _a[1];
+            var searchingCharset = this.charsetDescending.slice(this._binarySearchDescending(this.charsetDescending, nextCh));
             for (var _i = 0, searchingCharset_1 = searchingCharset; _i < searchingCharset_1.length; _i++) {
                 var ch = searchingCharset_1[_i];
                 if (currentNode[ch]) {
-                    return currentNode[ch];
+                    predecessorValues = this._getMax(currentNode[ch]).values;
+                    break;
                 }
             }
+            if (predecessorValues == null && currentNode._isEnd) {
+                predecessorValues = currentNode.values;
+                break;
+            }
         }
-        return null;
+        return predecessorValues;
     };
+    Trie.prototype._findPreorderSuccessorValues = function (queue) {
+        var successorValues = null;
+        var i = queue.length;
+        while (successorValues == null && --i >= 0) {
+            var _a = queue[i], currentNode = _a[0], nextCh = _a[1];
+            var searchingCharset = this.charsetAscending.slice(this._binarySearchAscending(this.charsetAscending, nextCh));
+            for (var _i = 0, searchingCharset_2 = searchingCharset; _i < searchingCharset_2.length; _i++) {
+                var ch = searchingCharset_2[_i];
+                if (currentNode[ch]) {
+                    successorValues = this._getMin(currentNode[ch]).values;
+                }
+            }
+        }
+        return successorValues;
+    };
     Trie.prototype._findNode = function (key) {
@@ -108,11 +139,48 @@ var currentNode = this.root;
     };
-    Trie.prototype.getPreorderPredecessorAndSuccessor = function (key) {
+    Trie.prototype._getAllPossibleNodesForPrefix = function (prefix) {
         var queue = [];
-        this._pushAllPossibleNodesForPrefix(key, queue);
-        var predecessor = this._moveToRoundSubtree(__spreadArray([], queue, true), false);
-        var successor = this._moveToRoundSubtree(__spreadArray([], queue, true), true);
-        predecessor = predecessor ? this._getMax(predecessor) : null;
-        successor = successor ? this._getMin(successor) : null;
-        return { predecessor: predecessor.values, successor: successor.values };
+        if (this.caseInsensitive) {
+            prefix = prefix.toLowerCase();
+        }
+        var currentNode = this.root;
+        var currI = 0;
+        for (; currI < prefix.length; currI++) {
+            var ch = prefix[currI];
+            if (!currentNode[ch]) {
+                queue.push([currentNode, ch]);
+                break;
+            }
+            queue.push([currentNode, ch]);
+            currentNode = currentNode[ch];
+        }
+        return { currI: currI, currentNode: currentNode, queue: queue };
     };
+    Trie.prototype.getPreorderPredecessorAndSuccessorForNewkey = function (key) {
+        if (this.caseInsensitive) {
+            key = key.toLowerCase();
+        }
+        var _a = this._getAllPossibleNodesForPrefix(key), currI = _a.currI, currentNode = _a.currentNode, queue = _a.queue;
+        var predecessorValues = null;
+        var successorValues = null;
+        predecessorValues = this._findPreorderPredecessorValues(queue);
+        if (currI === key.length) {
+            successorValues = this._getMin(currentNode).values;
+        }
+        if (currI < key.length) {
+            successorValues = this._findPreorderSuccessorValues(queue);
+        }
+        return { predecessorValues: predecessorValues, successorValues: successorValues };
+    };
+    Trie.prototype.getPreorderPredecessorAndSuccessorForExistingKey = function (key) {
+        if (this.caseInsensitive) {
+            key = key.toLowerCase();
+        }
+        var _a = this._getAllPossibleNodesForPrefix(key), currI = _a.currI, currentNode = _a.currentNode, queue = _a.queue;
+        var predecessorValues = null;
+        var successorValues = null;
+        predecessorValues = this._findPreorderPredecessorValues(queue);
+        var queueCopy = __spreadArray([], queue, true);
+        successorValues = this._findPreorderSuccessorValues(queueCopy);
+        return { predecessorValues: predecessorValues, successorValues: successorValues };
+    };
     Trie.prototype.createTrie = function (nodes) {
@@ -119,0 +187,0 @@ var _this = this;

package.json

 {
   "name": "@navpreetdevpuri/trie-js",
-  "version": "1.0.13",
+  "version": "1.0.14",
   "description": "Trie data structure implementation in javascript",
@@ -5,0 +5,0 @@ "main": "lib/index.js",

src/index.ts

@@ -83,40 +83,74 @@ type TrieNode = {
 
-  private _pushAllPossibleNodesForPrefix(
-    prefix: string,
-    queue: [TrieNode, string][]
-  ) {
-    if (this.caseInsensitive) {
-      prefix = prefix.toLowerCase();
+  _binarySearchAscending(array, value) {
+    let start = 0;
+    let end = array.length - 1;
+
+    while (start <= end) {
+      const mid = Math.floor((start + end) / 2);
+      if (value < array[mid]) {
+        end = mid - 1;
+      } else if (array[mid] <= value) {
+        start = mid + 1;
+      }
     }
-    let currentNode = this.root;
-    for (let i = 0; i < prefix.length; i++) {
-      const ch = prefix[i];
-      if (!currentNode[ch]) {
-        queue.push([currentNode, ch]);
-        break;
+
+    return start;
+  }
+
+  _binarySearchDescending(array, value) {
+    let start = 0;
+    let end = array.length - 1;
+
+    while (start <= end) {
+      const mid = Math.floor((start + end) / 2);
+      if (value > array[mid]) {
+        end = mid - 1;
+      } else if (array[mid] >= value) {
+        start = mid + 1;
       }
-      queue.push([currentNode, ch]);
-      currentNode = currentNode[ch];
     }
+
+    return start;
   }
 
-  _moveToRoundSubtree(queue: [TrieNode, string][], ceil = false): TrieNode {
-    let resultNode = null;
-    while (resultNode == null && queue.length > 0) {
-      const [currentNode, nextCh] = queue.pop();
-      const searchingCharset = ceil
-        ? this.charsetAscending.slice(this.charsetAscending.indexOf(nextCh) + 1)
-        : this.charsetDescending.slice(
-            this.charsetDescending.indexOf(nextCh) + 1
-          );
+  _findPreorderPredecessorValues(queue: [TrieNode, string][]): TrieNode {
+    let predecessorValues = null;
+    let i = queue.length;
+    while (predecessorValues == null && --i >= 0) {
+      const [currentNode, nextCh] = queue[i];
+      const searchingCharset = this.charsetDescending.slice(
+        this._binarySearchDescending(this.charsetDescending, nextCh)
+      );
       for (const ch of searchingCharset) {
         if (currentNode[ch]) {
-          return currentNode[ch];
+          predecessorValues = this._getMax(currentNode[ch]).values;
+          break;
         }
       }
+      if (predecessorValues == null && currentNode._isEnd) {
+        predecessorValues = currentNode.values;
+        break;
+      }
     }
 
-    return null;
+    return predecessorValues;
   }
+  _findPreorderSuccessorValues(queue: [TrieNode, string][]): TrieNode {
+    let successorValues = null;
+    let i = queue.length;
+    while (successorValues == null && --i >= 0) {
+      const [currentNode, nextCh] = queue[i];
+      const searchingCharset = this.charsetAscending.slice(
+        this._binarySearchAscending(this.charsetAscending, nextCh)
+      );
+      for (const ch of searchingCharset) {
+        if (currentNode[ch]) {
+          successorValues = this._getMin(currentNode[ch]).values;
+        }
+      }
+    }
 
+    return successorValues;
+  }
+
   _findNode(key: string): TrieNode {
@@ -132,17 +166,62 @@ let currentNode = this.root;
 
-  getPreorderPredecessorAndSuccessor(key: string): {
-    predecessor: any[];
-    successor: any[];
-  } {
+  private _getAllPossibleNodesForPrefix(prefix: string) {
     const queue: [TrieNode, string][] = [];
+    if (this.caseInsensitive) {
+      prefix = prefix.toLowerCase();
+    }
+    let currentNode = this.root;
+    let currI = 0;
+    for (; currI < prefix.length; currI++) {
+      const ch = prefix[currI];
+      if (!currentNode[ch]) {
+        queue.push([currentNode, ch]);
+        break;
+      }
+      queue.push([currentNode, ch]);
+      currentNode = currentNode[ch];
+    }
 
-    this._pushAllPossibleNodesForPrefix(key, queue);
+    return { currI, currentNode, queue };
+  }
 
-    let predecessor = this._moveToRoundSubtree([...queue], false);
-    let successor = this._moveToRoundSubtree([...queue], true);
+  getPreorderPredecessorAndSuccessorForNewkey(key: string): {
+    predecessorValues: any[];
+    successorValues: any[];
+  } {
+    if (this.caseInsensitive) {
+      key = key.toLowerCase();
+    }
+    const { currI, currentNode, queue } =
+      this._getAllPossibleNodesForPrefix(key);
 
-    predecessor = predecessor ? this._getMax(predecessor) : null;
-    successor = successor ? this._getMin(successor) : null;
+    let predecessorValues = null;
+    let successorValues = null;
+    predecessorValues = this._findPreorderPredecessorValues(queue);
+    if (currI === key.length) {
+      successorValues = this._getMin(currentNode).values;
+    }
+    if (currI < key.length) {
+      successorValues = this._findPreorderSuccessorValues(queue);
+    }
+    return { predecessorValues, successorValues };
+  }
 
-    return { predecessor: predecessor.values, successor: successor.values };
+  getPreorderPredecessorAndSuccessorForExistingKey(key: string): {
+    predecessorValues: any[];
+    successorValues: any[];
+  } {
+    if (this.caseInsensitive) {
+      key = key.toLowerCase();
+    }
+    const { currI, currentNode, queue } =
+      this._getAllPossibleNodesForPrefix(key);
+
+    let predecessorValues = null;
+    let successorValues = null;
+
+    predecessorValues = this._findPreorderPredecessorValues(queue);
+    const queueCopy = [...queue];
+    successorValues = this._findPreorderSuccessorValues(queueCopy);
+
+    return { predecessorValues, successorValues };
   }
@@ -149,0 +228,0 @@

No alert changes

Improved metrics

Total package byte prevSize

24882

26.31%

Lines of code

636

29.53%

No dependency changes