001/*
002 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 *  This file is licensed to You under the Eclipse Public License (EPL);
005 *  You may not use this file except in compliance with the License. You
006 *  may obtain a copy of the License at
007 *
008 *      http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 *  See the COPYRIGHT.txt file distributed with this work for information
011 *  regarding copyright ownership.
012 */
013package org.jikesrvm.compilers.opt.util;
014
015import java.util.ArrayList;
016import java.util.Enumeration;
017import java.util.List;
018
019
020/**
021 * This class implements depth-first search over a Graph,
022 * return an enumeration of the nodes of the graph in order of
023 * increasing finishing time.  This class follows the outNodes of the
024 * graph nodes to define the graph, but this behavior can be changed
025 * by overriding the getConnected method.
026 */
027public class DFSenumerateByFinish extends Stack<GraphNode> implements Enumeration<GraphNode> {
028
029  /**
030   *  Construct a depth-first enumerator across all the nodes of a
031   * graph.
032   *
033   * @param net the graph whose nodes to enumerate
034   */
035  protected DFSenumerateByFinish(Graph net) {
036    this(net, net.enumerateNodes());
037  }
038
039  /**
040   * Construct a depth-first enumerator across the (possibly
041   * improper) subset of nodes reachable from the nodes in the given
042   * enumeration.
043   *
044   * @param net the graph whose nodes to enumerate
045   * @param nodes the set of nodes from which to start searching
046   */
047  public DFSenumerateByFinish(Graph net, Enumeration<GraphNode> nodes) {
048    e = nodes;
049    net.compactNodeNumbering();
050    info = new ArrayList<Enumeration<GraphNode>>(net.numberOfNodes() + 1);
051    //  info = new java.util.HashMap( net.numberOfNodes() );
052    if (e.hasMoreElements()) {
053      theNextElement = e.nextElement();
054    }
055  }
056
057  /**
058   * While a depth-first enumeration is in progress, this field
059   * holds the current root node, i.e. the current bottom of the
060   * search stack (assuming stacks grow upward).  This is used
061   * primarily when constructing strongly connected components.
062   */
063  public GraphNode currentRoot;
064
065  /**
066   * Return whether there are any more nodes left to enumerate.
067   *
068   * @return true if there nodes left to enumerate.
069   */
070  @Override
071  public boolean hasMoreElements() {
072    return (!empty() || (theNextElement != null && info.get(theNextElement.getIndex()) == null));
073  }
074
075  /**
076   *  Find the next graph node in finishing time order.
077   *
078   *  @see #nextElement
079   *
080   *  @return the next graph node in finishing time order.
081   */
082  @Override
083  public GraphNode nextElement() {
084    if (empty()) {
085      GraphNode v = theNextElement;
086      currentRoot = theNextElement;
087      info.set(v.getIndex(), getConnected(v));
088      push(v);
089    }
090    recurse:
091    while (!empty()) {
092      GraphNode v = peek();
093      Enumeration<GraphNode> pendingChildren = info.get(v.getIndex());
094      for (Enumeration<GraphNode> e = pendingChildren; e.hasMoreElements();) {
095        GraphNode n = e.nextElement();
096        Enumeration<GraphNode> nChildren = info.get(n.getIndex());
097        if (nChildren == null) {
098          // found a new child: recurse to it.
099          info.set(n.getIndex(), getConnected(n));
100          push(n);
101          continue recurse;
102        }
103      }
104      // no more children to visit: finished this vertex
105      while (info.get(theNextElement.getIndex()) != null && e.hasMoreElements()) {
106        theNextElement = e.nextElement();
107      }
108      return pop();
109    }
110    return null;
111  }
112
113  /**
114   * the current next element in finishing time order
115   */
116  private GraphNode theNextElement;
117  /**
118   * an enumeration of all nodes to search from
119   */
120  private final Enumeration<GraphNode> e;
121  /**
122   * an enumeration of child nodes for each node being searched
123   */
124  private final List<Enumeration<GraphNode>> info;
125
126  /**
127   * get the out edges of a given node
128   *
129   * @param n the node of which to get the out edges
130   * @return the out edges
131   */
132  protected Enumeration<GraphNode> getConnected(GraphNode n) {
133    return n.outNodes();
134  }
135}