OLD | NEW |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, 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 203 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
214 _numberOfDeleted++; | 214 _numberOfDeleted++; |
215 return value; | 215 return value; |
216 } | 216 } |
217 return null; | 217 return null; |
218 } | 218 } |
219 | 219 |
220 bool isEmpty() { | 220 bool isEmpty() { |
221 return _numberOfEntries == 0; | 221 return _numberOfEntries == 0; |
222 } | 222 } |
223 | 223 |
224 int get length() { | 224 int get length { |
225 return _numberOfEntries; | 225 return _numberOfEntries; |
226 } | 226 } |
227 | 227 |
228 void forEach(void f(K key, V value)) { | 228 void forEach(void f(K key, V value)) { |
229 int length = _keys.length; | 229 int length = _keys.length; |
230 for (int i = 0; i < length; i++) { | 230 for (int i = 0; i < length; i++) { |
231 var key = _keys[i]; | 231 var key = _keys[i]; |
232 if ((key !== null) && (key !== _DELETED_KEY)) { | 232 if ((key !== null) && (key !== _DELETED_KEY)) { |
233 f(key, _values[i]); | 233 f(key, _values[i]); |
234 } | 234 } |
(...skipping 135 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
370 | 370 |
371 bool some(bool f(E element)) { | 371 bool some(bool f(E element)) { |
372 Collection<E> keys = _backingMap.getKeys(); | 372 Collection<E> keys = _backingMap.getKeys(); |
373 return keys.some(f); | 373 return keys.some(f); |
374 } | 374 } |
375 | 375 |
376 bool isEmpty() { | 376 bool isEmpty() { |
377 return _backingMap.isEmpty(); | 377 return _backingMap.isEmpty(); |
378 } | 378 } |
379 | 379 |
380 int get length() { | 380 int get length { |
381 return _backingMap.length; | 381 return _backingMap.length; |
382 } | 382 } |
383 | 383 |
384 Iterator<E> iterator() { | 384 Iterator<E> iterator() { |
385 return new HashSetIterator<E>(this); | 385 return new HashSetIterator<E>(this); |
386 } | 386 } |
387 | 387 |
388 String toString() { | 388 String toString() { |
389 return Collections.collectionToString(this); | 389 return Collections.collectionToString(this); |
390 } | 390 } |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
445 | 445 |
446 /** | 446 /** |
447 * A singleton sentinel used to represent when a key is deleted from the map. | 447 * A singleton sentinel used to represent when a key is deleted from the map. |
448 * We can't use [: const Object() :] as a sentinel because it would end up | 448 * We can't use [: const Object() :] as a sentinel because it would end up |
449 * canonicalized and then we cannot distinguish the deleted key from the | 449 * canonicalized and then we cannot distinguish the deleted key from the |
450 * canonicalized [: Object() :]. | 450 * canonicalized [: Object() :]. |
451 */ | 451 */ |
452 class _DeletedKeySentinel { | 452 class _DeletedKeySentinel { |
453 const _DeletedKeySentinel(); | 453 const _DeletedKeySentinel(); |
454 } | 454 } |
OLD | NEW |