| 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 |