← Back to branch summary

~ubuntu-branches/ubuntu/saucy/nodejs/saucy-proposed

« back to all changes in this revision

Viewing changes to deps/v8/benchmarks/spinning-balls/splay-tree.js

  • Committer: Package Import Robot
  • Author(s): Jérémy Lal
  • Date: 2013-08-14 00:16:46 UTC
  • mfrom: (7.1.40 sid)
  • Revision ID: package-import@ubuntu.com-20130814001646-bzlysfh8sd6mukbo
Tags: 0.10.15~dfsg1-4
* Update 2005 patch, adding a handful of tests that can fail on
  slow platforms.
* Add 1004 patch to fix test failures when writing NaN to buffer
  on mipsel.

Show diffs side-by-side

added added

removed removed

Lines of Context:
deps/v8/benchmarks/spinning-balls/splay-tree.js
 
1
// Copyright 2011 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
 * Constructs a Splay tree.  A splay tree is a self-balancing binary
 
30
 * search tree with the additional property that recently accessed
 
31
 * elements are quick to access again. It performs basic operations
 
32
 * such as insertion, look-up and removal in O(log(n)) amortized time.
 
33
 *
 
34
 * @constructor
 
35
 */
 
36
function SplayTree() {
 
37
};
 
38
 
 
39
 
 
40
/**
 
41
 * Pointer to the root node of the tree.
 
42
 *
 
43
 * @type {SplayTree.Node}
 
44
 * @private
 
45
 */
 
46
SplayTree.prototype.root_ = null;
 
47
 
 
48
 
 
49
/**
 
50
 * @return {boolean} Whether the tree is empty.
 
51
 */
 
52
SplayTree.prototype.isEmpty = function() {
 
53
  return !this.root_;
 
54
};
 
55
 
 
56
 
 
57
/**
 
58
 * Inserts a node into the tree with the specified key and value if
 
59
 * the tree does not already contain a node with the specified key. If
 
60
 * the value is inserted, it becomes the root of the tree.
 
61
 *
 
62
 * @param {number} key Key to insert into the tree.
 
63
 * @param {*} value Value to insert into the tree.
 
64
 */
 
65
SplayTree.prototype.insert = function(key, value) {
 
66
  if (this.isEmpty()) {
 
67
    this.root_ = new SplayTree.Node(key, value);
 
68
    return;
 
69
  }
 
70
  // Splay on the key to move the last node on the search path for
 
71
  // the key to the root of the tree.
 
72
  this.splay_(key);
 
73
  if (this.root_.key == key) {
 
74
    return;
 
75
  }
 
76
  var node = new SplayTree.Node(key, value);
 
77
  if (key > this.root_.key) {
 
78
    node.left = this.root_;
 
79
    node.right = this.root_.right;
 
80
    this.root_.right = null;
 
81
  } else {
 
82
    node.right = this.root_;
 
83
    node.left = this.root_.left;
 
84
    this.root_.left = null;
 
85
  }
 
86
  this.root_ = node;
 
87
};
 
88
 
 
89
 
 
90
/**
 
91
 * Removes a node with the specified key from the tree if the tree
 
92
 * contains a node with this key. The removed node is returned. If the
 
93
 * key is not found, an exception is thrown.
 
94
 *
 
95
 * @param {number} key Key to find and remove from the tree.
 
96
 * @return {SplayTree.Node} The removed node.
 
97
 */
 
98
SplayTree.prototype.remove = function(key) {
 
99
  if (this.isEmpty()) {
 
100
    throw Error('Key not found: ' + key);
 
101
  }
 
102
  this.splay_(key);
 
103
  if (this.root_.key != key) {
 
104
    throw Error('Key not found: ' + key);
 
105
  }
 
106
  var removed = this.root_;
 
107
  if (!this.root_.left) {
 
108
    this.root_ = this.root_.right;
 
109
  } else {
 
110
    var right = this.root_.right;
 
111
    this.root_ = this.root_.left;
 
112
    // Splay to make sure that the new root has an empty right child.
 
113
    this.splay_(key);
 
114
    // Insert the original right child as the right child of the new
 
115
    // root.
 
116
    this.root_.right = right;
 
117
  }
 
118
  return removed;
 
119
};
 
120
 
 
121
 
 
122
/**
 
123
 * Returns the node having the specified key or null if the tree doesn't contain
 
124
 * a node with the specified key.
 
125
 *
 
126
 * @param {number} key Key to find in the tree.
 
127
 * @return {SplayTree.Node} Node having the specified key.
 
128
 */
 
129
SplayTree.prototype.find = function(key) {
 
130
  if (this.isEmpty()) {
 
131
    return null;
 
132
  }
 
133
  this.splay_(key);
 
134
  return this.root_.key == key ? this.root_ : null;
 
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 than 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 keys of tree's nodes.
 
178
 */
 
179
SplayTree.prototype.exportKeys = function() {
 
180
  var result = [];
 
181
  if (!this.isEmpty()) {
 
182
    this.root_.traverse_(function(node) { result.push(node.key); });
 
183
  }
 
184
  return result;
 
185
};
 
186
 
 
187
 
 
188
/**
 
189
 * Perform the splay operation for the given key. Moves the node with
 
190
 * the given key to the top of the tree.  If no node has the given
 
191
 * key, the last node on the search path is moved to the top of the
 
192
 * tree. This is the simplified top-down splaying algorithm from:
 
193
 * "Self-adjusting Binary Search Trees" by Sleator and Tarjan
 
194
 *
 
195
 * @param {number} key Key to splay the tree on.
 
196
 * @private
 
197
 */
 
198
SplayTree.prototype.splay_ = function(key) {
 
199
  if (this.isEmpty()) {
 
200
    return;
 
201
  }
 
202
  // Create a dummy node.  The use of the dummy node is a bit
 
203
  // counter-intuitive: The right child of the dummy node will hold
 
204
  // the L tree of the algorithm.  The left child of the dummy node
 
205
  // will hold the R tree of the algorithm.  Using a dummy node, left
 
206
  // and right will always be nodes and we avoid special cases.
 
207
  var dummy, left, right;
 
208
  dummy = left = right = new SplayTree.Node(null, null);
 
209
  var current = this.root_;
 
210
  while (true) {
 
211
    if (key < current.key) {
 
212
      if (!current.left) {
 
213
        break;
 
214
      }
 
215
      if (key < current.left.key) {
 
216
        // Rotate right.
 
217
        var tmp = current.left;
 
218
        current.left = tmp.right;
 
219
        tmp.right = current;
 
220
        current = tmp;
 
221
        if (!current.left) {
 
222
          break;
 
223
        }
 
224
      }
 
225
      // Link right.
 
226
      right.left = current;
 
227
      right = current;
 
228
      current = current.left;
 
229
    } else if (key > current.key) {
 
230
      if (!current.right) {
 
231
        break;
 
232
      }
 
233
      if (key > current.right.key) {
 
234
        // Rotate left.
 
235
        var tmp = current.right;
 
236
        current.right = tmp.left;
 
237
        tmp.left = current;
 
238
        current = tmp;
 
239
        if (!current.right) {
 
240
          break;
 
241
        }
 
242
      }
 
243
      // Link left.
 
244
      left.right = current;
 
245
      left = current;
 
246
      current = current.right;
 
247
    } else {
 
248
      break;
 
249
    }
 
250
  }
 
251
  // Assemble.
 
252
  left.right = current.left;
 
253
  right.left = current.right;
 
254
  current.left = dummy.right;
 
255
  current.right = dummy.left;
 
256
  this.root_ = current;
 
257
};
 
258
 
 
259
 
 
260
/**
 
261
 * Constructs a Splay tree node.
 
262
 *
 
263
 * @param {number} key Key.
 
264
 * @param {*} value Value.
 
265
 */
 
266
SplayTree.Node = function(key, value) {
 
267
  this.key = key;
 
268
  this.value = value;
 
269
};
 
270
 
 
271
 
 
272
/**
 
273
 * @type {SplayTree.Node}
 
274
 */
 
275
SplayTree.Node.prototype.left = null;
 
276
 
 
277
 
 
278
/**
 
279
 * @type {SplayTree.Node}
 
280
 */
 
281
SplayTree.Node.prototype.right = null;
 
282
 
 
283
 
 
284
/**
 
285
 * Performs an ordered traversal of the subtree starting at
 
286
 * this SplayTree.Node.
 
287
 *
 
288
 * @param {function(SplayTree.Node)} f Visitor function.
 
289
 * @private
 
290
 */
 
291
SplayTree.Node.prototype.traverse_ = function(f) {
 
292
  var current = this;
 
293
  while (current) {
 
294
    var left = current.left;
 
295
    if (left) left.traverse_(f);
 
296
    f(current);
 
297
    current = current.right;
 
298
  }
 
299
};
 
300
 
 
301
SplayTree.prototype.traverseBreadthFirst = function (f) {
 
302
  if (f(this.root_.value)) return;
 
303
 
 
304
  var stack = [this.root_];
 
305
  var length = 1;
 
306
 
 
307
  while (length > 0) {
 
308
    var new_stack = new Array(stack.length * 2);
 
309
    var new_length = 0;
 
310
    for (var i = 0; i < length; i++) {
 
311
      var n = stack[i];
 
312
      var l = n.left;
 
313
      var r = n.right;
 
314
      if (l) {
 
315
        if (f(l.value)) return;
 
316
        new_stack[new_length++] = l;
 
317
      }
 
318
      if (r) {
 
319
        if (f(r.value)) return;
 
320
        new_stack[new_length++] = r;
 
321
      }
 
322
    }
 
323
    stack = new_stack;
 
324
    length = new_length;
 
325
  }
 
326
};