DevTools: introduce Trie data structure

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

Index: third_party/WebKit/Source/devtools/front_end/platform/Trie.js
diff --git a/third_party/WebKit/Source/devtools/front_end/platform/Trie.js b/third_party/WebKit/Source/devtools/front_end/platform/Trie.js
new file mode 100644
index 0000000000000000000000000000000000000000..ebcabd448c3a15b28829c77cbd54fca33224fa9c
--- /dev/null
+++ b/third_party/WebKit/Source/devtools/front_end/platform/Trie.js
@@ -0,0 +1,128 @@
+// 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
+ */
+function Trie()
+{
+    this.clear();
+}
+
+Trie.prototype = {
+    /**
+     * @param {string} word
+     */
+    add: function(word)
+    {
+        var node = this._root;
+        for (var i = 0; i < word.length; ++i) {
+            var edge = word[i];
+            var next = this._edges[node][edge];
+            if (!next) {
+                next = this._size++;
+                this._marks.push(false);
+                this._edges.push({ __proto__: null });
+                this._edges[node][edge] = next;
+            }
+            node = next;
+        }
+        this._marks[node] = true;
+    },
+
+    /**
+     * @param {string} word
+     * @return {boolean}
+     */
+    remove: function(word)
+    {
+        var node = this._root;
+        for (var i = 0; i < word.length; ++i) {
+            node = this._edges[node][word[i]];
+            if (!node)
+                return false;
+        }
+        if (!this._marks[node])
+            return false;
+        this._marks[node] = false;

[dgozman, 2016/10/03 20:32:57]

Why not remove edges which do not lead to leafs?

[lushnikov, 2016/10/03 22:56:22]

Done.

+        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) {
+            var next = this._edges[node][prefix[i]];
+            if (!next)
+                return [];
+            node = next;

[dgozman, 2016/10/03 20:32:57]

Can avoid |next| variable similar to has() function.

[lushnikov, 2016/10/03 22:56:22]

Nice, thanks

+        }
+        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];
+    }
+}