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.
+///
+/// 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.

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

Worth mentioning that the individual sets are assumed to use operator= equality.
If they don't, the GroupSet may not have a consistent behavior.

[nweiz, 2016/04/12 20:29:20]

Done. We could have the weaker requirement that the component sets have the same
equality semantics, but we'd have to do something like
`_sets.first.toSet()..clear()` in _iterable and that doesn't seem great.

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

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

.. and if the sets turn out to not be disjoint after all, some operations may
behave inconsistently.

[nweiz, 2016/04/12 20:29:20]

Done.

+  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.
+  /// 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);
+
+    // 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;
+  }
+}