lib/src/functions.dart

// 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:math' as math;
import 'dart:collection';

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/*<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*/;

  var result = /*<K2, V2>*/{};
  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/*<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);
  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<dynamic/*=T*/, List/*<S>*/> groupBy/*<S, T>*/(Iterable/*<S>*/ values,
    /*=T*/ key(/*=S*/ element)) {
  var map = /*<T, List<S>>*/{};
  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<T>] and they are
/// compared using their [Comparable.compareTo].
/*=S*/ minBy/*<S, T>*/(Iterable/*<S>*/ values, /*=T*/ orderBy(/*=S*/ element),
    {int compare(/*=T*/ value1, /*=T*/ value2)}) {
  compare ??= defaultCompare/*<T>*/();

  var/*=S*/ minValue;
  var/*=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<T>] and they are
/// compared using their [Comparable.compareTo].
/*=S*/ maxBy/*<S, T>*/(Iterable/*<S>*/ values, /*=T*/ orderBy(/*=S*/ element),
    {int compare(/*=T*/ value1, /*=T*/ value2)}) {
  compare ??= defaultCompare/*<T>*/();

  var/*=S*/ maxValue;
  var/*=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<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);
  });

  // 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<Set/*<T>*/> stronglyConnectedComponents/*<T>*/(
    Map<dynamic/*=T*/, Iterable/*<T>*/> 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 = /*<T>*/[];
  var result = /*<Set<T>>*/[];

  // The order of these doesn't matter, so we use un-linked implementations to
  // avoid unnecessary overhead.
  var indices = new HashMap/*<T, int>*/();
  var lowLinks = new HashMap/*<T, int>*/();
  var onStack = new HashSet/*<T>*/();

  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 = new Set/*<T>*/();
      var/*=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();
}