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

tests/corelib/hash_set_test.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.
-
-// Tests of hash set behavior, with focus in iteration and concurrent
-// modification errors.
-
-library hash_map2_test;
-import 'dart:collection';
-
-testSet(Set newSet(), Set newSetFrom(Set from)) {
-  Set gen(int from, int to) =>
-      new Set.from(new Iterable.generate(to - from, (n) => n + from));
-
-  bool odd(int n) => (n & 1) == 1;
-  bool even(int n) => (n & 1) == 0;
-
-  {  // Test growing to largish capacity.
-    Set set = newSet();
-
-    for (int i = 0; i < 256; i++) {
-      set.add(i);
-    }
-    set.addAll(gen(256, 512));
-    set.addAll(newSetFrom(gen(512, 1000)));
-    Expect.equals(1000, set.length);
-
-    // Remove half.
-    for (int i = 0; i < 1000; i += 2) set.remove(i);
-    Expect.equals(500, set.length);
-    Expect.isFalse(set.any(even));
-    Expect.isTrue(set.every(odd));
-
-    // Re-add all.
-    set.addAll(gen(0, 1000));
-    Expect.equals(1000, set.length);
-  }
-
-  {  // Test having many deleted elements.
-    Set set = newSet();
-    set.add(0);
-    for (int i = 0; i < 1000; i++) {
-      set.add(i + 1);
-      set.remove(i);
-      Expect.equals(1, set.length);
-    }
-  }
-
-  {  // Test having many elements with same hashCode
-    Set set = newSet();
-    for (int i = 0; i < 1000; i++) {
-      set.add(new BadHashCode());
-    }
-    Expect.equals(1000, set.length);
-  }
-
-  {  // Check concurrent modification
-    Set set = newSet()..add(0)..add(1);
-
-    {  // Test adding before a moveNext.
-      Iterator iter = set.iterator;
-      iter.moveNext();
-      set.add(1);  // Updating existing key isn't a modification.
-      iter.moveNext();
-      set.add(2);
-      Expect.throws(iter.moveNext, (e) => e is Error);
-    }
-
-    {  // Test adding after last element.
-      Iterator iter = set.iterator;
-      Expect.equals(3, set.length);
-      iter.moveNext();
-      iter.moveNext();
-      iter.moveNext();
-      set.add(3);
-      Expect.throws(iter.moveNext, (e) => e is Error);
-    }
-
-    {  // Test removing during iteration.
-      Iterator iter = set.iterator;
-      iter.moveNext();
-      set.remove(1000);  // Not a modification if it's not there.
-      iter.moveNext();
-      int n = iter.current;
-      set.remove(n);
-      // Removing doesn't change current.
-      Expect.equals(n, iter.current);
-      Expect.throws(iter.moveNext, (e) => e is Error);
-    }
-
-    {  // Test removing after last element.
-      Iterator iter = set.iterator;
-      Expect.equals(3, set.length);
-      iter.moveNext();
-      iter.moveNext();
-      iter.moveNext();
-      int n = iter.current;
-      set.remove(n);
-      // Removing doesn't change current.
-      Expect.equals(n, iter.current);
-      Expect.throws(iter.moveNext, (e) => e is Error);
-    }
-
-    {  // Test that updating value doesn't cause error.
-      Iterator iter = set.iterator;
-      Expect.equals(2, set.length);
-      iter.moveNext();
-      int n = iter.current;
-      set.add(n);
-      iter.moveNext();
-      Expect.isTrue(set.contains(iter.current));
-    }
-
-    {  // Check adding many existing values isn't considered modification.
-      Set set2 = newSet();
-      for (var value in set) {
-        set2.add(value);
-      }
-      Iterator iter = set.iterator;
-      set.addAll(set2);
-      // Shouldn't throw.
-      iter.moveNext();
-    }
-  }
-
-  {  // Check that updating existing elements is not a modification.
-     // This must be the case even if the underlying data structure is
-     // nearly full.
-     for (int i = 1; i < 128; i++) {
-        // Create maps of different sizes, some of which should be
-        // at a limit of the underlying data structure.
-        Set set = newSetFrom(gen(0, i));
-        Iterator iter = set.iterator;
-        for (int j = 0; j < i; j++) {
-          set.add(j);
-        }
-        iter.moveNext();  // Should not throw.
-
-        for (int j = 1; j < i; j++) {
-          set.remove(j);
-        }
-        iter = set.iterator;
-        set.add(0);
-        iter.moveNext();  // Should not throw.
-     }
-  }
-
-  {  // Check that null can be in the set.
-    Set set = newSet();
-    set.add(null);
-    Expect.equals(1, set.length);
-    Expect.isTrue(set.contains(null));
-    Expect.isNull(set.first);
-    Expect.isNull(set.last);
-    set.add(null);
-    Expect.equals(1, set.length);
-    Expect.isTrue(set.contains(null));
-    set.remove(null);
-    Expect.isTrue(set.isEmpty);
-    Expect.isFalse(set.contains(null));
-
-    // Created using Set.from.
-    set = newSetFrom([null]);
-    Expect.equals(1, set.length);
-    Expect.isTrue(set.contains(null));
-    Expect.isNull(set.first);
-    Expect.isNull(set.last);
-    set.add(null);
-    Expect.equals(1, set.length);
-    Expect.isTrue(set.contains(null));
-    set.remove(null);
-    Expect.isTrue(set.isEmpty);
-    Expect.isFalse(set.contains(null));
-
-    // Set that grows with null in it.
-    set = newSetFrom([1, 2, 3, null, 4, 5, 6]);
-    Expect.equals(7, set.length);
-    for (int i = 7; i < 128; i++) {
-      set.add(i);
-    }
-    Expect.equals(128, set.length);
-    Expect.isTrue(set.contains(null));
-    set.add(null);
-    Expect.equals(128, set.length);
-    Expect.isTrue(set.contains(null));
-    set.remove(null);
-    Expect.equals(127, set.length);
-    Expect.isFalse(set.contains(null));
-  }
-}
-
-void main() {
-  testSet(() => new HashSet(), (m) => new HashSet.from(m));
-  testSet(() => new LinkedHashSet(), (m) => new LinkedHashSet.from(m));
-}
-
-
-class BadHashCode {
-  static int idCounter = 0;
-  final int id;
-  BadHashCode() : id = idCounter++;
-  int get hashCode => 42;
-  // operator == is identity.
-  // Can't make a bad compareTo that isn't invalid.
-  int compareTo(BadHashCode other) => id - other.id;
-}