New implementation of {,Linked}Hash{Set,Map}.

sdk/lib/collection/map.dart

-// Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-
-part of dart.collection;
-
-
-/**
- * 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);
-  }
-}