Add top-level collection-manipulation functions.

lib/src/functions.dart

Index: lib/src/functions.dart
diff --git a/lib/src/functions.dart b/lib/src/functions.dart
new file mode 100644
index 0000000000000000000000000000000000000000..4de7b9d65950636e2d898d4118f673c717472c2b
--- /dev/null
+++ b/lib/src/functions.dart
@@ -0,0 +1,129 @@
+// 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 [keyFn] are used as the keys and the return values of

[Lasse Reichstein Nielsen, 2016/05/20 12:22:38]

keyFn -> key (actual name used)
Ditto valueFn -> value

[nweiz, 2016/05/25 21:29:56]

Done.

+/// [valueFn] 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*/;
+
+  return new Map.fromIterable(map.keys,
+      key: (mapKey) => key(mapKey as dynamic/*=K1*/, map[mapKey]),
+      value: (mapKey) => value(mapKey as dynamic/*=K1*/, map[mapKey]));

[Lasse Reichstein Nielsen, 2016/05/20 12:22:38]

Seems inefficient with all those lookups. Maybe just:

var result = new Map/*<K2, V2>*/();
map.forEach((/*=K1*/ k, /*=V1*/ v) {
  result[key(k, v)] = value(k, v);
});
return result;

[nweiz, 2016/05/25 21:29:54]

Done.

+}
+
+/// Returns a new map with all values in both [map1] and [map2].

[Lasse Reichstein Nielsen, 2016/05/20 12:22:38]

values -> keys? key/value pairs?
(If keys overlap, this sounds like a key has more than one associated value in
the result)

[nweiz, 2016/05/25 21:29:55]

Done.

+///
+/// If there are conflicting keys, [value] is used to merge them. If it's
+/// not passed, [map2]'s value wins.

[Lasse Reichstein Nielsen, 2016/05/23 06:44:31]

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.

[nweiz, 2016/05/25 21:29:54]

Done.

+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);

[Lasse Reichstein Nielsen, 2016/05/20 12:22:38]

If value is null, you can use the addAll method on maps

if (value == null) {
  result.addAll(map2);
  return result;
}

I think that's easier to read, and it also pulls the value == null check out of
the loop.

[nweiz, 2016/05/25 21:29:55]

Done.

+  map2.forEach((key, mapValue) {
+    if (value == null || !result.containsKey(key)) {
+      result[key] = mapValue;
+    } else {
+      result[key] = value(result[key], mapValue);
+    }
+  });
+  return result;
+}
+
+/// Groups the elements in [iter] by the value returned by [key].

[Lasse Reichstein Nielsen, 2016/05/20 12:22:38]

Don't abbreviate iter, and "iterable" isn't describing what it is, just its
type. So maybe "elements" or "values".

[nweiz, 2016/05/25 21:29:54]

Done.

+///
+/// This returns a map whose keys are the return values of [key] and whose
+/// values are lists of each element in [iter] for which [key] returned that
+/// key, in the order those elements appear in [iter].

[Lasse Reichstein Nielsen, 2016/05/20 12:22:38]

Sounds complex. How about:

Returns a map from keys computed by [key] to a list of all values for which
[key] computes that key. The values appear in the list in the same relative
order as in [values].

Maybe add:

  So for each `value` in `values`, `groupBy(values,
key)[key(value)].contains(value)`.

Hmm, still complex.

[nweiz, 2016/05/25 21:29:55]

Done.

+Map<dynamic/*=T*/, List/*<S>*/> groupBy/*<S, T>*/(Iterable/*<S>*/ iter,
+    /*=T*/ key(/*=S*/ element)) {
+  var map = /*<T, List<S>>*/{};
+  for (var element in iter) {
+    var list = map.putIfAbsent(key(element), () => []);
+    list.add(element);
+  }
+  return map;
+}
+
+/// Returns the element of [iter] for which [order] returns the minimum value.

[Lasse Reichstein Nielsen, 2016/05/20 12:22:38]

iter -> values
Maybe: minimal -> least

[nweiz, 2016/05/25 21:29:55]

Done.
I think "minimum" is clearer.

+///
+/// By default, the return value of [order] is assumed to implement
+/// [Comparable<T>], and its [Comparable.compareTo()] method is called. However,
+/// if [compare] is passed, it's used to compare these values instead.

[Lasse Reichstein Nielsen, 2016/05/20 12:22:38]

We usually write that the other way around: Assume that "compare" is provided,
say what it does, then say what happens if it's omitted.

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].

[nweiz, 2016/05/25 21:29:54]

Done.

+/*=S*/ minBy/*<S, T>*/(Iterable/*<S>*/ iter, /*=T*/ order(/*=S*/ element),

[Lasse Reichstein Nielsen, 2016/05/20 12:22:38]

I'd rename "order" into "orderBy". It's a function, not a relation, and it
doesn't "order" its arguments itself.

[nweiz, 2016/05/25 21:29:55]

Done.

+    {int compare(/*=T*/ value1, /*=T*/ value2)}) {
+  compare ??= defaultCompare/*<T>*/();

[Lasse Reichstein Nielsen, 2016/05/20 12:22:38]

You should be able to use Comparable.compare as the default comparison on
comparables, but it's probably not strong-mode-ified yet.

[nweiz, 2016/05/25 21:29:54]

It's not :(.

+
+  var/*=S*/ min;

[Lasse Reichstein Nielsen, 2016/05/20 12:22:38]

min -> minValue

[nweiz, 2016/05/25 21:29:55]

Done.

+  var/*=T*/ minOrder;

[Lasse Reichstein Nielsen, 2016/05/20 12:22:38]

minOrderBy

[nweiz, 2016/05/25 21:29:54]

Done.

+  for (var element in iter) {
+    var elementOrder = order(element);
+    if (minOrder == null || compare(elementOrder, minOrder) < 0) {
+      min = element;
+      minOrder = elementOrder;
+    }
+  }
+  return min;
+}
+
+/// Returns the element of [iter] for which [order] returns the maximum value.

[Lasse Reichstein Nielsen, 2016/05/20 12:22:38]

Same comments as for minBy.

[nweiz, 2016/05/25 21:29:55]

Done.

+///
+/// By default, the return value of [order] is assumed to implement
+/// [Comparable<T>], and its [Comparable.compareTo()] method is called. However,
+/// if [compare] is passed, it's used to compare these values instead.
+/*=S*/ maxBy/*<S, T>*/(Iterable/*<S>*/ iter, /*=T*/ order(/*=S*/ element),
+    {int compare(/*=T*/ value1, /*=T*/ value2)}) {
+  compare ??= defaultCompare/*<T>*/();
+
+  var/*=S*/ max;
+  var/*=T*/ maxOrder;
+  for (var element in iter) {
+    var elementOrder = order(element);
+    if (maxOrder == null || compare(elementOrder, maxOrder) > 0) {
+      max = element;
+      maxOrder = elementOrder;
+    }
+  }
+  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. It assumes that
+/// every vertex in the graph has a key, even if that vertex has no outgoing
+/// edges.

[Lasse Reichstein Nielsen, 2016/05/20 12:22:38]

Not sure I understand the difference between keys and vertices.
Aren't the keys of the map exactly the vertices of the graph?

[nweiz, 2016/05/25 21:29:55]

There *shouldn't* be a difference—that's what this sentence is saying. Otherwise
users might expect that {"a": ["b"]} is a valid graph, when in fact it must be
{"a": ["b"], "b": []}. I've added a sentence giving this example.

+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);
+  });
+
+  for (var vertex1 in graph.keys) {
+    for (var vertex2 in graph.keys) {
+      for (var vertex3 in graph.keys) {

[Lasse Reichstein Nielsen, 2016/05/20 12:22:38]

Consider creating a list copy of graph.keys. Lists are faster and simpler to
iterate than maps. That would also mean that the graph isn't used any more, and
it can (potentially) be GC'ed.

[nweiz, 2016/05/25 21:29:55]

Done.

+        if (result[vertex2].contains(vertex1) &&
+            result[vertex1].contains(vertex3)) {

[Lasse Reichstein Nielsen, 2016/05/20 12:22:38]

It seems to me this ignores all vertex3 not in result[vertex1], so the third
loop could just loop over result[vertex1] instead of graph.keys.

(However, then you can no longer ignore the case where the sets contain elements
that are not vertices - not keys in the original graph map).

[Lasse Reichstein Nielsen, 2016/05/20 14:50:26]

On the other hand, then you have to worry about concurrent modification when
vertex2 == vertex1, so I guess this is simpler.

+          result[vertex2].add(vertex3);
+        }
+      }
+    }
+  }
+
+  return result;
+}