Add MapKeySet and MapValueSet to the collection package.

pkg/collection/lib/wrappers.dart

 // 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.
 
 /**
  * Delegating wrappers for [Iterable], [List], [Set], [Queue] and [Map].
  *
  * Also adds unmodifiable views for `Set` and `Map`, and a fixed length
  * view for `List`. The unmodifable list view from `dart:collection` is exported
  * as well, just for completeness.
  */
 library dart.pkg.collection.wrappers;
 
 import "dart:collection";
 import "dart:math" show Random;
 
 export "dart:collection" show UnmodifiableListView;
 
 part "src/unmodifiable_wrappers.dart";
 
 /**
- * Creates an [Iterable] that delegates all operations to a base iterable.
+ * A base class for delegating iterables.
  *
- * This class can be used hide non-`Iterable` methods of an iterable object,
- * or it can be extended to add extra functionality on top of an existing
- * iterable object.
+ * Subclasses can provide a [_base] that should be delegated to. Unlike
+ * [DelegatingIterable], this allows the base to be created on demand.
  */
-class DelegatingIterable<E> implements Iterable<E> {
-  final Iterable<E> _base;
+abstract class _DelegatingIterableBase<E> implements Iterable<E> {
+  Iterable<E> get _base;
 
-  /**
-   * Create a wrapper that forwards operations to [base].
-   */
-  const DelegatingIterable(Iterable<E> base) : _base = base;
+  const _DelegatingIterableBase();
 
   bool any(bool test(E element)) => _base.any(test);
 
   bool contains(Object element) => _base.contains(element);
 
   E elementAt(int index) => _base.elementAt(index);
 
   bool every(bool test(E element)) => _base.every(test);
 
   Iterable expand(Iterable f(E element)) => _base.expand(f);
@@ skipping 41 matching lines @@
 
   List<E> toList({bool growable: true}) => _base.toList(growable: growable);
 
   Set<E> toSet() => _base.toSet();
 
   Iterable<E> where(bool test(E element)) => _base.where(test);
 
   String toString() => _base.toString();
 }
 
+/**
+ * Creates an [Iterable] that delegates all operations to a base iterable.
+ *
+ * This class can be used hide non-`Iterable` methods of an iterable object,
+ * or it can be extended to add extra functionality on top of an existing
+ * iterable object.
+ */
+class DelegatingIterable<E> extends _DelegatingIterableBase<E> {
+  final Iterable<E> _base;
+
+  /**
+   * Create a wrapper that forwards operations to [base].
+   */
+  const DelegatingIterable(Iterable<E> base) : _base = base;
+}
+
 
 /**
  * Creates a [List] that delegates all operations to a base list.
  *
  * This class can be used hide non-`List` methods of a list object,
  * or it can be extended to add extra functionality on top of an existing
  * list object.
  */
 class DelegatingList<E> extends DelegatingIterable<E> implements List<E> {
   const DelegatingList(List<E> base) : super(base);
@@ skipping 224 matching lines @@
   int get length => _base.length;
 
   V putIfAbsent(K key, V ifAbsent()) => _base.putIfAbsent(key, ifAbsent);
 
   V remove(Object key) => _base.remove(key);
 
   Iterable<V> get values => _base.values;
 
   String toString() => _base.toString();
 }
+
+/**
+ * An unmodifiable [Set] view of the keys of a [Map].
+ *
+ * The set delegates all operations to the underlying map.
+ *
+ * A `Map` can only contain each key once, so its keys can always
+ * be viewed as a `Set` without any loss, even if the [Map.keys]
+ * getter only shows an [Iterable] view of the keys.
+ *
+ * Note that [lookup] is not supported for this set.
+ */
+class MapKeySet<E> extends _DelegatingIterableBase<E>
+    with UnmodifiableSetMixin<E> {
+  final Map<E, dynamic> _baseMap;
+
+  MapKeySet(Map<E, dynamic> base) : _baseMap = base;
+
+  Iterable<E> get _base => _baseMap.keys;
+
+  bool contains(Object element) => _baseMap.containsKey(element);
+
+  bool get isEmpty => _baseMap.isEmpty;
+
+  bool get isNotEmpty => _baseMap.isNotEmpty;
+
+  int get length => _baseMap.length;
+
+  String toString() => "{${_base.join(', ')}}";
+
+  bool containsAll(Iterable<Object> other) => other.every(contains);
+
+  /**
+   * Returns a new set with the the elements of [this] that are not in [other].
+   *
+   * That is, the returned set contains all the elements of this [Set] that are
+   * not elements of [other] according to `other.contains`.
+   *
+   * Note that the returned set will use the default equality operation, which
+   * may be different than the equality operation [this] uses.
+   */
+  Set<E> difference(Set<E> other) =>
+      where((element) => !other.contains(element)).toSet();

[Lasse Reichstein Nielsen, 2014/05/20 12:26:31]

Maybe do:
   toSet()..removeWhere(other.contains)
and for intersection do:
   toSet()..retainWhere(other.contains);

If we change toSet to return an "equivalent set", this should start working
correctly.
At that point we still have the problem of implementing toSet, though, so it's
probably not worth changing this now.

[nweiz, 2014/05/20 21:35:24]

If only there were some way to extract the equality operation from a Map
instance.

[Lasse Reichstein Nielsen, 2014/05/21 05:57:44]

I thought about that, but you need more than just the equality operation to
re-create a map or set. For a HashMap, you need the hashCode and isValidKey, for
SplayTreeMap, you need the comparator and isValidKey.

Hmm, how about a class like:

  abstract class Equality<T> {
    bool equals(T a, T b);
    /// Returns empty map with key equality based on this equality.
    Map<T, dynamic> createMap();
    /// Returns empty set with element equality based on this equality.
    Set<T> createSet();
  }
with sub-classes like HashEquality and ComparatorEquality.

Then Map and Set (and, heck, Iterable) can have an "Equality get equality;"
getter.

[nweiz, 2014/05/21 18:00:55]

At this point, even adding a getter to Map or Set would be a
backwards-incompatible change, wouldn't it? There's a lot of code in the wild
that implements them.

[Lasse Reichstein Nielsen, 2014/05/21 19:01:06]

It's not impossible to add methods to existing classes, we just can't use those
methods, at least not in existing code. Then a class not implementing the new
method just gets a warning, but never an error.
It won't break existing code.

New code that expects the method will then break if put together with old
implementations, but that's a new problem in new code, not breaking existing
code.

I don't see this change happening, though :(

+
+  /**
+   * Returns a new set which is the intersection between [this] and [other].
+   *
+   * That is, the returned set contains all the elements of this [Set] that are
+   * also elements of [other] according to `other.contains`.
+   *
+   * Note that the returned set will use the default equality operation, which
+   * may be different than the equality operation [this] uses.
+   */
+  Set<E> intersection(Set<Object> other) => where(other.contains).toSet();
+
+  E lookup(E element) => throw new UnsupportedError(

[Lasse Reichstein Nielsen, 2014/05/20 12:26:31]

Add documentation on lookup that says that it is unsupported because there is no
corresponding operation on Map.

[nweiz, 2014/05/20 21:35:24]

Done.

+      "MapKeySet doesn't support lookup().");
+
+  /**
+   * Returns a new set which contains all the elements of [this] and [other].
+   *
+   * That is, the returned set contains all the elements of this [Set] and all
+   * the elements of [other].
+   *
+   * Note that the returned set will use the default equality operation, which
+   * may be different than the equality operation [this] uses.
+   */
+  Set<E> union(Set<E> other) => toSet()..addAll(other);
+}
+
+/**
+ * Creates a modifiable [Set] view of the values of a [Map].
+ * 
+ * The `Set` view assumes that the keys of the `Map` can be uniquely determined
+ * from the values. The `keyForValue` function passed to the constructor finds
+ * the key for a single value. The `keyForValue` function should be consistent
+ * with equality. If `value1 == value2` then `keyForValue(value1)` and
+ * `keyForValue(value2)` should be considered equal keys by the underlying map,
+ * and vice versa.
+ *
+ * Modifying the set will modify the underlying map based on the key returned by
+ * `keyForValue`

[Lasse Reichstein Nielsen, 2014/05/20 12:26:31]

End with '.'

[nweiz, 2014/05/20 21:35:24]

Done.

+ *
+ * If the `Map` contents are not compatible with the `keyForValue` function, the
+ * set will not work consistently, and may give meaningless responses or do
+ * inconsistent updates.
+ *
+ * This set can, for example, be used on a map from database record IDs to the
+ * records. It exposes the records as a set, and allows for writing both
+ * `recordSet.add(databaseRecord)` and `recordMap[id]`.
+ *
+ * Effectively, the map will act as a kind of index for the set.
+ */
+class MapValueSet<K, V> extends _DelegatingIterableBase<V> implements Set<V> {
+  final Map<K, V> _baseMap;
+  final Function _keyForValue;
+
+  /**
+   * Creates a new [MapValueSet] based on [base].
+   *
+   * [keyForValue] returns the key in the map that should be associated with the
+   * given value. The set's notion of equality is identical to the equality of
+   * the return values of [keyForValue].
+   */
+  MapValueSet(Map<K, V> base, K keyForValue(V value))
+      : _baseMap = base,
+        _keyForValue = keyForValue;
+
+  Iterable<V> get _base => _baseMap.values;
+
+  bool contains(Object element) {
+    if (element != null && element is! V) return false;

[Lasse Reichstein Nielsen, 2014/05/20 12:26:31]

Consider having an optional 'validKey' function as constructor parameter that
you can use here instead of "is! V", like we do for CustomHashMap and
SplayTreeMap. It can default to "(v) => v is V".

[nweiz, 2014/05/20 21:35:24]

I think I'll save that for a future addition.

+    return _baseMap.containsKey(_keyForValue(element));
+  }
+
+  bool get isEmpty => _baseMap.isEmpty;
+
+  bool get isNotEmpty => _baseMap.isNotEmpty;
+
+  int get length => _baseMap.length;
+
+  String toString() => toSet().toString();
+
+  bool add(V value) {
+    K key = _keyForValue(value);
+    bool result = false;
+    _baseMap.putIfAbsent(key, () {
+      result = true;
+      return value;
+    });
+    return result;
+  }
+
+  void addAll(Iterable<V> elements) => elements.forEach(add);
+
+  void clear() => _baseMap.clear();
+
+  bool containsAll(Iterable<Object> other) => other.every(contains);
+
+  /**
+   * Returns a new set with the the elements of [this] that are not in [other].
+   *
+   * That is, the returned set contains all the elements of this [Set] that are
+   * not elements of [other] according to `other.contains`.
+   *
+   * Note that the returned set will use the default equality operation, which
+   * may be different than the equality operation [this] uses.
+   */
+  Set<V> difference(Set<V> other) =>
+      where((element) => !other.contains(element)).toSet();
+
+  /**
+   * Returns a new set which is the intersection between [this] and [other].
+   *
+   * That is, the returned set contains all the elements of this [Set] that are
+   * also elements of [other] according to `other.contains`.
+   *
+   * Note that the returned set will use the default equality operation, which
+   * may be different than the equality operation [this] uses.
+   */
+  Set<V> intersection(Set<Object> other) => where(other.contains).toSet();
+
+  V lookup(V element) => _baseMap[_keyForValue(element)];
+
+  bool remove(Object value) {
+    if (value != null && value is! V) return false;
+    var key = _keyForValue(value);
+    if (!_baseMap.containsKey(key)) return false;
+    _baseMap.remove(key);
+    return true;
+  }
+
+  void removeAll(Iterable<Object> elements) => elements.forEach(remove);
+
+  void removeWhere(bool test(V element)) {
+    var toRemove = [];
+    _baseMap.forEach((key, value) {
+      if (test(value)) toRemove.add(key);
+    });
+    toRemove.forEach(_baseMap.remove);
+  }
+
+  void retainAll(Iterable<Object> elements) {
+    var toRetain = elements.where((element) => element is V)
+        .map((element) => _keyForValue(element)).toSet();

[Lasse Reichstein Nielsen, 2014/05/20 12:26:31]

This still looks dangerous if toSet generates a set with a different equality
than this set. Not that I can see a general solution.
Maybe just add to the class description that the map should use operator== for
key equality, or it won't work.
(Did I mention that I regret retainAll? :)

"(element) => _keyForValue(element)" can be just "_keyForValue".

[nweiz, 2014/05/20 21:35:24]

Okay, I think I've come up with an implementation that really avoids equality
pitfalls and is still O(n + m). PTAL

+    var toRemove = [];
+    _baseMap.forEach((key, value) {
+      if (!toRetain.contains(key)) toRemove.add(key);
+    });
+    toRemove.forEach(_baseMap.remove);
+  }
+
+  void retainWhere(bool test(V element)) =>
+      removeWhere((element) => !test(element));
+
+  /**
+   * Returns a new set which contains all the elements of [this] and [other].
+   *
+   * That is, the returned set contains all the elements of this [Set] and all
+   * the elements of [other].
+   *
+   * Note that the returned set will use the default equality operation, which
+   * may be different than the equality operation [this] uses.
+   */
+  Set<V> union(Set<V> other) => toSet()..addAll(other);
+}