12d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// Copyright 2009 the V8 project authors. All rights reserved. 22d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// Redistribution and use in source and binary forms, with or without 32d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// modification, are permitted provided that the following conditions are 42d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// met: 52d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// 62d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// * Redistributions of source code must retain the above copyright 72d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// notice, this list of conditions and the following disclaimer. 82d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// * Redistributions in binary form must reproduce the above 92d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// copyright notice, this list of conditions and the following 102d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// disclaimer in the documentation and/or other materials provided 112d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// with the distribution. 122d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// * Neither the name of Google Inc. nor the names of its 132d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// contributors may be used to endorse or promote products derived 142d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// from this software without specific prior written permission. 152d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// 162d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 172d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 202d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 212d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 222d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 232d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 242d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 252d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 262d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 282d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 292d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org/** 302d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * Constructs a Splay tree. A splay tree is a self-balancing binary 312d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * search tree with the additional property that recently accessed 322d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * elements are quick to access again. It performs basic operations 332d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * such as insertion, look-up and removal in O(log(n)) amortized time. 342d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * 352d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * @constructor 362d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org */ 37496c03a64f12710e837204e261ef155601247895sgjesse@chromium.orgfunction SplayTree() { 382d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org}; 392d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 402d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 412d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org/** 422d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * Pointer to the root node of the tree. 432d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * 44496c03a64f12710e837204e261ef155601247895sgjesse@chromium.org * @type {SplayTree.Node} 452d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * @private 462d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org */ 47496c03a64f12710e837204e261ef155601247895sgjesse@chromium.orgSplayTree.prototype.root_ = null; 482d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 492d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 502d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org/** 512d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * @return {boolean} Whether the tree is empty. 522d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org */ 53496c03a64f12710e837204e261ef155601247895sgjesse@chromium.orgSplayTree.prototype.isEmpty = function() { 542d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org return !this.root_; 552d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org}; 562d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 572d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 582d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 592d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org/** 602d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * Inserts a node into the tree with the specified key and value if 612d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * the tree does not already contain a node with the specified key. If 622d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * the value is inserted, it becomes the root of the tree. 632d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * 642d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * @param {number} key Key to insert into the tree. 652d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * @param {*} value Value to insert into the tree. 662d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org */ 67496c03a64f12710e837204e261ef155601247895sgjesse@chromium.orgSplayTree.prototype.insert = function(key, value) { 682d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (this.isEmpty()) { 69496c03a64f12710e837204e261ef155601247895sgjesse@chromium.org this.root_ = new SplayTree.Node(key, value); 702d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org return; 712d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 722d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // Splay on the key to move the last node on the search path for 732d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // the key to the root of the tree. 742d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org this.splay_(key); 752d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (this.root_.key == key) { 762d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org return; 772d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 78496c03a64f12710e837204e261ef155601247895sgjesse@chromium.org var node = new SplayTree.Node(key, value); 792d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (key > this.root_.key) { 802d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org node.left = this.root_; 812d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org node.right = this.root_.right; 822d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org this.root_.right = null; 832d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } else { 842d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org node.right = this.root_; 852d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org node.left = this.root_.left; 862d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org this.root_.left = null; 872d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 882d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org this.root_ = node; 892d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org}; 902d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 912d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 922d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org/** 932d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * Removes a node with the specified key from the tree if the tree 942d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * contains a node with this key. The removed node is returned. If the 952d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * key is not found, an exception is thrown. 962d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * 972d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * @param {number} key Key to find and remove from the tree. 98496c03a64f12710e837204e261ef155601247895sgjesse@chromium.org * @return {SplayTree.Node} The removed node. 992d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org */ 100496c03a64f12710e837204e261ef155601247895sgjesse@chromium.orgSplayTree.prototype.remove = function(key) { 1012d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (this.isEmpty()) { 1022d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org throw Error('Key not found: ' + key); 1032d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 1042d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org this.splay_(key); 1052d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (this.root_.key != key) { 1062d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org throw Error('Key not found: ' + key); 1072d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 1082d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org var removed = this.root_; 1092d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (!this.root_.left) { 1102d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org this.root_ = this.root_.right; 1112d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } else { 1122d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org var right = this.root_.right; 1132d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org this.root_ = this.root_.left; 1142d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // Splay to make sure that the new root has an empty right child. 1152d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org this.splay_(key); 1162d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // Insert the original right child as the right child of the new 1172d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // root. 1182d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org this.root_.right = right; 1192d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 1202d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org return removed; 1212d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org}; 1222d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 1232d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 1242d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org/** 1252d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * Returns the node having the specified key or null if the tree doesn't contain 1262d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * a node with the specified key. 1272d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * 1282d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * @param {number} key Key to find in the tree. 129496c03a64f12710e837204e261ef155601247895sgjesse@chromium.org * @return {SplayTree.Node} Node having the specified key. 1302d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org */ 131496c03a64f12710e837204e261ef155601247895sgjesse@chromium.orgSplayTree.prototype.find = function(key) { 1322d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (this.isEmpty()) { 1332d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org return null; 1342d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 1352d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org this.splay_(key); 1362d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org return this.root_.key == key ? this.root_ : null; 1372d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org}; 1382d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 1392d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 1402d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org/** 141496c03a64f12710e837204e261ef155601247895sgjesse@chromium.org * @return {SplayTree.Node} Node having the minimum key value. 1422d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org */ 143496c03a64f12710e837204e261ef155601247895sgjesse@chromium.orgSplayTree.prototype.findMin = function() { 1442d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (this.isEmpty()) { 1452d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org return null; 1462d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 1472d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org var current = this.root_; 1482d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org while (current.left) { 1492d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org current = current.left; 1502d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 1512d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org return current; 1522d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org}; 1532d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 1542d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 1552d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org/** 156496c03a64f12710e837204e261ef155601247895sgjesse@chromium.org * @return {SplayTree.Node} Node having the maximum key value. 1572d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org */ 158496c03a64f12710e837204e261ef155601247895sgjesse@chromium.orgSplayTree.prototype.findMax = function(opt_startNode) { 1592d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (this.isEmpty()) { 1602d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org return null; 1612d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 1622d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org var current = opt_startNode || this.root_; 1632d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org while (current.right) { 1642d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org current = current.right; 1652d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 1662d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org return current; 1672d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org}; 1682d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 1692d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 1702d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org/** 171496c03a64f12710e837204e261ef155601247895sgjesse@chromium.org * @return {SplayTree.Node} Node having the maximum key value that 1722d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * is less or equal to the specified key value. 1732d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org */ 174496c03a64f12710e837204e261ef155601247895sgjesse@chromium.orgSplayTree.prototype.findGreatestLessThan = function(key) { 1752d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (this.isEmpty()) { 1762d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org return null; 1772d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 1782d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // Splay on the key to move the node with the given key or the last 1792d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // node on the search path to the top of the tree. 1802d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org this.splay_(key); 1812d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // Now the result is either the root node or the greatest node in 1822d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // the left subtree. 1832d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (this.root_.key <= key) { 1842d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org return this.root_; 1852d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } else if (this.root_.left) { 1862d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org return this.findMax(this.root_.left); 1872d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } else { 1882d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org return null; 1892d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 1902d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org}; 1912d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 1922d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 1932d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org/** 194030d38ee536bc25856546e75fdac60d1a0c42bddwhesse@chromium.org * @return {Array<*>} An array containing all the values of tree's nodes paired 195030d38ee536bc25856546e75fdac60d1a0c42bddwhesse@chromium.org * with keys. 196030d38ee536bc25856546e75fdac60d1a0c42bddwhesse@chromium.org */ 197030d38ee536bc25856546e75fdac60d1a0c42bddwhesse@chromium.orgSplayTree.prototype.exportKeysAndValues = function() { 198030d38ee536bc25856546e75fdac60d1a0c42bddwhesse@chromium.org var result = []; 199030d38ee536bc25856546e75fdac60d1a0c42bddwhesse@chromium.org this.traverse_(function(node) { result.push([node.key, node.value]); }); 200030d38ee536bc25856546e75fdac60d1a0c42bddwhesse@chromium.org return result; 201030d38ee536bc25856546e75fdac60d1a0c42bddwhesse@chromium.org}; 202030d38ee536bc25856546e75fdac60d1a0c42bddwhesse@chromium.org 203030d38ee536bc25856546e75fdac60d1a0c42bddwhesse@chromium.org 204030d38ee536bc25856546e75fdac60d1a0c42bddwhesse@chromium.org/** 2052d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * @return {Array<*>} An array containing all the values of tree's nodes. 2062d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org */ 207496c03a64f12710e837204e261ef155601247895sgjesse@chromium.orgSplayTree.prototype.exportValues = function() { 2082d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org var result = []; 2092d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org this.traverse_(function(node) { result.push(node.value); }); 2102d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org return result; 2112d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org}; 2122d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 2132d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 2142d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org/** 2152d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * Perform the splay operation for the given key. Moves the node with 2162d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * the given key to the top of the tree. If no node has the given 2172d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * key, the last node on the search path is moved to the top of the 2182d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * tree. This is the simplified top-down splaying algorithm from: 2192d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * "Self-adjusting Binary Search Trees" by Sleator and Tarjan 2202d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * 2212d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * @param {number} key Key to splay the tree on. 2222d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * @private 2232d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org */ 224496c03a64f12710e837204e261ef155601247895sgjesse@chromium.orgSplayTree.prototype.splay_ = function(key) { 2252d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (this.isEmpty()) { 2262d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org return; 2272d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 2282d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // Create a dummy node. The use of the dummy node is a bit 2292d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // counter-intuitive: The right child of the dummy node will hold 2302d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // the L tree of the algorithm. The left child of the dummy node 2312d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // will hold the R tree of the algorithm. Using a dummy node, left 2322d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // and right will always be nodes and we avoid special cases. 2332d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org var dummy, left, right; 234496c03a64f12710e837204e261ef155601247895sgjesse@chromium.org dummy = left = right = new SplayTree.Node(null, null); 2352d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org var current = this.root_; 2362d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org while (true) { 2372d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (key < current.key) { 2382d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (!current.left) { 2392d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org break; 2402d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 2412d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (key < current.left.key) { 2422d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // Rotate right. 2432d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org var tmp = current.left; 2442d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org current.left = tmp.right; 2452d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org tmp.right = current; 2462d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org current = tmp; 2472d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (!current.left) { 2482d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org break; 2492d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 2502d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 2512d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // Link right. 2522d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org right.left = current; 2532d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org right = current; 2542d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org current = current.left; 2552d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } else if (key > current.key) { 2562d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (!current.right) { 2572d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org break; 2582d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 2592d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (key > current.right.key) { 2602d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // Rotate left. 2612d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org var tmp = current.right; 2622d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org current.right = tmp.left; 2632d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org tmp.left = current; 2642d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org current = tmp; 2652d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (!current.right) { 2662d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org break; 2672d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 2682d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 2692d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // Link left. 2702d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org left.right = current; 2712d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org left = current; 2722d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org current = current.right; 2732d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } else { 2742d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org break; 2752d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 2762d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 2772d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org // Assemble. 2782d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org left.right = current.left; 2792d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org right.left = current.right; 2802d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org current.left = dummy.right; 2812d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org current.right = dummy.left; 2822d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org this.root_ = current; 2832d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org}; 2842d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 2852d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 2862d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org/** 2872d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * Performs a preorder traversal of the tree. 2882d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * 289496c03a64f12710e837204e261ef155601247895sgjesse@chromium.org * @param {function(SplayTree.Node)} f Visitor function. 2902d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * @private 2912d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org */ 292496c03a64f12710e837204e261ef155601247895sgjesse@chromium.orgSplayTree.prototype.traverse_ = function(f) { 2932d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org var nodesToVisit = [this.root_]; 2942d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org while (nodesToVisit.length > 0) { 2952d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org var node = nodesToVisit.shift(); 2962d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org if (node == null) { 2972d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org continue; 2982d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 2992d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org f(node); 3002d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org nodesToVisit.push(node.left); 3012d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org nodesToVisit.push(node.right); 3022d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org } 3032d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org}; 3042d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 3052d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 3062d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org/** 3072d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * Constructs a Splay tree node. 3082d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * 3092d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * @param {number} key Key. 3102d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org * @param {*} value Value. 3112d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org */ 312496c03a64f12710e837204e261ef155601247895sgjesse@chromium.orgSplayTree.Node = function(key, value) { 3132d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org this.key = key; 3142d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org this.value = value; 3152d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org}; 3162d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 3172d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 3182d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org/** 319496c03a64f12710e837204e261ef155601247895sgjesse@chromium.org * @type {SplayTree.Node} 3202d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org */ 321496c03a64f12710e837204e261ef155601247895sgjesse@chromium.orgSplayTree.Node.prototype.left = null; 3222d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 3232d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org 3242d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org/** 325496c03a64f12710e837204e261ef155601247895sgjesse@chromium.org * @type {SplayTree.Node} 3262d18d10b30bbe822dcb5e2d6e90fd7863496243ckasperl@chromium.org */ 327496c03a64f12710e837204e261ef155601247895sgjesse@chromium.orgSplayTree.Node.prototype.right = null; 328