| // 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'; |
| import 'scanner.dart' show Token; |
| |
| /** |
| * The class `BooleanArray` defines methods for operating on integers as if they were arrays |
| * of booleans. These arrays can be indexed by either integers or by enumeration constants. |
| */ |
| class BooleanArray { |
| /** |
| * Return the value of the element at the given index. |
| * |
| * @param array the array being accessed |
| * @param index the index of the element being accessed |
| * @return the value of the element at the given index |
| * @throws IndexOutOfBoundsException if the index is not between zero (0) and 31, inclusive |
| */ |
| static bool get(int array, int index) { |
| _checkIndex(index); |
| return (array & (1 << index)) > 0; |
| } |
| |
| /** |
| * Return the value of the element at the given index. |
| * |
| * @param array the array being accessed |
| * @param index the index of the element being accessed |
| * @return the value of the element at the given index |
| * @throws IndexOutOfBoundsException if the index is not between zero (0) and 31, inclusive |
| */ |
| static bool getEnum(int array, Enum index) => get(array, index.ordinal); |
| |
| /** |
| * Set the value of the element at the given index to the given value. |
| * |
| * @param array the array being modified |
| * @param index the index of the element being set |
| * @param value the value to be assigned to the element |
| * @return the updated value of the array |
| * @throws IndexOutOfBoundsException if the index is not between zero (0) and 31, inclusive |
| */ |
| static int set(int array, int index, bool value) { |
| _checkIndex(index); |
| if (value) { |
| return array | (1 << index); |
| } else { |
| return array & ~(1 << index); |
| } |
| } |
| |
| /** |
| * Set the value of the element at the given index to the given value. |
| * |
| * @param array the array being modified |
| * @param index the index of the element being set |
| * @param value the value to be assigned to the element |
| * @return the updated value of the array |
| * @throws IndexOutOfBoundsException if the index is not between zero (0) and 31, inclusive |
| */ |
| static int setEnum(int array, Enum index, bool value) => set(array, index.ordinal, value); |
| |
| /** |
| * Throw an exception if the index is not within the bounds allowed for an integer-encoded array |
| * of boolean values. |
| * |
| * @throws IndexOutOfBoundsException if the index is not between zero (0) and 31, inclusive |
| */ |
| static void _checkIndex(int index) { |
| if (index < 0 || index > 30) { |
| throw new RangeError("Index not between 0 and 30: ${index}"); |
| } |
| } |
| } |
| |
| /** |
| * Instances of the class `TokenMap` map one set of tokens to another set of tokens. |
| */ |
| class TokenMap { |
| /** |
| * A table mapping tokens to tokens. This should be replaced by a more performant implementation. |
| * One possibility is a pair of parallel arrays, with keys being sorted by their offset and a |
| * cursor indicating where to start searching. |
| */ |
| Map<Token, Token> _map = new Map<Token, Token>(); |
| |
| /** |
| * Return the token that is mapped to the given token, or `null` if there is no token |
| * corresponding to the given token. |
| * |
| * @param key the token being mapped to another token |
| * @return the token that is mapped to the given token |
| */ |
| Token get(Token key) => _map[key]; |
| |
| /** |
| * Map the key to the value. |
| * |
| * @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. |
| */ |
| final 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(this._graph) : super(); |
| |
| /** |
| * 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 (!identical(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]); |
| } |
| } |
| } |