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