Add GroupSet and SetGroup classes.
GroupSet provides a view of the union of a set of sets. SetGroup
provides an easy way to manage a GroupSet in a class context.
R=floitsch@google.com, lrn@google.com
Review URL: https://codereview.chromium.org//1873373002 .
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 01da16b..559e810 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,4 +1,9 @@
-## 1.5.2
+## 1.6.0
+
+* Add a `UnionSet` class that provides a view of the union of a set of sets.
+
+* Add a `UnionSetController` class that provides a convenient way to manage the
+ contents of a `UnionSet`.
* Fix another incorrectly-declared generic type.
diff --git a/lib/collection.dart b/lib/collection.dart
index b2c7e73..95b8479 100644
--- a/lib/collection.dart
+++ b/lib/collection.dart
@@ -9,5 +9,7 @@
export "src/iterable_zip.dart";
export "src/priority_queue.dart";
export "src/queue_list.dart";
+export "src/union_set.dart";
+export "src/union_set_controller.dart";
export "src/unmodifiable_wrappers.dart";
export "src/wrappers.dart";
diff --git a/lib/src/union_set.dart b/lib/src/union_set.dart
new file mode 100644
index 0000000..5d88b6b
--- /dev/null
+++ b/lib/src/union_set.dart
@@ -0,0 +1,88 @@
+// 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;
+ }
+}
diff --git a/lib/src/union_set_controller.dart b/lib/src/union_set_controller.dart
new file mode 100644
index 0000000..1d0eb74
--- /dev/null
+++ b/lib/src/union_set_controller.dart
@@ -0,0 +1,54 @@
+// 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 'union_set.dart';
+
+/// A controller that exposes a view of the union of a collection of sets.
+///
+/// This is a convenience class for creating a [UnionSet] whose contents change
+/// over the lifetime of a class. For example:
+///
+/// ```dart
+/// class Engine {
+/// Set<Test> get activeTests => _activeTestsGroup.set;
+/// final _activeTestsGroup = new UnionSetController<Test>();
+///
+/// void addSuite(Suite suite) {
+/// _activeTestsGroup.add(suite.tests);
+/// _runSuite(suite);
+/// _activeTestsGroup.remove(suite.tests);
+/// }
+/// }
+/// ```
+class UnionSetController<E> {
+ /// The [UnionSet] that provides a view of the union of sets in [this].
+ UnionSet<E> get set => _set;
+ UnionSet<E> _set;
+
+ /// The sets whose union is exposed through [set].
+ final _sets = new Set<Set<E>>();
+
+ /// Creates a set of sets that provides a view of the union of those sets.
+ ///
+ /// 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.
+ UnionSetController({bool disjoint: false}) {
+ _set = new UnionSet<E>(_sets, disjoint: disjoint);
+ }
+
+ /// Adds the contents of [component] to [set].
+ ///
+ /// If the contents of [component] change over time, [set] will change
+ /// accordingly.
+ void add(Set<E> component) {
+ _sets.add(component);
+ }
+
+ /// Removes the contents of [component] to [set].
+ ///
+ /// If another set in [this] has overlapping elements with [component], those
+ /// elements will remain in [set].
+ bool remove(Set<E> component) => _sets.remove(component);
+}
diff --git a/pubspec.yaml b/pubspec.yaml
index 00a3f7c..992e7ae 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,5 +1,5 @@
name: collection
-version: 1.5.2-dev
+version: 1.6.0
author: Dart Team <misc@dartlang.org>
description: Collections and utilities functions and classes related to collections.
homepage: https://www.github.com/dart-lang/collection
diff --git a/test/union_set_controller_test.dart b/test/union_set_controller_test.dart
new file mode 100644
index 0000000..aa8c1c9
--- /dev/null
+++ b/test/union_set_controller_test.dart
@@ -0,0 +1,36 @@
+// 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 "package:test/test.dart";
+
+import "package:collection/collection.dart";
+
+void main() {
+ var controller;
+ var innerSet;
+ setUp(() {
+ innerSet = new Set.from([1, 2, 3]);
+ controller = new UnionSetController<int>()..add(innerSet);
+ });
+
+ test("exposes a union set", () {
+ expect(controller.set, unorderedEquals([1, 2, 3]));
+
+ controller.add(new Set.from([3, 4, 5]));
+ expect(controller.set, unorderedEquals([1, 2, 3, 4, 5]));
+
+ controller.remove(innerSet);
+ expect(controller.set, unorderedEquals([3, 4, 5]));
+ });
+
+ test("exposes a disjoint union set", () {
+ expect(controller.set, unorderedEquals([1, 2, 3]));
+
+ controller.add(new Set.from([4, 5, 6]));
+ expect(controller.set, unorderedEquals([1, 2, 3, 4, 5, 6]));
+
+ controller.remove(innerSet);
+ expect(controller.set, unorderedEquals([4, 5, 6]));
+ });
+}
diff --git a/test/union_set_test.dart b/test/union_set_test.dart
new file mode 100644
index 0000000..15d9d49
--- /dev/null
+++ b/test/union_set_test.dart
@@ -0,0 +1,222 @@
+// 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 "package:test/test.dart";
+
+import "package:collection/collection.dart";
+
+void main() {
+ group("with an empty outer set", () {
+ var set;
+ setUp(() {
+ set = new UnionSet<int>(new Set());
+ });
+
+ test("length returns 0", () {
+ expect(set.length, equals(0));
+ });
+
+ test("contains() returns false", () {
+ expect(set.contains(0), isFalse);
+ expect(set.contains(null), isFalse);
+ expect(set.contains("foo"), isFalse);
+ });
+
+ test("lookup() returns null", () {
+ expect(set.lookup(0), isNull);
+ expect(set.lookup(null), isNull);
+ expect(set.lookup("foo"), isNull);
+ });
+
+ test("toSet() returns an empty set", () {
+ expect(set.toSet(), isEmpty);
+ expect(set.toSet(), isNot(same(set)));
+ });
+
+ test("map() doesn't run on any elements", () {
+ expect(set.map(expectAsync((_) {}, count: 0)), isEmpty);
+ });
+ });
+
+ group("with multiple disjoint sets", () {
+ var set;
+ setUp(() {
+ set = new UnionSet<int>.from([
+ new Set.from([1, 2]),
+ new Set.from([3, 4]),
+ new Set.from([5]),
+ new Set()
+ ], disjoint: true);
+ });
+
+ test("length returns the total length", () {
+ expect(set.length, equals(5));
+ });
+
+ test("contains() returns whether any set contains the element", () {
+ expect(set.contains(1), isTrue);
+ expect(set.contains(4), isTrue);
+ expect(set.contains(5), isTrue);
+ expect(set.contains(6), isFalse);
+ });
+
+ test("lookup() returns elements that are in any set", () {
+ expect(set.lookup(1), equals(1));
+ expect(set.lookup(4), equals(4));
+ expect(set.lookup(5), equals(5));
+ expect(set.lookup(6), isNull);
+ });
+
+ test("toSet() returns the union of all the sets", () {
+ expect(set.toSet(), unorderedEquals([1, 2, 3, 4, 5]));
+ expect(set.toSet(), isNot(same(set)));
+ });
+
+ test("map() maps the elements", () {
+ expect(set.map((i) => i * 2), unorderedEquals([2, 4, 6, 8, 10]));
+ });
+ });
+
+ group("with multiple overlapping sets", () {
+ var set;
+ setUp(() {
+ set = new UnionSet<int>.from([
+ new Set.from([1, 2, 3]),
+ new Set.from([3, 4]),
+ new Set.from([5, 1]),
+ new Set()
+ ]);
+ });
+
+ test("length returns the total length", () {
+ expect(set.length, equals(5));
+ });
+
+ test("contains() returns whether any set contains the element", () {
+ expect(set.contains(1), isTrue);
+ expect(set.contains(4), isTrue);
+ expect(set.contains(5), isTrue);
+ expect(set.contains(6), isFalse);
+ });
+
+ test("lookup() returns elements that are in any set", () {
+ expect(set.lookup(1), equals(1));
+ expect(set.lookup(4), equals(4));
+ expect(set.lookup(5), equals(5));
+ expect(set.lookup(6), isNull);
+ });
+
+ test("lookup() returns the first element in an ordered context", () {
+ var duration1 = new Duration(seconds: 0);
+ var duration2 = new Duration(seconds: 0);
+ expect(duration1, equals(duration2));
+ expect(duration1, isNot(same(duration2)));
+
+ var set = new UnionSet.from([
+ new Set.from([duration1]),
+ new Set.from([duration2])
+ ]);
+
+ expect(set.lookup(new Duration(seconds: 0)), same(duration1));
+ });
+
+ test("toSet() returns the union of all the sets", () {
+ expect(set.toSet(), unorderedEquals([1, 2, 3, 4, 5]));
+ expect(set.toSet(), isNot(same(set)));
+ });
+
+ test("map() maps the elements", () {
+ expect(set.map((i) => i * 2), unorderedEquals([2, 4, 6, 8, 10]));
+ });
+ });
+
+ group("after an inner set was modified", () {
+ var set;
+ setUp(() {
+ var innerSet = new Set.from([3, 7]);
+ set = new UnionSet<int>.from([
+ new Set.from([1, 2]),
+ new Set.from([5]),
+ innerSet
+ ]);
+
+ innerSet.add(4);
+ innerSet.remove(7);
+ });
+
+ test("length returns the total length", () {
+ expect(set.length, equals(5));
+ });
+
+ test("contains() returns true for a new element", () {
+ expect(set.contains(4), isTrue);
+ });
+
+ test("contains() returns false for a removed element", () {
+ expect(set.contains(7), isFalse);
+ });
+
+ test("lookup() returns a new element", () {
+ expect(set.lookup(4), equals(4));
+ });
+
+ test("lookup() doesn't returns a removed element", () {
+ expect(set.lookup(7), isNull);
+ });
+
+ test("toSet() returns the union of all the sets", () {
+ expect(set.toSet(), unorderedEquals([1, 2, 3, 4, 5]));
+ expect(set.toSet(), isNot(same(set)));
+ });
+
+ test("map() maps the elements", () {
+ expect(set.map((i) => i * 2), unorderedEquals([2, 4, 6, 8, 10]));
+ });
+ });
+
+ group("after the outer set was modified", () {
+ var set;
+ setUp(() {
+ var innerSet = new Set.from([6]);
+ var outerSet = new Set.from([
+ new Set.from([1, 2]),
+ new Set.from([5]),
+ innerSet
+ ]);
+
+ set = new UnionSet<int>(outerSet);
+ outerSet.remove(innerSet);
+ outerSet.add(new Set.from([3, 4]));
+ });
+
+ test("length returns the total length", () {
+ expect(set.length, equals(5));
+ });
+
+ test("contains() returns true for a new element", () {
+ expect(set.contains(4), isTrue);
+ });
+
+ test("contains() returns false for a removed element", () {
+ expect(set.contains(6), isFalse);
+ });
+
+ test("lookup() returns a new element", () {
+ expect(set.lookup(4), equals(4));
+ });
+
+ test("lookup() doesn't returns a removed element", () {
+ expect(set.lookup(6), isNull);
+ });
+
+ test("toSet() returns the union of all the sets", () {
+ expect(set.toSet(), unorderedEquals([1, 2, 3, 4, 5]));
+ expect(set.toSet(), isNot(same(set)));
+ });
+
+ test("map() maps the elements", () {
+ expect(set.map((i) => i * 2), unorderedEquals([2, 4, 6, 8, 10]));
+ });
+ });
+}
