| OLD | NEW |
| 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 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 | 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 /** | |
| 6 * Defines equality relations on collections. | |
| 7 */ | |
| 8 library dart.pkg.collection.equality; | |
| 9 | |
| 10 import "dart:collection"; | 5 import "dart:collection"; |
| 11 | 6 |
| 12 const int _HASH_MASK = 0x7fffffff; | 7 const int _HASH_MASK = 0x7fffffff; |
| 13 | 8 |
| 14 /** | 9 /// A generic equality relation on objects. |
| 15 * A generic equality relation on objects. | |
| 16 */ | |
| 17 abstract class Equality<E> { | 10 abstract class Equality<E> { |
| 18 const factory Equality() = DefaultEquality; | 11 const factory Equality() = DefaultEquality; |
| 19 | 12 |
| 20 /** | 13 /// Compare two elements for being equal. |
| 21 * Compare two elements for being equal. | 14 /// |
| 22 * | 15 /// This should be a proper equality relation. |
| 23 * This should be a proper equality relation. | |
| 24 */ | |
| 25 bool equals(E e1, E e2); | 16 bool equals(E e1, E e2); |
| 26 | 17 |
| 27 /** | 18 /// Get a hashcode of an element. |
| 28 * Get a hashcode of an element. | 19 /// |
| 29 * | 20 /// The hashcode should be compatible with [equals], so that if |
| 30 * The hashcode should be compatible with [equals], so that if | 21 /// `equals(a, b)` then `hash(a) == hash(b)`. |
| 31 * `equals(a, b)` then `hash(a) == hash(b)`. | |
| 32 */ | |
| 33 int hash(E e); | 22 int hash(E e); |
| 34 | 23 |
| 35 /** | 24 /// Test whether an object is a valid argument to [equals] and [hash]. |
| 36 * Test whether an object is a valid argument to [equals] and [hash]. | 25 /// |
| 37 * | 26 /// Some implementations may be restricted to only work on specific types |
| 38 * Some implementations may be restricted to only work on specific types | 27 /// of objects. |
| 39 * of objects. | |
| 40 */ | |
| 41 bool isValidKey(Object o); | 28 bool isValidKey(Object o); |
| 42 } | 29 } |
| 43 | 30 |
| 44 /** | 31 /// Equality of objects that compares only the natural equality of the objects. |
| 45 * Equality of objects that compares only the natural equality of the objects. | 32 /// |
| 46 * | 33 /// This equality uses the objects' own [Object.==] and [Object.hashCode] for |
| 47 * This equality uses the objects' own [Object.==] and [Object.hashCode] for | 34 /// the equality. |
| 48 * the equality. | |
| 49 */ | |
| 50 class DefaultEquality implements Equality { | 35 class DefaultEquality implements Equality { |
| 51 const DefaultEquality(); | 36 const DefaultEquality(); |
| 52 bool equals(Object e1, Object e2) => e1 == e2; | 37 bool equals(Object e1, Object e2) => e1 == e2; |
| 53 int hash(Object e) => e.hashCode; | 38 int hash(Object e) => e.hashCode; |
| 54 bool isValidKey(Object o) => true; | 39 bool isValidKey(Object o) => true; |
| 55 } | 40 } |
| 56 | 41 |
| 57 /** | 42 /// Equality of objects that compares only the identity of the objects. |
| 58 * Equality of objects that compares only the identity of the objects. | |
| 59 */ | |
| 60 class IdentityEquality implements Equality { | 43 class IdentityEquality implements Equality { |
| 61 const IdentityEquality(); | 44 const IdentityEquality(); |
| 62 bool equals(Object e1, Object e2) => identical(e1, e2); | 45 bool equals(Object e1, Object e2) => identical(e1, e2); |
| 63 int hash(Object e) => identityHashCode(e); | 46 int hash(Object e) => identityHashCode(e); |
| 64 bool isValidKey(Object o) => true; | 47 bool isValidKey(Object o) => true; |
| 65 } | 48 } |
| 66 | 49 |
| 67 /** | 50 /// Equality on iterables. |
| 68 * Equality on iterables. | 51 /// |
| 69 * | 52 /// Two iterables are equal if they have the same elements in the same order. |
| 70 * Two iterables are equal if they have the same elements in the same order. | |
| 71 */ | |
| 72 class IterableEquality<E> implements Equality<Iterable<E>> { | 53 class IterableEquality<E> implements Equality<Iterable<E>> { |
| 73 final Equality<E> _elementEquality; | 54 final Equality<E> _elementEquality; |
| 74 const IterableEquality([Equality<E> elementEquality = | 55 const IterableEquality([Equality<E> elementEquality = |
| 75 const DefaultEquality()]) | 56 const DefaultEquality()]) |
| 76 : _elementEquality = elementEquality; | 57 : _elementEquality = elementEquality; |
| 77 | 58 |
| 78 bool equals(Iterable<E> elements1, Iterable<E> elements2) { | 59 bool equals(Iterable<E> elements1, Iterable<E> elements2) { |
| 79 if (identical(elements1, elements2)) return true; | 60 if (identical(elements1, elements2)) return true; |
| 80 if (elements1 == null || elements2 == null) return false; | 61 if (elements1 == null || elements2 == null) return false; |
| 81 Iterator it1 = elements1.iterator; | 62 Iterator it1 = elements1.iterator; |
| (...skipping 17 matching lines...) Expand all Loading... |
| 99 } | 80 } |
| 100 hash = (hash + (hash << 3)) & _HASH_MASK; | 81 hash = (hash + (hash << 3)) & _HASH_MASK; |
| 101 hash ^= (hash >> 11); | 82 hash ^= (hash >> 11); |
| 102 hash = (hash + (hash << 15)) & _HASH_MASK; | 83 hash = (hash + (hash << 15)) & _HASH_MASK; |
| 103 return hash; | 84 return hash; |
| 104 } | 85 } |
| 105 | 86 |
| 106 bool isValidKey(Object o) => o is Iterable<E>; | 87 bool isValidKey(Object o) => o is Iterable<E>; |
| 107 } | 88 } |
| 108 | 89 |
| 109 /** | 90 /// Equality on lists. |
| 110 * Equality on lists. | 91 /// |
| 111 * | 92 /// Two lists are equal if they have the same length and their elements |
| 112 * Two lists are equal if they have the same length and their elements | 93 /// at each index are equal. |
| 113 * at each index are equal. | 94 /// |
| 114 * | 95 /// This is effectively the same as [IterableEquality] except that it |
| 115 * This is effectively the same as [IterableEquality] except that it | 96 /// accesses elements by index instead of through iteration. |
| 116 * accesses elements by index instead of through iteration. | |
| 117 */ | |
| 118 class ListEquality<E> implements Equality<List<E>> { | 97 class ListEquality<E> implements Equality<List<E>> { |
| 119 final Equality<E> _elementEquality; | 98 final Equality<E> _elementEquality; |
| 120 const ListEquality([Equality<E> elementEquality = const DefaultEquality()]) | 99 const ListEquality([Equality<E> elementEquality = const DefaultEquality()]) |
| 121 : _elementEquality = elementEquality; | 100 : _elementEquality = elementEquality; |
| 122 | 101 |
| 123 bool equals(List<E> e1, List<E> e2) { | 102 bool equals(List<E> e1, List<E> e2) { |
| 124 if (identical(e1, e2)) return true; | 103 if (identical(e1, e2)) return true; |
| 125 if (e1 == null || e2 == null) return false; | 104 if (e1 == null || e2 == null) return false; |
| 126 int length = e1.length; | 105 int length = e1.length; |
| 127 if (length != e2.length) return false; | 106 if (length != e2.length) return false; |
| (...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 186 int c = _elementEquality.hash(element); | 165 int c = _elementEquality.hash(element); |
| 187 hash = (hash + c) & _HASH_MASK; | 166 hash = (hash + c) & _HASH_MASK; |
| 188 } | 167 } |
| 189 hash = (hash + (hash << 3)) & _HASH_MASK; | 168 hash = (hash + (hash << 3)) & _HASH_MASK; |
| 190 hash ^= (hash >> 11); | 169 hash ^= (hash >> 11); |
| 191 hash = (hash + (hash << 15)) & _HASH_MASK; | 170 hash = (hash + (hash << 15)) & _HASH_MASK; |
| 192 return hash; | 171 return hash; |
| 193 } | 172 } |
| 194 } | 173 } |
| 195 | 174 |
| 196 /** | 175 /// Equality of the elements of two iterables without considering order. |
| 197 * Equality of the elements of two iterables without considering order. | 176 /// |
| 198 * | 177 /// Two iterables are considered equal if they have the same number of elements, |
| 199 * Two iterables are considered equal if they have the same number of elements, | 178 /// and the elements of one set can be paired with the elements |
| 200 * and the elements of one set can be paired with the elements | 179 /// of the other iterable, so that each pair are equal. |
| 201 * of the other iterable, so that each pair are equal. | |
| 202 */ | |
| 203 class UnorderedIterableEquality<E> extends _UnorderedEquality<E, Iterable<E>> { | 180 class UnorderedIterableEquality<E> extends _UnorderedEquality<E, Iterable<E>> { |
| 204 const UnorderedIterableEquality( | 181 const UnorderedIterableEquality( |
| 205 [Equality<E> elementEquality = const DefaultEquality()]) | 182 [Equality<E> elementEquality = const DefaultEquality()]) |
| 206 : super(elementEquality); | 183 : super(elementEquality); |
| 207 | 184 |
| 208 bool isValidKey(Object o) => o is Iterable<E>; | 185 bool isValidKey(Object o) => o is Iterable<E>; |
| 209 } | 186 } |
| 210 | 187 |
| 211 /** | 188 /// Equality of sets. |
| 212 * Equality of sets. | 189 /// |
| 213 * | 190 /// Two sets are considered equal if they have the same number of elements, |
| 214 * Two sets are considered equal if they have the same number of elements, | 191 /// and the elements of one set can be paired with the elements |
| 215 * and the elements of one set can be paired with the elements | 192 /// of the other set, so that each pair are equal. |
| 216 * of the other set, so that each pair are equal. | 193 /// |
| 217 * | 194 /// This equality behaves the same as [UnorderedIterableEquality] except that |
| 218 * This equality behaves the same as [UnorderedIterableEquality] except that | 195 /// it expects sets instead of iterables as arguments. |
| 219 * it expects sets instead of iterables as arguments. | |
| 220 */ | |
| 221 class SetEquality<E> extends _UnorderedEquality<E, Set<E>> { | 196 class SetEquality<E> extends _UnorderedEquality<E, Set<E>> { |
| 222 const SetEquality( | 197 const SetEquality( |
| 223 [Equality<E> elementEquality = const DefaultEquality()]) | 198 [Equality<E> elementEquality = const DefaultEquality()]) |
| 224 : super(elementEquality); | 199 : super(elementEquality); |
| 225 | 200 |
| 226 bool isValidKey(Object o) => o is Set<E>; | 201 bool isValidKey(Object o) => o is Set<E>; |
| 227 } | 202 } |
| 228 | 203 |
| 229 /** | 204 /// Internal class used by [MapEquality]. |
| 230 * Internal class used by [MapEquality]. | 205 /// |
| 231 * | 206 /// The class represents a map entry as a single object, |
| 232 * The class represents a map entry as a single object, | 207 /// using a combined hashCode and equality of the key and value. |
| 233 * using a combined hashCode and equality of the key and value. | |
| 234 */ | |
| 235 class _MapEntry { | 208 class _MapEntry { |
| 236 final MapEquality equality; | 209 final MapEquality equality; |
| 237 final key; | 210 final key; |
| 238 final value; | 211 final value; |
| 239 _MapEntry(this.equality, this.key, this.value); | 212 _MapEntry(this.equality, this.key, this.value); |
| 240 | 213 |
| 241 int get hashCode => | 214 int get hashCode => |
| 242 (3 * equality._keyEquality.hash(key) + | 215 (3 * equality._keyEquality.hash(key) + |
| 243 7 * equality._valueEquality.hash(value)) & _HASH_MASK; | 216 7 * equality._valueEquality.hash(value)) & _HASH_MASK; |
| 244 | 217 |
| 245 bool operator==(Object other) { | 218 bool operator==(Object other) { |
| 246 if (other is! _MapEntry) return false; | 219 if (other is! _MapEntry) return false; |
| 247 _MapEntry otherEntry = other; | 220 _MapEntry otherEntry = other; |
| 248 return equality._keyEquality.equals(key, otherEntry.key) && | 221 return equality._keyEquality.equals(key, otherEntry.key) && |
| 249 equality._valueEquality.equals(value, otherEntry.value); | 222 equality._valueEquality.equals(value, otherEntry.value); |
| 250 | 223 |
| 251 } | 224 } |
| 252 } | 225 } |
| 253 | 226 |
| 254 /** | 227 /// Equality on maps. |
| 255 * Equality on maps. | 228 /// |
| 256 * | 229 /// Two maps are equal if they have the same number of entries, and if the |
| 257 * Two maps are equal if they have the same number of entries, and if the | 230 /// entries of the two maps are pairwise equal on both key and value. |
| 258 * entries of the two maps are pairwise equal on both key and value. | |
| 259 */ | |
| 260 class MapEquality<K, V> implements Equality<Map<K, V>> { | 231 class MapEquality<K, V> implements Equality<Map<K, V>> { |
| 261 final Equality<K> _keyEquality; | 232 final Equality<K> _keyEquality; |
| 262 final Equality<V> _valueEquality; | 233 final Equality<V> _valueEquality; |
| 263 const MapEquality({ Equality<K> keys : const DefaultEquality(), | 234 const MapEquality({ Equality<K> keys : const DefaultEquality(), |
| 264 Equality<V> values : const DefaultEquality() }) | 235 Equality<V> values : const DefaultEquality() }) |
| 265 : _keyEquality = keys, _valueEquality = values; | 236 : _keyEquality = keys, _valueEquality = values; |
| 266 | 237 |
| 267 bool equals(Map<K, V> e1, Map<K, V> e2) { | 238 bool equals(Map<K, V> e1, Map<K, V> e2) { |
| 268 if (identical(e1, e2)) return true; | 239 if (identical(e1, e2)) return true; |
| 269 if (e1 == null || e2 == null) return false; | 240 if (e1 == null || e2 == null) return false; |
| (...skipping 24 matching lines...) Expand all Loading... |
| 294 } | 265 } |
| 295 hash = (hash + (hash << 3)) & _HASH_MASK; | 266 hash = (hash + (hash << 3)) & _HASH_MASK; |
| 296 hash ^= (hash >> 11); | 267 hash ^= (hash >> 11); |
| 297 hash = (hash + (hash << 15)) & _HASH_MASK; | 268 hash = (hash + (hash << 15)) & _HASH_MASK; |
| 298 return hash; | 269 return hash; |
| 299 } | 270 } |
| 300 | 271 |
| 301 bool isValidKey(Object o) => o is Map<K, V>; | 272 bool isValidKey(Object o) => o is Map<K, V>; |
| 302 } | 273 } |
| 303 | 274 |
| 304 /** | 275 /// Combines several equalities into a single equality. |
| 305 * Combines several equalities into a single equality. | 276 /// |
| 306 * | 277 /// Tries each equality in order, using [Equality.isValidKey], and returns |
| 307 * Tries each equality in order, using [Equality.isValidKey], and returns | 278 /// the result of the first equality that applies to the argument or arguments. |
| 308 * the result of the first equality that applies to the argument or arguments. | 279 /// |
| 309 * | 280 /// For `equals`, the first equality that matches the first argument is used, |
| 310 * For `equals`, the first equality that matches the first argument is used, | 281 /// and if the second argument of `equals` is not valid for that equality, |
| 311 * and if the second argument of `equals` is not valid for that equality, | 282 /// it returns false. |
| 312 * it returns false. | 283 /// |
| 313 * | 284 /// Because the equalities are tried in order, they should generally work on |
| 314 * Because the equalities are tried in order, they should generally work on | 285 /// disjoint types. Otherwise the multi-equality may give inconsistent results |
| 315 * disjoint types. Otherwise the multi-equality may give inconsistent results | 286 /// for `equals(e1, e2)` and `equals(e2, e1)`. This can happen if one equality |
| 316 * for `equals(e1, e2)` and `equals(e2, e1)`. This can happen if one equality | 287 /// considers only `e1` a valid key, and not `e2`, but an equality which is |
| 317 * considers only `e1` a valid key, and not `e2`, but an equality which is | 288 /// checked later, allows both. |
| 318 * checked later, allows both. | |
| 319 */ | |
| 320 class MultiEquality<E> implements Equality<E> { | 289 class MultiEquality<E> implements Equality<E> { |
| 321 final Iterable<Equality<E>> _equalities; | 290 final Iterable<Equality<E>> _equalities; |
| 322 | 291 |
| 323 const MultiEquality(Iterable<Equality<E>> equalities) | 292 const MultiEquality(Iterable<Equality<E>> equalities) |
| 324 : _equalities = equalities; | 293 : _equalities = equalities; |
| 325 | 294 |
| 326 bool equals(E e1, E e2) { | 295 bool equals(E e1, E e2) { |
| 327 for (Equality<E> eq in _equalities) { | 296 for (Equality<E> eq in _equalities) { |
| 328 if (eq.isValidKey(e1)) return eq.isValidKey(e2) && eq.equals(e1, e2); | 297 if (eq.isValidKey(e1)) return eq.isValidKey(e2) && eq.equals(e1, e2); |
| 329 } | 298 } |
| 330 return false; | 299 return false; |
| 331 } | 300 } |
| 332 | 301 |
| 333 int hash(E e) { | 302 int hash(E e) { |
| 334 for (Equality<E> eq in _equalities) { | 303 for (Equality<E> eq in _equalities) { |
| 335 if (eq.isValidKey(e)) return eq.hash(e); | 304 if (eq.isValidKey(e)) return eq.hash(e); |
| 336 } | 305 } |
| 337 return -1; | 306 return -1; |
| 338 } | 307 } |
| 339 | 308 |
| 340 bool isValidKey(Object o) { | 309 bool isValidKey(Object o) { |
| 341 for (Equality<E> eq in _equalities) { | 310 for (Equality<E> eq in _equalities) { |
| 342 if (eq.isValidKey(o)) return true; | 311 if (eq.isValidKey(o)) return true; |
| 343 } | 312 } |
| 344 return false; | 313 return false; |
| 345 } | 314 } |
| 346 } | 315 } |
| 347 | 316 |
| 348 /** | 317 /// Deep equality on collections. |
| 349 * Deep equality on collections. | 318 /// |
| 350 * | 319 /// Recognizes lists, sets, iterables and maps and compares their elements using |
| 351 * Recognizes lists, sets, iterables and maps and compares their elements using | 320 /// deep equality as well. |
| 352 * deep equality as well. | 321 /// |
| 353 * | 322 /// Non-iterable/map objects are compared using a configurable base equality. |
| 354 * Non-iterable/map objects are compared using a configurable base equality. | 323 /// |
| 355 * | 324 /// Works in one of two modes: ordered or unordered. |
| 356 * Works in one of two modes: ordered or unordered. | 325 /// |
| 357 * | 326 /// In ordered mode, lists and iterables are required to have equal elements |
| 358 * In ordered mode, lists and iterables are required to have equal elements | 327 /// in the same order. In unordered mode, the order of elements in iterables |
| 359 * in the same order. In unordered mode, the order of elements in iterables | 328 /// and lists are not important. |
| 360 * and lists are not important. | 329 /// |
| 361 * | 330 /// A list is only equal to another list, likewise for sets and maps. All other |
| 362 * A list is only equal to another list, likewise for sets and maps. All other | 331 /// iterables are compared as iterables only. |
| 363 * iterables are compared as iterables only. | |
| 364 */ | |
| 365 class DeepCollectionEquality implements Equality { | 332 class DeepCollectionEquality implements Equality { |
| 366 final Equality _base; | 333 final Equality _base; |
| 367 final bool _unordered; | 334 final bool _unordered; |
| 368 const DeepCollectionEquality([Equality base = const DefaultEquality()]) | 335 const DeepCollectionEquality([Equality base = const DefaultEquality()]) |
| 369 : _base = base, _unordered = false; | 336 : _base = base, _unordered = false; |
| 370 | 337 |
| 371 /** | 338 /// Creates a deep equality on collections where the order of lists and |
| 372 * Creates a deep equality on collections where the order of lists and | 339 /// iterables are not considered important. That is, lists and iterables are |
| 373 * iterables are not considered important. That is, lists and iterables are | 340 /// treated as unordered iterables. |
| 374 * treated as unordered iterables. | |
| 375 */ | |
| 376 const DeepCollectionEquality.unordered( | 341 const DeepCollectionEquality.unordered( |
| 377 [Equality base = const DefaultEquality()]) | 342 [Equality base = const DefaultEquality()]) |
| 378 : _base = base, _unordered = true; | 343 : _base = base, _unordered = true; |
| 379 | 344 |
| 380 bool equals(e1, e2) { | 345 bool equals(e1, e2) { |
| 381 if (e1 is Set) { | 346 if (e1 is Set) { |
| 382 if (e2 is! Set) return false; | 347 if (e2 is! Set) return false; |
| 383 return new SetEquality(this).equals(e1, e2); | 348 return new SetEquality(this).equals(e1, e2); |
| 384 } | 349 } |
| 385 if (e1 is Map) { | 350 if (e1 is Map) { |
| (...skipping 24 matching lines...) Expand all Loading... |
| 410 if (o is List) return new ListEquality(this).hash(o); | 375 if (o is List) return new ListEquality(this).hash(o); |
| 411 if (o is Iterable) return new IterableEquality(this).hash(o); | 376 if (o is Iterable) return new IterableEquality(this).hash(o); |
| 412 } else if (o is Iterable) { | 377 } else if (o is Iterable) { |
| 413 return new UnorderedIterableEquality(this).hash(o); | 378 return new UnorderedIterableEquality(this).hash(o); |
| 414 } | 379 } |
| 415 return _base.hash(o); | 380 return _base.hash(o); |
| 416 } | 381 } |
| 417 | 382 |
| 418 bool isValidKey(Object o) => o is Iterable || o is Map || _base.isValidKey(o); | 383 bool isValidKey(Object o) => o is Iterable || o is Map || _base.isValidKey(o); |
| 419 } | 384 } |
| OLD | NEW |