Add a CanonicalizedMap class to pkg/collection.

pkg/collection/lib/src/canonicalized_map.dart

Index: pkg/collection/lib/src/canonicalized_map.dart
diff --git a/pkg/collection/lib/src/canonicalized_map.dart b/pkg/collection/lib/src/canonicalized_map.dart
new file mode 100644
index 0000000000000000000000000000000000000000..8ec48ed68285498609a9caaf54e17b5afa7db3e4
--- /dev/null
+++ b/pkg/collection/lib/src/canonicalized_map.dart
@@ -0,0 +1,88 @@
+// Copyright (c) 2014, 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 dart.pkg.collection.canonicalized_map;
+
+import '../wrappers.dart';
+
+/**
+ * A map whose keys are converted to canonical values.
+ *
+ * This is useful for using case-insensitive String keys, for example. It's more
+ * efficient than a [LinkedHashMap] with a custom equality operator because it
+ * only canonicalizes each once, rather than doing so for each comparison.
+ */
+class CanonicalizedMap<K, V> extends DelegatingMap<K, V> {

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

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.

[nweiz, 2014/06/30 20:37:46]

Done.

+  final Function _canonicalize;
+
+  /**
+   * A map from the canonicalized keys to their original values.
+   */
+  final _keys = new Map<K, V>();

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

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.

[nweiz, 2014/06/30 20:37:46]

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

+
+  /**
+   * Creates an empty canonicalized map.
+   *
+   * The [canonicalize] function should return the canonical value for the given
+   * key. Keys with the same canonical value are considered identical, and the

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

identical -> equivalent

Ditto below.

[nweiz, 2014/06/30 20:37:46]

Done.

+   * canonical values of the keys are stored in the map.

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

"stored in the map" is vague but sounds significant.
Maybe just "are cached".

[nweiz, 2014/06/30 20:37:46]

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.

+   */
+  CanonicalizedMap(K canonicalize(K key))

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

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.

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

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.

[nweiz, 2014/06/30 20:37:46]

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.

[nweiz, 2014/06/30 20:37:46]

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.

[Lasse Reichstein Nielsen, 2014/07/01 09:18:14]

ACK, if we make the type of canonical object C instead of K, I'm fine with
requiring C to have a functional operator==.

[Lasse Reichstein Nielsen, 2014/07/01 09:18:14]

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.

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

Done.

+      : _canonicalize = canonicalize,
+        super({});
+
+  /**
+   * Creates a canonicalized map that contains all key/value pairs of [other].

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

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:46]

Good point. Done.

+   *
+   * The [canonicalize] function should return the canonical value for the given
+   * key. Keys with the same canonical value are considered identical, and the
+   * canonical values of the keys are stored in the map.
+   */
+  CanonicalizedMap.from(Map<K, V> other, K canonicalize(K key))
+      : _canonicalize = canonicalize,
+        super({}) {
+    addAll(other);
+  }
+
+  V operator [](Object key) {
+    if (key != null && key is! K) return null;
+    return super[_canonicalize(key)];
+  }
+
+  void operator []=(K key, V value) {
+    var canonical = _canonicalize(key);
+    _keys[canonical] = key;
+    super[canonical] = value;
+  }
+
+  void addAll(Map<K, V> other) {
+    other.forEach((key, value) => this[key] = value);
+  }
+
+  bool containsKey(Object key) {
+    if (key != null && key is! K) return null;
+    return super.containsKey(_canonicalize(key));
+  }
+
+  void forEach(void f(K key, V value)) {
+    super.forEach((key, value) => f(_keys[key], value));
+  }
+
+  Iterable<K> get keys => _keys.values;
+
+  V putIfAbsent(K key, V ifAbsent()) {
+    var canonical = _canonicalize(key);
+    return super.putIfAbsent(canonical, () {
+      _keys[canonical] = key;
+      return ifAbsent();
+    });
+  }
+
+  V remove(Object key) {
+    if (key != null && key is! K) return null;
+    var canonical = _canonicalize(key);
+    _keys.remove(canonical);
+    return super.remove(canonical);
+  }
+}