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 |