1a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Copyright 2009 the V8 project authors. All rights reserved. 2a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Redistribution and use in source and binary forms, with or without 3a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// modification, are permitted provided that the following conditions are 4a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// met: 5a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// 6a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// * Redistributions of source code must retain the above copyright 7a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// notice, this list of conditions and the following disclaimer. 8a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// * Redistributions in binary form must reproduce the above 9a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// copyright notice, this list of conditions and the following 10a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// disclaimer in the documentation and/or other materials provided 11a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// with the distribution. 12a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// * Neither the name of Google Inc. nor the names of its 13a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// contributors may be used to endorse or promote products derived 14a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// from this software without specific prior written permission. 15a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// 16a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 28a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// This benchmark is based on a JavaScript log processing module used 29a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// by the V8 profiler to generate execution time profiles for runs of 30a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// JavaScript applications, and it effectively measures how fast the 31a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// JavaScript engine is at allocating nodes and reclaiming the memory 32a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// used for old nodes. Because of the way splay trees work, the engine 33a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// also has to deal with a lot of changes to the large tree object 34a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// graph. 35a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 360d5e116f6aee03185f237311a943491bb079a768Kristian Monsenvar Splay = new BenchmarkSuite('Splay', 81491, [ 37a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block new Benchmark("Splay", SplayRun, SplaySetup, SplayTearDown) 38a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block]); 39a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 40a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 41a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Configuration. 42a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockvar kSplayTreeSize = 8000; 43a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockvar kSplayTreeModifications = 80; 44a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockvar kSplayTreePayloadDepth = 5; 45a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 46a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockvar splayTree = null; 47a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 48a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 4925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsenfunction GeneratePayloadTree(depth, tag) { 50a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (depth == 0) { 51a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return { 52a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block array : [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ], 5325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen string : 'String for key ' + tag + ' in leaf node' 54a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block }; 55a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 56a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return { 5725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen left: GeneratePayloadTree(depth - 1, tag), 5825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen right: GeneratePayloadTree(depth - 1, tag) 59a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block }; 60a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 61a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 62a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 63a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 64a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction GenerateKey() { 65a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // The benchmark framework guarantees that Math.random is 66a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // deterministic; see base.js. 67a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return Math.random(); 68a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 69a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 70a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 71a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction InsertNewNode() { 72a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Insert new node with a unique key. 73a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var key; 74a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block do { 75a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block key = GenerateKey(); 76a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } while (splayTree.find(key) != null); 7725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen var payload = GeneratePayloadTree(kSplayTreePayloadDepth, String(key)); 7825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen splayTree.insert(key, payload); 79a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return key; 80a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 81a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 82a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 83a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 84a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction SplaySetup() { 85a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block splayTree = new SplayTree(); 86a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < kSplayTreeSize; i++) InsertNewNode(); 87a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 88a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 89a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 90a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction SplayTearDown() { 91a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Allow the garbage collector to reclaim the memory 92a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // used by the splay tree no matter how we exit the 93a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // tear down function. 94a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var keys = splayTree.exportKeys(); 95a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block splayTree = null; 96a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 97a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Verify that the splay tree has the right size. 98a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var length = keys.length; 99a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (length != kSplayTreeSize) { 100a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block throw new Error("Splay tree has wrong size"); 101a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 102a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 103a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Verify that the splay tree has sorted, unique keys. 104a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < length - 1; i++) { 105a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (keys[i] >= keys[i + 1]) { 106a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block throw new Error("Splay tree not sorted"); 107a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 108a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 109a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 110a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 111a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 112a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction SplayRun() { 113a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Replace a few nodes in the splay tree. 114a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < kSplayTreeModifications; i++) { 115a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var key = InsertNewNode(); 116a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var greatest = splayTree.findGreatestLessThan(key); 117a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (greatest == null) splayTree.remove(key); 118a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block else splayTree.remove(greatest.key); 119a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 120a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 121a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 122a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 123a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 124a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Constructs a Splay tree. A splay tree is a self-balancing binary 125a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * search tree with the additional property that recently accessed 126a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * elements are quick to access again. It performs basic operations 127a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * such as insertion, look-up and removal in O(log(n)) amortized time. 128a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * 129a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @constructor 130a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 131a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction SplayTree() { 132a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 133a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 134a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 135a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 136a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Pointer to the root node of the tree. 137a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * 138a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @type {SplayTree.Node} 139a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @private 140a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 141a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockSplayTree.prototype.root_ = null; 142a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 143a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 144a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 145a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @return {boolean} Whether the tree is empty. 146a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 147a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockSplayTree.prototype.isEmpty = function() { 148a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return !this.root_; 149a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 150a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 151a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 152a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 153a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Inserts a node into the tree with the specified key and value if 154a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * the tree does not already contain a node with the specified key. If 155a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * the value is inserted, it becomes the root of the tree. 156a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * 157a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @param {number} key Key to insert into the tree. 158a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @param {*} value Value to insert into the tree. 159a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 160a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockSplayTree.prototype.insert = function(key, value) { 161a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.isEmpty()) { 162a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.root_ = new SplayTree.Node(key, value); 163a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return; 164a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 165a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Splay on the key to move the last node on the search path for 166a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // the key to the root of the tree. 167a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.splay_(key); 168a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.root_.key == key) { 169a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return; 170a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 171a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var node = new SplayTree.Node(key, value); 172a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (key > this.root_.key) { 173a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block node.left = this.root_; 174a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block node.right = this.root_.right; 175a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.root_.right = null; 176a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 177a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block node.right = this.root_; 178a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block node.left = this.root_.left; 179a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.root_.left = null; 180a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 181a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.root_ = node; 182a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 183a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 184a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 185a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 186a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Removes a node with the specified key from the tree if the tree 187a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * contains a node with this key. The removed node is returned. If the 188a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * key is not found, an exception is thrown. 189a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * 190a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @param {number} key Key to find and remove from the tree. 191a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @return {SplayTree.Node} The removed node. 192a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 193a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockSplayTree.prototype.remove = function(key) { 194a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.isEmpty()) { 195a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block throw Error('Key not found: ' + key); 196a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 197a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.splay_(key); 198a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.root_.key != key) { 199a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block throw Error('Key not found: ' + key); 200a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 201a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var removed = this.root_; 202a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!this.root_.left) { 203a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.root_ = this.root_.right; 204a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 205a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var right = this.root_.right; 206a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.root_ = this.root_.left; 207a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Splay to make sure that the new root has an empty right child. 208a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.splay_(key); 209a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Insert the original right child as the right child of the new 210a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // root. 211a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.root_.right = right; 212a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 213a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return removed; 214a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 215a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 216a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 217a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 218a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Returns the node having the specified key or null if the tree doesn't contain 219a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * a node with the specified key. 220a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * 221a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @param {number} key Key to find in the tree. 222a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @return {SplayTree.Node} Node having the specified key. 223a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 224a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockSplayTree.prototype.find = function(key) { 225a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.isEmpty()) { 226a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return null; 227a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 228a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.splay_(key); 229a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this.root_.key == key ? this.root_ : null; 230a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 231a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 232a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 233a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 2348defd9ff6930b4e24729971a61cf7469daf119beSteve Block * @return {SplayTree.Node} Node having the maximum key value. 2358defd9ff6930b4e24729971a61cf7469daf119beSteve Block */ 2368defd9ff6930b4e24729971a61cf7469daf119beSteve BlockSplayTree.prototype.findMax = function(opt_startNode) { 2378defd9ff6930b4e24729971a61cf7469daf119beSteve Block if (this.isEmpty()) { 2388defd9ff6930b4e24729971a61cf7469daf119beSteve Block return null; 2398defd9ff6930b4e24729971a61cf7469daf119beSteve Block } 2408defd9ff6930b4e24729971a61cf7469daf119beSteve Block var current = opt_startNode || this.root_; 2418defd9ff6930b4e24729971a61cf7469daf119beSteve Block while (current.right) { 2428defd9ff6930b4e24729971a61cf7469daf119beSteve Block current = current.right; 2438defd9ff6930b4e24729971a61cf7469daf119beSteve Block } 2448defd9ff6930b4e24729971a61cf7469daf119beSteve Block return current; 2458defd9ff6930b4e24729971a61cf7469daf119beSteve Block}; 2468defd9ff6930b4e24729971a61cf7469daf119beSteve Block 2478defd9ff6930b4e24729971a61cf7469daf119beSteve Block 2488defd9ff6930b4e24729971a61cf7469daf119beSteve Block/** 249a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @return {SplayTree.Node} Node having the maximum key value that 2508defd9ff6930b4e24729971a61cf7469daf119beSteve Block * is less than the specified key value. 251a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 252a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockSplayTree.prototype.findGreatestLessThan = function(key) { 253a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.isEmpty()) { 254a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return null; 255a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 256a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Splay on the key to move the node with the given key or the last 257a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // node on the search path to the top of the tree. 258a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.splay_(key); 259a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Now the result is either the root node or the greatest node in 260a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // the left subtree. 2618defd9ff6930b4e24729971a61cf7469daf119beSteve Block if (this.root_.key < key) { 262a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this.root_; 263a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else if (this.root_.left) { 264a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this.findMax(this.root_.left); 265a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 266a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return null; 267a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 268a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 269a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 270a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 271a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 272a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @return {Array<*>} An array containing all the keys of tree's nodes. 273a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 274a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockSplayTree.prototype.exportKeys = function() { 275a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var result = []; 276a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!this.isEmpty()) { 277a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.root_.traverse_(function(node) { result.push(node.key); }); 278a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 279a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return result; 280a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 281a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 282a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 283a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 284a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Perform the splay operation for the given key. Moves the node with 285a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * the given key to the top of the tree. If no node has the given 286a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * key, the last node on the search path is moved to the top of the 287a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * tree. This is the simplified top-down splaying algorithm from: 288a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * "Self-adjusting Binary Search Trees" by Sleator and Tarjan 289a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * 290a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @param {number} key Key to splay the tree on. 291a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @private 292a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 293a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockSplayTree.prototype.splay_ = function(key) { 294a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.isEmpty()) { 295a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return; 296a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 297a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Create a dummy node. The use of the dummy node is a bit 298a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // counter-intuitive: The right child of the dummy node will hold 299a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // the L tree of the algorithm. The left child of the dummy node 300a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // will hold the R tree of the algorithm. Using a dummy node, left 301a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // and right will always be nodes and we avoid special cases. 302a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var dummy, left, right; 303a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block dummy = left = right = new SplayTree.Node(null, null); 304a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = this.root_; 305a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block while (true) { 306a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (key < current.key) { 307a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!current.left) { 308a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block break; 309a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 310a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (key < current.left.key) { 311a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Rotate right. 312a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var tmp = current.left; 313a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block current.left = tmp.right; 314a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tmp.right = current; 315a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block current = tmp; 316a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!current.left) { 317a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block break; 318a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 319a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 320a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Link right. 321a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block right.left = current; 322a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block right = current; 323a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block current = current.left; 324a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else if (key > current.key) { 325a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!current.right) { 326a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block break; 327a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 328a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (key > current.right.key) { 329a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Rotate left. 330a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var tmp = current.right; 331a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block current.right = tmp.left; 332a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tmp.left = current; 333a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block current = tmp; 334a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!current.right) { 335a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block break; 336a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 337a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 338a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Link left. 339a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block left.right = current; 340a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block left = current; 341a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block current = current.right; 342a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 343a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block break; 344a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 345a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 346a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Assemble. 347a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block left.right = current.left; 348a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block right.left = current.right; 349a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block current.left = dummy.right; 350a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block current.right = dummy.left; 351a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.root_ = current; 352a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 353a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 354a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 355a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 356a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Constructs a Splay tree node. 357a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * 358a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @param {number} key Key. 359a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @param {*} value Value. 360a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 361a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockSplayTree.Node = function(key, value) { 362a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.key = key; 363a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.value = value; 364a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 365a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 366a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 367a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 368a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @type {SplayTree.Node} 369a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 370a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockSplayTree.Node.prototype.left = null; 371a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 372a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 373a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 374a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @type {SplayTree.Node} 375a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 376a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockSplayTree.Node.prototype.right = null; 377a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 378a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 379a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 380a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Performs an ordered traversal of the subtree starting at 381a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * this SplayTree.Node. 382a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * 383a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @param {function(SplayTree.Node)} f Visitor function. 384a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * @private 385a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 386a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockSplayTree.Node.prototype.traverse_ = function(f) { 387a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var current = this; 388a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block while (current) { 389a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var left = current.left; 390a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (left) left.traverse_(f); 391a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block f(current); 392a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block current = current.right; 393a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 394a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 395