Revert "Reapply "New implementation of {,Linked}Hash{Set,Map}.""

sdk/lib/collection/map.dart

Index: sdk/lib/collection/map.dart
diff --git a/pkg/serialization/lib/src/polyfill_identity_set.dart b/sdk/lib/collection/map.dart
similarity index 57%
copy from pkg/serialization/lib/src/polyfill_identity_set.dart
copy to sdk/lib/collection/map.dart
index 56a78651d5649eafea8ccb6d4707d95bc24bf2e8..1beaf2b9aa785770b43daa6fd446f035c46c595e 100644
--- a/pkg/serialization/lib/src/polyfill_identity_set.dart
+++ b/sdk/lib/collection/map.dart
@@ -1,14 +1,47 @@
-// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// 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.
 
-// TODO(alanknight): Replace with proper identity collection. Issue 4161
-library identity_set;
+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);
+}
 
-import 'dart:collection';
 
 // Hash map implementation with open addressing and quadratic probing.
-class IdentityMap<K, V> implements HashMap<K, V> {
+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
@@ -47,16 +80,16 @@ class IdentityMap<K, V> implements HashMap<K, V> {
   // The initial capacity of a hash map.
   static const int _INITIAL_CAPACITY = 8;  // must be power of 2
 
-  IdentityMap() {
+  _HashMapImpl() {
     _numberOfEntries = 0;
     _numberOfDeleted = 0;
     _loadLimit = _computeLoadLimit(_INITIAL_CAPACITY);
-    _keys = new List(_INITIAL_CAPACITY);
-    _values = new List<V>(_INITIAL_CAPACITY);
+    _keys = new List.fixedLength(_INITIAL_CAPACITY);
+    _values = new List<V>.fixedLength(_INITIAL_CAPACITY);
   }
 
-  factory IdentityMap.from(Map<K, V> other) {
-    Map<K, V> result = new IdentityMap<K, V>();
+  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;
   }
@@ -90,7 +123,7 @@ class IdentityMap<K, V> implements HashMap<K, V> {
         if (insertionIndex < 0) return hash;
         // If we did find an insertion slot before, return it.
         return insertionIndex;
-      } else if (identical(existingKey, key)) {
+      } else if (existingKey == key) {
         // The key is already in the map. Return its slot.
         return hash;
       } else if ((insertionIndex < 0) &&
@@ -120,7 +153,7 @@ class IdentityMap<K, V> implements HashMap<K, V> {
       // 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 (identical(existingKey, key)) return hash;
+      if (existingKey == key) return hash;
       // Go to the next probe.
       hash = _nextProbe(hash, numberOfProbes++, _keys.length);
       // _ensureCapacity has guaranteed the following cannot happen.
@@ -158,8 +191,8 @@ class IdentityMap<K, V> implements HashMap<K, V> {
     _loadLimit = _computeLoadLimit(newCapacity);
     List oldKeys = _keys;
     List<V> oldValues = _values;
-    _keys = new List(newCapacity);
-    _values = new List<V>(newCapacity);
+    _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];
@@ -234,54 +267,93 @@ class IdentityMap<K, V> implements HashMap<K, V> {
   }
 
   void forEach(void f(K key, V value)) {
-    int length = _keys.length;
-    for (int i = 0; i < length; i++) {
-      var key = _keys[i];
-      if ((key != null) && (!identical(key, _DELETED_KEY))) {
-        f(key, _values[i]);
-      }
+    Iterator<int> it = new _HashMapImplIndexIterator(this);
+    while (it.moveNext()) {
+      f(_keys[it.current], _values[it.current]);
     }
   }
 
+  Iterable<K> get keys => new _HashMapImplKeyIterable<K>(this);
 
-  Collection<K> get keys {
-    List<K> list = new List<K>(length);
-    int i = 0;
-    forEach((K key, V value) {
-      list[i++] = key;
-    });
-    return list;
-  }
-
-  Collection<V> get values {
-    List<V> list = new List<V>(length);
-    int i = 0;
-    forEach((K key, V value) {
-      list[i++] = value;
-    });
-    return list;
-  }
+  Iterable<V> get values => new _HashMapImplValueIterable<V>(this);
 
   bool containsKey(K key) {
     return (_probeForLookup(key) != -1);
   }
 
-  bool containsValue(V value) {
-    int length = _values.length;
-    for (int i = 0; i < length; i++) {
-      var key = _keys[i];
-      if ((key != null) && (!identical(key, _DELETED_KEY))) {
-        if (_values[i] == value) return true;
+  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;
   }
 
-  String toString() {
-    return Maps.mapToString(this);
+  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.
@@ -303,4 +375,100 @@ class _KeyValuePair<K, V> {
 
   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);
+  }
+}