Add ordered set.

sdk/lib/core/set.dart

Index: sdk/lib/core/set.dart
diff --git a/sdk/lib/core/set.dart b/sdk/lib/core/set.dart
index 95a633a447ca6b9c5165e0475d6cb8e9145e5948..33e65b9851d68da3f85c1fe6deda95c3b5868a7f 100644
--- a/sdk/lib/core/set.dart
+++ b/sdk/lib/core/set.dart
@@ -78,21 +78,16 @@ abstract class HashSet<E> extends Set<E> {
   factory HashSet.from(Iterable<E> other) => new _HashSetImpl<E>.from(other);
 }
 
+abstract class _MapBackedSet<E> extends Iterable<E> implements HashSet<E> {

[Lasse Reichstein Nielsen, 2013/01/04 09:39:06]

Why implement HashSet? Being a HashSet is an implementation choice, so if you
don't inherit from HashSet, you don't get that implementation. It's just a Set.
If we create a non-HashMap Map (which we definitely will eventually, probably at
least TreeMap), we should be able to use this class as well.

Is the problem that you want HashSet to have a factory returning a
_MapBackedSet? In that case, make a 
 class _MapBackedHashSet extends _MapBackedSet implements HashSet {
   _MapBackedHashSet(Map m) : super(m);
 }
and use that.

+  _MapBackedSet(this._backingMap);
 
-class _HashSetImpl<E> extends Iterable<E> implements HashSet<E> {
-
-  _HashSetImpl() {
-    _backingMap = new _HashMapImpl<E, E>();
-  }
-
-  factory _HashSetImpl.from(Iterable<E> other) {
-    Set<E> set = new _HashSetImpl<E>();
-    for (final e in other) {
-      set.add(e);
+  _MapBackedSet.from(this._backingMap, Iterable<E> iterable) {
+    for (final e in iterable) {
+      add(e);
     }
-    return set;
   }
 
+
   void clear() {
     _backingMap.clear();
   }
@@ -155,7 +150,7 @@ class _HashSetImpl<E> extends Iterable<E> implements HashSet<E> {
     return _backingMap.length;
   }
 
-  Iterator<E> get iterator => new _HashSetIterator<E>(this);
+  Iterator<E> get iterator => _backingMap.keys.iterator;
 
   String toString() {
     return Collections.collectionToString(this);
@@ -164,32 +159,19 @@ class _HashSetImpl<E> extends Iterable<E> implements HashSet<E> {
   // The map backing this set. The associations in this map are all
   // of the form element -> element. If a value is not in the map,
   // then it is not in the set.
-  _HashMapImpl<E, E> _backingMap;
+  Map<E, E> _backingMap;
 }
 
-class _HashSetIterator<E> implements Iterator<E> {
-
-  _HashSetIterator(_HashSetImpl<E> set)
-    : _keysIterator = set._backingMap._keys.iterator;
+class _HashSetImpl<E> extends _MapBackedSet<E> implements HashSet<E> {
+  _HashSetImpl.from(Iterable<E> iterable)
+      : super.from(new _HashMapImpl<E, E>(), iterable);
 
-  E get current {
-    var result = _keysIterator.current;
-    if (identical(result, _HashMapImpl._DELETED_KEY)) {
-      // TODO(floitsch): improve the error reporting.
-      throw new StateError("Concurrent modification.");
-    }
-    return result;
-  }
+  _HashSetImpl() : super(new _HashMapImpl<E, E>());
+}
 
-  bool moveNext() {
-    bool result;
-    do {
-      result = _keysIterator.moveNext();
-    } while (result &&
-             (_keysIterator.current == null ||
-              identical(_keysIterator.current, _HashMapImpl._DELETED_KEY)));
-    return result;
-  }
+class OrderedSet<E> extends _MapBackedSet<E> implements Set<E> {

[Lasse Reichstein Nielsen, 2013/01/04 09:39:06]

I don't like "OrderedSet" as a name. It doesn't say how the set is ordered. It
sounds too much like Java's SortedSet. This is an insertion-order preserving
set, which was just called LinkedHashSet in Java - it was an implementation
detail on a HashSet that it preserves *insertion* order.

I'd actually prefer LinkedHashSet too.

Also, no need for "implements Set<E>" when you extend a Set.

[sra1, 2013/01/04 09:56:15]

+1.  From the CL title I thought at last we had a set ordered by a compareTo
function.

'InsertionOrderedSet<E>' would be descriptive, if long.

[sra1, 2013/01/04 10:02:43]

+1.  From the CL title I thought at last we had a set ordered by a compareTo
function.

'InsertionOrderedSet<E>' would be descriptive, if long.

The class comment is missing.
This would be a place to address the following question:
What happens when an element is added, removed, and re-added?
Does it maintain its position in the ordering, or get a new position?

+  OrderedSet.from(Iterable<E> iterable)
+      : super.from(new _LinkedHashMapImpl<E, E>(), iterable);
 
-  Iterator _keysIterator;
+  OrderedSet() : super(new _LinkedHashMapImpl<E, E>());

[Lasse Reichstein Nielsen, 2013/01/04 09:39:06]

I still think it's silly to have a HashMap interface and a separate
implementation. It's just an implementation class for the Map interface.

 }