Debian Codegraph @

closure-library/closure/goog/structs/avltree_test.js

raw
1 // Copyright 2007 The Closure Library Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 goog.provide('goog.structs.AvlTreeTest');
16 goog.setTestOnly('goog.structs.AvlTreeTest');
17
18 goog.require('goog.array');
19 goog.require('goog.structs.AvlTree');
20 goog.require('goog.testing.jsunit');
21
22
23 /**
24 * This test verifies that we can insert strings into the AvlTree and have
25 * them be stored and sorted correctly by the default comparator.
26 */
27 function testInsertsWithDefaultComparator() {
28 var tree = new goog.structs.AvlTree();
29 var values = ['bill', 'blake', 'elliot', 'jacob', 'john', 'myles', 'ted'];
30
31 // Insert strings into tree out of order
32 tree.add(values[4]);
33 tree.add(values[3]);
34 tree.add(values[0]);
35 tree.add(values[6]);
36 tree.add(values[5]);
37 tree.add(values[1]);
38 tree.add(values[2]);
39
40 // Verify strings are stored in sorted order
41 var i = 0;
42 tree.inOrderTraverse(function(value) {
43 assertEquals(values[i], value);
44 i += 1;
45 });
46 assertEquals(i, values.length);
47
48 // Verify that no nodes are visited if the start value is larger than all
49 // values
50 tree.inOrderTraverse(function(value) { fail(); }, 'zed');
51
52 // Verify strings are stored in sorted order
53 i = values.length;
54 tree.reverseOrderTraverse(function(value) {
55 i--;
56 assertEquals(values[i], value);
57 });
58 assertEquals(i, 0);
59
60 // Verify that no nodes are visited if the start value is smaller than all
61 // values
62 tree.reverseOrderTraverse(function(value) { fail(); }, 'aardvark');
63 }
64
65
66 /**
67 * This test verifies that we can insert strings into and remove strings from
68 * the AvlTree and have the only the non-removed values be stored and sorted
69 * correctly by the default comparator.
70 */
71 function testRemovesWithDefaultComparator() {
72 var tree = new goog.structs.AvlTree();
73 var values = ['bill', 'blake', 'elliot', 'jacob', 'john', 'myles', 'ted'];
74
75 // Insert strings into tree out of order
76 tree.add('frodo');
77 tree.add(values[4]);
78 tree.add(values[3]);
79 tree.add(values[0]);
80 tree.add(values[6]);
81 tree.add('samwise');
82 tree.add(values[5]);
83 tree.add(values[1]);
84 tree.add(values[2]);
85 tree.add('pippin');
86
87 // Remove strings from tree
88 assertEquals(tree.remove('samwise'), 'samwise');
89 assertEquals(tree.remove('pippin'), 'pippin');
90 assertEquals(tree.remove('frodo'), 'frodo');
91 assertEquals(tree.remove('merry'), null);
92
93
94 // Verify strings are stored in sorted order
95 var i = 0;
96 tree.inOrderTraverse(function(value) {
97 assertEquals(values[i], value);
98 i += 1;
99 });
100 assertEquals(i, values.length);
101 }
102
103
104 /**
105 * This test verifies that we can insert values into and remove values from
106 * the AvlTree and have them be stored and sorted correctly by a custom
107 * comparator.
108 */
109 function testInsertsAndRemovesWithCustomComparator() {
110 var tree = new goog.structs.AvlTree(function(a, b) { return a - b; });
111
112 var NUM_TO_INSERT = 37;
113 var valuesToRemove = [1, 0, 6, 7, 36];
114
115 // Insert ints into tree out of order
116 var values = [];
117 for (var i = 0; i < NUM_TO_INSERT; i += 1) {
118 tree.add(i);
119 values.push(i);
120 }
121
122 for (var i = 0; i < valuesToRemove.length; i += 1) {
123 assertEquals(tree.remove(valuesToRemove[i]), valuesToRemove[i]);
124 goog.array.remove(values, valuesToRemove[i]);
125 }
126 assertEquals(tree.remove(-1), null);
127 assertEquals(tree.remove(37), null);
128
129 // Verify strings are stored in sorted order
130 var i = 0;
131 tree.inOrderTraverse(function(value) {
132 assertEquals(values[i], value);
133 i += 1;
134 });
135 assertEquals(i, values.length);
136 }
137
138
139 /**
140 * This test verifies that we can insert values into and remove values from
141 * the AvlTree and have it maintain the AVL-Tree upperbound on its height.
142 */
143 function testAvlTreeHeight() {
144 var tree = new goog.structs.AvlTree(function(a, b) { return a - b; });
145
146 var NUM_TO_INSERT = 2000;
147 var NUM_TO_REMOVE = 500;
148
149 // Insert ints into tree out of order
150 for (var i = 0; i < NUM_TO_INSERT; i += 1) {
151 tree.add(i);
152 }
153
154 // Remove valuse
155 for (var i = 0; i < NUM_TO_REMOVE; i += 1) {
156 tree.remove(i);
157 }
158
159 assertTrue(
160 tree.getHeight() <=
161 1.4405 * (Math.log(NUM_TO_INSERT - NUM_TO_REMOVE + 2) / Math.log(2)) -
162 1.3277);
163 }
164
165
166 /**
167 * This test verifies that we can insert values into and remove values from
168 * the AvlTree and have its contains method correctly determine the values it
169 * is contains.
170 */
171 function testAvlTreeContains() {
172 var tree = new goog.structs.AvlTree();
173 var values = ['bill', 'blake', 'elliot', 'jacob', 'john', 'myles', 'ted'];
174
175 // Insert strings into tree out of order
176 tree.add('frodo');
177 tree.add(values[4]);
178 tree.add(values[3]);
179 tree.add(values[0]);
180 tree.add(values[6]);
181 tree.add('samwise');
182 tree.add(values[5]);
183 tree.add(values[1]);
184 tree.add(values[2]);
185 tree.add('pippin');
186
187 // Remove strings from tree
188 assertEquals(tree.remove('samwise'), 'samwise');
189 assertEquals(tree.remove('pippin'), 'pippin');
190 assertEquals(tree.remove('frodo'), 'frodo');
191
192 for (var i = 0; i < values.length; i += 1) {
193 assertTrue(tree.contains(values[i]));
194 }
195 assertFalse(tree.contains('samwise'));
196 assertFalse(tree.contains('pippin'));
197 assertFalse(tree.contains('frodo'));
198 }
199
200
201 /**
202 * This test verifies that we can insert values into and remove values from
203 * the AvlTree and have its indexOf method correctly determine the in-order
204 * index of the values it contains.
205 */
206 function testAvlTreeIndexOf() {
207 var tree = new goog.structs.AvlTree();
208 var values = ['bill', 'blake', 'elliot', 'jacob', 'john', 'myles', 'ted'];
209
210 // Insert strings into tree out of order
211 tree.add('frodo');
212 tree.add(values[4]);
213 tree.add(values[3]);
214 tree.add(values[0]);
215 tree.add(values[6]);
216 tree.add('samwise');
217 tree.add(values[5]);
218 tree.add(values[1]);
219 tree.add(values[2]);
220 tree.add('pippin');
221
222 // Remove strings from tree
223 assertEquals('samwise', tree.remove('samwise'));
224 assertEquals('pippin', tree.remove('pippin'));
225 assertEquals('frodo', tree.remove('frodo'));
226
227 for (var i = 0; i < values.length; i += 1) {
228 assertEquals(i, tree.indexOf(values[i]));
229 }
230 assertEquals(-1, tree.indexOf('samwise'));
231 assertEquals(-1, tree.indexOf('pippin'));
232 assertEquals(-1, tree.indexOf('frodo'));
233 }
234
235
236 /**
237 * This test verifies that we can insert values into and remove values from
238 * the AvlTree and have its minValue and maxValue routines return the correct
239 * min and max values contained by the tree.
240 */
241 function testMinAndMaxValues() {
242 var tree = new goog.structs.AvlTree(function(a, b) { return a - b; });
243
244 var NUM_TO_INSERT = 2000;
245 var NUM_TO_REMOVE = 500;
246
247 // Insert ints into tree out of order
248 for (var i = 0; i < NUM_TO_INSERT; i += 1) {
249 tree.add(i);
250 }
251
252 // Remove valuse
253 for (var i = 0; i < NUM_TO_REMOVE; i += 1) {
254 tree.remove(i);
255 }
256
257 assertEquals(tree.getMinimum(), NUM_TO_REMOVE);
258 assertEquals(tree.getMaximum(), NUM_TO_INSERT - 1);
259 }
260
261
262 /**
263 * This test verifies that we can insert values into and remove values from
264 * the AvlTree and traverse the tree in reverse order using the
265 * reverseOrderTraverse routine.
266 */
267 function testReverseOrderTraverse() {
268 var tree = new goog.structs.AvlTree(function(a, b) { return a - b; });
269
270 var NUM_TO_INSERT = 2000;
271 var NUM_TO_REMOVE = 500;
272
273 // Insert ints into tree out of order
274 for (var i = 0; i < NUM_TO_INSERT; i += 1) {
275 tree.add(i);
276 }
277
278 // Remove valuse
279 for (var i = 0; i < NUM_TO_REMOVE; i += 1) {
280 tree.remove(i);
281 }
282
283 var i = NUM_TO_INSERT - 1;
284 tree.reverseOrderTraverse(function(value) {
285 assertEquals(value, i);
286 i -= 1;
287 });
288 assertEquals(i, NUM_TO_REMOVE - 1);
289 }
290
291
292 /**
293 * Verifies correct behavior of getCount(). See http://b/4347755
294 */
295 function testGetCountBehavior() {
296 var tree = new goog.structs.AvlTree();
297 tree.add(1);
298 tree.remove(1);
299 assertEquals(0, tree.getCount());
300
301 var values = ['bill', 'blake', 'elliot', 'jacob', 'john', 'myles', 'ted'];
302
303 // Insert strings into tree out of order
304 tree.add('frodo');
305 tree.add(values[4]);
306 tree.add(values[3]);
307 tree.add(values[0]);
308 tree.add(values[6]);
309 tree.add('samwise');
310 tree.add(values[5]);
311 tree.add(values[1]);
312 tree.add(values[2]);
313 tree.add('pippin');
314 assertEquals(10, tree.getCount());
315 assertEquals(
316 tree.root_.left.count + tree.root_.right.count + 1, tree.getCount());
317
318 // Remove strings from tree
319 assertEquals('samwise', tree.remove('samwise'));
320 assertEquals('pippin', tree.remove('pippin'));
321 assertEquals('frodo', tree.remove('frodo'));
322 assertEquals(null, tree.remove('merry'));
323 assertEquals(7, tree.getCount());
324
325 assertEquals(
326 tree.root_.left.count + tree.root_.right.count + 1, tree.getCount());
327 }
328
329
330 /**
331 * This test verifies that getKthOrder gets the correct value.
332 */
333 function testGetKthOrder() {
334 var tree = new goog.structs.AvlTree(function(a, b) { return a - b; });
335
336 var NUM_TO_INSERT = 2000;
337 var NUM_TO_REMOVE = 500;
338
339 // Insert ints into tree out of order
340 for (var i = 0; i < NUM_TO_INSERT; i += 1) {
341 tree.add(i);
342 }
343
344 // Remove values.
345 for (var i = 0; i < NUM_TO_REMOVE; i += 1) {
346 tree.remove(i);
347 }
348 for (var k = 0; k < tree.getCount(); ++k) {
349 assertEquals(NUM_TO_REMOVE + k, tree.getKthValue(k));
350 }
351 }