package tracks.levelGeneration.geneticLevelGenerator;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Random;

import core.game.GameDescription;
import core.generator.AbstractLevelGenerator;
import tools.ElapsedCpuTimer;
import tools.GameAnalyzer;
import tools.LevelMapping;

public class LevelGenerator extends AbstractLevelGenerator {

    /**
     * Level mapping of the best chromosome
     */
    private LevelMapping bestChromosomeLevelMapping;
    /**
     * The best chromosome fitness across generations
     */
    private ArrayList<Double> bestFitness;
    /**
     * number of feasible chromosomes across generations
     */
    private ArrayList<Integer> numOfFeasible;
    /**
     * number of infeasible chromosomes across generations
     */
    private ArrayList<Integer> numOfInFeasible;

    /**
     * Initializing the level generator
     * 
     * @param game         game description object
     * @param elapsedTimer amount of time for intiailization
     */
    public LevelGenerator(GameDescription game, ElapsedCpuTimer elapsedTimer) {
        SharedData.random = new Random();
        SharedData.gameDescription = game;
        SharedData.gameAnalyzer = new GameAnalyzer(game);
        SharedData.constructiveGen = new tracks.levelGeneration.constructiveLevelGenerator.LevelGenerator(game, null);
        bestChromosomeLevelMapping = null;
        bestFitness = null;
        numOfFeasible = null;
        numOfInFeasible = null;
    }

    /**
     * Get the next population based on the current feasible infeasible population
     * 
     * @param fPopulation array of the current feasible chromosomes
     * @param iPopulation array of the current infeasible chromosomes
     * @return array of the new chromosomes at the new population
     */
    private ArrayList<Chromosome> getNextPopulation(ArrayList<Chromosome> fPopulation,
            ArrayList<Chromosome> iPopulation) {
        ArrayList<Chromosome> newPopulation = new ArrayList<Chromosome>();

        // collect some statistics about the current generation
        ArrayList<Double> fitnessArray = new ArrayList<Double>();
        for (int i = 0; i < fPopulation.size(); i++) {
            fitnessArray.add(fPopulation.get(i).getFitness().get(0));
        }

        Collections.sort(fitnessArray);
        if (fitnessArray.size() > 0) {
            bestFitness.add(fitnessArray.get(fitnessArray.size() - 1));
        } else {
            bestFitness.add((double) 0);
        }
        numOfFeasible.add(fPopulation.size());
        numOfInFeasible.add(iPopulation.size());

        while (newPopulation.size() < SharedData.POPULATION_SIZE) {
            // choosing which population to work on with 50/50 probability
            // of selecting either any of them
            ArrayList<Chromosome> population = fPopulation;
            if (fPopulation.size() <= 0) {
                population = iPopulation;
            }
            if (SharedData.random.nextDouble() < 0.5) {
                population = iPopulation;
                if (iPopulation.size() <= 0) {
                    population = fPopulation;
                }
            }

            // select the parents using roulletewheel selection
            Chromosome parent1 = rouletteWheelSelection(population);
            Chromosome parent2 = rouletteWheelSelection(population);
            Chromosome child1 = parent1.clone();
            Chromosome child2 = parent2.clone();
            // do cross over
            if (SharedData.random.nextDouble() < SharedData.CROSSOVER_PROB) {
                ArrayList<Chromosome> children = parent1.crossOver(parent2);
                child1 = children.get(0);
                child2 = children.get(1);

                // do muation to the children
                if (SharedData.random.nextDouble() < SharedData.MUTATION_PROB) {
                    child1.mutate();
                }
                if (SharedData.random.nextDouble() < SharedData.MUTATION_PROB) {
                    child2.mutate();
                }
            }

            // mutate the copies of the parents
            else if (SharedData.random.nextDouble() < SharedData.MUTATION_PROB) {
                child1.mutate();
            } else if (SharedData.random.nextDouble() < SharedData.MUTATION_PROB) {
                child2.mutate();
            }

            // add the new children to the new population
            newPopulation.add(child1);
            newPopulation.add(child2);
        }

        // calculate fitness of the new population chromosomes
        for (int i = 0; i < newPopulation.size(); i++) {
            newPopulation.get(i).calculateFitness(SharedData.EVALUATION_TIME);
            if (newPopulation.get(i).getConstrainFitness() < 1) {
                System.out.println("\tChromosome #" + (i + 1) + " Constrain Fitness: "
                        + newPopulation.get(i).getConstrainFitness());
            } else {
                System.out.println("\tChromosome #" + (i + 1) + " Fitness: " + newPopulation.get(i).getFitness());
            }
        }

        // add the best chromosome(s) from old population to the new population
        Collections.sort(newPopulation);
        for (int i = SharedData.POPULATION_SIZE - SharedData.ELITISM_NUMBER; i < newPopulation.size(); i++) {
            newPopulation.remove(i);
        }

        if (fPopulation.isEmpty()) {
            Collections.sort(iPopulation);
            for (int i = 0; i < SharedData.ELITISM_NUMBER; i++) {
                newPopulation.add(iPopulation.get(i));
            }
        } else {
            Collections.sort(fPopulation);
            for (int i = 0; i < SharedData.ELITISM_NUMBER; i++) {
                newPopulation.add(fPopulation.get(i));
            }
        }

        return newPopulation;
    }

    /**
     * Roullete wheel selection for the infeasible population
     * 
     * @param population array of chromosomes surviving in this population
     * @return the picked chromosome based on its constraint fitness
     */
    private Chromosome constraintRouletteWheelSelection(ArrayList<Chromosome> population) {
        // calculate the probabilities of the chromosomes based on their fitness
        double[] probabilities = new double[population.size()];
        probabilities[0] = population.get(0).getConstrainFitness();
        for (int i = 1; i < population.size(); i++) {
            probabilities[i] = probabilities[i - 1] + population.get(i).getConstrainFitness() + SharedData.EIPSLON;
        }

        for (int i = 0; i < probabilities.length; i++) {
            probabilities[i] = probabilities[i] / probabilities[probabilities.length - 1];
        }

        // choose a chromosome based on its probability
        double prob = SharedData.random.nextDouble();
        for (int i = 0; i < probabilities.length; i++) {
            if (prob < probabilities[i]) {
                return population.get(i);
            }
        }

        return population.get(0);
    }

    /**
     * Get the fitness for any population
     * 
     * @param population array of chromosomes surviving in this population
     * @return the picked chromosome based on its fitness
     */
    private Chromosome rouletteWheelSelection(ArrayList<Chromosome> population) {
        // if the population is infeasible use the constraintRoulletWheel function
        if (population.get(0).getConstrainFitness() < 1) {
            return constraintRouletteWheelSelection(population);
        }

        // calculate the probabilities for the current population
        double[] probabilities = new double[population.size()];
        probabilities[0] = population.get(0).getCombinedFitness();
        for (int i = 1; i < population.size(); i++) {
            probabilities[i] = probabilities[i - 1] + population.get(i).getCombinedFitness() + SharedData.EIPSLON;
        }

        for (int i = 0; i < probabilities.length; i++) {
            probabilities[i] = probabilities[i] / probabilities[probabilities.length - 1];
        }

        // choose random chromosome based on its fitness
        double prob = SharedData.random.nextDouble();
        for (int i = 0; i < probabilities.length; i++) {
            if (prob < probabilities[i]) {
                return population.get(i);
            }
        }

        return population.get(0);
    }

    /**
     * Generate a level using GA in a fixed amount of time and return the level in
     * form of a string
     * 
     * @param game         the current game description object
     * @param elapsedTimer the amount of time allowed for generation
     * @return string for the generated level
     */
    @Override
    public String generateLevel(GameDescription game, ElapsedCpuTimer elapsedTimer) {
        // initialize the statistics objects
        bestFitness = new ArrayList<Double>();
        numOfFeasible = new ArrayList<Integer>();
        numOfInFeasible = new ArrayList<Integer>();

        SharedData.gameDescription = game;

        int size = 0;
        if (SharedData.gameAnalyzer.getSolidSprites().size() > 0) {
            size = 2;
        }

        // get the level size
        int width = (int) Math.max(SharedData.MIN_SIZE + size,
                game.getAllSpriteData().size() * (1 + 0.25 * SharedData.random.nextDouble()) + size);
        int height = (int) Math.max(SharedData.MIN_SIZE + size,
                game.getAllSpriteData().size() * (1 + 0.25 * SharedData.random.nextDouble()) + size);
        width = (int) Math.min(width, SharedData.MAX_SIZE + size);
        height = (int) Math.min(height, SharedData.MAX_SIZE + size);

        System.out.println("Generation #1: ");
        ArrayList<Chromosome> fChromosomes = new ArrayList<Chromosome>();
        ArrayList<Chromosome> iChromosomes = new ArrayList<Chromosome>();
        for (int i = 0; i < SharedData.POPULATION_SIZE; i++) {

            // initialize the population using either randomly or using contructive level
            // generator
            Chromosome chromosome = new Chromosome(width, height);
            if (SharedData.CONSTRUCTIVE_INITIALIZATION) {
                chromosome.InitializeConstructive();
            } else {
                chromosome.InitializeRandom();
            }

            // calculate the fitness for all the chromosomes and add them to the correct
            // population
            // either the feasible or the infeasible one
            chromosome.calculateFitness(SharedData.EVALUATION_TIME);
            if (chromosome.getConstrainFitness() < 1) {
                iChromosomes.add(chromosome);
                System.out.println(
                        "\tChromosome #" + (i + 1) + " Constrain Fitness: " + chromosome.getConstrainFitness());
            } else {
                fChromosomes.add(chromosome);
                System.out.println("\tChromosome #" + (i + 1) + " Fitness: " + chromosome.getFitness());
            }
        }

        // some variables to make sure not getting out of time
        double worstTime = SharedData.EVALUATION_TIME * SharedData.POPULATION_SIZE;
        double avgTime = worstTime;
        double totalTime = 0;
        int numberOfIterations = 0;

        System.out.println(elapsedTimer.remainingTimeMillis() + " " + avgTime + " " + worstTime);
        while (elapsedTimer.remainingTimeMillis() > 2 * avgTime && elapsedTimer.remainingTimeMillis() > worstTime) {
            ElapsedCpuTimer timer = new ElapsedCpuTimer();

            System.out.println("Generation #" + (numberOfIterations + 2) + ": ");

            // get the new population and split it to a the feasible and infeasible
            // populations
            ArrayList<Chromosome> chromosomes = getNextPopulation(fChromosomes, iChromosomes);
            fChromosomes.clear();
            iChromosomes.clear();
            for (Chromosome c : chromosomes) {
                if (c.getConstrainFitness() < 1) {
                    iChromosomes.add(c);
                } else {
                    fChromosomes.add(c);
                }
            }

            numberOfIterations += 1;
            totalTime += timer.elapsedMillis();
            avgTime = totalTime / numberOfIterations;
        }

        // return the best infeasible chromosome
        if (fChromosomes.isEmpty()) {
            for (int i = 0; i < iChromosomes.size(); i++) {
                iChromosomes.get(i).calculateFitness(SharedData.EVALUATION_TIME);
            }

            Collections.sort(iChromosomes);
            bestChromosomeLevelMapping = iChromosomes.get(0).getLevelMapping();
            System.out.println("Best Fitness: " + iChromosomes.get(0).getConstrainFitness());
            return iChromosomes.get(0).getLevelString(bestChromosomeLevelMapping);
        }

        // return the best feasible chromosome otherwise and print some statistics
        for (int i = 0; i < fChromosomes.size(); i++) {
            fChromosomes.get(i).calculateFitness(SharedData.EVALUATION_TIME);
        }
        Collections.sort(fChromosomes);
        bestChromosomeLevelMapping = fChromosomes.get(0).getLevelMapping();
        System.out.println("Best Chromosome Fitness: " + fChromosomes.get(0).getFitness());
        System.out.println(bestFitness);
        System.out.println(numOfFeasible);
        System.out.println(numOfInFeasible);
        return fChromosomes.get(0).getLevelString(bestChromosomeLevelMapping);
    }

    /**
     * get the current used level mapping to create the level string
     * 
     * @return the level mapping used to create the level string
     */
    @Override
    public HashMap<Character, ArrayList<String>> getLevelMapping() {
        return bestChromosomeLevelMapping.getCharMapping();
    }
}
