src/third_party/trace-viewer/trace_viewer/tracing/importer/v8/splaytree.html

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