import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class Graph {
	// Rather than making an algorithm to reverse vertices, each graph maintains both
	// the normal and reverse versions of itself.
	private Map<Integer, Vertex> vertices;
	private Map<Integer, Vertex> reversedVertices;
	
	// List of the number of nodes found in each SCC
	List<Integer> sccSizes;
	
	// Variable to hold the running size of the current SCC
	int components;
	
	// List of vertices in the order they complete in a DFS pass on the reversed graph G
	Stack<Vertex> finishingTimes;
	
	
	/**
	 * 
	 * @param vertices
	 */
	public Graph(Map<Integer,Vertex> vertices, Map<Integer,Vertex> reversedVertices) {
		this.vertices = vertices;
		this.reversedVertices = reversedVertices;
		sccSizes = new ArrayList<Integer>();
		finishingTimes = new Stack<Vertex>();
	}
	
	/**
	 *  Constructs a graph directly from a text file (format specified in assignment)
	 *  
	 * @param filePath a string with the full filePath with digraph representation (see assignment for spec)
	 * @throws IOException
	 */
	public Graph(String filePath) throws IOException {
		// Both normal and reversed graphs will be constructed
		Map<Integer, Vertex> vertices = new HashMap<Integer, Vertex>();
		Map<Integer, Vertex> reversedVertices = new HashMap<Integer, Vertex>();
		
		// Open necessary objects to read file contents
		FileReader fileReader = new FileReader(filePath);
		BufferedReader bufferedReader = new BufferedReader(fileReader);
		
		String line = bufferedReader.readLine();
		
		while(line != null) {
			// Split each line into head and tail
			String[] edge = line.split(" ");
			int head = Integer.parseInt(edge[0]);
			int tail = Integer.parseInt(edge[1]);
			
			// In the reversed graph, the head and tail are switched
			int headReversed = Integer.parseInt(edge[1]);
			int tailReversed = Integer.parseInt(edge[0]);
			
			// For both head and tail in normal and reversed graphs, if head or tail is not already a vertex
			// add it to the graph.
			if(!vertices.containsKey(head)) {
				Vertex v = new Vertex(head);
				vertices.put(head, v);
			}
			if(!reversedVertices.containsKey(headReversed)) {
				Vertex vR = new Vertex(headReversed);
				reversedVertices.put(headReversed, vR);
			}
			if(!vertices.containsKey(tail)) {
				Vertex v2 = new Vertex(tail);
				vertices.put(tail, v2);
			}
			if(!reversedVertices.containsKey(tailReversed)) {
				Vertex v2R = new Vertex(tailReversed);
				reversedVertices.put(tailReversed, v2R);
			}
			
			//  Add the tail to the list of adjacent nodes for the head (construct the digraph connections)
			vertices.get(head).addAdjacentNode(vertices.get(tail));
			reversedVertices.get(headReversed).addAdjacentNode(reversedVertices.get(tailReversed));
			
			line = bufferedReader.readLine(); // get the next line
		} 
		bufferedReader.close(); // clean up
		
		// Finally, set the graph
		this.vertices = vertices;
		this.reversedVertices = reversedVertices;
		sccSizes = new ArrayList<Integer>();
		finishingTimes = new Stack<Vertex>();
	}
	
	/**
	 * 
	 * @return
	 */
	public Map<Integer, Vertex> getVertices() {
		return vertices;
	}
	
	/**
	 * 
	 * @param visited
	 */
	public void setAllVisited(boolean visited) {
		for(Vertex n : this.getVertices().values()) {
			n.setVisited(false);
		}
	}
	
	public void setReversedGraph(Map<Integer, Vertex> nodesReversed) {
		this.reversedVertices = nodesReversed;
	}
	
	public Map<Integer, Vertex> getReversedVertices() {
		return this.reversedVertices;
	}
	
	public Stack<Vertex> depthFirstSearchLoop() {
		for(Vertex v : this.getVertices().values()) {
			if(!v.isVisited()) {
				depthFirstSearch(v);
			}
		}
		return this.finishingTimes;
	}
	
	public void depthFirstSearchLoop(Stack<Vertex> finishingTimes) {
		Vertex v;
		while(!finishingTimes.isEmpty()) {
			v = finishingTimes.pop();
			
			// TODO correct bug, fixed, but finishingTimes come in with references to nodes
			// on reversed graphs. Have to convert to normal graph here
			v = this.getVertices().get(v.getValue());
			if(!v.isVisited()) {
				components = 1;
				this.depthFirstSearch(v);
				sccSizes.add(components);
			}
		}	
	}
	
	/**
	 * 
	 * @param g
	 * @param v
	 */
	public void depthFirstSearch(Vertex v) {
		v.setVisited(true);
		for(Vertex adjacentVertex : v.getAdjacentVertices()) {
			if(!adjacentVertex.isVisited()) {
				components++;
				this.depthFirstSearch(adjacentVertex);
			}
		}
		finishingTimes.push(v);
	}
	
	/**
	 * Returns a sorted list (ascending order) with size equal to the number of strongly connected components 
	 * (SCCs) in the directed graph (digraph) g. The value of each element is the number of vertices in the 
	 * respective SCC.
	 * 
	 * @param g
	 * @return
	 */
	public List<Integer> stronglyConnectedComponents() {
		
		Graph gReversed = new Graph(this.reversedVertices, this.vertices);

		Stack<Vertex> finishingTimes = gReversed.depthFirstSearchLoop();
		
		gReversed.setAllVisited(false);
		// This line fixed bug... Should be using a stack, not a queue, which is what unreversed list does
		this.depthFirstSearchLoop(finishingTimes);
		
		Collections.sort(sccSizes);
		return sccSizes;
	}
}