package dfatool.strategy.graph;

import java.io.UnsupportedEncodingException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import dfatool.parser.ParseException;
import dfatool.util.Pair;

public class TarjanAlgorithm {
	
	List<TarjanNode> nodes;
	int i;
	SpanningTree spt;
	
	public TarjanAlgorithm() throws UnsupportedEncodingException, ParseException{
		nodes = new ArrayList<TarjanNode>();
	}
	
	private void createTarjanTree() throws UnsupportedEncodingException, ParseException {
		IGraph graph = CommunicationGraph.getInstance().getGraph();
		INode root = pickRoot(graph);
		spt = new SpanningTree(root);
		posOrder(spt.getRoot());
	}
	
	private INode pickRoot(IGraph graph){
		Iterator<INode> iterator = graph.getNodes().iterator();
		return iterator.hasNext() ? iterator.next() : null;
	}

	private void posOrder(TarjanNode node) {
		for(TarjanNode tn : node.getTreeConnections()){
			posOrder(tn);
		}
		node.setNumber(i);
		nodes.add(node);
		i++;
	}
	
	public List<Bridge> getBridges(){
		try {
			createTarjanTree();
		} catch (UnsupportedEncodingException | ParseException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		List<Bridge> bridges = new ArrayList<Bridge>();
		for(TarjanNode node : nodes){
			node.setND(calcNd(node));
			node.setL(calcL(node));
			node.setH(calcH(node));
			for(TarjanNode target : node.getTreeConnections()){
				System.out.println("Target: "+target.getH());
				if((target.getH() == target.getNumber()) ){
					bridges.add(new Bridge(node.getIdentifier(),target.getIdentifier()));
					System.out.println("Brigde:" + node.getIdentifier() +" - "+ target.getIdentifier());
				}else{
					System.out.println("Not a bridge!");
				}
			}
		}
		return bridges;
	}
	
	private int calcNd(TarjanNode node){
		int ND = 1;
		for(TarjanNode tn : node.getTreeConnections()){
			ND += tn.getND();
		}
		return ND;
	}
	
	private int calcL(TarjanNode node){
		int L =  node.getNumber() - node.getND();
		for(TarjanNode tn : node.getTreeConnections()){
			L = min(L,tn.getL());
		}
		for(TarjanNode tn : node.getNonTreeConnections()){
			L = min(L,tn.getNumber());
		}
		return L;
	}
	
	private int calcH(TarjanNode node){
		int H =  node.getNumber();
		for(TarjanNode tn : node.getTreeConnections()){
			H = max(H,tn.getH());
		}
		for(TarjanNode tn : node.getNonTreeConnections()){
			H = max(H,tn.getNumber());
		}
		return H;
	}

	private int min(int a, int b){
		return a < b ? a : b;
	}
	
	private int max(int a, int b){
		return a > b ? a : b;
	}

	

	// create derected rooted tree;
	// number vertices
	// for v from 1 to V
	//     ND(v) = 1 + Somatorio dos NDs dos descendentes --
	// 	   L(v) = minimum(S(v))
	// 	   S(v) --> decendentes e descedentes que geram ciclos passando por ciclo 
	//	   H(v) = maximum(S(v))
	
	void calculateND(){
		
	}

	public static void main(String[] args) {
		try {
			TarjanAlgorithm ta = new TarjanAlgorithm();
			ta.getBridges();
			for(TarjanNode tn : ta.nodes){
				System.out.println(tn);
			}
		} catch (UnsupportedEncodingException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (ParseException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
			
	}
	
	public class Bridge extends Pair<NodeIdentifier,NodeIdentifier>{

		public Bridge(NodeIdentifier fst, NodeIdentifier snd) {
			super(fst, snd);
		}
		
		@Override
		public String toString() {
			return getFst().toString()+" - "+getSnd();
		}
		
	}
}
