| 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 [deletedKey_] of type | 10 // will contain both elements of type K, and the [_deletedKey] of type |
| 11 // Object. | 11 // Object. |
| 12 // The alternative of declaring the [keys_] list as of type Object | 12 // The alternative of declaring the [_keys] list as of type Object |
| 13 // does not work, because the HashSetIterator constructor would fail: | 13 // does not work, because the HashSetIterator constructor would fail: |
| 14 // HashSetIterator(HashSet<E> set_) | 14 // HashSetIterator(HashSet<E> set) |
| 15 // : _nextValidIndex = -1, | 15 // : _nextValidIndex = -1, |
| 16 // _entries = set_._backingMap._keys { | 16 // _entries = set_._backingMap._keys { |
| 17 // _advance(); | 17 // _advance(); |
| 18 // } | 18 // } |
| 19 // With K being type int, for example, it would fail because | 19 // With K being type int, for example, it would fail because |
| 20 // ObjectArray<Object> is not assignable to type List<int> of entries_. | 20 // List<Object> is not assignable to type List<int> of entries. |
| 21 List _keys; | 21 List _keys; |
| 22 | 22 |
| 23 // The values_ inserted in the map. For a filled entry index in this | 23 // The values inserted in the map. For a filled entry index in this |
| 24 // list, there is always the corresponding key in the [keys_] list | 24 // list, there is always the corresponding key in the [keys_] list |
| 25 // at the same entry index. | 25 // at the same entry index. |
| 26 List<V> _values; | 26 List<V> _values; |
| 27 | 27 |
| 28 // The load limit is the number of entries we allow until we double | 28 // The load limit is the number of entries we allow until we double |
| 29 // the size of the lists. | 29 // the size of the lists. |
| 30 int _loadLimit; | 30 int _loadLimit; |
| 31 | 31 |
| 32 // The current number of entries in the map. Will never be greater | 32 // The current number of entries in the map. Will never be greater |
| 33 // than [_loadLimit]. | 33 // than [_loadLimit]. |
| (...skipping 383 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 417 } | 417 } |
| 418 | 418 |
| 419 // The entries in the set. May contain null or the sentinel value. | 419 // The entries in the set. May contain null or the sentinel value. |
| 420 List<E> _entries; | 420 List<E> _entries; |
| 421 | 421 |
| 422 // The next valid index in [_entries] or the length of [entries_]. | 422 // The next valid index in [_entries] or the length of [entries_]. |
| 423 // If it is the length of [_entries], calling [hasNext] on the | 423 // If it is the length of [_entries], calling [hasNext] on the |
| 424 // iterator will return false. | 424 // iterator will return false. |
| 425 int _nextValidIndex; | 425 int _nextValidIndex; |
| 426 } | 426 } |
| OLD | NEW |