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, V> implements HashMap<K, V> { | 6 class HashMapImplementation<K, 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 388 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
399 | 399 |
400 class HashSetIterator<E> implements Iterator<E> { | 400 class HashSetIterator<E> implements Iterator<E> { |
401 | 401 |
402 // TODO(4504458): Replace set_ with set. | 402 // TODO(4504458): Replace set_ with set. |
403 HashSetIterator(HashSetImplementation<E> set_) | 403 HashSetIterator(HashSetImplementation<E> set_) |
404 : _nextValidIndex = -1, | 404 : _nextValidIndex = -1, |
405 _entries = set_._backingMap._keys { | 405 _entries = set_._backingMap._keys { |
406 _advance(); | 406 _advance(); |
407 } | 407 } |
408 | 408 |
409 bool hasNext() { | 409 bool get hasNext { |
410 if (_nextValidIndex >= _entries.length) return false; | 410 if (_nextValidIndex >= _entries.length) return false; |
411 if (_entries[_nextValidIndex] === HashMapImplementation._DELETED_KEY) { | 411 if (_entries[_nextValidIndex] === HashMapImplementation._DELETED_KEY) { |
412 // This happens in case the set was modified in the meantime. | 412 // This happens in case the set was modified in the meantime. |
413 // A modification on the set may make this iterator misbehave, | 413 // A modification on the set may make this iterator misbehave, |
414 // but we should never return the sentinel. | 414 // but we should never return the sentinel. |
415 _advance(); | 415 _advance(); |
416 } | 416 } |
417 return _nextValidIndex < _entries.length; | 417 return _nextValidIndex < _entries.length; |
418 } | 418 } |
419 | 419 |
420 E next() { | 420 E next() { |
421 if (!hasNext()) { | 421 if (!hasNext) { |
422 throw const NoMoreElementsException(); | 422 throw const NoMoreElementsException(); |
423 } | 423 } |
424 E res = _entries[_nextValidIndex]; | 424 E res = _entries[_nextValidIndex]; |
425 _advance(); | 425 _advance(); |
426 return res; | 426 return res; |
427 } | 427 } |
428 | 428 |
429 void _advance() { | 429 void _advance() { |
430 int length = _entries.length; | 430 int length = _entries.length; |
431 var entry; | 431 var entry; |
(...skipping 15 matching lines...) Expand all Loading... |
447 | 447 |
448 /** | 448 /** |
449 * A singleton sentinel used to represent when a key is deleted from the map. | 449 * A singleton sentinel used to represent when a key is deleted from the map. |
450 * We can't use [: const Object() :] as a sentinel because it would end up | 450 * We can't use [: const Object() :] as a sentinel because it would end up |
451 * canonicalized and then we cannot distinguish the deleted key from the | 451 * canonicalized and then we cannot distinguish the deleted key from the |
452 * canonicalized [: Object() :]. | 452 * canonicalized [: Object() :]. |
453 */ | 453 */ |
454 class _DeletedKeySentinel { | 454 class _DeletedKeySentinel { |
455 const _DeletedKeySentinel(); | 455 const _DeletedKeySentinel(); |
456 } | 456 } |
OLD | NEW |