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 [key] are used as the keys and the return values of |
| 12 /// [value] 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 var result = /*<K2, V2>*/{}; |
| 20 map.forEach((mapKey, mapValue) { |
| 21 result[key(mapKey, mapValue)] = value(mapKey, mapValue); |
| 22 }); |
| 23 return result; |
| 24 } |
| 25 |
| 26 /// Returns a new map with all key/value pairs in both [map1] and [map2]. |
| 27 /// |
| 28 /// If there are keys that occur in both maps, the [value] function is used to |
| 29 /// select the value that goes into the resulting map based on the two original |
| 30 /// values. If [value] is omitted, the value from [map2] is used. |
| 31 Map/*<K, V>*/ mergeMaps/*<K, V>*/(Map/*<K, V>*/ map1, Map/*<K, V>*/ map2, |
| 32 {/*=V*/ value(/*=V*/ value1, /*=V*/ value2)}) { |
| 33 var result = new Map/*<K, V>*/.from(map1); |
| 34 if (value == null) return result..addAll(map2); |
| 35 |
| 36 map2.forEach((key, mapValue) { |
| 37 result[key] = result.containsKey(key) |
| 38 ? value(result[key], mapValue) |
| 39 : mapValue; |
| 40 }); |
| 41 return result; |
| 42 } |
| 43 |
| 44 /// Groups the elements in [values] by the value returned by [key]. |
| 45 /// |
| 46 /// Returns a map from keys computed by [key] to a list of all values for which |
| 47 /// [key] returns that key. The values appear in the list in the same relative |
| 48 /// order as in [values]. |
| 49 Map<dynamic/*=T*/, List/*<S>*/> groupBy/*<S, T>*/(Iterable/*<S>*/ values, |
| 50 /*=T*/ key(/*=S*/ element)) { |
| 51 var map = /*<T, List<S>>*/{}; |
| 52 for (var element in values) { |
| 53 var list = map.putIfAbsent(key(element), () => []); |
| 54 list.add(element); |
| 55 } |
| 56 return map; |
| 57 } |
| 58 |
| 59 /// Returns the element of [values] for which [orderBy] returns the minimum |
| 60 /// value. |
| 61 /// |
| 62 /// The values returned by [orderBy] are compared using the [compare] function. |
| 63 /// If [compare] is omitted, values must implement [Comparable<T>] and they are |
| 64 /// compared using their [Comparable.compareTo]. |
| 65 /*=S*/ minBy/*<S, T>*/(Iterable/*<S>*/ values, /*=T*/ orderBy(/*=S*/ element), |
| 66 {int compare(/*=T*/ value1, /*=T*/ value2)}) { |
| 67 compare ??= defaultCompare/*<T>*/(); |
| 68 |
| 69 var/*=S*/ minValue; |
| 70 var/*=T*/ minOrderBy; |
| 71 for (var element in values) { |
| 72 var elementOrderBy = orderBy(element); |
| 73 if (minOrderBy == null || compare(elementOrderBy, minOrderBy) < 0) { |
| 74 minValue = element; |
| 75 minOrderBy = elementOrderBy; |
| 76 } |
| 77 } |
| 78 return min; |
| 79 } |
| 80 |
| 81 /// Returns the element of [values] for which [orderBy] returns the maximum |
| 82 /// value. |
| 83 /// |
| 84 /// The values returned by [orderBy] are compared using the [compare] function. |
| 85 /// If [compare] is omitted, values must implement [Comparable<T>] and they are |
| 86 /// compared using their [Comparable.compareTo]. |
| 87 /*=S*/ maxBy/*<S, T>*/(Iterable/*<S>*/ values, /*=T*/ orderBy(/*=S*/ element), |
| 88 {int compare(/*=T*/ value1, /*=T*/ value2)}) { |
| 89 compare ??= defaultCompare/*<T>*/(); |
| 90 |
| 91 var/*=S*/ maxValue; |
| 92 var/*=T*/ maxOrderBy; |
| 93 for (var element in values) { |
| 94 var elementOrderBy = orderBy(element); |
| 95 if (maxOrderBy == null || compare(elementOrderBy, maxOrderBy) > 0) { |
| 96 maxValue = element; |
| 97 maxOrderBy = elementOrderBy; |
| 98 } |
| 99 } |
| 100 return max; |
| 101 } |
| 102 |
| 103 /// Returns the [transitive closure][] of [graph]. |
| 104 /// |
| 105 /// [transitive closure]: https://en.wikipedia.org/wiki/Transitive_closure |
| 106 /// |
| 107 /// This interprets [graph] as a directed graph with a vertex for each key and |
| 108 /// edges from each key to the values associated with that key. |
| 109 /// |
| 110 /// Assumes that every vertex in the graph has a key to represent it, even if |
| 111 /// that vertex has no outgoing edges. For example, `{"a": ["b"]}` is not valid, |
| 112 /// but `{"a": ["b"], "b": []}` is. |
| 113 Map<dynamic/*=T*/, Set/*<T>*/> transitiveClosure/*<T>*/( |
| 114 Map<dynamic/*=T*/, Iterable/*<T>*/> graph) { |
| 115 // This uses [Warshall's algorithm][], modified not to add a vertex from each |
| 116 // node to itself. |
| 117 // |
| 118 // [Warshall's algorithm]: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshal
l_algorithm#Applications_and_generalizations. |
| 119 var result = /*<T, Set>*/{}; |
| 120 graph.forEach((vertex, edges) { |
| 121 result[vertex] = new Set/*<T>*/.from(edges); |
| 122 }); |
| 123 |
| 124 // Lists are faster to iterate than maps, so we create a list since we're |
| 125 // iterating repeatedly. |
| 126 var keys = graph.keys.toList(); |
| 127 for (var vertex1 in keys) { |
| 128 for (var vertex2 in keys) { |
| 129 for (var vertex3 in keys) { |
| 130 if (result[vertex2].contains(vertex1) && |
| 131 result[vertex1].contains(vertex3)) { |
| 132 result[vertex2].add(vertex3); |
| 133 } |
| 134 } |
| 135 } |
| 136 } |
| 137 |
| 138 return result; |
| 139 } |
OLD | NEW |