Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
277563007:
Add MapKeySet and MapValueSet to the collection package. (Closed)
|
Created:
6 years, 7 months ago by nweiz Modified:
6 years, 7 months ago CC:
reviews_dartlang.org Visibility:
Public. |
DescriptionAdd MapKeySet and MapValueSet to the collection package.
These classes provide Set views that are implemented as Maps under the
covers.
BUG=18705
R=floitsch@google.com, lrn@google.com
Committed: https://code.google.com/p/dart/source/detail?r=36447
Patch Set 1 #
Total comments: 4
Patch Set 2 : more documentation #
Total comments: 39
Patch Set 3 : code review #
Total comments: 13
Patch Set 4 : code review #
Total comments: 4
Patch Set 5 : code review #
Messages
Total messages: 19 (0 generated)
DBC https://codereview.chromium.org/277563007/diff/1/pkg/collection/lib/wrappers.... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/1/pkg/collection/lib/wrappers.... pkg/collection/lib/wrappers.dart:395: * This class can be used to make a `Map` whose keys are determinable from its I'm a bit confused by this sentence. What's the use case?
https://codereview.chromium.org/277563007/diff/1/pkg/collection/lib/wrappers.... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/1/pkg/collection/lib/wrappers.... pkg/collection/lib/wrappers.dart:395: * This class can be used to make a `Map` whose keys are determinable from its On 2014/05/08 20:40:15, kevmoo wrote: > I'm a bit confused by this sentence. What's the use case? See my comment on the issue: https://code.google.com/p/dart/issues/detail?id=18705#c3
https://codereview.chromium.org/277563007/diff/1/pkg/collection/lib/wrappers.... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/1/pkg/collection/lib/wrappers.... pkg/collection/lib/wrappers.dart:395: * This class can be used to make a `Map` whose keys are determinable from its On 2014/05/08 21:14:56, nweiz wrote: > On 2014/05/08 20:40:15, kevmoo wrote: > > I'm a bit confused by this sentence. What's the use case? > > See my comment on the issue: > https://code.google.com/p/dart/issues/detail?id=18705#c3 Your comment makes the usage clear, but the docs here are a bit confusing IMHO. It might be worth an example.
https://codereview.chromium.org/277563007/diff/1/pkg/collection/lib/wrappers.... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/1/pkg/collection/lib/wrappers.... pkg/collection/lib/wrappers.dart:395: * This class can be used to make a `Map` whose keys are determinable from its On 2014/05/08 23:01:53, kevmoo wrote: > On 2014/05/08 21:14:56, nweiz wrote: > > On 2014/05/08 20:40:15, kevmoo wrote: > > > I'm a bit confused by this sentence. What's the use case? > > > > See my comment on the issue: > > https://code.google.com/p/dart/issues/detail?id=18705#c3 > > Your comment makes the usage clear, but the docs here are a bit confusing IMHO. > It might be worth an example. Done.
Florian, could you take a look at this and see if I missed something? https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:354: * Creates an unmodifiable [Set] that delegates all operations to a base map's 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). https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:358: * is not `O(1)` for this set. Or say that it is unsupported, if we can't find a way to support it. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:364: Iterable<E> get _base => _baseMap.keys; Move getter below constructor. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:376: String toString() => toSet().toString(); 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. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:380: Set<E> difference(Set<E> other) => 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. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:384: where((element) => other.contains(element)).toSet(); "(element) => other.contains(element)" can be just "other.contains". https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:386: E lookup(E element) => firstWhere((key) => element == key, 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. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:396: * values look like a `Set`. 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? https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:436: _baseMap[key] = value; Maybe use: bool result = false; _baseMap.putIfAbsent(key, () { result = true; return value; }); return result; https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:446: Set<V> difference(Set<V> other) => Document that the returned set is not of the same type as this set, and might not use the same equality relation. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:450: where((element) => other.contains(element)).toSet(); where(other.contains).toSet() https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:457: if (!_baseMap.containsKey(key)) return false; 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. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:466: if (test(value)) remove(key); -> _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); https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:470: void retainAll(Iterable<Object> elements) { I *so* regret keeping retainAll in the Set interface. It's always horrible to implement. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:472: .map((element) => _keyForValue(element)).toSet(); 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);
LGTM. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:358: * is not `O(1)` for this set. On 2014/05/09 09:00:17, Lasse Reichstein Nielsen wrote: > Or say that it is unsupported, if we can't find a way to support it. I think it's ok to have the slow method. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:376: String toString() => toSet().toString(); On 2014/05/09 09:00:17, Lasse Reichstein Nielsen wrote: > 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. Why not simply return "{${_base.join(', ')}}"; ? https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:386: E lookup(E element) => firstWhere((key) => element == key, On 2014/05/09 09:00:17, Lasse Reichstein Nielsen wrote: > 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. 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(...) https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:407: Iterable<V> get _base => _baseMap.values; getter below constructor. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:434: var key = _keyForValue(value); K key = _keyForValue...
https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:358: * is not `O(1)` for this set. 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 ?!? https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:376: String toString() => toSet().toString(); 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.
https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:358: * is not `O(1)` for this set. 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 ?!?
https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:354: * Creates an unmodifiable [Set] that delegates all operations to a base map's On 2014/05/09 09:00:17, Lasse Reichstein Nielsen wrote: > 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. Done. > If we had a SetMixin, this could likely be implemented efficiently on top of > that (except for lookup, which sucks). https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:358: * is not `O(1)` for this set. On 2014/05/09 10:52:52, Lasse Reichstein Nielsen wrote: > 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 ?!? Marked as unsupported. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:364: Iterable<E> get _base => _baseMap.keys; On 2014/05/09 09:00:17, Lasse Reichstein Nielsen wrote: > Move getter below constructor. Done. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:376: String toString() => toSet().toString(); On 2014/05/09 10:50:48, Lasse Reichstein Nielsen wrote: > 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. Done. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:380: Set<E> difference(Set<E> other) => On 2014/05/09 09:00:17, Lasse Reichstein Nielsen wrote: > 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. Done. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:384: where((element) => other.contains(element)).toSet(); On 2014/05/09 09:00:17, Lasse Reichstein Nielsen wrote: > "(element) => other.contains(element)" can be just "other.contains". Done. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:386: E lookup(E element) => firstWhere((key) => element == key, On 2014/05/09 09:49:41, floitsch wrote: > On 2014/05/09 09:00:17, Lasse Reichstein Nielsen wrote: > > 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. > > 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(...) I'm happy to do whichever you two agree on. For now I've changed it to UnsupportedError. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:396: * values look like a `Set`. On 2014/05/09 09:00:17, Lasse Reichstein Nielsen wrote: > 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. > ---- Done. > Could we use "Index" in the name somehow? We could call it "MapIndexSet", but I kind of like how "MapValueSet" parallels "MapKeySet". https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:407: Iterable<V> get _base => _baseMap.values; On 2014/05/09 09:49:41, floitsch wrote: > getter below constructor. Done. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:434: var key = _keyForValue(value); On 2014/05/09 09:49:41, floitsch wrote: > K key = _keyForValue... Done, although this is contrary to the style guide. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:436: _baseMap[key] = value; On 2014/05/09 09:00:17, Lasse Reichstein Nielsen wrote: > Maybe use: > bool result = false; > _baseMap.putIfAbsent(key, () { result = true; return value; }); > return result; Done. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:446: Set<V> difference(Set<V> other) => On 2014/05/09 09:00:17, Lasse Reichstein Nielsen wrote: > Document that the returned set is not of the same type as this set, and might > not use the same equality relation. Done. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:450: where((element) => other.contains(element)).toSet(); On 2014/05/09 09:00:17, Lasse Reichstein Nielsen wrote: > where(other.contains).toSet() Done. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:457: if (!_baseMap.containsKey(key)) return false; On 2014/05/09 09:00:17, Lasse Reichstein Nielsen wrote: > 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. > 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. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:466: if (test(value)) remove(key); On 2014/05/09 09:00:17, Lasse Reichstein Nielsen wrote: > -> _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); > Done. https://codereview.chromium.org/277563007/diff/20001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:472: .map((element) => _keyForValue(element)).toSet(); On 2014/05/09 09:00:17, Lasse Reichstein Nielsen wrote: > 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); > > 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.
lgtm https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:394: where((element) => !other.contains(element)).toSet(); 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. https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:407: E lookup(E element) => throw new UnsupportedError( Add documentation on lookup that says that it is unsupported because there is no corresponding operation on Map. https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:433: * `keyForValue` End with '.' https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:463: if (element != null && element is! V) return false; 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". https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:536: .map((element) => _keyForValue(element)).toSet(); 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".
https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:394: where((element) => !other.contains(element)).toSet(); On 2014/05/20 12:26:31, Lasse Reichstein Nielsen wrote: > 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. If only there were some way to extract the equality operation from a Map instance. https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:407: E lookup(E element) => throw new UnsupportedError( On 2014/05/20 12:26:31, Lasse Reichstein Nielsen wrote: > Add documentation on lookup that says that it is unsupported because there is no > corresponding operation on Map. Done. https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:433: * `keyForValue` On 2014/05/20 12:26:31, Lasse Reichstein Nielsen wrote: > End with '.' Done. https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:463: if (element != null && element is! V) return false; On 2014/05/20 12:26:31, Lasse Reichstein Nielsen wrote: > 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". I think I'll save that for a future addition. https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:536: .map((element) => _keyForValue(element)).toSet(); On 2014/05/20 12:26:31, Lasse Reichstein Nielsen wrote: > 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". Okay, I think I've come up with an implementation that really avoids equality pitfalls and is still O(n + m). PTAL
https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:394: where((element) => !other.contains(element)).toSet(); 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. https://codereview.chromium.org/277563007/diff/60001/pkg/collection/lib/wrapp... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/60001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:549: _baseMap[pair.first] = pair.last; Nice try, but not entirely correct. If the baseMap key equality is not identity, this might change the identity of the the keys in the map. Also, it may change the order of the keys if the map is a linked hash map. I prefer the previous version with a "must use operator==" restriction. How about this: Set<V> valuesToRetain = new Set<V>.identity(); for (var element in elements) { if (element != null && element is! V) continue; var key = _keyForValue(element); if (!_baseMap.containsKey(key)) continue; valuesToRetain.add(_baseMap[key]); } List keysToRemove = []; _baseMap.forEach((k, v) { if (!valuesToRetain.contains(v)) keysToRemove.add(k); }); keysToRemove.forEach(_baseMap.remove); ? Basically it's a slow way to do lookup(key). So slow I wouldn't recommend it for the lookup method (linear lookup isn't nice). I still think you should have an isValidKey function, and not use "is! V" hardcoded.
https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:394: where((element) => !other.contains(element)).toSet(); On 2014/05/21 05:57:44, Lasse Reichstein Nielsen wrote: > 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. 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. https://codereview.chromium.org/277563007/diff/60001/pkg/collection/lib/wrapp... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/60001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:549: _baseMap[pair.first] = pair.last; On 2014/05/21 05:57:44, Lasse Reichstein Nielsen wrote: > Nice try, but not entirely correct. If the baseMap key equality is not identity, > this might change the identity of the the keys in the map. > Also, it may change the order of the keys if the map is a linked hash map. > I prefer the previous version with a "must use operator==" restriction. > > How about this: > > Set<V> valuesToRetain = new Set<V>.identity(); > for (var element in elements) { > if (element != null && element is! V) continue; > var key = _keyForValue(element); > if (!_baseMap.containsKey(key)) continue; > valuesToRetain.add(_baseMap[key]); > } > List keysToRemove = []; > _baseMap.forEach((k, v) { > if (!valuesToRetain.contains(v)) keysToRemove.add(k); > }); > keysToRemove.forEach(_baseMap.remove); > > > ? > > Basically it's a slow way to do lookup(key). So slow I wouldn't recommend it for > the lookup method (linear lookup isn't nice). Done. I suppose it's reasonable to assume that the map's notion of equality will be reflexive. > I still think you should have an isValidKey function, and not use "is! V" > hardcoded. We'd still have to hard-code "is! V"; isValidKey would just be called in addition to that. For example, [_baseMap.contains] takes a V, so we'd still need to guarantee that the argument is a V even if isValidKey is called as well. I'm happy to add that functionality, but I'd like to do it in a separate CL so I can get this one committed.
https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/40001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:394: where((element) => !other.contains(element)).toSet(); 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 :( https://codereview.chromium.org/277563007/diff/60001/pkg/collection/lib/wrapp... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/60001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:549: _baseMap[pair.first] = pair.last; It's not so much being reflexive (but yes, we can assume that, or lookup wouldn't work :), but this particular map being guaranteed to be a bijection. No two keys can have the same value, so we can use values to identify the keys. I don't dare expect that keyForValue returns identical objects for identical values, so getting the key by keyForValue(_baseMap[element]) wouldn't be enough. I believe Map.containsKey and Map.containsValue both take Object as argument. I think the only place where the check is needed is for the argument to keyForValue.
https://codereview.chromium.org/277563007/diff/60001/pkg/collection/lib/wrapp... File pkg/collection/lib/wrappers.dart (right): https://codereview.chromium.org/277563007/diff/60001/pkg/collection/lib/wrapp... pkg/collection/lib/wrappers.dart:549: _baseMap[pair.first] = pair.last; On 2014/05/21 19:01:06, Lasse Reichstein Nielsen wrote: > It's not so much being reflexive (but yes, we can assume that, or lookup > wouldn't work :), but this particular map being guaranteed to be a bijection. No > two keys can have the same value, so we can use values to identify the keys. > > I don't dare expect that keyForValue returns identical objects for identical > values, so getting the key by keyForValue(_baseMap[element]) wouldn't be enough. Is the current implementation acceptable, though? > I believe Map.containsKey and Map.containsValue both take Object as argument. I > think the only place where the check is needed is for the argument to > keyForValue. Good point. Still, I think users would expect isValidValue to be typed as "bool isValidValue(V value)".
Yes, lgtm!
Message was sent while issue was closed.
Committed patchset #5 manually as r36447 (presubmit successful).
Message was sent while issue was closed.
Now I finally got my head wrapped around the MapValueSet.
Sleeping on it might be the thing :)
It's really equivalent to:
new Set(equals: (a, b) =>
equals(keyFromValue(a), keyFromValue(b)),
hashCode: (a) => hashCode(keyFromValue(a)))
where equals and hashCode form the equality of the underlying map (well, if it
is hash based).
The only difference is that the MapValueSet caches the results of keyFromValue
and builds the inverse mapping in a map.
I've kept thinking that you put in a pre-filled map as base map, but if you use
an empty map, it is really just representing the equality on the keys.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
