OLD | NEW |
| (Empty) |
1 // Copyright 2009 the V8 project authors. All rights reserved. | |
2 // Redistribution and use in source and binary forms, with or without | |
3 // modification, are permitted provided that the following conditions are | |
4 // met: | |
5 // | |
6 // * Redistributions of source code must retain the above copyright | |
7 // notice, this list of conditions and the following disclaimer. | |
8 // * Redistributions in binary form must reproduce the above | |
9 // copyright notice, this list of conditions and the following | |
10 // disclaimer in the documentation and/or other materials provided | |
11 // with the distribution. | |
12 // * Neither the name of Google Inc. nor the names of its | |
13 // contributors may be used to endorse or promote products derived | |
14 // from this software without specific prior written permission. | |
15 // | |
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
27 | |
28 | |
29 // A namespace stub. It will become more clear how to declare it properly | |
30 // during integration of this script into Dev Tools. | |
31 var goog = goog || {}; | |
32 goog.structs = goog.structs || {}; | |
33 | |
34 | |
35 /** | |
36 * Constructs a Splay tree. A splay tree is a self-balancing binary | |
37 * search tree with the additional property that recently accessed | |
38 * elements are quick to access again. It performs basic operations | |
39 * such as insertion, look-up and removal in O(log(n)) amortized time. | |
40 * | |
41 * @constructor | |
42 */ | |
43 goog.structs.SplayTree = function() { | |
44 }; | |
45 | |
46 | |
47 /** | |
48 * Pointer to the root node of the tree. | |
49 * | |
50 * @type {goog.structs.SplayTree.Node} | |
51 * @private | |
52 */ | |
53 goog.structs.SplayTree.prototype.root_ = null; | |
54 | |
55 | |
56 /** | |
57 * @return {boolean} Whether the tree is empty. | |
58 */ | |
59 goog.structs.SplayTree.prototype.isEmpty = function() { | |
60 return !this.root_; | |
61 }; | |
62 | |
63 | |
64 | |
65 /** | |
66 * Inserts a node into the tree with the specified key and value if | |
67 * the tree does not already contain a node with the specified key. If | |
68 * the value is inserted, it becomes the root of the tree. | |
69 * | |
70 * @param {number} key Key to insert into the tree. | |
71 * @param {*} value Value to insert into the tree. | |
72 */ | |
73 goog.structs.SplayTree.prototype.insert = function(key, value) { | |
74 if (this.isEmpty()) { | |
75 this.root_ = new goog.structs.SplayTree.Node(key, value); | |
76 return; | |
77 } | |
78 // Splay on the key to move the last node on the search path for | |
79 // the key to the root of the tree. | |
80 this.splay_(key); | |
81 if (this.root_.key == key) { | |
82 return; | |
83 } | |
84 var node = new goog.structs.SplayTree.Node(key, value); | |
85 if (key > this.root_.key) { | |
86 node.left = this.root_; | |
87 node.right = this.root_.right; | |
88 this.root_.right = null; | |
89 } else { | |
90 node.right = this.root_; | |
91 node.left = this.root_.left; | |
92 this.root_.left = null; | |
93 } | |
94 this.root_ = node; | |
95 }; | |
96 | |
97 | |
98 /** | |
99 * Removes a node with the specified key from the tree if the tree | |
100 * contains a node with this key. The removed node is returned. If the | |
101 * key is not found, an exception is thrown. | |
102 * | |
103 * @param {number} key Key to find and remove from the tree. | |
104 * @return {goog.structs.SplayTree.Node} The removed node. | |
105 */ | |
106 goog.structs.SplayTree.prototype.remove = function(key) { | |
107 if (this.isEmpty()) { | |
108 throw Error('Key not found: ' + key); | |
109 } | |
110 this.splay_(key); | |
111 if (this.root_.key != key) { | |
112 throw Error('Key not found: ' + key); | |
113 } | |
114 var removed = this.root_; | |
115 if (!this.root_.left) { | |
116 this.root_ = this.root_.right; | |
117 } else { | |
118 var right = this.root_.right; | |
119 this.root_ = this.root_.left; | |
120 // Splay to make sure that the new root has an empty right child. | |
121 this.splay_(key); | |
122 // Insert the original right child as the right child of the new | |
123 // root. | |
124 this.root_.right = right; | |
125 } | |
126 return removed; | |
127 }; | |
128 | |
129 | |
130 /** | |
131 * Returns the node having the specified key or null if the tree doesn't contain | |
132 * a node with the specified key. | |
133 * | |
134 * @param {number} key Key to find in the tree. | |
135 * @return {goog.structs.SplayTree.Node} Node having the specified key. | |
136 */ | |
137 goog.structs.SplayTree.prototype.find = function(key) { | |
138 if (this.isEmpty()) { | |
139 return null; | |
140 } | |
141 this.splay_(key); | |
142 return this.root_.key == key ? this.root_ : null; | |
143 }; | |
144 | |
145 | |
146 /** | |
147 * @return {goog.structs.SplayTree.Node} Node having the minimum key value. | |
148 */ | |
149 goog.structs.SplayTree.prototype.findMin = function() { | |
150 if (this.isEmpty()) { | |
151 return null; | |
152 } | |
153 var current = this.root_; | |
154 while (current.left) { | |
155 current = current.left; | |
156 } | |
157 return current; | |
158 }; | |
159 | |
160 | |
161 /** | |
162 * @return {goog.structs.SplayTree.Node} Node having the maximum key value. | |
163 */ | |
164 goog.structs.SplayTree.prototype.findMax = function(opt_startNode) { | |
165 if (this.isEmpty()) { | |
166 return null; | |
167 } | |
168 var current = opt_startNode || this.root_; | |
169 while (current.right) { | |
170 current = current.right; | |
171 } | |
172 return current; | |
173 }; | |
174 | |
175 | |
176 /** | |
177 * @return {goog.structs.SplayTree.Node} Node having the maximum key value that | |
178 * is less or equal to the specified key value. | |
179 */ | |
180 goog.structs.SplayTree.prototype.findGreatestLessThan = function(key) { | |
181 if (this.isEmpty()) { | |
182 return null; | |
183 } | |
184 // Splay on the key to move the node with the given key or the last | |
185 // node on the search path to the top of the tree. | |
186 this.splay_(key); | |
187 // Now the result is either the root node or the greatest node in | |
188 // the left subtree. | |
189 if (this.root_.key <= key) { | |
190 return this.root_; | |
191 } else if (this.root_.left) { | |
192 return this.findMax(this.root_.left); | |
193 } else { | |
194 return null; | |
195 } | |
196 }; | |
197 | |
198 | |
199 /** | |
200 * @return {Array<*>} An array containing all the values of tree's nodes. | |
201 */ | |
202 goog.structs.SplayTree.prototype.exportValues = function() { | |
203 var result = []; | |
204 this.traverse_(function(node) { result.push(node.value); }); | |
205 return result; | |
206 }; | |
207 | |
208 | |
209 /** | |
210 * Perform the splay operation for the given key. Moves the node with | |
211 * the given key to the top of the tree. If no node has the given | |
212 * key, the last node on the search path is moved to the top of the | |
213 * tree. This is the simplified top-down splaying algorithm from: | |
214 * "Self-adjusting Binary Search Trees" by Sleator and Tarjan | |
215 * | |
216 * @param {number} key Key to splay the tree on. | |
217 * @private | |
218 */ | |
219 goog.structs.SplayTree.prototype.splay_ = function(key) { | |
220 if (this.isEmpty()) { | |
221 return; | |
222 } | |
223 // Create a dummy node. The use of the dummy node is a bit | |
224 // counter-intuitive: The right child of the dummy node will hold | |
225 // the L tree of the algorithm. The left child of the dummy node | |
226 // will hold the R tree of the algorithm. Using a dummy node, left | |
227 // and right will always be nodes and we avoid special cases. | |
228 var dummy, left, right; | |
229 dummy = left = right = new goog.structs.SplayTree.Node(null, null); | |
230 var current = this.root_; | |
231 while (true) { | |
232 if (key < current.key) { | |
233 if (!current.left) { | |
234 break; | |
235 } | |
236 if (key < current.left.key) { | |
237 // Rotate right. | |
238 var tmp = current.left; | |
239 current.left = tmp.right; | |
240 tmp.right = current; | |
241 current = tmp; | |
242 if (!current.left) { | |
243 break; | |
244 } | |
245 } | |
246 // Link right. | |
247 right.left = current; | |
248 right = current; | |
249 current = current.left; | |
250 } else if (key > current.key) { | |
251 if (!current.right) { | |
252 break; | |
253 } | |
254 if (key > current.right.key) { | |
255 // Rotate left. | |
256 var tmp = current.right; | |
257 current.right = tmp.left; | |
258 tmp.left = current; | |
259 current = tmp; | |
260 if (!current.right) { | |
261 break; | |
262 } | |
263 } | |
264 // Link left. | |
265 left.right = current; | |
266 left = current; | |
267 current = current.right; | |
268 } else { | |
269 break; | |
270 } | |
271 } | |
272 // Assemble. | |
273 left.right = current.left; | |
274 right.left = current.right; | |
275 current.left = dummy.right; | |
276 current.right = dummy.left; | |
277 this.root_ = current; | |
278 }; | |
279 | |
280 | |
281 /** | |
282 * Performs a preorder traversal of the tree. | |
283 * | |
284 * @param {function(goog.structs.SplayTree.Node)} f Visitor function. | |
285 * @private | |
286 */ | |
287 goog.structs.SplayTree.prototype.traverse_ = function(f) { | |
288 var nodesToVisit = [this.root_]; | |
289 while (nodesToVisit.length > 0) { | |
290 var node = nodesToVisit.shift(); | |
291 if (node == null) { | |
292 continue; | |
293 } | |
294 f(node); | |
295 nodesToVisit.push(node.left); | |
296 nodesToVisit.push(node.right); | |
297 } | |
298 }; | |
299 | |
300 | |
301 /** | |
302 * Constructs a Splay tree node. | |
303 * | |
304 * @param {number} key Key. | |
305 * @param {*} value Value. | |
306 */ | |
307 goog.structs.SplayTree.Node = function(key, value) { | |
308 this.key = key; | |
309 this.value = value; | |
310 }; | |
311 | |
312 | |
313 /** | |
314 * @type {goog.structs.SplayTree.Node} | |
315 */ | |
316 goog.structs.SplayTree.Node.prototype.left = null; | |
317 | |
318 | |
319 /** | |
320 * @type {goog.structs.SplayTree.Node} | |
321 */ | |
322 goog.structs.SplayTree.Node.prototype.right = null; | |
OLD | NEW |