package dependentNodes.withoutDfs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Stack;

class Graph{
	private ArrayList<Project> nodes = new ArrayList<Project>();
	HashMap<String,Project> map = new HashMap<String, Project>();

	public Project getOrCreateNode(String name){
		if(!map.containsKey(name)){
			Project proj = new Project(name);
			map.put(name, proj);
			nodes.add(proj);
		}
		return map.get(name);
	}
	public ArrayList<Project> getNodes(){
		return this.nodes;
	}
	public void addEdge(String name1, String name2){
		Project p1 = getOrCreateNode(name1);
		Project p2 = getOrCreateNode(name2);
		p1.addChild(p2);

	}
}

enum State{
	BLANK,PARTIAL,COMPLETE;
}

class Project{
	private String name;
	private ArrayList<Project> children = new ArrayList<Project>();
	State state = State.BLANK;

	public Project(String name){
		this.name = name;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public ArrayList<Project> getChildren() {
		return children;
	}
	public void setChildren(ArrayList<Project> children) {
		this.children = children;
	}

	public void addChild(Project child){
		this.children.add(child);
	}
}

public class BuildOrderDfs {
	public Stack<Project> findBuildOrder(String[] projects, String [][] dependencies){
		Graph g = buildGraph(projects, dependencies);
		return buildOrder(g);
	}
	public Graph buildGraph(String [] projects, String [][] dependencies){
		Graph g = new Graph();
		for(String proj: projects)
			g.getOrCreateNode(proj);
		for (String [] dependency : dependencies){
			String proj1 = dependency[0];
			String proj2 = dependency[1];
			g.addEdge(proj1,proj2);
		}
		return g;
	}
	public Stack<Project> buildOrder(Graph g){
		//make a stack to hold the projects
		Stack<Project> stack = new Stack<Project>();
		ArrayList<Project> projects = g.getNodes();

		//dfs on the projects
		for (Project proj: projects){
			if(!DFS(proj,stack))
				return null;
		}
		return stack;
	}
	public boolean DFS(Project proj, Stack<Project> stack){
		//base case
		if(proj == null)
			return true;
		if(proj.state == State.COMPLETE)             //already visited. so no need to visit again!
			return true;
		//cycle is detected
		if(proj.state == State.PARTIAL)
			return false;
		proj.state = State.PARTIAL;
		ArrayList<Project> children = proj.getChildren();
		for (Project child : children){
			if(!DFS(child,stack))
				return false;                  //return false if any of the child has a cycle
		}
		proj.state = State.COMPLETE;           //this node is visited . hence mark is complete
		stack.push(proj);
		return true;

	}

	public static void main (String [] args){
		BuildOrderDfs obj = new BuildOrderDfs();
		String [] projects = new String[8];
		projects[0] = "a";
		projects[1] = "b";
		projects[2] = "c";
		projects[3] = "d";
		projects[4] = "e";
		projects[5] = "f";
		projects[6] = "g";
		projects[7] = "h";
		String [][] dependencies = new String[9][2];
		dependencies[0][0] = "f";
		dependencies[0][1] = "c";
		dependencies[1][0] = "c";
		dependencies[1][1] = "a";
		dependencies[2][0] = "a";
		dependencies[2][1] = "e";
		dependencies[3][0] = "f";
		dependencies[3][1] = "a";
		dependencies[4][0] = "f";
		dependencies[4][1] = "b";
		dependencies[5][0] = "b";
		dependencies[5][1] = "a";
		dependencies[6][0] = "b";
		dependencies[6][1] = "e";
		dependencies[7][0] = "b";
		dependencies[7][1] = "h";
		dependencies[8][0] = "d";
		dependencies[8][1] = "g";
		Stack<Project> stack = obj.findBuildOrder(projects, dependencies);
		while (!stack.isEmpty()){
			System.out.println("  "+stack.peek().getName());
			stack.pop();
		}
	}
}