Index: mojo/public/dart/third_party/barback/lib/src/utils/multiset.dart |
diff --git a/mojo/public/dart/third_party/barback/lib/src/utils/multiset.dart b/mojo/public/dart/third_party/barback/lib/src/utils/multiset.dart |
new file mode 100644 |
index 0000000000000000000000000000000000000000..20d1c57e04a18098bda124a038bf68f52b096c25 |
--- /dev/null |
+++ b/mojo/public/dart/third_party/barback/lib/src/utils/multiset.dart |
@@ -0,0 +1,63 @@ |
+// Copyright (c) 2013, 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. |
+ |
+library barback.utils.multiset; |
+ |
+import 'dart:collection'; |
+ |
+/// A set of objects where each object can appear multiple times. |
+/// |
+/// Like a set, this has amortized O(1) insertion, removal, and |
+/// existence-checking of elements. Counting the number of copies of an element |
+/// in the set is also amortized O(1). |
+/// |
+/// Distinct elements retain insertion order. Additional copies of an element |
+/// beyond the first are grouped with the original element. |
+/// |
+/// If multiple equal elements are added, only the first actual object is |
+/// retained. |
+class Multiset<E> extends IterableBase<E> { |
+ /// A map from each element in the set to the number of copies of that element |
+ /// in the set. |
+ final _map = new Map<E, int>(); |
+ |
+ Iterator<E> get iterator { |
+ return _map.keys.expand((element) { |
+ return new Iterable.generate(_map[element], (_) => element); |
+ }).iterator; |
+ } |
+ |
+ Multiset() |
+ : super(); |
+ |
+ /// Creates a multi-set and initializes it using the contents of [other]. |
+ Multiset.from(Iterable<E> other) |
+ : super() { |
+ other.forEach(add); |
+ } |
+ |
+ /// Adds [value] to the set. |
+ void add(E value) { |
+ _map.putIfAbsent(value, () => 0); |
+ _map[value] += 1; |
+ } |
+ |
+ /// Removes one copy of [value] from the set. |
+ /// |
+ /// Returns whether a copy of [value] was removed, regardless of whether more |
+ /// copies remain. |
+ bool remove(E value) { |
+ if (!_map.containsKey(value)) return false; |
+ |
+ _map[value] -= 1; |
+ if (_map[value] == 0) _map.remove(value); |
+ return true; |
+ } |
+ |
+ /// Returns whether [value] is in the set. |
+ bool contains(E value) => _map.containsKey(value); |
+ |
+ /// Returns the number of copies of [value] in the set. |
+ int count(E value) => _map.containsKey(value) ? _map[value] : 0; |
+} |