OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 library barback.utils.multiset; | 5 library barback.utils.multiset; |
6 | 6 |
7 import 'dart:collection'; | 7 import 'dart:collection'; |
8 | 8 |
9 /// A set of objects where each object can appear multiple times. | 9 /// A set of objects where each object can appear multiple times. |
10 /// | 10 /// |
11 /// Like a set, this has amortized O(1) insertion, removal, and | 11 /// Like a set, this has amortized O(1) insertion, removal, and |
12 /// existence-checking of elements. Counting the number of copies of an element | 12 /// existence-checking of elements. Counting the number of copies of an element |
13 /// in the set is also amortized O(1). | 13 /// in the set is also amortized O(1). |
14 /// | 14 /// |
15 /// Distinct elements retain insertion order. Additional copies of an element | 15 /// Distinct elements retain insertion order. Additional copies of an element |
16 /// beyond the first are grouped with the original element. | 16 /// beyond the first are grouped with the original element. |
17 /// | 17 /// |
18 /// If multiple equal elements are added, only the first actual object is | 18 /// If multiple equal elements are added, only the first actual object is |
19 /// retained. | 19 /// retained. |
20 class Multiset<E> extends IterableBase<E> { | 20 class Multiset<E> extends IterableBase<E> { |
21 /// A map from each element in the set to the number of copies of that element | 21 /// A map from each element in the set to the number of copies of that element |
22 /// in the set. | 22 /// in the set. |
23 final _map = new Map<E, int>(); | 23 final _map = new Map<E, int>(); |
24 | 24 |
25 Iterator<E> get iterator { | 25 Iterator<E> get iterator { |
26 return _map.keys.expand((element) { | 26 return _map.keys |
27 return new Iterable.generate(_map[element], (_) => element); | 27 .expand((element) => |
28 }).iterator; | 28 new Iterable<E>.generate(_map[element], (_) => element)) |
| 29 .iterator; |
29 } | 30 } |
30 | 31 |
31 Multiset() | 32 Multiset() |
32 : super(); | 33 : super(); |
33 | 34 |
34 /// Creates a multi-set and initializes it using the contents of [other]. | 35 /// Creates a multi-set and initializes it using the contents of [other]. |
35 Multiset.from(Iterable<E> other) | 36 Multiset.from(Iterable<E> other) |
36 : super() { | 37 : super() { |
37 other.forEach(add); | 38 other.forEach(add); |
38 } | 39 } |
(...skipping 10 matching lines...) Expand all Loading... |
49 /// copies remain. | 50 /// copies remain. |
50 bool remove(E value) { | 51 bool remove(E value) { |
51 if (!_map.containsKey(value)) return false; | 52 if (!_map.containsKey(value)) return false; |
52 | 53 |
53 _map[value] -= 1; | 54 _map[value] -= 1; |
54 if (_map[value] == 0) _map.remove(value); | 55 if (_map[value] == 0) _map.remove(value); |
55 return true; | 56 return true; |
56 } | 57 } |
57 | 58 |
58 /// Returns whether [value] is in the set. | 59 /// Returns whether [value] is in the set. |
59 bool contains(E value) => _map.containsKey(value); | 60 bool contains(Object value) => _map.containsKey(value); |
60 | 61 |
61 /// Returns the number of copies of [value] in the set. | 62 /// Returns the number of copies of [value] in the set. |
62 int count(E value) => _map.containsKey(value) ? _map[value] : 0; | 63 int count(E value) => _map.containsKey(value) ? _map[value] : 0; |
63 } | 64 } |
OLD | NEW |