Add ordered set.

Add ordered set.

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

LGTM if you change the name.

https://codereview.chromium.org/11644072/diff/1/sdk/lib/core/set.dart
File sdk/lib/core/set.dart (right):

https://codereview.chromium.org/11644072/diff/1/sdk/lib/core/set.dart#newcode81
sdk/lib/core/set.dart:81: abstract class _MapBackedSet<E> extends Iterable<E>
implements HashSet<E> {
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.

https://codereview.chromium.org/11644072/diff/1/sdk/lib/core/set.dart#newcode115
sdk/lib/core/set.dart:115: Set<E> intersection(Collection<E> collection) {
Why not Iterable?

https://codereview.chromium.org/11644072/diff/1/sdk/lib/core/set.dart#newcode124
sdk/lib/core/set.dart:124: return new Set<E>.from(other).containsAll(this);
ICK. Can't we really find a more efficient way to do that.

https://codereview.chromium.org/11644072/diff/1/sdk/lib/core/set.dart#newcode172
sdk/lib/core/set.dart:172: class OrderedSet<E> extends _MapBackedSet<E>
implements Set<E> {
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.

https://codereview.chromium.org/11644072/diff/1/sdk/lib/core/set.dart#newcode176
sdk/lib/core/set.dart:176: OrderedSet() : super(new _LinkedHashMapImpl<E, E>());
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.

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

DBC.

https://codereview.chromium.org/11644072/diff/1/sdk/lib/core/set.dart
File sdk/lib/core/set.dart (right):

https://codereview.chromium.org/11644072/diff/1/sdk/lib/core/set.dart#newcode124
sdk/lib/core/set.dart:124: return new Set<E>.from(other).containsAll(this);
On 2013/01/04 09:39:06, Lasse Reichstein Nielsen wrote:
> ICK. Can't we really find a more efficient way to do that.

Would a check be good enough?

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

https://codereview.chromium.org/11644072/diff/1/sdk/lib/core/set.dart#newcode172
sdk/lib/core/set.dart:172: class OrderedSet<E> extends _MapBackedSet<E>
implements Set<E> {
On 2013/01/04 09:39:06, Lasse Reichstein Nielsen wrote:
> 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.

+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]

https://codereview.chromium.org/11644072/diff/1/sdk/lib/core/set.dart
File sdk/lib/core/set.dart (right):

https://codereview.chromium.org/11644072/diff/1/sdk/lib/core/set.dart#newcode172
sdk/lib/core/set.dart:172: class OrderedSet<E> extends _MapBackedSet<E>
implements Set<E> {
On 2013/01/04 09:39:06, Lasse Reichstein Nielsen wrote:
> 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.

+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?

[Lasse Reichstein Nielsen, 2013-09-26 12:05:13]

This CL is outdated now, right?

[floitsch, 2013-09-26 15:09:13]

Closing.