package com.github.dexecutor.executor.graph;
   
   import java.util.ArrayList;
   import java.util.Collection;
   
   import com.github.dexecutor.executor.graph.Graph.Node;
   
   /**
    * A {@code Validator} which does cyclic checks
   * @author Nadeem Mohammad
   *
   * @param <T>
   */
  public class CyclicValidator<T extends Comparable<T>> implements Validator<T> {
  
  	private Collection<Graph.Node<T>> processedNodes = new ArrayList<Graph.Node<T>>();
  	private Collection<Graph.Node<T>> onStackNodes = new ArrayList<Graph.Node<T>>();
  
  	public void validate(final Graph<T> graph) {
  		doProcess(graph.allNodes());
  	}
  
  	private void doProcess(final Collection<Graph.Node<T>> nodes) {
  		for (Graph.Node<T> node : nodes) {
  			detectCycle(node);
  		}
  	}
  
  	private void detectCycle(final Node<T> node) {
  		this.processedNodes.add(node);
  		this.onStackNodes.add(node);
  		doDepthFirstTraversal(node);
  		this.onStackNodes.remove(node);
  	}
  
  	private void doDepthFirstTraversal(final Node<T> node) {
  		for (Node<T> adjNode : node.getOutGoingNodes()) {
  			if (!isAlreadyProcessed(adjNode)) {
  				detectCycle(adjNode);
  			} else if (isOnStack(adjNode)) {
  				throw new IllegalArgumentException("Cycle Detected " + node + " With " + adjNode);
  			}
  		}
  	}
  
  	private boolean isAlreadyProcessed(final Node<T> node) {
  		return this.processedNodes.contains(node);
  	}
  
  	private boolean isOnStack(final Node<T> node) {
  		return this.onStackNodes.contains(node);
  	}
  }