package javakurs.musterloesung.uebung08;

import java.util.ArrayList;
import java.util.List;

/**
 * {@link TopoOrderVisitor} implements the {@link DfsGraphVisitor} interface to
 * calculate the topological order of the vertices of a graph.
 *
 * @param <EdgeInfo>
 *          the kind of information assigned to the edges of the traversed graph
 *
 * @author Joerg Steffen, DFKI
 * @version $Id: TopoOrderVisitor.java,v 1.2 2011/01/12 16:30:18 steffen Exp $
 */
public class TopoOrderVisitor<EdgeInfo>
     implements DfsGraphVisitor<EdgeInfo> {

  /**
   * Here we collect the sorted vertices.
   */
  private List<Integer> sortedVertices;


  /**
   * This creates a new instance of {@link TopoOrderVisitor}.
   */
  public TopoOrderVisitor() {

    this.sortedVertices = new ArrayList<Integer>();
  }


  /**
   * This returns the topological sorted vertices after the visitor is finished.
   *
   * @return the list of topological sorted vertices
   */
  public List<Integer> getSortedVertices() {

    return this.sortedVertices;
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public void startVertex(int v, DirectedGraphBase<EdgeInfo> g) {

    // nothing to do
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public void discoverVertex(int v, DirectedGraphBase<EdgeInfo> g) {

    // nothing to do
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public void finishVertex(int v, DirectedGraphBase<EdgeInfo> g) {

    // add a finished vertex at the start of the list
    this.sortedVertices.add(0, v);
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public void treeEdgeBefore(Edge<EdgeInfo> e, DirectedGraphBase<EdgeInfo> g) {

    // nothing to do
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public void treeEdgeAfter(Edge<EdgeInfo> e, DirectedGraphBase<EdgeInfo> g) {

    // nothing to do
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public void nonTreeEdge(Edge<EdgeInfo> e, DirectedGraphBase<EdgeInfo> g) {

    // nothing to do
  }
}
