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.Enumeration;
016import java.util.HashSet;
017import java.util.NoSuchElementException;
018import java.util.Set;
019
020
021public 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}