Add GroupSet and SetGroup classes.

lib/src/group_set.dart

Index: lib/src/group_set.dart
diff --git a/lib/src/group_set.dart b/lib/src/group_set.dart
new file mode 100644
index 0000000000000000000000000000000000000000..e3500af7966ca86daa8d653a9e9f6ce974e19524
--- /dev/null
+++ b/lib/src/group_set.dart
@@ -0,0 +1,81 @@
+// 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.

[Lasse Reichstein Nielsen, 2016/04/12 13:55:22]

Why must it be a set of sets and not just any collection of sets?
I.e., why Set<Set> and not Iterable<Set>?
All the code below looks like it would work anyway, and you avoid the extra
.toSet in the constructor. If a user wants to de-duplicate the input they can
call toSet before passing it to the GroupSet constructor.

[nweiz, 2016/04/13 21:30:06]

Supporting any iterable would be confusing. APIs that take iterables pretty much
universally only iterate over them once in case they're lazily generated from
some expensive or side-effect-y computation, so taking an iterable with the
intent to iterate over it repeatedly would break user expectations.

Given that, the choice is what concrete collection type to use. Set seems
logical since duplicating an element doesn't change the semantics.

+///
+/// 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.
+class GroupSet<E> extends SetMixin<E> with UnmodifiableSetMixin<E> {
+  /// The set of sets that this provides a view of.
+  final Set<Set<E>> _sets;
+
+  /// 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
+  /// 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
+  /// disjoint—that is, that they contain no elements in common. This makes
+  /// many operations including [length] more efficient.
+  GroupSet(this._sets, {bool disjoint: false}) : _disjoint = disjoint;

[Lasse Reichstein Nielsen, 2016/04/12 13:55:22]

As usual, I recommend not having a private parameter name in the exposed API.

[nweiz, 2016/04/13 21:30:06]

Acknowledged, but this is a very common pattern in Dart code and it doesn't seem
to cause problems in practice.

+
+  /// 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.
+  /// However, unlike [new GroupSet], this creates a copy of its parameter, so
+  /// changes in [sets] will not be reflected in this [GroupSet].
+  ///
+  /// If [disjoint] is `true`, this assumes that all component sets are
+  /// disjoint—that is, that they contain no elements in common. This makes
+  /// many operations including [length] more efficient.
+  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;
+
+  Iterable<E> get _iterable {
+    if (_disjoint) return _sets.expand((set) => set);
+

[Lasse Reichstein Nielsen, 2016/04/12 13:55:22]

Consider moving the following code into a separate helper function.
That increases the likelihood that the function can be inlined in the _disjoint
case.

[nweiz, 2016/04/13 21:30:06]

Done.

+    // If the sets aren't guaranteed to be disjoint, keep track of the elements
+    // we've already emitted so that we can de-duplicate elements.
+    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;
+  }
+}