Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(719)

Side by Side Diff: lib/src/equality.dart

Issue 1638163002: Modernize the package's style. (Closed) Base URL: git@github.com:dart-lang/collection@master
Patch Set: Code review changes Created 4 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « lib/src/comparators.dart ('k') | lib/src/iterable_zip.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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 }
OLDNEW
« no previous file with comments | « lib/src/comparators.dart ('k') | lib/src/iterable_zip.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698