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 part of dart.core; | 5 part of dart.core; |
6 | 6 |
7 /** | 7 /** |
8 * A [Map] is an associative container, mapping a key to a value. | 8 * A [Map] is an associative container, mapping a key to a value. |
9 * Null values are supported, but null keys are not. | 9 * Null values are supported, but null keys are not. |
10 */ | 10 */ |
11 abstract class Map<K, V> { | 11 abstract class Map<K, V> { |
12 /** | 12 /** |
13 * Creates a map with the default implementation. | 13 * Creates a map with the default implementation. |
14 */ | 14 */ |
15 factory Map() => new _HashMapImpl<K, V>(); | 15 factory Map() => new HashMap<K, V>(); |
16 | 16 |
17 /** | 17 /** |
18 * Creates a [Map] that contains all key value pairs of [other]. | 18 * Creates a [Map] that contains all key value pairs of [other]. |
19 */ | 19 */ |
20 factory Map.from(Map<K, V> other) => new _HashMapImpl<K, V>.from(other); | 20 factory Map.from(Map<K, V> other) => new HashMap<K, V>.from(other); |
21 | 21 |
22 | 22 |
23 /** | 23 /** |
24 * Returns whether this map contains the given [value]. | 24 * Returns whether this map contains the given [value]. |
25 */ | 25 */ |
26 bool containsValue(V value); | 26 bool containsValue(V value); |
27 | 27 |
28 /** | 28 /** |
29 * Returns whether this map contains the given [key]. | 29 * Returns whether this map contains the given [key]. |
30 */ | 30 */ |
(...skipping 51 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
82 /** | 82 /** |
83 * The number of {key, value} pairs in the map. | 83 * The number of {key, value} pairs in the map. |
84 */ | 84 */ |
85 int get length; | 85 int get length; |
86 | 86 |
87 /** | 87 /** |
88 * Returns true if there is no {key, value} pair in the map. | 88 * Returns true if there is no {key, value} pair in the map. |
89 */ | 89 */ |
90 bool get isEmpty; | 90 bool get isEmpty; |
91 } | 91 } |
92 | |
93 /** | |
94 * Hash map version of the [Map] interface. A [HashMap] does not | |
95 * provide any guarantees on the order of keys and values in [keys] | |
96 * and [values]. | |
97 */ | |
98 abstract class HashMap<K, V> extends Map<K, V> { | |
99 /** | |
100 * Creates a map with the default implementation. | |
101 */ | |
102 factory HashMap() => new _HashMapImpl<K, V>(); | |
103 | |
104 /** | |
105 * Creates a [HashMap] that contains all key value pairs of [other]. | |
106 */ | |
107 factory HashMap.from(Map<K, V> other) => new _HashMapImpl<K, V>.from(other); | |
108 } | |
109 | |
110 /** | |
111 * Hash map version of the [Map] interface that preserves insertion | |
112 * order. | |
113 */ | |
114 abstract class LinkedHashMap<K, V> extends HashMap<K, V> { | |
115 /** | |
116 * Creates a map with the default implementation. | |
117 */ | |
118 factory LinkedHashMap() => new _LinkedHashMapImpl<K, V>(); | |
119 | |
120 /** | |
121 * Creates a [LinkedHashMap] that contains all key value pairs of [other]. | |
122 */ | |
123 factory LinkedHashMap.from(Map<K, V> other) | |
124 => new _LinkedHashMapImpl<K, V>.from(other); | |
125 } | |
126 | |
127 | |
128 // Hash map implementation with open addressing and quadratic probing. | |
129 class _HashMapImpl<K, V> implements HashMap<K, V> { | |
130 | |
131 // The [_keys] list contains the keys inserted in the map. | |
132 // The [_keys] list must be a raw list because it | |
133 // will contain both elements of type K, and the [_DELETED_KEY] of type | |
134 // [_DeletedKeySentinel]. | |
135 // The alternative of declaring the [_keys] list as of type Object | |
136 // does not work, because the HashSetIterator constructor would fail: | |
137 // HashSetIterator(HashSet<E> set) | |
138 // : _nextValidIndex = -1, | |
139 // _entries = set_._backingMap._keys { | |
140 // _advance(); | |
141 // } | |
142 // With K being type int, for example, it would fail because | |
143 // List<Object> is not assignable to type List<int> of entries. | |
144 List _keys; | |
145 | |
146 // The values inserted in the map. For a filled entry index in this | |
147 // list, there is always the corresponding key in the [keys_] list | |
148 // at the same entry index. | |
149 List<V> _values; | |
150 | |
151 // The load limit is the number of entries we allow until we double | |
152 // the size of the lists. | |
153 int _loadLimit; | |
154 | |
155 // The current number of entries in the map. Will never be greater | |
156 // than [_loadLimit]. | |
157 int _numberOfEntries; | |
158 | |
159 // The current number of deleted entries in the map. | |
160 int _numberOfDeleted; | |
161 | |
162 // The sentinel when a key is deleted from the map. | |
163 static const _DeletedKeySentinel _DELETED_KEY = const _DeletedKeySentinel(); | |
164 | |
165 // The initial capacity of a hash map. | |
166 static const int _INITIAL_CAPACITY = 8; // must be power of 2 | |
167 | |
168 _HashMapImpl() { | |
169 _numberOfEntries = 0; | |
170 _numberOfDeleted = 0; | |
171 _loadLimit = _computeLoadLimit(_INITIAL_CAPACITY); | |
172 _keys = new List.fixedLength(_INITIAL_CAPACITY); | |
173 _values = new List<V>.fixedLength(_INITIAL_CAPACITY); | |
174 } | |
175 | |
176 factory _HashMapImpl.from(Map<K, V> other) { | |
177 Map<K, V> result = new _HashMapImpl<K, V>(); | |
178 other.forEach((K key, V value) { result[key] = value; }); | |
179 return result; | |
180 } | |
181 | |
182 static int _computeLoadLimit(int capacity) { | |
183 return (capacity * 3) ~/ 4; | |
184 } | |
185 | |
186 static int _firstProbe(int hashCode, int length) { | |
187 return hashCode & (length - 1); | |
188 } | |
189 | |
190 static int _nextProbe(int currentProbe, int numberOfProbes, int length) { | |
191 return (currentProbe + numberOfProbes) & (length - 1); | |
192 } | |
193 | |
194 int _probeForAdding(K key) { | |
195 if (key == null) throw new ArgumentError(null); | |
196 int hash = _firstProbe(key.hashCode, _keys.length); | |
197 int numberOfProbes = 1; | |
198 int initialHash = hash; | |
199 // insertionIndex points to a slot where a key was deleted. | |
200 int insertionIndex = -1; | |
201 while (true) { | |
202 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. | |
203 Object existingKey = _keys[hash]; | |
204 if (existingKey == null) { | |
205 // We are sure the key is not already in the set. | |
206 // If the current slot is empty and we didn't find any | |
207 // insertion slot before, return this slot. | |
208 if (insertionIndex < 0) return hash; | |
209 // If we did find an insertion slot before, return it. | |
210 return insertionIndex; | |
211 } else if (existingKey == key) { | |
212 // The key is already in the map. Return its slot. | |
213 return hash; | |
214 } else if ((insertionIndex < 0) && | |
215 (identical(existingKey, _DELETED_KEY))) { | |
216 // The slot contains a deleted element. Because previous calls to this | |
217 // method may not have had this slot deleted, we must continue iterate | |
218 // to find if there is a slot with the given key. | |
219 insertionIndex = hash; | |
220 } | |
221 | |
222 // We did not find an insertion slot. Look at the next one. | |
223 hash = _nextProbe(hash, numberOfProbes++, _keys.length); | |
224 // _ensureCapacity has guaranteed the following cannot happen. | |
225 // assert(hash != initialHash); | |
226 } | |
227 } | |
228 | |
229 int _probeForLookup(K key) { | |
230 if (key == null) throw new ArgumentError(null); | |
231 int hash = _firstProbe(key.hashCode, _keys.length); | |
232 int numberOfProbes = 1; | |
233 int initialHash = hash; | |
234 while (true) { | |
235 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. | |
236 Object existingKey = _keys[hash]; | |
237 // If the slot does not contain anything (in particular, it does not | |
238 // contain a deleted key), we know the key is not in the map. | |
239 if (existingKey == null) return -1; | |
240 // The key is in the map, return its index. | |
241 if (existingKey == key) return hash; | |
242 // Go to the next probe. | |
243 hash = _nextProbe(hash, numberOfProbes++, _keys.length); | |
244 // _ensureCapacity has guaranteed the following cannot happen. | |
245 // assert(hash != initialHash); | |
246 } | |
247 } | |
248 | |
249 void _ensureCapacity() { | |
250 int newNumberOfEntries = _numberOfEntries + 1; | |
251 // Test if adding an element will reach the load limit. | |
252 if (newNumberOfEntries >= _loadLimit) { | |
253 _grow(_keys.length * 2); | |
254 return; | |
255 } | |
256 | |
257 // Make sure that we don't have poor performance when a map | |
258 // contains lots of deleted entries: we _grow if | |
259 // there are more deleted entried than free entries. | |
260 int capacity = _keys.length; | |
261 int numberOfFreeOrDeleted = capacity - newNumberOfEntries; | |
262 int numberOfFree = numberOfFreeOrDeleted - _numberOfDeleted; | |
263 // assert(numberOfFree > 0); | |
264 if (_numberOfDeleted > numberOfFree) { | |
265 _grow(_keys.length); | |
266 } | |
267 } | |
268 | |
269 static bool _isPowerOfTwo(int x) { | |
270 return ((x & (x - 1)) == 0); | |
271 } | |
272 | |
273 void _grow(int newCapacity) { | |
274 assert(_isPowerOfTwo(newCapacity)); | |
275 int capacity = _keys.length; | |
276 _loadLimit = _computeLoadLimit(newCapacity); | |
277 List oldKeys = _keys; | |
278 List<V> oldValues = _values; | |
279 _keys = new List.fixedLength(newCapacity); | |
280 _values = new List<V>.fixedLength(newCapacity); | |
281 for (int i = 0; i < capacity; i++) { | |
282 // [key] can be either of type [K] or [_DeletedKeySentinel]. | |
283 Object key = oldKeys[i]; | |
284 // If there is no key, we don't need to deal with the current slot. | |
285 if (key == null || identical(key, _DELETED_KEY)) { | |
286 continue; | |
287 } | |
288 V value = oldValues[i]; | |
289 // Insert the {key, value} pair in their new slot. | |
290 int newIndex = _probeForAdding(key); | |
291 _keys[newIndex] = key; | |
292 _values[newIndex] = value; | |
293 } | |
294 _numberOfDeleted = 0; | |
295 } | |
296 | |
297 void clear() { | |
298 _numberOfEntries = 0; | |
299 _numberOfDeleted = 0; | |
300 int length = _keys.length; | |
301 for (int i = 0; i < length; i++) { | |
302 _keys[i] = null; | |
303 _values[i] = null; | |
304 } | |
305 } | |
306 | |
307 void operator []=(K key, V value) { | |
308 _ensureCapacity(); | |
309 int index = _probeForAdding(key); | |
310 if ((_keys[index] == null) || (identical(_keys[index], _DELETED_KEY))) { | |
311 _numberOfEntries++; | |
312 } | |
313 _keys[index] = key; | |
314 _values[index] = value; | |
315 } | |
316 | |
317 V operator [](K key) { | |
318 int index = _probeForLookup(key); | |
319 if (index < 0) return null; | |
320 return _values[index]; | |
321 } | |
322 | |
323 V putIfAbsent(K key, V ifAbsent()) { | |
324 int index = _probeForLookup(key); | |
325 if (index >= 0) return _values[index]; | |
326 | |
327 V value = ifAbsent(); | |
328 this[key] = value; | |
329 return value; | |
330 } | |
331 | |
332 V remove(K key) { | |
333 int index = _probeForLookup(key); | |
334 if (index >= 0) { | |
335 _numberOfEntries--; | |
336 V value = _values[index]; | |
337 _values[index] = null; | |
338 // Set the key to the sentinel to not break the probing chain. | |
339 _keys[index] = _DELETED_KEY; | |
340 _numberOfDeleted++; | |
341 return value; | |
342 } | |
343 return null; | |
344 } | |
345 | |
346 bool get isEmpty { | |
347 return _numberOfEntries == 0; | |
348 } | |
349 | |
350 int get length { | |
351 return _numberOfEntries; | |
352 } | |
353 | |
354 void forEach(void f(K key, V value)) { | |
355 Iterator<int> it = new _HashMapImplIndexIterator(this); | |
356 while (it.moveNext()) { | |
357 f(_keys[it.current], _values[it.current]); | |
358 } | |
359 } | |
360 | |
361 Iterable<K> get keys => new _HashMapImplKeyIterable<K>(this); | |
362 | |
363 Iterable<V> get values => new _HashMapImplValueIterable<V>(this); | |
364 | |
365 bool containsKey(K key) { | |
366 return (_probeForLookup(key) != -1); | |
367 } | |
368 | |
369 bool containsValue(V value) => values.contains(value); | |
370 | |
371 String toString() { | |
372 return Maps.mapToString(this); | |
373 } | |
374 } | |
375 | |
376 class _HashMapImplKeyIterable<E> extends Iterable<E> { | |
377 final _HashMapImpl _map; | |
378 _HashMapImplKeyIterable(this._map); | |
379 | |
380 Iterator<E> get iterator => new _HashMapImplKeyIterator<E>(_map); | |
381 } | |
382 | |
383 class _HashMapImplValueIterable<E> extends Iterable<E> { | |
384 final _HashMapImpl _map; | |
385 _HashMapImplValueIterable(this._map); | |
386 | |
387 Iterator<E> get iterator => new _HashMapImplValueIterator<E>(_map); | |
388 } | |
389 | |
390 abstract class _HashMapImplIterator<E> implements Iterator<E> { | |
391 final _HashMapImpl _map; | |
392 int _index = -1; | |
393 E _current; | |
394 | |
395 _HashMapImplIterator(this._map); | |
396 | |
397 E _computeCurrentFromIndex(int index, List keys, List values); | |
398 | |
399 bool moveNext() { | |
400 int length = _map._keys.length; | |
401 int newIndex = _index + 1; | |
402 while (newIndex < length) { | |
403 var key = _map._keys[newIndex]; | |
404 if ((key != null) && (!identical(key, _HashMapImpl._DELETED_KEY))) { | |
405 _current = _computeCurrentFromIndex(newIndex, _map._keys, _map._values); | |
406 _index = newIndex; | |
407 return true; | |
408 } | |
409 newIndex++; | |
410 } | |
411 _index = length; | |
412 _current = null; | |
413 return false; | |
414 } | |
415 | |
416 E get current => _current; | |
417 } | |
418 | |
419 class _HashMapImplKeyIterator<E> extends _HashMapImplIterator<E> { | |
420 _HashMapImplKeyIterator(_HashMapImpl map) : super(map); | |
421 | |
422 E _computeCurrentFromIndex(int index, List keys, List values) { | |
423 return keys[index]; | |
424 } | |
425 } | |
426 | |
427 class _HashMapImplValueIterator<E> extends _HashMapImplIterator<E> { | |
428 _HashMapImplValueIterator(_HashMapImpl map) : super(map); | |
429 | |
430 E _computeCurrentFromIndex(int index, List keys, List values) { | |
431 return values[index]; | |
432 } | |
433 } | |
434 | |
435 class _HashMapImplIndexIterator extends _HashMapImplIterator<int> { | |
436 _HashMapImplIndexIterator(_HashMapImpl map) : super(map); | |
437 | |
438 int _computeCurrentFromIndex(int index, List keys, List values) { | |
439 return index; | |
440 } | |
441 } | |
442 | |
443 /** | |
444 * A singleton sentinel used to represent when a key is deleted from the map. | |
445 * We can't use [: const Object() :] as a sentinel because it would end up | |
446 * canonicalized and then we cannot distinguish the deleted key from the | |
447 * canonicalized [: Object() :]. | |
448 */ | |
449 class _DeletedKeySentinel { | |
450 const _DeletedKeySentinel(); | |
451 } | |
452 | |
453 | |
454 /** | |
455 * This class represents a pair of two objects, used by LinkedHashMap | |
456 * to store a {key, value} in a list. | |
457 */ | |
458 class _KeyValuePair<K, V> { | |
459 _KeyValuePair(this.key, this.value) {} | |
460 | |
461 final K key; | |
462 V value; | |
463 } | |
464 | |
465 /** | |
466 * A LinkedHashMap is a hash map that preserves the insertion order | |
467 * when iterating over the keys or the values. Updating the value of a | |
468 * key does not change the order. | |
469 */ | |
470 class _LinkedHashMapImpl<K, V> implements LinkedHashMap<K, V> { | |
471 DoubleLinkedQueue<_KeyValuePair<K, V>> _list; | |
472 HashMap<K, DoubleLinkedQueueEntry<_KeyValuePair<K, V>>> _map; | |
473 | |
474 _LinkedHashMapImpl() { | |
475 _map = new HashMap<K, DoubleLinkedQueueEntry<_KeyValuePair<K, V>>>(); | |
476 _list = new DoubleLinkedQueue<_KeyValuePair<K, V>>(); | |
477 } | |
478 | |
479 factory _LinkedHashMapImpl.from(Map<K, V> other) { | |
480 Map<K, V> result = new _LinkedHashMapImpl<K, V>(); | |
481 other.forEach((K key, V value) { result[key] = value; }); | |
482 return result; | |
483 } | |
484 | |
485 void operator []=(K key, V value) { | |
486 if (_map.containsKey(key)) { | |
487 _map[key].element.value = value; | |
488 } else { | |
489 _list.addLast(new _KeyValuePair<K, V>(key, value)); | |
490 _map[key] = _list.lastEntry(); | |
491 } | |
492 } | |
493 | |
494 V operator [](K key) { | |
495 DoubleLinkedQueueEntry<_KeyValuePair<K, V>> entry = _map[key]; | |
496 if (entry == null) return null; | |
497 return entry.element.value; | |
498 } | |
499 | |
500 V remove(K key) { | |
501 DoubleLinkedQueueEntry<_KeyValuePair<K, V>> entry = _map.remove(key); | |
502 if (entry == null) return null; | |
503 entry.remove(); | |
504 return entry.element.value; | |
505 } | |
506 | |
507 V putIfAbsent(K key, V ifAbsent()) { | |
508 V value = this[key]; | |
509 if ((this[key] == null) && !(containsKey(key))) { | |
510 value = ifAbsent(); | |
511 this[key] = value; | |
512 } | |
513 return value; | |
514 } | |
515 | |
516 Iterable<K> get keys { | |
517 return new MappedIterable<_KeyValuePair<K, V>, K>( | |
518 _list, (_KeyValuePair<K, V> entry) => entry.key); | |
519 } | |
520 | |
521 | |
522 Iterable<V> get values { | |
523 return new MappedIterable<_KeyValuePair<K, V>, V>( | |
524 _list, (_KeyValuePair<K, V> entry) => entry.value); | |
525 } | |
526 | |
527 void forEach(void f(K key, V value)) { | |
528 _list.forEach((_KeyValuePair<K, V> entry) { | |
529 f(entry.key, entry.value); | |
530 }); | |
531 } | |
532 | |
533 bool containsKey(K key) { | |
534 return _map.containsKey(key); | |
535 } | |
536 | |
537 bool containsValue(V value) { | |
538 return _list.any((_KeyValuePair<K, V> entry) { | |
539 return (entry.value == value); | |
540 }); | |
541 } | |
542 | |
543 int get length { | |
544 return _map.length; | |
545 } | |
546 | |
547 bool get isEmpty { | |
548 return length == 0; | |
549 } | |
550 | |
551 void clear() { | |
552 _map.clear(); | |
553 _list.clear(); | |
554 } | |
555 | |
556 String toString() { | |
557 return Maps.mapToString(this); | |
558 } | |
559 } | |
560 | |
OLD | NEW |