| 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 |