Index: packages/collection/lib/src/union_set.dart |
diff --git a/packages/collection/lib/src/union_set.dart b/packages/collection/lib/src/union_set.dart |
new file mode 100644 |
index 0000000000000000000000000000000000000000..5d88b6bca66dcacfc8e98ca397f3ac9b4d5099d8 |
--- /dev/null |
+++ b/packages/collection/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; |
+ } |
+} |