import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;


public class LongestPath {
	
	Map<Object, Object> predMap;
	
	
	public static void main(String[] args) {
	    DAG g = new DAG();
	    g.add(new ArcoOrdinato("a","b",new Integer(1)));
	    g.add(new ArcoOrdinato("a","c",new Integer(2)));
	    g.add(new ArcoOrdinato("a","e",new Integer(3)));
	    g.add(new ArcoOrdinato("c","d",new Integer(4)));
	    g.add(new ArcoOrdinato("c","e",new Integer(2)));
	    g.add(new ArcoOrdinato("b","d",new Integer(3)));

	    System.out.println(g);
	    
	    LongestPath lg = new LongestPath();
	    
	    Integer maxDist = lg.computeLongestPathValue(g,"a","d");
	    List<Object> path = lg.computeLongestPath(g, "a", "d");
	    
	    System.out.println("cammino "+path);
	    System.out.println("distanza "+maxDist);
	    
	}

	/**
	 * Calcola il valore della distanza massima dalla sorgente alla destinazione
	 * 
	 * @param g DAG su cui si vuole calcolare la distanza massima
	 * @param source sorgente
	 * @param sink destinazione
	 * @return distanza massima dalla sorgente alla destinazione
	 */
	public Integer computeLongestPathValue(DAG g, Object source,
			Object sink) {
		Map<Object,Integer> sValues = computeSValues(g,source);
		return sValues.get(sink);
		
	}
	
	/**
	 * Calcola il cammino piu' lungo dalla sorgente alla destinazione
	 * 
	 * @param g DAG su cui si vuole calcolare il cammino piu' lungo
	 * @param source sorgente 
	 * @param sink destinazione
	 * @return cammino piu' lungo dalla sorgente alla destinazione
	 */
	public List<Object> computeLongestPath(DAG g, Object source,
			Object sink) {
		System.out.println("metodo da implementare");
		return null;
		
	}
	
	/**
	 * Calcolo i valori s e la mappa dei predecessori per il DAG g a partire dalla sorgente source
	 * 
	 * @param g DAG per cui voglio calcolare i valori S
	 * @param source sorgente rispetto a cui calcolo i valori S
	 * @return una mappa da nodi ad interi che rappresenta i valori S di ciascun nodo 
	 */
	public Map<Object, Integer> computeSValues(DAG g, Object source) {
		
		//creo la mappa dei predecessori
		predMap = new HashMap<Object, Object>();
		
		//calcolo un ordine topologico del DAG a partire dalla sorgente
		List<Object> order = getTopologicalOrder(g, source);
		System.out.println(order);
		
		//inizializzo tutti i valori S dei nodi in order a 0
		Map<Object, Integer> sValues = resetSValues(order);
		System.out.println(sValues);
		
		//Calcolare i valori s di tutti i nodi presenti nell'ordine
		//aggiornare la predmap in maniera coerente
		System.out.println("Codice mancante");	


		System.out.println(sValues);
		return sValues;
	}

	/**
	 * inizializza a zero tutti i valori S dei nodi
	 * facenti parte dell'ordine passato come parametro
	 * 
	 * @param order ordine topologico contente i nodi da inizializzare
	 * @return una mappa da ogetti a sValues inizializzata a zero contenente tutti i 
	 * nodi nell'ordine topologico
	 */
	public Map<Object, Integer> resetSValues(List<Object> order) {
		Map<Object,Integer> sValues = new HashMap<Object, Integer>();
		for (Iterator iterator = order.iterator(); iterator.hasNext();) {
			Object node = iterator.next();
			sValues.put(node,0);
		}
		return sValues;
	}

	/**
	 * Ritorna un ordine topologico del DAG,
	 * con la sorgente come primo nodo
	 * 
	 * @param g DAG di cui calcolo l'ordine topologico
	 * @param source sorgente da cui parte l'ordine topologico
	 * @return una lista di nodi che rappresenta l'ordine topologico a partire dalla sorgente
	 */
	public List<Object> getTopologicalOrder(DAG g, Object source) {
		List<Object> order = g.getTopologicalOrder();	
		System.out.println("Order "+order);
		List<Object> res = new LinkedList<Object>();
		boolean done = false;
		Iterator it = order.iterator();
		for (;it.hasNext()&&!done;){
		  Object cn = it.next();
		  if (cn.equals(source)){
		    res.add(cn);
		    done = true;
		  }
		}
		
		for (;it.hasNext();){
		  Object nn = it.next();
		  res.add(nn);
		}
		System.out.println("res "+res);
		
		return res;
	}
}