Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1692)

Side by Side Diff: sdk/lib/core/map.dart

Issue 11867024: Move some core classes to collection library. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Update status files with bug number. Created 7 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « sdk/lib/core/iterator.dart ('k') | sdk/lib/core/queue.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
OLDNEW
« no previous file with comments | « sdk/lib/core/iterator.dart ('k') | sdk/lib/core/queue.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698