1<!DOCTYPE html>
2<!--
3Copyright (c) 2012 The Chromium Authors. All rights reserved.
4Use of this source code is governed by a BSD-style license that can be
5found in the LICENSE file.
6-->
7<link rel="import" href="/tracing/base/base.html">
8<script>
9'use strict';
10
11/**
12 * @fileoverview Splay tree used by CodeMap.
13 */
14tr.exportTo('tr.e.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>
307