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();
 }
+
+/**
+ * Creates an unmodifiable [Set] that delegates all operations to a base map's

[Lasse Reichstein Nielsen, 2014/05/09 09:00:17]

How about:
  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.

If we had a SetMixin, this could likely be implemented efficiently on top of
that (except for lookup, which sucks).

[nweiz, 2014/05/19 20:58:48]

Done.

+ * keys.
+ *
+ * This class can be used to make a `Map` look like a `Set`. Note that [lookup]
+ * is not `O(1)` for this set.

[Lasse Reichstein Nielsen, 2014/05/09 09:00:17]

Or say that it is unsupported, if we can't find a way to support it.

[floitsch, 2014/05/09 09:49:41]

I think it's ok to have the slow method.

[Lasse Reichstein Nielsen, 2014/05/09 10:50:48]

It's not that it's slow, but that it's wrong.
Testing for map.containsKey(key) first won't solve the problem.
It could also be that the map contains two keys that are == to the argument to
lookup, but only one that is considered equal by the map.

E.g.:
 var m = new LinkedHashMap.identity()..[-0.0] = 42 .. [0.0] = 37;
 print(m.lookup(0.0));   // -0.0 ?!?

[Lasse Reichstein Nielsen, 2014/05/09 10:52:52]

Should ofcourse be:
  var m = new LinkedHashMap.identity()..[-0.0] = 42 .. [0.0] = 37;
  var s = new MapKeySet(m);
  print(m[0.0]);   // 37
  print(m[-0.0]);  // 42
  print(s.lookup(0.0));   // -0.0 ?!?
  print(m[s.lookup(0.0)]);  // 42 ?!?

[nweiz, 2014/05/19 20:58:48]

Marked as unsupported.

+ */
+class MapKeySet<E> extends _DelegatingIterableBase<E>
+    with UnmodifiableSetMixin<E> {
+  final Map<E, dynamic> _baseMap;
+
+  Iterable<E> get _base => _baseMap.keys;

[Lasse Reichstein Nielsen, 2014/05/09 09:00:17]

Move getter below constructor.

[nweiz, 2014/05/19 20:58:48]

Done.

+
+  MapKeySet(Map<E, dynamic> base) : _baseMap = base;
+
+  bool contains(Object element) => _baseMap.containsKey(element);
+
+  bool get isEmpty => _baseMap.isEmpty;
+
+  bool get isNotEmpty => _baseMap.isNotEmpty;
+
+  int get length => _baseMap.length;
+
+  String toString() => toSet().toString();

[Lasse Reichstein Nielsen, 2014/05/09 09:00:17]

The toSet operation may lose elements if the base map isn't using default
equality.
How about:
 var s = _baseMap.keys.toString();
 if (s[0] == '(' && s[s.length-1] == ')') 
   return "{" + s.substring(1, s.length - 1) + "}";
 }
 return s;

At least until we have a SetBase/SetMixin to get a toString from.

[floitsch, 2014/05/09 09:49:41]

Why not simply return "{${_base.join(', ')}}"; ?

[Lasse Reichstein Nielsen, 2014/05/09 10:50:48]

Yes, I think I mistakenly thought that _baseMap.keys.toString would avoid
cycles, but since it is a new Iterable each time, the cycle detection won't
detect it.

We should have a safe way to make toString, but I'll probably make a
SetBase/SetMixin "soon" which will solve it.

[nweiz, 2014/05/19 20:58:48]

Done.

+
+  bool containsAll(Iterable<Object> other) => other.every(contains);
+
+  Set<E> difference(Set<E> other) =>

[Lasse Reichstein Nielsen, 2014/05/09 09:00:17]

It should be commented that the set returned here is not of the same kind as the
current set, and doesn't necessarily use the same equality.
If the map was an identity map, the returned set here is an equality set, so it
may equate keys that were distinct in the original.

[nweiz, 2014/05/19 20:58:48]

Done.

+      where((element) => !other.contains(element)).toSet();
+
+  Set<E> intersection(Set<Object> other) =>
+      where((element) => other.contains(element)).toSet();

[Lasse Reichstein Nielsen, 2014/05/09 09:00:17]

"(element) => other.contains(element)" can be just "other.contains".

[nweiz, 2014/05/19 20:58:48]

Done.

+
+  E lookup(E element) => firstWhere((key) => element == key,

[Lasse Reichstein Nielsen, 2014/05/09 09:00:17]

Using == here might be incompatible with the actual equality of the Map. If the
set is an identity Map, then you may return something from this `lookup` even if
the `contains` returns false for the same argument. 

On the other hand, there is no good way to implement lookup using map
operations. (We should never have added lookup to the interface - it breaks
abstraction. Should we add a similar `MapEntry lookup(key)` to Map that returns
the actual key and value as a pair?)

I'd prefer to just throw "UnsupportedError" here, until we find a way to support
it correctly.

[floitsch, 2014/05/09 09:49:41]

I think that's too unexpected.
We should probably start by checking if the key is actually in the map.
if (!_baseMap.contains(element)) return null;
return firstWhere(...)

[nweiz, 2014/05/19 20:58:48]

I'm happy to do whichever you two agree on. For now I've changed it to
UnsupportedError.

+      orElse: () => null);
+
+  Set<E> union(Set<E> other) => toSet()..addAll(other);
+}
+
+/**
+ * Creates a [Set] that delegates all operations to a base map's values.
+ *
+ * This class can be used to make a `Map` whose keys are determinable from its
+ * values look like a `Set`.

[Lasse Reichstein Nielsen, 2014/05/09 09:00:17]

How about:

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

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

Could we use "Index" in the name somehow?

[nweiz, 2014/05/19 20:58:48]

Done.
We could call it "MapIndexSet", but I kind of like how "MapValueSet" parallels
"MapKeySet".

+ *
+ * For example, this might be used to expose a map from IDs to database records
+ * as a Set. The `keyForValue` function would be `(record) => record.id`, and
+ * this would allow users to write both `recordSet.add(databaseRecord)` and
+ * `recordMap[id]`.
+ */
+class MapValueSet<K, V> extends _DelegatingIterableBase<V> implements Set<V> {
+  final Map<K, V> _baseMap;
+  final Function _keyForValue;
+
+  Iterable<V> get _base => _baseMap.values;

[floitsch, 2014/05/09 09:49:41]

getter below constructor.

[nweiz, 2014/05/19 20:58:48]

Done.

+
+  /**
+   * 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;
+
+  bool contains(Object element) {
+    if (element is! V) return false;
+    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) {
+    var key = _keyForValue(value);

[floitsch, 2014/05/09 09:49:41]

K key = _keyForValue...

[nweiz, 2014/05/19 20:58:48]

Done, although this is contrary to the style guide.

+    if (_baseMap.containsKey(key)) return false;
+    _baseMap[key] = value;

[Lasse Reichstein Nielsen, 2014/05/09 09:00:17]

Maybe use:
  bool result = false;
  _baseMap.putIfAbsent(key, () { result = true; return value; });
  return result;

[nweiz, 2014/05/19 20:58:48]

Done.

+    return true;
+  }
+
+  void addAll(Iterable<V> elements) => elements.forEach(add);
+
+  void clear() => _baseMap.clear();
+
+  bool containsAll(Iterable<Object> other) => other.every(contains);
+
+  Set<V> difference(Set<V> other) =>

[Lasse Reichstein Nielsen, 2014/05/09 09:00:17]

Document that the returned set is not of the same type as this set, and might
not use the same equality relation.

[nweiz, 2014/05/19 20:58:48]

Done.

+      where((element) => !other.contains(element)).toSet();
+
+  Set<V> intersection(Set<Object> other) =>
+      where((element) => other.contains(element)).toSet();

[Lasse Reichstein Nielsen, 2014/05/09 09:00:17]

where(other.contains).toSet()

[nweiz, 2014/05/19 20:58:48]

Done.

+
+  V lookup(V element) => _baseMap[_keyForValue(element)];
+
+  bool remove(Object value) {
+    if (value is! V) return false;
+    var key = _keyForValue(value);
+    if (!_baseMap.containsKey(key)) return false;

[Lasse Reichstein Nielsen, 2014/05/09 09:00:17]

return _baseMap.remove(key) != null;

Since null values are disallowed by the "is! V" test above, and we require the
map to be consistent with the `_keyForValue` function, values should not be
null.

[nweiz, 2014/05/19 20:58:48]

I don't think we should necessarily disallow null. As a straw example,
_keyForValue could just be the identity function, in which case `null` is a
valid value. In general I think users expect "null" to be a valid value for
object types.

I'm changing the "is! V" check to handle null values, but if you feel strongly I
can encode the assumption that null values are disallowed.

+    _baseMap.remove(key);
+    return true;
+  }
+
+  void removeAll(Iterable<Object> elements) => elements.forEach(remove);
+
+  void removeWhere(bool test(V element)) {
+    new Map.from(_baseMap).forEach((key, value) {
+      if (test(value)) remove(key);

[Lasse Reichstein Nielsen, 2014/05/09 09:00:17]

-> _baseMap.remove(key)

The new map may not agree on equalty with _baseMap, so some elements may get
lost (e.g., if _baseMap is an identity map and contains keys that are equal but
not identical).

How about:

  var values = _baseMap.values.toList();
  for (var value in values) {
    if (test(value)) _baseMap.remove(_keyForValue(value));
  }

Or, if you do want to remove incompatible key/value pairs too:
  var toRemove = [];
  _baseMap.forEach((k, v) { if (test(v)) toRemove.add(k); });
  for (var k in toRemove) _baseMap.remove(k);
  

[nweiz, 2014/05/19 20:58:48]

Done.

+    });
+  }
+
+  void retainAll(Iterable<Object> elements) {

[Lasse Reichstein Nielsen, 2014/05/09 09:00:17]

I *so* regret keeping retainAll in the Set interface. It's always horrible to
implement.

+    var retainKeys = elements.where((element) => element is V)
+        .map((element) => _keyForValue(element)).toSet();

[Lasse Reichstein Nielsen, 2014/05/09 09:00:17]

There is a problem with equality here too. The equality on keys is not
necessarily equality. This set uses equality on the values, so we have to work
with that.

How about:

  Set<V> valuesToNotRemove = elements.toSet();  // Default equality is ok.
  List<K> keysToRemove = <K>[];
  _baseMap.forEach((key, value) {
    if (!valuesToNotRemove.contains(value)) keysToRemove.add(key);
  }
  for (K key in keysToRemove) _baseMap.remove(key);

or briefer:

  retainWhere(elements.toSet().contains);

  

[nweiz, 2014/05/19 20:58:48]

According to the retainAll documentation, element equality is based on the same
equality as [Set.contains], so these suggestions don't have the right behavior.
PTAL at my new implementation.

+    new Map.from(_baseMap).forEach((key, value) {
+      if (!retainKeys.contains(key)) remove(key);
+    });
+  }
+
+  void retainWhere(bool test(V element)) =>
+      removeWhere((element) => !test(element));
+
+  Set<V> union(Set<V> other) => toSet()..addAll(other);
+}