15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Copyright 2009 the V8 project authors. All rights reserved. 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Redistribution and use in source and binary forms, with or without 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// modification, are permitted provided that the following conditions are 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// met: 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// * Redistributions of source code must retain the above copyright 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// notice, this list of conditions and the following disclaimer. 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// * Redistributions in binary form must reproduce the above 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// copyright notice, this list of conditions and the following 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// disclaimer in the documentation and/or other materials provided 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// with the distribution. 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// * Neither the name of Google Inc. nor the names of its 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// contributors may be used to endorse or promote products derived 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// from this software without specific prior written permission. 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// This benchmark is based on a JavaScript log processing module used 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// by the V8 profiler to generate execution time profiles for runs of 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// JavaScript applications, and it effectively measures how fast the 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// JavaScript engine is at allocating nodes and reclaiming the memory 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// used for old nodes. Because of the way splay trees work, the engine 335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// also has to deal with a lot of changes to the large tree object 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// graph. 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Configuration. 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)var kSplayTreeSize = 8000; 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)var kSplayTreeModifications = 80; 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)var kSplayTreePayloadDepth = 5; 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)var splayTree = null; 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function GeneratePayloadTree(depth, key) { 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (depth == 0) { 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return { 475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) array : [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ], 485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) string : 'String for key ' + key + ' in leaf node' 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return { 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) left: GeneratePayloadTree(depth - 1, key), 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) right: GeneratePayloadTree(depth - 1, key) 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function GenerateKey() { 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The benchmark framework guarantees that Math.random is 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // deterministic; see base.js. 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return Math.random(); 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function InsertNewNode() { 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Insert new node with a unique key. 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var key; 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) do { 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) key = GenerateKey(); 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } while (splayTree.find(key) != null); 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) splayTree.insert(key, GeneratePayloadTree(kSplayTreePayloadDepth, key)); 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return key; 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function SplaySetup() { 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) splayTree = new SplayTree(); 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < kSplayTreeSize; i++) InsertNewNode(); 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function SplayTearDown() { 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Allow the garbage collector to reclaim the memory 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // used by the splay tree no matter how we exit the 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // tear down function. 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var keys = splayTree.exportKeys(); 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) splayTree = null; 905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Verify that the splay tree has the right size. 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var length = keys.length; 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (length != kSplayTreeSize) { 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) throw new Error("Splay tree has wrong size"); 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Verify that the splay tree has sorted, unique keys. 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < length - 1; i++) { 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (keys[i] >= keys[i + 1]) { 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) throw new Error("Splay tree not sorted"); 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function SplayRun() { 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Replace a few nodes in the splay tree. 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < kSplayTreeModifications; i++) { 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var key = InsertNewNode(); 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var greatest = splayTree.findGreatestLessThan(key); 1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (greatest == null) splayTree.remove(key); 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else splayTree.remove(greatest.key); 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Constructs a Splay tree. A splay tree is a self-balancing binary 1195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * search tree with the additional property that recently accessed 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * elements are quick to access again. It performs basic operations 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * such as insertion, look-up and removal in O(log(n)) amortized time. 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @constructor 1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function SplayTree() { 1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Pointer to the root node of the tree. 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @type {SplayTree.Node} 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @private 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.prototype.root_ = null; 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @return {boolean} Whether the tree is empty. 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.prototype.isEmpty = function() { 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return !this.root_; 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Inserts a node into the tree with the specified key and value if 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the tree does not already contain a node with the specified key. If 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the value is inserted, it becomes the root of the tree. 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @param {number} key Key to insert into the tree. 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @param {*} value Value to insert into the tree. 1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 1545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.prototype.insert = function(key, value) { 1555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.isEmpty()) { 1565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_ = new SplayTree.Node(key, value); 1575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 1585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Splay on the key to move the last node on the search path for 1605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // the key to the root of the tree. 1615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.splay_(key); 1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.root_.key == key) { 1635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 1645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var node = new SplayTree.Node(key, value); 1665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (key > this.root_.key) { 1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) node.left = this.root_; 1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) node.right = this.root_.right; 1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_.right = null; 1705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) node.right = this.root_; 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) node.left = this.root_.left; 1735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_.left = null; 1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_ = node; 1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Removes a node with the specified key from the tree if the tree 1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * contains a node with this key. The removed node is returned. If the 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * key is not found, an exception is thrown. 1835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @param {number} key Key to find and remove from the tree. 1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @return {SplayTree.Node} The removed node. 1865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 1875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.prototype.remove = function(key) { 1885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.isEmpty()) { 1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) throw Error('Key not found: ' + key); 1905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.splay_(key); 1925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.root_.key != key) { 1935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) throw Error('Key not found: ' + key); 1945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var removed = this.root_; 1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!this.root_.left) { 1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_ = this.root_.right; 1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 1995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var right = this.root_.right; 2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_ = this.root_.left; 2015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Splay to make sure that the new root has an empty right child. 2025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.splay_(key); 2035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Insert the original right child as the right child of the new 2045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // root. 2055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_.right = right; 2065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return removed; 2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Returns the node having the specified key or null if the tree doesn't contain 2135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * a node with the specified key. 2145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 2155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @param {number} key Key to find in the tree. 2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @return {SplayTree.Node} Node having the specified key. 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.prototype.find = function(key) { 2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.isEmpty()) { 2205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return null; 2215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.splay_(key); 2235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this.root_.key == key ? this.root_ : null; 2245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 2285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @return {SplayTree.Node} Node having the maximum key value that 2295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * is less or equal to the specified key value. 2305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 2315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.prototype.findGreatestLessThan = function(key) { 2325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.isEmpty()) { 2335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return null; 2345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Splay on the key to move the node with the given key or the last 2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // node on the search path to the top of the tree. 2375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.splay_(key); 2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Now the result is either the root node or the greatest node in 2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // the left subtree. 2405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.root_.key <= key) { 2415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this.root_; 2425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else if (this.root_.left) { 2435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this.findMax(this.root_.left); 2445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 2455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return null; 2465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 2515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @return {Array<*>} An array containing all the keys of tree's nodes. 2525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 2535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.prototype.exportKeys = function() { 2545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var result = []; 2555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!this.isEmpty()) { 2565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_.traverse_(function(node) { result.push(node.key); }); 2575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 2595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 2635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Perform the splay operation for the given key. Moves the node with 2645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the given key to the top of the tree. If no node has the given 2655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * key, the last node on the search path is moved to the top of the 2665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * tree. This is the simplified top-down splaying algorithm from: 2675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * "Self-adjusting Binary Search Trees" by Sleator and Tarjan 2685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 2695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @param {number} key Key to splay the tree on. 2705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @private 2715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 2725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.prototype.splay_ = function(key) { 2735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.isEmpty()) { 2745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 2755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Create a dummy node. The use of the dummy node is a bit 2775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // counter-intuitive: The right child of the dummy node will hold 2785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // the L tree of the algorithm. The left child of the dummy node 2795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // will hold the R tree of the algorithm. Using a dummy node, left 2805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // and right will always be nodes and we avoid special cases. 2815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var dummy, left, right; 2825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dummy = left = right = new SplayTree.Node(null, null); 2835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var current = this.root_; 2845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (true) { 2855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (key < current.key) { 2865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!current.left) { 2875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 2885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (key < current.left.key) { 2905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Rotate right. 2915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var tmp = current.left; 2925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current.left = tmp.right; 2935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tmp.right = current; 2945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current = tmp; 2955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!current.left) { 2965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 2975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Link right. 3005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) right.left = current; 3015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) right = current; 3025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current = current.left; 3035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else if (key > current.key) { 3045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!current.right) { 3055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 3065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (key > current.right.key) { 3085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Rotate left. 3095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var tmp = current.right; 3105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current.right = tmp.left; 3115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tmp.left = current; 3125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current = tmp; 3135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!current.right) { 3145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 3155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Link left. 3185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) left.right = current; 3195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) left = current; 3205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current = current.right; 3215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 3225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 3235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Assemble. 3265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) left.right = current.left; 3275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) right.left = current.right; 3285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current.left = dummy.right; 3295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current.right = dummy.left; 3305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_ = current; 3315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 3325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 3355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Constructs a Splay tree node. 3365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 3375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @param {number} key Key. 3385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @param {*} value Value. 3395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 3405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.Node = function(key, value) { 3415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.key = key; 3425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.value = value; 3435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 3445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 3475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @type {SplayTree.Node} 3485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 3495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.Node.prototype.left = null; 3505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 3535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @type {SplayTree.Node} 3545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 3555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.Node.prototype.right = null; 3565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 3595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Performs an ordered traversal of the subtree starting at 3605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * this SplayTree.Node. 3615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 3625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @param {function(SplayTree.Node)} f Visitor function. 3635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @private 3645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 3655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.Node.prototype.traverse_ = function(f) { 3665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var current = this; 3675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (current) { 3685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var left = current.left; 3695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (left) left.traverse_(f); 3705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) f(current); 3715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current = current.right; 3725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 3745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplaySetup(); 3765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayRun(); 3775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTearDown(); 378