blob: 83e0493a4dce7f244d8e88b89f697eb3362d8e52 [file] [log] [blame]
 // 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 'dart:collection'; import 'dart:math' as math; 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 mapMap(Map map, {K2 key(K1 key, V1 value), V2 value(K1 key, V1 value)}) { key ??= (mapKey, _) => mapKey as K2; value ??= (_, mapValue) => mapValue as V2; var result = {}; 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 mergeMaps(Map map1, Map map2, {V value(V value1, V value2)}) { var result = Map.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> groupBy(Iterable values, T key(S element)) { var map = >{}; 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] and they are /// compared using their [Comparable.compareTo]. S minBy(Iterable values, T orderBy(S element), {int compare(T value1, T value2)}) { compare ??= defaultCompare(); S minValue; T minOrderBy; for (var element in values) { var elementOrderBy = orderBy(element); if (minOrderBy == null || compare(elementOrderBy, minOrderBy) < 0) { minValue = element; minOrderBy = elementOrderBy; } } return minValue; } /// 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] and they are /// compared using their [Comparable.compareTo]. S maxBy(Iterable values, T orderBy(S element), {int compare(T value1, T value2)}) { compare ??= defaultCompare(); S maxValue; T maxOrderBy; for (var element in values) { var elementOrderBy = orderBy(element); if (maxOrderBy == null || compare(elementOrderBy, maxOrderBy) > 0) { maxValue = element; maxOrderBy = elementOrderBy; } } return maxValue; } /// Returns the [transitive closure][] of [graph]. /// /// [transitive closure]: https://en.wikipedia.org/wiki/Transitive_closure /// /// Interprets [graph] as a directed graph with a vertex for each key and edges /// from each key to the values that the key maps to. /// /// Assumes that every vertex in the graph has a key to represent it, even if /// that vertex has no outgoing edges. This isn't checked, but if it's not /// satisfied, the function may crash or provide unexpected output. For example, /// `{"a": ["b"]}` is not valid, but `{"a": ["b"], "b": []}` is. Map> transitiveClosure(Map> 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 = >{}; graph.forEach((vertex, edges) { result[vertex] = Set.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; } /// Returns the [strongly connected components][] of [graph], in topological /// order. /// /// [strongly connected components]: https://en.wikipedia.org/wiki/Strongly_connected_component /// /// Interprets [graph] as a directed graph with a vertex for each key and edges /// from each key to the values that the key maps to. /// /// Assumes that every vertex in the graph has a key to represent it, even if /// that vertex has no outgoing edges. This isn't checked, but if it's not /// satisfied, the function may crash or provide unexpected output. For example, /// `{"a": ["b"]}` is not valid, but `{"a": ["b"], "b": []}` is. List> stronglyConnectedComponents(Map> graph) { // This uses [Tarjan's algorithm][]. // // [Tarjan's algorithm]: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm var index = 0; var stack = []; var result = >[]; // The order of these doesn't matter, so we use un-linked implementations to // avoid unnecessary overhead. var indices = HashMap(); var lowLinks = HashMap(); var onStack = HashSet(); strongConnect(T vertex) { indices[vertex] = index; lowLinks[vertex] = index; index++; stack.add(vertex); onStack.add(vertex); for (var successor in graph[vertex]) { if (!indices.containsKey(successor)) { strongConnect(successor); lowLinks[vertex] = math.min(lowLinks[vertex], lowLinks[successor]); } else if (onStack.contains(successor)) { lowLinks[vertex] = math.min(lowLinks[vertex], lowLinks[successor]); } } if (lowLinks[vertex] == indices[vertex]) { var component = Set(); T neighbor; do { neighbor = stack.removeLast(); onStack.remove(neighbor); component.add(neighbor); } while (neighbor != vertex); result.add(component); } } for (var vertex in graph.keys) { if (!indices.containsKey(vertex)) strongConnect(vertex); } // Tarjan's algorithm produces a reverse-topological sort, so we reverse it to // get a normal topological sort. return result.reversed.toList(); }