| 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 210 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 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 if ((_keys[i] !== null) && (_keys[i] !== _DELETED_KEY)) { | 231 K key = _keys[i]; |
| 232 f(_keys[i], _values[i]); | 232 if ((key !== null) && (key !== _DELETED_KEY)) { |
| 233 f(key, _values[i]); |
| 233 } | 234 } |
| 234 } | 235 } |
| 235 } | 236 } |
| 236 | 237 |
| 237 | 238 |
| 238 Collection<K> getKeys() { | 239 Collection<K> getKeys() { |
| 239 List<K> list = new List<K>(length); | 240 List<K> list = new List<K>(length); |
| 240 int i = 0; | 241 int i = 0; |
| 241 forEach(void _(K key, V value) { | 242 forEach(void _(K key, V value) { |
| 242 list[i++] = key; | 243 list[i++] = key; |
| (...skipping 10 matching lines...) Expand all Loading... |
| 253 return list; | 254 return list; |
| 254 } | 255 } |
| 255 | 256 |
| 256 bool containsKey(K key) { | 257 bool containsKey(K key) { |
| 257 return (_probeForLookup(key) != -1); | 258 return (_probeForLookup(key) != -1); |
| 258 } | 259 } |
| 259 | 260 |
| 260 bool containsValue(V value) { | 261 bool containsValue(V value) { |
| 261 int length = _values.length; | 262 int length = _values.length; |
| 262 for (int i = 0; i < length; i++) { | 263 for (int i = 0; i < length; i++) { |
| 263 if ((_keys[i] !== null) && (_keys[i] !== _DELETED_KEY)) { | 264 K key = _keys[i]; |
| 265 if ((key !== null) && (key !== _DELETED_KEY)) { |
| 264 if (_values[i] == value) return true; | 266 if (_values[i] == value) return true; |
| 265 } | 267 } |
| 266 } | 268 } |
| 267 return false; | 269 return false; |
| 268 } | 270 } |
| 269 } | 271 } |
| 270 | 272 |
| 271 class HashSetImplementation<E extends Hashable> implements HashSet<E> { | 273 class HashSetImplementation<E extends Hashable> implements HashSet<E> { |
| 272 | 274 |
| 273 HashSetImplementation() { | 275 HashSetImplementation() { |
| (...skipping 156 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 430 | 432 |
| 431 /** | 433 /** |
| 432 * A singleton sentinel used to represent when a key is deleted from the map. | 434 * A singleton sentinel used to represent when a key is deleted from the map. |
| 433 * We can't use [: const Object() :] as a sentinel because it would end up | 435 * We can't use [: const Object() :] as a sentinel because it would end up |
| 434 * canonicalized and then we cannot distinguish the deleted key from the | 436 * canonicalized and then we cannot distinguish the deleted key from the |
| 435 * canonicalized [: Object() :]. | 437 * canonicalized [: Object() :]. |
| 436 */ | 438 */ |
| 437 class _DeletedKeySentinel { | 439 class _DeletedKeySentinel { |
| 438 const _DeletedKeySentinel(); | 440 const _DeletedKeySentinel(); |
| 439 } | 441 } |
| OLD | NEW |