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 a set of sets. | |
10 /// | |
11 /// This behaves like the union of all sets passed in to [new GroupSet]. Since | |
12 /// it's just a view, it will reflect any changes in the underlying sets. | |
13 /// | |
14 /// If an element is in multiple sets and the outer set is ordered, the version | |
15 /// in the earliest inner set is preferred. | |
Lasse Reichstein Nielsen
2016/04/12 13:55:22
Worth mentioning that the individual sets are assu
nweiz
2016/04/12 20:29:20
Done. We could have the weaker requirement that th
| |
16 class GroupSet<E> extends SetMixin<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 [GroupSet] will reflect that change. If | |
26 /// a new set is added to [sets], this [GroupSet] will reflect that as well. | |
27 /// | |
28 /// If [disjoint] is `true`, this assumes that all component sets are | |
29 /// disjoint—that is, that they contain no elements in common. This makes | |
30 /// 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 aft
nweiz
2016/04/12 20:29:20
Done.
| |
31 GroupSet(this._sets, {bool disjoint: false}) : _disjoint = disjoint; | |
32 | |
33 /// Creates a new set that's a view of the union of all sets in [sets]. | |
34 /// | |
35 /// If any sets in [sets] change, this [GroupSet] will reflect that change. | |
36 /// However, unlike [new GroupSet], this creates a copy of its parameter, so | |
37 /// changes in [sets] will not be reflected in this [GroupSet]. | |
38 /// | |
39 /// If [disjoint] is `true`, this assumes that all component sets are | |
40 /// disjoint—that is, that they contain no elements in common. This makes | |
41 /// many operations including [length] more efficient. | |
42 GroupSet.from(Iterable<Set<E>> sets, {bool disjoint: false}) | |
43 : this(sets.toSet(), disjoint: disjoint); | |
44 | |
45 int get length => _disjoint | |
46 ? _sets.fold(0, (length, set) => length + set.length) | |
47 : _iterable.length; | |
48 | |
49 Iterator<E> get iterator => _iterable.iterator; | |
50 | |
51 Iterable<E> get _iterable { | |
52 if (_disjoint) return _sets.expand((set) => set); | |
53 | |
54 // If the sets aren't guaranteed to be disjoint, keep track of the elements | |
55 // we've already emitted so that we can de-duplicate elements. | |
56 var seen = new Set<E>(); | |
57 return _sets.expand((set) => set).where((element) { | |
58 if (seen.contains(element)) return false; | |
59 seen.add(element); | |
60 return true; | |
61 }); | |
62 } | |
63 | |
64 bool contains(Object element) => _sets.any((set) => set.contains(element)); | |
65 | |
66 E lookup(Object element) { | |
67 if (element == null) return null; | |
68 | |
69 return _sets | |
70 .map((set) => set.lookup(element)) | |
71 .firstWhere((result) => result != null, orElse: () => null); | |
72 } | |
73 | |
74 Set<E> toSet() { | |
75 var result = new Set<E>(); | |
76 for (var set in _sets) { | |
77 result.addAll(set); | |
78 } | |
79 return result; | |
80 } | |
81 } | |
OLD | NEW |