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 import "dart:collection"; |
| 6 |
| 7 import "comparators.dart"; |
| 8 |
| 9 const int _HASH_MASK = 0x7fffffff; |
| 10 |
| 11 /// A generic equality relation on objects. |
| 12 abstract class Equality<E> { |
| 13 const factory Equality() = DefaultEquality<E>; |
| 14 |
| 15 /// Compare two elements for being equal. |
| 16 /// |
| 17 /// This should be a proper equality relation. |
| 18 bool equals(E e1, E e2); |
| 19 |
| 20 /// Get a hashcode of an element. |
| 21 /// |
| 22 /// The hashcode should be compatible with [equals], so that if |
| 23 /// `equals(a, b)` then `hash(a) == hash(b)`. |
| 24 int hash(E e); |
| 25 |
| 26 /// Test whether an object is a valid argument to [equals] and [hash]. |
| 27 /// |
| 28 /// Some implementations may be restricted to only work on specific types |
| 29 /// of objects. |
| 30 bool isValidKey(Object o); |
| 31 } |
| 32 |
| 33 typedef F _GetKey<E, F>(E object); |
| 34 |
| 35 /// Equality of objects based on derived values. |
| 36 /// |
| 37 /// For example, given the class: |
| 38 /// ```dart |
| 39 /// abstract class Employee { |
| 40 /// int get employmentId; |
| 41 /// } |
| 42 /// ``` |
| 43 /// |
| 44 /// The following [Equality] considers employees with the same IDs to be equal: |
| 45 /// ```dart |
| 46 /// new EqualityBy((Employee e) => e.employmentId); |
| 47 /// ``` |
| 48 /// |
| 49 /// It's also possible to pass an additional equality instance that should be |
| 50 /// used to compare the value itself. |
| 51 class EqualityBy<E, F> implements Equality<E> { |
| 52 // Returns a derived value F from an object E. |
| 53 final _GetKey<E, F> _getKey; |
| 54 |
| 55 // Determines equality between two values of F. |
| 56 final Equality<F> _inner; |
| 57 |
| 58 EqualityBy(F getKey(E object), [Equality<F> inner = const DefaultEquality()]) |
| 59 : _getKey = getKey, |
| 60 _inner = inner; |
| 61 |
| 62 bool equals(E e1, E e2) => _inner.equals(_getKey(e1), _getKey(e2)); |
| 63 |
| 64 int hash(E e) => _inner.hash(_getKey(e)); |
| 65 |
| 66 bool isValidKey(Object o) { |
| 67 if (o is E) { |
| 68 final value = _getKey(o); |
| 69 return value is F && _inner.isValidKey(value); |
| 70 } |
| 71 return false; |
| 72 } |
| 73 } |
| 74 |
| 75 /// Equality of objects that compares only the natural equality of the objects. |
| 76 /// |
| 77 /// This equality uses the objects' own [Object.==] and [Object.hashCode] for |
| 78 /// the equality. |
| 79 class DefaultEquality<E> implements Equality<E> { |
| 80 const DefaultEquality(); |
| 81 bool equals(E e1, E e2) => e1 == e2; |
| 82 int hash(E e) => e.hashCode; |
| 83 bool isValidKey(Object o) => true; |
| 84 } |
| 85 |
| 86 /// Equality of objects that compares only the identity of the objects. |
| 87 class IdentityEquality<E> implements Equality<E> { |
| 88 const IdentityEquality(); |
| 89 bool equals(E e1, E e2) => identical(e1, e2); |
| 90 int hash(E e) => identityHashCode(e); |
| 91 bool isValidKey(Object o) => true; |
| 92 } |
| 93 |
| 94 /// Equality on iterables. |
| 95 /// |
| 96 /// Two iterables are equal if they have the same elements in the same order. |
| 97 /// |
| 98 /// The [equals] and [hash] methods accepts `null` values, |
| 99 /// even if the [isValidKey] returns `false` for `null`. |
| 100 /// The [hash] of `null` is `null.hashCode`. |
| 101 class IterableEquality<E> implements Equality<Iterable<E>> { |
| 102 final Equality<E> _elementEquality; |
| 103 const IterableEquality( |
| 104 [Equality<E> elementEquality = const DefaultEquality()]) |
| 105 : _elementEquality = elementEquality; |
| 106 |
| 107 bool equals(Iterable<E> elements1, Iterable<E> elements2) { |
| 108 if (identical(elements1, elements2)) return true; |
| 109 if (elements1 == null || elements2 == null) return false; |
| 110 var it1 = elements1.iterator; |
| 111 var it2 = elements2.iterator; |
| 112 while (true) { |
| 113 bool hasNext = it1.moveNext(); |
| 114 if (hasNext != it2.moveNext()) return false; |
| 115 if (!hasNext) return true; |
| 116 if (!_elementEquality.equals(it1.current, it2.current)) return false; |
| 117 } |
| 118 } |
| 119 |
| 120 int hash(Iterable<E> elements) { |
| 121 if (elements == null) return null.hashCode; |
| 122 // Jenkins's one-at-a-time hash function. |
| 123 int hash = 0; |
| 124 for (E element in elements) { |
| 125 int c = _elementEquality.hash(element); |
| 126 hash = (hash + c) & _HASH_MASK; |
| 127 hash = (hash + (hash << 10)) & _HASH_MASK; |
| 128 hash ^= (hash >> 6); |
| 129 } |
| 130 hash = (hash + (hash << 3)) & _HASH_MASK; |
| 131 hash ^= (hash >> 11); |
| 132 hash = (hash + (hash << 15)) & _HASH_MASK; |
| 133 return hash; |
| 134 } |
| 135 |
| 136 bool isValidKey(Object o) => o is Iterable<E>; |
| 137 } |
| 138 |
| 139 /// Equality on lists. |
| 140 /// |
| 141 /// Two lists are equal if they have the same length and their elements |
| 142 /// at each index are equal. |
| 143 /// |
| 144 /// This is effectively the same as [IterableEquality] except that it |
| 145 /// accesses elements by index instead of through iteration. |
| 146 /// |
| 147 /// The [equals] and [hash] methods accepts `null` values, |
| 148 /// even if the [isValidKey] returns `false` for `null`. |
| 149 /// The [hash] of `null` is `null.hashCode`. |
| 150 class ListEquality<E> implements Equality<List<E>> { |
| 151 final Equality<E> _elementEquality; |
| 152 const ListEquality([Equality<E> elementEquality = const DefaultEquality()]) |
| 153 : _elementEquality = elementEquality; |
| 154 |
| 155 bool equals(List<E> list1, List<E> list2) { |
| 156 if (identical(list1, list2)) return true; |
| 157 if (list1 == null || list2 == null) return false; |
| 158 int length = list1.length; |
| 159 if (length != list2.length) return false; |
| 160 for (int i = 0; i < length; i++) { |
| 161 if (!_elementEquality.equals(list1[i], list2[i])) return false; |
| 162 } |
| 163 return true; |
| 164 } |
| 165 |
| 166 int hash(List<E> list) { |
| 167 if (list == null) return null.hashCode; |
| 168 // Jenkins's one-at-a-time hash function. |
| 169 // This code is almost identical to the one in IterableEquality, except |
| 170 // that it uses indexing instead of iterating to get the elements. |
| 171 int hash = 0; |
| 172 for (int i = 0; i < list.length; i++) { |
| 173 int c = _elementEquality.hash(list[i]); |
| 174 hash = (hash + c) & _HASH_MASK; |
| 175 hash = (hash + (hash << 10)) & _HASH_MASK; |
| 176 hash ^= (hash >> 6); |
| 177 } |
| 178 hash = (hash + (hash << 3)) & _HASH_MASK; |
| 179 hash ^= (hash >> 11); |
| 180 hash = (hash + (hash << 15)) & _HASH_MASK; |
| 181 return hash; |
| 182 } |
| 183 |
| 184 bool isValidKey(Object o) => o is List<E>; |
| 185 } |
| 186 |
| 187 abstract class _UnorderedEquality<E, T extends Iterable<E>> |
| 188 implements Equality<T> { |
| 189 final Equality<E> _elementEquality; |
| 190 |
| 191 const _UnorderedEquality(this._elementEquality); |
| 192 |
| 193 bool equals(T elements1, T elements2) { |
| 194 if (identical(elements1, elements2)) return true; |
| 195 if (elements1 == null || elements2 == null) return false; |
| 196 HashMap<E, int> counts = new HashMap( |
| 197 equals: _elementEquality.equals, |
| 198 hashCode: _elementEquality.hash, |
| 199 isValidKey: _elementEquality.isValidKey); |
| 200 int length = 0; |
| 201 for (var e in elements1) { |
| 202 int count = counts[e]; |
| 203 if (count == null) count = 0; |
| 204 counts[e] = count + 1; |
| 205 length++; |
| 206 } |
| 207 for (var e in elements2) { |
| 208 int count = counts[e]; |
| 209 if (count == null || count == 0) return false; |
| 210 counts[e] = count - 1; |
| 211 length--; |
| 212 } |
| 213 return length == 0; |
| 214 } |
| 215 |
| 216 int hash(T elements) { |
| 217 if (elements == null) return null.hashCode; |
| 218 int hash = 0; |
| 219 for (E element in elements) { |
| 220 int c = _elementEquality.hash(element); |
| 221 hash = (hash + c) & _HASH_MASK; |
| 222 } |
| 223 hash = (hash + (hash << 3)) & _HASH_MASK; |
| 224 hash ^= (hash >> 11); |
| 225 hash = (hash + (hash << 15)) & _HASH_MASK; |
| 226 return hash; |
| 227 } |
| 228 } |
| 229 |
| 230 /// Equality of the elements of two iterables without considering order. |
| 231 /// |
| 232 /// Two iterables are considered equal if they have the same number of elements, |
| 233 /// and the elements of one set can be paired with the elements |
| 234 /// of the other iterable, so that each pair are equal. |
| 235 class UnorderedIterableEquality<E> extends _UnorderedEquality<E, Iterable<E>> { |
| 236 const UnorderedIterableEquality( |
| 237 [Equality<E> elementEquality = const DefaultEquality()]) |
| 238 : super(elementEquality); |
| 239 |
| 240 bool isValidKey(Object o) => o is Iterable<E>; |
| 241 } |
| 242 |
| 243 /// Equality of sets. |
| 244 /// |
| 245 /// Two sets are considered equal if they have the same number of elements, |
| 246 /// and the elements of one set can be paired with the elements |
| 247 /// of the other set, so that each pair are equal. |
| 248 /// |
| 249 /// This equality behaves the same as [UnorderedIterableEquality] except that |
| 250 /// it expects sets instead of iterables as arguments. |
| 251 /// |
| 252 /// The [equals] and [hash] methods accepts `null` values, |
| 253 /// even if the [isValidKey] returns `false` for `null`. |
| 254 /// The [hash] of `null` is `null.hashCode`. |
| 255 class SetEquality<E> extends _UnorderedEquality<E, Set<E>> { |
| 256 const SetEquality([Equality<E> elementEquality = const DefaultEquality()]) |
| 257 : super(elementEquality); |
| 258 |
| 259 bool isValidKey(Object o) => o is Set<E>; |
| 260 } |
| 261 |
| 262 /// Internal class used by [MapEquality]. |
| 263 /// |
| 264 /// The class represents a map entry as a single object, |
| 265 /// using a combined hashCode and equality of the key and value. |
| 266 class _MapEntry { |
| 267 final MapEquality equality; |
| 268 final key; |
| 269 final value; |
| 270 _MapEntry(this.equality, this.key, this.value); |
| 271 |
| 272 int get hashCode => |
| 273 (3 * equality._keyEquality.hash(key) + |
| 274 7 * equality._valueEquality.hash(value)) & |
| 275 _HASH_MASK; |
| 276 |
| 277 bool operator ==(Object other) { |
| 278 if (other is! _MapEntry) return false; |
| 279 _MapEntry otherEntry = other; |
| 280 return equality._keyEquality.equals(key, otherEntry.key) && |
| 281 equality._valueEquality.equals(value, otherEntry.value); |
| 282 } |
| 283 } |
| 284 |
| 285 /// Equality on maps. |
| 286 /// |
| 287 /// Two maps are equal if they have the same number of entries, and if the |
| 288 /// entries of the two maps are pairwise equal on both key and value. |
| 289 /// |
| 290 /// The [equals] and [hash] methods accepts `null` values, |
| 291 /// even if the [isValidKey] returns `false` for `null`. |
| 292 /// The [hash] of `null` is `null.hashCode`. |
| 293 class MapEquality<K, V> implements Equality<Map<K, V>> { |
| 294 final Equality<K> _keyEquality; |
| 295 final Equality<V> _valueEquality; |
| 296 const MapEquality( |
| 297 {Equality<K> keys: const DefaultEquality(), |
| 298 Equality<V> values: const DefaultEquality()}) |
| 299 : _keyEquality = keys, |
| 300 _valueEquality = values; |
| 301 |
| 302 bool equals(Map<K, V> map1, Map<K, V> map2) { |
| 303 if (identical(map1, map2)) return true; |
| 304 if (map1 == null || map2 == null) return false; |
| 305 int length = map1.length; |
| 306 if (length != map2.length) return false; |
| 307 Map<_MapEntry, int> equalElementCounts = new HashMap(); |
| 308 for (K key in map1.keys) { |
| 309 _MapEntry entry = new _MapEntry(this, key, map1[key]); |
| 310 int count = equalElementCounts[entry]; |
| 311 if (count == null) count = 0; |
| 312 equalElementCounts[entry] = count + 1; |
| 313 } |
| 314 for (K key in map2.keys) { |
| 315 _MapEntry entry = new _MapEntry(this, key, map2[key]); |
| 316 int count = equalElementCounts[entry]; |
| 317 if (count == null || count == 0) return false; |
| 318 equalElementCounts[entry] = count - 1; |
| 319 } |
| 320 return true; |
| 321 } |
| 322 |
| 323 int hash(Map<K, V> map) { |
| 324 if (map == null) return null.hashCode; |
| 325 int hash = 0; |
| 326 for (K key in map.keys) { |
| 327 int keyHash = _keyEquality.hash(key); |
| 328 int valueHash = _valueEquality.hash(map[key]); |
| 329 hash = (hash + 3 * keyHash + 7 * valueHash) & _HASH_MASK; |
| 330 } |
| 331 hash = (hash + (hash << 3)) & _HASH_MASK; |
| 332 hash ^= (hash >> 11); |
| 333 hash = (hash + (hash << 15)) & _HASH_MASK; |
| 334 return hash; |
| 335 } |
| 336 |
| 337 bool isValidKey(Object o) => o is Map<K, V>; |
| 338 } |
| 339 |
| 340 /// Combines several equalities into a single equality. |
| 341 /// |
| 342 /// Tries each equality in order, using [Equality.isValidKey], and returns |
| 343 /// the result of the first equality that applies to the argument or arguments. |
| 344 /// |
| 345 /// For `equals`, the first equality that matches the first argument is used, |
| 346 /// and if the second argument of `equals` is not valid for that equality, |
| 347 /// it returns false. |
| 348 /// |
| 349 /// Because the equalities are tried in order, they should generally work on |
| 350 /// disjoint types. Otherwise the multi-equality may give inconsistent results |
| 351 /// for `equals(e1, e2)` and `equals(e2, e1)`. This can happen if one equality |
| 352 /// considers only `e1` a valid key, and not `e2`, but an equality which is |
| 353 /// checked later, allows both. |
| 354 class MultiEquality<E> implements Equality<E> { |
| 355 final Iterable<Equality<E>> _equalities; |
| 356 |
| 357 const MultiEquality(Iterable<Equality<E>> equalities) |
| 358 : _equalities = equalities; |
| 359 |
| 360 bool equals(E e1, E e2) { |
| 361 for (Equality<E> eq in _equalities) { |
| 362 if (eq.isValidKey(e1)) return eq.isValidKey(e2) && eq.equals(e1, e2); |
| 363 } |
| 364 return false; |
| 365 } |
| 366 |
| 367 int hash(E e) { |
| 368 for (Equality<E> eq in _equalities) { |
| 369 if (eq.isValidKey(e)) return eq.hash(e); |
| 370 } |
| 371 return 0; |
| 372 } |
| 373 |
| 374 bool isValidKey(Object o) { |
| 375 for (Equality<E> eq in _equalities) { |
| 376 if (eq.isValidKey(o)) return true; |
| 377 } |
| 378 return false; |
| 379 } |
| 380 } |
| 381 |
| 382 /// Deep equality on collections. |
| 383 /// |
| 384 /// Recognizes lists, sets, iterables and maps and compares their elements using |
| 385 /// deep equality as well. |
| 386 /// |
| 387 /// Non-iterable/map objects are compared using a configurable base equality. |
| 388 /// |
| 389 /// Works in one of two modes: ordered or unordered. |
| 390 /// |
| 391 /// In ordered mode, lists and iterables are required to have equal elements |
| 392 /// in the same order. In unordered mode, the order of elements in iterables |
| 393 /// and lists are not important. |
| 394 /// |
| 395 /// A list is only equal to another list, likewise for sets and maps. All other |
| 396 /// iterables are compared as iterables only. |
| 397 class DeepCollectionEquality implements Equality { |
| 398 final Equality _base; |
| 399 final bool _unordered; |
| 400 const DeepCollectionEquality([Equality base = const DefaultEquality()]) |
| 401 : _base = base, |
| 402 _unordered = false; |
| 403 |
| 404 /// Creates a deep equality on collections where the order of lists and |
| 405 /// iterables are not considered important. That is, lists and iterables are |
| 406 /// treated as unordered iterables. |
| 407 const DeepCollectionEquality.unordered( |
| 408 [Equality base = const DefaultEquality()]) |
| 409 : _base = base, |
| 410 _unordered = true; |
| 411 |
| 412 bool equals(e1, e2) { |
| 413 if (e1 is Set) { |
| 414 if (e2 is! Set) return false; |
| 415 return new SetEquality(this).equals(e1, e2); |
| 416 } |
| 417 if (e1 is Map) { |
| 418 if (e2 is! Map) return false; |
| 419 return new MapEquality(keys: this, values: this).equals(e1, e2); |
| 420 } |
| 421 if (!_unordered) { |
| 422 if (e1 is List) { |
| 423 if (e2 is! List) return false; |
| 424 return new ListEquality(this).equals(e1, e2); |
| 425 } |
| 426 if (e1 is Iterable) { |
| 427 if (e2 is! Iterable) return false; |
| 428 return new IterableEquality(this).equals(e1, e2); |
| 429 } |
| 430 } else if (e1 is Iterable) { |
| 431 if (e2 is! Iterable) return false; |
| 432 if (e1 is List != e2 is List) return false; |
| 433 return new UnorderedIterableEquality(this).equals(e1, e2); |
| 434 } |
| 435 return _base.equals(e1, e2); |
| 436 } |
| 437 |
| 438 int hash(Object o) { |
| 439 if (o is Set) return new SetEquality(this).hash(o); |
| 440 if (o is Map) return new MapEquality(keys: this, values: this).hash(o); |
| 441 if (!_unordered) { |
| 442 if (o is List) return new ListEquality(this).hash(o); |
| 443 if (o is Iterable) return new IterableEquality(this).hash(o); |
| 444 } else if (o is Iterable) { |
| 445 return new UnorderedIterableEquality(this).hash(o); |
| 446 } |
| 447 return _base.hash(o); |
| 448 } |
| 449 |
| 450 bool isValidKey(Object o) => o is Iterable || o is Map || _base.isValidKey(o); |
| 451 } |
| 452 |
| 453 /// String equality that's insensitive to differences in ASCII case. |
| 454 /// |
| 455 /// Non-ASCII characters are compared as-is, with no conversion. |
| 456 class CaseInsensitiveEquality implements Equality<String> { |
| 457 const CaseInsensitiveEquality(); |
| 458 |
| 459 bool equals(String string1, String string2) => |
| 460 equalsIgnoreAsciiCase(string1, string2); |
| 461 |
| 462 int hash(String string) => hashIgnoreAsciiCase(string); |
| 463 |
| 464 bool isValidKey(Object object) => object is String; |
| 465 } |
OLD | NEW |