| OLD | NEW |
| (Empty) |
| 1 // Copyright (c) 2013, 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 part of dart.collection; | |
| 6 | |
| 7 /** Common parts of [HashSet] and [LinkedHashSet] implementations. */ | |
| 8 abstract class _HashSetBase<E> extends SetBase<E> { | |
| 9 | |
| 10 // The following two methods override the ones in SetBase. | |
| 11 // It's possible to be more efficient if we have a way to create an empty | |
| 12 // set of the correct type. | |
| 13 | |
| 14 Set<E> difference(Set<Object> other) { | |
| 15 Set<E> result = _newSet(); | |
| 16 for (var element in this) { | |
| 17 if (!other.contains(element)) result.add(element); | |
| 18 } | |
| 19 return result; | |
| 20 } | |
| 21 | |
| 22 Set<E> intersection(Set<Object> other) { | |
| 23 Set<E> result = _newSet(); | |
| 24 for (var element in this) { | |
| 25 if (other.contains(element)) result.add(element); | |
| 26 } | |
| 27 return result; | |
| 28 } | |
| 29 | |
| 30 Set<E> _newSet(); | |
| 31 | |
| 32 // Subclasses can optimize this further. | |
| 33 Set<E> toSet() => _newSet()..addAll(this); | |
| 34 } | |
| 35 | |
| 36 /** | |
| 37 * An unordered hash-table based [Set] implementation. | |
| 38 * | |
| 39 * The elements of a `HashSet` must have consistent equality | |
| 40 * and hashCode implementations. This means that the equals operation | |
| 41 * must define a stable equivalence relation on the elements (reflexive, | |
| 42 * symmetric, transitive, and consistent over time), and that the hashCode | |
| 43 * must consistent with equality, so that the same for objects that are | |
| 44 * considered equal. | |
| 45 * | |
| 46 * The set allows `null` as an element. | |
| 47 * | |
| 48 * Most simple operations on `HashSet` are done in (potentially amorteized) | |
| 49 * constant time: [add], [contains], [remove], and [length], provided the hash | |
| 50 * codes of objects are well distributed. | |
| 51 */ | |
| 52 abstract class HashSet<E> implements Set<E> { | |
| 53 /** | |
| 54 * Create a hash set using the provided [equals] as equality. | |
| 55 * | |
| 56 * The provided [equals] must define a stable equivalence relation, and | |
| 57 * [hashCode] must be consistent with [equals]. If the [equals] or [hashCode] | |
| 58 * methods won't work on all objects, but only to instances of E, the | |
| 59 * [isValidKey] predicate can be used to restrict the keys that they are | |
| 60 * applied to. Any key for which [isValidKey] returns false is automatically | |
| 61 * assumed to not be in the set. | |
| 62 * | |
| 63 * If [equals] or [hashCode] are omitted, the set uses | |
| 64 * the objects' intrinsic [Object.operator==] and [Object.hashCode]. | |
| 65 * | |
| 66 * If [isValidKey] is omitted, it defaults to testing if the object is an | |
| 67 * [E] instance. | |
| 68 * | |
| 69 * If you supply one of [equals] and [hashCode], | |
| 70 * you should generally also to supply the other. | |
| 71 * An example would be using [identical] and [identityHashCode], | |
| 72 * which is equivalent to using the shorthand [LinkedSet.identity]). | |
| 73 */ | |
| 74 factory HashSet({ bool equals(E e1, E e2), | |
| 75 int hashCode(E e), | |
| 76 bool isValidKey(Object potentialKey) }) { | |
| 77 if (isValidKey == null) { | |
| 78 if (hashCode == null) { | |
| 79 if (equals == null) { | |
| 80 return new _HashSet<E>(); | |
| 81 } | |
| 82 hashCode = _defaultHashCode; | |
| 83 } else { | |
| 84 if (identical(identityHashCode, hashCode) && | |
| 85 identical(identical, equals)) { | |
| 86 return new _IdentityHashSet<E>(); | |
| 87 } | |
| 88 if (equals == null) { | |
| 89 equals = _defaultEquals; | |
| 90 } | |
| 91 } | |
| 92 } else { | |
| 93 if (hashCode == null) { | |
| 94 hashCode = _defaultHashCode; | |
| 95 } | |
| 96 if (equals == null) { | |
| 97 equals = _defaultEquals; | |
| 98 } | |
| 99 } | |
| 100 return new _CustomHashSet<E>(equals, hashCode, isValidKey); | |
| 101 } | |
| 102 | |
| 103 /** | |
| 104 * Creates an unordered identity-based set. | |
| 105 * | |
| 106 * Effectively a shorthand for: | |
| 107 * | |
| 108 * new HashSet(equals: identical, hashCode: identityHashCodeOf) | |
| 109 */ | |
| 110 factory HashSet.identity() = _IdentityHashSet<E>; | |
| 111 | |
| 112 /** | |
| 113 * Create a hash set containing all [elements]. | |
| 114 * | |
| 115 * Creates a hash set as by `new HashSet<E>()` and adds each element of | |
| 116 * `elements` to this set in the order they are iterated. | |
| 117 * | |
| 118 * All the [elements] should be assignable to [E]. | |
| 119 * The `elements` iterable itself may have any element type, so this | |
| 120 * constructor can be used to down-cast a `Set`, for example as: | |
| 121 * | |
| 122 * Set<SuperType> superSet = ...; | |
| 123 * Set<SubType> subSet = | |
| 124 * new HashSet<SubType>.from(superSet.where((e) => e is SubType)); | |
| 125 */ | |
| 126 factory HashSet.from(Iterable elements) { | |
| 127 HashSet<E> result = new HashSet<E>(); | |
| 128 for (E e in elements) result.add(e); | |
| 129 return result; | |
| 130 } | |
| 131 | |
| 132 /** | |
| 133 * Provides an iterator that iterates over the elements of this set. | |
| 134 * | |
| 135 * The order of iteration is unspecified, | |
| 136 * but consistent between changes to the set. | |
| 137 */ | |
| 138 Iterator<E> get iterator; | |
| 139 } | |
| OLD | NEW |