Add GroupSet and SetGroup classes.

lib/src/union_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 the union over a set of sets.
+///
+/// Since this is just a view, it reflects all 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 UnionSet<E> extends SetBase<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 [UnionSet] reflects that change. If a
+  /// new set is added to [sets], this [UnionSet] reflects that as well.
+  ///
+  /// If [disjoint] is `true`, then all component sets must be 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.
+  UnionSet(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 [UnionSet] reflects that change.
+  /// However, unlike [new UnionSet], this creates a copy of its parameter, so
+  /// changes in [sets] aren't reflected in this [UnionSet].
+  ///
+  /// If [disjoint] is `true`, then all component sets must be 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.
+  UnionSet.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;
+  }
+}