OLD | NEW |
(Empty) | |
| 1 // Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. |
| 4 |
| 5 import 'dart:collection'; |
| 6 |
| 7 import 'unmodifiable_wrappers.dart'; |
| 8 |
| 9 /// A single set that provides a view of the union over a set of sets. |
| 10 /// |
| 11 /// Since this is just a view, it reflects all changes in the underlying sets. |
| 12 /// |
| 13 /// If an element is in multiple sets and the outer set is ordered, the version |
| 14 /// in the earliest inner set is preferred. Component sets are assumed to use |
| 15 /// `==` and `hashCode` for equality. |
| 16 class UnionSet<E> extends SetBase<E> with UnmodifiableSetMixin<E> { |
| 17 /// The set of sets that this provides a view of. |
| 18 final Set<Set<E>> _sets; |
| 19 |
| 20 /// Whether the sets in [_sets] are guaranteed to be disjoint. |
| 21 final bool _disjoint; |
| 22 |
| 23 /// Creates a new set that's a view of the union of all sets in [sets]. |
| 24 /// |
| 25 /// If any sets in [sets] change, this [UnionSet] reflects that change. If a |
| 26 /// new set is added to [sets], this [UnionSet] reflects that as well. |
| 27 /// |
| 28 /// If [disjoint] is `true`, then all component sets must be disjoint. That |
| 29 /// is, that they contain no elements in common. This makes many operations |
| 30 /// including [length] more efficient. If the component sets turn out not to |
| 31 /// be disjoint, some operations may behave inconsistently. |
| 32 UnionSet(this._sets, {bool disjoint: false}) : _disjoint = disjoint; |
| 33 |
| 34 /// Creates a new set that's a view of the union of all sets in [sets]. |
| 35 /// |
| 36 /// If any sets in [sets] change, this [UnionSet] reflects that change. |
| 37 /// However, unlike [new UnionSet], this creates a copy of its parameter, so |
| 38 /// changes in [sets] aren't reflected in this [UnionSet]. |
| 39 /// |
| 40 /// If [disjoint] is `true`, then all component sets must be disjoint. That |
| 41 /// is, that they contain no elements in common. This makes many operations |
| 42 /// including [length] more efficient. If the component sets turn out not to |
| 43 /// be disjoint, some operations may behave inconsistently. |
| 44 UnionSet.from(Iterable<Set<E>> sets, {bool disjoint: false}) |
| 45 : this(sets.toSet(), disjoint: disjoint); |
| 46 |
| 47 int get length => _disjoint |
| 48 ? _sets.fold(0, (length, set) => length + set.length) |
| 49 : _iterable.length; |
| 50 |
| 51 Iterator<E> get iterator => _iterable.iterator; |
| 52 |
| 53 /// Returns an iterable over the contents of all the sets in [this]. |
| 54 Iterable<E> get _iterable => |
| 55 _disjoint ? _sets.expand((set) => set) : _dedupIterable; |
| 56 |
| 57 /// Returns an iterable over the contents of all the sets in [this] that |
| 58 /// de-duplicates elements. |
| 59 /// |
| 60 /// If the sets aren't guaranteed to be disjoint, this keeps track of the |
| 61 /// elements we've already emitted so that we can de-duplicate them. |
| 62 Iterable<E> get _dedupIterable { |
| 63 var seen = new Set<E>(); |
| 64 return _sets.expand((set) => set).where((element) { |
| 65 if (seen.contains(element)) return false; |
| 66 seen.add(element); |
| 67 return true; |
| 68 }); |
| 69 } |
| 70 |
| 71 bool contains(Object element) => _sets.any((set) => set.contains(element)); |
| 72 |
| 73 E lookup(Object element) { |
| 74 if (element == null) return null; |
| 75 |
| 76 return _sets |
| 77 .map((set) => set.lookup(element)) |
| 78 .firstWhere((result) => result != null, orElse: () => null); |
| 79 } |
| 80 |
| 81 Set<E> toSet() { |
| 82 var result = new Set<E>(); |
| 83 for (var set in _sets) { |
| 84 result.addAll(set); |
| 85 } |
| 86 return result; |
| 87 } |
| 88 } |
OLD | NEW |