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