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.Enumeration;
016    import java.util.HashSet;
017    import java.util.NoSuchElementException;
018    import java.util.Set;
019    
020    
021    public final class DepthFirstEnumerator implements Enumeration<GraphNode> {
022      private final Stack<GraphNode> stack;
023      private final Set<GraphNode> visited;
024    
025      public DepthFirstEnumerator(GraphNode start) {
026        stack = new Stack<GraphNode>();
027        stack.push(start);
028        visited = new HashSet<GraphNode>();
029      }
030    
031      @Override
032      public boolean hasMoreElements() {
033        if (stack == null) {
034          return false;
035        }
036    
037        for (GraphNode node : stack) {
038          if (notVisited(node)) {
039            return true;
040          }
041        }
042        return false;
043      }
044    
045      @Override
046      public GraphNode nextElement() {
047        if (stack == null) {
048          throw new NoSuchElementException("DepthFirstEnumerator");
049        }
050        while (!stack.isEmpty()) {
051          GraphNode node = stack.pop();
052          if (notVisited(node)) {
053            for (Enumeration<GraphNode> e = node.outNodes(); e.hasMoreElements();) {
054              GraphNode n = e.nextElement();
055              if (n != null) {
056                stack.push(n);
057              }
058            }
059            visited.add(node);
060            return node;
061          }
062        }
063        throw new NoSuchElementException("DepthFirstEnumerator");
064      }
065    
066      private boolean notVisited(GraphNode node) {
067        return !visited.contains(node);
068      }
069    
070    }