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