content: // 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),
                            bool isValidKey(potentialKey) }) {
      if (isValidKey == null) {
        if (hashCode == null) {
          if (equals == null) {
            return new _HashMap<K, V>();
          }
          hashCode = _defaultHashCode;
        } else {
          if (identical(identityHashCode, hashCode) &&
              identical(identical, equals)) {
            return new _IdentityHashMap<K, V>();
          }
          if (equals == null) {
            equals = _defaultEquals;
          }
        }
      } else {
        if (hashCode == null) {
          hashCode = _defaultHashCode;
        }
        if (equals == null) {
          equals = _defaultEquals;
        }
      }
      return new _CustomHashMap<K, V>(equals, hashCode, isValidKey);
    }
  
    patch factory HashMap.identity() = _IdentityHashMap<K, V>;
  }
  
  class _HashMap<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;
  
    _HashMap();
  
  
    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 {
      return keys.map((each) => this[each]);
    }
  
    bool containsKey(Object key) {
      if (_isStringKey(key)) {
        var strings = _strings;
        return (strings == null) ? false : _hasTableEntry(strings, key);
      } else if (_isNumericKey(key)) {
        var nums = _nums;
        return (nums == null) ? false : _hasTableEntry(nums, key);
      } else {
        var rest = _rest;
        if (rest == null) return false;
        var bucket = _getBucket(rest, key);
        return _findBucketIndex(bucket, key) >= 0;
      }
    }
  
    bool containsValue(Object value) {
      return _computeKeys().any((each) => this[each] == value);
    }
  
    void addAll(Map<K, V> other) {
      other.forEach((K key, V value) {
        this[key] = value;
      });
    }
  
    V operator[](Object key) {
      if (_isStringKey(key)) {
        var strings = _strings;
        return (strings == null) ? null : _getTableEntry(strings, key);
      } else if (_isNumericKey(key)) {
        var nums = _nums;
        return (nums == null) ? null : _getTableEntry(nums, key);
      } else {
        var rest = _rest;
        if (rest == null) return null;
        var bucket = _getBucket(rest, key);
        int index = _findBucketIndex(bucket, key);
        return (index < 0) ? null : JS('var', '#[#]', bucket, index + 1);
      }
    }
  
    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) {
          _setTableEntry(rest, hash, JS('var', '[#, #]', key, value));
          _length++;
          _keys = null;
        } else {
          int index = _findBucketIndex(bucket, key);
          if (index >= 0) {
            JS('void', '#[#] = #', bucket, index + 1, value);
          } else {
            JS('void', '#.push(#, #)', bucket, key, value);
            _length++;
            _keys = null;
          }
        }
      }
    }
  
    V putIfAbsent(K key, V ifAbsent()) {
      if (containsKey(key)) return this[key];
      V value = ifAbsent();
      this[key] = value;
      return value;
    }
  
    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;
        // TODO(kasperl): Consider getting rid of the bucket list when
        // the length reaches zero.
        _length--;
        _keys = null;
        // Use splice to remove the two [key, value] elements at the
        // index and return the value.
        return JS('var', '#.splice(#, 2)[1]', bucket, index);
      }
    }
  
    void clear() {
      if (_length > 0) {
        _strings = _nums = _rest = _keys = null;
        _length = 0;
      }
    }
  
    void forEach(void action(K key, V value)) {
      List keys = _computeKeys();
      for (int i = 0, length = keys.length; i < length; i++) {
        var key = JS('var', '#[#]', keys, i);
        action(key, this[key]);
        if (JS('bool', '# !== #', keys, _keys)) {
          throw new ConcurrentModificationError(this);
        }
      }
    }
  
    List _computeKeys() {
      if (_keys != null) return _keys;
      List result = new List(_length);
      int index = 0;
  
      // Add all string keys to the list.
      var strings = _strings;
      if (strings != null) {
        var names = JS('var', 'Object.getOwnPropertyNames(#)', strings);
        int entries = JS('int', '#.length', names);
        for (int i = 0; i < entries; i++) {
          String key = JS('String', '#[#]', names, i);
          JS('void', '#[#] = #', result, index, key);
          index++;
        }
      }
  
      // Add all numeric keys to the list.
      var nums = _nums;
      if (nums != null) {
        var names = JS('var', 'Object.getOwnPropertyNames(#)', nums);
        int entries = JS('int', '#.length', names);
        for (int i = 0; i < entries; i++) {
          // Object.getOwnPropertyNames returns a list of strings, so we
          // have to convert the keys back to numbers (+).
          num key = JS('num', '+#[#]', names, i);
          JS('void', '#[#] = #', result, index, key);
          index++;
        }
      }
  
      // Add all the remaining keys to the list.
      var rest = _rest;
      if (rest != null) {
        var names = JS('var', 'Object.getOwnPropertyNames(#)', rest);
        int entries = JS('int', '#.length', names);
        for (int i = 0; i < entries; i++) {
          var key = JS('String', '#[#]', names, i);
          var bucket = JS('var', '#[#]', rest, key);
          int length = JS('int', '#.length', bucket);
          for (int i = 0; i < length; i += 2) {
            var key = JS('var', '#[#]', bucket, i);
            JS('void', '#[#] = #', result, index, key);
            index++;
          }
        }
      }
      assert(index == _length);
      return _keys = result;
    }
  
    void _addHashTableEntry(var table, K key, V value) {
      if (!_hasTableEntry(table, key)) {
        _length++;
        _keys = null;
      }
      _setTableEntry(table, key, value);
    }
  
    V _removeHashTableEntry(var table, Object key) {
      if (table != null && _hasTableEntry(table, key)) {
        V value = _getTableEntry(table, key);
        _deleteTableEntry(table, key);
        _length--;
        _keys = null;
        return value;
      } else {
        return null;
      }
    }
  
    static bool _isStringKey(var key) {
      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);
    }
  
    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 bool _hasTableEntry(var table, var key) {
      var entry = JS('var', '#[#]', table, key);
      // We take care to only store non-null entries in the table, so we
      // can check if the table has an entry for the given key with a
      // simple null check.
      return entry != null;
    }
  
    static _getTableEntry(var table, var key) {
      var entry = JS('var', '#[#]', table, key);
      // We store the table itself as the entry to signal that it really
      // is a null value, so we have to map back to null here.
      return JS('bool', '# === #', entry, table) ? null : entry;
    }
  
    static void _setTableEntry(var table, var key, var value) {
      // We only store non-null entries in the table, so we have to
      // change null values to refer to the table itself. Such values
      // will be recognized and mapped back to null on access.
      if (value == null) {
        // Do not update [value] with [table], otherwise our
        // optimizations could be confused by this opaque object being
        // now used for more things than storing and fetching from it.
        JS('void', '#[#] = #', table, key, table);
      } else {
        JS('void', '#[#] = #', table, key, value);
      }
    }
  
    static void _deleteTableEntry(var table, var key) {
      JS('void', 'delete #[#]', table, key);
    }
  
    List _getBucket(var table, var key) {
      var hash = _computeHashCode(key);
      return JS('var', '#[#]', table, hash);
    }
  
    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 (JS('var', '#[#]', bucket, i) == 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;
    }
  }
  
  class _IdentityHashMap<K, V> extends _HashMap<K, V> {
    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', identityHashCode(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 += 2) {
        if (identical(JS('var', '#[#]', bucket, i), key)) return i;
      }
      return -1;
    }
  }
  
  class _CustomHashMap<K, V> extends _HashMap<K, V> {
    final _Equality<K> _equals;
    final _Hasher<K> _hashCode;
    final _Predicate _validKey;
    _CustomHashMap(this._equals, this._hashCode, bool validKey(potentialKey))
        : _validKey = (validKey != null) ? validKey : ((v) => v is K);
  
    V operator[](Object key) {
      if (!_validKey(key)) return null;
      return super[key];
    }
  
    bool containsKey(Object key) {
      if (!_validKey(key)) return false;
      return super.containsKey(key);
    }
  
    V remove(Object key) {
      if (!_validKey(key)) return null;
      return super.remove(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', _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 += 2) {
        if (_equals(JS('var', '#[#]', bucket, i), key)) return i;
      }
      return -1;
    }
  
    String toString() => Maps.mapToString(this);
  }
  
  class HashMapKeyIterable<E> extends IterableBase<E>
                              implements EfficientLength {
    final _map;
    HashMapKeyIterable(this._map);
  
    int get length => _map._length;
    bool get isEmpty => _map._length == 0;
  
    Iterator<E> get iterator {
      return new HashMapKeyIterator<E>(_map, _map._computeKeys());
    }
  
    bool contains(Object element) {
      return _map.containsKey(element);
    }
  
    void forEach(void f(E element)) {
      List keys = _map._computeKeys();
      for (int i = 0, length = JS('int', '#.length', keys); i < length; i++) {
        f(JS('var', '#[#]', keys, i));
        if (JS('bool', '# !== #', keys, _map._keys)) {
          throw new ConcurrentModificationError(_map);
        }
      }
    }
  }
  
  class HashMapKeyIterator<E> implements Iterator<E> {
    final _map;
    final List _keys;
    int _offset = 0;
    E _current;
  
    HashMapKeyIterator(this._map, this._keys);
  
    E get current => _current;
  
    bool moveNext() {
      var keys = _keys;
      int offset = _offset;
      if (JS('bool', '# !== #', keys, _map._keys)) {
        throw new ConcurrentModificationError(_map);
      } else if (offset >= JS('int', '#.length', keys)) {
        _current = null;
        return false;
      } else {
        _current = JS('var', '#[#]', keys, offset);
        // 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),
                                  bool isValidKey(potentialKey) }) {
      if (isValidKey == null) {
        if (hashCode == null) {
          if (equals == null) {
            return new _LinkedHashMap<K, V>();
          }
          hashCode = _defaultHashCode;
        } else {
          if (identical(identityHashCode, hashCode) &&
              identical(identical, equals)) {
            return new _LinkedIdentityHashMap<K, V>();
          }
          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 factory LinkedHashMap.identity() = _LinkedIdentityHashMap<K, V>;
  }
  
  class _LinkedHashMap<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;
  
    _LinkedHash();
  
  
    int get length => _length;
    bool get isEmpty => _length == 0;
    bool get isNotEmpty => !isEmpty;
  
    Iterable<K> get keys {
      return new LinkedHashMapKeyIterable<K>(this);
    }
  
    Iterable<V> get values {
      return keys.map((each) => this[each]);
    }
  
    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;
      }
    }
  
    bool containsValue(Object value) {
      return keys.any((each) => this[each] == value);
    }
  
    void addAll(Map<K, V> other) {
      other.forEach((K key, V value) {
        this[key] = value;
      });
    }
  
    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;
      }
    }
  
    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);
          }
        }
      }
    }
  
    V putIfAbsent(K key, V ifAbsent()) {
      if (containsKey(key)) return this[key];
      V value = ifAbsent();
      this[key] = value;
      return value;
    }
  
    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;
      }
    }
  
    void clear() {
      if (_length > 0) {
        _strings = _nums = _rest = _first = _last = null;
        _length = 0;
        _modified();
      }
    }
  
    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;
      }
    }
  
    void _addHashTableEntry(var table, K key, V value) {
      LinkedHashMapCell cell = _getTableEntry(table, key);
      if (cell == null) {
        _setTableEntry(table, key, _newLinkedCell(key, value));
      } else {
        cell._value = value;
      }
    }
  
    V _removeHashTableEntry(var table, Object key) {
      if (table == null) return null;
      LinkedHashMapCell cell = _getTableEntry(table, key);
      if (cell == null) return null;
      _unlinkCell(cell);
      _deleteTableEntry(table, key);
      return cell._value;
    }
  
    void _modified() {
      // Value cycles after 2^30 modifications. If you keep hold of an
      // iterator for that long, you might miss a modification
      // detection, and iteration can go sour. Don't do that.
      _modifications = (_modifications + 1) & 0x3ffffff;
    }
  
    // Create a new cell and link it in as the last one in the list.
    LinkedHashMapCell _newLinkedCell(K key, V value) {
      LinkedHashMapCell cell = new LinkedHashMapCell(key, value);
      if (_first == null) {
        _first = _last = cell;
      } else {
        LinkedHashMapCell last = _last;
        cell._previous = last;
        _last = last._next = cell;
      }
      _length++;
      _modified();
      return cell;
    }
  
    // Unlink the given cell from the linked list of cells.
    void _unlinkCell(LinkedHashMapCell cell) {
      LinkedHashMapCell previous = cell._previous;
      LinkedHashMapCell next = cell._next;
      if (previous == null) {
        assert(cell == _first);
        _first = next;
      } else {
        previous._next = next;
      }
      if (next == null) {
        assert(cell == _last);
        _last = previous;
      } else {
        next._previous = previous;
      }
      _length--;
      _modified();
    }
  
    static bool _isStringKey(var key) {
      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);
    }
  
    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);
    }
  
    List _getBucket(var table, var key) {
      var hash = _computeHashCode(key);
      return JS('var', '#[#]', table, hash);
    }
  
    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 _LinkedHashMap<K, V> {
    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', identityHashCode(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 (identical(cell._key, key)) return i;
      }
      return -1;
    }
  }
  
  class _LinkedCustomHashMap<K, V> extends _LinkedHashMap<K, V> {
    final _Equality<K> _equals;
    final _Hasher<K> _hashCode;
    final _Predicate _validKey;
    _LinkedCustomHashMap(this._equals, this._hashCode,
                         bool validKey(potentialKey))
        : _validKey = (validKey != null) ? validKey : ((v) => v is K);
  
    V operator[](Object key) {
      if (!_validKey(key)) return null;
      return super[key];
    }
  
    bool containsKey(Object key) {
      if (!_validKey(key)) return false;
      return super.containsKey(key);
    }
  
    V remove(Object key) {
      if (!_validKey(key)) return null;
      return super.remove(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', _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);
  }
  
  class LinkedHashMapKeyIterable<E> extends IterableBase<E>
                                    implements EfficientLength {
    final _map;
    LinkedHashMapKeyIterable(this._map);
  
    int get length => _map._length;
    bool get isEmpty => _map._length == 0;
  
    Iterator<E> get iterator {
      return new LinkedHashMapKeyIterator<E>(_map, _map._modifications);
    }
  
    bool contains(Object element) {
      return _map.containsKey(element);
    }
  
    void forEach(void f(E element)) {
      LinkedHashMapCell cell = _map._first;
      int modifications = _map._modifications;
      while (cell != null) {
        f(cell._key);
        if (modifications != _map._modifications) {
          throw new ConcurrentModificationError(_map);
        }
        cell = cell._next;
      }
    }
  }
  
  class LinkedHashMapKeyIterator<E> implements Iterator<E> {
    final _map;
    final int _modifications;
    LinkedHashMapCell _cell;
    E _current;
  
    LinkedHashMapKeyIterator(this._map, this._modifications) {
      _cell = _map._first;
    }
  
    E get current => _current;
  
    bool moveNext() {
      if (_modifications != _map._modifications) {
        throw new ConcurrentModificationError(_map);
      } else if (_cell == null) {
        _current = null;
        return false;
      } else {
        _current = _cell._key;
        _cell = _cell._next;
        return true;
      }
    }
  }
  
  patch class HashSet<E> {
    patch factory HashSet({ bool equals(E e1, E e2),
                            int hashCode(E e),
                            bool isValidKey(potentialKey) }) {
      if (isValidKey == null) {
        if (hashCode == null) {
          if (equals == null) {
            return new _HashSet<E>();
          }
          hashCode = _defaultHashCode;
        } else {
          if (identical(identityHashCode, hashCode) &&
              identical(identical, equals)) {
            return new _IdentityHashSet<E>();
          }
          if (equals == null) {
            equals = _defaultEquals;
          }
        }
      } else {
        if (hashCode == null) {
          hashCode = _defaultHashCode;
        }
        if (equals == null) {
          equals = _defaultEquals;
        }
      }
      return new _CustomHashSet<E>(equals, hashCode, isValidKey);
    }
  
    patch factory HashSet.identity() = _IdentityHashSet<E>;
  }
  
  class _HashSet<E> extends _HashSetBase<E> implements HashSet<E> {
    int _length = 0;
  
    // The hash set contents are divided into three parts: one part for
    // string elements, one for numeric elements, and one for the
    // rest. String and numeric elements map directly to a sentinel
    // value, but the rest of the entries are stored in bucket lists of
    // the form:
    //
    //    [element-0, element-1, element-2, ...]
    //
    // where all elements in the same bucket share the same hash code.
    var _strings;
    var _nums;
    var _rest;
  
    // When iterating over the hash set, it is very convenient to have a
    // list of all the elements. We cache that on the instance and clear
    // the the cache whenever the set changes. This is also used to
    // guard against concurrent modifications.
    List _elements;
  
    _HashSet();
  
    Set<E> _newSet() => new _HashSet<E>();
  
    // Iterable.
    Iterator<E> get iterator {
      return new HashSetIterator<E>(this, _computeElements());
    }
  
    int get length => _length;
    bool get isEmpty => _length == 0;
    bool get isNotEmpty => !isEmpty;
  
    bool contains(Object object) {
      if (_isStringElement(object)) {
        var strings = _strings;
        return (strings == null) ? false : _hasTableEntry(strings, object);
      } else if (_isNumericElement(object)) {
        var nums = _nums;
        return (nums == null) ? false : _hasTableEntry(nums, object);
      } else {
        var rest = _rest;
        if (rest == null) return false;
        var bucket = _getBucket(rest, object);
        return _findBucketIndex(bucket, object) >= 0;
      }
    }
  
    E lookup(Object object) {
      if (_isStringElement(object) || _isNumericElement(object)) {
        return this.contains(object) ? object : null;
      }
      var rest = _rest;
      if (rest == null) return null;
      var bucket = _getBucket(rest, object);
      var index = _findBucketIndex(bucket, object);
      if (index < 0) return null;
      return bucket[index];
    }
  
    // Collection.
    bool add(E element) {
      if (_isStringElement(element)) {
        var strings = _strings;
        if (strings == null) _strings = strings = _newHashTable();
        return _addHashTableEntry(strings, element);
      } else if (_isNumericElement(element)) {
        var nums = _nums;
        if (nums == null) _nums = nums = _newHashTable();
        return _addHashTableEntry(nums, element);
      } else {
        var rest = _rest;
        if (rest == null) _rest = rest = _newHashTable();
        var hash = _computeHashCode(element);
        var bucket = JS('var', '#[#]', rest, hash);
        if (bucket == null) {
          _setTableEntry(rest, hash, JS('var', '[#]', element));
        } else {
          int index = _findBucketIndex(bucket, element);
          if (index >= 0) return false;
          JS('void', '#.push(#)', bucket, element);
        }
        _length++;
        _elements = null;
        return true;
      }
    }
  
    void addAll(Iterable<E> objects) {
      for (E each in objects) {
        add(each);
      }
    }
  
    bool remove(Object object) {
      if (_isStringElement(object)) {
        return _removeHashTableEntry(_strings, object);
      } else if (_isNumericElement(object)) {
        return _removeHashTableEntry(_nums, object);
      } else {
        var rest = _rest;
        if (rest == null) return false;
        var bucket = _getBucket(rest, object);
        int index = _findBucketIndex(bucket, object);
        if (index < 0) return false;
        // TODO(kasperl): Consider getting rid of the bucket list when
        // the length reaches zero.
        _length--;
        _elements = null;
        // TODO(kasperl): It would probably be faster to move the
        // element to the end and reduce the length of the bucket list.
        JS('void', '#.splice(#, 1)', bucket, index);
        return true;
      }
    }
  
    void removeAll(Iterable<Object> objectsToRemove) {
      for (var each in objectsToRemove) {
        remove(each);
      }
    }
  
    void retainAll(Iterable<Object> elements) {
      super._retainAll(elements, (o) => o is E);
    }
  
    void removeWhere(bool test(E element)) {
      removeAll(_computeElements().where(test));
    }
  
    void retainWhere(bool test(E element)) {
      removeAll(_computeElements().where((E element) => !test(element)));
    }
  
    void clear() {
      if (_length > 0) {
        _strings = _nums = _rest = _elements = null;
        _length = 0;
      }
    }
  
    List _computeElements() {
      if (_elements != null) return _elements;
      List result = new List(_length);
      int index = 0;
  
      // Add all string elements to the list.
      var strings = _strings;
      if (strings != null) {
        var names = JS('var', 'Object.getOwnPropertyNames(#)', strings);
        int entries = JS('int', '#.length', names);
        for (int i = 0; i < entries; i++) {
          String element = JS('String', '#[#]', names, i);
          JS('void', '#[#] = #', result, index, element);
          index++;
        }
      }
  
      // Add all numeric elements to the list.
      var nums = _nums;
      if (nums != null) {
        var names = JS('var', 'Object.getOwnPropertyNames(#)', nums);
        int entries = JS('int', '#.length', names);
        for (int i = 0; i < entries; i++) {
          // Object.getOwnPropertyNames returns a list of strings, so we
          // have to convert the elements back to numbers (+).
          num element = JS('num', '+#[#]', names, i);
          JS('void', '#[#] = #', result, index, element);
          index++;
        }
      }
  
      // Add all the remaining elements to the list.
      var rest = _rest;
      if (rest != null) {
        var names = JS('var', 'Object.getOwnPropertyNames(#)', rest);
        int entries = JS('int', '#.length', names);
        for (int i = 0; i < entries; i++) {
          var entry = JS('String', '#[#]', names, i);
          var bucket = JS('var', '#[#]', rest, entry);
          int length = JS('int', '#.length', bucket);
          for (int i = 0; i < length; i++) {
            JS('void', '#[#] = #[#]', result, index, bucket, i);
            index++;
          }
        }
      }
      assert(index == _length);
      return _elements = result;
    }
  
    bool _addHashTableEntry(var table, E element) {
      if (_hasTableEntry(table, element)) return false;
      _setTableEntry(table, element, 0);
      _length++;
      _elements = null;
      return true;
    }
  
    bool _removeHashTableEntry(var table, Object element) {
      if (table != null && _hasTableEntry(table, element)) {
        _deleteTableEntry(table, element);
        _length--;
        _elements = null;
        return true;
      } else {
        return false;
      }
    }
  
    static bool _isStringElement(var element) {
      return element is String && element != '__proto__';
    }
  
    static bool _isNumericElement(var element) {
      // Only treat unsigned 30-bit integers as numeric elements. This
      // way, we avoid converting them to strings when we use them as
      // keys in the JavaScript hash table object.
      return element is num &&
          JS('bool', '(# & 0x3ffffff) === #', element, element);
    }
  
    int _computeHashCode(var element) {
      // We force the hash codes to be unsigned 30-bit integers to avoid
      // issues with problematic elements like '__proto__'. Another
      // option would be to throw an exception if the hash code isn't a
      // number.
      return JS('int', '# & 0x3ffffff', element.hashCode);
    }
  
    static bool _hasTableEntry(var table, var key) {
      var entry = JS('var', '#[#]', table, key);
      // We take care to only store non-null entries in the table, so we
      // can check if the table has an entry for the given key with a
      // simple null check.
      return entry != null;
    }
  
    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);
    }
  
    List _getBucket(var table, var element) {
      var hash = _computeHashCode(element);
      return JS('var', '#[#]', table, hash);
    }
  
    int _findBucketIndex(var bucket, var element) {
      if (bucket == null) return -1;
      int length = JS('int', '#.length', bucket);
      for (int i = 0; i < length; i++) {
        if (JS('var', '#[#]', bucket, i) == element) 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;
    }
  }
  
  class _IdentityHashSet<E> extends _HashSet<E> {
    Set<E> _newSet() => new _IdentityHashSet<E>();
  
    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', identityHashCode(key));
    }
  
    int _findBucketIndex(var bucket, var element) {
      if (bucket == null) return -1;
      int length = JS('int', '#.length', bucket);
      for (int i = 0; i < length; i++) {
        if (identical(JS('var', '#[#]', bucket, i), element)) return i;
      }
      return -1;
    }
  }
  
  class _CustomHashSet<E> extends _HashSet<E> {
    _Equality<E> _equality;
    _Hasher<E> _hasher;
    _Predicate _validKey;
    _CustomHashSet(this._equality, this._hasher, bool validKey(potentialKey))
        : _validKey = (validKey != null) ? validKey : ((x) => x is E);
  
    Set<E> _newSet() => new _CustomHashSet<E>(_equality, _hasher, _validKey);
  
    int _findBucketIndex(var bucket, var element) {
      if (bucket == null) return -1;
      int length = JS('int', '#.length', bucket);
      for (int i = 0; i < length; i++) {
        if (_equality(JS('var', '#[#]', bucket, i), element)) return i;
      }
      return -1;
    }
  
    int _computeHashCode(var element) {
      // We force the hash codes to be unsigned 30-bit integers to avoid
      // issues with problematic elements like '__proto__'. Another
      // option would be to throw an exception if the hash code isn't a
      // number.
      return JS('int', '# & 0x3ffffff', _hasher(element));
    }
  
    bool contains(Object object) {
      if (!_validKey(object)) return false;
      return super.contains(object);
    }
  
    E lookup(Object object) {
      if (!_validKey(object)) return null;
      return super.lookup(object);
    }
  
    bool remove(Object object) {
      if (!_validKey(object)) return false;
      return super.remove(object);
    }
  
    bool containsAll(Iterable<Object> elements) {
      for (Object element in elements) {
        if (!_validKey(element) || !this.contains(element)) return false;
      }
      return true;
    }
  
    void removeAll(Iterable<Object> elements) {
      for (Object element in elements) {
        if (_validKey(element)) {
          super.remove(element);
        }
      }
    }
  
    void retainAll(Iterable<Object> elements) {
      super._retainAll(elements, _validKey);
    }
  }
  
  // TODO(kasperl): Share this code with HashMapKeyIterator<E>?
  class HashSetIterator<E> implements Iterator<E> {
    final _set;
    final List _elements;
    int _offset = 0;
    E _current;
  
    HashSetIterator(this._set, this._elements);
  
    E get current => _current;
  
    bool moveNext() {
      var elements = _elements;
      int offset = _offset;
      if (JS('bool', '# !== #', elements, _set._elements)) {
        throw new ConcurrentModificationError(_set);
      } else if (offset >= JS('int', '#.length', elements)) {
        _current = null;
        return false;
      } else {
        _current = JS('var', '#[#]', elements, offset);
        // 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 LinkedHashSet<E> {
    patch factory LinkedHashSet({ bool equals(E e1, E e2),
                                  int hashCode(E e),
                                  bool isValidKey(potentialKey) }) {
      if (isValidKey == null) {
        if (hashCode == null) {
          if (equals == null) {
            return new _LinkedHashSet<E>();
          }
          hashCode = _defaultHashCode;
        } else {
          if (identical(identityHashCode, hashCode) &&
              identical(identical, equals)) {
            return new _LinkedIdentityHashSet<E>();
          }
          if (equals == null) {
            equals = _defaultEquals;
          }
        }
      } else {
        if (hashCode == null) {
          hashCode = _defaultHashCode;
        }
        if (equals == null) {
          equals = _defaultEquals;
        }
      }
      return new _LinkedCustomHashSet<E>(equals, hashCode, isValidKey);
    }
  
    patch factory LinkedHashSet.identity() = _LinkedIdentityHashSet<E>;
  }
  
  class _LinkedHashSet<E> extends _HashSetBase<E> implements LinkedHashSet<E> {
    int _length = 0;
  
    // The hash set contents are divided into three parts: one part for
    // string elements, one for numeric elements, and one for the
    // rest. String and numeric elements 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 elements in the same bucket share the same hash code.
    var _strings;
    var _nums;
    var _rest;
  
    // The elements are stored in cells that are linked together
    // to form a double linked list.
    LinkedHashSetCell _first;
    LinkedHashSetCell _last;
  
    // We track the number of modifications done to the element set to
    // be able to throw when the set is modified while being iterated
    // over.
    int _modifications = 0;
  
    _LinkedHashSet();
  
    Set<E> _newSet() => new _LinkedHashSet<E>();
  
    void _unsupported(String operation) {
      throw 'LinkedHashSet: unsupported $operation';
    }
  
    // Iterable.
    Iterator<E> get iterator {
      return new LinkedHashSetIterator(this, _modifications);
    }
  
    int get length => _length;
    bool get isEmpty => _length == 0;
    bool get isNotEmpty => !isEmpty;
  
    bool contains(Object object) {
      if (_isStringElement(object)) {
        var strings = _strings;
        if (strings == null) return false;
        LinkedHashSetCell cell = _getTableEntry(strings, object);
        return cell != null;
      } else if (_isNumericElement(object)) {
        var nums = _nums;
        if (nums == null) return false;
        LinkedHashSetCell cell = _getTableEntry(nums, object);
        return cell != null;
      } else {
        var rest = _rest;
        if (rest == null) return false;
        var bucket = _getBucket(rest, object);
        return _findBucketIndex(bucket, object) >= 0;
      }
    }
  
    E lookup(Object object) {
      if (_isStringElement(object) || _isNumericElement(object)) {
        return this.contains(object) ? object : null;
      } else {
        var rest = _rest;
        if (rest == null) return null;
        var bucket = _getBucket(rest, object);
        var index = _findBucketIndex(bucket, object);
        if (index < 0) return null;
        return bucket[index]._element;
      }
    }
  
    void forEach(void action(E element)) {
      LinkedHashSetCell cell = _first;
      int modifications = _modifications;
      while (cell != null) {
        action(cell._element);
        if (modifications != _modifications) {
          throw new ConcurrentModificationError(this);
        }
        cell = cell._next;
      }
    }
  
    E get first {
      if (_first == null) throw new StateError("No elements");
      return _first._element;
    }
  
    E get last {
      if (_last == null) throw new StateError("No elements");
      return _last._element;
    }
  
    // Collection.
    bool add(E element) {
      if (_isStringElement(element)) {
        var strings = _strings;
        if (strings == null) _strings = strings = _newHashTable();
        return _addHashTableEntry(strings, element);
      } else if (_isNumericElement(element)) {
        var nums = _nums;
        if (nums == null) _nums = nums = _newHashTable();
        return _addHashTableEntry(nums, element);
      } else {
        var rest = _rest;
        if (rest == null) _rest = rest = _newHashTable();
        var hash = _computeHashCode(element);
        var bucket = JS('var', '#[#]', rest, hash);
        if (bucket == null) {
          LinkedHashSetCell cell = _newLinkedCell(element);
          _setTableEntry(rest, hash, JS('var', '[#]', cell));
        } else {
          int index = _findBucketIndex(bucket, element);
          if (index >= 0) return false;
          LinkedHashSetCell cell = _newLinkedCell(element);
          JS('void', '#.push(#)', bucket, cell);
        }
        return true;
      }
    }
  
    void addAll(Iterable<E> objects) {
      for (E object in objects) {
        add(object);
      }
    }
  
    bool remove(Object object) {
      if (_isStringElement(object)) {
        return _removeHashTableEntry(_strings, object);
      } else if (_isNumericElement(object)) {
        return _removeHashTableEntry(_nums, object);
      } else {
        var rest = _rest;
        if (rest == null) return false;
        var bucket = _getBucket(rest, object);
        int index = _findBucketIndex(bucket, object);
        if (index < 0) return false;
        // Use splice to remove the [cell] element at the index and
        // unlink it.
        LinkedHashSetCell cell = JS('var', '#.splice(#, 1)[0]', bucket, index);
        _unlinkCell(cell);
        return true;
      }
    }
  
    void removeAll(Iterable objectsToRemove) {
      for (var each in objectsToRemove) {
        remove(each);
      }
    }
  
    void retainAll(Iterable<Object> elements) {
      super._retainAll(elements, (o) => o is E);
    }
  
    void removeWhere(bool test(E element)) {
      _filterWhere(test, true);
    }
  
    void retainWhere(bool test(E element)) {
      _filterWhere(test, false);
    }
  
    void _filterWhere(bool test(E element), bool removeMatching) {
      LinkedHashSetCell cell = _first;
      while (cell != null) {
        E element = cell._element;
        LinkedHashSetCell next = cell._next;
        int modifications = _modifications;
        bool shouldRemove = (removeMatching == test(element));
        if (modifications != _modifications) {
          throw new ConcurrentModificationError(this);
        }
        if (shouldRemove) remove(element);
        cell = next;
      }
    }
  
    void clear() {
      if (_length > 0) {
        _strings = _nums = _rest = _first = _last = null;
        _length = 0;
        _modified();
      }
    }
  
    bool _addHashTableEntry(var table, E element) {
      LinkedHashSetCell cell = _getTableEntry(table, element);
      if (cell != null) return false;
      _setTableEntry(table, element, _newLinkedCell(element));
      return true;
    }
  
    bool _removeHashTableEntry(var table, Object element) {
      if (table == null) return false;
      LinkedHashSetCell cell = _getTableEntry(table, element);
      if (cell == null) return false;
      _unlinkCell(cell);
      _deleteTableEntry(table, element);
      return true;
    }
  
    void _modified() {
      // Value cycles after 2^30 modifications. If you keep hold of an
      // iterator for that long, you might miss a modification
      // detection, and iteration can go sour. Don't do that.
      _modifications = (_modifications + 1) & 0x3ffffff;
    }
  
    // Create a new cell and link it in as the last one in the list.
    LinkedHashSetCell _newLinkedCell(E element) {
      LinkedHashSetCell cell = new LinkedHashSetCell(element);
      if (_first == null) {
        _first = _last = cell;
      } else {
        LinkedHashSetCell last = _last;
        cell._previous = last;
        _last = last._next = cell;
      }
      _length++;
      _modified();
      return cell;
    }
  
    // Unlink the given cell from the linked list of cells.
    void _unlinkCell(LinkedHashSetCell cell) {
      LinkedHashSetCell previous = cell._previous;
      LinkedHashSetCell next = cell._next;
      if (previous == null) {
        assert(cell == _first);
        _first = next;
      } else {
        previous._next = next;
      }
      if (next == null) {
        assert(cell == _last);
        _last = previous;
      } else {
        next._previous = previous;
      }
      _length--;
      _modified();
    }
  
    static bool _isStringElement(var element) {
      return element is String && element != '__proto__';
    }
  
    static bool _isNumericElement(var element) {
      // Only treat unsigned 30-bit integers as numeric elements. This
      // way, we avoid converting them to strings when we use them as
      // keys in the JavaScript hash table object.
      return element is num &&
          JS('bool', '(# & 0x3ffffff) === #', element, element);
    }
  
    int _computeHashCode(var element) {
      // We force the hash codes to be unsigned 30-bit integers to avoid
      // issues with problematic elements like '__proto__'. Another
      // option would be to throw an exception if the hash code isn't a
      // number.
      return JS('int', '# & 0x3ffffff', element.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);
    }
  
    List _getBucket(var table, var element) {
      var hash = _computeHashCode(element);
      return JS('var', '#[#]', table, hash);
    }
  
    int _findBucketIndex(var bucket, var element) {
      if (bucket == null) return -1;
      int length = JS('int', '#.length', bucket);
      for (int i = 0; i < length; i++) {
        LinkedHashSetCell cell = JS('var', '#[#]', bucket, i);
        if (cell._element == element) 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;
    }
  }
  
  class _LinkedIdentityHashSet<E> extends _LinkedHashSet<E> {
    Set<E> _newSet() => new _LinkedIdentityHashSet<E>();
  
    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', identityHashCode(key));
    }
  
    int _findBucketIndex(var bucket, var element) {
      if (bucket == null) return -1;
      int length = JS('int', '#.length', bucket);
      for (int i = 0; i < length; i++) {
        LinkedHashSetCell cell = JS('var', '#[#]', bucket, i);
        if (identical(cell._element, element)) return i;
      }
      return -1;
    }
  }
  
  class _LinkedCustomHashSet<E> extends _LinkedHashSet<E> {
    _Equality<E> _equality;
    _Hasher<E> _hasher;
    _Predicate _validKey;
    _LinkedCustomHashSet(this._equality, this._hasher,
                         bool validKey(potentialKey))
        : _validKey = (validKey != null) ? validKey : ((x) => x is E);
  
    Set<E> _newSet() =>
        new _LinkedCustomHashSet<E>(_equality, _hasher, _validKey);
  
    int _findBucketIndex(var bucket, var element) {
      if (bucket == null) return -1;
      int length = JS('int', '#.length', bucket);
      for (int i = 0; i < length; i++) {
        LinkedHashSetCell cell = JS('var', '#[#]', bucket, i);
        if (_equality(cell._element, element)) return i;
      }
      return -1;
    }
  
    int _computeHashCode(var element) {
      // We force the hash codes to be unsigned 30-bit integers to avoid
      // issues with problematic elements like '__proto__'. Another
      // option would be to throw an exception if the hash code isn't a
      // number.
      return JS('int', '# & 0x3ffffff', _hasher(element));
    }
  
    bool contains(Object object) {
      if (!_validKey(object)) return false;
      return super.contains(object);
    }
  
    E lookup(Object object) {
      if (!_validKey(object)) return null;
      return super.lookup(object);
    }
  
    bool remove(Object object) {
      if (!_validKey(object)) return false;
      return super.remove(object);
    }
  
    bool containsAll(Iterable<Object> elements) {
      for (Object element in elements) {
        if (!_validKey(element) || !this.contains(element)) return false;
      }
      return true;
    }
  
    void removeAll(Iterable<Object> elements) {
      for (Object element in elements) {
        if (_validKey(element)) {
          super.remove(element);
        }
      }
    }
  
    void retainAll(Iterable<Object> elements) {
      super._retainAll(elements, _validKey);
    }
  }
  
  class LinkedHashSetCell {
    final _element;
  
    LinkedHashSetCell _next;
    LinkedHashSetCell _previous;
  
    LinkedHashSetCell(this._element);
  }
  
  // TODO(kasperl): Share this code with LinkedHashMapKeyIterator<E>?
  class LinkedHashSetIterator<E> implements Iterator<E> {
    final _set;
    final int _modifications;
    LinkedHashSetCell _cell;
    E _current;
  
    LinkedHashSetIterator(this._set, this._modifications) {
      _cell = _set._first;
    }
  
    E get current => _current;
  
    bool moveNext() {
      if (_modifications != _set._modifications) {
        throw new ConcurrentModificationError(_set);
      } else if (_cell == null) {
        _current = null;
        return false;
      } else {
        _current = _cell._element;
        _cell = _cell._next;
        return true;
      }
    }
  }
  