| OLD | NEW |
| 1 // Copyright (c) 2011, 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 |
| (...skipping 318 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 329 return contains(value); | 329 return contains(value); |
| 330 }); | 330 }); |
| 331 } | 331 } |
| 332 | 332 |
| 333 void forEach(void f(E element)) { | 333 void forEach(void f(E element)) { |
| 334 _backingMap.forEach(void _(E key, E value) { | 334 _backingMap.forEach(void _(E key, E value) { |
| 335 f(key); | 335 f(key); |
| 336 }); | 336 }); |
| 337 } | 337 } |
| 338 | 338 |
| 339 Set map(f(E element)) { |
| 340 Set result = new Set(); |
| 341 _backingMap.forEach(void _(E key, E value) { |
| 342 result.add(f(key)); |
| 343 }); |
| 344 return result; |
| 345 } |
| 346 |
| 339 Set<E> filter(bool f(E element)) { | 347 Set<E> filter(bool f(E element)) { |
| 340 Set<E> result = new Set<E>(); | 348 Set<E> result = new Set<E>(); |
| 341 _backingMap.forEach(void _(E key, E value) { | 349 _backingMap.forEach(void _(E key, E value) { |
| 342 if (f(key)) result.add(key); | 350 if (f(key)) result.add(key); |
| 343 }); | 351 }); |
| 344 return result; | 352 return result; |
| 345 } | 353 } |
| 346 | 354 |
| 347 bool every(bool f(E element)) { | 355 bool every(bool f(E element)) { |
| 348 Collection<E> keys = _backingMap.getKeys(); | 356 Collection<E> keys = _backingMap.getKeys(); |
| (...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 422 | 430 |
| 423 /** | 431 /** |
| 424 * A singleton sentinel used to represent when a key is deleted from the map. | 432 * A singleton sentinel used to represent when a key is deleted from the map. |
| 425 * We can't use [: const Object() :] as a sentinel because it would end up | 433 * We can't use [: const Object() :] as a sentinel because it would end up |
| 426 * canonicalized and then we cannot distinguish the deleted key from the | 434 * canonicalized and then we cannot distinguish the deleted key from the |
| 427 * canonicalized [: Object() :]. | 435 * canonicalized [: Object() :]. |
| 428 */ | 436 */ |
| 429 class _DeletedKeySentinel { | 437 class _DeletedKeySentinel { |
| 430 const _DeletedKeySentinel(); | 438 const _DeletedKeySentinel(); |
| 431 } | 439 } |
| OLD | NEW |