package javaGenetyczny;

import java.io.File;
import java.lang.reflect.Array;
import java.util.Scanner;
import java.util.stream.Collector;
import java.util.stream.Collectors;

import javax.jws.Oneway;
import javax.swing.plaf.metal.MetalIconFactory.FolderIcon16;

import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;
import java.util.Random;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;

public class Main {

    private static final int NUMBER_OF_ITERATIONS = 400000;
    private static final int NUMBER_OF_TOURISTS = 40;
    private static final int MUTATION_PROPABILITY = 5; //0.5%
    private static final int CROSSOVER_PROPABILITY = 700; //70%
    private static final int QUANTITY_OF_COMP_SELECTION = 3; //skacz co K osobników w turnieju

    public static void main(String[] args) throws Exception {

        String fileName = "berlin52.txt";
        String logRecord;
        File dataFile = new File(fileName);
        String[] splitLine = null;
        Scanner scanner = new Scanner(dataFile);
        int rowSize = Integer.valueOf(scanner.nextLine()); // pierwsza linia
                                                            // wczytanego
                                                            // dokumentu (ilosc
                                                            // wierszy w pliku)
        int[][] tab = new int[rowSize][rowSize];
        int[][] tourist = new int[NUMBER_OF_TOURISTS][rowSize];
        int[] distance = new int[NUMBER_OF_TOURISTS];

        shuffleArrayList(rowSize, tourist);

        int i = 0;
        while (scanner.hasNextLine()) {
            logRecord = scanner.nextLine();
            splitLine = logRecord.split("\\s");

            for (int j = 0; j < splitLine.length; j++) {
                if (!"0".equals(splitLine[j])) {
                    tab[i][j] = Integer.valueOf(splitLine[j]);
                    tab[j][i] = Integer.valueOf(splitLine[j]);
                }
            }
            i++;
        }
        // ---------------------------------------------------------------------------------------------------------------------------------------
        for (int d = 0; d < NUMBER_OF_TOURISTS; d++) {
            System.out.printf("Wiersz %2d. ", d + 1); // numerowanie wierszy
            for (int j = 0; j < rowSize; j++) {
                System.out.printf("%5d", tourist[d][j]); // wypisanie
                                                            // pojedynczego
                                                            // miasta
                                                            // (dlugosci)???
            }
            distance[d] = countDistance(tab, tourist[d]);
            System.out.printf(" :: %s  ", distance[d]);
            System.out.println();
        }
        System.out.println("\nOceny: ");
        for (int j = 0; j < NUMBER_OF_TOURISTS; j++) {
            System.out.printf("%5d ", distance[j]);
        }
        System.out.println("\n");
        System.out.println("Najkrótsza route: " + getMin(distance) + "\n\n");
        // ----------------------------------------------------------------------------------------------------------
        // ----------------------------------------------------------------------------------------------------------

        int[][] touristTMP = tourist;
        int tmpdistance = Integer.MAX_VALUE;
        int[] selectionIndex = new int[NUMBER_OF_TOURISTS];


        for (int k = 0; k < NUMBER_OF_ITERATIONS; k++) {

            if(k%20000<10000){
                selectionIndex = competitionSelection(distance);
                System.out.println("Turniej");
            } else {
                selectionIndex = rouletteSelection(distance);
                System.out.println("Ruletka");
            }

            System.out.printf("\nIteracja: "+(k+1)+" ::: ");

            for (int j = 0; j < NUMBER_OF_TOURISTS; j++) {
                System.out.printf("%5d", selectionIndex[j]);
            }
            System.out.println();

            int[][] touristChild = new int[NUMBER_OF_TOURISTS][rowSize];

            touristChild = crossOver(selectionIndex, touristChild, touristTMP); /// mamy
                                                                                    /// pokrzyzowana
                                                                                    /// populacje
                                                                                    /// (wynik
                                                                                    /// tablica[][])
            touristChild = mutation(selectionIndex, touristChild);



            for (int d = 0; d < NUMBER_OF_TOURISTS; d++) {

                distance[d] = countDistance(tab, touristChild[d]);

            }

            if (getMin(distance) < tmpdistance) {
                tmpdistance = getMin(distance);
            }

            touristTMP = touristChild;

             System.out.println("Iteracja: "+(k+1)+" -> Najkrótsza trasa: " +
             tmpdistance + "\n\n");
        }
    }



    // --------------------------METODY----------------------------------------

    // Mieszanie wartości w tablicy
    private static void shuffleArrayList(int rowSize, int[][] tourist) {
        for (int i = 0; i < tourist.length; i++) {

            ArrayList<Integer> numbers = new ArrayList<>();
            for (int q = 0; q < rowSize; q++) {
                numbers.add(q + 1);
            }
            Collections.shuffle(numbers);
            for (int j = 0; j < rowSize; j++) {
                tourist[i][j] = numbers.get(j);
            }
        }
    }

    // Znajdź min z tablicy[]
    public static int getMin(int[] inputArray) {
        int minValue = inputArray[0];
        for (int i = 1; i < inputArray.length; i++) {
            if (inputArray[i] < minValue) {
                minValue = inputArray[i];
            }
        }
        return minValue;
    }
    // Znajdz max z tablicy[]
    public static int getMax(int[] inputArray) {
        int maxValue = inputArray[0];
        for (int i = 1; i < inputArray.length; i++) {
            if (inputArray[i] > maxValue) {
                maxValue = inputArray[i];
            }
        }
        return maxValue;
    }

    // Licz distans
    private static int countDistance(int[][] tab, int[] user) {
        int route = 0;
        int a, b;
        for (int i = 0; i < user.length; i++) {
            a = user[i];
            if (i == (user.length - 1)) {
                b = user[0];
            } else {
                b = user[i + 1];
            }
            route += tab[a - 1][b - 1];
        }
        return route;
    }

    private static int[] competitionSelection(int distance[]) {
        Random r = new Random();

        int[] competitionIndexes = new int[NUMBER_OF_TOURISTS];
        for (int j = 0; j < NUMBER_OF_TOURISTS; j++) {
            int distanceMin = Integer.MAX_VALUE; // największa możliwa wartość,

            int indexMin = -1; // -1 bo napewno go nie ma, deklaracja
            for (int i = 0; i < QUANTITY_OF_COMP_SELECTION; i++) {
                int randIndeks = r.nextInt(NUMBER_OF_TOURISTS);
                if (distance[randIndeks] < distanceMin) {
                    indexMin = randIndeks;
                    distanceMin = distance[randIndeks];
                }
            }
            competitionIndexes[j] = indexMin;
        }

        return competitionIndexes;

    }

    // ----------------------Koło ruletki----------------------

    private static int[] rouletteSelection(int distance[]) {


        int max = getMax(distance);
        int[] tmpDistance = new int[NUMBER_OF_TOURISTS];
        for (int i = 0; i < distance.length; i++) {
            tmpDistance[i] = max + 1 - distance[i];
        }


        int propabilitySum = 0;
        for (int i = 0; i < tmpDistance.length; i++) {
            propabilitySum += tmpDistance[i];
        }

        int[] rouletteIndexes = new int[NUMBER_OF_TOURISTS];
        Random r = new Random();

        for (int i = 0; i < NUMBER_OF_TOURISTS; i++) {
            int numberRand = r.nextInt(propabilitySum);
            int j = 0;

            while (numberRand > 0) {
                numberRand = numberRand - tmpDistance[j];
                j++;
                if(j==NUMBER_OF_TOURISTS){
                    j=j-1;
                }
            }
            rouletteIndexes[i] = j;
        }

        return rouletteIndexes;
    }

    // ----------------------Krzyżowanie----------------------

    // indexOf
    private static int indeksOf(int[] tab, int el) {
        for (int i = 0; i < tab.length; i++) {
            if (tab[i] == el)
                return i;
        }
        return -1;
    }

    // Krzyzowanie
    private static int[][] crossOver(int[] selectionIndex, int[][] touristChild, int[][] tourist) {
        Random rand = new Random();


            for (int i = 0; i < selectionIndex.length; i += 2) {
                if(rand.nextInt(1000) < CROSSOVER_PROPABILITY){
                int p1 = selectionIndex[i];
                int p2 = selectionIndex[i + 1];
                Random r = new Random();
                int cross1 = r.nextInt(tourist[0].length - 3) + 1;
                int cross2 = r.nextInt(tourist[0].length - 1 - cross1) + cross1 + 1;

                // zamiana środka
                for (int j = cross1; j <= cross2; j++) {
                    touristChild[i][j] = tourist[p1][j];
                    touristChild[i + 1][j] = tourist[p2][j];
                }

                // krzyżowanie PMX
                for (int j = 0; j < cross1; j++) {
                    int city1 = tourist[p2][j];
                    int ind;
                    // zamiana nieistniejących środka
                    while ((ind = indeksOf(touristChild[i], city1)) != -1) {
                        city1 = tourist[p2][ind];
                    }
                    touristChild[i][j] = city1;
                }

                for (int j = cross2 + 1; j < tourist[0].length; j++) {
                    int city1 = tourist[p2][j];
                    int ind;

                    // zamiana nieistniejących środka
                    while ((ind = indeksOf(touristChild[i], city1)) != -1) {
                        city1 = tourist[p2][ind];
                    }
                    touristChild[i][j] = city1;
                }

                for (int j = 0; j < cross1; j++) {
                    int city1 = tourist[p1][j];
                    int ind;
                    // zamiana nieistniejących środka
                    while ((ind = indeksOf(touristChild[i + 1], city1)) != -1) {
                        city1 = tourist[p1][ind];
                    }
                    touristChild[i + 1][j] = city1;
                }

                for (int j = cross2 + 1; j < tourist[0].length; j++) {
                    int city1 = tourist[p1][j];
                    int ind;
                    // zamiana nieistniejących środka
                    while ((ind = indeksOf(touristChild[i + 1], city1)) != -1) {
                        city1 = tourist[p1][ind];
                    }
                    touristChild[i + 1][j] = city1;
                }
            } else {
                for (int j = 0; j < tourist[i].length; j++) {

                    touristChild[i][j] = tourist[i][j];
                    touristChild[i + 1][j] = tourist[i + 1][j];

                }
            }


        }
        return touristChild;
    }

    // -----------------------------Mutacja-------------------------------------------------------
    private static int[][] mutation(int[] selectionIndex, int[][] touristChild) {
        Random rand = new Random();
        if(rand.nextInt(1000) < MUTATION_PROPABILITY){

            // losowanie przeciec
            int cross1 = 0;
            int cross2 = 0;

            for (int i = 0; i < selectionIndex.length; i++) {

                Random r = new Random();

                cross1 = r.nextInt(touristChild[0].length - 3) + 1;
                cross2 = r.nextInt(touristChild[0].length - 1 - cross1) + cross1 + 1;

                ArrayList<Integer> touristChildTmpCenterPart = new ArrayList<>();

                // przypisujemy srodek z touristCHild
                for (int j = cross1; j <= cross2; j++) {
                    touristChildTmpCenterPart.add(touristChild[i][j]);
                }

                Collections.reverse(touristChildTmpCenterPart);

                int tmpIndex = 0;
                for (int j = cross1; j <= cross2; j++) {

                    touristChild[i][j] = touristChildTmpCenterPart.get(tmpIndex);
                    tmpIndex++;
                }

            }


        }
        return touristChild;

    }