| 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 |