Add a CanonicalizedMap class to pkg/collection.
BUG=18708
R=lrn@google.com
Review URL: https://codereview.chromium.org//350183010
git-svn-id: https://dart.googlecode.com/svn/branches/bleeding_edge/dart/pkg/collection@37908 260f80e4-7a28-3924-810f-c04153c831b5
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 6c1c554..1ed9863 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,8 @@
+## 0.9.4
+
+* Add a `CanonicalizedMap` class that canonicalizes its keys to provide a custom
+ equality relation.
+
## 0.9.3+1
* Fix all analyzer hints.
diff --git a/lib/collection.dart b/lib/collection.dart
index d640071..d24dd39 100644
--- a/lib/collection.dart
+++ b/lib/collection.dart
@@ -21,4 +21,5 @@
export "equality.dart";
export "iterable_zip.dart";
export "priority_queue.dart";
+export "src/canonicalized_map.dart";
export "wrappers.dart";
diff --git a/lib/src/canonicalized_map.dart b/lib/src/canonicalized_map.dart
new file mode 100644
index 0000000..f1cd859
--- /dev/null
+++ b/lib/src/canonicalized_map.dart
@@ -0,0 +1,115 @@
+// 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 'dart:collection';
+
+import 'utils.dart';
+
+/**
+ * A map whose keys are converted to canonical values of type `C`.
+ *
+ * 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 key once, rather than doing so for each comparison.
+ *
+ * By default, `null` is allowed as a key. It can be forbidden via the
+ * `isValidKey` parameter.
+ */
+class CanonicalizedMap<C, K, V> implements Map<K, V> {
+ final Function _canonicalize;
+
+ final Function _isValidKeyFn;
+
+ final _base = new Map<C, Pair<K, V>>();
+
+ /**
+ * 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 equivalent.
+ *
+ * The [isValidKey] function is called before calling [canonicalize] for
+ * methods that take arbitrary objects. It can be used to filter out keys that
+ * can't be canonicalized.
+ */
+ CanonicalizedMap(C canonicalize(K key), {bool isValidKey(K key)})
+ : _canonicalize = canonicalize,
+ _isValidKeyFn = isValidKey;
+
+ /**
+ * Creates a canonicalized map that is initialized with the key/value pairs of
+ * [other].
+ *
+ * The [canonicalize] function should return the canonical value for the given
+ * key. Keys with the same canonical value are considered equivalent.
+ *
+ * The [isValidKey] function is called before calling [canonicalize] for
+ * methods that take arbitrary objects. It can be used to filter out keys that
+ * can't be canonicalized.
+ */
+ CanonicalizedMap.from(Map<K, V> other, C canonicalize(K key),
+ {bool isValidKey(K key)})
+ : _canonicalize = canonicalize,
+ _isValidKeyFn = isValidKey {
+ addAll(other);
+ }
+
+ V operator [](Object key) {
+ if (!_isValidKey(key)) return null;
+ var pair = _base[_canonicalize(key)];
+ return pair == null ? null : pair.last;
+ }
+
+ void operator []=(K key, V value) {
+ _base[_canonicalize(key)] = new Pair(key, value);
+ }
+
+ void addAll(Map<K, V> other) {
+ other.forEach((key, value) => this[key] = value);
+ }
+
+ void clear() {
+ _base.clear();
+ }
+
+ bool containsKey(Object key) {
+ if (!_isValidKey(key)) return false;
+ return _base.containsKey(_canonicalize(key));
+ }
+
+ bool containsValue(Object value) =>
+ _base.values.any((pair) => pair.last == value);
+
+ void forEach(void f(K key, V value)) {
+ _base.forEach((key, pair) => f(pair.first, pair.last));
+ }
+
+ bool get isEmpty => _base.isEmpty;
+
+ bool get isNotEmpty => _base.isNotEmpty;
+
+ Iterable<K> get keys => _base.values.map((pair) => pair.first);
+
+ int get length => _base.length;
+
+ V putIfAbsent(K key, V ifAbsent()) {
+ return _base.putIfAbsent(_canonicalize(key),
+ () => new Pair(key, ifAbsent())).last;
+ }
+
+ V remove(Object key) {
+ if (!_isValidKey(key)) return null;
+ var pair = _base.remove(_canonicalize(key));
+ return pair == null ? null : pair.last;
+ }
+
+ Iterable<V> get values => _base.values.map((pair) => pair.last);
+
+ String toString() => Maps.mapToString(this);
+
+ bool _isValidKey(Object key) => (key == null || key is K) &&
+ (_isValidKeyFn == null || _isValidKeyFn(key));
+}
diff --git a/lib/src/utils.dart b/lib/src/utils.dart
new file mode 100644
index 0000000..c9c7537
--- /dev/null
+++ b/lib/src/utils.dart
@@ -0,0 +1,13 @@
+// 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.utils;
+
+/// A pair of values.
+class Pair<E, F> {
+ E first;
+ F last;
+
+ Pair(this.first, this.last);
+}
diff --git a/lib/wrappers.dart b/lib/wrappers.dart
index 2034174..509a966 100644
--- a/lib/wrappers.dart
+++ b/lib/wrappers.dart
@@ -16,6 +16,7 @@
export "dart:collection" show UnmodifiableListView;
+export "src/canonicalized_map.dart";
part "src/unmodifiable_wrappers.dart";
/**
diff --git a/pubspec.yaml b/pubspec.yaml
index 80b0972..3d48447 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,5 +1,5 @@
name: collection
-version: 0.9.3+1
+version: 0.9.4
author: Dart Team <misc@dartlang.org>
description: Collections and utilities functions and classes related to collections.
homepage: http://www.dartlang.org
diff --git a/test/canonicalized_map_test.dart b/test/canonicalized_map_test.dart
new file mode 100644
index 0000000..1793777
--- /dev/null
+++ b/test/canonicalized_map_test.dart
@@ -0,0 +1,166 @@
+// 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.
+
+import "package:collection/collection.dart";
+import "package:unittest/unittest.dart";
+
+void main() {
+ group("with an empty canonicalized map", () {
+ var map;
+ setUp(() {
+ map = new CanonicalizedMap<int, String, String>(int.parse,
+ isValidKey: new RegExp(r"^\d+$").hasMatch);
+ });
+
+ test("canonicalizes keys on set and get", () {
+ map["1"] = "value";
+ expect(map["01"], equals("value"));
+ });
+
+ test("get returns null for uncanonicalizable key", () {
+ expect(map["foo"], isNull);
+ });
+
+ test("canonicalizes keys for addAll", () {
+ map.addAll({
+ "1": "value 1",
+ "2": "value 2",
+ "3": "value 3"
+ });
+ expect(map["01"], equals("value 1"));
+ expect(map["02"], equals("value 2"));
+ expect(map["03"], equals("value 3"));
+ });
+
+ test("uses the final value for addAll collisions", () {
+ map.addAll({
+ "1": "value 1",
+ "01": "value 2",
+ "001": "value 3"
+ });
+ expect(map.length, equals(1));
+ expect(map["0001"], equals("value 3"));
+ });
+
+ test("clear clears the map", () {
+ map.addAll({
+ "1": "value 1",
+ "2": "value 2",
+ "3": "value 3"
+ });
+ expect(map, isNot(isEmpty));
+ map.clear();
+ expect(map, isEmpty);
+ });
+
+ test("canonicalizes keys for containsKey", () {
+ map["1"] = "value";
+ expect(map.containsKey("01"), isTrue);
+ expect(map.containsKey("2"), isFalse);
+ });
+
+ test("containsKey returns false for uncanonicalizable key", () {
+ expect(map.containsKey("foo"), isFalse);
+ });
+
+ test("canonicalizes keys for putIfAbsent", () {
+ map["1"] = "value";
+ expect(map.putIfAbsent("01", () => throw "shouldn't run"),
+ equals("value"));
+ expect(map.putIfAbsent("2", () => "new value"), equals("new value"));
+ });
+
+ test("canonicalizes keys for remove", () {
+ map["1"] = "value";
+ expect(map.remove("2"), isNull);
+ expect(map.remove("01"), equals("value"));
+ expect(map, isEmpty);
+ });
+
+ test("remove returns null for uncanonicalizable key", () {
+ expect(map.remove("foo"), isNull);
+ });
+
+ test("containsValue returns whether a value is in the map", () {
+ map["1"] = "value";
+ expect(map.containsValue("value"), isTrue);
+ expect(map.containsValue("not value"), isFalse);
+ });
+
+ test("isEmpty returns whether the map is empty", () {
+ expect(map.isEmpty, isTrue);
+ map["1"] = "value";
+ expect(map.isEmpty, isFalse);
+ map.remove("01");
+ expect(map.isEmpty, isTrue);
+ });
+
+ test("isNotEmpty returns whether the map isn't empty", () {
+ expect(map.isNotEmpty, isFalse);
+ map["1"] = "value";
+ expect(map.isNotEmpty, isTrue);
+ map.remove("01");
+ expect(map.isNotEmpty, isFalse);
+ });
+
+ test("length returns the number of pairs in the map", () {
+ expect(map.length, equals(0));
+ map["1"] = "value 1";
+ expect(map.length, equals(1));
+ map["01"] = "value 01";
+ expect(map.length, equals(1));
+ map["02"] = "value 02";
+ expect(map.length, equals(2));
+ });
+
+ test("uses original keys for keys", () {
+ map["001"] = "value 1";
+ map["02"] = "value 2";
+ expect(map.keys, equals(["001", "02"]));
+ });
+
+ test("uses original keys for forEach", () {
+ map["001"] = "value 1";
+ map["02"] = "value 2";
+
+ var keys = [];
+ map.forEach((key, value) => keys.add(key));
+ expect(keys, equals(["001", "02"]));
+ });
+
+ test("values returns all values in the map", () {
+ map.addAll({
+ "1": "value 1",
+ "01": "value 01",
+ "2": "value 2",
+ "03": "value 03"
+ });
+
+ expect(map.values, equals(["value 01", "value 2", "value 03"]));
+ });
+ });
+
+ group("CanonicalizedMap.from", () {
+ test("canonicalizes its keys", () {
+ var map = new CanonicalizedMap.from({
+ "1": "value 1",
+ "2": "value 2",
+ "3": "value 3"
+ }, int.parse);
+ expect(map["01"], equals("value 1"));
+ expect(map["02"], equals("value 2"));
+ expect(map["03"], equals("value 3"));
+ });
+
+ test("uses the final value for collisions", () {
+ var map = new CanonicalizedMap.from({
+ "1": "value 1",
+ "01": "value 2",
+ "001": "value 3"
+ }, int.parse);
+ expect(map.length, equals(1));
+ expect(map["0001"], equals("value 3"));
+ });
+ });
+}
