Add a CanonicalizedMap class to pkg/collection.

Add a CanonicalizedMap class to pkg/collection.

BUG=18708
R=lrn@google.com

Committed: https://code.google.com/p/dart/source/detail?r=37908

[Lasse Reichstein Nielsen, 2014-06-27 06:57:47]

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/collectio...
File pkg/collection/lib/collection.dart (right):

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/collectio...
pkg/collection/lib/collection.dart:24: export "src/canonicalized_map.dart";
This makes CanonicalizedMap *only* available by importing package:collection.
The other libraries can be imported individually as well (it's deliberate that
they are not in the src directory).

Either move canonicalized_map to lib/ or just make it part of wrappers.dart (I
think I prefer the latter, just make it a part instead of a library, and part it
from wrappers.dart)

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
File pkg/collection/lib/src/canonicalized_map.dart (right):

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
pkg/collection/lib/src/canonicalized_map.dart:16: class CanonicalizedMap<K, V>
extends DelegatingMap<K, V> {
Could we allow the canonicalization of a key to not have the same type as the
key?

That would make it 
  class CanonicalizedMap<C,K,V> 
and 
  CanonicalizedMap(C canonicalize(K key))
etc.

That would allow:
  canonicalize(LargeRecord r) => r.id
to work.

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
pkg/collection/lib/src/canonicalized_map.dart:22: final _keys = new Map<K, V>();
Should  be <K,K>.

Have you considered using a 
  Map<K, _MapEntry<K, V>> 
instead of having two maps?
(with  
  class _MapEntry<K, V> {
   K key;
   V value;
  }
  static getKey(_MapEntry e) => e.key;
  static getValue(_MapEntry e) => e.value;
  static _MapEntry create() => new _MapEntry();
)

Then you can do: 
  
  get values => super.values.map(_MapEntry.getValue);  
  get keys  => super.values.map(_MapEntry.getKey);
  add(K key, V value) {
    var entry = super.putIfAbsent(_canonicalize(key),
                                  _MapEntry.create);
    bool added = (entry.key == null);
    entry.key = key;
    entry.value = value;
    return added;
  }

etc.

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
pkg/collection/lib/src/canonicalized_map.dart:28: * key. Keys with the same
canonical value are considered identical, and the
identical -> equivalent

Ditto below.

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
pkg/collection/lib/src/canonicalized_map.dart:29: * canonical values of the keys
are stored in the map.
"stored in the map" is vague but sounds significant.
Maybe just "are cached".

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
pkg/collection/lib/src/canonicalized_map.dart:31: CanonicalizedMap(K
canonicalize(K key))
I'd also like to have an "bool isValidKey(Object o)" parameter, which can
default to "(x) => x is K" if omitted, instead of having "is!K" everywhere. That
way you can restrict the keys that you apply _canonicalize to to the ones where
it works, even if they are not all of K.

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
pkg/collection/lib/src/canonicalized_map.dart:31: CanonicalizedMap(K
canonicalize(K key))
Please see if you can also make the map a parameter:

  CanonicalizedMap(K canonicalize(K key), [Map<K, V> map]) :
    : _canonicalize = canonicalize,
      super((map == null) ? {} : map);

That allows you to not always use a LinkedHashMap, and it gives you a place to
document that (if you don't provide one) the default is a LinkedHashMap.

This does collide with needing another Map for the keys, so you need another Map
with the same key equality. 
If you switch to "Map<C, _MapEntry<K,V>>" then you can at least ask for a single
Map<C, Object> as configurable parameter.

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
pkg/collection/lib/src/canonicalized_map.dart:36: * Creates a canonicalized map
that contains all key/value pairs of [other].
Because of the canonicalization, it might contain be all the keys.
Just say "... that is initialized with the key/value paris of [other]".

[nweiz, 2014-06-30 20:37:47]

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/collectio...
File pkg/collection/lib/collection.dart (right):

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/collectio...
pkg/collection/lib/collection.dart:24: export "src/canonicalized_map.dart";
On 2014/06/27 06:57:47, Lasse Reichstein Nielsen wrote:
> This makes CanonicalizedMap *only* available by importing package:collection.
> The other libraries can be imported individually as well (it's deliberate that
> they are not in the src directory).

This is contrary to the standard package layout; I had assumed the current
layout of this package was a holdover from before the standards were solidified.

Since we have show/hide, there's not really much utility in having a large
number of top-level libraries except when those libraries use incompatible core
libraries (e.g. dart:io vs dart:html) or when those libraries are intended to be
imported with different prefixes (e.g. json_rpc_2's error_codes library).

> Either move canonicalized_map to lib/ or just make it part of wrappers.dart (I
> think I prefer the latter, just make it a part instead of a library, and part
it
> from wrappers.dart)

I can do this if you want, but please consider moving this package towards the
standard layout. The less idiosyncratic it is the easier it will be for users to
understand it.

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
File pkg/collection/lib/src/canonicalized_map.dart (right):

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
pkg/collection/lib/src/canonicalized_map.dart:16: class CanonicalizedMap<K, V>
extends DelegatingMap<K, V> {
On 2014/06/27 06:57:47, Lasse Reichstein Nielsen wrote:
> Could we allow the canonicalization of a key to not have the same type as the
> key?
> 
> That would make it 
>   class CanonicalizedMap<C,K,V> 
> and 
>   CanonicalizedMap(C canonicalize(K key))
> etc.
> 
> That would allow:
>   canonicalize(LargeRecord r) => r.id
> to work.

Done.

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
pkg/collection/lib/src/canonicalized_map.dart:22: final _keys = new Map<K, V>();
On 2014/06/27 06:57:47, Lasse Reichstein Nielsen wrote:
> Should  be <K,K>.
> 
> Have you considered using a 
>   Map<K, _MapEntry<K, V>> 
> instead of having two maps?
> (with  
>   class _MapEntry<K, V> {
>    K key;
>    V value;
>   }
>   static getKey(_MapEntry e) => e.key;
>   static getValue(_MapEntry e) => e.value;
>   static _MapEntry create() => new _MapEntry();
> )
> 
> Then you can do: 
>   
>   get values => super.values.map(_MapEntry.getValue);  
>   get keys  => super.values.map(_MapEntry.getKey);
>   add(K key, V value) {
>     var entry = super.putIfAbsent(_canonicalize(key),
>                                   _MapEntry.create);
>     bool added = (entry.key == null);
>     entry.key = key;
>     entry.value = value;
>     return added;
>   }
> 
> etc.

Done, using the Pair class that's used elsewhere in Dart team packages.

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
pkg/collection/lib/src/canonicalized_map.dart:28: * key. Keys with the same
canonical value are considered identical, and the
On 2014/06/27 06:57:47, Lasse Reichstein Nielsen wrote:
> identical -> equivalent
> 
> Ditto below.

Done.

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
pkg/collection/lib/src/canonicalized_map.dart:29: * canonical values of the keys
are stored in the map.
On 2014/06/27 06:57:47, Lasse Reichstein Nielsen wrote:
> "stored in the map" is vague but sounds significant.
> Maybe just "are cached".

I just removed this. It was a holdover from before I tracked the original key
value and now I think it adds more confusion that it removes.

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
pkg/collection/lib/src/canonicalized_map.dart:31: CanonicalizedMap(K
canonicalize(K key))
On 2014/06/27 06:57:47, Lasse Reichstein Nielsen wrote:
> I'd also like to have an "bool isValidKey(Object o)" parameter, which can
> default to "(x) => x is K" if omitted, instead of having "is!K" everywhere.
That
> way you can restrict the keys that you apply _canonicalize to to the ones
where
> it works, even if they are not all of K.

I don't completely understand the purpose of this function. What happens if I
write "map[key] = value" for a key that's considered invalid? Doing nothing
seems like it violates the contract of a Map. Maybe it should throw an error,
but it seems like [canonicalize] is better equipped to throw a useful error
there.

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
pkg/collection/lib/src/canonicalized_map.dart:31: CanonicalizedMap(K
canonicalize(K key))
On 2014/06/27 06:57:47, Lasse Reichstein Nielsen wrote:
> Please see if you can also make the map a parameter:
> 
>   CanonicalizedMap(K canonicalize(K key), [Map<K, V> map]) :
>     : _canonicalize = canonicalize,
>       super((map == null) ? {} : map);
> 
> That allows you to not always use a LinkedHashMap, and it gives you a place to
> document that (if you don't provide one) the default is a LinkedHashMap.
> 
> This does collide with needing another Map for the keys, so you need another
Map
> with the same key equality. 
> If you switch to "Map<C, _MapEntry<K,V>>" then you can at least ask for a
single
> Map<C, Object> as configurable parameter.

I don't think it's worth complicating the API to support an internal map with
custom equality, especially if that involves having confusing type parameter
restrictions on the map that's passed in. The point of using a canonicalized map
in the first place is that the existing means of customizing equality don't fit
the user's needs, but canonicalization does. If users have a strong need for
both types, they can also get it by using a custom type for C with equality
defined however they want.

I also don't think the theoretical constant-time gains for using a different Map
implementation than LinkedHashMap are worth the complication.

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
pkg/collection/lib/src/canonicalized_map.dart:36: * Creates a canonicalized map
that contains all key/value pairs of [other].
On 2014/06/27 06:57:47, Lasse Reichstein Nielsen wrote:
> Because of the canonicalization, it might contain be all the keys.
> Just say "... that is initialized with the key/value paris of [other]".

Good point. Done.

[Lasse Reichstein Nielsen, 2014-07-01 09:18:15]

LGTM if you export it from wrapper.dart instead of collection.dart.

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/collectio...
File pkg/collection/lib/collection.dart (right):

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/collectio...
pkg/collection/lib/collection.dart:24: export "src/canonicalized_map.dart";
I don't see where the standard layout
(https://www.dartlang.org/tools/pub/package-layout.html#public-libraries)
restricts the public libraries only to those that are incompatible in some way.
I thought it was a completely valid choice to have a package containing several
individual libraries.

The individual libraries in package:collection can be quite large (even if not
all are), so we wanted to be able to import only the type of functionality that
was needed - it's not viable to "show", e.g., everything currently in
equality.dart

So, unless there is a general agreement that having separate top-level libraries
grouped by subject, not by requirements, is deprecated, I think I'll prefer to
keep it that way.

I still think I'd want canonicalized-map to be in the wrappers library, so you
can keep it in source and export it from wrappers instead (or make it a part
instead of a library).

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
File pkg/collection/lib/src/canonicalized_map.dart (right):

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
pkg/collection/lib/src/canonicalized_map.dart:31: CanonicalizedMap(K
canonicalize(K key))
ACK, if we make the type of canonical object C instead of K, I'm fine with
requiring C to have a functional operator==.

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
pkg/collection/lib/src/canonicalized_map.dart:31: CanonicalizedMap(K
canonicalize(K key))
I assume that if isValidKey(o) return false, then canonicalize(o) would throw. 

The isValidKey is a way to allow a canonicalize function that doesn't work on
all objects of type K, so that the non-inserting operations (remove,
containsKey, []) will still work.
Just checking "is K" won't be enough in that case.

It's what I have done for Equality and SplayTreeMap/Set, allowing you to have a
compare function for SplayTrees that doesn't work on all elements of the key
type (e.g., num keys but doesn't work on NaN).

If the canonicalize function works on all K objects, having a default of ((x)=>x
is K) is fine, and you can just omit passing it as a parameter. Or if you don't
expect the map to be used by anyone with invalid arguments to
remove/containsKey/[], you can also just ignore it.

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/lib/src/c...
File pkg/collection/lib/src/canonicalized_map.dart (right):

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/lib/src/c...
pkg/collection/lib/src/canonicalized_map.dart:14: * only canonicalizes each
once, rather than doing so for each comparison.
each once -> each key once

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/lib/src/c...
pkg/collection/lib/src/canonicalized_map.dart:15: */
Document whether the Map allows null as a key (afaics it does).

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/lib/src/c...
pkg/collection/lib/src/canonicalized_map.dart:56: void clear() => _base.clear();
I'd prefer "{...}" to "=>" for a void function.

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/lib/src/c...
pkg/collection/lib/src/canonicalized_map.dart:93: "}";
Just use:
   String toString() => Maps.mapToString(this);
from dart:collection. It also handles cyclic structures.

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/lib/src/u...
File pkg/collection/lib/src/utils.dart (right):

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/lib/src/u...
pkg/collection/lib/src/utils.dart:21: int get hashCode => first.hashCode ^
last.hashCode;
I'd prefer some less symmetric operation, like
  => (first.hashCode * 37 + last.hashCode) & 0x3fffffff;

The plain xor gives zero if first and last are the same value, which is too
likely a case in general.
(We don't use the hashCode for anything, right? Would it be safe to remove
toString, == and hashCode until we actually need it? I'm thinking it's methods
that dart2js would not be able to tree-shake in general, so the extra code could
be (slightly) harmful).

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/test/cano...
File pkg/collection/test/canonicalized_map_test.dart (right):

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/test/cano...
pkg/collection/test/canonicalized_map_test.dart:12: map = new
CanonicalizedMap<int, String, String>((key) => int.parse(key));
"(key) => int.parse(key)" could be just "int.parse".

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/test/cano...
pkg/collection/test/canonicalized_map_test.dart:61: equals("value"));
indent to '('?

[nweiz, 2014-07-01 21:21:44]

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/collectio...
File pkg/collection/lib/collection.dart (right):

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/collectio...
pkg/collection/lib/collection.dart:24: export "src/canonicalized_map.dart";
On 2014/07/01 09:18:14, Lasse Reichstein Nielsen wrote:
> I don't see where the standard layout
> (https://www.dartlang.org/tools/pub/package-layout.html#public-libraries)
> restricts the public libraries only to those that are incompatible in some
way.
> I thought it was a completely valid choice to have a package containing
several
> individual libraries.

That page just lists the hard requirements and strong suggestions. This is more
of a community convention that's been adopted by most packages.

> The individual libraries in package:collection can be quite large (even if not
> all are), so we wanted to be able to import only the type of functionality
that
> was needed - it's not viable to "show", e.g., everything currently in
> equality.dart
> 
> So, unless there is a general agreement that having separate top-level
libraries
> grouped by subject, not by requirements, is deprecated, I think I'll prefer to
> keep it that way.
> 
> I still think I'd want canonicalized-map to be in the wrappers library, so you
> can keep it in source and export it from wrappers instead (or make it a part
> instead of a library).

Done.

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
File pkg/collection/lib/src/canonicalized_map.dart (right):

https://codereview.chromium.org/350183010/diff/1/pkg/collection/lib/src/canon...
pkg/collection/lib/src/canonicalized_map.dart:31: CanonicalizedMap(K
canonicalize(K key))
On 2014/07/01 09:18:14, Lasse Reichstein Nielsen wrote:
> I assume that if isValidKey(o) return false, then canonicalize(o) would throw.

> 
> The isValidKey is a way to allow a canonicalize function that doesn't work on
> all objects of type K, so that the non-inserting operations (remove,
> containsKey, []) will still work.
> Just checking "is K" won't be enough in that case.
> 
> It's what I have done for Equality and SplayTreeMap/Set, allowing you to have
a
> compare function for SplayTrees that doesn't work on all elements of the key
> type (e.g., num keys but doesn't work on NaN).
> 
> If the canonicalize function works on all K objects, having a default of
((x)=>x
> is K) is fine, and you can just omit passing it as a parameter. Or if you
don't
> expect the map to be used by anyone with invalid arguments to
> remove/containsKey/[], you can also just ignore it.

Done.

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/lib/src/c...
File pkg/collection/lib/src/canonicalized_map.dart (right):

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/lib/src/c...
pkg/collection/lib/src/canonicalized_map.dart:14: * only canonicalizes each
once, rather than doing so for each comparison.
On 2014/07/01 09:18:15, Lasse Reichstein Nielsen wrote:
> each once -> each key once

Done.

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/lib/src/c...
pkg/collection/lib/src/canonicalized_map.dart:15: */
On 2014/07/01 09:18:15, Lasse Reichstein Nielsen wrote:
> Document whether the Map allows null as a key (afaics it does).

Done.

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/lib/src/c...
pkg/collection/lib/src/canonicalized_map.dart:56: void clear() => _base.clear();
On 2014/07/01 09:18:15, Lasse Reichstein Nielsen wrote:
> I'd prefer "{...}" to "=>" for a void function.

Done.

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/lib/src/c...
pkg/collection/lib/src/canonicalized_map.dart:93: "}";
On 2014/07/01 09:18:15, Lasse Reichstein Nielsen wrote:
> Just use:
>    String toString() => Maps.mapToString(this);
> from dart:collection. It also handles cyclic structures.

Done.

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/lib/src/u...
File pkg/collection/lib/src/utils.dart (right):

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/lib/src/u...
pkg/collection/lib/src/utils.dart:21: int get hashCode => first.hashCode ^
last.hashCode;
On 2014/07/01 09:18:15, Lasse Reichstein Nielsen wrote:
> I'd prefer some less symmetric operation, like
>   => (first.hashCode * 37 + last.hashCode) & 0x3fffffff;
> 
> The plain xor gives zero if first and last are the same value, which is too
> likely a case in general.
> (We don't use the hashCode for anything, right? Would it be safe to remove
> toString, == and hashCode until we actually need it? I'm thinking it's methods
> that dart2js would not be able to tree-shake in general, so the extra code
could
> be (slightly) harmful).

Removed these.

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/test/cano...
File pkg/collection/test/canonicalized_map_test.dart (right):

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/test/cano...
pkg/collection/test/canonicalized_map_test.dart:12: map = new
CanonicalizedMap<int, String, String>((key) => int.parse(key));
On 2014/07/01 09:18:15, Lasse Reichstein Nielsen wrote:
> "(key) => int.parse(key)" could be just "int.parse".

Done.

https://codereview.chromium.org/350183010/diff/20001/pkg/collection/test/cano...
pkg/collection/test/canonicalized_map_test.dart:61: equals("value"));
On 2014/07/01 09:18:15, Lasse Reichstein Nielsen wrote:
> indent to '('?

Done.

[nweiz, 2014-07-01 21:22:28]

Committed patchset #3 manually as r37908 (presubmit successful).