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 -> v
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 ju
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,
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 [va
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
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 descri
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 key
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.
|
+/// |
+/// 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
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
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 th
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
nweiz
2016/05/25 21:29:55
There *shouldn't* be a difference—that's what this
|
+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
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 res
Lasse Reichstein Nielsen
2016/05/20 14:50:26
On the other hand, then you have to worry about co
|
+ result[vertex2].add(vertex3); |
+ } |
+ } |
+ } |
+ } |
+ |
+ return result; |
+} |