OLD | NEW |
1 // Copyright 2009 the V8 project authors. All rights reserved. | 1 // Copyright 2009 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 63 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
74 right: { key: 80, value: 80, | 74 right: { key: 80, value: 80, |
75 left: null, right: null } }, | 75 left: null, right: null } }, |
76 right: { key: 100, value: 100, | 76 right: { key: 100, value: 100, |
77 left: null, right: null } } } }; | 77 left: null, right: null } } } }; |
78 }; | 78 }; |
79 | 79 |
80 | 80 |
81 (function testSplay() { | 81 (function testSplay() { |
82 var tree = new SplayTree(); | 82 var tree = new SplayTree(); |
83 tree.root_ = createSampleTree(); | 83 tree.root_ = createSampleTree(); |
84 assertArrayEquals(['50', '30', '60', '10', '40', '90', '20', '70', '100', '15'
, '80'], | 84 assertArrayEquals([50, 30, 60, 10, 40, 90, 20, 70, 100, 15, 80], |
85 tree.exportValues()); | 85 tree.exportValues()); |
86 tree.splay_(50); | 86 tree.splay_(50); |
87 assertArrayEquals(['50', '30', '60', '10', '40', '90', '20', '70', '100', '15'
, '80'], | 87 assertArrayEquals([50, 30, 60, 10, 40, 90, 20, 70, 100, 15, 80], |
88 tree.exportValues()); | 88 tree.exportValues()); |
89 tree.splay_(80); | 89 tree.splay_(80); |
90 assertArrayEquals(['80', '60', '90', '50', '70', '100', '30', '10', '40', '20'
, '15'], | 90 assertArrayEquals([80, 60, 90, 50, 70, 100, 30, 10, 40, 20, 15], |
91 tree.exportValues()); | 91 tree.exportValues()); |
92 })(); | 92 })(); |
93 | 93 |
94 | 94 |
95 (function testInsert() { | 95 (function testInsert() { |
96 var tree = new SplayTree(); | 96 var tree = new SplayTree(); |
97 tree.insert(5, 'root'); | 97 tree.insert(5, 'root'); |
98 tree.insert(3, 'left'); | 98 tree.insert(3, 'left'); |
99 assertArrayEquals(['left', 'root'], tree.exportValues()); | 99 assertArrayEquals(['left', 'root'], tree.exportValues()); |
100 tree.insert(7, 'right'); | 100 tree.insert(7, 'right'); |
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
157 tree.insert(3, 'left'); | 157 tree.insert(3, 'left'); |
158 tree.insert(7, 'right'); | 158 tree.insert(7, 'right'); |
159 assertThrows('tree.remove(1)'); | 159 assertThrows('tree.remove(1)'); |
160 assertThrows('tree.remove(6)'); | 160 assertThrows('tree.remove(6)'); |
161 assertThrows('tree.remove(10)'); | 161 assertThrows('tree.remove(10)'); |
162 assertEquals('root', tree.remove(5).value); | 162 assertEquals('root', tree.remove(5).value); |
163 assertEquals('left', tree.remove(3).value); | 163 assertEquals('left', tree.remove(3).value); |
164 assertEquals('right', tree.remove(7).value); | 164 assertEquals('right', tree.remove(7).value); |
165 assertArrayEquals([], tree.exportValues()); | 165 assertArrayEquals([], tree.exportValues()); |
166 })(); | 166 })(); |
OLD | NEW |