OLD | NEW |
---|---|
(Empty) | |
1 // Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file | |
2 // for details. All rights reserved. Use of this source code is governed by a | |
3 // BSD-style license that can be found in the LICENSE file. | |
4 | |
5 import 'utils.dart'; | |
6 | |
7 // TODO(nweiz): When sdk#26488 is fixed, use overloads to ensure that if [key] | |
8 // or [value] isn't passed, `K2`/`V2` defaults to `K1`/`V1`, respectively. | |
9 /// Creates a new map from [map] with new keys and values. | |
10 /// | |
11 /// 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.
| |
12 /// [valueFn] are used as the values for the new map. | |
13 Map/*<K2, V2>*/ mapMap/*<K1, V1, K2, V2>*/(Map/*<K1, V1>*/ map, | |
14 {/*=K2*/ key(/*=K1*/ key, /*=V1*/ value), | |
15 /*=V2*/ value(/*=K1*/ key, /*=V1*/ value)}) { | |
16 key ??= (mapKey, _) => mapKey as dynamic/*=K2*/; | |
17 value ??= (_, mapValue) => mapValue as dynamic/*=V2*/; | |
18 | |
19 return new Map.fromIterable(map.keys, | |
20 key: (mapKey) => key(mapKey as dynamic/*=K1*/, map[mapKey]), | |
21 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.
| |
22 } | |
23 | |
24 /// 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.
| |
25 /// | |
26 /// If there are conflicting keys, [value] is used to merge them. If it's | |
27 /// 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.
| |
28 Map/*<K, V>*/ mergeMaps/*<K, V>*/(Map/*<K, V>*/ map1, Map/*<K, V>*/ map2, | |
29 {/*=V*/ value(/*=V*/ value1, /*=V*/ value2)}) { | |
30 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.
| |
31 map2.forEach((key, mapValue) { | |
32 if (value == null || !result.containsKey(key)) { | |
33 result[key] = mapValue; | |
34 } else { | |
35 result[key] = value(result[key], mapValue); | |
36 } | |
37 }); | |
38 return result; | |
39 } | |
40 | |
41 /// 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.
| |
42 /// | |
43 /// This returns a map whose keys are the return values of [key] and whose | |
44 /// values are lists of each element in [iter] for which [key] returned that | |
45 /// 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.
| |
46 Map<dynamic/*=T*/, List/*<S>*/> groupBy/*<S, T>*/(Iterable/*<S>*/ iter, | |
47 /*=T*/ key(/*=S*/ element)) { | |
48 var map = /*<T, List<S>>*/{}; | |
49 for (var element in iter) { | |
50 var list = map.putIfAbsent(key(element), () => []); | |
51 list.add(element); | |
52 } | |
53 return map; | |
54 } | |
55 | |
56 /// 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.
| |
57 /// | |
58 /// By default, the return value of [order] is assumed to implement | |
59 /// [Comparable<T>], and its [Comparable.compareTo()] method is called. However, | |
60 /// 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.
| |
61 /*=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.
| |
62 {int compare(/*=T*/ value1, /*=T*/ value2)}) { | |
63 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 :(.
| |
64 | |
65 var/*=S*/ min; | |
Lasse Reichstein Nielsen
2016/05/20 12:22:38
min -> minValue
nweiz
2016/05/25 21:29:55
Done.
| |
66 var/*=T*/ minOrder; | |
Lasse Reichstein Nielsen
2016/05/20 12:22:38
minOrderBy
nweiz
2016/05/25 21:29:54
Done.
| |
67 for (var element in iter) { | |
68 var elementOrder = order(element); | |
69 if (minOrder == null || compare(elementOrder, minOrder) < 0) { | |
70 min = element; | |
71 minOrder = elementOrder; | |
72 } | |
73 } | |
74 return min; | |
75 } | |
76 | |
77 /// 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.
| |
78 /// | |
79 /// By default, the return value of [order] is assumed to implement | |
80 /// [Comparable<T>], and its [Comparable.compareTo()] method is called. However, | |
81 /// if [compare] is passed, it's used to compare these values instead. | |
82 /*=S*/ maxBy/*<S, T>*/(Iterable/*<S>*/ iter, /*=T*/ order(/*=S*/ element), | |
83 {int compare(/*=T*/ value1, /*=T*/ value2)}) { | |
84 compare ??= defaultCompare/*<T>*/(); | |
85 | |
86 var/*=S*/ max; | |
87 var/*=T*/ maxOrder; | |
88 for (var element in iter) { | |
89 var elementOrder = order(element); | |
90 if (maxOrder == null || compare(elementOrder, maxOrder) > 0) { | |
91 max = element; | |
92 maxOrder = elementOrder; | |
93 } | |
94 } | |
95 return max; | |
96 } | |
97 | |
98 /// Returns the [transitive closure][] of [graph]. | |
99 /// | |
100 /// [transitive closure]: https://en.wikipedia.org/wiki/Transitive_closure | |
101 /// | |
102 /// This interprets [graph] as a directed graph with a vertex for each key and | |
103 /// edges from each key to the values associated with that key. It assumes that | |
104 /// every vertex in the graph has a key, even if that vertex has no outgoing | |
105 /// 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
| |
106 Map<dynamic/*=T*/, Set/*<T>*/> transitiveClosure/*<T>*/( | |
107 Map<dynamic/*=T*/, Iterable/*<T>*/> graph) { | |
108 // This uses [Warshall's algorithm][], modified not to add a vertex from each | |
109 // node to itself. | |
110 // | |
111 // [Warshall's algorithm]: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshal l_algorithm#Applications_and_generalizations. | |
112 var result = /*<T, Set>*/{}; | |
113 graph.forEach((vertex, edges) { | |
114 result[vertex] = new Set/*<T>*/.from(edges); | |
115 }); | |
116 | |
117 for (var vertex1 in graph.keys) { | |
118 for (var vertex2 in graph.keys) { | |
119 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.
| |
120 if (result[vertex2].contains(vertex1) && | |
121 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
| |
122 result[vertex2].add(vertex3); | |
123 } | |
124 } | |
125 } | |
126 } | |
127 | |
128 return result; | |
129 } | |
OLD | NEW |