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 |