package javakurs.musterloesung.uebung09.aufgabe1;

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

import javakurs.musterloesung.uebung08.DfsGraphVisitor;
import javakurs.musterloesung.uebung08.DirectedGraphBase;
import javakurs.musterloesung.uebung08.Edge;
import javakurs.musterloesung.uebung08.VertexPropertyMap;

/**
 * {@link TarjanVisitor} implements the {@link DfsGraphVisitor} interface for a
 * visitor identifying the SCCs of a graph using depth-first search.
 *
 * @param <EdgeInfo>
 *          the kind of edge info used in this graph
 *
 * @author Bernd Kiefer, DFKI
 * @author Joerg Steffen, DFKI
 * @version $Id: TarjanVisitor.java,v 1.3 2011/01/21 08:38:08 steffen Exp $
 */
public class TarjanVisitor<EdgeInfo>
    implements DfsGraphVisitor<EdgeInfo> {

  /**
   * Contains the discovery time for each vertex.
   */
  private VertexPropertyMap<Integer> _discovery;

  /**
   * Contains for each vertex the lowest discovery time of a vertex reachable
   * from it.
   */
  private VertexPropertyMap<Integer> _low;

  /**
   * Contains the vertices currently discovered but not finished yet
   */
  private Stack<Integer> _vertexStack;

  /**
   * Contains the SCCs after the visitor has finished traversing the graph.
   */
  private List<List<Integer>> _components;

  /**
   * Contains the time counter that is increased during DFS.
   */
  private int _time;


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

    // nothing to do here
  }


  /**
   * Returns the strongly connected components after the visitor has traversed
   * the graph.
   *
   * @return a list of SCCs represented as lists of integers
   */
  public List<List<Integer>> getSCCs() {

    return _components;
  }


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

    // do the initialization if required
    if (_components == null) {
      _discovery = new VertexPropertyMap<Integer>(g);
      _low = new VertexPropertyMap<Integer>(g);
      _vertexStack = new Stack<Integer>();
      _components = new ArrayList<List<Integer>>();
      _time = 0;
    }
  }


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

    ++_time;
    // use _low to detect if a vertex is still in the queue, see later
    _low.put(v, _time);
    _discovery.put(v, _time);
    _vertexStack.push(v);
    System.out.println(
      "discovered " + g.getPropertyMap("names").get(v) + " at " + _low.get(v));
  }


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

    // nothing to do here
  }


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

    // if the target is the root of another SCC and has been popped already,
    // it's low value would be set to null again, so we have to check
    int endVertex = e.getEndVertex();
    if (_low.get(endVertex) != null) {
      int startVertex = e.getStartVertex();
      _low.put(startVertex,
        Math.min(_low.get(startVertex), _low.get(endVertex)));
    }
  }


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

    int endVertex = e.getEndVertex();
    // is endVertex part of another SCC?
    if (_low.get(endVertex) != null) {
      int startVertex = e.getStartVertex();
      _low.put(startVertex,
        Math.min(_low.get(startVertex), _low.get(endVertex)));
    }
  }


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

    // do the computation of the lowest reachable vertex now
    System.out.println(
      "finished " + g.getPropertyMap("names").get(v) + " at " + _low.get(v));
    int low = _low.get(v);
    if (low == _discovery.get(v)) {
      System.out.println(
        "found new SCC with root " + g.getPropertyMap("names").get(v));
      // all vertices on top of v in the stack and v itself belong to the SCC
      List<Integer> component = new ArrayList<Integer>();
      int nextVertex = -1;
      do {
        nextVertex = _vertexStack.pop();
        component.add(nextVertex);
        // we use _low to detect if a vertex is still in the queue
        _low.remove(nextVertex);
      } while (nextVertex != v);
      _components.add(component);
    }
  }
}
