import java.util.HashMap;
import java.util.Map.Entry;

public class Algo{

	private HashMap<String,Ville> villes;

	public Algo(){

		villes = new HashMap<String,Ville>();

		Ville nice = new Ville("Nice");
		nice.addDistance("Angers",999);
		nice.addDistance("Bordeaux",844);
		nice.addDistance("Clermond",620);
		nice.addDistance("Paris",950);
		nice.addDistance("Strasbourg",842);
		nice.addDistance("Montpellier",345);
		villes.put(nice.getNom(),nice);

		Ville angers = new Ville("Angers");
		angers.addDistance("Nice",999);
		angers.addDistance("Bordeaux",335);
		angers.addDistance("Clermond",402);
		angers.addDistance("Paris",303);
		angers.addDistance("Strasbourg",742);
		angers.addDistance("Montpellier",692);
		villes.put(angers.getNom(),angers);

		Ville bordeaux = new Ville("Bordeaux");
		bordeaux.addDistance("Nice",844);
		bordeaux.addDistance("Angers",335);
		bordeaux.addDistance("Clermond",369);
		bordeaux.addDistance("Paris",561);
		bordeaux.addDistance("Strasbourg",958);
		bordeaux.addDistance("Montpellier",499);
		villes.put(bordeaux.getNom(),bordeaux);

		Ville clermond = new Ville("Clermond");
		clermond.addDistance("Nice",620);
		clermond.addDistance("Angers",102);
		clermond.addDistance("Bordeaux",369);
		clermond.addDistance("Paris",425);
		clermond.addDistance("Strasbourg",574);
		clermond.addDistance("Montpellier",367);
		villes.put(clermond.getNom(), clermond);

		Ville paris = new Ville("Paris");
		paris.addDistance("Nice",950);
		paris.addDistance("Angers",303);
		paris.addDistance("Bordeaux",561);
		paris.addDistance("Clermond",425);
		paris.addDistance("Strasbourg",448);
		paris.addDistance("Montpellier",763);
		villes.put(paris.getNom(),paris);

		Ville strasbourg = new Ville("Strasbourg");
		strasbourg.addDistance("Nice",842);
		strasbourg.addDistance("Angers",742);
		strasbourg.addDistance("Bordeaux",958);
		strasbourg.addDistance("Clermond",574);
		strasbourg.addDistance("Paris",448);
		strasbourg.addDistance("Montpellier",727);
		villes.put(strasbourg.getNom(),strasbourg);

		Ville montpellier = new Ville("Montpellier");
		montpellier.addDistance("Nice",345);
		montpellier.addDistance("Angers",692);
		montpellier.addDistance("Bordeaux",499);
		montpellier.addDistance("Clermond",367);
		montpellier.addDistance("Paris",763);
		montpellier.addDistance("Strasbourg",727);
		villes.put(montpellier.getNom(),montpellier);
	}

	public HashMap<String,Ville> getVilles(){
		return this.villes;
	}

	public int displayTravelingSalesmanV1(String nom, String arrive, HashMap<String,Ville> villesRestantes){

		int min = Integer.MAX_VALUE;
		String nextVille = null;
		int distance;

		for(Entry<String, Ville> entry : villesRestantes.entrySet()) {
		    Ville value = entry.getValue();
		   	distance = value.getDistanceTo(nom);
			if(distance > 0 && distance < min && (!arrive.equals(value.getNom()) || villesRestantes.size() <= 1)){
				min = distance;
				nextVille = value.getNom();
			}
		}


		if(nextVille != null){
			villesRestantes.remove(nextVille);
			System.out.println(nom + " -> " + nextVille + " = " + min + "km");
			return min + displayTravelingSalesmanV1(nextVille,arrive,villesRestantes);
		}
		return 0;
	}

	int[][] suites = new int[7][7];

	public int displayTravelingSalesmanV2(int i, int j){


	}

	public static void main(String[] args){
		Algo algo = new Algo();
		int distanceTotale = algo.displayTravelingSalesmanV1("Paris","Paris", algo.getVilles());

		System.out.println("Distance Total parcourue: " + distanceTotale + "km");
	}

}