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 */
10base.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});
317