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

sdk/lib/collection/hash_set.dart

Index: sdk/lib/collection/hash_set.dart
diff --git a/sdk/lib/collection/hash_set.dart b/sdk/lib/collection/hash_set.dart
new file mode 100644
index 0000000000000000000000000000000000000000..dc5a99673a4d236fae8a0c95611d26adecd622c9
--- /dev/null
+++ b/sdk/lib/collection/hash_set.dart
@@ -0,0 +1,125 @@
+part of dart.collection;
+
+class HashSet<E> extends Collection<E> implements Set<E> {
+  static const int _INITIAL_CAPACITY = 8;
+  final _HashTable<E> _table;
+
+  HashSet() : _table = new _HashTable(_INITIAL_CAPACITY);
+
+  factory HashSet.from(Iterable<E> iterable) {
+    return new HashSet<E>()..addAll(iterable);
+  }
+
+  // Iterable.
+  Iterator<E> get iterator => new _HashTableKeyIterator<E>(_table);
+
+  bool get isEmpty => _table._elementCount == 0;
+
+  bool contains(Object object) => _table._get(object) >= 0;
+
+  // Collection.
+  void add(E element) {
+    _table._ensureCapacity(1);
+    _table._put(element);
+  }
+
+  void addAll(Iterable<E> objects) {

[erikcorry, 2013/02/05 16:25:05]

I can't see where this increments the modification count.

[Lasse Reichstein Nielsen, 2013/02/05 19:47:40]

True. I was probably assuming that it was done in _put, if necessary. I'll add
it there.

+    if (objects is Set || objects is List) {
+      int length = objects.length;
+      _table._ensureCapacity(length);
+      for (E object in objects) {
+        _table._put(object);
+      }
+    } else {
+      for (E object in objects) {
+        _table._ensureCapacity(1);
+        _table._put(object);
+      }
+    }
+  }
+
+  bool remove(Object object) {
+    int offset = _table._remove(object);

[floitsch, 2013/02/06 10:43:58]

modification count here too.

[Lasse Reichstein Nielsen, 2013/02/08 13:53:01]

Added to _remove.

+    return offset >= 0;
+  }
+
+  void removeAll(Iterable objectsToRemove) {
+    for (Object object in objectsToRemove) {

[floitsch, 2013/02/06 10:43:58]

ditto.

[Lasse Reichstein Nielsen, 2013/02/08 13:53:01]

Et ditto.

+      _table._remove(object);
+    }
+  }
+
+  void retainAll(Iterable objectsToRemove) {

[erikcorry, 2013/02/05 16:25:05]

Parameter is misnamed.

[Lasse Reichstein Nielsen, 2013/02/05 19:47:40]

Whoops.

+    IterableMixinWorkaround.retainAll(this, objectsToRemove);
+  }
+
+  void removeMatching(bool test(E element)) {
+    int entrySize = _table._entrySize;
+    int length = _table._table.length;
+    for (int offset =  0; offset < length; offset += entrySize) {
+      Object entry = _table._key(offset);
+      if (!_table._isFree(entry)) {
+        E key = entry;
+        int modificationCount = _table._modificationCount;
+        bool matches = test(key);
+        _table._checkModification(modificationCount);
+        if (matches) {
+          _table._deleteEntry(offset);
+          _table._modificationCount++;
+        }
+      }
+    }
+  }
+
+  void retainMatching(bool test(E element)) {
+    int entrySize = _table._entrySize;
+    int length = _table._table.length;
+    for (int offset =  0; offset < length; offset += entrySize) {
+      Object entry = _table._key(offset);
+      if (!_table._isFree(entry)) {
+        E key = entry;
+        int modificationCount = _table._modificationCount;
+        bool matches = test(key);
+        _table._checkModification(modificationCount);
+        if (!matches) {
+          _table._deleteEntry(offset);
+          _table._modificationCount++;
+        }
+      }
+    }
+  }
+
+  void clear() {
+    _table._clear();
+  }
+
+  // Set.
+  bool isSubsetOf(Collection<E> collection) {
+    Set otherSet;
+    if (collection is Set) {
+      otherSet = collection;
+    } else {
+      otherSet = collection.toSet();
+    }
+    return otherSet.containsAll(this);
+  }
+
+  bool containsAll(Collection<E> collection) {

[floitsch, 2013/02/06 10:43:58]

We should change this to be an Iterable.

[Lasse Reichstein Nielsen, 2013/02/08 13:53:01]

Or a Set. I think I would prefer that for intersection.
Not changing the Set signature it in this CL.

+    for (E element in collection) {
+      if (!this.contains(element)) return false;
+    }
+    return true;
+  }
+
+  Set<E> intersection(Collection<E> other) {

[floitsch, 2013/02/06 10:43:58]

ditto.

[Lasse Reichstein Nielsen, 2013/02/08 13:53:01]

Same.

+    Set<E> result = new HashSet<E>();

[floitsch, 2013/02/06 10:43:58]

new Set<E>(). It should be the default Set.

[Lasse Reichstein Nielsen, 2013/02/08 13:53:01]

Let's keep this the same type as the set creating the intersection.

+    for (E element in other) {
+      if (this.contains(element)) {
+        result.add(element);
+      }
+    }
+    return result;
+  }
+
+  String toString() =>  Collections.collectionToString(this);
+}