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 /** 30 * Constructs a Splay tree. A splay tree is a self-balancing binary 31 * search tree with the additional property that recently accessed 32 * elements are quick to access again. It performs basic operations 33 * such as insertion, look-up and removal in O(log(n)) amortized time. 34 * 35 * @constructor 36 */ 37 function SplayTree() { 38 }; 39 40 41 /** 42 * Pointer to the root node of the tree. 43 * 44 * @type {SplayTree.Node} 45 * @private 46 */ 47 SplayTree.prototype.root_ = null; 48 49 50 /** 51 * @return {boolean} Whether the tree is empty. 52 */ 53 SplayTree.prototype.isEmpty = function() { 54 return !this.root_; 55 }; 56 57 58 59 /** 60 * Inserts a node into the tree with the specified key and value if 61 * the tree does not already contain a node with the specified key. If 62 * the value is inserted, it becomes the root of the tree. 63 * 64 * @param {number} key Key to insert into the tree. 65 * @param {*} value Value to insert into the tree. 66 */ 67 SplayTree.prototype.insert = function(key, value) { 68 if (this.isEmpty()) { 69 this.root_ = new SplayTree.Node(key, value); 70 return; 71 } 72 // Splay on the key to move the last node on the search path for 73 // the key to the root of the tree. 74 this.splay_(key); 75 if (this.root_.key == key) { 76 return; 77 } 78 var node = new SplayTree.Node(key, value); 79 if (key > this.root_.key) { 80 node.left = this.root_; 81 node.right = this.root_.right; 82 this.root_.right = null; 83 } else { 84 node.right = this.root_; 85 node.left = this.root_.left; 86 this.root_.left = null; 87 } 88 this.root_ = node; 89 }; 90 91 92 /** 93 * Removes a node with the specified key from the tree if the tree 94 * contains a node with this key. The removed node is returned. If the 95 * key is not found, an exception is thrown. 96 * 97 * @param {number} key Key to find and remove from the tree. 98 * @return {SplayTree.Node} The removed node. 99 */ 100 SplayTree.prototype.remove = function(key) { 101 if (this.isEmpty()) { 102 throw Error('Key not found: ' + key); 103 } 104 this.splay_(key); 105 if (this.root_.key != key) { 106 throw Error('Key not found: ' + key); 107 } 108 var removed = this.root_; 109 if (!this.root_.left) { 110 this.root_ = this.root_.right; 111 } else { 112 var right = this.root_.right; 113 this.root_ = this.root_.left; 114 // Splay to make sure that the new root has an empty right child. 115 this.splay_(key); 116 // Insert the original right child as the right child of the new 117 // root. 118 this.root_.right = right; 119 } 120 return removed; 121 }; 122 123 124 /** 125 * Returns the node having the specified key or null if the tree doesn't contain 126 * a node with the specified key. 127 * 128 * @param {number} key Key to find in the tree. 129 * @return {SplayTree.Node} Node having the specified key. 130 */ 131 SplayTree.prototype.find = function(key) { 132 if (this.isEmpty()) { 133 return null; 134 } 135 this.splay_(key); 136 return this.root_.key == key ? this.root_ : null; 137 }; 138 139 140 /** 141 * @return {SplayTree.Node} Node having the minimum key value. 142 */ 143 SplayTree.prototype.findMin = function() { 144 if (this.isEmpty()) { 145 return null; 146 } 147 var current = this.root_; 148 while (current.left) { 149 current = current.left; 150 } 151 return current; 152 }; 153 154 155 /** 156 * @return {SplayTree.Node} Node having the maximum key value. 157 */ 158 SplayTree.prototype.findMax = function(opt_startNode) { 159 if (this.isEmpty()) { 160 return null; 161 } 162 var current = opt_startNode || this.root_; 163 while (current.right) { 164 current = current.right; 165 } 166 return current; 167 }; 168 169 170 /** 171 * @return {SplayTree.Node} Node having the maximum key value that 172 * is less or equal to the specified key value. 173 */ 174 SplayTree.prototype.findGreatestLessThan = function(key) { 175 if (this.isEmpty()) { 176 return null; 177 } 178 // Splay on the key to move the node with the given key or the last 179 // node on the search path to the top of the tree. 180 this.splay_(key); 181 // Now the result is either the root node or the greatest node in 182 // the left subtree. 183 if (this.root_.key <= key) { 184 return this.root_; 185 } else if (this.root_.left) { 186 return this.findMax(this.root_.left); 187 } else { 188 return null; 189 } 190 }; 191 192 193 /** 194 * @return {Array<*>} An array containing all the values of tree's nodes. 195 */ 196 SplayTree.prototype.exportValues = function() { 197 var result = []; 198 this.traverse_(function(node) { result.push(node.value); }); 199 return result; 200 }; 201 202 203 /** 204 * Perform the splay operation for the given key. Moves the node with 205 * the given key to the top of the tree. If no node has the given 206 * key, the last node on the search path is moved to the top of the 207 * tree. This is the simplified top-down splaying algorithm from: 208 * "Self-adjusting Binary Search Trees" by Sleator and Tarjan 209 * 210 * @param {number} key Key to splay the tree on. 211 * @private 212 */ 213 SplayTree.prototype.splay_ = function(key) { 214 if (this.isEmpty()) { 215 return; 216 } 217 // Create a dummy node. The use of the dummy node is a bit 218 // counter-intuitive: The right child of the dummy node will hold 219 // the L tree of the algorithm. The left child of the dummy node 220 // will hold the R tree of the algorithm. Using a dummy node, left 221 // and right will always be nodes and we avoid special cases. 222 var dummy, left, right; 223 dummy = left = right = new SplayTree.Node(null, null); 224 var current = this.root_; 225 while (true) { 226 if (key < current.key) { 227 if (!current.left) { 228 break; 229 } 230 if (key < current.left.key) { 231 // Rotate right. 232 var tmp = current.left; 233 current.left = tmp.right; 234 tmp.right = current; 235 current = tmp; 236 if (!current.left) { 237 break; 238 } 239 } 240 // Link right. 241 right.left = current; 242 right = current; 243 current = current.left; 244 } else if (key > current.key) { 245 if (!current.right) { 246 break; 247 } 248 if (key > current.right.key) { 249 // Rotate left. 250 var tmp = current.right; 251 current.right = tmp.left; 252 tmp.left = current; 253 current = tmp; 254 if (!current.right) { 255 break; 256 } 257 } 258 // Link left. 259 left.right = current; 260 left = current; 261 current = current.right; 262 } else { 263 break; 264 } 265 } 266 // Assemble. 267 left.right = current.left; 268 right.left = current.right; 269 current.left = dummy.right; 270 current.right = dummy.left; 271 this.root_ = current; 272 }; 273 274 275 /** 276 * Performs a preorder traversal of the tree. 277 * 278 * @param {function(SplayTree.Node)} f Visitor function. 279 * @private 280 */ 281 SplayTree.prototype.traverse_ = function(f) { 282 var nodesToVisit = [this.root_]; 283 while (nodesToVisit.length > 0) { 284 var node = nodesToVisit.shift(); 285 if (node == null) { 286 continue; 287 } 288 f(node); 289 nodesToVisit.push(node.left); 290 nodesToVisit.push(node.right); 291 } 292 }; 293 294 295 /** 296 * Constructs a Splay tree node. 297 * 298 * @param {number} key Key. 299 * @param {*} value Value. 300 */ 301 SplayTree.Node = function(key, value) { 302 this.key = key; 303 this.value = value; 304 }; 305 306 307 /** 308 * @type {SplayTree.Node} 309 */ 310 SplayTree.Node.prototype.left = null; 311 312 313 /** 314 * @type {SplayTree.Node} 315 */ 316 SplayTree.Node.prototype.right = null; 317