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     */
013    package org.jikesrvm.compilers.opt.util;
014    
015    import java.util.ArrayList;
016    import java.util.Enumeration;
017    import 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     */
027    public 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    }