188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown// Copyright (c) 2012 The Chromium Authors. All rights reserved. 288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown// Use of this source code is governed by a BSD-style license that can be 388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown// found in the LICENSE file. 488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown/** 788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @fileoverview Splay tree used by CodeMap. 888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown */ 988448d9ae4dfff1805045790ef5f32495d62abccJeff Brownbase.exportTo('tracing.importer.v8', function() { 1088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown /** 1188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * Constructs a Splay tree. A splay tree is a self-balancing binary 1288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * search tree with the additional property that recently accessed 1388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * elements are quick to access again. It performs basic operations 1488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * such as insertion, look-up and removal in O(log(n)) amortized time. 1588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * 1688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @constructor 1788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown */ 1888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown function SplayTree() { 1988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown }; 2088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 2188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 2288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown /** 2388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * Pointer to the root node of the tree. 2488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * 2588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @type {SplayTree.Node} 2688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @private 2788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown */ 2888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown SplayTree.prototype.root_ = null; 2988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 3088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 3188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown /** 3288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @return {boolean} Whether the tree is empty. 3388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown */ 3488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown SplayTree.prototype.isEmpty = function() { 3588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return !this.root_; 3688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown }; 3788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 3888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 3988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 4088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown /** 4188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * Inserts a node into the tree with the specified key and value if 4288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * the tree does not already contain a node with the specified key. If 4388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * the value is inserted, it becomes the root of the tree. 4488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * 4588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @param {number} key Key to insert into the tree. 4688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @param {*} value Value to insert into the tree. 4788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown */ 4888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown SplayTree.prototype.insert = function(key, value) { 4988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (this.isEmpty()) { 5088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown this.root_ = new SplayTree.Node(key, value); 5188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return; 5288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 5388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // Splay on the key to move the last node on the search path for 5488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // the key to the root of the tree. 5588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown this.splay_(key); 5688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (this.root_.key == key) { 5788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return; 5888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 5988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown var node = new SplayTree.Node(key, value); 6088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (key > this.root_.key) { 6188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown node.left = this.root_; 6288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown node.right = this.root_.right; 6388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown this.root_.right = null; 6488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } else { 6588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown node.right = this.root_; 6688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown node.left = this.root_.left; 6788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown this.root_.left = null; 6888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 6988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown this.root_ = node; 7088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown }; 7188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 7288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 7388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown /** 7488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * Removes a node with the specified key from the tree if the tree 7588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * contains a node with this key. The removed node is returned. If the 7688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * key is not found, an exception is thrown. 7788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * 7888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @param {number} key Key to find and remove from the tree. 7988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @return {SplayTree.Node} The removed node. 8088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown */ 8188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown SplayTree.prototype.remove = function(key) { 8288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (this.isEmpty()) { 8388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown throw Error('Key not found: ' + key); 8488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 8588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown this.splay_(key); 8688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (this.root_.key != key) { 8788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown throw Error('Key not found: ' + key); 8888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 8988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown var removed = this.root_; 9088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (!this.root_.left) { 9188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown this.root_ = this.root_.right; 9288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } else { 9388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown var right = this.root_.right; 9488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown this.root_ = this.root_.left; 9588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // Splay to make sure that the new root has an empty right child. 9688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown this.splay_(key); 9788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // Insert the original right child as the right child of the new 9888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // root. 9988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown this.root_.right = right; 10088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 10188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return removed; 10288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown }; 10388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 10488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 10588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown /** 10688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * Returns the node having the specified key or null if the tree doesn't 10788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * contain a node with the specified key. 10888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * 10988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * 11088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @param {number} key Key to find in the tree. 11188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @return {SplayTree.Node} Node having the specified key. 11288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown */ 11388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown SplayTree.prototype.find = function(key) { 11488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (this.isEmpty()) { 11588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return null; 11688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 11788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown this.splay_(key); 11888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return this.root_.key == key ? this.root_ : null; 11988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown }; 12088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 12188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 12288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown /** 12388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @return {SplayTree.Node} Node having the minimum key value. 12488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown */ 12588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown SplayTree.prototype.findMin = function() { 12688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (this.isEmpty()) { 12788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return null; 12888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 12988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown var current = this.root_; 13088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown while (current.left) { 13188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown current = current.left; 13288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 13388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return current; 13488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown }; 13588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 13688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 13788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown /** 13888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @return {SplayTree.Node} Node having the maximum key value. 13988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown */ 14088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown SplayTree.prototype.findMax = function(opt_startNode) { 14188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (this.isEmpty()) { 14288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return null; 14388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 14488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown var current = opt_startNode || this.root_; 14588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown while (current.right) { 14688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown current = current.right; 14788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 14888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return current; 14988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown }; 15088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 15188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 15288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown /** 15388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @return {SplayTree.Node} Node having the maximum key value that 15488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * is less or equal to the specified key value. 15588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown */ 15688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown SplayTree.prototype.findGreatestLessThan = function(key) { 15788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (this.isEmpty()) { 15888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return null; 15988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 16088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // Splay on the key to move the node with the given key or the last 16188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // node on the search path to the top of the tree. 16288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown this.splay_(key); 16388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // Now the result is either the root node or the greatest node in 16488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // the left subtree. 16588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (this.root_.key <= key) { 16688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return this.root_; 16788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } else if (this.root_.left) { 16888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return this.findMax(this.root_.left); 16988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } else { 17088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return null; 17188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 17288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown }; 17388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 17488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 17588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown /** 17688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @return {Array<*>} An array containing all the values of tree's nodes 17788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * paired with keys. 17888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * 17988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown */ 18088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown SplayTree.prototype.exportKeysAndValues = function() { 18188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown var result = []; 18288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown this.traverse_(function(node) { result.push([node.key, node.value]); }); 18388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return result; 18488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown }; 18588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 18688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 18788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown /** 18888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @return {Array<*>} An array containing all the values of tree's nodes. 18988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown */ 19088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown SplayTree.prototype.exportValues = function() { 19188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown var result = []; 19288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown this.traverse_(function(node) { result.push(node.value); }); 19388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return result; 19488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown }; 19588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 19688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 19788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown /** 19888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * Perform the splay operation for the given key. Moves the node with 19988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * the given key to the top of the tree. If no node has the given 20088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * key, the last node on the search path is moved to the top of the 20188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * tree. This is the simplified top-down splaying algorithm from: 20288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * "Self-adjusting Binary Search Trees" by Sleator and Tarjan 20388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * 20488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @param {number} key Key to splay the tree on. 20588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @private 20688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown */ 20788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown SplayTree.prototype.splay_ = function(key) { 20888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (this.isEmpty()) { 20988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return; 21088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 21188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // Create a dummy node. The use of the dummy node is a bit 21288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // counter-intuitive: The right child of the dummy node will hold 21388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // the L tree of the algorithm. The left child of the dummy node 21488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // will hold the R tree of the algorithm. Using a dummy node, left 21588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // and right will always be nodes and we avoid special cases. 21688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown var dummy, left, right; 21788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown dummy = left = right = new SplayTree.Node(null, null); 21888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown var current = this.root_; 21988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown while (true) { 22088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (key < current.key) { 22188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (!current.left) { 22288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown break; 22388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 22488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (key < current.left.key) { 22588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // Rotate right. 22688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown var tmp = current.left; 22788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown current.left = tmp.right; 22888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown tmp.right = current; 22988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown current = tmp; 23088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (!current.left) { 23188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown break; 23288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 23388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 23488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // Link right. 23588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown right.left = current; 23688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown right = current; 23788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown current = current.left; 23888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } else if (key > current.key) { 23988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (!current.right) { 24088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown break; 24188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 24288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (key > current.right.key) { 24388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // Rotate left. 24488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown var tmp = current.right; 24588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown current.right = tmp.left; 24688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown tmp.left = current; 24788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown current = tmp; 24888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (!current.right) { 24988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown break; 25088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 25188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 25288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // Link left. 25388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown left.right = current; 25488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown left = current; 25588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown current = current.right; 25688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } else { 25788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown break; 25888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 25988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 26088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown // Assemble. 26188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown left.right = current.left; 26288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown right.left = current.right; 26388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown current.left = dummy.right; 26488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown current.right = dummy.left; 26588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown this.root_ = current; 26688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown }; 26788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 26888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 26988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown /** 27088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * Performs a preorder traversal of the tree. 27188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * 27288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @param {function(SplayTree.Node)} f Visitor function. 27388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @private 27488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown */ 27588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown SplayTree.prototype.traverse_ = function(f) { 27688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown var nodesToVisit = [this.root_]; 27788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown while (nodesToVisit.length > 0) { 27888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown var node = nodesToVisit.shift(); 27988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown if (node == null) { 28088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown continue; 28188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 28288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown f(node); 28388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown nodesToVisit.push(node.left); 28488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown nodesToVisit.push(node.right); 28588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown } 28688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown }; 28788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 28888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 28988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown /** 29088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * Constructs a Splay tree node. 29188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * 29288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @param {number} key Key. 29388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @param {*} value Value. 29488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown */ 29588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown SplayTree.Node = function(key, value) { 29688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown this.key = key; 29788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown this.value = value; 29888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown }; 29988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 30088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 30188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown /** 30288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @type {SplayTree.Node} 30388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown */ 30488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown SplayTree.Node.prototype.left = null; 30588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 30688448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 30788448d9ae4dfff1805045790ef5f32495d62abccJeff Brown /** 30888448d9ae4dfff1805045790ef5f32495d62abccJeff Brown * @type {SplayTree.Node} 30988448d9ae4dfff1805045790ef5f32495d62abccJeff Brown */ 31088448d9ae4dfff1805045790ef5f32495d62abccJeff Brown SplayTree.Node.prototype.right = null; 31188448d9ae4dfff1805045790ef5f32495d62abccJeff Brown 31288448d9ae4dfff1805045790ef5f32495d62abccJeff Brown return { 31388448d9ae4dfff1805045790ef5f32495d62abccJeff Brown SplayTree: SplayTree 31488448d9ae4dfff1805045790ef5f32495d62abccJeff Brown }; 31588448d9ae4dfff1805045790ef5f32495d62abccJeff Brown}); 316