DevTools: introduce Trie data structure

third_party/WebKit/Source/devtools/front_end/common/Trie.js

Index: third_party/WebKit/Source/devtools/front_end/common/Trie.js
diff --git a/third_party/WebKit/Source/devtools/front_end/common/Trie.js b/third_party/WebKit/Source/devtools/front_end/common/Trie.js
new file mode 100644
index 0000000000000000000000000000000000000000..c6ae75ded9d61d92adc1ed5d8ce466c2d90bd6e1
--- /dev/null
+++ b/third_party/WebKit/Source/devtools/front_end/common/Trie.js
@@ -0,0 +1,143 @@
+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+/**
+ * @constructor
+ */
+WebInspector.Trie = function()
+{
+    this.clear();
+}
+
+WebInspector.Trie.prototype = {
+    /**
+     * @param {string} word
+     */
+    add: function(word)
+    {
+        var node = this._root;
+        ++this._subtreeMarks[this._root];
+        for (var i = 0; i < word.length; ++i) {
+            var edge = word[i];
+            var next = this._edges[node][edge];
+            if (!next) {
+                if (this._freeNodes.length) {
+                    next = this._freeNodes.pop();

[dgozman, 2016/10/03 23:08:34]

Let's comment that we don't clear all the fields because they are properly
cleaned up in remove().

[lushnikov, 2016/10/04 00:17:59]

Done.

+                } else {
+                    next = this._size++;
+                    this._marks.push(false);
+                    this._subtreeMarks.push(0);
+                    this._edges.push({ __proto__: null });
+                }
+                this._edges[node][edge] = next;
+            }
+            ++this._subtreeMarks[next];
+            node = next;
+        }
+        this._marks[node] = true;
+    },
+
+    /**
+     * @param {string} word
+     * @return {boolean}
+     */
+    remove: function(word)
+    {
+        if (!this.has(word))
+            return false;
+        var node = this._root;
+        --this._subtreeMarks[this._root];
+        for (var i = 0; i < word.length; ++i) {
+            var edge = word[i];
+            var next = this._edges[node][edge];
+            if (!--this._subtreeMarks[next]) {
+                delete this._edges[node][edge];
+                this._freeNodes.push(next);

[dgozman, 2016/10/03 23:08:34]

Let's exercise add->remove->add in the test. 

[lushnikov, 2016/10/04 00:17:59]

Done.

+            }
+            node = next;
+        }
+        this._marks[node] = false;
+        return true;
+    },
+
+    /**
+     * @param {string} word
+     * @return {boolean}
+     */
+    has: function(word)
+    {
+        var node = this._root;
+        for (var i = 0; i < word.length; ++i) {
+            node = this._edges[node][word[i]];
+            if (!node)
+                return false;
+        }
+        return this._marks[node];
+    },
+
+    /**
+     * @param {string=} prefix
+     * @return {!Array<string>}
+     */
+    words: function(prefix)
+    {
+        prefix = prefix || "";
+        var node = this._root;
+        for (var i = 0; i < prefix.length; ++i) {
+            node = this._edges[node][prefix[i]];
+            if (!node)
+                return [];
+        }
+        var results = [];
+        this._dfs(node, prefix, results);
+        return results;
+    },
+
+    /**
+     * @param {number} node
+     * @param {string} prefix
+     * @param {!Array<string>} results
+     */
+    _dfs: function(node, prefix, results)
+    {
+        if (this._marks[node])
+            results.push(prefix);
+        var edges = this._edges[node];
+        for (var edge in edges)
+            this._dfs(edges[edge], prefix + edge, results);
+    },
+
+    /**
+     * @param {string} word
+     * @param {boolean} fullWordOnly
+     * @return {string}
+     */
+    longestPrefix: function(word, fullWordOnly)
+    {
+        var node = this._root;
+        var wordIndex = 0;
+        for (var i = 0; i < word.length; ++i) {
+            if (!fullWordOnly || this._marks[node])
+                wordIndex = i;
+            node = this._edges[node][word[i]];
+            if (!node)
+                break;
+        }
+        return word.substring(0, wordIndex);
+    },
+
+    clear: function()
+    {
+        this._size = 1;
+        this._root = 0;
+        /** @type {!Array<!Object<string, number>>} */
+        this._edges = [{ __proto__: null }];
+        /** @type {!Array<boolean>} */
+        this._marks = [false];

[dgozman, 2016/10/03 23:08:34]

_isWord or something like that?

[lushnikov, 2016/10/04 00:17:59]

Done.

+        /** @type {!Array<number>} */
+        this._subtreeMarks = [0];

[dgozman, 2016/10/03 23:08:34]

_wordsInSubtree

[lushnikov, 2016/10/04 00:17:59]

Done.

+        /** @type {!Array<number>} */
+        this._freeNodes = [];
+    }
+}