| OLD | NEW |
| 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2011, 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 // Hash map implementation with open addressing and quadratic probing. | 5 // Hash map implementation with open addressing and quadratic probing. |
| 6 class HashMapImplementation<K extends Hashable, V> implements HashMap<K, V> { | 6 class HashMapImplementation<K extends Hashable, V> implements HashMap<K, V> { |
| 7 | 7 |
| 8 // The [_keys] list contains the keys inserted in the map. | 8 // The [_keys] list contains the keys inserted in the map. |
| 9 // The [_keys] list must be a raw list because it | 9 // The [_keys] list must be a raw list because it |
| 10 // will contain both elements of type K, and the [_DELETED_KEY] of type | 10 // will contain both elements of type K, and the [_DELETED_KEY] of type |
| 11 // [_DeletedKeySentinel]. | 11 // [_DeletedKeySentinel]. |
| (...skipping 249 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 261 bool containsValue(V value) { | 261 bool containsValue(V value) { |
| 262 int length = _values.length; | 262 int length = _values.length; |
| 263 for (int i = 0; i < length; i++) { | 263 for (int i = 0; i < length; i++) { |
| 264 var key = _keys[i]; | 264 var key = _keys[i]; |
| 265 if ((key !== null) && (key !== _DELETED_KEY)) { | 265 if ((key !== null) && (key !== _DELETED_KEY)) { |
| 266 if (_values[i] == value) return true; | 266 if (_values[i] == value) return true; |
| 267 } | 267 } |
| 268 } | 268 } |
| 269 return false; | 269 return false; |
| 270 } | 270 } |
| 271 | |
| 272 String toString() { | |
| 273 return Maps.mapToString(this); | |
| 274 } | |
| 275 } | 271 } |
| 276 | 272 |
| 277 class HashSetImplementation<E extends Hashable> implements HashSet<E> { | 273 class HashSetImplementation<E extends Hashable> implements HashSet<E> { |
| 278 | 274 |
| 279 HashSetImplementation() { | 275 HashSetImplementation() { |
| 280 _backingMap = new HashMapImplementation<E, E>(); | 276 _backingMap = new HashMapImplementation<E, E>(); |
| 281 } | 277 } |
| 282 | 278 |
| 283 factory HashSetImplementation.from(Iterable<E> other) { | 279 factory HashSetImplementation.from(Iterable<E> other) { |
| 284 Set<E> set = new HashSetImplementation<E>(); | 280 Set<E> set = new HashSetImplementation<E>(); |
| (...skipping 88 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 373 } | 369 } |
| 374 | 370 |
| 375 int get length() { | 371 int get length() { |
| 376 return _backingMap.length; | 372 return _backingMap.length; |
| 377 } | 373 } |
| 378 | 374 |
| 379 Iterator<E> iterator() { | 375 Iterator<E> iterator() { |
| 380 return new HashSetIterator<E>(this); | 376 return new HashSetIterator<E>(this); |
| 381 } | 377 } |
| 382 | 378 |
| 383 String toString() { | |
| 384 return Collections.collectionToString(this); | |
| 385 } | |
| 386 | |
| 387 // The map backing this set. The associations in this map are all | 379 // The map backing this set. The associations in this map are all |
| 388 // of the form element -> element. If a value is not in the map, | 380 // of the form element -> element. If a value is not in the map, |
| 389 // then it is not in the set. | 381 // then it is not in the set. |
| 390 HashMapImplementation<E, E> _backingMap; | 382 HashMapImplementation<E, E> _backingMap; |
| 391 } | 383 } |
| 392 | 384 |
| 393 class HashSetIterator<E> implements Iterator<E> { | 385 class HashSetIterator<E> implements Iterator<E> { |
| 394 | 386 |
| 395 // TODO(4504458): Replace set_ with set. | 387 // TODO(4504458): Replace set_ with set. |
| 396 HashSetIterator(HashSetImplementation<E> set_) | 388 HashSetIterator(HashSetImplementation<E> set_) |
| (...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 440 | 432 |
| 441 /** | 433 /** |
| 442 * A singleton sentinel used to represent when a key is deleted from the map. | 434 * A singleton sentinel used to represent when a key is deleted from the map. |
| 443 * We can't use [: const Object() :] as a sentinel because it would end up | 435 * We can't use [: const Object() :] as a sentinel because it would end up |
| 444 * canonicalized and then we cannot distinguish the deleted key from the | 436 * canonicalized and then we cannot distinguish the deleted key from the |
| 445 * canonicalized [: Object() :]. | 437 * canonicalized [: Object() :]. |
| 446 */ | 438 */ |
| 447 class _DeletedKeySentinel { | 439 class _DeletedKeySentinel { |
| 448 const _DeletedKeySentinel(); | 440 const _DeletedKeySentinel(); |
| 449 } | 441 } |
| OLD | NEW |