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 import "dart:collection"; | 5 import "dart:collection"; |
6 | 6 |
7 const int _HASH_MASK = 0x7fffffff; | 7 const int _HASH_MASK = 0x7fffffff; |
8 | 8 |
9 /// A generic equality relation on objects. | 9 /// A generic equality relation on objects. |
10 abstract class Equality<E> { | 10 abstract class Equality<E> { |
11 const factory Equality() = DefaultEquality; | 11 const factory Equality() = DefaultEquality<E>; |
12 | 12 |
13 /// Compare two elements for being equal. | 13 /// Compare two elements for being equal. |
14 /// | 14 /// |
15 /// This should be a proper equality relation. | 15 /// This should be a proper equality relation. |
16 bool equals(E e1, E e2); | 16 bool equals(E e1, E e2); |
17 | 17 |
18 /// Get a hashcode of an element. | 18 /// Get a hashcode of an element. |
19 /// | 19 /// |
20 /// The hashcode should be compatible with [equals], so that if | 20 /// The hashcode should be compatible with [equals], so that if |
21 /// `equals(a, b)` then `hash(a) == hash(b)`. | 21 /// `equals(a, b)` then `hash(a) == hash(b)`. |
22 int hash(E e); | 22 int hash(E e); |
23 | 23 |
24 /// Test whether an object is a valid argument to [equals] and [hash]. | 24 /// Test whether an object is a valid argument to [equals] and [hash]. |
25 /// | 25 /// |
26 /// Some implementations may be restricted to only work on specific types | 26 /// Some implementations may be restricted to only work on specific types |
27 /// of objects. | 27 /// of objects. |
28 bool isValidKey(Object o); | 28 bool isValidKey(Object o); |
29 } | 29 } |
30 | 30 |
31 /// Equality of objects that compares only the natural equality of the objects. | 31 /// Equality of objects that compares only the natural equality of the objects. |
32 /// | 32 /// |
33 /// This equality uses the objects' own [Object.==] and [Object.hashCode] for | 33 /// This equality uses the objects' own [Object.==] and [Object.hashCode] for |
34 /// the equality. | 34 /// the equality. |
35 class DefaultEquality implements Equality { | 35 class DefaultEquality<E> implements Equality<E> { |
36 const DefaultEquality(); | 36 const DefaultEquality(); |
37 bool equals(Object e1, Object e2) => e1 == e2; | 37 bool equals(E e1, E e2) => e1 == e2; |
38 int hash(Object e) => e.hashCode; | 38 int hash(E e) => e.hashCode; |
39 bool isValidKey(Object o) => true; | 39 bool isValidKey(Object o) => true; |
40 } | 40 } |
41 | 41 |
42 /// Equality of objects that compares only the identity of the objects. | 42 /// Equality of objects that compares only the identity of the objects. |
43 class IdentityEquality implements Equality { | 43 class IdentityEquality<E> implements Equality<E> { |
44 const IdentityEquality(); | 44 const IdentityEquality(); |
45 bool equals(Object e1, Object e2) => identical(e1, e2); | 45 bool equals(E e1, E e2) => identical(e1, e2); |
46 int hash(Object e) => identityHashCode(e); | 46 int hash(E e) => identityHashCode(e); |
47 bool isValidKey(Object o) => true; | 47 bool isValidKey(Object o) => true; |
48 } | 48 } |
49 | 49 |
50 /// Equality on iterables. | 50 /// Equality on iterables. |
51 /// | 51 /// |
52 /// Two iterables are equal if they have the same elements in the same order. | 52 /// Two iterables are equal if they have the same elements in the same order. |
53 class IterableEquality<E> implements Equality<Iterable<E>> { | 53 class IterableEquality<E> implements Equality<Iterable<E>> { |
54 final Equality<E> _elementEquality; | 54 final Equality<E> _elementEquality; |
55 const IterableEquality([Equality<E> elementEquality = | 55 const IterableEquality([Equality<E> elementEquality = |
56 const DefaultEquality()]) | 56 const DefaultEquality()]) |
57 : _elementEquality = elementEquality; | 57 : _elementEquality = elementEquality; |
58 | 58 |
59 bool equals(Iterable<E> elements1, Iterable<E> elements2) { | 59 bool equals(Iterable<E> elements1, Iterable<E> elements2) { |
60 if (identical(elements1, elements2)) return true; | 60 if (identical(elements1, elements2)) return true; |
61 if (elements1 == null || elements2 == null) return false; | 61 if (elements1 == null || elements2 == null) return false; |
62 Iterator it1 = elements1.iterator; | 62 var it1 = elements1.iterator; |
63 Iterator it2 = elements2.iterator; | 63 var it2 = elements2.iterator; |
64 while (true) { | 64 while (true) { |
65 bool hasNext = it1.moveNext(); | 65 bool hasNext = it1.moveNext(); |
66 if (hasNext != it2.moveNext()) return false; | 66 if (hasNext != it2.moveNext()) return false; |
67 if (!hasNext) return true; | 67 if (!hasNext) return true; |
68 if (!_elementEquality.equals(it1.current, it2.current)) return false; | 68 if (!_elementEquality.equals(it1.current, it2.current)) return false; |
69 } | 69 } |
70 } | 70 } |
71 | 71 |
72 int hash(Iterable<E> elements) { | 72 int hash(Iterable<E> elements) { |
73 // Jenkins's one-at-a-time hash function. | 73 // Jenkins's one-at-a-time hash function. |
(...skipping 301 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
375 if (o is List) return new ListEquality(this).hash(o); | 375 if (o is List) return new ListEquality(this).hash(o); |
376 if (o is Iterable) return new IterableEquality(this).hash(o); | 376 if (o is Iterable) return new IterableEquality(this).hash(o); |
377 } else if (o is Iterable) { | 377 } else if (o is Iterable) { |
378 return new UnorderedIterableEquality(this).hash(o); | 378 return new UnorderedIterableEquality(this).hash(o); |
379 } | 379 } |
380 return _base.hash(o); | 380 return _base.hash(o); |
381 } | 381 } |
382 | 382 |
383 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); |
384 } | 384 } |
OLD | NEW |