Track the original assets more efficiently in Phase.

pkg/barback/lib/src/multi_set.dart

Index: pkg/barback/lib/src/multi_set.dart
diff --git a/pkg/barback/lib/src/multi_set.dart b/pkg/barback/lib/src/multi_set.dart
new file mode 100644
index 0000000000000000000000000000000000000000..ab53a1ddad915dce51e5a0f08f7f6a7f4bdd5247
--- /dev/null
+++ b/pkg/barback/lib/src/multi_set.dart
@@ -0,0 +1,60 @@
+// 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.multi_set;
+
+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.
+class MultiSet<E> extends IterableBase<E> {

[Bob Nystrom, 2013/10/09 17:04:48]

Nit, but "multi" is a prefix, not a word, so this should be "Multiset", though
that also looks weird.

How about "Bag"?

[nweiz, 2013/10/15 21:32:06]

Renamed to "Multiset".

+  /// 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>();

[Bob Nystrom, 2013/10/09 17:04:48]

This assumes that all == E's will never need to be distinguished from each
other. In cases where E is mutable, or where the user cares about identity, this
doesn't do the same thing as a multiset that actually stored each added E
separately.

The semantics here are OK, but should be spelled out. Maybe:

"Elements are considered equal using their == operator. When multiple equal
objects are added, only the first one is retained."

[nweiz, 2013/10/15 21:32:06]

I think it's clear that equality is based on ==, but I'll mention that only the
first copy of equal elements is retained.

+
+  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;
+}