import java.util.ArrayList;
import java.util.Random;

public class Util {
    public Util() {
        //DO NOT USE!!!
    }
    /**
     * Uses heapsort and sort a population of Individuals by highest fitness.
     * @param population
     */
    public static void sort(ArrayList<Individual> population) {
        int N = population.size();

        for (int k = N/2; k > 0; k--)
        downheap(population, k, N);

        do {
            Individual T = population.get(0);
            population.set(0,population.get(N - 1));
            population.set(N - 1,T);

            N--;
            downheap(population, 1, N);
        }while (N > 1);
    }

    private static void downheap(ArrayList<Individual> population, int k, int N) {
        Individual T = population.get(k - 1);

        while (k <= N/2) {
            int j = k + k;
            if ((j < N) && (population.get(j - 1).getFitness() > population.get(j).getFitness()))
            j++;

            if (T.getFitness() <= population.get(j - 1).getFitness())
            break;

            else
            {
                population.set(k - 1, population.get(j - 1));
                k = j;
            }
        }
        population.set(k - 1,T);
    }

    public static String alphabet() {
        return "AZERTYUIOPQSDFGHJKLMWXCVBNazertyuiopqsdfghjklmwxcvbn ";
    }

    public static ArrayList<Individual> initialise(int numberOfIndividuals) {
        Random rand = new Random();
        ArrayList<Individual> population = new ArrayList<Individual>();

        for(int i = 0; i< numberOfIndividuals; i++) {
            String chromosome = "";
            for(int j = 0; j < 11; j++) {
                chromosome += Util.alphabet().charAt(rand.nextInt(Util.alphabet().length()));
            }
            Individual individual = new Individual(chromosome);
            population.add(individual);
        }
        return population;

    }

    public static ArrayList<Individual> mate (ArrayList<Individual> population, double mutation_rate) {
        Random rand = new Random();

        Util.sort(population);
        Individual parent1 = null;
        Individual parent2 = null;
        ArrayList<Individual> newPopulation = new ArrayList<Individual>();
        double highest_fitness = 0;
        for(int i = 0; i< population.size(); i++) {
            if(population.get(i).getFitness() > highest_fitness) {
                parent1 = population.get(i);
                parent2 = parent1;
            }
        }

        //Random rand2 = new Random();
        for(int i = 0; i < population.size();i++) {
            //Generate a random split point.
            int split_point = rand.nextInt(parent1.getChromosome().length());
            //Merging the two
            Individual newIndividual = new Individual(parent1.getChromosome().substring(0,split_point)+parent2.getChromosome().substring(split_point));
            if(mutation_rate > rand.nextInt(101)) {
                char[] temp = newIndividual.getChromosome().toCharArray();
                temp[rand.nextInt(temp.length)] = Util.alphabet().charAt(rand.nextInt(Util.alphabet().length()));
                String newString = "";
                for(int j = 0; j <temp.length; j++) {
                    newString += temp[j];
                }
                newIndividual = new Individual(newString);
                newPopulation.add(newIndividual);
            }else {
                newPopulation.add(newIndividual);
            }

        }
        return newPopulation;

    }

    public static void display(ArrayList<Individual> population) {
        for(int i = 0; i<population.size(); i++) {
            System.out.println(population.get(i).getChromosome() + " -> " + population.get(i).getFitness() + "%");
        }
    }

    public static boolean check(ArrayList<Individual> population) {
        for(int i = 0; i<population.size(); i++) {
            if(population.get(i).getChromosome().equals("Hello World")) {
                return true;
            }
        }
        return false;
    }
}