1a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Copyright 2009 the V8 project authors. All rights reserved. 2a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Redistribution and use in source and binary forms, with or without 3a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// modification, are permitted provided that the following conditions are 4a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// met: 5a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// 6a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// * Redistributions of source code must retain the above copyright 7a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// notice, this list of conditions and the following disclaimer. 8a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// * Redistributions in binary form must reproduce the above 9a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// copyright notice, this list of conditions and the following 10a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// disclaimer in the documentation and/or other materials provided 11a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// with the distribution. 12a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// * Neither the name of Google Inc. nor the names of its 13a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// contributors may be used to endorse or promote products derived 14a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// from this software without specific prior written permission. 15a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// 16a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 28a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Load the Splay tree implementation from <project root>/tools. 29a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Files: tools/splaytree.js 30a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 31a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 32a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block(function testIsEmpty() { 331e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block var tree = new SplayTree(); 34a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertTrue(tree.isEmpty()); 35a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(0, 'value'); 36a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertFalse(tree.isEmpty()); 37a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block})(); 38a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 39a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 40a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block(function testExportValues() { 411e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block var tree = new SplayTree(); 42a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertArrayEquals([], tree.exportValues()); 43a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(0, 'value'); 44a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertArrayEquals(['value'], tree.exportValues()); 45a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(0, 'value'); 46a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertArrayEquals(['value'], tree.exportValues()); 47a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block})(); 48a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 49a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 50a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction createSampleTree() { 51a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Creates the following tree: 52a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // 50 53a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // / \ 54a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // 30 60 55a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // / \ \ 56a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // 10 40 90 57a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // \ / \ 58a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // 20 70 100 59a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // / \ 60a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // 15 80 61a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // 62a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // We can't use the 'insert' method because it also uses 'splay_'. 63a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return { key: 50, value: 50, 64a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block left: { key: 30, value: 30, 65a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block left: { key: 10, value: 10, left: null, 66a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block right: { key: 20, value: 20, 67a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block left: { key: 15, value: 15, 68a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block left: null, right: null }, 69a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block right: null } }, 70a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block right: { key: 40, value: 40, left: null, right: null } }, 71a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block right: { key: 60, value: 60, left: null, 72a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block right: { key: 90, value: 90, 73a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block left: { key: 70, value: 70, left: null, 74a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block right: { key: 80, value: 80, 75a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block left: null, right: null } }, 76a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block right: { key: 100, value: 100, 77a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block left: null, right: null } } } }; 78a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 79a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 80a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 81a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block(function testSplay() { 821e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block var tree = new SplayTree(); 83a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.root_ = createSampleTree(); 84257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch assertArrayEquals([50, 30, 60, 10, 40, 90, 20, 70, 100, 15, 80], 85a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.exportValues()); 86a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.splay_(50); 87257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch assertArrayEquals([50, 30, 60, 10, 40, 90, 20, 70, 100, 15, 80], 88a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.exportValues()); 89a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.splay_(80); 90257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch assertArrayEquals([80, 60, 90, 50, 70, 100, 30, 10, 40, 20, 15], 91a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.exportValues()); 92a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block})(); 93a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 94a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 95a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block(function testInsert() { 961e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block var tree = new SplayTree(); 97a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(5, 'root'); 98a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(3, 'left'); 99a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertArrayEquals(['left', 'root'], tree.exportValues()); 100a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(7, 'right'); 101a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertArrayEquals(['right', 'root', 'left'], tree.exportValues()); 102a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block})(); 103a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 104a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 105a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block(function testFind() { 1061e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block var tree = new SplayTree(); 107a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(5, 'root'); 108a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(3, 'left'); 109a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(7, 'right'); 110a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals('root', tree.find(5).value); 111a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals('left', tree.find(3).value); 112a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals('right', tree.find(7).value); 113a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals(null, tree.find(0)); 114a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals(null, tree.find(100)); 115a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals(null, tree.find(-100)); 116a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block})(); 117a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 118a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 119a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block(function testFindMin() { 1201e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block var tree = new SplayTree(); 121a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals(null, tree.findMin()); 122a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(5, 'root'); 123a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(3, 'left'); 124a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(7, 'right'); 125a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals('left', tree.findMin().value); 126a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block})(); 127a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 128a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 129a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block(function testFindMax() { 1301e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block var tree = new SplayTree(); 131a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals(null, tree.findMax()); 132a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(5, 'root'); 133a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(3, 'left'); 134a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(7, 'right'); 135a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals('right', tree.findMax().value); 136a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block})(); 137a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 138a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 139a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block(function testFindGreatestLessThan() { 1401e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block var tree = new SplayTree(); 141a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals(null, tree.findGreatestLessThan(10)); 142a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(5, 'root'); 143a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(3, 'left'); 144a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(7, 'right'); 145a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals('right', tree.findGreatestLessThan(10).value); 146a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals('right', tree.findGreatestLessThan(7).value); 147a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals('root', tree.findGreatestLessThan(6).value); 148a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals('left', tree.findGreatestLessThan(4).value); 149a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals(null, tree.findGreatestLessThan(2)); 150a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block})(); 151a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 152a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 153a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block(function testRemove() { 1541e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block var tree = new SplayTree(); 155a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertThrows('tree.remove(5)'); 156a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(5, 'root'); 157a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(3, 'left'); 158a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block tree.insert(7, 'right'); 159a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertThrows('tree.remove(1)'); 160a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertThrows('tree.remove(6)'); 161a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertThrows('tree.remove(10)'); 162a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals('root', tree.remove(5).value); 163a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals('left', tree.remove(3).value); 164a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertEquals('right', tree.remove(7).value); 165a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block assertArrayEquals([], tree.exportValues()); 166a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block})(); 167