OLD | NEW |
| (Empty) |
1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | |
2 // for details. All rights reserved. Use of this source code is governed by a | |
3 // BSD-style license that can be found in the LICENSE file. | |
4 | |
5 library set_test; | |
6 | |
7 import 'package:expect/expect.dart'; | |
8 import "dart:collection"; | |
9 | |
10 void testMain(Set create()) { | |
11 testInts(create); | |
12 testStrings(create); | |
13 testInts(() => create().toSet()); | |
14 testStrings(() => create().toSet()); | |
15 } | |
16 | |
17 void testInts(Set create()) { | |
18 Set set = create(); | |
19 | |
20 testLength(0, set); | |
21 Expect.isTrue(set.add(1)); | |
22 testLength(1, set); | |
23 Expect.isTrue(set.contains(1)); | |
24 | |
25 Expect.isFalse(set.add(1)); | |
26 testLength(1, set); | |
27 Expect.isTrue(set.contains(1)); | |
28 | |
29 Expect.isTrue(set.remove(1)); | |
30 testLength(0, set); | |
31 Expect.isFalse(set.contains(1)); | |
32 | |
33 Expect.isFalse(set.remove(1)); | |
34 testLength(0, set); | |
35 Expect.isFalse(set.contains(1)); | |
36 | |
37 for (int i = 0; i < 10; i++) { | |
38 set.add(i); | |
39 } | |
40 | |
41 testLength(10, set); | |
42 for (int i = 0; i < 10; i++) { | |
43 Expect.isTrue(set.contains(i)); | |
44 } | |
45 | |
46 testLength(10, set); | |
47 | |
48 for (int i = 10; i < 20; i++) { | |
49 Expect.isFalse(set.contains(i)); | |
50 } | |
51 | |
52 // Test Set.forEach. | |
53 int sum = 0; | |
54 testForEach(int val) { | |
55 sum += (val + 1); | |
56 } | |
57 | |
58 set.forEach(testForEach); | |
59 Expect.equals(10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1, sum); | |
60 | |
61 Expect.isTrue(set.containsAll(set)); | |
62 | |
63 // Test Set.map. | |
64 testMap(int val) { | |
65 return val * val; | |
66 } | |
67 | |
68 Set mapped = set.map(testMap).toSet(); | |
69 Expect.equals(10, mapped.length); | |
70 | |
71 Expect.isTrue(mapped.contains(0)); | |
72 Expect.isTrue(mapped.contains(1)); | |
73 Expect.isTrue(mapped.contains(4)); | |
74 Expect.isTrue(mapped.contains(9)); | |
75 Expect.isTrue(mapped.contains(16)); | |
76 Expect.isTrue(mapped.contains(25)); | |
77 Expect.isTrue(mapped.contains(36)); | |
78 Expect.isTrue(mapped.contains(49)); | |
79 Expect.isTrue(mapped.contains(64)); | |
80 Expect.isTrue(mapped.contains(81)); | |
81 | |
82 sum = 0; | |
83 set.forEach(testForEach); | |
84 Expect.equals(10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1, sum); | |
85 | |
86 sum = 0; | |
87 | |
88 mapped.forEach(testForEach); | |
89 Expect.equals(1 + 2 + 5 + 10 + 17 + 26 + 37 + 50 + 65 + 82, sum); | |
90 | |
91 // Test Set.filter. | |
92 testFilter(int val) { | |
93 return val.isEven; | |
94 } | |
95 | |
96 Set filtered = set.where(testFilter).toSet(); | |
97 | |
98 Expect.equals(5, filtered.length); | |
99 | |
100 Expect.isTrue(filtered.contains(0)); | |
101 Expect.isTrue(filtered.contains(2)); | |
102 Expect.isTrue(filtered.contains(4)); | |
103 Expect.isTrue(filtered.contains(6)); | |
104 Expect.isTrue(filtered.contains(8)); | |
105 | |
106 sum = 0; | |
107 filtered.forEach(testForEach); | |
108 Expect.equals(1 + 3 + 5 + 7 + 9, sum); | |
109 | |
110 Expect.isTrue(set.containsAll(filtered)); | |
111 | |
112 // Test Set.every. | |
113 testEvery(int val) { | |
114 return (val < 10); | |
115 } | |
116 | |
117 Expect.isTrue(set.every(testEvery)); | |
118 Expect.isTrue(filtered.every(testEvery)); | |
119 | |
120 filtered.add(10); | |
121 Expect.isFalse(filtered.every(testEvery)); | |
122 | |
123 // Test Set.some. | |
124 testSome(int val) { | |
125 return (val == 4); | |
126 } | |
127 | |
128 Expect.isTrue(set.any(testSome)); | |
129 Expect.isTrue(filtered.any(testSome)); | |
130 filtered.remove(4); | |
131 Expect.isFalse(filtered.any(testSome)); | |
132 | |
133 // Test Set.intersection. | |
134 Set intersection = set.intersection(filtered); | |
135 Expect.isTrue(set.contains(0)); | |
136 Expect.isTrue(set.contains(2)); | |
137 Expect.isTrue(set.contains(6)); | |
138 Expect.isTrue(set.contains(8)); | |
139 Expect.isFalse(intersection.contains(1)); | |
140 Expect.isFalse(intersection.contains(3)); | |
141 Expect.isFalse(intersection.contains(4)); | |
142 Expect.isFalse(intersection.contains(5)); | |
143 Expect.isFalse(intersection.contains(7)); | |
144 Expect.isFalse(intersection.contains(9)); | |
145 Expect.isFalse(intersection.contains(10)); | |
146 Expect.equals(4, intersection.length); | |
147 | |
148 Expect.isTrue(set.containsAll(intersection)); | |
149 Expect.isTrue(filtered.containsAll(intersection)); | |
150 | |
151 // Test Set.union. | |
152 Set twice = create()..addAll([0, 2, 4, 6, 8, 10, 12, 14]); | |
153 Set thrice = create()..addAll([0, 3, 6, 9, 12, 15]); | |
154 Set union = twice.union(thrice); | |
155 Expect.equals(11, union.length); | |
156 for (int i = 0; i < 16; i++) { | |
157 Expect.equals(i.isEven || (i % 3) == 0, union.contains(i)); | |
158 } | |
159 | |
160 // Test Set.difference. | |
161 Set difference = twice.difference(thrice); | |
162 Expect.equals(5, difference.length); | |
163 for (int i = 0; i < 16; i++) { | |
164 Expect.equals(i.isEven && (i % 3) != 0, difference.contains(i)); | |
165 } | |
166 Expect.isTrue(twice.difference(thrice).difference(twice).isEmpty); | |
167 | |
168 // Test Set.addAll. | |
169 List list = new List(10); | |
170 for (int i = 0; i < 10; i++) { | |
171 list[i] = i + 10; | |
172 } | |
173 set.addAll(list); | |
174 testLength(20, set); | |
175 for (int i = 0; i < 20; i++) { | |
176 Expect.isTrue(set.contains(i)); | |
177 } | |
178 | |
179 // Test Set.removeAll | |
180 set.removeAll(list); | |
181 testLength(10, set); | |
182 for (int i = 0; i < 10; i++) { | |
183 Expect.isTrue(set.contains(i)); | |
184 } | |
185 for (int i = 10; i < 20; i++) { | |
186 Expect.isFalse(set.contains(i)); | |
187 } | |
188 | |
189 // Test Set.clear. | |
190 set.clear(); | |
191 testLength(0, set); | |
192 Expect.isTrue(set.add(11)); | |
193 testLength(1, set); | |
194 | |
195 // Test Set.toSet. | |
196 set.add(1); | |
197 set.add(21); | |
198 testLength(3, set); | |
199 var set2 = set.toSet(); | |
200 testLength(3, set2); | |
201 Expect.listEquals(set.toList(), set2.toList()); | |
202 set.add(31); | |
203 testLength(4, set); | |
204 testLength(3, set2); | |
205 | |
206 set2 = set.toSet()..clear(); | |
207 testLength(0, set2); | |
208 Expect.isTrue(set2.add(11)); | |
209 Expect.isTrue(set2.add(1)); | |
210 Expect.isTrue(set2.add(21)); | |
211 Expect.isTrue(set2.add(31)); | |
212 testLength(4, set2); | |
213 Expect.listEquals(set.toList(), set2.toList()); | |
214 | |
215 set2 = (set.toSet()..clear()).toSet(); // Cloning empty set shouldn't fail. | |
216 testLength(0, set2); | |
217 } | |
218 | |
219 void testLength(int length, Set set) { | |
220 Expect.equals(length, set.length); | |
221 (length == 0 ? Expect.isTrue : Expect.isFalse)(set.isEmpty); | |
222 (length != 0 ? Expect.isTrue : Expect.isFalse)(set.isNotEmpty); | |
223 if (length == 0) { | |
224 for (var e in set) { | |
225 Expect.fail("contains element when iterated: $e"); | |
226 } | |
227 } | |
228 (length == 0 ? Expect.isFalse : Expect.isTrue)(set.iterator.moveNext()); | |
229 } | |
230 | |
231 void testStrings(Set create()) { | |
232 var set = create(); | |
233 var strings = ["foo", "bar", "baz", "qux", "fisk", "hest", "svin", "pigvar"]; | |
234 set.addAll(strings); | |
235 testLength(8, set); | |
236 set.removeAll(strings.where((x) => x.length == 3)); | |
237 testLength(4, set); | |
238 Expect.isTrue(set.add("bar")); | |
239 Expect.isTrue(set.add("qux")); | |
240 testLength(6, set); | |
241 set.addAll(strings); | |
242 testLength(8, set); | |
243 set.removeWhere((x) => x.length != 3); | |
244 testLength(4, set); | |
245 set.retainWhere((x) => x[1] == "a"); | |
246 testLength(2, set); | |
247 Expect.isTrue(set.containsAll(["baz", "bar"])); | |
248 | |
249 set = set.union(strings.where((x) => x.length != 3).toSet()); | |
250 testLength(6, set); | |
251 set = set.intersection(["qux", "baz", "fisk", "egern"].toSet()); | |
252 testLength(2, set); | |
253 Expect.isTrue(set.containsAll(["baz", "fisk"])); | |
254 } | |
255 | |
256 void testTypeAnnotations(Set<int> set) { | |
257 set.add(0); | |
258 set.add(999); | |
259 set.add(0x800000000); | |
260 set.add(0x20000000000000); | |
261 Expect.isFalse(set.contains("not an it")); | |
262 Expect.isFalse(set.remove("not an it")); | |
263 Expect.isFalse(set.containsAll(["Not an int", "Also no an int"])); | |
264 | |
265 testLength(4, set); | |
266 set.removeAll(["Not an int", 999, "Also no an int"]); | |
267 testLength(3, set); | |
268 set.retainAll(["Not an int", 0, "Also no an int"]); | |
269 testLength(1, set); | |
270 } | |
271 | |
272 void testRetainWhere( | |
273 Set<CE> create( | |
274 [CEEq equals, CEHash hashCode, ValidKey validKey, CECompare compare])) { | |
275 // The retainWhere method must not collapse the argument Iterable | |
276 // in a way that doesn't match the equality of the set. | |
277 // It must not throw away equal elements that are different in the | |
278 // equality of the set. | |
279 // It must not consider objects to be not there if they are equal | |
280 // in the equality of the set. | |
281 | |
282 // If set equality is natural equality, using different but equal objects | |
283 // must work. Can't use an identity set internally (as was done at some point | |
284 // during development). | |
285 var set = create(); | |
286 set.addAll([new CE(0), new CE(1), new CE(2)]); | |
287 Expect.equals(3, set.length); // All different. | |
288 set.retainAll([new CE(0), new CE(2)]); | |
289 Expect.equals(2, set.length); | |
290 Expect.isTrue(set.contains(new CE(0))); | |
291 Expect.isTrue(set.contains(new CE(2))); | |
292 | |
293 // If equality of set is identity, we can't internally use a non-identity | |
294 // based set because it might throw away equal objects that are not identical. | |
295 var elems = [new CE(0), new CE(1), new CE(2), new CE(0)]; | |
296 set = create(identical, null, null, identityCompare); | |
297 set.addAll(elems); | |
298 Expect.equals(4, set.length); | |
299 set.retainAll([elems[0], elems[2], elems[3]]); | |
300 Expect.equals(3, set.length); | |
301 Expect.isTrue(set.contains(elems[0])); | |
302 Expect.isTrue(set.contains(elems[2])); | |
303 Expect.isTrue(set.contains(elems[3])); | |
304 | |
305 // If set equality is less precise than equality, we must not use equality | |
306 // internally to see if the element is there: | |
307 set = create(customEq(3), customHash(3), validKey, customCompare(3)); | |
308 set.addAll([new CE(0), new CE(1), new CE(2)]); | |
309 Expect.equals(3, set.length); | |
310 set.retainAll([new CE(3), new CE(5)]); | |
311 Expect.equals(2, set.length); | |
312 Expect.isTrue(set.contains(new CE(6))); | |
313 Expect.isTrue(set.contains(new CE(8))); | |
314 | |
315 // It shouldn't matter if the input is a set. | |
316 set.clear(); | |
317 set.addAll([new CE(0), new CE(1), new CE(2)]); | |
318 Expect.equals(3, set.length); | |
319 set.retainAll(new Set.from([new CE(3), new CE(5)])); | |
320 Expect.equals(2, set.length); | |
321 Expect.isTrue(set.contains(new CE(6))); | |
322 Expect.isTrue(set.contains(new CE(8))); | |
323 } | |
324 | |
325 void testDifferenceIntersection(create([equals, hashCode, validKey, compare])) { | |
326 // Test that elements of intersection comes from receiver set. | |
327 CE ce1a = new CE(1); | |
328 CE ce1b = new CE(1); | |
329 CE ce2 = new CE(2); | |
330 CE ce3 = new CE(3); | |
331 Expect.equals(ce1a, ce1b); // Sanity check. | |
332 | |
333 var set1 = create(); | |
334 var set2 = create(); | |
335 set1.add(ce1a); | |
336 set1.add(ce2); | |
337 set2.add(ce1b); | |
338 set2.add(ce3); | |
339 | |
340 var difference = set1.difference(set2); | |
341 testLength(1, difference); | |
342 Expect.identical(ce2, difference.lookup(ce2)); | |
343 | |
344 difference = set2.difference(set1); | |
345 testLength(1, difference); | |
346 Expect.identical(ce3, difference.lookup(ce3)); | |
347 | |
348 // Difference uses other.contains to check for equality. | |
349 var set3 = create(identical, identityHashCode, null, identityCompare); | |
350 set3.add(ce1b); | |
351 difference = set1.difference(set3); | |
352 testLength(2, difference); // ce1a is not identical to element in set3. | |
353 Expect.identical(ce1a, difference.lookup(ce1a)); | |
354 Expect.identical(ce2, difference.lookup(ce2)); | |
355 | |
356 // Intersection always takes elements from receiver set. | |
357 var intersection = set1.intersection(set2); | |
358 testLength(1, intersection); | |
359 Expect.identical(ce1a, intersection.lookup(ce1a)); | |
360 | |
361 intersection = set1.intersection(set3); | |
362 testLength(0, intersection); | |
363 } | |
364 | |
365 // Objects that are equal based on data. | |
366 class CE implements Comparable<CE> { | |
367 final int id; | |
368 const CE(this.id); | |
369 int get hashCode => id; | |
370 bool operator ==(Object other) => other is CE && id == other.id; | |
371 int compareTo(CE other) => id - other.id; | |
372 String toString() => "CE($id)"; | |
373 } | |
374 | |
375 typedef int CECompare(CE e1, CE e2); | |
376 typedef int CEHash(CE e1); | |
377 typedef bool CEEq(CE e1, CE e2); | |
378 typedef bool ValidKey(Object o); | |
379 // Equality of Id objects based on id modulo value. | |
380 CEEq customEq(int mod) => (CE e1, CE e2) => ((e1.id - e2.id) % mod) == 0; | |
381 CEHash customHash(int mod) => (CE e) => e.id % mod; | |
382 CECompare customCompare(int mod) => | |
383 (CE e1, CE e2) => (e1.id % mod) - (e2.id % mod); | |
384 bool validKey(Object o) => o is CE; | |
385 final customId = new Map<dynamic, dynamic>.identity(); | |
386 int counter = 0; | |
387 int identityCompare(e1, e2) { | |
388 if (identical(e1, e2)) return 0; | |
389 int i1 = customId.putIfAbsent(e1, () => ++counter); | |
390 int i2 = customId.putIfAbsent(e2, () => ++counter); | |
391 return i1 - i2; | |
392 } | |
393 | |
394 void testIdentity(Set create()) { | |
395 Set set = create(); | |
396 var e1 = new CE(0); | |
397 var e2 = new CE(0); | |
398 Expect.equals(e1, e2); | |
399 Expect.isFalse(identical(e1, e2)); | |
400 | |
401 testLength(0, set); | |
402 set.add(e1); | |
403 testLength(1, set); | |
404 Expect.isTrue(set.contains(e1)); | |
405 Expect.isFalse(set.contains(e2)); | |
406 | |
407 set.add(e2); | |
408 testLength(2, set); | |
409 Expect.isTrue(set.contains(e1)); | |
410 Expect.isTrue(set.contains(e2)); | |
411 | |
412 var set2 = set.toSet(); | |
413 testLength(2, set2); | |
414 Expect.isTrue(set2.contains(e1)); | |
415 Expect.isTrue(set2.contains(e2)); | |
416 } | |
417 | |
418 void testIntSetFrom(setFrom) { | |
419 List<num> numList = [2, 3, 5, 7, 11, 13]; | |
420 | |
421 Set<int> set1 = setFrom(numList); | |
422 Expect.listEquals(numList, set1.toList()..sort()); | |
423 | |
424 Set<num> numSet = numList.toSet(); | |
425 Set<int> set2 = setFrom(numSet); | |
426 Expect.listEquals(numList, set2.toList()..sort()); | |
427 | |
428 Iterable<num> numIter = numList.where((x) => true); | |
429 Set<int> set3 = setFrom(numIter); | |
430 Expect.listEquals(numList, set3.toList()..sort()); | |
431 | |
432 Set<int> set4 = setFrom(new Iterable.generate(0)); | |
433 Expect.isTrue(set4.isEmpty); | |
434 } | |
435 | |
436 void testCESetFrom(setFrom) { | |
437 var ceList = [ | |
438 new CE(2), | |
439 new CE(3), | |
440 new CE(5), | |
441 new CE(7), | |
442 new CE(11), | |
443 new CE(13) | |
444 ]; | |
445 | |
446 Set<CE> set1 = setFrom(ceList); | |
447 Expect.listEquals(ceList, set1.toList()..sort()); | |
448 | |
449 Set<CE> ceSet = ceList.toSet(); | |
450 Set<CE> set2 = setFrom(ceSet); | |
451 Expect.listEquals(ceList, set2.toList()..sort()); | |
452 | |
453 Iterable<CE> ceIter = ceList.where((x) => true); | |
454 Set<CE> set3 = setFrom(ceIter); | |
455 Expect.listEquals(ceList, set3.toList()..sort()); | |
456 | |
457 Set<CE> set4 = setFrom(new Iterable.generate(0)); | |
458 Expect.isTrue(set4.isEmpty); | |
459 } | |
460 | |
461 class A {} | |
462 | |
463 class B {} | |
464 | |
465 class C implements A, B {} | |
466 | |
467 void testASetFrom(setFrom) { | |
468 List<B> bList = <B>[new C()]; | |
469 // Set.from allows to cast elements. | |
470 Set<A> aSet = setFrom(bList); | |
471 Expect.isTrue(aSet.length == 1); | |
472 } | |
473 | |
474 main() { | |
475 testMain(() => new HashSet()); | |
476 testMain(() => new LinkedHashSet()); | |
477 testMain(() => new HashSet.identity()); | |
478 testMain(() => new LinkedHashSet.identity()); | |
479 testMain(() => new HashSet(equals: identical)); | |
480 testMain(() => new LinkedHashSet(equals: identical)); | |
481 testMain(() => new HashSet( | |
482 equals: (a, b) => a == b, | |
483 hashCode: (a) => -a.hashCode, | |
484 isValidKey: (a) => true)); | |
485 testMain(() => new LinkedHashSet( | |
486 equals: (a, b) => a == b, | |
487 hashCode: (a) => -a.hashCode, | |
488 isValidKey: (a) => true)); | |
489 testMain(() => new SplayTreeSet()); | |
490 | |
491 testIdentity(() => new HashSet.identity()); | |
492 testIdentity(() => new LinkedHashSet.identity()); | |
493 testIdentity(() => new HashSet(equals: identical)); | |
494 testIdentity(() => new LinkedHashSet(equals: identical)); | |
495 testIdentity(() => new SplayTreeSet(identityCompare)); | |
496 | |
497 testTypeAnnotations(new HashSet<int>()); | |
498 testTypeAnnotations(new LinkedHashSet<int>()); | |
499 testTypeAnnotations(new HashSet<int>(equals: identical)); | |
500 testTypeAnnotations(new LinkedHashSet<int>(equals: identical)); | |
501 testTypeAnnotations(new HashSet<int>( | |
502 equals: (int a, int b) => a == b, | |
503 hashCode: (int a) => a.hashCode, | |
504 isValidKey: (a) => a is int)); | |
505 testTypeAnnotations(new LinkedHashSet<int>( | |
506 equals: (int a, int b) => a == b, | |
507 hashCode: (int a) => a.hashCode, | |
508 isValidKey: (a) => a is int)); | |
509 testTypeAnnotations(new SplayTreeSet<int>()); | |
510 | |
511 testRetainWhere(([equals, hashCode, validKey, comparator]) => | |
512 new HashSet(equals: equals, hashCode: hashCode, isValidKey: validKey)); | |
513 testRetainWhere(([equals, hashCode, validKey, comparator]) => | |
514 new LinkedHashSet( | |
515 equals: equals, hashCode: hashCode, isValidKey: validKey)); | |
516 testRetainWhere(([equals, hashCode, validKey, comparator]) => | |
517 new SplayTreeSet(comparator, validKey)); | |
518 | |
519 testDifferenceIntersection(([equals, hashCode, validKey, comparator]) => | |
520 new HashSet(equals: equals, hashCode: hashCode, isValidKey: validKey)); | |
521 testDifferenceIntersection(([equals, hashCode, validKey, comparator]) => | |
522 new LinkedHashSet( | |
523 equals: equals, hashCode: hashCode, isValidKey: validKey)); | |
524 testDifferenceIntersection(([equals, hashCode, validKey, comparator]) => | |
525 new SplayTreeSet(comparator, validKey)); | |
526 | |
527 testIntSetFrom((x) => new Set<int>.from(x)); | |
528 testIntSetFrom((x) => new HashSet<int>.from(x)); | |
529 testIntSetFrom((x) => new LinkedHashSet<int>.from(x)); | |
530 testIntSetFrom((x) => new SplayTreeSet<int>.from(x)); | |
531 | |
532 testCESetFrom((x) => new Set<CE>.from(x)); | |
533 testCESetFrom((x) => new HashSet<CE>.from(x)); | |
534 testCESetFrom((x) => new LinkedHashSet<CE>.from(x)); | |
535 testCESetFrom((x) => new SplayTreeSet<CE>.from(x)); | |
536 | |
537 testCESetFrom( | |
538 (x) => new SplayTreeSet<CE>.from(x, customCompare(20), validKey)); | |
539 testCESetFrom((x) => new SplayTreeSet<CE>.from(x, identityCompare)); | |
540 | |
541 testASetFrom((x) => new Set<A>.from(x)); | |
542 testASetFrom((x) => new HashSet<A>.from(x)); | |
543 testASetFrom((x) => new LinkedHashSet<A>.from(x)); | |
544 testASetFrom((x) => new SplayTreeSet<A>.from(x, identityCompare)); | |
545 } | |
OLD | NEW |