package zadanie;

import java.io.IOException;
import java.nio.file.Paths;
import java.util.Scanner;

public class Main {

    // tablica przechowujaca nazwy miast
    private static String[] cities;

    // tablica przechowująca odległości do miast
    private static double[][] weights;
    private static double[][] points;

    // tablica przechowujaca informacje o tym czy miasto zostalo juz odwiedzone
    private static boolean[] visited;

    // przechowuje liczbe miast
    private static int citiesCount;



    // wypisuje miasto w postaci tabeli
    private static void printCitiesTable() {

        // wypisanie nowej linii i zrobienie odstepu na 10 znakow od lewej strony
        System.out.printf("\n");
        System.out.printf("%10s", " ");

        // wypisanie miast w kolumnach o szerokosci 10 znakow
        for(int j = 0; j < citiesCount; j++) {
            System.out.printf("%10s", cities[j]);
        }
        System.out.println("");

        // wypisanie miasta i odleglosci z niego do kazdego innego miasta
        for(int i = 0; i < citiesCount; i++) {
            System.out.printf("%10s", cities[i]);
            for(int j = 0; j < citiesCount; j++) {
                System.out.printf("%10.2f", weights[i][j]);
            }
            System.out.println("");
        }
    }

    // znajduje najkrotsza sciezke
    // zaczynajac od miasta podanego w parametrze from
    private static int getDistance(int from) {
        int beginning = from; // usaw poczatek na from
        int distance = 0;     // na start odleglosc 0

        // zacznamy z pewnego punktu wiec ten punkt startowy jest juz odiwedzony
        visited[from] = true; // Ustaw wybrany wierzchołek jako aktualny, oznacz go jako odwiedzony.



        System.out.print("\n\n"+cities[from]);

        // Znajdź ten spośród nieodwiedzonych wierzchołków, który jest połączony z aktualnym krawędzią o najmniejszej wadze.

        // ustaw nowy wierzcholem, jezeli zaczynamy z 0 to na 1, jezeli nie to na 0
        // dzieki temu program sie nie zapętli
        int newNode = (from == 0) ? 1 : 0;

        // pętla wyszukujacy najkrotsza trase z podanego punktu
        do {

            // dla wszystkich miast
            for (int i = 0; i < citiesCount; i++) {
                // jezeli bylo odwiedzone lub to jest miasto
                // z ktorego zaczynamy to je po pomin i przejdz
                // do kolejnej iteracji petli
                if (i == from || visited[i]) {
                    continue;
                }

                // jezeli odleglosc z miasta aktualnie ogladanego
                // jest mniejsza niz z miasta, ktore wybrano
                // jako kolejny punkt trasy
                // to znaczy, ze znaleziono nowe miasto
                // ktore powinno odwiedzic sie jako nastepne
                if (weights[from][i] <= weights[from][newNode]) {
                    // ustaw nowe miasto jako to przed chwila znalezione
                    newNode = i;
                }
            }

            // zsumuj odleglosc do kolejnego miasta
            distance += weights[from][newNode];

            // teraz from to miasto przed chwila znalezione
            // poniewaz od niego teraz bedzie wyszukiwane kolejne najblizsze
            from = newNode;

            // ustaw miasto jako odwiedzone
            visited[from] = true;

            // wypisz strzalke i nazwe kolejnego miasta
            System.out.print(" -> " + cities[from]);

            // sprawdz we wszystkich miastach
            for(int j = 0; j < citiesCount; j++) {
                // jezeli nie jest bylo odwiedzone
                if(!visited[j]) {
                    // ustaw nowe jako numer tego nie odwiedzonego
                    newNode = j;
                }
            }
        } while(visitedCount() != citiesCount); // powtarzaj petle dopoki wszystkie miasta nie zostana odwiedzone

        // wypisz strzalke i nazwe miasta poczatkowego zeby zamknac trase
        System.out.print(" -> " + cities[beginning]);

        // dodaj odleglosc z ostatniego miasta do pierwszego zeby zamknac trase
        distance += weights[from][beginning];

        // wypisz dlugosc trasy
        System.out.println("\nDystans " + distance + "km");


        // wyzeruj odwiedzenia miast
        for(int i = 0; i < citiesCount; i++) {
            visited[i] = false;
        }
        return distance;
    }

    // zwraca liczbe miast ktore zostaly juz odwiedzone
    public static int visitedCount() {
        int sum = 0;

        // przejdz przez tablice odwiedzeń miast
        for(boolean v : visited) {
            if(v) { // jezeli odwiedzone to zwieksz licznik odwiedzonych miast o jeden
                sum++;
            }
        }

        // zwroc liczbe odiwedzonych miast
        return sum;
    }


    // znajduje najkrotsza sciezke miedzy miastami
    public static int getShortestPath() {
        // na start dystanc na wartosc maksymalna, bedzie wyszukiwane
        // cokolwiek co jest mniejsze od tej wartosci i zapisywane w tej zmiennej
        // wiec w ostatecznosci tutaj bedzie najmniejsza odleglosc
        int distance = Integer.MAX_VALUE;

        // numer miasta do ktorego aktualnia byla najkrotsza sciezka
        int shortest = 0;

        // zmienna tymczasowa na przechowanie odleglosci
        int temp = 0;

        // przejdz przez wszystkie miasta
        for(int i = 0; i < citiesCount; i++) {

            // znajdz najkrotszy dystans z miasta o numerze i
            temp = getDistance(i);

            // jezeli temp jest mniejsze od wartosci w distance
            // to znaleziono nowa najkrotsza odleglosc
            if(temp < distance) {
                distance = temp; // zapisz najkrotsza odleglosc
                shortest = i;   // zapisz numer miasta z ktorego zaczac
                                // zeby otrzymac najkrtosza sciezke
            }
        }

        System.out.println("\n\nNajkrótsza ścieżka: ");
        return getDistance(shortest);
    }

    // wczytuje miasta zapisane w postaci tabeli z kilometrami
    // aktualnie ta funkcja nie jest uzywana, bo miasta mialy byc
    // zapisane w postaci wspolrzednych 2d
    public static void readFile(String name) throws IOException {
        Scanner fileReader = new Scanner(Paths.get(name), "UTF-8");

        // wczytuje liczbe miast
        citiesCount = fileReader.nextInt();

        System.out.println("Liczba miast: " + citiesCount);

        // rezerwuje tablice
        cities = new String[citiesCount];
        visited = new boolean[citiesCount];
        weights = new double [citiesCount][citiesCount];

        // wczytuje nazwy miast
        for(int i = 0; i < citiesCount; i++) {
            cities[i] = fileReader.next();
            System.out.println("Dodaje miasto: " + cities[i]);
        }

        // wczytuje kilometry z kadzego miasta do kazdego
        for(int i = 0; i < citiesCount; i++) {
            for(int j = 0; j < citiesCount; j++) {
                weights[i][j] = fileReader.nextInt();
            }
        }
    }

    // wczytuje miasta zapisane w postaci wspolrzednych 2d
    public static void readFile2(String name) throws IOException {
        Scanner fileReader = new Scanner(Paths.get(name), "UTF-8");

        // wczytaj ilosc miast
        citiesCount = fileReader.nextInt();

        // wypisuje ilosc nazw
        System.out.println("Liczba miast: " + citiesCount);

        // rezerwuje tablice na podstawie liczby miast
        cities = new String[citiesCount];
        visited = new boolean[citiesCount];
        weights = new double[citiesCount][citiesCount];

        // wczytuje nazwy miast
        for(int i = 0; i < citiesCount; i++) {
            cities[i] = fileReader.next();
            System.out.println("Dodaje miasto: " + cities[i]);
        }

        // rezerwuje tablice na wspolrzedne dla kazdego miasta
        points = new double[citiesCount][2];

        // wczytuje wspolrzedne dla kazdego miasta
        for(int i = 0; i < citiesCount; i++) {
            points[i][0] = fileReader.nextDouble();
            points[i][1] = fileReader.nextDouble();

            // wypisuje informacje o wczytanych wspolrzednych
            System.out.println("Dodano współrzędne: : " + cities[i] + " " + points[i][0] + ", " + points[i][1]);
        }

        // oblicza odleglosc z kazdego miasta do kazdego
        for(int i = 0; i < citiesCount; i++) {
            for(int j = 0; j < citiesCount; j++) {
                weights[i][j] = calculateDistance(points[i][0], points[i][1], points[j][0], points[j][1]);
                //System.out.printf("%7.2f", weights[i][j]);
            }
            //System.out.println("");
        }

    }


    // liczy odleglosc miedzy dwoma punktami w ukladzie 2D
    public static double calculateDistance(double x1, double y1, double x2, double y2) {
        return Math.sqrt(Math.pow(x1-x2, 2) + Math.pow(y1-y2, 2));
    }

    public static void main(String[] args) {
        try {

            // wczytuje miasta z pliku
            readFile2("miasta2.txt");
            //readFile("miasta.txt");

            // wypisuje tabele odleglosci do miast
            printCitiesTable();

            // znajduje najkrotsza sciezke miedzy miastami
            getShortestPath();
        } catch (IOException e) {
            e.printStackTrace();
        }

    }
}