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

Unified 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 side-by-side diff with in-line comments
Download patch
« no previous file with comments | « sdk/lib/core/iterator.dart ('k') | sdk/lib/core/queue.dart » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: sdk/lib/core/map.dart
diff --git a/sdk/lib/core/map.dart b/sdk/lib/core/map.dart
index 9b2b66675e09090be74dbf5b7ff892d2912e60fc..8b27b3e07bc4a95a9567f0aee70be0cec6e73258 100644
--- a/sdk/lib/core/map.dart
+++ b/sdk/lib/core/map.dart
@@ -12,12 +12,12 @@ abstract class Map<K, V> {
/**
* Creates a map with the default implementation.
*/
- factory Map() => new _HashMapImpl<K, V>();
+ factory Map() => new HashMap<K, V>();
/**
* Creates a [Map] that contains all key value pairs of [other].
*/
- factory Map.from(Map<K, V> other) => new _HashMapImpl<K, V>.from(other);
+ factory Map.from(Map<K, V> other) => new HashMap<K, V>.from(other);
/**
@@ -89,472 +89,3 @@ abstract class Map<K, V> {
*/
bool get isEmpty;
}
-
-/**
- * Hash map version of the [Map] interface. A [HashMap] does not
- * provide any guarantees on the order of keys and values in [keys]
- * and [values].
- */
-abstract class HashMap<K, V> extends Map<K, V> {
- /**
- * Creates a map with the default implementation.
- */
- factory HashMap() => new _HashMapImpl<K, V>();
-
- /**
- * Creates a [HashMap] that contains all key value pairs of [other].
- */
- factory HashMap.from(Map<K, V> other) => new _HashMapImpl<K, V>.from(other);
-}
-
-/**
- * Hash map version of the [Map] interface that preserves insertion
- * order.
- */
-abstract class LinkedHashMap<K, V> extends HashMap<K, V> {
- /**
- * Creates a map with the default implementation.
- */
- factory LinkedHashMap() => new _LinkedHashMapImpl<K, V>();
-
- /**
- * Creates a [LinkedHashMap] that contains all key value pairs of [other].
- */
- factory LinkedHashMap.from(Map<K, V> other)
- => new _LinkedHashMapImpl<K, V>.from(other);
-}
-
-
-// Hash map implementation with open addressing and quadratic probing.
-class _HashMapImpl<K, V> implements HashMap<K, V> {
-
- // The [_keys] list contains the keys inserted in the map.
- // The [_keys] list must be a raw list because it
- // will contain both elements of type K, and the [_DELETED_KEY] of type
- // [_DeletedKeySentinel].
- // The alternative of declaring the [_keys] list as of type Object
- // does not work, because the HashSetIterator constructor would fail:
- // HashSetIterator(HashSet<E> set)
- // : _nextValidIndex = -1,
- // _entries = set_._backingMap._keys {
- // _advance();
- // }
- // With K being type int, for example, it would fail because
- // List<Object> is not assignable to type List<int> of entries.
- List _keys;
-
- // The values inserted in the map. For a filled entry index in this
- // list, there is always the corresponding key in the [keys_] list
- // at the same entry index.
- List<V> _values;
-
- // The load limit is the number of entries we allow until we double
- // the size of the lists.
- int _loadLimit;
-
- // The current number of entries in the map. Will never be greater
- // than [_loadLimit].
- int _numberOfEntries;
-
- // The current number of deleted entries in the map.
- int _numberOfDeleted;
-
- // The sentinel when a key is deleted from the map.
- static const _DeletedKeySentinel _DELETED_KEY = const _DeletedKeySentinel();
-
- // The initial capacity of a hash map.
- static const int _INITIAL_CAPACITY = 8; // must be power of 2
-
- _HashMapImpl() {
- _numberOfEntries = 0;
- _numberOfDeleted = 0;
- _loadLimit = _computeLoadLimit(_INITIAL_CAPACITY);
- _keys = new List.fixedLength(_INITIAL_CAPACITY);
- _values = new List<V>.fixedLength(_INITIAL_CAPACITY);
- }
-
- factory _HashMapImpl.from(Map<K, V> other) {
- Map<K, V> result = new _HashMapImpl<K, V>();
- other.forEach((K key, V value) { result[key] = value; });
- return result;
- }
-
- static int _computeLoadLimit(int capacity) {
- return (capacity * 3) ~/ 4;
- }
-
- static int _firstProbe(int hashCode, int length) {
- return hashCode & (length - 1);
- }
-
- static int _nextProbe(int currentProbe, int numberOfProbes, int length) {
- return (currentProbe + numberOfProbes) & (length - 1);
- }
-
- int _probeForAdding(K key) {
- if (key == null) throw new ArgumentError(null);
- int hash = _firstProbe(key.hashCode, _keys.length);
- int numberOfProbes = 1;
- int initialHash = hash;
- // insertionIndex points to a slot where a key was deleted.
- int insertionIndex = -1;
- while (true) {
- // [existingKey] can be either of type [K] or [_DeletedKeySentinel].
- Object existingKey = _keys[hash];
- if (existingKey == null) {
- // We are sure the key is not already in the set.
- // If the current slot is empty and we didn't find any
- // insertion slot before, return this slot.
- if (insertionIndex < 0) return hash;
- // If we did find an insertion slot before, return it.
- return insertionIndex;
- } else if (existingKey == key) {
- // The key is already in the map. Return its slot.
- return hash;
- } else if ((insertionIndex < 0) &&
- (identical(existingKey, _DELETED_KEY))) {
- // The slot contains a deleted element. Because previous calls to this
- // method may not have had this slot deleted, we must continue iterate
- // to find if there is a slot with the given key.
- insertionIndex = hash;
- }
-
- // We did not find an insertion slot. Look at the next one.
- hash = _nextProbe(hash, numberOfProbes++, _keys.length);
- // _ensureCapacity has guaranteed the following cannot happen.
- // assert(hash != initialHash);
- }
- }
-
- int _probeForLookup(K key) {
- if (key == null) throw new ArgumentError(null);
- int hash = _firstProbe(key.hashCode, _keys.length);
- int numberOfProbes = 1;
- int initialHash = hash;
- while (true) {
- // [existingKey] can be either of type [K] or [_DeletedKeySentinel].
- Object existingKey = _keys[hash];
- // If the slot does not contain anything (in particular, it does not
- // contain a deleted key), we know the key is not in the map.
- if (existingKey == null) return -1;
- // The key is in the map, return its index.
- if (existingKey == key) return hash;
- // Go to the next probe.
- hash = _nextProbe(hash, numberOfProbes++, _keys.length);
- // _ensureCapacity has guaranteed the following cannot happen.
- // assert(hash != initialHash);
- }
- }
-
- void _ensureCapacity() {
- int newNumberOfEntries = _numberOfEntries + 1;
- // Test if adding an element will reach the load limit.
- if (newNumberOfEntries >= _loadLimit) {
- _grow(_keys.length * 2);
- return;
- }
-
- // Make sure that we don't have poor performance when a map
- // contains lots of deleted entries: we _grow if
- // there are more deleted entried than free entries.
- int capacity = _keys.length;
- int numberOfFreeOrDeleted = capacity - newNumberOfEntries;
- int numberOfFree = numberOfFreeOrDeleted - _numberOfDeleted;
- // assert(numberOfFree > 0);
- if (_numberOfDeleted > numberOfFree) {
- _grow(_keys.length);
- }
- }
-
- static bool _isPowerOfTwo(int x) {
- return ((x & (x - 1)) == 0);
- }
-
- void _grow(int newCapacity) {
- assert(_isPowerOfTwo(newCapacity));
- int capacity = _keys.length;
- _loadLimit = _computeLoadLimit(newCapacity);
- List oldKeys = _keys;
- List<V> oldValues = _values;
- _keys = new List.fixedLength(newCapacity);
- _values = new List<V>.fixedLength(newCapacity);
- for (int i = 0; i < capacity; i++) {
- // [key] can be either of type [K] or [_DeletedKeySentinel].
- Object key = oldKeys[i];
- // If there is no key, we don't need to deal with the current slot.
- if (key == null || identical(key, _DELETED_KEY)) {
- continue;
- }
- V value = oldValues[i];
- // Insert the {key, value} pair in their new slot.
- int newIndex = _probeForAdding(key);
- _keys[newIndex] = key;
- _values[newIndex] = value;
- }
- _numberOfDeleted = 0;
- }
-
- void clear() {
- _numberOfEntries = 0;
- _numberOfDeleted = 0;
- int length = _keys.length;
- for (int i = 0; i < length; i++) {
- _keys[i] = null;
- _values[i] = null;
- }
- }
-
- void operator []=(K key, V value) {
- _ensureCapacity();
- int index = _probeForAdding(key);
- if ((_keys[index] == null) || (identical(_keys[index], _DELETED_KEY))) {
- _numberOfEntries++;
- }
- _keys[index] = key;
- _values[index] = value;
- }
-
- V operator [](K key) {
- int index = _probeForLookup(key);
- if (index < 0) return null;
- return _values[index];
- }
-
- V putIfAbsent(K key, V ifAbsent()) {
- int index = _probeForLookup(key);
- if (index >= 0) return _values[index];
-
- V value = ifAbsent();
- this[key] = value;
- return value;
- }
-
- V remove(K key) {
- int index = _probeForLookup(key);
- if (index >= 0) {
- _numberOfEntries--;
- V value = _values[index];
- _values[index] = null;
- // Set the key to the sentinel to not break the probing chain.
- _keys[index] = _DELETED_KEY;
- _numberOfDeleted++;
- return value;
- }
- return null;
- }
-
- bool get isEmpty {
- return _numberOfEntries == 0;
- }
-
- int get length {
- return _numberOfEntries;
- }
-
- void forEach(void f(K key, V value)) {
- Iterator<int> it = new _HashMapImplIndexIterator(this);
- while (it.moveNext()) {
- f(_keys[it.current], _values[it.current]);
- }
- }
-
- Iterable<K> get keys => new _HashMapImplKeyIterable<K>(this);
-
- Iterable<V> get values => new _HashMapImplValueIterable<V>(this);
-
- bool containsKey(K key) {
- return (_probeForLookup(key) != -1);
- }
-
- bool containsValue(V value) => values.contains(value);
-
- String toString() {
- return Maps.mapToString(this);
- }
-}
-
-class _HashMapImplKeyIterable<E> extends Iterable<E> {
- final _HashMapImpl _map;
- _HashMapImplKeyIterable(this._map);
-
- Iterator<E> get iterator => new _HashMapImplKeyIterator<E>(_map);
-}
-
-class _HashMapImplValueIterable<E> extends Iterable<E> {
- final _HashMapImpl _map;
- _HashMapImplValueIterable(this._map);
-
- Iterator<E> get iterator => new _HashMapImplValueIterator<E>(_map);
-}
-
-abstract class _HashMapImplIterator<E> implements Iterator<E> {
- final _HashMapImpl _map;
- int _index = -1;
- E _current;
-
- _HashMapImplIterator(this._map);
-
- E _computeCurrentFromIndex(int index, List keys, List values);
-
- bool moveNext() {
- int length = _map._keys.length;
- int newIndex = _index + 1;
- while (newIndex < length) {
- var key = _map._keys[newIndex];
- if ((key != null) && (!identical(key, _HashMapImpl._DELETED_KEY))) {
- _current = _computeCurrentFromIndex(newIndex, _map._keys, _map._values);
- _index = newIndex;
- return true;
- }
- newIndex++;
- }
- _index = length;
- _current = null;
- return false;
- }
-
- E get current => _current;
-}
-
-class _HashMapImplKeyIterator<E> extends _HashMapImplIterator<E> {
- _HashMapImplKeyIterator(_HashMapImpl map) : super(map);
-
- E _computeCurrentFromIndex(int index, List keys, List values) {
- return keys[index];
- }
-}
-
-class _HashMapImplValueIterator<E> extends _HashMapImplIterator<E> {
- _HashMapImplValueIterator(_HashMapImpl map) : super(map);
-
- E _computeCurrentFromIndex(int index, List keys, List values) {
- return values[index];
- }
-}
-
-class _HashMapImplIndexIterator extends _HashMapImplIterator<int> {
- _HashMapImplIndexIterator(_HashMapImpl map) : super(map);
-
- int _computeCurrentFromIndex(int index, List keys, List values) {
- return index;
- }
-}
-
-/**
- * A singleton sentinel used to represent when a key is deleted from the map.
- * We can't use [: const Object() :] as a sentinel because it would end up
- * canonicalized and then we cannot distinguish the deleted key from the
- * canonicalized [: Object() :].
- */
-class _DeletedKeySentinel {
- const _DeletedKeySentinel();
-}
-
-
-/**
- * This class represents a pair of two objects, used by LinkedHashMap
- * to store a {key, value} in a list.
- */
-class _KeyValuePair<K, V> {
- _KeyValuePair(this.key, this.value) {}
-
- final K key;
- V value;
-}
-
-/**
- * A LinkedHashMap is a hash map that preserves the insertion order
- * when iterating over the keys or the values. Updating the value of a
- * key does not change the order.
- */
-class _LinkedHashMapImpl<K, V> implements LinkedHashMap<K, V> {
- DoubleLinkedQueue<_KeyValuePair<K, V>> _list;
- HashMap<K, DoubleLinkedQueueEntry<_KeyValuePair<K, V>>> _map;
-
- _LinkedHashMapImpl() {
- _map = new HashMap<K, DoubleLinkedQueueEntry<_KeyValuePair<K, V>>>();
- _list = new DoubleLinkedQueue<_KeyValuePair<K, V>>();
- }
-
- factory _LinkedHashMapImpl.from(Map<K, V> other) {
- Map<K, V> result = new _LinkedHashMapImpl<K, V>();
- other.forEach((K key, V value) { result[key] = value; });
- return result;
- }
-
- void operator []=(K key, V value) {
- if (_map.containsKey(key)) {
- _map[key].element.value = value;
- } else {
- _list.addLast(new _KeyValuePair<K, V>(key, value));
- _map[key] = _list.lastEntry();
- }
- }
-
- V operator [](K key) {
- DoubleLinkedQueueEntry<_KeyValuePair<K, V>> entry = _map[key];
- if (entry == null) return null;
- return entry.element.value;
- }
-
- V remove(K key) {
- DoubleLinkedQueueEntry<_KeyValuePair<K, V>> entry = _map.remove(key);
- if (entry == null) return null;
- entry.remove();
- return entry.element.value;
- }
-
- V putIfAbsent(K key, V ifAbsent()) {
- V value = this[key];
- if ((this[key] == null) && !(containsKey(key))) {
- value = ifAbsent();
- this[key] = value;
- }
- return value;
- }
-
- Iterable<K> get keys {
- return new MappedIterable<_KeyValuePair<K, V>, K>(
- _list, (_KeyValuePair<K, V> entry) => entry.key);
- }
-
-
- Iterable<V> get values {
- return new MappedIterable<_KeyValuePair<K, V>, V>(
- _list, (_KeyValuePair<K, V> entry) => entry.value);
- }
-
- void forEach(void f(K key, V value)) {
- _list.forEach((_KeyValuePair<K, V> entry) {
- f(entry.key, entry.value);
- });
- }
-
- bool containsKey(K key) {
- return _map.containsKey(key);
- }
-
- bool containsValue(V value) {
- return _list.any((_KeyValuePair<K, V> entry) {
- return (entry.value == value);
- });
- }
-
- int get length {
- return _map.length;
- }
-
- bool get isEmpty {
- return length == 0;
- }
-
- void clear() {
- _map.clear();
- _list.clear();
- }
-
- String toString() {
- return Maps.mapToString(this);
- }
-}
-
« 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