Debian Codegraph @

closure-library/closure/goog/structs/trie_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.TrieTest');
16 goog.setTestOnly('goog.structs.TrieTest');
17
18 goog.require('goog.object');
19 goog.require('goog.structs');
20 goog.require('goog.structs.Trie');
21 goog.require('goog.testing.jsunit');
22
23 function makeTrie() {
24 var trie = new goog.structs.Trie();
25 trie.add('hello', 1);
26 trie.add('hi', 'howdy');
27 trie.add('', 'an empty string key');
28 trie.add('empty value', '');
29 trie.add('zero', 0);
30 trie.add('object', {});
31 trie.add('null', null);
32 trie.add('hello, world', 2);
33 trie.add('world', {});
34 return trie;
35 }
36
37 function checkTrie(trie) {
38 assertEquals('get, should be 1', trie.get('hello'), 1);
39 assertEquals('get, should be "howdy"', trie.get('hi'), 'howdy');
40 assertEquals(
41 'get, should be "an empty string key"', trie.get(''),
42 'an empty string key');
43 assertEquals('get, should be ""', trie.get('empty value'), '');
44 assertEquals('get, should be ""', typeof trie.get('empty value'), 'string');
45 assertEquals('get, should be an object', typeof trie.get('object'), 'object');
46 assertEquals('get, should be 0', trie.get('zero'), 0);
47 assertEquals('get "null", should be null', trie.get('null'), null);
48 assertEquals('get, should be 2', trie.get('hello, world'), 2);
49 assertEquals('get, should be an object', typeof trie.get('world'), 'object');
50 }
51
52 function testTrieFormation() {
53 var t = makeTrie();
54 checkTrie(t);
55 }
56
57 function testFailureOfMultipleAdds() {
58 var t = new goog.structs.Trie();
59 t.add('hello', 'testing');
60 assertThrows('Error should be thrown when same key added twice.', function() {
61 t.add('hello', 'test');
62 });
63
64 t = new goog.structs.Trie();
65 t.add('null', null);
66 assertThrows('Error should be thrown when same key added twice.', function() {
67 t.add('null', 'hi!');
68 });
69
70 t = new goog.structs.Trie();
71 t.add('null', 'blah');
72 assertThrows('Error should be thrown when same key added twice.', function() {
73 t.add('null', null);
74 });
75 }
76
77 function testTrieClone() {
78 var trieOne = makeTrie();
79 var trieTwo = new goog.structs.Trie(trieOne);
80 checkTrie(trieTwo);
81 }
82
83 function testTrieFromObject() {
84 var someObject = {
85 'hello': 1,
86 'hi': 'howdy',
87 '': 'an empty string key',
88 'empty value': '',
89 'object': {},
90 'zero': 0,
91 'null': null,
92 'hello, world': 2,
93 'world': {}
94 };
95 var trie = new goog.structs.Trie(someObject);
96 checkTrie(trie);
97 }
98
99 function testTrieGetValues() {
100 var trie = makeTrie();
101 var values = trie.getValues();
102 assertTrue(
103 'getValues, should contain "howdy"',
104 goog.object.contains(values, 'howdy'));
105 assertTrue('getValues, should contain 1', goog.object.contains(values, 1));
106 assertTrue('getValues, should contain 0', goog.object.contains(values, 0));
107 assertTrue('getValues, should contain ""', goog.object.contains(values, ''));
108 assertTrue(
109 'getValues, should contain null', goog.object.contains(values, null));
110 assertEquals(
111 'goog.structs.getCount(getValues()) should be 9',
112 goog.structs.getCount(values), 9);
113 }
114
115 function testTrieGetKeys() {
116 var trie = makeTrie();
117 var keys = trie.getKeys();
118 assertTrue(
119 'getKeys, should contain "hello"', goog.object.contains(keys, 'hello'));
120 assertTrue(
121 'getKeys, should contain "empty value"',
122 goog.object.contains(keys, 'empty value'));
123 assertTrue('getKeys, should contain ""', goog.object.contains(keys, ''));
124 assertTrue(
125 'getKeys, should contain "zero"', goog.object.contains(keys, 'zero'));
126 assertEquals(
127 'goog.structs.getCount(getKeys()) should be 9',
128 goog.structs.getCount(keys), 9);
129 }
130
131
132 function testTrieCount() {
133 var trieOne = makeTrie();
134 var trieTwo = new goog.structs.Trie();
135 assertEquals('count, should be 9', trieOne.getCount(), 9);
136 assertEquals('count, should be 0', trieTwo.getCount(), 0);
137 }
138
139 function testRemoveKeyFromTrie() {
140 var trie = new goog.structs.Trie();
141 trie.add('key1', 'value1');
142 trie.add('key2', 'value2');
143 trie.add('ke', 'value3');
144 trie.add('zero', 0);
145 trie.remove('key2');
146 assertEquals('get "key1", should be "value1"', trie.get('key1'), 'value1');
147 assertUndefined('get "key2", should be undefined', trie.get('key2'));
148 trie.remove('zero');
149 assertUndefined('get "zero", should be undefined', trie.get('zero'));
150 trie.remove('ke');
151 assertUndefined('get "ke", should be undefined', trie.get('ke'));
152 assertEquals('get "key1", should be "value1"', trie.get('key1'), 'value1');
153 trie.add('a', 'value4');
154 assertTrue(
155 'testing internal structure, a should be a child',
156 'a' in trie.childNodes_);
157 trie.remove('a');
158 assertFalse(
159 'testing internal structure, a should no longer be a child',
160 'a' in trie.childNodes_);
161
162 trie.add('xyza', 'value');
163 trie.remove('xyza', 'value');
164 assertFalse('Should not have "x"', 'x' in trie.childNodes_);
165
166 trie.add('xyza', null);
167 assertTrue('Should have "x"', 'x' in trie.childNodes_);
168 trie.remove('xyza');
169 assertFalse('Should not have "x"', 'x' in trie.childNodes_);
170
171 trie.add('xyza', 'value');
172 trie.add('xb', 'value');
173 trie.remove('xyza');
174 assertTrue('get "x" should be defined', 'x' in trie.childNodes_);
175 assertFalse(
176 'get "y" should be undefined', 'y' in trie.childNodes_['x'].childNodes_);
177
178 trie.add('akey', 'value1');
179 trie.add('akey1', 'value2');
180 trie.remove('akey1');
181 assertEquals('get "akey", should be "value1"', 'value1', trie.get('akey'));
182 assertUndefined('get "akey1", should be undefined', trie.get('akey1'));
183 }
184
185 function testRemoveKeyFromTrieWithNulls() {
186 var trie = new goog.structs.Trie();
187 trie.add('key1', null);
188 trie.add('key2', 'value2');
189 trie.add('ke', 'value3');
190 trie.add('zero', 0);
191 trie.remove('key2');
192 assertEquals('get "key1", should be null', trie.get('key1'), null);
193 assertUndefined('get "key2", should be undefined', trie.get('key2'));
194 trie.remove('zero');
195 assertUndefined('get "zero", should be undefined', trie.get('zero'));
196 trie.remove('ke');
197 assertUndefined('get "ke", should be undefined', trie.get('ke'));
198 assertEquals('get "key1", should be null', trie.get('key1'), null);
199 trie.add('a', 'value4');
200 assertTrue(
201 'testing internal structure, a should be a child',
202 'a' in trie.childNodes_);
203 trie.remove('a');
204 assertFalse(
205 'testing internal structure, a should no longer be a child',
206 'a' in trie.childNodes_);
207
208 trie.add('xyza', null);
209 trie.add('xb', 'value');
210 trie.remove('xyza');
211 assertTrue('Should have "x"', 'x' in trie.childNodes_);
212 assertFalse('Should not have "y"', 'y' in trie.childNodes_['x'].childNodes_);
213 }
214
215 function testRemoveKeyException() {
216 var trie = new goog.structs.Trie();
217 trie.add('abcdefg', 'value');
218 trie.add('abcz', 'value');
219 trie.add('abc', 'value');
220
221 assertThrows(
222 'Remove should throw an error on removal of non-existent key',
223 function() { trie.remove('abcdefge'); });
224 }
225
226 function testTrieIsEmpty() {
227 var trieOne = new goog.structs.Trie();
228 var trieTwo = makeTrie();
229 assertTrue('isEmpty, should be empty', trieOne.isEmpty());
230 assertFalse('isEmpty, should not be empty', trieTwo.isEmpty());
231 trieOne.add('', 1);
232 assertFalse('isEmpty, should not be empty', trieTwo.isEmpty());
233 trieOne.remove('');
234 assertTrue('isEmpty, should be empty', trieOne.isEmpty());
235 trieOne.add('', 1);
236 trieOne.add('a', 1);
237 trieOne.remove('a');
238 assertFalse('isEmpty, should not be empty', trieOne.isEmpty());
239 trieOne.remove('');
240 assertTrue('isEmpty, should be empty', trieOne.isEmpty());
241 trieOne.add('', 1);
242 trieOne.add('a', 1);
243 trieOne.remove('');
244 assertFalse('isEmpty, should not be empty', trieOne.isEmpty());
245 trieOne.remove('a');
246 assertTrue('isEmpty, should be empty', trieOne.isEmpty());
247 }
248
249 function testTrieClear() {
250 var trie = new goog.structs.Trie();
251 trie.add('key1', 'value1');
252 trie.add('key2', 'value2');
253 trie.add('key3', null);
254 trie.clear();
255 assertUndefined('get key1, should be undefined', trie.get('key1'));
256 assertUndefined('get key2, should be undefined', trie.get('key2'));
257 assertUndefined('get key3, should be undefined', trie.get('key3'));
258 }
259
260 function testTrieContainsKey() {
261 var trie = makeTrie();
262 assertTrue('containsKey, should contain "hello"', trie.containsKey('hello'));
263 assertTrue('containsKey, should contain "hi"', trie.containsKey('hi'));
264 assertTrue('containsKey, should contain ""', trie.containsKey(''));
265 assertTrue(
266 'containsKey, should contain "empty value"',
267 trie.containsKey('empty value'));
268 assertTrue(
269 'containsKey, should contain "object"', trie.containsKey('object'));
270 assertTrue('containsKey, should contain "zero"', trie.containsKey('zero'));
271 assertTrue('containsKey, should contain "null"', trie.containsKey('null'));
272 assertFalse(
273 'containsKey, should not contain "blah"', trie.containsKey('blah'));
274 trie.remove('');
275 trie.remove('hi');
276 trie.remove('zero');
277 trie.remove('null');
278 assertFalse(
279 'containsKey, should not contain "zero"', trie.containsKey('zero'));
280 assertFalse('containsKey, should not contain ""', trie.containsKey(''));
281 assertFalse('containsKey, should not contain "hi"', trie.containsKey('hi'));
282 assertFalse(
283 'containsKey, should not contain "null"', trie.containsKey('null'));
284 }
285
286 function testTrieContainsPrefix() {
287 // Empty trie.
288 var trie = new goog.structs.Trie();
289 assertFalse('containsPrefix, should not contain ""', trie.containsPrefix(''));
290 assertFalse(
291 'containsPrefix, should not contain "any"', trie.containsPrefix('any'));
292 trie.add('key', 'value');
293 assertTrue('containsPrefix, should contain ""', trie.containsPrefix(''));
294
295 // Non-empty trie.
296 trie = makeTrie();
297 assertTrue('containsPrefix, should contain ""', trie.containsPrefix(''));
298 assertFalse(
299 'containsPrefix, should not contain "blah"', trie.containsPrefix('blah'));
300 assertTrue('containsPrefix, should contain "h"', trie.containsPrefix('h'));
301 assertTrue(
302 'containsPrefix, should contain "hello"', trie.containsPrefix('hello'));
303 assertTrue(
304 'containsPrefix, should contain "hello, world"',
305 trie.containsPrefix('hello, world'));
306 assertFalse(
307 'containsPrefix, should not contain "hello, world!"',
308 trie.containsPrefix('hello, world!'));
309 assertTrue('containsPrefix, should contain "nu"', trie.containsPrefix('nu'));
310 assertTrue(
311 'containsPrefix, should contain "null"', trie.containsPrefix('null'));
312 assertTrue(
313 'containsPrefix, should contain "empty value"',
314 trie.containsPrefix('empty value'));
315
316 // Remove nodes.
317 trie.remove('');
318 assertTrue('containsPrefix, should contain ""', trie.containsPrefix(''));
319 trie.remove('hi');
320 assertTrue('containsPrefix, should contain "h"', trie.containsPrefix('h'));
321 assertFalse(
322 'containsPrefix, should not contain "hi"', trie.containsPrefix('hi'));
323 trie.remove('hello');
324 trie.remove('hello, world');
325 assertFalse(
326 'containsPrefix, should not contain "h"', trie.containsPrefix('h'));
327 assertFalse(
328 'containsPrefix, should not contain "hello"',
329 trie.containsPrefix('hello'));
330
331 // Remove all nodes.
332 trie.remove('empty value');
333 trie.remove('zero');
334 trie.remove('object');
335 trie.remove('null');
336 trie.remove('world');
337 assertFalse('containsPrefix, should not contain ""', trie.containsPrefix(''));
338 assertFalse(
339 'containsPrefix, should not contain "h"', trie.containsPrefix('h'));
340 assertFalse(
341 'containsPrefix, should not contain "hi"', trie.containsPrefix('hi'));
342
343 // Add some new nodes.
344 trie.add('hi', 'value');
345 trie.add('null', 'value');
346 assertTrue('containsPrefix, should contain ""', trie.containsPrefix(''));
347 assertTrue('containsPrefix, should contain "h"', trie.containsPrefix('h'));
348 assertTrue('containsPrefix, should contain "hi"', trie.containsPrefix('hi'));
349 assertFalse(
350 'containsPrefix, should not contain "hello"',
351 trie.containsPrefix('hello'));
352 assertFalse(
353 'containsPrefix, should not contain "zero"', trie.containsPrefix('zero'));
354
355 // Clear the trie.
356 trie.clear();
357 assertFalse('containsPrefix, should not contain ""', trie.containsPrefix(''));
358 assertFalse(
359 'containsPrefix, should not contain "h"', trie.containsPrefix('h'));
360 assertFalse(
361 'containsPrefix, should not contain "hi"', trie.containsPrefix('hi'));
362 }
363
364 function testTrieContainsValue() {
365 var trie = makeTrie();
366 assertTrue(
367 'containsValue, should be true, should contain 1', trie.containsValue(1));
368 assertTrue(
369 'containsValue, should be true, should contain "howdy"',
370 trie.containsValue('howdy'));
371 assertTrue(
372 'containsValue, should be true, should contain ""',
373 trie.containsValue(''));
374 assertTrue(
375 'containsValue, should be true, should contain 0', trie.containsValue(0));
376 assertTrue(
377 'containsValue, should be true, should contain null',
378 trie.containsValue(null));
379 assertTrue(
380 'containsValue, should be true, should ' +
381 'contain "an empty string key"',
382 trie.containsValue('an empty string key'));
383 assertFalse(
384 'containsValue, should be false, should not contain "blah"',
385 trie.containsValue('blah'));
386 trie.remove('empty value');
387 trie.remove('zero');
388 assertFalse(
389 'containsValue, should be false, should not contain 0',
390 trie.containsValue(0));
391 assertFalse(
392 'containsValue, should be false, should not contain ""',
393 trie.containsValue(''));
394 }
395
396 function testTrieHandlingOfEmptyStrings() {
397 var trie = new goog.structs.Trie();
398 assertEquals('get, should be undefined', trie.get(''), undefined);
399 assertFalse('containsValue, should be false', trie.containsValue(''));
400 assertFalse('containsKey, should be false', trie.containsKey(''));
401 trie.add('', 'test');
402 trie.add('test2', '');
403 assertTrue('containsValue, should be true', trie.containsValue(''));
404 assertTrue('containsKey, should be true', trie.containsKey(''));
405 assertEquals('get, should be "test"', trie.get(''), 'test');
406 assertEquals('get, should be ""', trie.get('test2'), '');
407 trie.remove('');
408 trie.remove('test2');
409 assertEquals('get, should be undefined', trie.get(''), undefined);
410 assertFalse('containsValue, should be false', trie.containsValue(''));
411 assertFalse('containsKey, should be false', trie.containsKey(''));
412 }
413
414 function testPrefixOptionOnGetKeys() {
415 var trie = new goog.structs.Trie();
416 trie.add('abcdefg', 'one');
417 trie.add('abcdefghijk', 'two');
418 trie.add('abcde', 'three');
419 trie.add('abcq', null);
420 trie.add('abc', 'four');
421 trie.add('xyz', 'five');
422 assertEquals('getKeys, should be 1', trie.getKeys('xy').length, 1);
423 assertEquals('getKeys, should be 1', trie.getKeys('xyz').length, 1);
424 assertEquals('getKeys, should be 1', trie.getKeys('x').length, 1);
425 assertEquals('getKeys, should be 4', trie.getKeys('abc').length, 5);
426 assertEquals('getKeys, should be 2', trie.getKeys('abcdef').length, 2);
427 assertEquals('getKeys, should be 0', trie.getKeys('abcdefgi').length, 0);
428 }
429
430 function testGetKeyAndPrefixes() {
431 var trie = makeTrie();
432 // Note: trie has one of its keys as ''
433 assertEquals(
434 'getKeyAndPrefixes, should be 2', 2,
435 goog.object.getCount(trie.getKeyAndPrefixes('world')));
436 assertEquals(
437 'getKeyAndPrefixes, should be 2', 2,
438 goog.object.getCount(trie.getKeyAndPrefixes('hello')));
439 assertEquals(
440 'getKeyAndPrefixes, should be 2', 2,
441 goog.object.getCount(trie.getKeyAndPrefixes('hello,')));
442 assertEquals(
443 'getKeyAndPrefixes, should be 3', 3,
444 goog.object.getCount(trie.getKeyAndPrefixes('hello, world')));
445 assertEquals(
446 'getKeyAndPrefixes, should be 1', 1,
447 goog.object.getCount(trie.getKeyAndPrefixes('hell')));
448 }
449
450 function testGetKeyAndPrefixesStartIndex() {
451 var trie = new goog.structs.Trie();
452 trie.add('abcdefg', 'one');
453 trie.add('bcdefg', 'two');
454 trie.add('abcdefghijk', 'three');
455 trie.add('abcde', 'four');
456 trie.add('abcq', null);
457 trie.add('q', null);
458 trie.add('abc', 'five');
459 trie.add('xyz', 'six');
460 assertEquals(
461 'getKeyAndPrefixes, should be 3', 3,
462 goog.object.getCount(trie.getKeyAndPrefixes('abcdefg', 0)));
463 assertEquals(
464 'getKeyAndPrefixes, should be 1', 1,
465 goog.object.getCount(trie.getKeyAndPrefixes('abcdefg', 1)));
466 assertEquals(
467 'getKeyAndPrefixes, should be 1', 1,
468 goog.object.getCount(trie.getKeyAndPrefixes('abcq', 3)));
469 assertEquals(
470 'getKeyAndPrefixes, should be 0', 0,
471 goog.object.getCount(trie.getKeyAndPrefixes('abcd', 3)));
472 }