Add ordered set.

sdk/lib/core/set.dart

 // Copyright (c) 2011, 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.
 
 part of dart.core;
 
 /**
  * This class is the public interface of a set. A set is a collection
  * without duplicates.
  */
@@ skipping 60 matching lines @@
 
 abstract class HashSet<E> extends Set<E> {
   factory HashSet() => new _HashSetImpl<E>();
 
   /**
    * Creates a [Set] that contains all elements of [other].
    */
   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>();
+  _MapBackedSet.from(this._backingMap, Iterable<E> iterable) {
+    for (final e in iterable) {
+      add(e);
+    }
   }
 
-  factory _HashSetImpl.from(Iterable<E> other) {
-    Set<E> set = new _HashSetImpl<E>();
-    for (final e in other) {
-      set.add(e);
-    }
-    return set;
-  }
 
   void clear() {
     _backingMap.clear();
   }
 
   void add(E value) {
     _backingMap[value] = value;
   }
 
   bool contains(E value) {
     return _backingMap.containsKey(value);
   }
 
   bool remove(E value) {
     if (!_backingMap.containsKey(value)) return false;
     _backingMap.remove(value);
     return true;
   }
 
   void addAll(Iterable<E> iterable) {
     for (E element in iterable) {
       add(element);
     }
   }
 
   Set<E> intersection(Collection<E> collection) {

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

Why not Iterable?

     Set<E> result = new Set<E>();
     collection.forEach((E value) {
       if (contains(value)) result.add(value);
     });
     return result;
   }
 
   bool isSubsetOf(Collection<E> other) {
     return new Set<E>.from(other).containsAll(this);

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

ICK. Can't we really find a more efficient way to do that.

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

Would a check be good enough?

if (other is Set) return other.containsAll(this);

   }
 
   void removeAll(Iterable<E> iterable) {
     for (E value in iterable) {
       remove(value);
     }
   }
 
   bool containsAll(Collection<E> collection) {
     return collection.every((E value) {
       return contains(value);
     });
   }
 
   void forEach(void f(E element)) {
     _backingMap.forEach((E key, E value) {
       f(key);
     });
   }
 
   bool get isEmpty {
     return _backingMap.isEmpty;
   }
 
   int get length {
     return _backingMap.length;
   }
 
-  Iterator<E> get iterator => new _HashSetIterator<E>(this);
+  Iterator<E> get iterator => _backingMap.keys.iterator;
 
   String toString() {
     return Collections.collectionToString(this);
   }
 
   // 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> {
+class _HashSetImpl<E> extends _MapBackedSet<E> implements HashSet<E> {
+  _HashSetImpl.from(Iterable<E> iterable)
+      : super.from(new _HashMapImpl<E, E>(), iterable);
 
-  _HashSetIterator(_HashSetImpl<E> set)
-    : _keysIterator = set._backingMap._keys.iterator;
+  _HashSetImpl() : super(new _HashMapImpl<E, E>());
+}
 
-  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;
-  }
+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);
 
-  bool moveNext() {
-    bool result;
-    do {
-      result = _keysIterator.moveNext();
-    } while (result &&
-             (_keysIterator.current == null ||
-              identical(_keysIterator.current, _HashMapImpl._DELETED_KEY)));
-    return result;
-  }
-
-  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.

 }