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.
8 * @fileoverview Splay tree used by CodeMap.
10 tvcm.exportTo('tracing.importer.v8', function() {
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.
19 function SplayTree() {
24 * Pointer to the root node of the tree.
26 * @type {SplayTree.Node}
29 SplayTree.prototype.root_ = null;
33 * @return {boolean} Whether the tree is empty.
35 SplayTree.prototype.isEmpty = function() {
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.
46 * @param {number} key Key to insert into the tree.
47 * @param {*} value Value to insert into the tree.
49 SplayTree.prototype.insert = function(key, value) {
51 this.root_ = new SplayTree.Node(key, value);
54 // Splay on the key to move the last node on the search path for
55 // the key to the root of the tree.
57 if (this.root_.key == key) {
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;
66 node.right = this.root_;
67 node.left = this.root_.left;
68 this.root_.left = null;
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.
79 * @param {number} key Key to find and remove from the tree.
80 * @return {SplayTree.Node} The removed node.
82 SplayTree.prototype.remove = function(key) {
84 throw Error('Key not found: ' + key);
87 if (this.root_.key != key) {
88 throw Error('Key not found: ' + key);
90 var removed = this.root_;
91 if (!this.root_.left) {
92 this.root_ = this.root_.right;
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.
98 // Insert the original right child as the right child of the new
100 this.root_.right = right;
107 * Returns the node having the specified key or null if the tree doesn't
108 * contain a node with the specified key.
111 * @param {number} key Key to find in the tree.
112 * @return {SplayTree.Node} Node having the specified key.
114 SplayTree.prototype.find = function(key) {
115 if (this.isEmpty()) {
119 return this.root_.key == key ? this.root_ : null;
124 * @return {SplayTree.Node} Node having the minimum key value.
126 SplayTree.prototype.findMin = function() {
127 if (this.isEmpty()) {
130 var current = this.root_;
131 while (current.left) {
132 current = current.left;
139 * @return {SplayTree.Node} Node having the maximum key value.
141 SplayTree.prototype.findMax = function(opt_startNode) {
142 if (this.isEmpty()) {
145 var current = opt_startNode || this.root_;
146 while (current.right) {
147 current = current.right;
154 * @return {SplayTree.Node} Node having the maximum key value that
155 * is less or equal to the specified key value.
157 SplayTree.prototype.findGreatestLessThan = function(key) {
158 if (this.isEmpty()) {
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.
164 // Now the result is either the root node or the greatest node in
166 if (this.root_.key <= key) {
168 } else if (this.root_.left) {
169 return this.findMax(this.root_.left);
177 * @return {Array<*>} An array containing all the values of tree's nodes
181 SplayTree.prototype.exportKeysAndValues = function() {
183 this.traverse_(function(node) { result.push([node.key, node.value]); });
189 * @return {Array<*>} An array containing all the values of tree's nodes.
191 SplayTree.prototype.exportValues = function() {
193 this.traverse_(function(node) { result.push(node.value); });
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
205 * @param {number} key Key to splay the tree on.
208 SplayTree.prototype.splay_ = function(key) {
209 if (this.isEmpty()) {
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_;
221 if (key < current.key) {
225 if (key < current.left.key) {
227 var tmp = current.left;
228 current.left = tmp.right;
236 right.left = current;
238 current = current.left;
239 } else if (key > current.key) {
240 if (!current.right) {
243 if (key > current.right.key) {
245 var tmp = current.right;
246 current.right = tmp.left;
249 if (!current.right) {
254 left.right = current;
256 current = current.right;
262 left.right = current.left;
263 right.left = current.right;
264 current.left = dummy.right;
265 current.right = dummy.left;
266 this.root_ = current;
271 * Performs a preorder traversal of the tree.
273 * @param {function(SplayTree.Node)} f Visitor function.
276 SplayTree.prototype.traverse_ = function(f) {
277 var nodesToVisit = [this.root_];
278 while (nodesToVisit.length > 0) {
279 var node = nodesToVisit.shift();
284 nodesToVisit.push(node.left);
285 nodesToVisit.push(node.right);
291 * Constructs a Splay tree node.
293 * @param {number} key Key.
294 * @param {*} value Value.
296 SplayTree.Node = function(key, value) {
303 * @type {SplayTree.Node}
305 SplayTree.Node.prototype.left = null;
309 * @type {SplayTree.Node}
311 SplayTree.Node.prototype.right = null;