OLD | NEW |
1 // Copyright (c) 2011, 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 |
11 // [_DeletedKeySentinel]. | 11 // [_DeletedKeySentinel]. |
(...skipping 249 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
261 bool containsValue(V value) { | 261 bool containsValue(V value) { |
262 int length = _values.length; | 262 int length = _values.length; |
263 for (int i = 0; i < length; i++) { | 263 for (int i = 0; i < length; i++) { |
264 var key = _keys[i]; | 264 var key = _keys[i]; |
265 if ((key !== null) && (key !== _DELETED_KEY)) { | 265 if ((key !== null) && (key !== _DELETED_KEY)) { |
266 if (_values[i] == value) return true; | 266 if (_values[i] == value) return true; |
267 } | 267 } |
268 } | 268 } |
269 return false; | 269 return false; |
270 } | 270 } |
| 271 |
| 272 String toString() { |
| 273 return Maps.mapToString(this); |
| 274 } |
271 } | 275 } |
272 | 276 |
273 class HashSetImplementation<E extends Hashable> implements HashSet<E> { | 277 class HashSetImplementation<E extends Hashable> implements HashSet<E> { |
274 | 278 |
275 HashSetImplementation() { | 279 HashSetImplementation() { |
276 _backingMap = new HashMapImplementation<E, E>(); | 280 _backingMap = new HashMapImplementation<E, E>(); |
277 } | 281 } |
278 | 282 |
279 factory HashSetImplementation.from(Iterable<E> other) { | 283 factory HashSetImplementation.from(Iterable<E> other) { |
280 Set<E> set = new HashSetImplementation<E>(); | 284 Set<E> set = new HashSetImplementation<E>(); |
(...skipping 88 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
369 } | 373 } |
370 | 374 |
371 int get length() { | 375 int get length() { |
372 return _backingMap.length; | 376 return _backingMap.length; |
373 } | 377 } |
374 | 378 |
375 Iterator<E> iterator() { | 379 Iterator<E> iterator() { |
376 return new HashSetIterator<E>(this); | 380 return new HashSetIterator<E>(this); |
377 } | 381 } |
378 | 382 |
| 383 String toString() { |
| 384 return Collections.collectionToString(this); |
| 385 } |
| 386 |
379 // The map backing this set. The associations in this map are all | 387 // The map backing this set. The associations in this map are all |
380 // of the form element -> element. If a value is not in the map, | 388 // of the form element -> element. If a value is not in the map, |
381 // then it is not in the set. | 389 // then it is not in the set. |
382 HashMapImplementation<E, E> _backingMap; | 390 HashMapImplementation<E, E> _backingMap; |
383 } | 391 } |
384 | 392 |
385 class HashSetIterator<E> implements Iterator<E> { | 393 class HashSetIterator<E> implements Iterator<E> { |
386 | 394 |
387 // TODO(4504458): Replace set_ with set. | 395 // TODO(4504458): Replace set_ with set. |
388 HashSetIterator(HashSetImplementation<E> set_) | 396 HashSetIterator(HashSetImplementation<E> set_) |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
432 | 440 |
433 /** | 441 /** |
434 * A singleton sentinel used to represent when a key is deleted from the map. | 442 * A singleton sentinel used to represent when a key is deleted from the map. |
435 * We can't use [: const Object() :] as a sentinel because it would end up | 443 * We can't use [: const Object() :] as a sentinel because it would end up |
436 * canonicalized and then we cannot distinguish the deleted key from the | 444 * canonicalized and then we cannot distinguish the deleted key from the |
437 * canonicalized [: Object() :]. | 445 * canonicalized [: Object() :]. |
438 */ | 446 */ |
439 class _DeletedKeySentinel { | 447 class _DeletedKeySentinel { |
440 const _DeletedKeySentinel(); | 448 const _DeletedKeySentinel(); |
441 } | 449 } |
OLD | NEW |