import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
import java.util.Vector;

import ee.ut.kiho.aa.graaf.Graaf;
import ee.ut.kiho.aa.graaf.GraafiJoonistaja;
import ee.ut.kiho.aa.graaf.Kaar;
import ee.ut.kiho.aa.graaf.Tipp;

/**
 * Algoritmid ja andmestruktuurid
 * 2016/2017 õppeaasta sügissemester
 * Arvutipraktikum
 * rühm: inf1
 *
 * 12. praktikumi ülesanne: GTE_2-1 Eellaste seadmine
 *
 * @Author Reemet Ammer
 */

public class GTE2_4 {

	static void teePikkus(Graaf g, List<Integer> tee){
		//System.out.println(tee.size());
		int pikkus = 0;
		for (int i = 0; i < tee.size()-1; i++){
			Tipp t1 = g.tipp(tee.get(i)-1);
			Tipp t2 = g.tipp(tee.get(i+1)-1);
			Kaar k = g.kaar(t1, t2);
			pikkus += Integer.parseInt(k.nimi());
		}
		System.out.println("Pikkus on " + pikkus);
	}

	static void tee(Graaf g, int b){
		List<Integer> tee = new ArrayList<Integer>();

		//Alustatakse lõpptipust ja käiakse järjest läbi eellased kuni algustipuni, iga tipp salvestatakse listi
		Tipp tipp = g.tipp(b);
		tee.add(g.indeks(tipp)+1);
		while (tipp.väli("eellane") != null){
			tipp = g.tipp(Integer.parseInt(tipp.väli("eellane"))-1);
			tee.add(g.indeks(tipp)+1);
		}

		Collections.reverse(tee);
		System.out.println(tee);
		teePikkus(g,tee);
	}

	//Antud: graaf g ja tema kaks tippu t ja b
	//Tulemus: g tippudele lisatakse välju "eellane" ja "vaadeldud"
	//kui leidub tee tipust t tippu b, siis on see tee määratud tipuväljadega "eellane"
	//x.väli("eellane") on selle tipu number, kust tuleb tee tippu x
	static void eellased_teel(Graaf g, Tipp t, Tipp b){

		if (t == b){
			tee(g, g.indeks(b));
			return;
		}
		else t.seadaVäli("vaadeldud", "x");

		for (Tipp v : g.naabrid(t)){
			if (v.väli("vaadeldud") == null){
				v.seadaVäli("eellane", "" + (g.indeks(t)+1));
				eellased_teel(g,v,b);
			}
		}
		t.eemaldadaVäli("vaadeldud");
	}

	public static void main(String[] args) {

		Graaf g = new Graaf();
		String fNimi = "graafTeed.txt";
		g = Graaf.sisestadaTabelist(fNimi);

		//Algustipp ja lõpptipp on tähistatud alljärgnevate numbritega, kuid nende tegelikud indeksid on t-1 ja b-1
		int t = 1;
		int b = 12;

		//Leitakse tee tipust tähistusega t tippu tähistusega b
		eellased_teel(g, g.tipp(t-1), g.tipp(b-1));
		//tee(g, g.indeks(g.tipp(11)));


		new GraafiJoonistaja(fNimi);

	}

}