Fix capitalization

[mirror_edk2.git] / Tools / Source / Prototype / DAG.java

import java.util.*;\r
\r
// A directed Acyclic Graph class. The main purpose is to provide a set of nodes\r
// and the dependency relations between them.  Then ask for a topological sort of\r
// the nodes.\r
\r
public class DAG<Node>\r
{\r
  // Constructor.\r
  DAG()\r
  {\r
    children = new HashMap<Node,Set<Node>>();\r
  }\r
\r
  public Set<Node> nodes() { return children.keySet(); }\r
  public Set<Node> children(Node parent) { return children.get(parent); }\r
\r
  // Add the relations from a compatible DAG to this one.\r
  public void add(DAG<Node> newDag)\r
  {\r
    for(Node parent : newDag.children.keySet())\r
    {\r
      children.put(parent, newDag.children(parent));\r
    }\r
  }\r
\r
  // The central data structure is a one-to-many map. Each node is \r
  // treated as a parent. It is mapped to a list of its children. Leaf\r
  // nodes are also treated as parents and map to an empty list of\r
  // children.\r
  Map<Node,Set<Node>> children;\r
\r
  public void remove(Collection<Node> nodes)\r
  {\r
    // Remove it as a parent\r
    for(Node node : nodes)\r
    {\r
      children.remove(node);\r
    }\r
\r
    for(Set<Node> childlist : children.values())\r
    {\r
      // Remove it as a child\r
      childlist.removeAll(nodes);\r
    }\r
  }\r
\r
  // Remove every occurrence of node from the DAG.\r
  public void remove(Node node)\r
  {\r
    // Remove it as a parent\r
    children.remove(node);\r
\r
    for(Set<Node> childlist : children.values())\r
    {\r
      // Remove it as a child\r
      childlist.remove(node);\r
    }\r
  }\r
\r
  // Return true iff parent is a direct parent of child.\r
  public boolean directDepends(Node parent, Node child)\r
  {\r
    return children.containsKey(parent) ? \r
           children(parent).contains(child) :\r
           false;\r
  }\r
\r
  // Return true iff parent is a direct or indirect parent of child.\r
  // This is the transitive closure of the dependency relation.\r
  public boolean depends(Node parent, Node child)\r
  {\r
    if(!children.containsKey(parent))\r
    {\r
      return false;\r
    }\r
    if( directDepends(parent, child) )\r
    {\r
      return true;\r
    }\r
    else\r
    {\r
      for(Node descendent : children(parent) )\r
      {\r
        // Recursively call depends() to compute the transitive closure of\r
        // the relation.\r
        if(depends(descendent, child))\r
        {\r
          return true;\r
        }\r
      }\r
      return false;\r
    } \r
  }\r
\r
  // Add a parent child relation to the dag. Fail if there is already\r
  // a dependency from the child to the parent. This implies a cycle.\r
  // Our invariant is that the DAG must never contain a cycle. That\r
  // way it lives up to its name.\r
  public void add(Node parent, Node child)\r
  {\r
    if(depends(child, parent))\r
    {\r
      System.out.format("Error: There is a cycle from %s to %s.\n", parent, child);\r
      return;\r
    }\r
    if(children.containsKey(parent))\r
    {\r
      children(parent).add(child);\r
    }\r
    else\r
    {\r
      Set<Node> cs = new HashSet<Node>();\r
      cs.add(child);\r
      children.put(parent, cs);\r
    }\r
    if(!children.containsKey(child))\r
    {\r
      children.put(child,new HashSet<Node>());\r
    }\r
  }\r
\r
  // Perform a topological sort on the DAG.\r
  public List<Node> sort()\r
  {\r
    // Make an ordered list to hold the topo sort.\r
    List<Node> sorted = new LinkedList<Node>();\r
\r
    // We add the leaves to the beginning of the list until\r
    // the sorted list contains all the nodes in the DAG.\r
    while(!sorted.containsAll(nodes()))\r
    {\r
      // Ignoring the ones we have found, what are the leaves of this\r
      // DAG?\r
      Set<Node> leaves = leaves(sorted);\r
      // Put the new leaves at the beginning of the list.\r
      sorted.addAll(0, leaves);\r
    }\r
    return sorted;\r
  }\r
\r
  // Return the set of nodes that have no children. Pretend\r
  // the nodes in the exclude list are not present.\r
  public Set<Node> leaves(Collection<Node> exclude)\r
  {\r
    Set<Node> leaves=new HashSet<Node>();\r
    for(Node parent : children.keySet())\r
    {\r
      if(exclude.contains(parent))\r
      {\r
        continue;\r
      }\r
      // If the children of parent are a subset of the exclude set,\r
      // then parent is a leaf.\r
      if(exclude.containsAll(children(parent)))\r
      {\r
        leaves.add(parent);\r
      }\r
    }\r
    return leaves;\r
  }\r
\r
  // Return the set of nodes that have no children.\r
  public Set<Node> leaves()\r
  {\r
    Set<Node> leaves=new HashSet<Node>();\r
    for(Node parent : children.keySet())\r
    {\r
      if( children(parent).isEmpty())\r
      {\r
        leaves.add(parent);\r
      }\r
    }\r
    return leaves;\r
  }\r
}\r