Debian Codegraph @

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

raw
1 // Copyright 2006 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.SetTest');
16 goog.setTestOnly('goog.structs.SetTest');
17
18 goog.require('goog.iter');
19 goog.require('goog.structs');
20 goog.require('goog.structs.Set');
21 goog.require('goog.testing.jsunit');
22
23 var Set = goog.structs.Set;
24
25 function stringifySet(s) {
26 return goog.structs.getValues(s).join('');
27 }
28
29 function testGetCount() {
30 var s = new Set;
31 var a = new String('a');
32 s.add(a);
33 var b = new String('b');
34 s.add(b);
35 var c = new String('c');
36 s.add(c);
37 assertEquals('count, should be 3', s.getCount(), 3);
38 var d = new String('d');
39 s.add(d);
40 assertEquals('count, should be 4', s.getCount(), 4);
41 s.remove(d);
42 assertEquals('count, should be 3', s.getCount(), 3);
43
44 s = new Set;
45 s.add('a');
46 s.add('b');
47 s.add('c');
48 assertEquals('count, should be 3', s.getCount(), 3);
49 s.add('d');
50 assertEquals('count, should be 4', s.getCount(), 4);
51 s.remove('d');
52 assertEquals('count, should be 3', s.getCount(), 3);
53 }
54
55 function testGetValues() {
56 var s = new Set;
57 var a = new String('a');
58 s.add(a);
59 var b = new String('b');
60 s.add(b);
61 var c = new String('c');
62 s.add(c);
63 var d = new String('d');
64 s.add(d);
65 assertEquals(s.getValues().join(''), 'abcd');
66
67 var s = new Set;
68 s.add('a');
69 s.add('b');
70 s.add('c');
71 s.add('d');
72 assertEquals(s.getValues().join(''), 'abcd');
73 }
74
75 function testContains() {
76 var s = new Set;
77 var a = new String('a');
78 s.add(a);
79 var b = new String('b');
80 s.add(b);
81 var c = new String('c');
82 s.add(c);
83 var d = new String('d');
84 s.add(d);
85 var e = new String('e');
86
87 assertTrue("contains, Should contain 'a'", s.contains(a));
88 assertFalse("contains, Should not contain 'e'", s.contains(e));
89
90 s = new Set;
91 s.add('a');
92 s.add('b');
93 s.add('c');
94 s.add('d');
95
96 assertTrue("contains, Should contain 'a'", s.contains('a'));
97 assertFalse("contains, Should not contain 'e'", s.contains('e'));
98 }
99
100 function testContainsFunctionValue() {
101 var s = new Set;
102
103 var fn1 = function() {};
104
105 assertFalse(s.contains(fn1));
106 s.add(fn1);
107 assertTrue(s.contains(fn1));
108
109 var fn2 = function() {};
110
111 assertFalse(s.contains(fn2));
112 s.add(fn2);
113 assertTrue(s.contains(fn2));
114
115 assertEquals(s.getCount(), 2);
116 }
117
118 function testContainsAll() {
119 var set = new Set([1, 2, 3]);
120
121 assertTrue('{1, 2, 3} contains []', set.containsAll([]));
122 assertTrue('{1, 2, 3} contains [1]', set.containsAll([1]));
123 assertTrue('{1, 2, 3} contains [1, 1]', set.containsAll([1, 1]));
124 assertTrue('{1, 2, 3} contains [3, 2, 1]', set.containsAll([3, 2, 1]));
125 assertFalse("{1, 2, 3} doesn't contain [4]", set.containsAll([4]));
126 assertFalse("{1, 2, 3} doesn't contain [1, 4]", set.containsAll([1, 4]));
127
128 assertTrue('{1, 2, 3} contains {a: 1}', set.containsAll({a: 1}));
129 assertFalse("{1, 2, 3} doesn't contain {a: 4}", set.containsAll({a: 4}));
130
131 assertTrue('{1, 2, 3} contains {1}', set.containsAll(new Set([1])));
132 assertFalse("{1, 2, 3} doesn't contain {4}", set.containsAll(new Set([4])));
133 }
134
135 function testIntersection() {
136 var emptySet = new Set;
137
138 assertTrue(
139 'intersection of empty set and [] should be empty',
140 emptySet.intersection([]).isEmpty());
141 assertIntersection(
142 'intersection of 2 empty sets should be empty', emptySet, new Set(),
143 new Set());
144
145 var abcdSet = new Set();
146 abcdSet.add('a');
147 abcdSet.add('b');
148 abcdSet.add('c');
149 abcdSet.add('d');
150
151 assertTrue(
152 'intersection of populated set and [] should be empty',
153 abcdSet.intersection([]).isEmpty());
154 assertIntersection(
155 'intersection of populated set and empty set should be empty', abcdSet,
156 new Set(), new Set());
157
158 var bcSet = new Set(['b', 'c']);
159 assertIntersection(
160 'intersection of [a,b,c,d] and [b,c]', abcdSet, bcSet, bcSet);
161
162 var bceSet = new Set(['b', 'c', 'e']);
163 assertIntersection(
164 'intersection of [a,b,c,d] and [b,c,e]', abcdSet, bceSet, bcSet);
165 }
166
167 function testDifference() {
168 var emptySet = new Set;
169
170 assertTrue(
171 'difference of empty set and [] should be empty',
172 emptySet.difference([]).isEmpty());
173 assertTrue(
174 'difference of 2 empty sets should be empty',
175 emptySet.difference(new Set()).isEmpty());
176
177 var abcdSet = new Set(['a', 'b', 'c', 'd']);
178
179 assertTrue(
180 'difference of populated set and [] should be the populated set',
181 abcdSet.difference([]).equals(abcdSet));
182 assertTrue(
183 'difference of populated set and empty set should be the populated set',
184 abcdSet.difference(new Set()).equals(abcdSet));
185 assertTrue(
186 'difference of two identical sets should be the empty set',
187 abcdSet.difference(abcdSet).equals(new Set()));
188
189 var bcSet = new Set(['b', 'c']);
190 assertTrue(
191 'difference of [a,b,c,d] and [b,c] shoule be [a,d]',
192 abcdSet.difference(bcSet).equals(new Set(['a', 'd'])));
193 assertTrue(
194 'difference of [b,c] and [a,b,c,d] should be the empty set',
195 bcSet.difference(abcdSet).equals(new Set()));
196
197 var xyzSet = new Set(['x', 'y', 'z']);
198 assertTrue(
199 'difference of [a,b,c,d] and [x,y,z] should be the [a,b,c,d]',
200 abcdSet.difference(xyzSet).equals(abcdSet));
201 }
202
203
204 /**
205 * Helper function to assert intersection is commutative.
206 */
207 function assertIntersection(msg, set1, set2, expectedIntersection) {
208 assertTrue(
209 msg + ': set1->set2',
210 set1.intersection(set2).equals(expectedIntersection));
211 assertTrue(
212 msg + ': set2->set1',
213 set2.intersection(set1).equals(expectedIntersection));
214 }
215
216 function testRemoveAll() {
217 assertRemoveAll('removeAll of empty set from empty set', [], [], []);
218 assertRemoveAll(
219 'removeAll of empty set from populated set', ['a', 'b', 'c', 'd'], [],
220 ['a', 'b', 'c', 'd']);
221 assertRemoveAll(
222 'removeAll of [a,d] from [a,b,c,d]', ['a', 'b', 'c', 'd'], ['a', 'd'],
223 ['b', 'c']);
224 assertRemoveAll(
225 'removeAll of [b,c] from [a,b,c,d]', ['a', 'b', 'c', 'd'], ['b', 'c'],
226 ['a', 'd']);
227 assertRemoveAll(
228 'removeAll of [b,c,e] from [a,b,c,d]', ['a', 'b', 'c', 'd'],
229 ['b', 'c', 'e'], ['a', 'd']);
230 assertRemoveAll(
231 'removeAll of [a,b,c,d] from [a,d]', ['a', 'd'], ['a', 'b', 'c', 'd'],
232 []);
233 assertRemoveAll(
234 'removeAll of [a,b,c,d] from [b,c]', ['b', 'c'], ['a', 'b', 'c', 'd'],
235 []);
236 assertRemoveAll(
237 'removeAll of [a,b,c,d] from [b,c,e]', ['b', 'c', 'e'],
238 ['a', 'b', 'c', 'd'], ['e']);
239 }
240
241
242 /**
243 * Helper function to test removeAll.
244 */
245 function assertRemoveAll(msg, elements1, elements2, expectedResult) {
246 var set1 = new Set(elements1);
247 var set2 = new Set(elements2);
248 set1.removeAll(set2);
249
250 assertTrue(
251 msg + ': set1 count increased after removeAll',
252 elements1.length >= set1.getCount());
253 assertEquals(
254 msg + ': set2 count changed after removeAll', elements2.length,
255 set2.getCount());
256 assertTrue(msg + ': wrong set1 after removeAll', set1.equals(expectedResult));
257 assertIntersection(
258 msg + ': non-empty intersection after removeAll', set1, set2, []);
259 }
260
261 function testAdd() {
262 var s = new Set;
263 var a = new String('a');
264 var b = new String('b');
265 s.add(a);
266 assertTrue(s.contains(a));
267 s.add(b);
268 assertTrue(s.contains(b));
269
270 s = new Set;
271 s.add('a');
272 assertTrue(s.contains('a'));
273 s.add('b');
274 assertTrue(s.contains('b'));
275 s.add(null);
276 assertTrue('contains null', s.contains(null));
277 assertFalse('does not contain "null"', s.contains('null'));
278 }
279
280
281 function testClear() {
282 var s = new Set;
283 var a = new String('a');
284 s.add(a);
285 var b = new String('b');
286 s.add(b);
287 var c = new String('c');
288 s.add(c);
289 var d = new String('d');
290 s.add(d);
291 s.clear();
292 assertTrue('cleared so it should be empty', s.isEmpty());
293 assertTrue("cleared so it should not contain 'a' key", !s.contains(a));
294
295 s = new Set;
296 s.add('a');
297 s.add('b');
298 s.add('c');
299 s.add('d');
300 s.clear();
301 assertTrue('cleared so it should be empty', s.isEmpty());
302 assertTrue("cleared so it should not contain 'a' key", !s.contains('a'));
303 }
304
305
306 function testAddAll() {
307 var s = new Set;
308 var a = new String('a');
309 var b = new String('b');
310 var c = new String('c');
311 var d = new String('d');
312 s.addAll([a, b, c, d]);
313 assertTrue('addAll so it should not be empty', !s.isEmpty());
314 assertTrue("addAll so it should contain 'c' key", s.contains(c));
315
316 var s2 = new Set;
317 s2.addAll(s);
318 assertTrue('addAll so it should not be empty', !s2.isEmpty());
319 assertTrue("addAll so it should contain 'c' key", s2.contains(c));
320
321
322 s = new Set;
323 s.addAll(['a', 'b', 'c', 'd']);
324 assertTrue('addAll so it should not be empty', !s.isEmpty());
325 assertTrue("addAll so it should contain 'c' key", s.contains('c'));
326
327 s2 = new Set;
328 s2.addAll(s);
329 assertTrue('addAll so it should not be empty', !s2.isEmpty());
330 assertTrue("addAll so it should contain 'c' key", s2.contains('c'));
331 }
332
333
334 function testConstructor() {
335 var s = new Set;
336 var a = new String('a');
337 s.add(a);
338 var b = new String('b');
339 s.add(b);
340 var c = new String('c');
341 s.add(c);
342 var d = new String('d');
343 s.add(d);
344 var s2 = new Set(s);
345 assertFalse('constr with Set so it should not be empty', s2.isEmpty());
346 assertTrue('constr with Set so it should contain c', s2.contains(c));
347
348 s = new Set;
349 s.add('a');
350 s.add('b');
351 s.add('c');
352 s.add('d');
353 s2 = new Set(s);
354 assertFalse('constr with Set so it should not be empty', s2.isEmpty());
355 assertTrue('constr with Set so it should contain c', s2.contains('c'));
356 }
357
358
359 function testClone() {
360 var s = new Set;
361 var a = new String('a');
362 s.add(a);
363 var b = new String('b');
364 s.add(b);
365 var c = new String('c');
366 s.add(c);
367 var d = new String('d');
368 s.add(d);
369
370 var s2 = s.clone();
371 assertFalse('clone so it should not be empty', s2.isEmpty());
372 assertTrue("clone so it should contain 'c' key", s2.contains(c));
373
374 var s = new Set;
375 s.add('a');
376 s.add('b');
377 s.add('c');
378 s.add('d');
379
380 s2 = s.clone();
381 assertFalse('clone so it should not be empty', s2.isEmpty());
382 assertTrue("clone so it should contain 'c' key", s2.contains('c'));
383 }
384
385
386 /**
387 * Helper method for testEquals().
388 * @param {Object} a First element to use in the tests.
389 * @param {Object} b Second element to use in the tests.
390 * @param {Object} c Third element to use in the tests.
391 * @param {Object} d Fourth element to use in the tests.
392 */
393 function helperForTestEquals(a, b, c, d) {
394 var s = new Set([a, b, c]);
395
396 assertTrue('set == itself', s.equals(s));
397 assertTrue('set == same set', s.equals(new Set([a, b, c])));
398 assertTrue('set == its clone', s.equals(s.clone()));
399 assertTrue('set == array of same elements', s.equals([a, b, c]));
400 assertTrue(
401 'set == array of same elements in different order', s.equals([c, b, a]));
402
403 assertFalse('set != empty set', s.equals(new Set));
404 assertFalse('set != its subset', s.equals(new Set([a, c])));
405 assertFalse('set != its superset', s.equals(new Set([a, b, c, d])));
406 assertFalse('set != different set', s.equals(new Set([b, c, d])));
407 assertFalse('set != its subset as array', s.equals([a, c]));
408 assertFalse('set != its superset as array', s.equals([a, b, c, d]));
409 assertFalse('set != different set as array', s.equals([b, c, d]));
410 assertFalse('set != [a, b, c, c]', s.equals([a, b, c, c]));
411 assertFalse('set != [a, b, b]', s.equals([a, b, b]));
412 assertFalse('set != [a, a]', s.equals([a, a]));
413 }
414
415
416 function testEquals() {
417 helperForTestEquals(1, 2, 3, 4);
418 helperForTestEquals('a', 'b', 'c', 'd');
419 helperForTestEquals(
420 new String('a'), new String('b'), new String('c'), new String('d'));
421 }
422
423
424 /**
425 * Helper method for testIsSubsetOf().
426 * @param {Object} a First element to use in the tests.
427 * @param {Object} b Second element to use in the tests.
428 * @param {Object} c Third element to use in the tests.
429 * @param {Object} d Fourth element to use in the tests.
430 */
431 function helperForTestIsSubsetOf(a, b, c, d) {
432 var s = new Set([a, b, c]);
433
434 assertTrue('set <= itself', s.isSubsetOf(s));
435 assertTrue('set <= same set', s.isSubsetOf(new Set([a, b, c])));
436 assertTrue('set <= its clone', s.isSubsetOf(s.clone()));
437 assertTrue('set <= array of same elements', s.isSubsetOf([a, b, c]));
438 assertTrue(
439 'set <= array of same elements in different order', s.equals([c, b, a]));
440
441 assertTrue('set <= Set([a, b, c, d])', s.isSubsetOf(new Set([a, b, c, d])));
442 assertTrue('set <= [a, b, c, d]', s.isSubsetOf([a, b, c, d]));
443 assertTrue('set <= [a, b, c, c]', s.isSubsetOf([a, b, c, c]));
444
445 assertFalse('set !<= Set([a, b])', s.isSubsetOf(new Set([a, b])));
446 assertFalse('set !<= [a, b]', s.isSubsetOf([a, b]));
447 assertFalse('set !<= Set([c, d])', s.isSubsetOf(new Set([c, d])));
448 assertFalse('set !<= [c, d]', s.isSubsetOf([c, d]));
449 assertFalse('set !<= Set([a, c, d])', s.isSubsetOf(new Set([a, c, d])));
450 assertFalse('set !<= [a, c, d]', s.isSubsetOf([a, c, d]));
451 assertFalse('set !<= [a, a, b]', s.isSubsetOf([a, a, b]));
452 assertFalse('set !<= [a, a, b, b]', s.isSubsetOf([a, a, b, b]));
453 }
454
455
456 function testIsSubsetOf() {
457 helperForTestIsSubsetOf(1, 2, 3, 4);
458 helperForTestIsSubsetOf('a', 'b', 'c', 'd');
459 helperForTestIsSubsetOf(
460 new String('a'), new String('b'), new String('c'), new String('d'));
461 }
462
463
464 function testForEach() {
465 var s = new Set;
466 var a = new String('a');
467 s.add(a);
468 var b = new String('b');
469 s.add(b);
470 var c = new String('c');
471 s.add(c);
472 var d = new String('d');
473 s.add(d);
474 var str = '';
475 goog.structs.forEach(s, function(val, key, set) {
476 assertUndefined(key);
477 assertEquals(s, set);
478 str += val;
479 });
480 assertEquals(str, 'abcd');
481
482 s = new Set;
483 s.add('a');
484 s.add('b');
485 s.add('c');
486 s.add('d');
487 str = '';
488 goog.structs.forEach(s, function(val, key, set) {
489 assertUndefined(key);
490 assertEquals(s, set);
491 str += val;
492 });
493 assertEquals(str, 'abcd');
494 }
495
496
497 function testFilter() {
498 var s = new Set;
499 var a = new Number(0);
500 s.add(a);
501 var b = new Number(1);
502 s.add(b);
503 var c = new Number(2);
504 s.add(c);
505 var d = new Number(3);
506 s.add(d);
507
508 var s2 = goog.structs.filter(s, function(val, key, set) {
509 assertUndefined(key);
510 assertEquals(s, set);
511 return val > 1;
512 });
513 assertEquals(stringifySet(s2), '23');
514
515 s = new Set;
516 s.add(0);
517 s.add(1);
518 s.add(2);
519 s.add(3);
520
521 s2 = goog.structs.filter(s, function(val, key, set) {
522 assertUndefined(key);
523 assertEquals(s, set);
524 return val > 1;
525 });
526 assertEquals(stringifySet(s2), '23');
527 }
528
529
530 function testSome() {
531 var s = new Set;
532 var a = new Number(0);
533 s.add(a);
534 var b = new Number(1);
535 s.add(b);
536 var c = new Number(2);
537 s.add(c);
538 var d = new Number(3);
539 s.add(d);
540
541 var b = goog.structs.some(s, function(val, key, s2) {
542 assertUndefined(key);
543 assertEquals(s, s2);
544 return val > 1;
545 });
546 assertTrue(b);
547 var b = goog.structs.some(s, function(val, key, s2) {
548 assertUndefined(key);
549 assertEquals(s, s2);
550 return val > 100;
551 });
552 assertFalse(b);
553
554 s = new Set;
555 s.add(0);
556 s.add(1);
557 s.add(2);
558 s.add(3);
559
560 b = goog.structs.some(s, function(val, key, s2) {
561 assertUndefined(key);
562 assertEquals(s, s2);
563 return val > 1;
564 });
565 assertTrue(b);
566 b = goog.structs.some(s, function(val, key, s2) {
567 assertUndefined(key);
568 assertEquals(s, s2);
569 return val > 100;
570 });
571 assertFalse(b);
572 }
573
574
575 function testEvery() {
576 var s = new Set;
577 var a = new Number(0);
578 s.add(a);
579 var b = new Number(1);
580 s.add(b);
581 var c = new Number(2);
582 s.add(c);
583 var d = new Number(3);
584 s.add(d);
585
586 var b = goog.structs.every(s, function(val, key, s2) {
587 assertUndefined(key);
588 assertEquals(s, s2);
589 return val >= 0;
590 });
591 assertTrue(b);
592 b = goog.structs.every(s, function(val, key, s2) {
593 assertUndefined(key);
594 assertEquals(s, s2);
595 return val > 1;
596 });
597 assertFalse(b);
598
599 s = new Set;
600 s.add(0);
601 s.add(1);
602 s.add(2);
603 s.add(3);
604
605 b = goog.structs.every(s, function(val, key, s2) {
606 assertUndefined(key);
607 assertEquals(s, s2);
608 return val >= 0;
609 });
610 assertTrue(b);
611 b = goog.structs.every(s, function(val, key, s2) {
612 assertUndefined(key);
613 assertEquals(s, s2);
614 return val > 1;
615 });
616 assertFalse(b);
617 }
618
619 function testIterator() {
620 var s = new Set;
621 s.add(0);
622 s.add(1);
623 s.add(2);
624 s.add(3);
625 s.add(4);
626
627 assertEquals('01234', goog.iter.join(s, ''));
628
629 s.remove(1);
630 s.remove(3);
631
632 assertEquals('024', goog.iter.join(s, ''));
633 }