Make LinkedHashMap also have a factory constructor and be customizable

sdk/lib/_internal/lib/collection_patch.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.
 
 // Patch file for dart:collection classes.
 import 'dart:_foreign_helper' show JS;
 
 patch class HashMap<K, V> {
   patch factory HashMap({ bool equals(K key1, K key2), int hashCode(K key) }) {
     if (hashCode == null) {
       if (equals == null) {
-        return new _HashMapImpl<K, V>();
+        return new _Hash<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);
   }
 }
 
-class _HashMapImpl<K, V> implements HashMap<K, V> {
+class _Hash<K, V> implements HashMap<K, V> {
   int _length = 0;
 
   // The hash map contents are divided into three parts: one part for
   // string keys, one for numeric keys, and one for the rest. String
   // and numeric keys map directly to their values, but the rest of
   // the entries are stored in bucket lists of the form:
   //
   //    [key-0, value-0, key-1, value-1, ...]
   //
   // where all keys in the same bucket share the same hash code.
   var _strings;
   var _nums;
   var _rest;
 
   // When iterating over the hash map, it is very convenient to have a
   // list of all the keys. We cache that on the instance and clear the
   // the cache whenever the key set changes. This is also used to
   // guard against concurrent modifications.
   List _keys;
 
-  _HashMapImpl();
+  _Hash();
 
   int get length => _length;
   bool get isEmpty => _length == 0;
   bool get isNotEmpty => !isEmpty;
 
   Iterable<K> get keys {
     return new HashMapKeyIterable<K>(this);
   }
 
   Iterable<V> get values {
@@ skipping 261 matching lines @@
     var table = JS('var', 'Object.create(null)');
     // Attempt to force the hash table into 'dictionary' mode by
     // adding a property to it and deleting it again.
     var temporaryKey = '<non-identifier-key>';
     _setTableEntry(table, temporaryKey, table);
     _deleteTableEntry(table, temporaryKey);
     return table;
   }
 }
 
-class _IdentityHashMap<K, V> extends _HashMapImpl<K, V> {
+class _IdentityHashMap<K, V> extends _Hash<K, V> {
   int _findBucketIndex(var bucket, var key) {
     if (bucket == null) return -1;
     int length = JS('int', '#.length', bucket);
     for (int i = 0; i < length; i += 2) {
       if (identical(JS('var', '#[#]', bucket, i), key)) return i;
     }
     return -1;
   }
 }
 
-class _CustomHashMap<K, V> extends _HashMapImpl<K, V> {
+class _CustomHashMap<K, V> extends _Hash<K, V> {
   final _Equality<K> _equals;
   final _Hasher<K> _hashCode;
   _CustomHashMap(this._equals, this._hashCode);
 
   int _computeHashCode(var key) {
     // We force the hash codes to be unsigned 30-bit integers to avoid
     // issues with problematic keys like '__proto__'. Another option
     // would be to throw an exception if the hash code isn't a number.
     return JS('int', '# & 0x3ffffff', _hashCode(key));
   }
@@ skipping 59 matching lines @@
       // TODO(kasperl): For now, we have to tell the type inferrer to
       // treat the result of doing offset + 1 as an int. Otherwise, we
       // get unnecessary bailout code.
       _offset = JS('int', '#', offset + 1);
       return true;
     }
   }
 }
 
 patch class LinkedHashMap<K, V> {
+  patch factory LinkedHashMap({ bool equals(K key1, K key2),
+                                int hashCode(K key) }) {
+    if (hashCode == null) {
+      if (equals == null) {
+        return new _LinkedHash<K, V>();
+      }
+      if (identical(identical, equals)) {
+        return new _LinkedIdentityHashMap<K, V>();
+      }
+      hashCode = _defaultHashCode;
+    } else if (equals == null) {
+      equals = _defaultEquals;
+    }
+    return new _LinkedCustomHashMap<K, V>(equals, hashCode);
+  }
+}
+
+class _LinkedHash<K, V> implements LinkedHashMap<K, V> {
   int _length = 0;
 
   // The hash map contents are divided into three parts: one part for
   // string keys, one for numeric keys, and one for the rest. String
   // and numeric keys map directly to their linked cells, but the rest
   // of the entries are stored in bucket lists of the form:
   //
   //    [cell-0, cell-1, ...]
   //
   // where all keys in the same bucket share the same hash code.
   var _strings;
   var _nums;
   var _rest;
 
   // The keys and values are stored in cells that are linked together
   // to form a double linked list.
   LinkedHashMapCell _first;
   LinkedHashMapCell _last;
 
   // We track the number of modifications done to the key set of the
   // hash map to be able to throw when the map is modified while being
   // iterated over.
   int _modifications = 0;
 
-  patch LinkedHashMap();
+  _LinkedHash();
 
-  patch int get length => _length;
-  patch bool get isEmpty => _length == 0;
-  patch bool get isNotEmpty => !isEmpty;
+  int get length => _length;
+  bool get isEmpty => _length == 0;
+  bool get isNotEmpty => !isEmpty;
 
 
-  patch Iterable<K> get keys {
+  Iterable<K> get keys {
     return new LinkedHashMapKeyIterable<K>(this);
   }
 
-  patch Iterable<V> get values {
+  Iterable<V> get values {
     return keys.map((each) => this[each]);
   }
 
-  patch bool containsKey(Object key) {
+  bool containsKey(Object key) {
     if (_isStringKey(key)) {
       var strings = _strings;
       if (strings == null) return false;
       LinkedHashMapCell cell = _getTableEntry(strings, key);
       return cell != null;
     } else if (_isNumericKey(key)) {
       var nums = _nums;
       if (nums == null) return false;
       LinkedHashMapCell cell = _getTableEntry(nums, key);
       return cell != null;
     } else {
       var rest = _rest;
       if (rest == null) return false;
       var bucket = _getBucket(rest, key);
       return _findBucketIndex(bucket, key) >= 0;
     }
   }
 
-  patch bool containsValue(Object value) {
+  bool containsValue(Object value) {
     return keys.any((each) => this[each] == value);
   }
 
-  patch void addAll(Map<K, V> other) {
+  void addAll(Map<K, V> other) {
     other.forEach((K key, V value) {
       this[key] = value;
     });
   }
 
-  patch V operator[](Object key) {
+  V operator[](Object key) {
     if (_isStringKey(key)) {
       var strings = _strings;
       if (strings == null) return null;
       LinkedHashMapCell cell = _getTableEntry(strings, key);
       return (cell == null) ? null : cell._value;
     } else if (_isNumericKey(key)) {
       var nums = _nums;
       if (nums == null) return null;
       LinkedHashMapCell cell = _getTableEntry(nums, key);
       return (cell == null) ? null : cell._value;
     } else {
       var rest = _rest;
       if (rest == null) return null;
       var bucket = _getBucket(rest, key);
       int index = _findBucketIndex(bucket, key);
       if (index < 0) return null;
       LinkedHashMapCell cell = JS('var', '#[#]', bucket, index);
       return cell._value;
     }
   }
 
-  patch void operator[]=(K key, V value) {
+  void operator[]=(K key, V value) {
     if (_isStringKey(key)) {
       var strings = _strings;
       if (strings == null) _strings = strings = _newHashTable();
       _addHashTableEntry(strings, key, value);
     } else if (_isNumericKey(key)) {
       var nums = _nums;
       if (nums == null) _nums = nums = _newHashTable();
       _addHashTableEntry(nums, key, value);
     } else {
       var rest = _rest;
       if (rest == null) _rest = rest = _newHashTable();
       var hash = _computeHashCode(key);
       var bucket = JS('var', '#[#]', rest, hash);
       if (bucket == null) {
         LinkedHashMapCell cell = _newLinkedCell(key, value);
         _setTableEntry(rest, hash, JS('var', '[#]', cell));
       } else {
         int index = _findBucketIndex(bucket, key);
         if (index >= 0) {
           LinkedHashMapCell cell = JS('var', '#[#]', bucket, index);
           cell._value = value;
         } else {
           LinkedHashMapCell cell = _newLinkedCell(key, value);
           JS('void', '#.push(#)', bucket, cell);
         }
       }
     }
   }
 
-  patch V putIfAbsent(K key, V ifAbsent()) {
+  V putIfAbsent(K key, V ifAbsent()) {
     if (containsKey(key)) return this[key];
     V value = ifAbsent();
     this[key] = value;
     return value;
   }
 
-  patch V remove(Object key) {
+  V remove(Object key) {
     if (_isStringKey(key)) {
       return _removeHashTableEntry(_strings, key);
     } else if (_isNumericKey(key)) {
       return _removeHashTableEntry(_nums, key);
     } else {
       var rest = _rest;
       if (rest == null) return null;
       var bucket = _getBucket(rest, key);
       int index = _findBucketIndex(bucket, key);
       if (index < 0) return null;
       // Use splice to remove the [cell] element at the index and
       // unlink the cell before returning its value.
       LinkedHashMapCell cell = JS('var', '#.splice(#, 1)[0]', bucket, index);
       _unlinkCell(cell);
       // TODO(kasperl): Consider getting rid of the bucket list when
       // the length reaches zero.
       return cell._value;
     }
   }
 
-  patch void clear() {
+  void clear() {
     if (_length > 0) {
       _strings = _nums = _rest = _first = _last = null;
       _length = 0;
       _modified();
     }
   }
 
-  patch void forEach(void action(K key, V value)) {
+  void forEach(void action(K key, V value)) {
     LinkedHashMapCell cell = _first;
     int modifications = _modifications;
     while (cell != null) {
       action(cell._key, cell._value);
       if (modifications != _modifications) {
         throw new ConcurrentModificationError(this);
       }
       cell = cell._next;
     }
   }
@@ skipping 62 matching lines @@
     return key is String && key != '__proto__';
   }
 
   static bool _isNumericKey(var key) {
     // Only treat unsigned 30-bit integers as numeric keys. This way,
     // we avoid converting them to strings when we use them as keys in
     // the JavaScript hash table object.
     return key is num && JS('bool', '(# & 0x3ffffff) === #', key, key);
   }
 
-  static int _computeHashCode(var key) {
+  int _computeHashCode(var key) {
     // We force the hash codes to be unsigned 30-bit integers to avoid
     // issues with problematic keys like '__proto__'. Another option
     // would be to throw an exception if the hash code isn't a number.
     return JS('int', '# & 0x3ffffff', key.hashCode);
   }
 
   static _getTableEntry(var table, var key) {
     return JS('var', '#[#]', table, key);
   }
 
   static void _setTableEntry(var table, var key, var value) {
     assert(value != null);
     JS('void', '#[#] = #', table, key, value);
   }
 
   static void _deleteTableEntry(var table, var key) {
     JS('void', 'delete #[#]', table, key);
   }
 
-  static List _getBucket(var table, var key) {
+  List _getBucket(var table, var key) {
     var hash = _computeHashCode(key);
     return JS('var', '#[#]', table, hash);
   }
 
-  static int _findBucketIndex(var bucket, var key) {
+  int _findBucketIndex(var bucket, var key) {
     if (bucket == null) return -1;
     int length = JS('int', '#.length', bucket);
     for (int i = 0; i < length; i++) {
       LinkedHashMapCell cell = JS('var', '#[#]', bucket, i);
       if (cell._key == key) return i;
     }
     return -1;
   }
 
   static _newHashTable() {
     // Create a new JavaScript object to be used as a hash table. Use
     // Object.create to avoid the properties on Object.prototype
     // showing up as entries.
     var table = JS('var', 'Object.create(null)');
     // Attempt to force the hash table into 'dictionary' mode by
     // adding a property to it and deleting it again.
     var temporaryKey = '<non-identifier-key>';
     _setTableEntry(table, temporaryKey, table);
     _deleteTableEntry(table, temporaryKey);
     return table;
   }
+
+  String toString() => Maps.mapToString(this);
+}
+
+class _LinkedIdentityHashMap<K, V> extends _LinkedHash<K, V> {
+  int _findBucketIndex(var bucket, var key) {
+    if (bucket == null) return -1;
+    int length = JS('int', '#.length', bucket);
+    for (int i = 0; i < length; i++) {
+      LinkedHashMapCell cell = JS('var', '#[#]', bucket, i);
+      if (identical(cell._key, key)) return i;
+    }
+    return -1;
+  }
+}
+
+class _LinkedCustomHashMap<K, V> extends _LinkedHash<K, V> {
+  final _Equality<K> _equals;
+  final _Hasher<K> _hashCode;
+  _LinkedCustomHashMap(this._equals, this._hashCode);
+
+  int _computeHashCode(var key) {
+    // We force the hash codes to be unsigned 30-bit integers to avoid
+    // issues with problematic keys like '__proto__'. Another option
+    // would be to throw an exception if the hash code isn't a number.
+    return JS('int', '# & 0x3ffffff', _hashCode(key));
+  }
+
+  int _findBucketIndex(var bucket, var key) {
+    if (bucket == null) return -1;
+    int length = JS('int', '#.length', bucket);
+    for (int i = 0; i < length; i++) {
+      LinkedHashMapCell cell = JS('var', '#[#]', bucket, i);
+      if (_equals(cell._key, key)) return i;
+    }
+    return -1;
+  }
 }
 
 class LinkedHashMapCell {
   final _key;
   var _value;
 
   LinkedHashMapCell _next;
   LinkedHashMapCell _previous;
 
   LinkedHashMapCell(this._key, this._value);
@@ skipping 658 matching lines @@
     } else if (_cell == null) {
       _current = null;
       return false;
     } else {
       _current = _cell._element;
       _cell = _cell._next;
       return true;
     }
   }
 }