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

sdk/lib/collection/linked_hash_set.dart

Index: sdk/lib/collection/linked_hash_set.dart
diff --git a/sdk/lib/collection/linked_hash_set.dart b/sdk/lib/collection/linked_hash_set.dart
new file mode 100644
index 0000000000000000000000000000000000000000..3e9e8364bc7931defbbe5e53ad5e80835401a878
--- /dev/null
+++ b/sdk/lib/collection/linked_hash_set.dart
@@ -0,0 +1,160 @@
+part of dart.collection;
+
+class LinkedHashSet<E> extends Collection<E> implements Set<E> {
+  static const int _INITIAL_CAPACITY = 8;
+  _LinkedHashTable<E> _table;
+
+  LinkedHashSet() : _table = new _LinkedHashTable(_INITIAL_CAPACITY);
+
+  // Iterable.
+  Iterator<E> get iterator => new _LinkedHashTableKeyIterator<E>(_table);
+
+  void forEach(void action(E element)) {
+    int offset = _table._next(_LinkedHashTable._HEAD_OFFSET);
+    int modificationCount = _table._modificationCount;
+    while (offset != _LinkedHashTable._HEAD_OFFSET) {
+      E key = _table._key(offset);
+      action(key);
+      _table._checkModification(modificationCount);
+      offset = _table._next(offset);
+    }
+  }
+
+  bool get isEmpty => _table._elementCount == 0;
+
+  bool contains(Object object) => _table._get(object) >= 0;
+
+  E get first {
+    int firstOffset = _table._next(_LinkedHashTable._HEAD_OFFSET);
+    if (firstOffset == _LinkedHashTable._HEAD_OFFSET) {
+      throw new StateError("No elements");
+    }
+    return _table._key(firstOffset);
+  }
+
+  E get last {
+    int lastOffset = _table._prev(_LinkedHashTable._HEAD_OFFSET);
+    if (lastOffset == _LinkedHashTable._HEAD_OFFSET) {
+      throw new StateError("No elements");
+    }
+    return _table._key(lastOffset);
+  }
+
+  E get single {
+    int firstOffset = _table._next(_LinkedHashTable._HEAD_OFFSET);
+    if (firstOffset == _LinkedHashTable._HEAD_OFFSET) {
+      throw new StateError("No elements");
+    }
+    int lastOffset = _table._prev(_LinkedHashTable._HEAD_OFFSET);
+    if (lastOffset != firstOffset) {
+      throw new StateError("Too many elements");
+    }
+    return _table._key(firstOffset);
+  }
+
+  // Collection.
+  void add(E element) {
+    _table._ensureCapacity(1);
+    _table._put(element);
+  }
+
+  void addAll(Iterable<E> objects) {
+    if (objects is Set || objects is List) {

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

I'm not convinced if we should special case, or not just call iterable.length.
Yes. it could be an O(n) operation, but on the other hand growing one by one is
not really optimal either.
(and an iterable that is given away should not assume that it is only called
once. If that's a requirement it has to "toList()" itself).

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

I think you are right. Reading objects.length will usually be fast for other
collections (exceptions are adding a .where()-filtered collection or some
special iterable that isn't based on a collection).

+      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);
+    return offset >= 0;
+  }
+
+  void removeAll(Iterable objectsToRemove) {
+    for (Object object in objectsToRemove) {
+      _table._remove(object);
+    }
+  }
+
+  void retainAll(Iterable objectsToRemove) {
+    IterableMixinWorkaround.retainAll(this, objectsToRemove);
+  }
+
+  void removeMatching(bool test(E element)) {
+    int entrySize = _table._entrySize;
+    int length = _table._table.length;
+    int offset = _table._next(_LinkedHashTable._HEAD_OFFSET);
+    while (offset != _LinkedHashTable._HEAD_OFFSET) {
+      E key = _table._key(offset);
+      int nextOffset = _table._next(offset);
+      int modificationCount = _table._modificationCount;
+      bool matches = test(key);
+      _table._checkModification(modificationCount);
+      if (matches) {
+        _table._deleteEntry(offset);
+        _table._modificationCount++;
+      }
+      offset = nextOffset;
+    }
+  }
+
+  void retainMatching(bool test(E element)) {

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

removeMatching and retainMatching could share the same code with a simple if
(matches == shouldMatch) {

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

Done.

+    int entrySize = _table._entrySize;
+    int length = _table._table.length;
+    int offset = _table._next(_LinkedHashTable._HEAD_OFFSET);
+    while (offset != _LinkedHashTable._HEAD_OFFSET) {
+      E key = _table._key(offset);
+      int nextOffset = _table._next(offset);
+      int modificationCount = _table._modificationCount;
+      bool matches = test(key);
+      _table._checkModification(modificationCount);
+      if (!matches) {
+        _table._deleteEntry(offset);
+        _table._modificationCount++;
+      }
+      offset = nextOffset;
+    }
+  }
+
+  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) {
+    for (E element in collection) {
+      if (!this.contains(element)) return false;
+    }
+    return true;
+  }
+
+  Set<E> intersection(Collection<E> other) {
+    Set<E> result = new HashSet<E>();

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

new Set.
I think it should be the default Set.

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

I'll make it the same typo as this set (which will be LinkedHashSet).

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