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