1// Copyright 2009 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28
29/**
30 * Constructs a Splay tree.  A splay tree is a self-balancing binary
31 * search tree with the additional property that recently accessed
32 * elements are quick to access again. It performs basic operations
33 * such as insertion, look-up and removal in O(log(n)) amortized time.
34 *
35 * @constructor
36 */
37function SplayTree() {
38};
39
40
41/**
42 * Pointer to the root node of the tree.
43 *
44 * @type {SplayTree.Node}
45 * @private
46 */
47SplayTree.prototype.root_ = null;
48
49
50/**
51 * @return {boolean} Whether the tree is empty.
52 */
53SplayTree.prototype.isEmpty = function() {
54  return !this.root_;
55};
56
57
58
59/**
60 * Inserts a node into the tree with the specified key and value if
61 * the tree does not already contain a node with the specified key. If
62 * the value is inserted, it becomes the root of the tree.
63 *
64 * @param {number} key Key to insert into the tree.
65 * @param {*} value Value to insert into the tree.
66 */
67SplayTree.prototype.insert = function(key, value) {
68  if (this.isEmpty()) {
69    this.root_ = new SplayTree.Node(key, value);
70    return;
71  }
72  // Splay on the key to move the last node on the search path for
73  // the key to the root of the tree.
74  this.splay_(key);
75  if (this.root_.key == key) {
76    return;
77  }
78  var node = new SplayTree.Node(key, value);
79  if (key > this.root_.key) {
80    node.left = this.root_;
81    node.right = this.root_.right;
82    this.root_.right = null;
83  } else {
84    node.right = this.root_;
85    node.left = this.root_.left;
86    this.root_.left = null;
87  }
88  this.root_ = node;
89};
90
91
92/**
93 * Removes a node with the specified key from the tree if the tree
94 * contains a node with this key. The removed node is returned. If the
95 * key is not found, an exception is thrown.
96 *
97 * @param {number} key Key to find and remove from the tree.
98 * @return {SplayTree.Node} The removed node.
99 */
100SplayTree.prototype.remove = function(key) {
101  if (this.isEmpty()) {
102    throw Error('Key not found: ' + key);
103  }
104  this.splay_(key);
105  if (this.root_.key != key) {
106    throw Error('Key not found: ' + key);
107  }
108  var removed = this.root_;
109  if (!this.root_.left) {
110    this.root_ = this.root_.right;
111  } else {
112    var right = this.root_.right;
113    this.root_ = this.root_.left;
114    // Splay to make sure that the new root has an empty right child.
115    this.splay_(key);
116    // Insert the original right child as the right child of the new
117    // root.
118    this.root_.right = right;
119  }
120  return removed;
121};
122
123
124/**
125 * Returns the node having the specified key or null if the tree doesn't contain
126 * a node with the specified key.
127 *
128 * @param {number} key Key to find in the tree.
129 * @return {SplayTree.Node} Node having the specified key.
130 */
131SplayTree.prototype.find = function(key) {
132  if (this.isEmpty()) {
133    return null;
134  }
135  this.splay_(key);
136  return this.root_.key == key ? this.root_ : null;
137};
138
139
140/**
141 * @return {SplayTree.Node} Node having the minimum key value.
142 */
143SplayTree.prototype.findMin = function() {
144  if (this.isEmpty()) {
145    return null;
146  }
147  var current = this.root_;
148  while (current.left) {
149    current = current.left;
150  }
151  return current;
152};
153
154
155/**
156 * @return {SplayTree.Node} Node having the maximum key value.
157 */
158SplayTree.prototype.findMax = function(opt_startNode) {
159  if (this.isEmpty()) {
160    return null;
161  }
162  var current = opt_startNode || this.root_;
163  while (current.right) {
164    current = current.right;
165  }
166  return current;
167};
168
169
170/**
171 * @return {SplayTree.Node} Node having the maximum key value that
172 *     is less or equal to the specified key value.
173 */
174SplayTree.prototype.findGreatestLessThan = function(key) {
175  if (this.isEmpty()) {
176    return null;
177  }
178  // Splay on the key to move the node with the given key or the last
179  // node on the search path to the top of the tree.
180  this.splay_(key);
181  // Now the result is either the root node or the greatest node in
182  // the left subtree.
183  if (this.root_.key <= key) {
184    return this.root_;
185  } else if (this.root_.left) {
186    return this.findMax(this.root_.left);
187  } else {
188    return null;
189  }
190};
191
192
193/**
194 * @return {Array<*>} An array containing all the values of tree's nodes paired
195 *     with keys.
196 */
197SplayTree.prototype.exportKeysAndValues = function() {
198  var result = [];
199  this.traverse_(function(node) { result.push([node.key, node.value]); });
200  return result;
201};
202
203
204/**
205 * @return {Array<*>} An array containing all the values of tree's nodes.
206 */
207SplayTree.prototype.exportValues = function() {
208  var result = [];
209  this.traverse_(function(node) { result.push(node.value); });
210  return result;
211};
212
213
214/**
215 * Perform the splay operation for the given key. Moves the node with
216 * the given key to the top of the tree.  If no node has the given
217 * key, the last node on the search path is moved to the top of the
218 * tree. This is the simplified top-down splaying algorithm from:
219 * "Self-adjusting Binary Search Trees" by Sleator and Tarjan
220 *
221 * @param {number} key Key to splay the tree on.
222 * @private
223 */
224SplayTree.prototype.splay_ = function(key) {
225  if (this.isEmpty()) {
226    return;
227  }
228  // Create a dummy node.  The use of the dummy node is a bit
229  // counter-intuitive: The right child of the dummy node will hold
230  // the L tree of the algorithm.  The left child of the dummy node
231  // will hold the R tree of the algorithm.  Using a dummy node, left
232  // and right will always be nodes and we avoid special cases.
233  var dummy, left, right;
234  dummy = left = right = new SplayTree.Node(null, null);
235  var current = this.root_;
236  while (true) {
237    if (key < current.key) {
238      if (!current.left) {
239        break;
240      }
241      if (key < current.left.key) {
242        // Rotate right.
243        var tmp = current.left;
244        current.left = tmp.right;
245        tmp.right = current;
246        current = tmp;
247        if (!current.left) {
248          break;
249        }
250      }
251      // Link right.
252      right.left = current;
253      right = current;
254      current = current.left;
255    } else if (key > current.key) {
256      if (!current.right) {
257        break;
258      }
259      if (key > current.right.key) {
260        // Rotate left.
261        var tmp = current.right;
262        current.right = tmp.left;
263        tmp.left = current;
264        current = tmp;
265        if (!current.right) {
266          break;
267        }
268      }
269      // Link left.
270      left.right = current;
271      left = current;
272      current = current.right;
273    } else {
274      break;
275    }
276  }
277  // Assemble.
278  left.right = current.left;
279  right.left = current.right;
280  current.left = dummy.right;
281  current.right = dummy.left;
282  this.root_ = current;
283};
284
285
286/**
287 * Performs a preorder traversal of the tree.
288 *
289 * @param {function(SplayTree.Node)} f Visitor function.
290 * @private
291 */
292SplayTree.prototype.traverse_ = function(f) {
293  var nodesToVisit = [this.root_];
294  while (nodesToVisit.length > 0) {
295    var node = nodesToVisit.shift();
296    if (node == null) {
297      continue;
298    }
299    f(node);
300    nodesToVisit.push(node.left);
301    nodesToVisit.push(node.right);
302  }
303};
304
305
306/**
307 * Constructs a Splay tree node.
308 *
309 * @param {number} key Key.
310 * @param {*} value Value.
311 */
312SplayTree.Node = function(key, value) {
313  this.key = key;
314  this.value = value;
315};
316
317
318/**
319 * @type {SplayTree.Node}
320 */
321SplayTree.Node.prototype.left = null;
322
323
324/**
325 * @type {SplayTree.Node}
326 */
327SplayTree.Node.prototype.right = null;
328