OLD | NEW |
1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | 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 | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 library set_test; | 5 library set_test; |
6 | 6 |
7 | |
8 import 'package:expect/expect.dart'; | 7 import 'package:expect/expect.dart'; |
9 import "dart:collection"; | 8 import "dart:collection"; |
10 | 9 |
11 void testMain(Set create()) { | 10 void testMain(Set create()) { |
12 testInts(create); | 11 testInts(create); |
13 testStrings(create); | 12 testStrings(create); |
14 testInts(() => create().toSet()); | 13 testInts(() => create().toSet()); |
15 testStrings(() => create().toSet()); | 14 testStrings(() => create().toSet()); |
16 } | 15 } |
17 | 16 |
(...skipping 188 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
206 | 205 |
207 set2 = set.toSet()..clear(); | 206 set2 = set.toSet()..clear(); |
208 testLength(0, set2); | 207 testLength(0, set2); |
209 Expect.isTrue(set2.add(11)); | 208 Expect.isTrue(set2.add(11)); |
210 Expect.isTrue(set2.add(1)); | 209 Expect.isTrue(set2.add(1)); |
211 Expect.isTrue(set2.add(21)); | 210 Expect.isTrue(set2.add(21)); |
212 Expect.isTrue(set2.add(31)); | 211 Expect.isTrue(set2.add(31)); |
213 testLength(4, set2); | 212 testLength(4, set2); |
214 Expect.listEquals(set.toList(), set2.toList()); | 213 Expect.listEquals(set.toList(), set2.toList()); |
215 | 214 |
216 set2 = (set.toSet()..clear()).toSet(); // Cloning empty set shouldn't fail. | 215 set2 = (set.toSet()..clear()).toSet(); // Cloning empty set shouldn't fail. |
217 testLength(0, set2); | 216 testLength(0, set2); |
218 } | 217 } |
219 | 218 |
220 void testLength(int length, Set set) { | 219 void testLength(int length, Set set) { |
221 Expect.equals(length, set.length); | 220 Expect.equals(length, set.length); |
222 (length == 0 ? Expect.isTrue : Expect.isFalse)(set.isEmpty); | 221 (length == 0 ? Expect.isTrue : Expect.isFalse)(set.isEmpty); |
223 (length != 0 ? Expect.isTrue : Expect.isFalse)(set.isNotEmpty); | 222 (length != 0 ? Expect.isTrue : Expect.isFalse)(set.isNotEmpty); |
224 if (length == 0) { | 223 if (length == 0) { |
225 for (var e in set) { Expect.fail("contains element when iterated: $e"); } | 224 for (var e in set) { |
| 225 Expect.fail("contains element when iterated: $e"); |
| 226 } |
226 } | 227 } |
227 (length == 0 ? Expect.isFalse : Expect.isTrue)(set.iterator.moveNext()); | 228 (length == 0 ? Expect.isFalse : Expect.isTrue)(set.iterator.moveNext()); |
228 } | 229 } |
229 | 230 |
230 void testStrings(Set create()) { | 231 void testStrings(Set create()) { |
231 var set = create(); | 232 var set = create(); |
232 var strings = ["foo", "bar", "baz", "qux", "fisk", "hest", "svin", "pigvar"]; | 233 var strings = ["foo", "bar", "baz", "qux", "fisk", "hest", "svin", "pigvar"]; |
233 set.addAll(strings); | 234 set.addAll(strings); |
234 testLength(8, set); | 235 testLength(8, set); |
235 set.removeAll(strings.where((x) => x.length == 3)); | 236 set.removeAll(strings.where((x) => x.length == 3)); |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
274 // It must not throw away equal elements that are different in the | 275 // It must not throw away equal elements that are different in the |
275 // equality of the set. | 276 // equality of the set. |
276 // It must not consider objects to be not there if they are equal | 277 // It must not consider objects to be not there if they are equal |
277 // in the equality of the set. | 278 // in the equality of the set. |
278 | 279 |
279 // If set equality is natural equality, using different but equal objects | 280 // If set equality is natural equality, using different but equal objects |
280 // must work. Can't use an identity set internally (as was done at some point | 281 // must work. Can't use an identity set internally (as was done at some point |
281 // during development). | 282 // during development). |
282 Set set = create(); | 283 Set set = create(); |
283 set.addAll([new CE(0), new CE(1), new CE(2)]); | 284 set.addAll([new CE(0), new CE(1), new CE(2)]); |
284 Expect.equals(3, set.length); // All different. | 285 Expect.equals(3, set.length); // All different. |
285 set.retainAll([new CE(0), new CE(2)]); | 286 set.retainAll([new CE(0), new CE(2)]); |
286 Expect.equals(2, set.length); | 287 Expect.equals(2, set.length); |
287 Expect.isTrue(set.contains(new CE(0))); | 288 Expect.isTrue(set.contains(new CE(0))); |
288 Expect.isTrue(set.contains(new CE(2))); | 289 Expect.isTrue(set.contains(new CE(2))); |
289 | 290 |
290 // If equality of set is identity, we can't internally use a non-identity | 291 // If equality of set is identity, we can't internally use a non-identity |
291 // based set because it might throw away equal objects that are not identical. | 292 // based set because it might throw away equal objects that are not identical. |
292 var elems = [new CE(0), new CE(1), new CE(2), new CE(0)]; | 293 var elems = [new CE(0), new CE(1), new CE(2), new CE(0)]; |
293 set = create(identical, null, null, identityCompare); | 294 set = create(identical, null, null, identityCompare); |
294 set.addAll(elems); | 295 set.addAll(elems); |
(...skipping 23 matching lines...) Expand all Loading... |
318 Expect.isTrue(set.contains(new CE(6))); | 319 Expect.isTrue(set.contains(new CE(6))); |
319 Expect.isTrue(set.contains(new CE(8))); | 320 Expect.isTrue(set.contains(new CE(8))); |
320 } | 321 } |
321 | 322 |
322 void testDifferenceIntersection(create([equals, hashCode, validKey, compare])) { | 323 void testDifferenceIntersection(create([equals, hashCode, validKey, compare])) { |
323 // Test that elements of intersection comes from receiver set. | 324 // Test that elements of intersection comes from receiver set. |
324 CE ce1a = new CE(1); | 325 CE ce1a = new CE(1); |
325 CE ce1b = new CE(1); | 326 CE ce1b = new CE(1); |
326 CE ce2 = new CE(2); | 327 CE ce2 = new CE(2); |
327 CE ce3 = new CE(3); | 328 CE ce3 = new CE(3); |
328 Expect.equals(ce1a, ce1b); // Sanity check. | 329 Expect.equals(ce1a, ce1b); // Sanity check. |
329 | 330 |
330 var set1 = create(); | 331 var set1 = create(); |
331 var set2 = create(); | 332 var set2 = create(); |
332 set1.add(ce1a); | 333 set1.add(ce1a); |
333 set1.add(ce2); | 334 set1.add(ce2); |
334 set2.add(ce1b); | 335 set2.add(ce1b); |
335 set2.add(ce3); | 336 set2.add(ce3); |
336 | 337 |
337 var difference = set1.difference(set2); | 338 var difference = set1.difference(set2); |
338 testLength(1, difference); | 339 testLength(1, difference); |
339 Expect.identical(ce2, difference.lookup(ce2)); | 340 Expect.identical(ce2, difference.lookup(ce2)); |
340 | 341 |
341 difference = set2.difference(set1); | 342 difference = set2.difference(set1); |
342 testLength(1, difference); | 343 testLength(1, difference); |
343 Expect.identical(ce3, difference.lookup(ce3)); | 344 Expect.identical(ce3, difference.lookup(ce3)); |
344 | 345 |
345 // Difference uses other.contains to check for equality. | 346 // Difference uses other.contains to check for equality. |
346 var set3 = create(identical, identityHashCode, null, identityCompare); | 347 var set3 = create(identical, identityHashCode, null, identityCompare); |
347 set3.add(ce1b); | 348 set3.add(ce1b); |
348 difference = set1.difference(set3); | 349 difference = set1.difference(set3); |
349 testLength(2, difference); // ce1a is not identical to element in set3. | 350 testLength(2, difference); // ce1a is not identical to element in set3. |
350 Expect.identical(ce1a, difference.lookup(ce1a)); | 351 Expect.identical(ce1a, difference.lookup(ce1a)); |
351 Expect.identical(ce2, difference.lookup(ce2)); | 352 Expect.identical(ce2, difference.lookup(ce2)); |
352 | 353 |
353 // Intesection always takes elements from receiver set. | 354 // Intesection always takes elements from receiver set. |
354 var intersection = set1.intersection(set2); | 355 var intersection = set1.intersection(set2); |
355 testLength(1, intersection); | 356 testLength(1, intersection); |
356 Expect.identical(ce1a, intersection.lookup(ce1a)); | 357 Expect.identical(ce1a, intersection.lookup(ce1a)); |
357 | 358 |
358 intersection = set1.intersection(set3); | 359 intersection = set1.intersection(set3); |
359 testLength(0, intersection); | 360 testLength(0, intersection); |
360 } | 361 } |
361 | 362 |
362 // Objects that are equal based on data. | 363 // Objects that are equal based on data. |
363 class CE implements Comparable<CE> { | 364 class CE implements Comparable<CE> { |
364 final int id; | 365 final int id; |
365 const CE(this.id); | 366 const CE(this.id); |
366 int get hashCode => id; | 367 int get hashCode => id; |
367 bool operator==(Object other) => other is CE && id == (other as CE).id; | 368 bool operator ==(Object other) => other is CE && id == (other as CE).id; |
368 int compareTo(CE other) => id - other.id; | 369 int compareTo(CE other) => id - other.id; |
369 String toString() => "CE($id)"; | 370 String toString() => "CE($id)"; |
370 } | 371 } |
371 | 372 |
372 typedef int CECompare(CE e1, CE e2); | 373 typedef int CECompare(CE e1, CE e2); |
373 // Equality of Id objects based on id modulo value. | 374 // Equality of Id objects based on id modulo value. |
374 Function customEq(int mod) => (CE e1, CE e2) => ((e1.id - e2.id) % mod) == 0; | 375 Function customEq(int mod) => (CE e1, CE e2) => ((e1.id - e2.id) % mod) == 0; |
375 Function customHash(int mod) => (CE e) => e.id % mod; | 376 Function customHash(int mod) => (CE e) => e.id % mod; |
376 CECompare customCompare(int mod) => (CE e1, CE e2) => | 377 CECompare customCompare(int mod) => |
377 (e1.id % mod) - (e2.id % mod); | 378 (CE e1, CE e2) => (e1.id % mod) - (e2.id % mod); |
378 bool validKey(Object o) => o is CE; | 379 bool validKey(Object o) => o is CE; |
379 final customId = new Map<dynamic, dynamic>.identity(); | 380 final customId = new Map<dynamic, dynamic>.identity(); |
380 int counter = 0; | 381 int counter = 0; |
381 int identityCompare(e1, e2) { | 382 int identityCompare(e1, e2) { |
382 if (identical(e1, e2)) return 0; | 383 if (identical(e1, e2)) return 0; |
383 int i1 = customId.putIfAbsent(e1, () => ++counter); | 384 int i1 = customId.putIfAbsent(e1, () => ++counter); |
384 int i2 = customId.putIfAbsent(e2, () => ++counter); | 385 int i2 = customId.putIfAbsent(e2, () => ++counter); |
385 return i1 - i2; | 386 return i1 - i2; |
386 } | 387 } |
387 | 388 |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
421 | 422 |
422 Iterable<num> numIter = numList.where((x) => true); | 423 Iterable<num> numIter = numList.where((x) => true); |
423 Set<int> set3 = setFrom(numIter); | 424 Set<int> set3 = setFrom(numIter); |
424 Expect.listEquals(numList, set3.toList()..sort()); | 425 Expect.listEquals(numList, set3.toList()..sort()); |
425 | 426 |
426 Set<int> set4 = setFrom(new Iterable.generate(0)); | 427 Set<int> set4 = setFrom(new Iterable.generate(0)); |
427 Expect.isTrue(set4.isEmpty); | 428 Expect.isTrue(set4.isEmpty); |
428 } | 429 } |
429 | 430 |
430 void testCESetFrom(setFrom) { | 431 void testCESetFrom(setFrom) { |
431 var ceList = [new CE(2), new CE(3), new CE(5), | 432 var ceList = [ |
432 new CE(7), new CE(11), new CE(13)]; | 433 new CE(2), |
| 434 new CE(3), |
| 435 new CE(5), |
| 436 new CE(7), |
| 437 new CE(11), |
| 438 new CE(13) |
| 439 ]; |
433 | 440 |
434 Set<CE> set1 = setFrom(ceList); | 441 Set<CE> set1 = setFrom(ceList); |
435 Expect.listEquals(ceList, set1.toList()..sort()); | 442 Expect.listEquals(ceList, set1.toList()..sort()); |
436 | 443 |
437 Set<CE> ceSet = ceList.toSet(); | 444 Set<CE> ceSet = ceList.toSet(); |
438 Set<CE> set2 = setFrom(ceSet); | 445 Set<CE> set2 = setFrom(ceSet); |
439 Expect.listEquals(ceList, set2.toList()..sort()); | 446 Expect.listEquals(ceList, set2.toList()..sort()); |
440 | 447 |
441 Iterable<CE> ceIter = ceList.where((x) => true); | 448 Iterable<CE> ceIter = ceList.where((x) => true); |
442 Set<CE> set3 = setFrom(ceIter); | 449 Set<CE> set3 = setFrom(ceIter); |
443 Expect.listEquals(ceList, set3.toList()..sort()); | 450 Expect.listEquals(ceList, set3.toList()..sort()); |
444 | 451 |
445 Set<CE> set4 = setFrom(new Iterable.generate(0)); | 452 Set<CE> set4 = setFrom(new Iterable.generate(0)); |
446 Expect.isTrue(set4.isEmpty); | 453 Expect.isTrue(set4.isEmpty); |
447 } | 454 } |
448 | 455 |
449 class A {} | 456 class A {} |
| 457 |
450 class B {} | 458 class B {} |
| 459 |
451 class C implements A, B {} | 460 class C implements A, B {} |
452 | 461 |
453 void testASetFrom(setFrom) { | 462 void testASetFrom(setFrom) { |
454 List<B> bList= <B>[new C()]; | 463 List<B> bList = <B>[new C()]; |
455 // Set.from allows to cast elements. | 464 // Set.from allows to cast elements. |
456 Set<A> aSet = setFrom(bList); | 465 Set<A> aSet = setFrom(bList); |
457 Expect.isTrue(aSet.length == 1); | 466 Expect.isTrue(aSet.length == 1); |
458 } | 467 } |
459 | 468 |
460 main() { | 469 main() { |
461 testMain(() => new HashSet()); | 470 testMain(() => new HashSet()); |
462 testMain(() => new LinkedHashSet()); | 471 testMain(() => new LinkedHashSet()); |
463 testMain(() => new HashSet.identity()); | 472 testMain(() => new HashSet.identity()); |
464 testMain(() => new LinkedHashSet.identity()); | 473 testMain(() => new LinkedHashSet.identity()); |
465 testMain(() => new HashSet(equals: identical)); | 474 testMain(() => new HashSet(equals: identical)); |
466 testMain(() => new LinkedHashSet(equals: identical)); | 475 testMain(() => new LinkedHashSet(equals: identical)); |
467 testMain(() => new HashSet(equals: (a, b) => a == b, | 476 testMain(() => new HashSet( |
468 hashCode: (a) => -a.hashCode, | 477 equals: (a, b) => a == b, |
469 isValidKey: (a) => true)); | 478 hashCode: (a) => -a.hashCode, |
| 479 isValidKey: (a) => true)); |
470 testMain(() => new LinkedHashSet( | 480 testMain(() => new LinkedHashSet( |
471 equals: (a, b) => a == b, | 481 equals: (a, b) => a == b, |
472 hashCode: (a) => -a.hashCode, | 482 hashCode: (a) => -a.hashCode, |
473 isValidKey: (a) => true)); | 483 isValidKey: (a) => true)); |
474 testMain(() => new SplayTreeSet()); | 484 testMain(() => new SplayTreeSet()); |
475 | 485 |
476 testIdentity(() => new HashSet.identity()); | 486 testIdentity(() => new HashSet.identity()); |
477 testIdentity(() => new LinkedHashSet.identity()); | 487 testIdentity(() => new LinkedHashSet.identity()); |
478 testIdentity(() => new HashSet(equals: identical)); | 488 testIdentity(() => new HashSet(equals: identical)); |
479 testIdentity(() => new LinkedHashSet(equals: identical)); | 489 testIdentity(() => new LinkedHashSet(equals: identical)); |
480 testIdentity(() => new SplayTreeSet(identityCompare)); | 490 testIdentity(() => new SplayTreeSet(identityCompare)); |
481 | 491 |
482 testTypeAnnotations(new HashSet<int>()); | 492 testTypeAnnotations(new HashSet<int>()); |
483 testTypeAnnotations(new LinkedHashSet<int>()); | 493 testTypeAnnotations(new LinkedHashSet<int>()); |
484 testTypeAnnotations(new HashSet<int>(equals: identical)); | 494 testTypeAnnotations(new HashSet<int>(equals: identical)); |
485 testTypeAnnotations(new LinkedHashSet<int>(equals: identical)); | 495 testTypeAnnotations(new LinkedHashSet<int>(equals: identical)); |
486 testTypeAnnotations(new HashSet<int>(equals: (int a, int b) => a == b, | 496 testTypeAnnotations(new HashSet<int>( |
487 hashCode: (int a) => a.hashCode, | 497 equals: (int a, int b) => a == b, |
488 isValidKey: (a) => a is int)); | 498 hashCode: (int a) => a.hashCode, |
489 testTypeAnnotations(new LinkedHashSet<int>(equals: (int a, int b) => a == b, | 499 isValidKey: (a) => a is int)); |
490 hashCode: (int a) => a.hashCode, | 500 testTypeAnnotations(new LinkedHashSet<int>( |
491 isValidKey: (a) => a is int)); | 501 equals: (int a, int b) => a == b, |
| 502 hashCode: (int a) => a.hashCode, |
| 503 isValidKey: (a) => a is int)); |
492 testTypeAnnotations(new SplayTreeSet<int>()); | 504 testTypeAnnotations(new SplayTreeSet<int>()); |
493 | 505 |
494 testRetainWhere(([equals, hashCode, validKey, comparator]) => | 506 testRetainWhere(([equals, hashCode, validKey, comparator]) => |
495 new HashSet(equals: equals, hashCode: hashCode, isValidKey: validKey)); | 507 new HashSet(equals: equals, hashCode: hashCode, isValidKey: validKey)); |
496 testRetainWhere(([equals, hashCode, validKey, comparator]) => | 508 testRetainWhere(([equals, hashCode, validKey, comparator]) => |
497 new LinkedHashSet(equals: equals, hashCode: hashCode, | 509 new LinkedHashSet( |
498 isValidKey: validKey)); | 510 equals: equals, hashCode: hashCode, isValidKey: validKey)); |
499 testRetainWhere(([equals, hashCode, validKey, comparator]) => | 511 testRetainWhere(([equals, hashCode, validKey, comparator]) => |
500 new SplayTreeSet(comparator, validKey)); | 512 new SplayTreeSet(comparator, validKey)); |
501 | 513 |
502 testDifferenceIntersection(([equals, hashCode, validKey, comparator]) => | 514 testDifferenceIntersection(([equals, hashCode, validKey, comparator]) => |
503 new HashSet(equals: equals, hashCode: hashCode, isValidKey: validKey)); | 515 new HashSet(equals: equals, hashCode: hashCode, isValidKey: validKey)); |
504 testDifferenceIntersection(([equals, hashCode, validKey, comparator]) => | 516 testDifferenceIntersection(([equals, hashCode, validKey, comparator]) => |
505 new LinkedHashSet(equals: equals, hashCode: hashCode, | 517 new LinkedHashSet( |
506 isValidKey: validKey)); | 518 equals: equals, hashCode: hashCode, isValidKey: validKey)); |
507 testDifferenceIntersection(([equals, hashCode, validKey, comparator]) => | 519 testDifferenceIntersection(([equals, hashCode, validKey, comparator]) => |
508 new SplayTreeSet(comparator, validKey)); | 520 new SplayTreeSet(comparator, validKey)); |
509 | 521 |
510 testIntSetFrom((x) => new Set<int>.from(x)); | 522 testIntSetFrom((x) => new Set<int>.from(x)); |
511 testIntSetFrom((x) => new HashSet<int>.from(x)); | 523 testIntSetFrom((x) => new HashSet<int>.from(x)); |
512 testIntSetFrom((x) => new LinkedHashSet<int>.from(x)); | 524 testIntSetFrom((x) => new LinkedHashSet<int>.from(x)); |
513 testIntSetFrom((x) => new SplayTreeSet<int>.from(x)); | 525 testIntSetFrom((x) => new SplayTreeSet<int>.from(x)); |
514 | 526 |
515 testCESetFrom((x) => new Set<CE>.from(x)); | 527 testCESetFrom((x) => new Set<CE>.from(x)); |
516 testCESetFrom((x) => new HashSet<CE>.from(x)); | 528 testCESetFrom((x) => new HashSet<CE>.from(x)); |
517 testCESetFrom((x) => new LinkedHashSet<CE>.from(x)); | 529 testCESetFrom((x) => new LinkedHashSet<CE>.from(x)); |
518 testCESetFrom((x) => new SplayTreeSet<CE>.from(x)); | 530 testCESetFrom((x) => new SplayTreeSet<CE>.from(x)); |
519 | 531 |
520 testCESetFrom((x) => new SplayTreeSet<CE>.from(x, | 532 testCESetFrom( |
521 customCompare(20), validKey)); | 533 (x) => new SplayTreeSet<CE>.from(x, customCompare(20), validKey)); |
522 testCESetFrom((x) => new SplayTreeSet<CE>.from(x, identityCompare)); | 534 testCESetFrom((x) => new SplayTreeSet<CE>.from(x, identityCompare)); |
523 | 535 |
524 testASetFrom((x) => new Set<A>.from(x)); | 536 testASetFrom((x) => new Set<A>.from(x)); |
525 testASetFrom((x) => new HashSet<A>.from(x)); | 537 testASetFrom((x) => new HashSet<A>.from(x)); |
526 testASetFrom((x) => new LinkedHashSet<A>.from(x)); | 538 testASetFrom((x) => new LinkedHashSet<A>.from(x)); |
527 testASetFrom((x) => new SplayTreeSet<A>.from(x, identityCompare)); | 539 testASetFrom((x) => new SplayTreeSet<A>.from(x, identityCompare)); |
528 } | 540 } |
OLD | NEW |