| 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 /** | 5 /** |
| 6 * Defines equality relations on collections. | 6 * Defines equality relations on collections. |
| 7 */ | 7 */ |
| 8 library dart.collection_helper.equality; | 8 library dart.collection_helper.equality; |
| 9 | 9 |
| 10 import "dart:collection"; | 10 import "dart:collection"; |
| (...skipping 133 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 144 } | 144 } |
| 145 hash = (hash + (hash << 3)) & _HASH_MASK; | 145 hash = (hash + (hash << 3)) & _HASH_MASK; |
| 146 hash ^= (hash >> 11); | 146 hash ^= (hash >> 11); |
| 147 hash = (hash + (hash << 15)) & _HASH_MASK; | 147 hash = (hash + (hash << 15)) & _HASH_MASK; |
| 148 return hash; | 148 return hash; |
| 149 } | 149 } |
| 150 | 150 |
| 151 bool isValidKey(Object o) => o is List<E>; | 151 bool isValidKey(Object o) => o is List<E>; |
| 152 } | 152 } |
| 153 | 153 |
| 154 /** | 154 abstract class _UnorderedEquality<T> implements Equality<T> { |
| 155 * Equality of the elements of two iterables without considering order. | |
| 156 * | |
| 157 * Two iterables are considered equal if they have the same number of elements, | |
| 158 * and the elements of one set can be paired with the elements | |
| 159 * of the other iterable, so that each pair are equal. | |
| 160 */ | |
| 161 class UnorderedIterableEquality<E> implements Equality<Iterable<E>> { | |
| 162 final Equality<E> _elementEquality; | 155 final Equality<E> _elementEquality; |
| 163 | 156 |
| 164 const UnorderedIterableEquality( | 157 const _UnorderedEquality(this._elementEquality); |
| 165 [Equality<E> elementEquality = const DefaultEquality()]) | |
| 166 : _elementEquality = elementEquality; | |
| 167 | 158 |
| 168 bool equals(Iterable<E> e1, Iterable<E> e2) { | 159 bool equals(T e1, T e2) { |
| 169 if (identical(e1, e2)) return true; | 160 if (identical(e1, e2)) return true; |
| 170 if (e1 == null || e2 == null) return false; | 161 if (e1 == null || e2 == null) return false; |
| 171 HashMap<E, int> counts = new HashMap( | 162 HashMap<E, int> counts = new HashMap( |
| 172 equals: _elementEquality.equals, | 163 equals: _elementEquality.equals, |
| 173 hashCode: _elementEquality.hash, | 164 hashCode: _elementEquality.hash, |
| 174 isValidKey: _elementEquality.isValidKey); | 165 isValidKey: _elementEquality.isValidKey); |
| 175 int length = 0; | 166 int length = 0; |
| 176 for (E e in e1) { | 167 for (var e in e1) { |
| 177 int count = counts[e]; | 168 int count = counts[e]; |
| 178 if (count == null) count = 0; | 169 if (count == null) count = 0; |
| 179 counts[e] = count + 1; | 170 counts[e] = count + 1; |
| 180 length++; | 171 length++; |
| 181 } | 172 } |
| 182 for (E e in e2) { | 173 for (var e in e2) { |
| 183 int count = counts[e]; | 174 int count = counts[e]; |
| 184 if (count == null || count == 0) return false; | 175 if (count == null || count == 0) return false; |
| 185 counts[e] = count - 1; | 176 counts[e] = count - 1; |
| 186 length--; | 177 length--; |
| 187 } | 178 } |
| 188 return length == 0; | 179 return length == 0; |
| 189 } | 180 } |
| 190 | 181 |
| 191 int hash(Iterable<E> e) { | 182 int hash(T e) { |
| 192 int hash = 0; | 183 int hash = 0; |
| 193 for (E element in e) { | 184 for (var element in e) { |
| 194 int c = _elementEquality.hash(element); | 185 int c = _elementEquality.hash(element); |
| 195 hash = (hash + c) & _HASH_MASK; | 186 hash = (hash + c) & _HASH_MASK; |
| 196 } | 187 } |
| 197 hash = (hash + (hash << 3)) & _HASH_MASK; | 188 hash = (hash + (hash << 3)) & _HASH_MASK; |
| 198 hash ^= (hash >> 11); | 189 hash ^= (hash >> 11); |
| 199 hash = (hash + (hash << 15)) & _HASH_MASK; | 190 hash = (hash + (hash << 15)) & _HASH_MASK; |
| 200 return hash; | 191 return hash; |
| 201 } | 192 } |
| 193 } |
| 194 |
| 195 /** |
| 196 * Equality of the elements of two iterables without considering order. |
| 197 * |
| 198 * Two iterables are considered equal if they have the same number of elements, |
| 199 * and the elements of one set can be paired with the elements |
| 200 * of the other iterable, so that each pair are equal. |
| 201 */ |
| 202 class UnorderedIterableEquality<E> extends _UnorderedEquality<Iterable<E>> { |
| 203 const UnorderedIterableEquality( |
| 204 [Equality<E> elementEquality = const DefaultEquality()]) |
| 205 : super(elementEquality); |
| 202 | 206 |
| 203 bool isValidKey(Object o) => o is Iterable<E>; | 207 bool isValidKey(Object o) => o is Iterable<E>; |
| 204 } | 208 } |
| 205 | 209 |
| 206 /** | 210 /** |
| 207 * Equality of sets. | 211 * Equality of sets. |
| 208 * | 212 * |
| 209 * Two sets are considered equal if they have the same number of elements, | 213 * Two sets are considered equal if they have the same number of elements, |
| 210 * and the elements of one set can be paired with the elements | 214 * and the elements of one set can be paired with the elements |
| 211 * of the other set, so that each pair are equal. | 215 * of the other set, so that each pair are equal. |
| 212 * | 216 * |
| 213 * This equality behaves the same as [UnorderedIterableEquality] except that | 217 * This equality behaves the same as [UnorderedIterableEquality] except that |
| 214 * it expects sets instead of iterables as arguments. | 218 * it expects sets instead of iterables as arguments. |
| 215 */ | 219 */ |
| 216 class SetEquality<E> extends UnorderedIterableEquality<E> | 220 class SetEquality<E> extends _UnorderedEquality<Set<E>> { |
| 217 implements Equality<Set<E>> { | |
| 218 const SetEquality( | 221 const SetEquality( |
| 219 [Equality<E> elementEquality = const DefaultEquality()]) | 222 [Equality<E> elementEquality = const DefaultEquality()]) |
| 220 : super(elementEquality); | 223 : super(elementEquality); |
| 221 | 224 |
| 222 bool equals(Set<E> e1, Set<E> e2) => super.equals(e1, e2); | |
| 223 | |
| 224 int hash(Set<E> e) => super.hash(e); | |
| 225 | |
| 226 bool isValidKey(Object o) => o is Set<E>; | 225 bool isValidKey(Object o) => o is Set<E>; |
| 227 } | 226 } |
| 228 | 227 |
| 229 /** | 228 /** |
| 230 * Internal class used by [MapEquality]. | 229 * Internal class used by [MapEquality]. |
| 231 * | 230 * |
| 232 * The class represents a map entry as a single object, | 231 * The class represents a map entry as a single object, |
| 233 * using a combined hashCode and equality of the key and value. | 232 * using a combined hashCode and equality of the key and value. |
| 234 */ | 233 */ |
| 235 class _MapEntry { | 234 class _MapEntry { |
| (...skipping 174 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 410 if (o is List) return new ListEquality(this).hash(o); | 409 if (o is List) return new ListEquality(this).hash(o); |
| 411 if (o is Iterable) return new IterableEquality(this).hash(o); | 410 if (o is Iterable) return new IterableEquality(this).hash(o); |
| 412 } else if (o is Iterable) { | 411 } else if (o is Iterable) { |
| 413 return new UnorderedIterableEquality(this).hash(o); | 412 return new UnorderedIterableEquality(this).hash(o); |
| 414 } | 413 } |
| 415 return _base.hash(o); | 414 return _base.hash(o); |
| 416 } | 415 } |
| 417 | 416 |
| 418 bool isValidKey(Object o) => o is Iterable || o is Map || _base.isValidKey(o); | 417 bool isValidKey(Object o) => o is Iterable || o is Map || _base.isValidKey(o); |
| 419 } | 418 } |
| OLD | NEW |