Add 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
Review URL: https://codereview.chromium.org//277563007
git-svn-id: https://dart.googlecode.com/svn/branches/bleeding_edge/dart/pkg/collection@36447 260f80e4-7a28-3924-810f-c04153c831b5
diff --git a/CHANGELOG.md b/CHANGELOG.md
new file mode 100644
index 0000000..e5a6381
--- /dev/null
+++ b/CHANGELOG.md
@@ -0,0 +1,7 @@
+## 0.9.3
+
+* Add a `MapKeySet` class that exposes an unmodifiable `Set` view of a `Map`'s
+ keys.
+
+* Add a `MapValueSet` class that takes a function from values to keys and uses
+ it to expose a `Set` view of a `Map`'s values.
diff --git a/lib/wrappers.dart b/lib/wrappers.dart
index 0fcc8c2..c9e919d 100644
--- a/lib/wrappers.dart
+++ b/lib/wrappers.dart
@@ -19,19 +19,15 @@
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);
@@ -93,6 +89,22 @@
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.
@@ -337,3 +349,219 @@
String toString() => _base.toString();
}
+
+/**
+ * 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.
+ *
+ * Note that [lookup] is not supported for this set.
+ */
+class MapKeySet<E> extends _DelegatingIterableBase<E>
+ with UnmodifiableSetMixin<E> {
+ final Map<E, dynamic> _baseMap;
+
+ MapKeySet(Map<E, dynamic> base) : _baseMap = base;
+
+ Iterable<E> get _base => _baseMap.keys;
+
+ bool contains(Object element) => _baseMap.containsKey(element);
+
+ bool get isEmpty => _baseMap.isEmpty;
+
+ bool get isNotEmpty => _baseMap.isNotEmpty;
+
+ int get length => _baseMap.length;
+
+ String toString() => "{${_base.join(', ')}}";
+
+ bool containsAll(Iterable<Object> other) => other.every(contains);
+
+ /**
+ * Returns a new set with the the elements of [this] that are not in [other].
+ *
+ * That is, the returned set contains all the elements of this [Set] that are
+ * not elements of [other] according to `other.contains`.
+ *
+ * Note that the returned set will use the default equality operation, which
+ * may be different than the equality operation [this] uses.
+ */
+ Set<E> difference(Set<E> other) =>
+ where((element) => !other.contains(element)).toSet();
+
+ /**
+ * Returns a new set which is the intersection between [this] and [other].
+ *
+ * That is, the returned set contains all the elements of this [Set] that are
+ * also elements of [other] according to `other.contains`.
+ *
+ * Note that the returned set will use the default equality operation, which
+ * may be different than the equality operation [this] uses.
+ */
+ Set<E> intersection(Set<Object> other) => where(other.contains).toSet();
+
+ /**
+ * Throws an [UnsupportedError] since there's no corresponding method for
+ * [Map]s.
+ */
+ E lookup(E element) => throw new UnsupportedError(
+ "MapKeySet doesn't support lookup().");
+
+ /**
+ * Returns a new set which contains all the elements of [this] and [other].
+ *
+ * That is, the returned set contains all the elements of this [Set] and all
+ * the elements of [other].
+ *
+ * Note that the returned set will use the default equality operation, which
+ * may be different than the equality operation [this] uses.
+ */
+ Set<E> union(Set<E> other) => toSet()..addAll(other);
+}
+
+/**
+ * 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.
+ */
+class MapValueSet<K, V> extends _DelegatingIterableBase<V> implements Set<V> {
+ final Map<K, V> _baseMap;
+ final Function _keyForValue;
+
+ /**
+ * 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;
+
+ Iterable<V> get _base => _baseMap.values;
+
+ bool contains(Object element) {
+ if (element != null && 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) {
+ K key = _keyForValue(value);
+ bool result = false;
+ _baseMap.putIfAbsent(key, () {
+ result = true;
+ return value;
+ });
+ return result;
+ }
+
+ void addAll(Iterable<V> elements) => elements.forEach(add);
+
+ void clear() => _baseMap.clear();
+
+ bool containsAll(Iterable<Object> other) => other.every(contains);
+
+ /**
+ * Returns a new set with the the elements of [this] that are not in [other].
+ *
+ * That is, the returned set contains all the elements of this [Set] that are
+ * not elements of [other] according to `other.contains`.
+ *
+ * Note that the returned set will use the default equality operation, which
+ * may be different than the equality operation [this] uses.
+ */
+ Set<V> difference(Set<V> other) =>
+ where((element) => !other.contains(element)).toSet();
+
+ /**
+ * Returns a new set which is the intersection between [this] and [other].
+ *
+ * That is, the returned set contains all the elements of this [Set] that are
+ * also elements of [other] according to `other.contains`.
+ *
+ * Note that the returned set will use the default equality operation, which
+ * may be different than the equality operation [this] uses.
+ */
+ Set<V> intersection(Set<Object> other) => where(other.contains).toSet();
+
+ V lookup(V element) => _baseMap[_keyForValue(element)];
+
+ bool remove(Object value) {
+ if (value != null && value is! V) return false;
+ var key = _keyForValue(value);
+ if (!_baseMap.containsKey(key)) return false;
+ _baseMap.remove(key);
+ return true;
+ }
+
+ void removeAll(Iterable<Object> elements) => elements.forEach(remove);
+
+ void removeWhere(bool test(V element)) {
+ var toRemove = [];
+ _baseMap.forEach((key, value) {
+ if (test(value)) toRemove.add(key);
+ });
+ toRemove.forEach(_baseMap.remove);
+ }
+
+ void retainAll(Iterable<Object> elements) {
+ var 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]);
+ }
+
+ var keysToRemove = [];
+ _baseMap.forEach((k, v) {
+ if (!valuesToRetain.contains(v)) keysToRemove.add(k);
+ });
+ keysToRemove.forEach(_baseMap.remove);
+ }
+
+ void retainWhere(bool test(V element)) =>
+ removeWhere((element) => !test(element));
+
+ /**
+ * Returns a new set which contains all the elements of [this] and [other].
+ *
+ * That is, the returned set contains all the elements of this [Set] and all
+ * the elements of [other].
+ *
+ * Note that the returned set will use the default equality operation, which
+ * may be different than the equality operation [this] uses.
+ */
+ Set<V> union(Set<V> other) => toSet()..addAll(other);
+}
diff --git a/pubspec.yaml b/pubspec.yaml
index 58482ce..45cf9b7 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,5 +1,5 @@
name: collection
-version: 0.9.2
+version: 0.9.3-dev
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/wrapper_test.dart b/test/wrapper_test.dart
index 86a0ddd..5858aaf 100644
--- a/test/wrapper_test.dart
+++ b/test/wrapper_test.dart
@@ -265,6 +265,178 @@
expect.toString().equals.toString();
}
+ // Runs tests of Set behavior.
+ //
+ // [setUpSet] should return a set with two elements: "foo" and "bar".
+ void testTwoElementSet(Set<String> setUpSet()) {
+ group("with two elements", () {
+ var set;
+ setUp(() => set = setUpSet());
+
+ test(".any", () {
+ expect(set.any((element) => element == "foo"), isTrue);
+ expect(set.any((element) => element == "baz"), isFalse);
+ });
+
+ test(".elementAt", () {
+ expect(set.elementAt(0), equals("foo"));
+ expect(set.elementAt(1), equals("bar"));
+ expect(() => set.elementAt(2), throwsRangeError);
+ });
+
+ test(".every", () {
+ expect(set.every((element) => element == "foo"), isFalse);
+ expect(set.every((element) => element is String), isTrue);
+ });
+
+ test(".expand", () {
+ expect(set.expand((element) {
+ return [element.substring(0, 1), element.substring(1)];
+ }), equals(["f", "oo", "b", "ar"]));
+ });
+
+ test(".first", () {
+ expect(set.first, equals("foo"));
+ });
+
+ test(".firstWhere", () {
+ expect(set.firstWhere((element) => element is String), equals("foo"));
+ expect(set.firstWhere((element) => element.startsWith("b")),
+ equals("bar"));
+ expect(() => set.firstWhere((element) => element is int),
+ throwsStateError);
+ expect(set.firstWhere((element) => element is int, orElse: () => "baz"),
+ equals("baz"));
+ });
+
+ test(".fold", () {
+ expect(set.fold("start", (previous, element) => previous + element),
+ equals("startfoobar"));
+ });
+
+ test(".forEach", () {
+ var values = [];
+ set.forEach(values.add);
+ expect(values, equals(["foo", "bar"]));
+ });
+
+ test(".iterator", () {
+ var values = [];
+ for (var element in set) {
+ values.add(element);
+ }
+ expect(values, equals(["foo", "bar"]));
+ });
+
+ test(".join", () {
+ expect(set.join(", "), equals("foo, bar"));
+ });
+
+ test(".last", () {
+ expect(set.last, equals("bar"));
+ });
+
+ test(".lastWhere", () {
+ expect(set.lastWhere((element) => element is String), equals("bar"));
+ expect(set.lastWhere((element) => element.startsWith("f")),
+ equals("foo"));
+ expect(() => set.lastWhere((element) => element is int),
+ throwsStateError);
+ expect(set.lastWhere((element) => element is int, orElse: () => "baz"),
+ equals("baz"));
+ });
+
+ test(".map", () {
+ expect(set.map((element) => element.substring(1)),
+ equals(["oo", "ar"]));
+ });
+
+ test(".reduce", () {
+ expect(set.reduce((previous, element) => previous + element),
+ equals("foobar"));
+ });
+
+ test(".singleWhere", () {
+ expect(() => set.singleWhere((element) => element == "baz"),
+ throwsStateError);
+ expect(set.singleWhere((element) => element == "foo"),
+ "foo");
+ expect(() => set.singleWhere((element) => element is String),
+ throwsStateError);
+ });
+
+ test(".skip", () {
+ expect(set.skip(0), equals(["foo", "bar"]));
+ expect(set.skip(1), equals(["bar"]));
+ expect(set.skip(2), equals([]));
+ });
+
+ test(".skipWhile", () {
+ expect(set.skipWhile((element) => element.startsWith("f")),
+ equals(["bar"]));
+ expect(set.skipWhile((element) => element.startsWith("z")),
+ equals(["foo", "bar"]));
+ expect(set.skipWhile((element) => element is String),
+ equals([]));
+ });
+
+ test(".take", () {
+ expect(set.take(0), equals([]));
+ expect(set.take(1), equals(["foo"]));
+ expect(set.take(2), equals(["foo", "bar"]));
+ });
+
+ test(".takeWhile", () {
+ expect(set.takeWhile((element) => element.startsWith("f")),
+ equals(["foo"]));
+ expect(set.takeWhile((element) => element.startsWith("z")),
+ equals([]));
+ expect(set.takeWhile((element) => element is String),
+ equals(["foo", "bar"]));
+ });
+
+ test(".toList", () {
+ expect(set.toList(), equals(["foo", "bar"]));
+ expect(() => set.toList(growable: false).add("baz"),
+ throwsUnsupportedError);
+ expect(set.toList()..add("baz"), equals(["foo", "bar", "baz"]));
+ });
+
+ test(".toSet", () {
+ expect(set.toSet(), equals(new Set.from(["foo", "bar"])));
+ });
+
+ test(".where", () {
+ expect(set.where((element) => element.startsWith("f")),
+ equals(["foo"]));
+ expect(set.where((element) => element.startsWith("z")), equals([]));
+ expect(set.where((element) => element is String),
+ equals(["foo", "bar"]));
+ });
+
+ test(".containsAll", () {
+ expect(set.containsAll(["foo", "bar"]), isTrue);
+ expect(set.containsAll(["foo"]), isTrue);
+ expect(set.containsAll(["foo", "bar", "qux"]), isFalse);
+ });
+
+ test(".difference", () {
+ expect(set.difference(new Set.from(["foo", "baz"])),
+ equals(new Set.from(["bar"])));
+ });
+
+ test(".intersection", () {
+ expect(set.intersection(new Set.from(["foo", "baz"])),
+ equals(new Set.from(["foo"])));
+ });
+
+ test(".union", () {
+ expect(set.union(new Set.from(["foo", "baz"])),
+ equals(new Set.from(["foo", "bar", "baz"])));
+ });
+ });
+ }
+
test("Iterable", () {
testIterable(new IterableExpector());
});
@@ -284,4 +456,209 @@
test("Map", () {
testMap(new MapExpector());
});
+
+ group("MapKeySet", () {
+ var map;
+ var set;
+
+ setUp(() {
+ map = new Map<String, int>();
+ set = new MapKeySet<String>(map);
+ });
+
+ testTwoElementSet(() {
+ map["foo"] = 1;
+ map["bar"] = 2;
+ return set;
+ });
+
+ test(".single", () {
+ expect(() => set.single, throwsStateError);
+ map["foo"] = 1;
+ expect(set.single, equals("foo"));
+ map["bar"] = 1;
+ expect(() => set.single, throwsStateError);
+ });
+
+ test(".toString", () {
+ expect(set.toString(), equals("{}"));
+ map["foo"] = 1;
+ map["bar"] = 2;
+ expect(set.toString(), equals("{foo, bar}"));
+ });
+
+ test(".contains", () {
+ expect(set.contains("foo"), isFalse);
+ map["foo"] = 1;
+ expect(set.contains("foo"), isTrue);
+ });
+
+ test(".isEmpty", () {
+ expect(set.isEmpty, isTrue);
+ map["foo"] = 1;
+ expect(set.isEmpty, isFalse);
+ });
+
+ test(".isNotEmpty", () {
+ expect(set.isNotEmpty, isFalse);
+ map["foo"] = 1;
+ expect(set.isNotEmpty, isTrue);
+ });
+
+ test(".length", () {
+ expect(set, hasLength(0));
+ map["foo"] = 1;
+ expect(set, hasLength(1));
+ map["bar"] = 2;
+ expect(set, hasLength(2));
+ });
+
+ test("is unmodifiable", () {
+ expect(() => set.add("baz"), throwsUnsupportedError);
+ expect(() => set.addAll(["baz", "bang"]), throwsUnsupportedError);
+ expect(() => set.remove("foo"), throwsUnsupportedError);
+ expect(() => set.removeAll(["baz", "bang"]), throwsUnsupportedError);
+ expect(() => set.retainAll(["foo"]), throwsUnsupportedError);
+ expect(() => set.removeWhere((_) => true), throwsUnsupportedError);
+ expect(() => set.retainWhere((_) => true), throwsUnsupportedError);
+ expect(() => set.clear(), throwsUnsupportedError);
+ });
+ });
+
+ group("MapValueSet", () {
+ var map;
+ var set;
+
+ setUp(() {
+ map = new Map<String, String>();
+ set = new MapValueSet<String, String>(map,
+ (string) => string.substring(0, 1));
+ });
+
+ testTwoElementSet(() {
+ map["f"] = "foo";
+ map["b"] = "bar";
+ return set;
+ });
+
+ test(".single", () {
+ expect(() => set.single, throwsStateError);
+ map["f"] = "foo";
+ expect(set.single, equals("foo"));
+ map["b"] = "bar";
+ expect(() => set.single, throwsStateError);
+ });
+
+ test(".toString", () {
+ expect(set.toString(), equals("{}"));
+ map["f"] = "foo";
+ map["b"] = "bar";
+ expect(set.toString(), equals("{foo, bar}"));
+ });
+
+ test(".contains", () {
+ expect(set.contains("foo"), isFalse);
+ map["f"] = "foo";
+ expect(set.contains("foo"), isTrue);
+ expect(set.contains("fblthp"), isTrue);
+ });
+
+ test(".isEmpty", () {
+ expect(set.isEmpty, isTrue);
+ map["f"] = "foo";
+ expect(set.isEmpty, isFalse);
+ });
+
+ test(".isNotEmpty", () {
+ expect(set.isNotEmpty, isFalse);
+ map["f"] = "foo";
+ expect(set.isNotEmpty, isTrue);
+ });
+
+ test(".length", () {
+ expect(set, hasLength(0));
+ map["f"] = "foo";
+ expect(set, hasLength(1));
+ map["b"] = "bar";
+ expect(set, hasLength(2));
+ });
+
+ test(".lookup", () {
+ map["f"] = "foo";
+ expect(set.lookup("fblthp"), equals("foo"));
+ expect(set.lookup("bar"), isNull);
+ });
+
+ test(".add", () {
+ set.add("foo");
+ set.add("bar");
+ expect(map, equals({"f": "foo", "b": "bar"}));
+ });
+
+ test(".addAll", () {
+ set.addAll(["foo", "bar"]);
+ expect(map, equals({"f": "foo", "b": "bar"}));
+ });
+
+ test(".clear", () {
+ map["f"] = "foo";
+ map["b"] = "bar";
+ set.clear();
+ expect(map, isEmpty);
+ });
+
+ test(".remove", () {
+ map["f"] = "foo";
+ map["b"] = "bar";
+ set.remove("fblthp");
+ expect(map, equals({"b": "bar"}));
+ });
+
+ test(".removeAll", () {
+ map["f"] = "foo";
+ map["b"] = "bar";
+ map["q"] = "qux";
+ set.removeAll(["fblthp", "qux"]);
+ expect(map, equals({"b": "bar"}));
+ });
+
+ test(".removeWhere", () {
+ map["f"] = "foo";
+ map["b"] = "bar";
+ map["q"] = "qoo";
+ set.removeWhere((element) => element.endsWith("o"));
+ expect(map, equals({"b": "bar"}));
+ });
+
+ test(".retainAll", () {
+ map["f"] = "foo";
+ map["b"] = "bar";
+ map["q"] = "qux";
+ set.retainAll(["fblthp", "qux"]);
+ expect(map, equals({"f": "foo", "q": "qux"}));
+ });
+
+ test(".retainAll respects an unusual notion of equality", () {
+ map = new HashMap<String, String>(
+ equals: (value1, value2) =>
+ value1.toLowerCase() == value2.toLowerCase(),
+ hashCode: (value) => value.toLowerCase().hashCode);
+ set = new MapValueSet<String, String>(map,
+ (string) => string.substring(0, 1));
+
+ map["f"] = "foo";
+ map["B"] = "bar";
+ map["Q"] = "qux";
+ set.retainAll(["fblthp", "qux"]);
+ expect(map, equals({"f": "foo", "Q": "qux"}));
+ });
+
+ test(".retainWhere", () {
+ map["f"] = "foo";
+ map["b"] = "bar";
+ map["q"] = "qoo";
+ set.retainWhere((element) => element.endsWith("o"));
+ expect(map, equals({"f": "foo", "q": "qoo"}));
+ });
+ });
}
