New analyzer snapshot.

pkg/analyzer/lib/src/generated/utilities_collection.dart

 // Copyright (c) 2014, 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.
 
 // This code was auto-generated, is not intended to be edited, and is subject to
 // significant change. Please see the README file for more information.
 
 library engine.utilities.collection;
 
 import 'java_core.dart';
@@ skipping 94 matching lines @@
    *
    * @param key the token being mapped to the value
    * @param value the token to which the key will be mapped
    */
   void put(Token key, Token value) {
     _map[key] = value;
   }
 }
 
 /**
+ * Instances of the class `DirectedGraph` implement a directed graph in which the nodes are
+ * arbitrary (client provided) objects and edges are represented implicitly. The graph will allow an
+ * edge from any node to any other node, including itself, but will not represent multiple edges
+ * between the same pair of nodes.
+ *
+ * @param N the type of the nodes in the graph
+ */
+class DirectedGraph<N> {
+  /**
+   * The table encoding the edges in the graph. An edge is represented by an entry mapping the head
+   * to a set of tails. Nodes that are not the head of any edge are represented by an entry mapping
+   * the node to an empty set of tails.
+   */
+  Map<N, Set<N>> _edges = new Map<N, Set<N>>();
+
+  /**
+   * Add an edge from the given head node to the given tail node. Both nodes will be a part of the
+   * graph after this method is invoked, whether or not they were before.
+   *
+   * @param head the node at the head of the edge
+   * @param tail the node at the tail of the edge
+   */
+  void addEdge(N head, N tail) {
+    //
+    // First, ensure that the tail is a node known to the graph.
+    //
+    if (_edges[tail] == null) {
+      _edges[tail] = new Set<N>();
+    }
+    //
+    // Then create the edge.
+    //
+    Set<N> tails = _edges[head];
+    if (tails == null) {
+      tails = new Set<N>();
+      _edges[head] = tails;
+    }
+    tails.add(tail);
+  }
+
+  /**
+   * Add the given node to the set of nodes in the graph.
+   *
+   * @param node the node to be added
+   */
+  void addNode(N node) {
+    Set<N> tails = _edges[node];
+    if (tails == null) {
+      _edges[node] = new Set<N>();
+    }
+  }
+
+  /**
+   * Return a list of nodes that form a cycle, or `null` if there are no cycles in this graph.
+   *
+   * @return a list of nodes that form a cycle
+   */
+  List<N> findCycle() => null;
+
+  /**
+   * Return a list of nodes that form a cycle containing the given node. If the node is not part of
+   * this graph, then a list containing only the node itself will be returned.
+   *
+   * @return a list of nodes that form a cycle containing the given node
+   */
+  List<N> findCycleContaining(N node) {
+    if (node == null) {
+      throw new IllegalArgumentException();
+    }
+    DirectedGraph_SccFinder<N> finder = new DirectedGraph_SccFinder<N>(this);
+    return finder.componentContaining(node);
+  }
+
+  /**
+   * Return the number of nodes in this graph.
+   *
+   * @return the number of nodes in this graph
+   */
+  int get nodeCount => _edges.length;
+
+  /**
+   * Return a set containing the tails of edges that have the given node as their head. The set will
+   * be empty if there are no such edges or if the node is not part of the graph. Clients must not
+   * modify the returned set.
+   *
+   * @param head the node at the head of all of the edges whose tails are to be returned
+   * @return a set containing the tails of edges that have the given node as their head
+   */
+  Set<N> getTails(N head) {
+    Set<N> tails = _edges[head];
+    if (tails == null) {
+      return new Set<N>();
+    }
+    return tails;
+  }
+
+  /**
+   * Return `true` if this graph is empty.
+   *
+   * @return `true` if this graph is empty
+   */
+  bool get isEmpty => _edges.isEmpty;
+
+  /**
+   * Remove all of the given nodes from this graph. As a consequence, any edges for which those
+   * nodes were either a head or a tail will also be removed.
+   *
+   * @param nodes the nodes to be removed
+   */
+  void removeAllNodes(List<N> nodes) {
+    for (N node in nodes) {
+      removeNode(node);
+    }
+  }
+
+  /**
+   * Remove the edge from the given head node to the given tail node. If there was no such edge then
+   * the graph will be unmodified: the number of edges will be the same and the set of nodes will be
+   * the same (neither node will either be added or removed).
+   *
+   * @param head the node at the head of the edge
+   * @param tail the node at the tail of the edge
+   * @return `true` if the graph was modified as a result of this operation
+   */
+  void removeEdge(N head, N tail) {
+    Set<N> tails = _edges[head];
+    if (tails != null) {
+      tails.remove(tail);
+    }
+  }
+
+  /**
+   * Remove the given node from this graph. As a consequence, any edges for which that node was
+   * either a head or a tail will also be removed.
+   *
+   * @param node the node to be removed
+   */
+  void removeNode(N node) {
+    _edges.remove(node);
+    for (Set<N> tails in _edges.values) {
+      tails.remove(node);
+    }
+  }
+
+  /**
+   * Find one node (referred to as a sink node) that has no outgoing edges (that is, for which there
+   * are no edges that have that node as the head of the edge) and remove it from this graph. Return
+   * the node that was removed, or `null` if there are no such nodes either because the graph
+   * is empty or because every node in the graph has at least one outgoing edge. As a consequence of
+   * removing the node from the graph any edges for which that node was a tail will also be removed.
+   *
+   * @return the sink node that was removed
+   */
+  N removeSink() {
+    N sink = _findSink();
+    if (sink == null) {
+      return null;
+    }
+    removeNode(sink);
+    return sink;
+  }
+
+  /**
+   * Return one node that has no outgoing edges (that is, for which there are no edges that have
+   * that node as the head of the edge), or `null` if there are no such nodes.
+   *
+   * @return a sink node
+   */
+  N _findSink() {
+    for (N key in _edges.keys) {
+      if (_edges[key].isEmpty) return key;
+    }
+    return null;
+  }
+}
+
+/**
+ * Instances of the class `NodeInfo` are used by the [SccFinder] to maintain
+ * information about the nodes that have been examined.
+ *
+ * @param N the type of the nodes corresponding to the entries
+ */
+class DirectedGraph_NodeInfo<N> {
+  /**
+   * The depth of this node.
+   */
+  int index = 0;
+
+  /**
+   * The depth of the first node in a cycle.
+   */
+  int lowlink = 0;
+
+  /**
+   * A flag indicating whether the corresponding node is on the stack. Used to remove the need for
+   * searching a collection for the node each time the question needs to be asked.
+   */
+  bool onStack = false;
+
+  /**
+   * The component that contains the corresponding node.
+   */
+  List<N> component;
+
+  /**
+   * Initialize a newly created information holder to represent a node at the given depth.
+   *
+   * @param depth the depth of the node being represented
+   */
+  DirectedGraph_NodeInfo(int depth) {
+    index = depth;
+    lowlink = depth;
+    onStack = false;
+  }
+}
+
+/**
+ * Instances of the class `SccFinder` implement Tarjan's Algorithm for finding the strongly
+ * connected components in a graph.
+ */
+class DirectedGraph_SccFinder<N> {
+  /**
+   * The graph to work with.
+   */
+  DirectedGraph<N> _graph;
+
+  /**
+   * The index used to uniquely identify the depth of nodes.
+   */
+  int _index = 0;
+
+  /**
+   * The stack of nodes that are being visited in order to identify components.
+   */
+  List<N> _stack = new List<N>();
+
+  /**
+   * A table mapping nodes to information about the nodes that is used by this algorithm.
+   */
+  Map<N, DirectedGraph_NodeInfo<N>> _nodeMap = new Map<N, DirectedGraph_NodeInfo<N>>();
+
+  /**
+   * Initialize a newly created finder.
+   */
+  DirectedGraph_SccFinder(DirectedGraph<N> graph) : super() {
+    this._graph = graph;
+  }
+
+  /**
+   * Return a list containing the nodes that are part of the strongly connected component that
+   * contains the given node.
+   *
+   * @param node the node used to identify the strongly connected component to be returned
+   * @return the nodes that are part of the strongly connected component that contains the given
+   *         node
+   */
+  List<N> componentContaining(N node) => _strongConnect(node).component;
+
+  /**
+   * Remove and return the top-most element from the stack.
+   *
+   * @return the element that was removed
+   */
+  N _pop() {
+    N node = _stack.removeAt(_stack.length - 1);
+    _nodeMap[node].onStack = false;
+    return node;
+  }
+
+  /**
+   * Add the given node to the stack.
+   *
+   * @param node the node to be added to the stack
+   */
+  void _push(N node) {
+    _nodeMap[node].onStack = true;
+    _stack.add(node);
+  }
+
+  /**
+   * Compute the strongly connected component that contains the given node as well as any
+   * components containing nodes that are reachable from the given component.
+   *
+   * @param v the node from which the search will begin
+   * @return the information about the given node
+   */
+  DirectedGraph_NodeInfo<N> _strongConnect(N v) {
+    //
+    // Set the depth index for v to the smallest unused index
+    //
+    DirectedGraph_NodeInfo<N> vInfo = new DirectedGraph_NodeInfo<N>(_index++);
+    _nodeMap[v] = vInfo;
+    _push(v);
+    //
+    // Consider successors of v
+    //
+    Set<N> tails = _graph._edges[v];
+    if (tails != null) {
+      for (N w in tails) {
+        DirectedGraph_NodeInfo<N> wInfo = _nodeMap[w];
+        if (wInfo == null) {
+          // Successor w has not yet been visited; recurse on it
+          wInfo = _strongConnect(w);
+          vInfo.lowlink = Math.min(vInfo.lowlink, wInfo.lowlink);
+        } else if (wInfo.onStack) {
+          // Successor w is in stack S and hence in the current SCC
+          vInfo.lowlink = Math.min(vInfo.lowlink, wInfo.index);
+        }
+      }
+    }
+    //
+    // If v is a root node, pop the stack and generate an SCC
+    //
+    if (vInfo.lowlink == vInfo.index) {
+      List<N> component = new List<N>();
+      N w;
+      do {
+        w = _pop();
+        component.add(w);
+        _nodeMap[w].component = component;
+      } while (w != v);
+    }
+    return vInfo;
+  }
+}
+
+/**
  * The class `ListUtilities` defines utility methods useful for working with [List
  ].
  */
 class ListUtilities {
   /**
    * Add all of the elements in the given array to the given list.
    *
    * @param list the list to which the elements are to be added
    * @param elements the elements to be added to the list
    */
   static void addAll(List list, List<Object> elements) {
     int count = elements.length;
     for (int i = 0; i < count; i++) {
       list.add(elements[i]);
     }
   }
 }