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.difference with non-element type. | |
169 Set diffSet = create()..addAll([0, 1, 2, 499, 999]); | |
170 Set<Object> objectSet = new Set<Object>(); | |
171 objectSet.add("foo"); | |
172 objectSet.add(499); | |
173 Set diffResult = diffSet.difference(objectSet); | |
174 Expect.equals(4, diffResult.length); | |
175 for (int value in [0, 1, 2, 999]) { | |
176 Expect.isTrue(diffResult.contains(value)); | |
177 } | |
178 | |
179 // Test Set.addAll. | |
180 List list = new List(10); | |
181 for (int i = 0; i < 10; i++) { | |
182 list[i] = i + 10; | |
183 } | |
184 set.addAll(list); | |
185 testLength(20, set); | |
186 for (int i = 0; i < 20; i++) { | |
187 Expect.isTrue(set.contains(i)); | |
188 } | |
189 | |
190 // Test Set.removeAll | |
191 set.removeAll(list); | |
192 testLength(10, set); | |
193 for (int i = 0; i < 10; i++) { | |
194 Expect.isTrue(set.contains(i)); | |
195 } | |
196 for (int i = 10; i < 20; i++) { | |
197 Expect.isFalse(set.contains(i)); | |
198 } | |
199 | |
200 // Test Set.clear. | |
201 set.clear(); | |
202 testLength(0, set); | |
203 Expect.isTrue(set.add(11)); | |
204 testLength(1, set); | |
205 | |
206 // Test Set.toSet. | |
207 set.add(1); | |
208 set.add(21); | |
209 testLength(3, set); | |
210 var set2 = set.toSet(); | |
211 testLength(3, set2); | |
212 Expect.listEquals(set.toList(), set2.toList()); | |
213 set.add(31); | |
214 testLength(4, set); | |
215 testLength(3, set2); | |
216 | |
217 set2 = set.toSet()..clear(); | |
218 testLength(0, set2); | |
219 Expect.isTrue(set2.add(11)); | |
220 Expect.isTrue(set2.add(1)); | |
221 Expect.isTrue(set2.add(21)); | |
222 Expect.isTrue(set2.add(31)); | |
223 testLength(4, set2); | |
224 Expect.listEquals(set.toList(), set2.toList()); | |
225 | |
226 set2 = (set.toSet()..clear()).toSet(); // Cloning empty set shouldn't fail. | |
227 testLength(0, set2); | |
228 } | |
229 | |
230 void testLength(int length, Set set) { | |
231 Expect.equals(length, set.length); | |
232 (length == 0 ? Expect.isTrue : Expect.isFalse)(set.isEmpty); | |
233 (length != 0 ? Expect.isTrue : Expect.isFalse)(set.isNotEmpty); | |
234 if (length == 0) { | |
235 for (var e in set) { | |
236 Expect.fail("contains element when iterated: $e"); | |
237 } | |
238 } | |
239 (length == 0 ? Expect.isFalse : Expect.isTrue)(set.iterator.moveNext()); | |
240 } | |
241 | |
242 void testStrings(Set create()) { | |
243 var set = create(); | |
244 var strings = ["foo", "bar", "baz", "qux", "fisk", "hest", "svin", "pigvar"]; | |
245 set.addAll(strings); | |
246 testLength(8, set); | |
247 set.removeAll(strings.where((x) => x.length == 3)); | |
248 testLength(4, set); | |
249 Expect.isTrue(set.add("bar")); | |
250 Expect.isTrue(set.add("qux")); | |
251 testLength(6, set); | |
252 set.addAll(strings); | |
253 testLength(8, set); | |
254 set.removeWhere((x) => x.length != 3); | |
255 testLength(4, set); | |
256 set.retainWhere((x) => x[1] == "a"); | |
257 testLength(2, set); | |
258 Expect.isTrue(set.containsAll(["baz", "bar"])); | |
259 | |
260 set = set.union(strings.where((x) => x.length != 3).toSet()); | |
261 testLength(6, set); | |
262 set = set.intersection(["qux", "baz", "fisk", "egern"].toSet()); | |
263 testLength(2, set); | |
264 Expect.isTrue(set.containsAll(["baz", "fisk"])); | |
265 } | |
266 | |
267 void testTypeAnnotations(Set<int> set) { | |
268 set.add(0); | |
269 set.add(999); | |
270 set.add(0x800000000); | |
271 set.add(0x20000000000000); | |
272 Expect.isFalse(set.contains("not an it")); | |
273 Expect.isFalse(set.remove("not an it")); | |
274 Expect.isFalse(set.containsAll(["Not an int", "Also no an int"])); | |
275 | |
276 testLength(4, set); | |
277 set.removeAll(["Not an int", 999, "Also no an int"]); | |
278 testLength(3, set); | |
279 set.retainAll(["Not an int", 0, "Also no an int"]); | |
280 testLength(1, set); | |
281 } | |
282 | |
283 void testRetainWhere(Set create([equals, hashCode, validKey, compare])) { | |
284 // The retainWhere method must not collapse the argument Iterable | |
285 // in a way that doesn't match the equality of the set. | |
286 // It must not throw away equal elements that are different in the | |
287 // equality of the set. | |
288 // It must not consider objects to be not there if they are equal | |
289 // in the equality of the set. | |
290 | |
291 // If set equality is natural equality, using different but equal objects | |
292 // must work. Can't use an identity set internally (as was done at some point | |
293 // during development). | |
294 Set set = create(); | |
295 set.addAll([new CE(0), new CE(1), new CE(2)]); | |
296 Expect.equals(3, set.length); // All different. | |
297 set.retainAll([new CE(0), new CE(2)]); | |
298 Expect.equals(2, set.length); | |
299 Expect.isTrue(set.contains(new CE(0))); | |
300 Expect.isTrue(set.contains(new CE(2))); | |
301 | |
302 // If equality of set is identity, we can't internally use a non-identity | |
303 // based set because it might throw away equal objects that are not identical. | |
304 var elems = [new CE(0), new CE(1), new CE(2), new CE(0)]; | |
305 set = create(identical, null, null, identityCompare); | |
306 set.addAll(elems); | |
307 Expect.equals(4, set.length); | |
308 set.retainAll([elems[0], elems[2], elems[3]]); | |
309 Expect.equals(3, set.length); | |
310 Expect.isTrue(set.contains(elems[0])); | |
311 Expect.isTrue(set.contains(elems[2])); | |
312 Expect.isTrue(set.contains(elems[3])); | |
313 | |
314 // If set equality is less precise than equality, we must not use equality | |
315 // internally to see if the element is there: | |
316 set = create(customEq(3), customHash(3), validKey, customCompare(3)); | |
317 set.addAll([new CE(0), new CE(1), new CE(2)]); | |
318 Expect.equals(3, set.length); | |
319 set.retainAll([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 // It shouldn't matter if the input is a set. | |
325 set.clear(); | |
326 set.addAll([new CE(0), new CE(1), new CE(2)]); | |
327 Expect.equals(3, set.length); | |
328 set.retainAll(new Set.from([new CE(3), new CE(5)])); | |
329 Expect.equals(2, set.length); | |
330 Expect.isTrue(set.contains(new CE(6))); | |
331 Expect.isTrue(set.contains(new CE(8))); | |
332 } | |
333 | |
334 void testDifferenceIntersection(create([equals, hashCode, validKey, compare])) { | |
335 // Test that elements of intersection comes from receiver set. | |
336 CE ce1a = new CE(1); | |
337 CE ce1b = new CE(1); | |
338 CE ce2 = new CE(2); | |
339 CE ce3 = new CE(3); | |
340 Expect.equals(ce1a, ce1b); // Sanity check. | |
341 | |
342 var set1 = create(); | |
343 var set2 = create(); | |
344 set1.add(ce1a); | |
345 set1.add(ce2); | |
346 set2.add(ce1b); | |
347 set2.add(ce3); | |
348 | |
349 var difference = set1.difference(set2); | |
350 testLength(1, difference); | |
351 Expect.identical(ce2, difference.lookup(ce2)); | |
352 | |
353 difference = set2.difference(set1); | |
354 testLength(1, difference); | |
355 Expect.identical(ce3, difference.lookup(ce3)); | |
356 | |
357 // Difference uses other.contains to check for equality. | |
358 var set3 = create(identical, identityHashCode, null, identityCompare); | |
359 set3.add(ce1b); | |
360 difference = set1.difference(set3); | |
361 testLength(2, difference); // ce1a is not identical to element in set3. | |
362 Expect.identical(ce1a, difference.lookup(ce1a)); | |
363 Expect.identical(ce2, difference.lookup(ce2)); | |
364 | |
365 // Intersection always takes elements from receiver set. | |
366 var intersection = set1.intersection(set2); | |
367 testLength(1, intersection); | |
368 Expect.identical(ce1a, intersection.lookup(ce1a)); | |
369 | |
370 intersection = set1.intersection(set3); | |
371 testLength(0, intersection); | |
372 } | |
373 | |
374 // Objects that are equal based on data. | |
375 class CE implements Comparable<CE> { | |
376 final int id; | |
377 const CE(this.id); | |
378 int get hashCode => id; | |
379 bool operator ==(Object other) => other is CE && id == (other as CE).id; | |
380 int compareTo(CE other) => id - other.id; | |
381 String toString() => "CE($id)"; | |
382 } | |
383 | |
384 // Equality of Id objects based on id modulo value. | |
385 Function customEq(int mod) => (CE e1, CE e2) => ((e1.id - e2.id) % mod) == 0; | |
386 Function customHash(int mod) => (CE e) => e.id % mod; | |
387 Function customCompare(int mod) => | |
388 (CE e1, CE e2) => (e1.id % mod) - (e2.id % mod); | |
389 bool validKey(Object o) => o is CE; | |
390 final customId = new Map.identity(); | |
391 int counter = 0; | |
392 int identityCompare(e1, e2) { | |
393 if (identical(e1, e2)) return 0; | |
394 int i1 = customId.putIfAbsent(e1, () => ++counter); | |
395 int i2 = customId.putIfAbsent(e2, () => ++counter); | |
396 return i1 - i2; | |
397 } | |
398 | |
399 void testIdentity(Set create()) { | |
400 Set set = create(); | |
401 var e1 = new CE(0); | |
402 var e2 = new CE(0); | |
403 Expect.equals(e1, e2); | |
404 Expect.isFalse(identical(e1, e2)); | |
405 | |
406 testLength(0, set); | |
407 set.add(e1); | |
408 testLength(1, set); | |
409 Expect.isTrue(set.contains(e1)); | |
410 Expect.isFalse(set.contains(e2)); | |
411 | |
412 set.add(e2); | |
413 testLength(2, set); | |
414 Expect.isTrue(set.contains(e1)); | |
415 Expect.isTrue(set.contains(e2)); | |
416 | |
417 var set2 = set.toSet(); | |
418 testLength(2, set2); | |
419 Expect.isTrue(set2.contains(e1)); | |
420 Expect.isTrue(set2.contains(e2)); | |
421 } | |
422 | |
423 void testIntSetFrom(setFrom) { | |
424 List<num> numList = [2, 3, 5, 7, 11, 13]; | |
425 | |
426 Set<int> set1 = setFrom(numList); | |
427 Expect.listEquals(numList, set1.toList()..sort()); | |
428 | |
429 Set<num> numSet = numList.toSet(); | |
430 Set<int> set2 = setFrom(numSet); | |
431 Expect.listEquals(numList, set2.toList()..sort()); | |
432 | |
433 Iterable<num> numIter = numList.where((x) => true); | |
434 Set<int> set3 = setFrom(numIter); | |
435 Expect.listEquals(numList, set3.toList()..sort()); | |
436 | |
437 Set<int> set4 = setFrom(new Iterable.generate(0)); | |
438 Expect.isTrue(set4.isEmpty); | |
439 } | |
440 | |
441 void testCESetFrom(setFrom) { | |
442 List<Object> ceList = [ | |
443 new CE(2), | |
444 new CE(3), | |
445 new CE(5), | |
446 new CE(7), | |
447 new CE(11), | |
448 new CE(13) | |
449 ]; | |
450 | |
451 Set<CE> set1 = setFrom(ceList); | |
452 Expect.listEquals(ceList, set1.toList()..sort()); | |
453 | |
454 Set<CE> ceSet = ceList.toSet(); | |
455 Set<CE> set2 = setFrom(ceSet); | |
456 Expect.listEquals(ceList, set2.toList()..sort()); | |
457 | |
458 Iterable<CE> ceIter = ceList.where((x) => true); | |
459 Set<CE> set3 = setFrom(ceIter); | |
460 Expect.listEquals(ceList, set3.toList()..sort()); | |
461 | |
462 Set<CE> set4 = setFrom(new Iterable.generate(0)); | |
463 Expect.isTrue(set4.isEmpty); | |
464 } | |
465 | |
466 class A {} | |
467 | |
468 class B {} | |
469 | |
470 class C implements A, B {} | |
471 | |
472 void testASetFrom(setFrom) { | |
473 List<B> bList = <B>[new C()]; | |
474 // Set.from allows to cast elements. | |
475 Set<A> aSet = setFrom(bList); | |
476 Expect.isTrue(aSet.length == 1); | |
477 } | |
478 | |
479 main() { | |
480 testMain(() => new HashSet()); | |
481 testMain(() => new LinkedHashSet()); | |
482 testMain(() => new HashSet.identity()); | |
483 testMain(() => new LinkedHashSet.identity()); | |
484 testMain(() => new HashSet(equals: identical)); | |
485 testMain(() => new LinkedHashSet(equals: identical)); | |
486 testMain(() => new HashSet( | |
487 equals: (a, b) => a == b, | |
488 hashCode: (a) => -a.hashCode, | |
489 isValidKey: (a) => true)); | |
490 testMain(() => new LinkedHashSet( | |
491 equals: (a, b) => a == b, | |
492 hashCode: (a) => -a.hashCode, | |
493 isValidKey: (a) => true)); | |
494 testMain(() => new SplayTreeSet()); | |
495 | |
496 testIdentity(() => new HashSet.identity()); | |
497 testIdentity(() => new LinkedHashSet.identity()); | |
498 testIdentity(() => new HashSet(equals: identical)); | |
499 testIdentity(() => new LinkedHashSet(equals: identical)); | |
500 testIdentity(() => new SplayTreeSet(identityCompare)); | |
501 | |
502 testTypeAnnotations(new HashSet<int>()); | |
503 testTypeAnnotations(new LinkedHashSet<int>()); | |
504 testTypeAnnotations(new HashSet<int>(equals: identical)); | |
505 testTypeAnnotations(new LinkedHashSet<int>(equals: identical)); | |
506 testTypeAnnotations(new HashSet<int>( | |
507 equals: (int a, int b) => a == b, | |
508 hashCode: (int a) => a.hashCode, | |
509 isValidKey: (a) => a is int)); | |
510 testTypeAnnotations(new LinkedHashSet<int>( | |
511 equals: (int a, int b) => a == b, | |
512 hashCode: (int a) => a.hashCode, | |
513 isValidKey: (a) => a is int)); | |
514 testTypeAnnotations(new SplayTreeSet<int>()); | |
515 | |
516 testRetainWhere(([equals, hashCode, validKey, comparator]) => | |
517 new HashSet(equals: equals, hashCode: hashCode, isValidKey: validKey)); | |
518 testRetainWhere(([equals, hashCode, validKey, comparator]) => | |
519 new LinkedHashSet( | |
520 equals: equals, hashCode: hashCode, isValidKey: validKey)); | |
521 testRetainWhere(([equals, hashCode, validKey, comparator]) => | |
522 new SplayTreeSet(comparator, validKey)); | |
523 | |
524 testDifferenceIntersection(([equals, hashCode, validKey, comparator]) => | |
525 new HashSet(equals: equals, hashCode: hashCode, isValidKey: validKey)); | |
526 testDifferenceIntersection(([equals, hashCode, validKey, comparator]) => | |
527 new LinkedHashSet( | |
528 equals: equals, hashCode: hashCode, isValidKey: validKey)); | |
529 testDifferenceIntersection(([equals, hashCode, validKey, comparator]) => | |
530 new SplayTreeSet(comparator, validKey)); | |
531 | |
532 testIntSetFrom((x) => new Set<int>.from(x)); | |
533 testIntSetFrom((x) => new HashSet<int>.from(x)); | |
534 testIntSetFrom((x) => new LinkedHashSet<int>.from(x)); | |
535 testIntSetFrom((x) => new SplayTreeSet<int>.from(x)); | |
536 | |
537 testCESetFrom((x) => new Set<CE>.from(x)); | |
538 testCESetFrom((x) => new HashSet<CE>.from(x)); | |
539 testCESetFrom((x) => new LinkedHashSet<CE>.from(x)); | |
540 testCESetFrom((x) => new SplayTreeSet<CE>.from(x)); | |
541 | |
542 testCESetFrom( | |
543 (x) => new SplayTreeSet<CE>.from(x, customCompare(20), validKey)); | |
544 testCESetFrom((x) => new SplayTreeSet<CE>.from(x, identityCompare)); | |
545 | |
546 testASetFrom((x) => new Set<A>.from(x)); | |
547 testASetFrom((x) => new HashSet<A>.from(x)); | |
548 testASetFrom((x) => new LinkedHashSet<A>.from(x)); | |
549 testASetFrom((x) => new SplayTreeSet<A>.from(x, identityCompare)); | |
550 } | |
OLD | NEW |