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