8f10239d480e129f29ee97f329831df147e75586
[platform/framework/web/crosswalk.git] / 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 });