Revert "Make LinkedHashMap also have a factory constructor and be customizable"

runtime/lib/collection_patch.dart

Index: runtime/lib/collection_patch.dart
diff --git a/runtime/lib/collection_patch.dart b/runtime/lib/collection_patch.dart
index ee4e86ee391a4fa748f1be4e6e7112d91f1b3fa6..3b3bcc089f41ee5237c695fff916420420072575 100644
--- a/runtime/lib/collection_patch.dart
+++ b/runtime/lib/collection_patch.dart
@@ -4,35 +4,25 @@
 
 patch class HashMap<K, V> {
   /* patch */ factory HashMap({ bool equals(K key1, K key2),
-                                int hashCode(K key),
-                                bool isValidKey(potentialKey) }) {
-    if (isValidKey == null) {
-      if (hashCode == null) {
-        if (equals == null) {
-          return new _HashMap<K, V>();
-        }
-        if (identical(identical, equals)) {
-          return new _IdentityHashMap<K, V>();
-        }
-        hashCode = _defaultHashCode;
-      } else if (equals == null) {
-        equals = _defaultEquals;
-      }
-    } else {
-      if (hashCode == null) {
-        hashCode = _defaultHashCode;
-      }
+                                int hashCode(K key) }) {
+    if (hashCode == null) {
       if (equals == null) {
-        equals = _defaultEquals;
+        return new _HashMapImpl<K, V>();
+      }
+      if (identical(identical, equals)) {
+        return new _IdentityHashMap<K, V>();
       }
+      hashCode = _defaultHashCode;
+    } else if (equals == null) {
+      equals = _defaultEquals;
     }
-    return new _CustomHashMap<K, V>(equals, hashCode, isValidKey);
+    return new _CustomHashMap<K, V>(equals, hashCode);
   }
 }
 
 const int _MODIFICATION_COUNT_MASK = 0x3fffffff;
 
-class _HashMap<K, V> implements HashMap<K, V> {
+class _HashMapImpl<K, V> implements HashMap<K, V> {
   static const int _INITIAL_CAPACITY = 8;
 
   int _elementCount = 0;
@@ -154,7 +144,11 @@ class _HashMap<K, V> implements HashMap<K, V> {
     while (entry != null) {
       _HashMapEntry next = entry.next;
       if (hashCode == entry.hashCode && entry.key == key) {
-        _removeEntry(entry, previous, index);
+        if (previous == null) {
+          buckets[index] = next;
+        } else {
+          previous.next = next;
+        }
         _elementCount--;
         _modificationCount =
             (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
@@ -172,16 +166,6 @@ class _HashMap<K, V> implements HashMap<K, V> {
     _modificationCount = (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
   }
 
-  void _removeEntry(_HashMapEntry entry,
-                    _HashMapEntry previousInBucket,
-                    int bucketIndex) {
-    if (previousInBucket == null) {
-      _buckets[bucketIndex] = entry.next;
-    } else {
-      previousInBucket.next = entry.next;
-    }
-  }
-
   void _addEntry(List buckets, int index, int length,
                  K key, V value, int hashCode) {
     _HashMapEntry entry =
@@ -217,15 +201,12 @@ class _HashMap<K, V> implements HashMap<K, V> {
   String toString() => Maps.mapToString(this);
 }
 
-class _CustomHashMap<K, V> extends _HashMap<K, V> {
+class _CustomHashMap<K, V> extends _HashMapImpl<K, V> {
   final _Equality<K> _equals;
   final _Hasher<K> _hashCode;
-  final _Predicate _validKey;
-  _CustomHashMap(this._equals, this._hashCode, validKey)
-      : _validKey = (validKey != null) ? validKey : new _TypeTest<K>().test;
+  _CustomHashMap(this._equals, this._hashCode);
 
   bool containsKey(Object key) {
-    if (!_validKey(key)) return false;
     int hashCode = _hashCode(key);
     List buckets = _buckets;
     int index = hashCode & (buckets.length - 1);
@@ -238,7 +219,6 @@ class _CustomHashMap<K, V> extends _HashMap<K, V> {
   }
 
   V operator[](Object key) {
-    if (!_validKey(key)) return null;
     int hashCode = _hashCode(key);
     List buckets = _buckets;
     int index = hashCode & (buckets.length - 1);
@@ -291,7 +271,6 @@ class _CustomHashMap<K, V> extends _HashMap<K, V> {
   }
 
   V remove(Object key) {
-    if (!_validKey(key)) return null;
     int hashCode = _hashCode(key);
     List buckets = _buckets;
     int index = hashCode & (buckets.length - 1);
@@ -300,7 +279,11 @@ class _CustomHashMap<K, V> extends _HashMap<K, V> {
     while (entry != null) {
       _HashMapEntry next = entry.next;
       if (hashCode == entry.hashCode && _equals(entry.key, key)) {
-        _removeEntry(entry, previous, index);
+        if (previous == null) {
+          buckets[index] = next;
+        } else {
+          previous.next = next;
+        }
         _elementCount--;
         _modificationCount =
             (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
@@ -315,7 +298,7 @@ class _CustomHashMap<K, V> extends _HashMap<K, V> {
   String toString() => Maps.mapToString(this);
 }
 
-class _IdentityHashMap<K, V> extends _HashMap<K, V> {
+class _IdentityHashMap<K, V> extends _HashMapImpl<K, V> {
   bool containsKey(Object key) {
     int hashCode = key.hashCode;
     List buckets = _buckets;
@@ -389,7 +372,11 @@ class _IdentityHashMap<K, V> extends _HashMap<K, V> {
     while (entry != null) {
       _HashMapEntry next = entry.next;
       if (hashCode == entry.hashCode && identical(entry.key, key)) {
-        _removeEntry(entry, previous, index);
+        if (previous == null) {
+          buckets[index] = next;
+        } else {
+          previous.next = next;
+        }
         _elementCount--;
         _modificationCount =
             (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
@@ -609,11 +596,11 @@ class _LinkedHashMapValueIterable<V> extends IterableBase<V> {
 }
 
 abstract class _LinkedHashMapIterator<T> implements Iterator<T> {
-  final LinkedHashMap _map;
+  final _LinkedHashMap _map;
   var _next;
   T _current;
   int _modificationCount;
-  _LinkedHashMapIterator(LinkedHashMap map)
+  _LinkedHashMapIterator(_LinkedHashMap map)
       : _map = map,
         _current = null,
         _next = map._nextEntry,
@@ -639,12 +626,12 @@ abstract class _LinkedHashMapIterator<T> implements Iterator<T> {
 }
 
 class _LinkedHashMapKeyIterator<K> extends _LinkedHashMapIterator<K> {
-  _LinkedHashMapKeyIterator(LinkedHashMap map) : super(map);
+  _LinkedHashMapKeyIterator(_LinkedHashMap map) : super(map);
   K _getValue(_LinkedHashMapEntry entry) => entry.key;
 }
 
 class _LinkedHashMapValueIterator<V> extends _LinkedHashMapIterator<V> {
-  _LinkedHashMapValueIterator(LinkedHashMap map) : super(map);
+  _LinkedHashMapValueIterator(_LinkedHashMap map) : super(map);
   V _getValue(_LinkedHashMapEntry entry) => entry.value;
 }
 
@@ -653,72 +640,153 @@ class _LinkedHashMapValueIterator<V> extends _LinkedHashMapIterator<V> {
  * A hash-based map that iterates keys and values in key insertion order.
  */
 patch class LinkedHashMap<K, V> {
+  static const int _INITIAL_CAPACITY = 8;
+  static const int _MODIFICATION_COUNT_MASK = 0x3fffffff;
+
+  int _elementCount = 0;
+  List<_HashMapEntry> _buckets = new List(_INITIAL_CAPACITY);
+  int _modificationCount = 0;
+
   var _nextEntry;
   var _previousEntry;
 
-  /* patch */ factory LinkedHashMap({ bool equals(K key1, K key2),
-                                      int hashCode(K key),
-                                      bool isValidKey(potentialKey) }) {
-    if (isValidKey == null) {
-      if (hashCode == null) {
-        if (equals == null) {
-          return new _LinkedHashMap<K, V>();
-        }
-        if (identical(identical, equals)) {
-          return new _LinkedIdentityHashMap<K, V>();
-        }
-        hashCode = _defaultHashCode;
-      } else if (equals == null) {
-        equals = _defaultEquals;
-      }
-    } else {
-      if (hashCode == null) {
-        hashCode = _defaultHashCode;
-      }
-      if (equals == null) {
-        equals = _defaultEquals;
-      }
-    }
-    return new _LinkedCustomHashMap<K, V>(equals, hashCode, isValidKey);
+  /* patch */ LinkedHashMap() {
+    _nextEntry = _previousEntry = this;
   }
-}
 
-// Methods that are exactly the same in all three linked hash map variants.
-abstract class _LinkedHashMapMixin<K, V> implements LinkedHashMap<K, V> {
-  var _nextEntry;
-  var _previousEntry;
+  /* patch */ int get length => _elementCount;
+  /* patch */ bool get isEmpty => _elementCount == 0;
+  /* patch */ bool get isNotEmpty => _elementCount != 0;
 
-  bool containsValue(Object value) {
-    int modificationCount = _modificationCount;
+  /* patch */ Iterable<K> get keys => new _LinkedHashMapKeyIterable<K>(this);
+  /* patch */ Iterable<V> get values => new _LinkedHashMapValueIterable<V>(this);
+
+  /* patch */ bool containsKey(Object key) {
+    int hashCode = key.hashCode;
+    List buckets = _buckets;
+    int index = hashCode & (buckets.length - 1);
+    _HashMapEntry entry = buckets[index];
+    while (entry != null) {
+      if (hashCode == entry.hashCode && entry.key == key) return true;
+      entry = entry.next;
+    }
+    return false;
+  }
+
+  /* patch */ bool containsValue(Object value) {
     var cursor = _nextEntry;
+    int modificationCount = _modificationCount;
     while (!identical(cursor, this)) {
       _HashMapEntry entry = cursor;
       if (entry.value == value) return true;
-      if (modificationCount != _modificationCount) {
-        throw new ConcurrentModificationError(this);
-      }
       cursor = cursor._nextEntry;
     }
     return false;
   }
 
-  void forEach(void action(K key, V value)) {
-    int modificationCount = _modificationCount;
+  /* patch */ V operator[](Object key) {
+    int hashCode = key.hashCode;
+    List buckets = _buckets;
+    int index = hashCode & (buckets.length - 1);
+    _HashMapEntry entry = buckets[index];
+    while (entry != null) {
+      if (hashCode == entry.hashCode && entry.key == key) {
+        return entry.value;
+      }
+      entry = entry.next;
+    }
+    return null;
+  }
+
+  /* patch */ void operator []=(K key, V value) {
+    int hashCode = key.hashCode;
+    List buckets = _buckets;
+    int length = buckets.length;
+    int index = hashCode & (length - 1);
+    _HashMapEntry entry = buckets[index];
+    while (entry != null) {
+      if (hashCode == entry.hashCode && entry.key == key) {
+        entry.value = value;
+        return;
+      }
+      entry = entry.next;
+    }
+    _addEntry(buckets, index, length, key, value, hashCode);
+  }
+
+  /* patch */ V putIfAbsent(K key, V ifAbsent()) {
+    int hashCode = key.hashCode;
+    List buckets = _buckets;
+    int length = buckets.length;
+    int index = hashCode & (length - 1);
+    _HashMapEntry entry = buckets[index];
+    while (entry != null) {
+      if (hashCode == entry.hashCode && entry.key == key) {
+        return entry.value;
+      }
+      entry = entry.next;
+    }
+    int stamp = _modificationCount;
+    V value = ifAbsent();
+    if (stamp == _modificationCount) {
+      _addEntry(buckets, index, length, key, value, hashCode);
+    } else {
+      this[key] = value;
+    }
+    return value;
+  }
+
+  /* patch */ void addAll(Map<K, V> other) {
+    other.forEach((K key, V value) {
+      this[key] = value;
+    });
+  }
+
+  /* patch */ void forEach(void action(K key, V value)) {
+    int stamp = _modificationCount;
     var cursor = _nextEntry;
     while (!identical(cursor, this)) {
       _HashMapEntry entry = cursor;
       action(entry.key, entry.value);
-      if (modificationCount != _modificationCount) {
+      if (stamp != _modificationCount) {
         throw new ConcurrentModificationError(this);
       }
       cursor = cursor._nextEntry;
     }
   }
 
-  void clear() {
-    _nextEntry = _previousEntry = this;
+  /* patch */ V remove(Object key) {
+    int hashCode = key.hashCode;
+    List buckets = _buckets;
+    int index = hashCode & (buckets.length - 1);
+    _LinkedHashMapEntry entry = buckets[index];
+    _HashMapEntry previous = null;
+    while (entry != null) {
+      _HashMapEntry next = entry.next;
+      if (hashCode == entry.hashCode && entry.key == key) {
+        if (previous == null) {
+          buckets[index] = next;
+        } else {
+          previous.next = next;
+        }
+        entry._previousEntry._nextEntry = entry._nextEntry;
+        entry._nextEntry._previousEntry = entry._previousEntry;
+        entry._nextEntry = entry._previousEntry = null;
+        _elementCount--;
+        _modificationCount =
+            (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
+        return entry.value;
+      }
+      previous = entry;
+      entry = next;
+    }
+    return null;
+  }
+
+  /* patch */ void clear() {
     _elementCount = 0;
-    _buckets = new List(_HashMap._INITIAL_CAPACITY);
+    _nextEntry = _previousEntry = this;
+    _buckets = new List(_INITIAL_CAPACITY);
     _modificationCount = (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
   }
 
@@ -736,50 +804,26 @@ abstract class _LinkedHashMapMixin<K, V> implements LinkedHashMap<K, V> {
     _modificationCount = (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
   }
 
-  void _removeEntry(_LinkedHashMapEntry entry,
-                    _HashMapEntry previousInBucket,
-                    int bucketIndex) {
-    var previousInChain = entry._previousEntry;
-    var nextInChain = entry._nextEntry;
-    previousInChain._nextEntry = nextInChain;
-    nextInChain._previousEntry = previousInChain;
-    if (previousInBucket == null) {
-      _buckets[bucketIndex] = entry.next;
-    } else {
-      previousInBucket.next = entry.next;
+  void _resize() {
+    List oldBuckets = _buckets;
+    int oldLength = oldBuckets.length;
+    int newLength = oldLength << 1;
+    List newBuckets = new List(newLength);
+    for (int i = 0; i < oldLength; i++) {
+      _HashMapEntry entry = oldBuckets[i];
+      while (entry != null) {
+        _HashMapEntry next = entry.next;
+        int hashCode = entry.hashCode;
+        int index = hashCode & (newLength - 1);
+        entry.next = newBuckets[index];
+        newBuckets[index] = entry;
+        entry = next;
+      }
     }
-  }
-
-
-  Iterable<K> get keys => new _LinkedHashMapKeyIterable<K>(this);
-  Iterable<V> get values => new _LinkedHashMapValueIterable<V>(this);
-}
-
-class _LinkedHashMap<K, V> extends _HashMap<K, V>
-                           with _LinkedHashMapMixin<K, V> {
-  _LinkedHashMap() {
-    _nextEntry = _previousEntry = this;
-  }
-}
-
-class _LinkedIdentityHashMap<K, V> extends _IdentityHashMap<K, V>
-                                   with _LinkedHashMapMixin<K, V> {
-  _LinkedIdentityHashMap() {
-    _nextEntry = _previousEntry = this;
-  }
-}
-
-class _LinkedCustomHashMap<K, V> extends _CustomHashMap<K, V>
-                                 with _LinkedHashMapMixin<K, V> {
-  _LinkedCustomHashMap(bool equals(K key1, K key2),
-                       int hashCode(K key),
-                       bool isValidKey(potentialKey))
-      : super(equals, hashCode, isValidKey) {
-    _nextEntry = _previousEntry = this;
+    _buckets = newBuckets;
   }
 }
 
-
 patch class LinkedHashSet<E> extends _HashSetBase<E> {
   static const int _INITIAL_CAPACITY = 8;
   _LinkedHashTable<E> _table;