import java.util.*;
import java.lang.Math.*;
/**
 * Write a description of class Luchthaven here.
 * 
 * @author Arne Vanhoof
 * @version (a version number or a date)
 */
public class Luchthaven
{
private int[] XCoordArray;
private int[] YCoordArray;
private int[] VerbindingenA;
private int[] VerbindingenB;
private ArrayList<Double> Afstandenlijst;
private ArrayList<Integer> Route;
private ArrayList<Double> RouteAfstand;


public Luchthaven() {
    XCoordArray = new int[8];
    YCoordArray = new int[8];
    VerbindingenA = new int[9];
    VerbindingenB = new int[9];
    Afstandenlijst = new ArrayList<Double>();
    Route = new ArrayList<Integer>();
    RouteAfstand = new ArrayList<Double>();
    
    XCoordArray[0] = 10;
    YCoordArray[0] = 29;
    
    XCoordArray[1] = 25;
    YCoordArray[1] = 46;
    
    XCoordArray[2] = 54;
    YCoordArray[2] = 46;
    
    XCoordArray[3] = 83;
    YCoordArray[3] = 46;
    
    XCoordArray[4] = 32;
    YCoordArray[4] = 10;
    
    XCoordArray[5] = 47;
    YCoordArray[5] = 10;
    
    XCoordArray[6] = 76;
    YCoordArray[6] = 10;
    
    XCoordArray[7] = 91;
    YCoordArray[7] = 26;

    VerbindingenA[0] = 1;
    VerbindingenB[0] = 2;

    VerbindingenA[1] = 1;
    VerbindingenB[1] = 5;
    
    VerbindingenA[2] = 2;
    VerbindingenB[2] = 3;
    
    VerbindingenA[3] = 2;
    VerbindingenB[3] = 5;
    
    VerbindingenA[4] = 3;
    VerbindingenB[4] = 4;
   
    VerbindingenA[5] = 3;
    VerbindingenB[5] = 6;
    
    VerbindingenA[6] = 5;
    VerbindingenB[6] = 6;
    
    VerbindingenA[7] = 6;
    VerbindingenB[7] = 7;

    VerbindingenA[8] = 7;
    VerbindingenB[8] = 8;
}


// We controleren met een boolean of de 2 opgegeven steden is verbinding staan met elkaar
public boolean Verbinding(int stad1, int stad2) {
    boolean waarde = false;
    for(int i = 0; i < VerbindingenA.length; i++) {
        if ( ((VerbindingenA[i] == stad1) && (VerbindingenB[i] == stad2)) || ((VerbindingenB[i] == stad1) && (VerbindingenA[i] == stad2)) ) {
            waarde = true;
        }
    }
    return waarde;
}

public boolean ZoekOplossing(int stad1, int stad2) {
    if (Verbinding(stad1, stad2)){
        //blablabla...
        System.out.println("wii onze steden staan in direct contact");
        Route.add(stad2);
        RouteAfstand.add(BerekenAfstand(stad1,stad2));
        return true;
    }
    else {
        //Nu moeten we gaan zoeken met welke steden stad 1 in contact staat en daarvan de kortste route kiezen.
        int stad3;
        if(BerekenKortste(stad1, stad2) != 0) {
            stad3 = BerekenKortste(stad1, stad2);//We stellen de nieuwe stad in
            Route.add(stad3);
            RouteAfstand.add(BerekenAfstand(stad1,stad3));
            System.out.println("de stad die het kortste licht is: " + stad3);
            if ( ZoekOplossing(stad3,stad2) ) {
                return true;
            }
            VerwijderLaatste();
        }
        return false;
    }
}

public void VerwijderLaatste() {
    int plaats = (Route.size() - 1);
    System.out.println("We verwijderen de laatste in de lijst: " + Route.get(plaats) + "wat staat op " + plaats);
    Route.remove(plaats);
    RouteAfstand.remove(plaats-1);// in onze RouteAfstand staat er eentje minder dan in de gewone route, want in de route array werd de beginpositie toegevoegd
}

public int BerekenKortste(int stad1, int stad2){
    ArrayList<Integer> Stedenlijst = new ArrayList<Integer>();
        //Nu moeten we gaan zoeken met welke steden stad1 in contact staat en daarvan de kortste route kiezen.
        for(int i = 0; i < VerbindingenA.length; i++) {
            if (VerbindingenA[i] == stad1 && !Route.contains(VerbindingenB[i])) {
                Stedenlijst.add( VerbindingenB[i] );
            }
            if (VerbindingenB[i] == stad1 && !Route.contains(VerbindingenA[i])) {
                Stedenlijst.add( VerbindingenA[i] );
            }
        }
        System.out.println("Onze steden stonden niet in direct contact. Maar stad: " + stad1 + " staat in contact met " + Stedenlijst.size() + " steden.");
        for(int i = 0; i < Stedenlijst.size(); i++) {
            System.out.println(" Stad : " + stad1 + " staat in contact met stad : " + Stedenlijst.get(i));
        }
        // Nu moeten we alle afstanden gaan zoeken tussen stad1 en zijn verbindingen. Deze slaan we eveneens op in een arraylist
        if(Stedenlijst.size() == 0) {
            System.out.println("vanaf hier zitten we vast, onze stad heeft geen verbindingen meer, we moeten teruggaan");
            return 0;
        }
        else if( Stedenlijst.size() == 1) {
            System.out.println("Onze stad staat maar met 1 stad in verbinding, nl stad: " + Stedenlijst.get(0));
            return Stedenlijst.get(0);//Onze stad staat maar met 1 stad in verbinding dus dit is sowieso de kortste!
        }
        else {// Er is maar dan 1 stad dus moeten we de afstanden gaan vergelijken.
            for(int i = 0; i < Stedenlijst.size(); i++) {
                Afstandenlijst.add(BerekenAfstand(Stedenlijst.get(i), stad2));
                System.out.println(" Stad : " + stad1 + " staat in contact met stad : " + Stedenlijst.get(i) + " en de afstand is : " + Afstandenlijst.get(i));
            }
        //De bijhorende steden staan nu in de Stedenlijst ArrayList en de bijhorende afstanden in de Afstandenlijst Arraylist, we zoeken nu de kortste
        return Stedenlijst.get(Minimum());
    }
}

public double BerekenAfstand(int stad1, int stad2) {
    double afstand;
    int stad1X = XCoordArray[stad1-1];
    int stad1Y = YCoordArray[stad1-1];
    int stad2X = XCoordArray[stad2-1];
    int stad2Y = YCoordArray[stad2-1];    
    afstand = Math.sqrt(((stad2X - stad1X) * (stad2X - stad1X)) + ((stad2Y - stad1Y) * (stad2Y - stad1Y)));
    return afstand;
}

public int Minimum() {
    if(Afstandenlijst.size() == 1){
        Afstandenlijst.clear();
        return 0;//Het minimum bevindt zich dan op de 0de positie in de array, dus de stad ook.
    }
    else {
        double minimum = Afstandenlijst.get(0);   // we zetten de eerste waarde als minimum
        int arraywaarde = 0; // Het minimum bevindt zich momenteel op arraywaarde 0
        for (int i=1; i<Afstandenlijst.size(); i++) {
            if (Afstandenlijst.get(i) < minimum) {
                minimum = Afstandenlijst.get(i);   // Nieuwe minimum wordt ingesteld.
                arraywaarde = i; // Nieuwe arraywaarde wordt ingesteld.
            }
        }
        Afstandenlijst.clear();//Zodat de waarden er voor de volgende berekening niet meer instaan
        return arraywaarde;
    }
}

public void ControleerOplossing(int stad1, int stad2) {
    Route.add(stad1);
    if(ZoekOplossing(stad1, stad2)) {
        System.out.println("Enter start city (1-8): " + stad1);
        System.out.println("Enter destination (1-8): " + stad2);
        print(stad1,stad2);
        Route.clear();
        RouteAfstand.clear();
    }
    else {
        System.out.println("Sorry, maar er is iets fout gelopen");
    }
}
 

public void print(int stad1, int stad2){
    double afstand = 0;
    System.out.print("Route: ");
    for(int i =0; i < Route.size(); i++) {
        System.out.print( Route.get(i) + " ," );
    }
    System.out.print("\n");
    System.out.print("Route-afstand: ");
    for(int i =0; i < RouteAfstand.size(); i++) {
        System.out.print( RouteAfstand.get(i) + " ," );
    }
    System.out.print("\n");
    System.out.print("Totale afstand:");
    
    for(int i =0; i < RouteAfstand.size(); i++) {
        afstand = afstand + RouteAfstand.get(i);
    }
    System.out.print( afstand );
    
}
}