Add top-level collection-manipulation functions.
These come from various package-specific utility library across the Dart
ecosystem.
R=lrn@google.com
Review URL: https://codereview.chromium.org//1994743003 .
diff --git a/CHANGELOG.md b/CHANGELOG.md
index de42222..90312a3 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,20 @@
+## 1.8.0
+
+* Add a top-level `mapMap()` function that works like `Iterable.map()` on a
+ `Map`.
+
+* Add a top-level `mergeMaps()` function that creates a new map with the
+ combined contents of two existing maps.
+
+* Add a top-level `groupBy()` function that converts an `Iterable` to a `Map` by
+ grouping its elements using a function.
+
+* Add top-level `minBy()` and `maxBy()` functions that return the minimum and
+ maximum values in an `Iterable`, respectively, ordered by a derived value.
+
+* Add a top-level `transitiveClosure()` function that returns the transitive
+ closure of a directed graph.
+
## 1.7.0
* Add a `const UnmodifiableSetView.empty()` constructor.
diff --git a/lib/collection.dart b/lib/collection.dart
index 95b8479..58d98f7 100644
--- a/lib/collection.dart
+++ b/lib/collection.dart
@@ -6,6 +6,7 @@
export "src/canonicalized_map.dart";
export "src/comparators.dart";
export "src/equality.dart";
+export "src/functions.dart";
export "src/iterable_zip.dart";
export "src/priority_queue.dart";
export "src/queue_list.dart";
diff --git a/lib/src/functions.dart b/lib/src/functions.dart
new file mode 100644
index 0000000..7f3ff99
--- /dev/null
+++ b/lib/src/functions.dart
@@ -0,0 +1,139 @@
+// Copyright (c) 2016, 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 'utils.dart';
+
+// TODO(nweiz): When sdk#26488 is fixed, use overloads to ensure that if [key]
+// or [value] isn't passed, `K2`/`V2` defaults to `K1`/`V1`, respectively.
+/// Creates a new map from [map] with new keys and values.
+///
+/// The return values of [key] are used as the keys and the return values of
+/// [value] are used as the values for the new map.
+Map/*<K2, V2>*/ mapMap/*<K1, V1, K2, V2>*/(Map/*<K1, V1>*/ map,
+ {/*=K2*/ key(/*=K1*/ key, /*=V1*/ value),
+ /*=V2*/ value(/*=K1*/ key, /*=V1*/ value)}) {
+ key ??= (mapKey, _) => mapKey as dynamic/*=K2*/;
+ value ??= (_, mapValue) => mapValue as dynamic/*=V2*/;
+
+ var result = /*<K2, V2>*/{};
+ map.forEach((mapKey, mapValue) {
+ result[key(mapKey, mapValue)] = value(mapKey, mapValue);
+ });
+ return result;
+}
+
+/// Returns a new map with all key/value pairs in both [map1] and [map2].
+///
+/// If there are keys that occur in both maps, the [value] function is used to
+/// select the value that goes into the resulting map based on the two original
+/// values. If [value] is omitted, the value from [map2] is used.
+Map/*<K, V>*/ mergeMaps/*<K, V>*/(Map/*<K, V>*/ map1, Map/*<K, V>*/ map2,
+ {/*=V*/ value(/*=V*/ value1, /*=V*/ value2)}) {
+ var result = new Map/*<K, V>*/.from(map1);
+ if (value == null) return result..addAll(map2);
+
+ map2.forEach((key, mapValue) {
+ result[key] = result.containsKey(key)
+ ? value(result[key], mapValue)
+ : mapValue;
+ });
+ return result;
+}
+
+/// Groups the elements in [values] by the value returned by [key].
+///
+/// Returns a map from keys computed by [key] to a list of all values for which
+/// [key] returns that key. The values appear in the list in the same relative
+/// order as in [values].
+Map<dynamic/*=T*/, List/*<S>*/> groupBy/*<S, T>*/(Iterable/*<S>*/ values,
+ /*=T*/ key(/*=S*/ element)) {
+ var map = /*<T, List<S>>*/{};
+ for (var element in values) {
+ var list = map.putIfAbsent(key(element), () => []);
+ list.add(element);
+ }
+ return map;
+}
+
+/// Returns the element of [values] for which [orderBy] returns the minimum
+/// value.
+///
+/// The values returned by [orderBy] are compared using the [compare] function.
+/// If [compare] is omitted, values must implement [Comparable<T>] and they are
+/// compared using their [Comparable.compareTo].
+/*=S*/ minBy/*<S, T>*/(Iterable/*<S>*/ values, /*=T*/ orderBy(/*=S*/ element),
+ {int compare(/*=T*/ value1, /*=T*/ value2)}) {
+ compare ??= defaultCompare/*<T>*/();
+
+ var/*=S*/ minValue;
+ var/*=T*/ minOrderBy;
+ for (var element in values) {
+ var elementOrderBy = orderBy(element);
+ if (minOrderBy == null || compare(elementOrderBy, minOrderBy) < 0) {
+ minValue = element;
+ minOrderBy = elementOrderBy;
+ }
+ }
+ return min;
+}
+
+/// Returns the element of [values] for which [orderBy] returns the maximum
+/// value.
+///
+/// The values returned by [orderBy] are compared using the [compare] function.
+/// If [compare] is omitted, values must implement [Comparable<T>] and they are
+/// compared using their [Comparable.compareTo].
+/*=S*/ maxBy/*<S, T>*/(Iterable/*<S>*/ values, /*=T*/ orderBy(/*=S*/ element),
+ {int compare(/*=T*/ value1, /*=T*/ value2)}) {
+ compare ??= defaultCompare/*<T>*/();
+
+ var/*=S*/ maxValue;
+ var/*=T*/ maxOrderBy;
+ for (var element in values) {
+ var elementOrderBy = orderBy(element);
+ if (maxOrderBy == null || compare(elementOrderBy, maxOrderBy) > 0) {
+ maxValue = element;
+ maxOrderBy = elementOrderBy;
+ }
+ }
+ return max;
+}
+
+/// Returns the [transitive closure][] of [graph].
+///
+/// [transitive closure]: https://en.wikipedia.org/wiki/Transitive_closure
+///
+/// This interprets [graph] as a directed graph with a vertex for each key and
+/// edges from each key to the values associated with that key.
+///
+/// Assumes that every vertex in the graph has a key to represent it, even if
+/// that vertex has no outgoing edges. For example, `{"a": ["b"]}` is not valid,
+/// but `{"a": ["b"], "b": []}` is.
+Map<dynamic/*=T*/, Set/*<T>*/> transitiveClosure/*<T>*/(
+ Map<dynamic/*=T*/, Iterable/*<T>*/> graph) {
+ // This uses [Warshall's algorithm][], modified not to add a vertex from each
+ // node to itself.
+ //
+ // [Warshall's algorithm]: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Applications_and_generalizations.
+ var result = /*<T, Set>*/{};
+ graph.forEach((vertex, edges) {
+ result[vertex] = new Set/*<T>*/.from(edges);
+ });
+
+ // Lists are faster to iterate than maps, so we create a list since we're
+ // iterating repeatedly.
+ var keys = graph.keys.toList();
+ for (var vertex1 in keys) {
+ for (var vertex2 in keys) {
+ for (var vertex3 in keys) {
+ if (result[vertex2].contains(vertex1) &&
+ result[vertex1].contains(vertex3)) {
+ result[vertex2].add(vertex3);
+ }
+ }
+ }
+ }
+
+ return result;
+}
diff --git a/pubspec.yaml b/pubspec.yaml
index 7c88550..06c2cb7 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,5 +1,5 @@
name: collection
-version: 1.7.0
+version: 1.8.0
author: Dart Team <misc@dartlang.org>
description: Collections and utilities functions and classes related to collections.
homepage: https://www.github.com/dart-lang/collection
diff --git a/test/functions_test.dart b/test/functions_test.dart
new file mode 100644
index 0000000..4d928bf
--- /dev/null
+++ b/test/functions_test.dart
@@ -0,0 +1,184 @@
+// Copyright (c) 2016, 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:test/test.dart";
+
+import "package:collection/collection.dart";
+
+void main() {
+ group("mapMap()", () {
+ test("with an empty map returns an empty map", () {
+ expect(
+ mapMap({},
+ key: expectAsync((_, __) {}, count: 0),
+ value: expectAsync((_, __) {}, count: 0)),
+ isEmpty);
+ });
+
+ test("with no callbacks, returns a copy of the map", () {
+ var map = {"foo": 1, "bar": 2};
+ var result = mapMap(map);
+ expect(result, equals({"foo": 1, "bar": 2}));
+
+ // The resulting map should be a copy.
+ result["foo"] = 3;
+ expect(map, equals({"foo": 1, "bar": 2}));
+ });
+
+ test("maps the map's keys", () {
+ expect(mapMap({"foo": 1, "bar": 2}, key: (key, value) => key[value]),
+ equals({"o": 1, "r": 2}));
+ });
+
+ test("maps the map's values", () {
+ expect(mapMap({"foo": 1, "bar": 2}, value: (key, value) => key[value]),
+ equals({"foo": "o", "bar": "r"}));
+ });
+
+ test("maps both the map's keys and values", () {
+ expect(
+ mapMap({"foo": 1, "bar": 2},
+ key: (key, value) => "$key$value",
+ value: (key, value) => key[value]),
+ equals({"foo1": "o", "bar2": "r"}));
+ });
+ });
+
+ group("mergeMaps()", () {
+ test("with empty maps returns an empty map", () {
+ expect(mergeMaps({}, {}, value: expectAsync((_, __) {}, count: 0)),
+ isEmpty);
+ });
+
+ test("returns a map with all values in both input maps", () {
+ expect(mergeMaps({"foo": 1, "bar": 2}, {"baz": 3, "qux": 4}),
+ equals({"foo": 1, "bar": 2, "baz": 3, "qux": 4}));
+ });
+
+ test("the second map's values win by default", () {
+ expect(mergeMaps({"foo": 1, "bar": 2}, {"bar": 3, "baz": 4}),
+ equals({"foo": 1, "bar": 3, "baz": 4}));
+ });
+
+ test("uses the callback to merge values", () {
+ expect(mergeMaps({"foo": 1, "bar": 2}, {"bar": 3, "baz": 4},
+ value: (value1, value2) => value1 + value2),
+ equals({"foo": 1, "bar": 5, "baz": 4}));
+ });
+ });
+
+ group("groupBy()", () {
+ test("returns an empty map for an empty iterable", () {
+ expect(groupBy([], expectAsync((_) {}, count: 0)), isEmpty);
+ });
+
+ test("groups elements by the function's return value", () {
+ expect(
+ groupBy(["foo", "bar", "baz", "bop", "qux"], (string) => string[1]),
+ equals({"o": ["foo", "bop"], "a": ["bar", "baz"], "u": ["qux"]}));
+ });
+ });
+
+ group("minBy()", () {
+ test("returns null for an empty iterable", () {
+ expect(
+ minBy([], expectAsync((_) {}, count: 0),
+ compare: expectAsync((_, __) {}, count: 0)),
+ isNull);
+ });
+
+ test("returns the element for which the ordering function returns the "
+ "smallest value", () {
+ expect(
+ minBy(
+ [{"foo": 3}, {"foo": 5}, {"foo": 4}, {"foo": 1}, {"foo": 2}],
+ (map) => map["foo"]),
+ equals({"foo": 1}));
+ });
+
+ test("uses a custom comparator if provided", () {
+ expect(
+ minBy(
+ [{"foo": 3}, {"foo": 5}, {"foo": 4}, {"foo": 1}, {"foo": 2}],
+ (map) => map,
+ compare: (map1, map2) => map1["foo"].compareTo(map2["foo"])),
+ equals({"foo": 1}));
+ });
+ });
+
+ group("maxBy()", () {
+ test("returns null for an empty iterable", () {
+ expect(
+ maxBy([], expectAsync((_) {}, count: 0),
+ compare: expectAsync((_, __) {}, count: 0)),
+ isNull);
+ });
+
+ test("returns the element for which the ordering function returns the "
+ "largest value", () {
+ expect(
+ maxBy(
+ [{"foo": 3}, {"foo": 5}, {"foo": 4}, {"foo": 1}, {"foo": 2}],
+ (map) => map["foo"]),
+ equals({"foo": 5}));
+ });
+
+ test("uses a custom comparator if provided", () {
+ expect(
+ maxBy(
+ [{"foo": 3}, {"foo": 5}, {"foo": 4}, {"foo": 1}, {"foo": 2}],
+ (map) => map,
+ compare: (map1, map2) => map1["foo"].compareTo(map2["foo"])),
+ equals({"foo": 5}));
+ });
+ });
+
+ group("transitiveClosure()", () {
+ test("returns an empty map for an empty graph", () {
+ expect(transitiveClosure({}), isEmpty);
+ });
+
+ test("returns the input when there are no transitive connections", () {
+ expect(transitiveClosure({
+ "foo": ["bar"],
+ "bar": [],
+ "bang": ["qux", "zap"],
+ "qux": [],
+ "zap": []
+ }), equals({
+ "foo": ["bar"],
+ "bar": [],
+ "bang": ["qux", "zap"],
+ "qux": [],
+ "zap": []
+ }));
+ });
+
+ test("flattens transitive connections", () {
+ expect(transitiveClosure({
+ "qux": [],
+ "bar": ["baz"],
+ "baz": ["qux"],
+ "foo": ["bar"]
+ }), equals({
+ "foo": ["bar", "baz", "qux"],
+ "bar": ["baz", "qux"],
+ "baz": ["qux"],
+ "qux": []
+ }));
+ });
+
+ test("handles loops", () {
+ expect(transitiveClosure({
+ "foo": ["bar"],
+ "bar": ["baz"],
+ "baz": ["foo"]
+ }), equals({
+ "foo": ["bar", "baz", "foo"],
+ "bar": ["baz", "foo", "bar"],
+ "baz": ["foo", "bar", "baz"]
+ }));
+ });
+ });
+}
