import java.util.*;

public class TSP {
    static int radius = 6371;
    public static void main(String[] args) {
        long start = System.nanoTime();
        FileIO reader = new FileIO();
        String[] inputs = reader.load("E:\\TSP/Towns.txt");

        int inputsRows = inputs.length;
        int inputsColumns = inputs[0].trim().split(",").length;
        int TownRows = inputs.length;
        int TownColumns = inputsColumns - 2;
        double[][] coords = new double[inputsRows][inputsColumns - 2];
        String[][] Towns = new String[TownRows][TownColumns];
        // populating Town string with town numbers and names.
        for(int i = 0; i < inputsRows; i++) {
            String[] tokens = inputs[i].trim().split(",");
            for(int j = 0; j < tokens.length - 2; j++) {
                Towns[i][j] = (tokens[j]);
            }
        }

        // //populating Coords string with the necessary information
        for(int i = 0; i < TownRows; i++) {
            String[] tokens = inputs[i].trim().split(",");
            for(int j = 2; j < tokens.length; j++) {
                coords[i][j - 2] = Double.parseDouble(tokens[j]);
            }
            // System.out.println();
        }

        double[][] distances = new double[inputs.length][inputs.length];
        // setting a default value to the array
        // getting the distances from each town to all other towns
        double bestshort=Double.MAX_VALUE;
        String shortestpath="";

        //         for(int here=0;here<1000;here++){
        //              if((999-here)%100==0){
        //                 System.out.println((999-here)+" runs left!");
        //              }
        for(int i = 0; i < inputs.length; i++) {
            for(int j = 0; j < inputs.length; j++) {
                if(distances[i][j] == 0) {
                    distances[i][j] = haversin(coords[i][0], coords[j][0], coords[i][1], coords[j][1]);
                    distances[j][i] = (distances[i][j]);
                }
            }
        }

        int timessimulated = inputs.length;
        String PathShort = "";
        // setting a big variable that there will definitely be shorter le   ngths then
        double travelledshort = Double.MAX_VALUE;
        double[][] dcopy = new double[distances.length][distances[0].length];
        int startingpoint = 0;
        // keep check of the town we are on
        int TownOn = startingpoint;
        for(int u = 0; u < timessimulated; u++) {
            // starts at 0 by default on the first run through of the code, on the second it starts at the town in slot 1
            // on the 3 its the town at slot 2 etc...
            // records the shortest distance found to the next location, ie from town 1 to town 40 is shortest,
            // so go to town 40
            String Path = (u+1)+".";
            startingpoint = u;
            double shortest = 0;
            // refilling the array as after each iteration of the code it is an array full of 0's
            // as i use 0's to mark where i have been and where not to return to.
            for(int a = 0; a < inputs.length; a++) {
                for(int s = 0; s < inputs.length; s++) {
                    dcopy[a][s] = distances[a][s];
                }
            }

            // the travelled variable does the same as travelledshort, however it is constantly updated
            // every iteration with the total distance, whereas travelledshort is only updated when a shorter distance is found
            double travelled = 0;
            // looping through the amount of co-ordiantes given to find the shortest route.
            for(int j = 0; j < inputs.length-1; j++) {
                // finds where to go to next(nearest neighbour)
                shortest=Double.MAX_VALUE;
                // looks for a shorter value then the one obtained, but omits 0 distances.
                for(int i = 0; i < dcopy.length; i++) {
                    if((dcopy[startingpoint][i] < shortest) && (dcopy[startingpoint][i] > 0)) {
                        shortest = dcopy[startingpoint][i];
                        // updates what town we are going to.
                        TownOn = i;
                    }
                }

                // setting all value leading to the current spot as 0, to prevent us coming back.
                for(int k = 0; k < dcopy.length; k++) {
                    dcopy[startingpoint][k] = 0;
                    dcopy[k][startingpoint] = 0;
                    // dcopy[TownOn][startingpoint]=shortest;
                }

                // adding the shortest town to the string
                Path += (TownOn + 1) + ".";

                // sets new starting point
                startingpoint = TownOn;
                // adding the distance to our new location to the current distance travelled.
                travelled += shortest;

            }
            //System.out.println(Path);
            // omitting unecessary values that somehow creeped in to the path.
            if(travelled < travelledshort) {
                // if the travelled path in this iteration is the shortest path then it is updated to path short.
                PathShort = Path;
                travelledshort=travelled;
            }
            //System.out.println(u);
        }
        //NEAREST NEIGHBOUR SOLUTION
        //System.out.println(PathShort);
        // time to implement 2-opt!
        System.out.println("Done with the nearest neighbour solution.");
        System.out.println("Excessively 2opting this solution, this will take a while.");
        System.out.println(PathShort);
        String [] split=PathShort.split("\\.");
        String[] array4 = split;
        // what will be the final output
        String[] output =split;

        // filling array with the towns

        boolean isshorter=true;
        int fill=0;
        int iterations=0;
        // moved all previous code to the Swapper method so i can call it on any part of the string
        while(isshorter){

            double tempcheck=0;
            double distanceofswapped=0;
            String temp=new String(Swapper(output,2,distances));
            String [] temp2=new String[output.length];

            //System.out.println(temp);

            temp2=temp.split("\\.");
            fill=0;
            while(fill<output.length-1){
                //sums the path length from the start position to a certain size
                distanceofswapped+=distances[(Integer.parseInt(output[fill]))-1][(Integer.parseInt(output[fill+1]))-1];
                tempcheck+=distances[(Integer.parseInt(temp2[fill]))-1][(Integer.parseInt(temp2[fill+1]))-1];
                fill++;
            }
            if((tempcheck<distanceofswapped)&&(tempcheck>0)){
                for(int y=0;y<array4.length;y++){
                    output[y]=temp2[y];
                }
                distanceofswapped=tempcheck;
            }
            else{
                isshorter=false;
            }
            if( iterations%10==0){
                System.out.println("shortest so far");
                for(int a=0;a<output.length;a++){
                    System.out.print(output[a]+".");
                }

            }
            else if(iterations==100){isshorter=false;}
            iterations++;
        }
        System.out.println("Done with excessively 2 opting the nearest neighbour solution.");
        System.out.println("It took: "+(System.nanoTime() - start) / 1000000 + "ms");
        System.out.println("Excessively 2opting the inverse this solution, this will also take a while. \n");
        String [] outputinverted=new String[output.length];
        String  outputinverted1="";
        for(int y=0;y<array4.length;y++){
            outputinverted[y]=output[array4.length-1-y];
        }
        iterations=0;
        while(isshorter){
            double tempcheck=0;
            double distanceofswapped=0;
            String temp=new String(Swapper(outputinverted,2,distances));
            String [] temp2=new String[output.length];

            //System.out.println(temp);

            for(int y=0;y<temp2.length;y++){
                temp2[y]=(temp.split("\\.")[y]);

                //                 System.out.println();
            }
            fill=0;
            while(fill<output.length-1){
                //sums the path length from the start position to a certain size
                distanceofswapped+=distances[(Integer.parseInt(outputinverted[fill]))-1][(Integer.parseInt(outputinverted[fill+1]))-1];
                tempcheck+=distances[(Integer.parseInt(temp2[fill]))-1][(Integer.parseInt(temp2[fill+1]))-1];
                fill++;
            }
            if((tempcheck<distanceofswapped)&&(tempcheck>0)){
                for(int y=0;y<array4.length;y++){
                    outputinverted[y]=temp2[y];
                }
                distanceofswapped=tempcheck;
            }
            else{
                isshorter=false;
            }
            if( iterations%10==0){
                System.out.println("shortest so far");
                for(int a=0;a<output.length;a++){
                    System.out.print(outputinverted[a]+".");
                }
            }
            else if(iterations==100){isshorter=false;}
            iterations++;
        }

        System.out.println("Done with excessively 2 opting inverted 2opted solution.");
        System.out.print("It took: "+(System.nanoTime() - start) / 1000000 + "ms \n");
        for(int a=0;a<array4.length;a++){
            System.out.print(output[a]+".");

        }
        System.out.println();

        //             outputinverted1=(Swapper(outputinverted,2,distances));
        //             for(int y=0;y<array4.length;y++){
        //                 outputinverted[y]=(outputinverted1.split("\\.")[y]);
        //             }
        //last step, checking if the inverse of the route is better!
        int normaldist=0;
        int invertdist=0;
        fill=0;
        while(fill<output.length-1){
            //sums the path length from the start position to a certain size
            normaldist+=distances[(Integer.parseInt(output[fill]))-1][(Integer.parseInt(output[fill+1]))-1];
            fill++;
        }
        fill=0;
        while(fill<output.length-1){
            //sums the path length from the start position to a certain size
            invertdist+=distances[(Integer.parseInt(outputinverted[fill]))-1][(Integer.parseInt(outputinverted[fill+1]))-1];
            fill++;
        }
        //System.out.println(normaldist+"     "+invertdist);
        if(normaldist<invertdist){
            if(normaldist<bestshort){
                bestshort=normaldist;
                shortestpath="";
                for(int a=0;a<array4.length;a++){
                    shortestpath+=(output[a]+".");

                }

            }
            //                 for(int a=0;a<array4.length;a++){
            //                     System.out.print(output[a]+".");
            //
            //                 }
            // System.out.println("\n"+"Normal");
        }
        else{
            if(invertdist<bestshort){
                bestshort=invertdist;
                shortestpath="";
                for(int a=0;a<array4.length;a++){
                    shortestpath+=(outputinverted[a]+".");

                }

            }
            //                 for(int a=0;a<array4.length;a++){
            //                     System.out.print(outputinverted[a]+".");
            //
            //                 }
        }
        //         System.out.println("\n" + "Normal");
        //         System.out.println();
        //         } //THIS ONE FOR THE FOR LOOP
        System.out.println("Shortest solution.");
        System.out.println(shortestpath);
        System.out.println("\n"+(System.nanoTime() - start) / 1000000 + "ms");
    }

    public static double haversin(double latitude1, double latitude2, double longitude1, double longitude2) {
        double la1 = Math.toRadians(latitude1);
        double la2 = Math.toRadians(latitude2);
        double lo1 = Math.toRadians(longitude1);
        double lo2 = Math.toRadians(longitude2);
        return (2 * radius)
        * Math.asin(Math.sqrt((Math.sin((la1 - la2) / 2) * Math.sin((la1 - la2) / 2) + (Math.cos(la1) * Math.cos(la2))
                    * (Math.sin((lo1 - lo2) / 2) * Math.sin((lo1 - lo2) / 2)))));
    }

    public static String Swapper(String[] array, int chunksof, double[][] distances) {
        String output="";
        String [] bestarray=new String[array.length];
        String [] arrayswapped=new String [array.length];
        String [] arraycopy=new String[array.length];
        String []output1=new String[array.length];
        Arrays.fill(output1,"-1");

        for(int a = 0; a < array.length; a++) {
            arrayswapped[a]=array[a];
            bestarray[a]=array[a];
            arraycopy[a]=array[a];
            output+=arrayswapped[a]+".";
        }
        while(chunksof<array.length){
            for(int a = 0; a < array.length; a++) {
                arrayswapped[a]=array[a];
                arraycopy[a]=array[a];
            }
            int lastswap=0;
            int swap=0;
            int start=0;
            int end=0;
            while(start<array.length-chunksof){

                swap=0;
                end=start+chunksof;
                double path1=0;
                double path2=0;
                int position;
                if(start==0){position=0;}
                else{position=start-1;}
                for(int a=0;a<arrayswapped.length;a++){
                    arrayswapped[a]=array[a];
                    //                     System.out.print(arrayswapped[a]+".");
                }
                while(swap<chunksof/2){
                    String [] temp=new String[1];
                    temp[0]=arrayswapped[start+1+swap];
                    arrayswapped[start+1+swap]=arrayswapped[end-swap];
                    arrayswapped[end-swap]=temp[0];
                    swap++;
                }


                while(position<array.length-1){
                    path1+=distances[Integer.parseInt(bestarray[position])-1][Integer.parseInt(bestarray[position+1])-1];
                    path2+=distances[Integer.parseInt(arrayswapped[position])-1][Integer.parseInt(arrayswapped[position+1])-1];
                    position++;
                }
                //                 System.out.println((start+1)+"   "+(end));
                //                      System.out.println(path1+"   "+path2);
                //                 System.out.println(Arrays.toString(arrayswapped));
                //                 System.out.println(Arrays.toString(bestarray));

                if(path2<path1){

                    // System.out.println(path1+"=path1     ,path2="+path2);
                    //                      System.out.println("before");
                    //                      System.out.println();
                    output="";
                    //System.out.println("Swappedarray=");
                    for(int copy=0;copy<array.length;copy++){
                        //System.out.print(arrayswapped[copy]+".");
                        bestarray[copy]=arrayswapped[copy];
                        output+= bestarray[copy]+".";
                    }
                    for(int copy=start+1;copy<array.length;copy++){
                        //System.out.print(arrayswapped[copy]+".");
                        output1[copy]=arrayswapped[copy];
                    }
                    //                      System.out.println("after");
                }

                start++;
            }
            if(start-array.length+chunksof>1){
                int newend=array.length-1;
                lastswap=(array.length)-start;
                int lastchunks=(lastswap-1)/2;
                swap=0;
                for(int a=0;a<arrayswapped.length;a++){
                    arrayswapped[a]=array[a];
                    //                     System.out.print(arrayswapped[a]+".");
                }
                while(swap<lastchunks){
                    String [] temp=new String[1];
                    temp[0]=arrayswapped[start+1+swap];
                    arrayswapped[start+1+swap]=arrayswapped[newend-swap];
                    arrayswapped[newend-swap]=temp[0];
                    swap++;
                }

                double path1=0;
                double path2=0;
                int position;
                if(start==0){position=0;}
                else{position=start-1;}

                while(position<array.length-1){
                    path1+=distances[Integer.parseInt(array[position])-1][Integer.parseInt(array[position+1])-1];
                    path2+=distances[Integer.parseInt(arrayswapped[position])-1][Integer.parseInt(arrayswapped[position+1])-1];
                    position++;
                }
                //                 System.out.println((start+1)+"   "+(newend));
                //                    System.out.println(path1+"   "+path2);
                //                 System.out.println(Arrays.toString(bestarray));
                if(path2<path1){
                    //                     System.out.println("yup");
                    output="";
                    //System.out.println("Swappedarray=");
                    for(int copy=0;copy<array.length;copy++){
                        //System.out.print(arrayswapped[copy]+".");
                        bestarray[copy]=arrayswapped[copy];
                        output+= bestarray[copy]+".";
                    }
                    for(int copy=start+1;copy<array.length;copy++){
                        //System.out.print(arrayswapped[copy]+".");
                        output1[copy]=arrayswapped[copy];
                    }

                }
            }

            chunksof+=2;
        }
        int check=0;
        int check1=0;
        for(int copy=0;copy<array.length;copy++){
            if(output1[copy]=="-1"){
                output1[copy]=array[copy];
            }
        }
        for(int copy=0;copy<array.length-1;copy++){
            check+=distances[Integer.parseInt(output1[copy])-1][Integer.parseInt(output1[copy+1])-1];
            check1+=distances[Integer.parseInt(bestarray[copy])-1][Integer.parseInt(bestarray[copy+1])-1];
        }
        if(check<check1){
            for(int copy=0;copy<array.length;copy++){
                output+=output1[copy];
            }
        }

        return output;
    }
}