Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(80)

Issues Search
    My Issues | Starred     Open | Closed | All

Side by Side Diff: third_party/WebKit/Source/devtools/front_end/common/Trie.js

Issue 2466123002: DevTools: reformat front-end code to match chromium style. (Closed)
Patch Set: all done Created 4 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « third_party/WebKit/Source/devtools/front_end/common/Throttler.js ('k') | third_party/WebKit/Source/devtools/front_end/common/UIString.js » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright 2016 The Chromium Authors. All rights reserved. 1 // Copyright 2016 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be 2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. 3 // found in the LICENSE file.
4 /**
5 * @unrestricted
6 */
7 WebInspector.Trie = class {
8 constructor() {
9 this.clear();
10 }
4 11
5 /** 12 /**
6 * @constructor 13 * @param {string} word
7 */ 14 */
8 WebInspector.Trie = function() 15 add(word) {
9 { 16 var node = this._root;
10 this.clear(); 17 ++this._wordsInSubtree[this._root];
18 for (var i = 0; i < word.length; ++i) {
19 var edge = word[i];
20 var next = this._edges[node][edge];
21 if (!next) {
22 if (this._freeNodes.length) {
23 // No need to reset any fields since they were properly cleaned up in remove().
24 next = this._freeNodes.pop();
25 } else {
26 next = this._size++;
27 this._isWord.push(false);
28 this._wordsInSubtree.push(0);
29 this._edges.push({__proto__: null});
30 }
31 this._edges[node][edge] = next;
32 }
33 ++this._wordsInSubtree[next];
34 node = next;
35 }
36 this._isWord[node] = true;
37 }
38
39 /**
40 * @param {string} word
41 * @return {boolean}
42 */
43 remove(word) {
44 if (!this.has(word))
45 return false;
46 var node = this._root;
47 --this._wordsInSubtree[this._root];
48 for (var i = 0; i < word.length; ++i) {
49 var edge = word[i];
50 var next = this._edges[node][edge];
51 if (!--this._wordsInSubtree[next]) {
52 delete this._edges[node][edge];
53 this._freeNodes.push(next);
54 }
55 node = next;
56 }
57 this._isWord[node] = false;
58 return true;
59 }
60
61 /**
62 * @param {string} word
63 * @return {boolean}
64 */
65 has(word) {
66 var node = this._root;
67 for (var i = 0; i < word.length; ++i) {
68 node = this._edges[node][word[i]];
69 if (!node)
70 return false;
71 }
72 return this._isWord[node];
73 }
74
75 /**
76 * @param {string=} prefix
77 * @return {!Array<string>}
78 */
79 words(prefix) {
80 prefix = prefix || '';
81 var node = this._root;
82 for (var i = 0; i < prefix.length; ++i) {
83 node = this._edges[node][prefix[i]];
84 if (!node)
85 return [];
86 }
87 var results = [];
88 this._dfs(node, prefix, results);
89 return results;
90 }
91
92 /**
93 * @param {number} node
94 * @param {string} prefix
95 * @param {!Array<string>} results
96 */
97 _dfs(node, prefix, results) {
98 if (this._isWord[node])
99 results.push(prefix);
100 var edges = this._edges[node];
101 for (var edge in edges)
102 this._dfs(edges[edge], prefix + edge, results);
103 }
104
105 /**
106 * @param {string} word
107 * @param {boolean} fullWordOnly
108 * @return {string}
109 */
110 longestPrefix(word, fullWordOnly) {
111 var node = this._root;
112 var wordIndex = 0;
113 for (var i = 0; i < word.length; ++i) {
114 node = this._edges[node][word[i]];
115 if (!node)
116 break;
117 if (!fullWordOnly || this._isWord[node])
118 wordIndex = i + 1;
119 }
120 return word.substring(0, wordIndex);
121 }
122
123 clear() {
124 this._size = 1;
125 this._root = 0;
126 /** @type {!Array<!Object<string, number>>} */
127 this._edges = [{__proto__: null}];
128 /** @type {!Array<boolean>} */
129 this._isWord = [false];
130 /** @type {!Array<number>} */
131 this._wordsInSubtree = [0];
132 /** @type {!Array<number>} */
133 this._freeNodes = [];
134 }
11 }; 135 };
12
13 WebInspector.Trie.prototype = {
14 /**
15 * @param {string} word
16 */
17 add: function(word)
18 {
19 var node = this._root;
20 ++this._wordsInSubtree[this._root];
21 for (var i = 0; i < word.length; ++i) {
22 var edge = word[i];
23 var next = this._edges[node][edge];
24 if (!next) {
25 if (this._freeNodes.length) {
26 // No need to reset any fields since they were properly clea ned up in remove().
27 next = this._freeNodes.pop();
28 } else {
29 next = this._size++;
30 this._isWord.push(false);
31 this._wordsInSubtree.push(0);
32 this._edges.push({ __proto__: null });
33 }
34 this._edges[node][edge] = next;
35 }
36 ++this._wordsInSubtree[next];
37 node = next;
38 }
39 this._isWord[node] = true;
40 },
41
42 /**
43 * @param {string} word
44 * @return {boolean}
45 */
46 remove: function(word)
47 {
48 if (!this.has(word))
49 return false;
50 var node = this._root;
51 --this._wordsInSubtree[this._root];
52 for (var i = 0; i < word.length; ++i) {
53 var edge = word[i];
54 var next = this._edges[node][edge];
55 if (!--this._wordsInSubtree[next]) {
56 delete this._edges[node][edge];
57 this._freeNodes.push(next);
58 }
59 node = next;
60 }
61 this._isWord[node] = false;
62 return true;
63 },
64
65 /**
66 * @param {string} word
67 * @return {boolean}
68 */
69 has: function(word)
70 {
71 var node = this._root;
72 for (var i = 0; i < word.length; ++i) {
73 node = this._edges[node][word[i]];
74 if (!node)
75 return false;
76 }
77 return this._isWord[node];
78 },
79
80 /**
81 * @param {string=} prefix
82 * @return {!Array<string>}
83 */
84 words: function(prefix)
85 {
86 prefix = prefix || "";
87 var node = this._root;
88 for (var i = 0; i < prefix.length; ++i) {
89 node = this._edges[node][prefix[i]];
90 if (!node)
91 return [];
92 }
93 var results = [];
94 this._dfs(node, prefix, results);
95 return results;
96 },
97
98 /**
99 * @param {number} node
100 * @param {string} prefix
101 * @param {!Array<string>} results
102 */
103 _dfs: function(node, prefix, results)
104 {
105 if (this._isWord[node])
106 results.push(prefix);
107 var edges = this._edges[node];
108 for (var edge in edges)
109 this._dfs(edges[edge], prefix + edge, results);
110 },
111
112 /**
113 * @param {string} word
114 * @param {boolean} fullWordOnly
115 * @return {string}
116 */
117 longestPrefix: function(word, fullWordOnly)
118 {
119 var node = this._root;
120 var wordIndex = 0;
121 for (var i = 0; i < word.length; ++i) {
122 node = this._edges[node][word[i]];
123 if (!node)
124 break;
125 if (!fullWordOnly || this._isWord[node])
126 wordIndex = i + 1;
127 }
128 return word.substring(0, wordIndex);
129 },
130
131 clear: function()
132 {
133 this._size = 1;
134 this._root = 0;
135 /** @type {!Array<!Object<string, number>>} */
136 this._edges = [{ __proto__: null }];
137 /** @type {!Array<boolean>} */
138 this._isWord = [false];
139 /** @type {!Array<number>} */
140 this._wordsInSubtree = [0];
141 /** @type {!Array<number>} */
142 this._freeNodes = [];
143 }
144 };
OLDNEW
« no previous file with comments | « third_party/WebKit/Source/devtools/front_end/common/Throttler.js ('k') | third_party/WebKit/Source/devtools/front_end/common/UIString.js » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698