Add GroupSet and SetGroup classes.

lib/src/group_set.dart

+// Copyright (c) 2016, 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.
+
+import 'dart:collection';
+
+import 'unmodifiable_wrappers.dart';
+
+/// A single set that provides a view of a set of sets.
+///
+/// This behaves like the union of all sets passed in to [new GroupSet]. Since
+/// it's just a view, it will reflect any changes in the underlying sets.
+///
+/// If an element is in multiple sets and the outer set is ordered, the version
+/// in the earliest inner set is preferred. Component sets are assumed to use
+/// `==` and `hashCode` for equality.
+class GroupSet<E> extends SetMixin<E> with UnmodifiableSetMixin<E> {

[floitsch, 2016/04/25 16:11:09]

What about "UnionSet" ?

[nweiz, 2016/04/26 21:23:52]

I like it. Done.

+  /// The set of sets that this provides a view of.
+  final Set<Set<E>> _sets;

[floitsch, 2016/04/25 16:11:10]

I'm not sure I like the fact that this has to be a Set.

There are few advantages of making this a 'Set'.
List seems to be more efficient, although that would preclude an Iterable here.

[nweiz, 2016/04/26 21:23:52]

I discussed this with lrn earlier. Ideally this would just be Collection to
allow either List or Set, but that type doesn't exist. Making it a set provides
automatic de-duplication and O(1) removal of the component sets without an
algorithmic cost for the main [GroupSet] operations.

+
+  /// Whether the sets in [_sets] are guaranteed to be disjoint.
+  final bool _disjoint;
+
+  /// Creates a new set that's a view of the union of all sets in [sets].
+  ///
+  /// If any sets in [sets] change, this [GroupSet] will reflect that change. If

[floitsch, 2016/04/25 16:11:10]

reflects that change. ... reflects ...

[nweiz, 2016/04/26 21:23:53]

Done.

+  /// a new set is added to [sets], this [GroupSet] will reflect that as well.
+  ///
+  /// If [disjoint] is `true`, this assumes that all component sets are

[floitsch, 2016/04/25 16:11:09]

If [disjoint] is `true`, then all component sets must be disjoint. That is, they
must not contain any element in common. This makes ...

I wouldn't even mention "inconsistent" behavior.

[nweiz, 2016/04/26 21:23:52]

Done.
Haha, this is exactly the opposite of Lasse's feedback. I think it's reasonable
to mention, though, since otherwise users might expect this to produce an error.

[floitsch, 2016/04/27 10:56:52]

Imho, it's the change to "must" that makes the 'inconsistent behavior'
unnecessary.

[Lasse Reichstein Nielsen, 2016/04/27 12:17:53]

Disagree. When we use "must" we generally mean that otherwise an error will be
raised. In this case there is no error thrown, just inconsistent behavior, and I
think it's fine to warn the user that we won't be catching that error for them.
We could reduce the text to "should" instead of "must", but it's more than just
a recommendation. It really is an error that we just don't catch actively.

So, I think the best solution is to say "must" and then say that doing it anyway
is not throwing as you would otherwise expect.

[floitsch, 2016/04/27 12:31:20]

I can live with the comment, so let's just keep it.

Personally, I do think that `must` should encompass inconsistent behavior if the
rules aren't respected. We shouldn't need to check it. "Must" means bad things
will happen if you don't respect the rules. An error is obviously the best bad
thing, but inconsistent behavior plainly falls into that category too.

+  /// disjoint—that is, that they contain no elements in common. This makes many

[floitsch, 2016/04/25 16:11:09]

Avoid non-ascii characters in documentation.

[nweiz, 2016/04/26 21:23:53]

Done, although I don't think this is a good general rule—it's 2016 and pretty
much everything can display Unicode effectively.

If this should be a rule, it should be mentioned in Effective Dart.

+  /// operations including [length] more efficient. If the component sets turn
+  /// out not to be disjoint, some operations may behave inconsistently.
+  GroupSet(this._sets, {bool disjoint: false}) : _disjoint = disjoint;
+
+  /// Creates a new set that's a view of the union of all sets in [sets].
+  ///
+  /// If any sets in [sets] change, this [GroupSet] will reflect that change.

[floitsch, 2016/04/25 16:11:10]

reflects

[nweiz, 2016/04/26 21:23:53]

Done.

+  /// However, unlike [new GroupSet], this creates a copy of its parameter, so
+  /// changes in [sets] will not be reflected in this [GroupSet].

[floitsch, 2016/04/25 16:11:10]

are not reflected

[nweiz, 2016/04/26 21:23:53]

Done.

+  ///
+  /// If [disjoint] is `true`, this assumes that all component sets are

[floitsch, 2016/04/25 16:11:10]

as above.

[nweiz, 2016/04/26 21:23:52]

Done.

+  /// disjoint—that is, that they contain no elements in common. This makes many
+  /// operations including [length] more efficient. If the component sets turn
+  /// out not to be disjoint, some operations may behave inconsistently.
+  GroupSet.from(Iterable<Set<E>> sets, {bool disjoint: false})
+      : this(sets.toSet(), disjoint: disjoint);
+
+  int get length => _disjoint
+      ? _sets.fold(0, (length, set) => length + set.length)
+      : _iterable.length;
+
+  Iterator<E> get iterator => _iterable.iterator;
+
+  /// Returns an iterable over the contents of all the sets in [this].
+  Iterable<E> get _iterable =>
+      _disjoint ? _sets.expand((set) => set) : _dedupIterable;
+
+  /// Returns an iterable over the contents of all the sets in [this] that
+  /// de-duplicates elements.
+  ///
+  /// If the sets aren't guaranteed to be disjoint, this keeps track of the
+  /// elements we've already emitted so that we can de-duplicate them.
+  Iterable<E> get _dedupIterable {
+    var seen = new Set<E>();
+    return _sets.expand((set) => set).where((element) {
+      if (seen.contains(element)) return false;
+      seen.add(element);
+      return true;
+    });
+  }
+
+  bool contains(Object element) => _sets.any((set) => set.contains(element));
+
+  E lookup(Object element) {
+    if (element == null) return null;
+
+    return _sets
+        .map((set) => set.lookup(element))
+        .firstWhere((result) => result != null, orElse: () => null);
+  }
+
+  Set<E> toSet() {
+    var result = new Set<E>();
+    for (var set in _sets) {
+      result.addAll(set);
+    }
+    return result;
+  }
+}