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, tag) { 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 ' + tag + ' in leaf node' 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return { 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) left: GeneratePayloadTree(depth - 1, tag), 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) right: GeneratePayloadTree(depth - 1, tag) 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) var payload = GeneratePayloadTree(kSplayTreePayloadDepth, String(key)); 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) splayTree.insert(key, payload); 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return key; 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function SplaySetup() { 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) splayTree = new SplayTree(); 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < kSplayTreeSize; i++) InsertNewNode(); 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function SplayTearDown() { 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Allow the garbage collector to reclaim the memory 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // used by the splay tree no matter how we exit the 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // tear down function. 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var keys = splayTree.exportKeys(); 905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) splayTree = null; 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Verify that the splay tree has the right size. 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var length = keys.length; 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (length != kSplayTreeSize) { 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) throw new Error("Splay tree has wrong size"); 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Verify that the splay tree has sorted, unique keys. 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < length - 1; i++) { 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (keys[i] >= keys[i + 1]) { 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) throw new Error("Splay tree not sorted"); 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function SplayRun() { 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Replace a few nodes in the splay tree. 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < kSplayTreeModifications; i++) { 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var key = InsertNewNode(); 1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var greatest = splayTree.findGreatestLessThan(key); 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (greatest == null) splayTree.remove(key); 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else splayTree.remove(greatest.key); 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 1195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Constructs a Splay tree. A splay tree is a self-balancing binary 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * search tree with the additional property that recently accessed 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * elements are quick to access again. It performs basic operations 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * such as insertion, look-up and removal in O(log(n)) amortized time. 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @constructor 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function SplayTree() { 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Pointer to the root node of the tree. 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @type {SplayTree.Node} 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @private 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.prototype.root_ = null; 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @return {boolean} Whether the tree is empty. 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.prototype.isEmpty = function() { 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return !this.root_; 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Inserts a node into the tree with the specified key and value if 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the tree does not already contain a node with the specified key. If 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the value is inserted, it becomes the root of the tree. 1515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @param {number} key Key to insert into the tree. 1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @param {*} value Value to insert into the tree. 1545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 1555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.prototype.insert = function(key, value) { 1565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.isEmpty()) { 1575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_ = new SplayTree.Node(key, value); 1585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Splay on the key to move the last node on the search path for 1615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // the key to the root of the tree. 1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.splay_(key); 1635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.root_.key == key) { 1645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var node = new SplayTree.Node(key, value); 1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (key > this.root_.key) { 1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) node.left = this.root_; 1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) node.right = this.root_.right; 1705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_.right = null; 1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) node.right = this.root_; 1735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) node.left = this.root_.left; 1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_.left = null; 1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_ = node; 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Removes a node with the specified key from the tree if the tree 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * contains a node with this key. The removed node is returned. If the 1835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * key is not found, an exception is thrown. 1845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @param {number} key Key to find and remove from the tree. 1865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @return {SplayTree.Node} The removed node. 1875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 1885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.prototype.remove = function(key) { 1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.isEmpty()) { 1905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) throw Error('Key not found: ' + key); 1915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.splay_(key); 1935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.root_.key != key) { 1945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) throw Error('Key not found: ' + key); 1955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var removed = this.root_; 1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!this.root_.left) { 1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_ = this.root_.right; 1995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var right = this.root_.right; 2015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_ = this.root_.left; 2025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Splay to make sure that the new root has an empty right child. 2035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.splay_(key); 2045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Insert the original right child as the right child of the new 2055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // root. 2065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_.right = right; 2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return removed; 2095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 2135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Returns the node having the specified key or null if the tree doesn't contain 2145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * a node with the specified key. 2155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @param {number} key Key to find in the tree. 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @return {SplayTree.Node} Node having the specified key. 2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.prototype.find = function(key) { 2205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.isEmpty()) { 2215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return null; 2225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.splay_(key); 2245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this.root_.key == key ? this.root_ : null; 2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 2295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @return {SplayTree.Node} Node having the maximum key value. 2305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 2315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.prototype.findMax = function(opt_startNode) { 2325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.isEmpty()) { 2335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return null; 2345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var current = opt_startNode || this.root_; 2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (current.right) { 2375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current = current.right; 2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return current; 2405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 2445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @return {SplayTree.Node} Node having the maximum key value that 2455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * is less than the specified key value. 2465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 2475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.prototype.findGreatestLessThan = function(key) { 2485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.isEmpty()) { 2495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return null; 2505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Splay on the key to move the node with the given key or the last 2525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // node on the search path to the top of the tree. 2535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.splay_(key); 2545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Now the result is either the root node or the greatest node in 2555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // the left subtree. 2565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.root_.key < key) { 2575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this.root_; 2585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else if (this.root_.left) { 2595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this.findMax(this.root_.left); 2605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 2615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return null; 2625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 2675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @return {Array<*>} An array containing all the keys of tree's nodes. 2685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 2695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.prototype.exportKeys = function() { 2705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var result = []; 2715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!this.isEmpty()) { 2725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_.traverse_(function(node) { result.push(node.key); }); 2735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 2755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 2795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Perform the splay operation for the given key. Moves the node with 2805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the given key to the top of the tree. If no node has the given 2815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * key, the last node on the search path is moved to the top of the 2825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * tree. This is the simplified top-down splaying algorithm from: 2835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * "Self-adjusting Binary Search Trees" by Sleator and Tarjan 2845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 2855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @param {number} key Key to splay the tree on. 2865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @private 2875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 2885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.prototype.splay_ = function(key) { 2895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.isEmpty()) { 2905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 2915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Create a dummy node. The use of the dummy node is a bit 2935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // counter-intuitive: The right child of the dummy node will hold 2945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // the L tree of the algorithm. The left child of the dummy node 2955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // will hold the R tree of the algorithm. Using a dummy node, left 2965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // and right will always be nodes and we avoid special cases. 2975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var dummy, left, right; 2985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dummy = left = right = new SplayTree.Node(null, null); 2995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var current = this.root_; 3005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (true) { 3015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (key < current.key) { 3025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!current.left) { 3035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 3045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (key < current.left.key) { 3065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Rotate right. 3075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var tmp = current.left; 3085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current.left = tmp.right; 3095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tmp.right = current; 3105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current = tmp; 3115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!current.left) { 3125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 3135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Link right. 3165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) right.left = current; 3175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) right = current; 3185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current = current.left; 3195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else if (key > current.key) { 3205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!current.right) { 3215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 3225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (key > current.right.key) { 3245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Rotate left. 3255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var tmp = current.right; 3265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current.right = tmp.left; 3275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tmp.left = current; 3285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current = tmp; 3295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!current.right) { 3305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 3315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Link left. 3345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) left.right = current; 3355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) left = current; 3365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current = current.right; 3375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 3385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 3395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Assemble. 3425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) left.right = current.left; 3435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) right.left = current.right; 3445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current.left = dummy.right; 3455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current.right = dummy.left; 3465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.root_ = current; 3475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 3485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 3515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Constructs a Splay tree node. 3525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 3535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @param {number} key Key. 3545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @param {*} value Value. 3555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 3565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.Node = function(key, value) { 3575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.key = key; 3585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.value = value; 3595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 3605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 3635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @type {SplayTree.Node} 3645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 3655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.Node.prototype.left = null; 3665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 3695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @type {SplayTree.Node} 3705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 3715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.Node.prototype.right = null; 3725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 3755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Performs an ordered traversal of the subtree starting at 3765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * this SplayTree.Node. 3775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 3785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @param {function(SplayTree.Node)} f Visitor function. 3795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * @private 3805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 3815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTree.Node.prototype.traverse_ = function(f) { 3825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var current = this; 3835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (current) { 3845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var left = current.left; 3855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (left) left.traverse_(f); 3865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) f(current); 3875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current = current.right; 3885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 3905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplaySetup(); 3925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayRun(); 3935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)SplayTearDown(); 394