src/v8/tools/splaytree.js

   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 paired
 195  *     with keys.
 196  */
 197 SplayTree.prototype.exportKeysAndValues = function() {
 198   var result = [];
 199   this.traverse_(function(node) { result.push([node.key, node.value]); });
 200   return result;
 201 };
 202
 203
 204 /**
 205  * @return {Array<*>} An array containing all the values of tree's nodes.
 206  */
 207 SplayTree.prototype.exportValues = function() {
 208   var result = [];
 209   this.traverse_(function(node) { result.push(node.value); });
 210   return result;
 211 };
 212
 213
 214 /**
 215  * Perform the splay operation for the given key. Moves the node with
 216  * the given key to the top of the tree.  If no node has the given
 217  * key, the last node on the search path is moved to the top of the
 218  * tree. This is the simplified top-down splaying algorithm from:
 219  * "Self-adjusting Binary Search Trees" by Sleator and Tarjan
 220  *
 221  * @param {number} key Key to splay the tree on.
 222  * @private
 223  */
 224 SplayTree.prototype.splay_ = function(key) {
 225   if (this.isEmpty()) {
 226     return;
 227   }
 228   // Create a dummy node.  The use of the dummy node is a bit
 229   // counter-intuitive: The right child of the dummy node will hold
 230   // the L tree of the algorithm.  The left child of the dummy node
 231   // will hold the R tree of the algorithm.  Using a dummy node, left
 232   // and right will always be nodes and we avoid special cases.
 233   var dummy, left, right;
 234   dummy = left = right = new SplayTree.Node(null, null);
 235   var current = this.root_;
 236   while (true) {
 237     if (key < current.key) {
 238       if (!current.left) {
 239         break;
 240       }
 241       if (key < current.left.key) {
 242         // Rotate right.
 243         var tmp = current.left;
 244         current.left = tmp.right;
 245         tmp.right = current;
 246         current = tmp;
 247         if (!current.left) {
 248           break;
 249         }
 250       }
 251       // Link right.
 252       right.left = current;
 253       right = current;
 254       current = current.left;
 255     } else if (key > current.key) {
 256       if (!current.right) {
 257         break;
 258       }
 259       if (key > current.right.key) {
 260         // Rotate left.
 261         var tmp = current.right;
 262         current.right = tmp.left;
 263         tmp.left = current;
 264         current = tmp;
 265         if (!current.right) {
 266           break;
 267         }
 268       }
 269       // Link left.
 270       left.right = current;
 271       left = current;
 272       current = current.right;
 273     } else {
 274       break;
 275     }
 276   }
 277   // Assemble.
 278   left.right = current.left;
 279   right.left = current.right;
 280   current.left = dummy.right;
 281   current.right = dummy.left;
 282   this.root_ = current;
 283 };
 284
 285
 286 /**
 287  * Performs a preorder traversal of the tree.
 288  *
 289  * @param {function(SplayTree.Node)} f Visitor function.
 290  * @private
 291  */
 292 SplayTree.prototype.traverse_ = function(f) {
 293   var nodesToVisit = [this.root_];
 294   while (nodesToVisit.length > 0) {
 295     var node = nodesToVisit.shift();
 296     if (node == null) {
 297       continue;
 298     }
 299     f(node);
 300     nodesToVisit.push(node.left);
 301     nodesToVisit.push(node.right);
 302   }
 303 };
 304
 305
 306 /**
 307  * Constructs a Splay tree node.
 308  *
 309  * @param {number} key Key.
 310  * @param {*} value Value.
 311  */
 312 SplayTree.Node = function(key, value) {
 313   this.key = key;
 314   this.value = value;
 315 };
 316
 317
 318 /**
 319  * @type {SplayTree.Node}
 320  */
 321 SplayTree.Node.prototype.left = null;
 322
 323
 324 /**
 325  * @type {SplayTree.Node}
 326  */
 327 SplayTree.Node.prototype.right = null;