src/third_party/trace-viewer/src/tracing/importer/v8/splaytree.js

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