// Genetic Algorithm class.
class GeneticAlgorithm {

    // Crossover methods.
    static CrossoverMethod = { Middle: 0, Random: 1 };

    // Population class that defines a population of individuals.
    static Population = class Population {

        // Individual class that defines an individual in a population as 
        // a chromosome of genes.
        static Individual = class Individual {

            // Individual constructor.
            constructor(seedFunction, fitnessFunction, sizeOfChromosome) {
                this.seedFunction = seedFunction;
                this.fitnessFunction = fitnessFunction;

                this.genes = new Array(sizeOfChromosome);
                for (let i = 0; i < sizeOfChromosome; ++i)
                    this.genes[i] = this.seedFunction.run();
                this.fitness = this.fitnessFunction.run(this.genes);
            }

            // Get all genes of the individual.
            getGenes() { return this.genes; }

            // Set genes and update fitness.
            setGenes(genes) {
                this.genes = genes;
                this.fitness = this.fitnessFunction.run(this.genes);
            }

            // Get a gene at a specific index.
            getGene(i) { return this.genes[i]; }

            // Set a gene at a specific index and update fitness.
            setGene(i, gene) {
                this.genes[i] = gene;
                this.fitness = this.fitnessFunction.run(this.genes);
            }

            // Get fitness of the individual.
            getFitness() { return this.fitness; }

            // Copy genes from another individual and update fitness.
            copyGenesFrom(individual) {
                this.genes = copy(individual.genes);
                this.fitness = this.fitnessFunction.run(this.genes);
            }

            // Select a random mutation point and change the gene at the point.
            randomMutation() {
                this.setGene(random(this.genes.length), this.seedFunction.run());
            }

            // Serialization function that turns an individual into a string.
            toString() {
                let os = '[';
                for (let i = 0; i < this.genes.length; ++i)
                    os += this.genes[i] + (i < this.genes.length - 1 ? ',' : '');
                os += ']=' + this.fitness;
                return os;
            }
        }

        // Population constructor.
        constructor(seedFunction, fitnessFunction, sizeOfChromosome, sizeOfPopulation = 0) {
            this.individuals = new Array(sizeOfPopulation);
            this.fittest = undefined;
            for (let i = 0; i < sizeOfPopulation; ++i)
                this.individuals[i] = new Population.Individual(seedFunction,
                    fitnessFunction, sizeOfChromosome);
            this.updateFittest();
        }

        // Get the size of the population.
        getSize() { return this.individuals.length; }

        // Get an individual at a specific index.
        getIndividual(i) { return this.individuals[i]; }

        // Get the fittest individual in the population.
        getFittest() { return this.fittest; }

        // Update the fittest individual in the population.
        updateFittest() {
            if (this.individuals.length) {
                this.fittest = this.individuals[0];
                for (let i = 1; i < this.individuals.length; ++i) {
                    if (this.individuals[i].getFitness() > this.fittest.getFitness())
                        this.fittest = this.individuals[i];
                }
            }
            else
                this.fittest = undefined;
        }

        // Serialization function that turns a population into a string.
        toString() {
            let s = ' = ' + this.getFittest().getFitness() + '\n';
            for (let i = 0; i < this.getSize(); ++i)
                s += '  ' + i + ':' + this.getIndividual(i).toString() + '\n';
            return s;
        }
    };

    // Genetic Algorithm constructor
    constructor(seedFunction, fitnessFunction) {
        this.seedFunction = seedFunction;
        this.fitnessFunction = fitnessFunction;
        this.population = null;
        this.generation = 0;
        this.log = '';
    }

    // Get the fittest individual in the current population.
    getFittest() { return this.population.getFittest(); }

    // Implementation of the Roulette Wheel Selection. The probability of an 
    // individual to be selected is directly proportional to its fitness.
    selection(sizeOfChromosome, sizeOfPopulation) {
        if (!this.population)
            this.setPopulation(new GeneticAlgorithm.Population(this.seedFunction,
                this.fitnessFunction, sizeOfChromosome, sizeOfPopulation));

        let newGeneration = new GeneticAlgorithm.Population(this.seedFunction,
            this.fitnessFunction, sizeOfChromosome, sizeOfPopulation);

        // Play roulette.
        let sum_fitness = 0;
        for (let i = 0; i < sizeOfPopulation; ++i)
            sum_fitness += this.population.getIndividual(i).getFitness();

        // If all fitness values are non-positive, roulette probabilities
        // are not meaningful.
        if (sum_fitness >= 0) {
            for (let i = 0; i < sizeOfPopulation; ++i) {
                let rnd = random(sum_fitness);
                let I = 0;
                for (; I < sizeOfPopulation; ++I) {
                    rnd -= this.population.getIndividual(I).getFitness();
                    if (rnd <= 0)
                        break;
                }
                // Copy genes
                newGeneration.getIndividual(i).copyGenesFrom(
                    this.population.getIndividual(I));
            }
        }
        newGeneration.updateFittest();
        return newGeneration;
    }

    // Crossover parents genes.
    crossover(newGeneration, sizeOfChromosome, crossoverMethod) {

        let sizeOfPopulation = newGeneration ? newGeneration.getSize() : 0;

        let crossOverPoint;
        if (crossoverMethod == GeneticAlgorithm.CrossoverMethod.Middle)
            crossOverPoint = sizeOfChromosome / 2;
        else if (crossoverMethod == GeneticAlgorithm.CrossoverMethod.Random)
            crossOverPoint = random(sizeOfChromosome);
        else
            throw new Error('Unknown crossover method: ' + crossoverMethod);

        for (let j = 0; j < sizeOfPopulation - 1; j += 2) {
            // Swap values among pairs.
            for (let i = 0; i < crossOverPoint; ++i) {
                // Swap genes.
                let t = newGeneration.getIndividual(j + 1).getGene(i);
                newGeneration.getIndividual(j + 1).setGene(i,
                    newGeneration.getIndividual(j).getGene(i));
                newGeneration.getIndividual(j).setGene(i, t);
            }
        }
    }

    // Perform mutation on the new generation under a given probability.
    mutation(newGeneration, mutationProbability) {

        let sizeOfPopulation = newGeneration ? newGeneration.getSize() : 0;

        for (let j = 0; j < sizeOfPopulation; ++j)
            // Select a random mutation point and flip 
            // genes at the mutation point.
            if (random(100) < mutationProbability)
                newGeneration.getIndividual(j).randomMutation();
    }

    // Replace existing population with a new generation.
    setPopulation(newGeneration) {
        this.population = newGeneration;
        this.population.updateFittest();
    }

    // Start the search.
    run(sizeOfChromosome, sizeOfPopulation, mutationProbability,
            crossoverMethod, isLog) {
        this.generation = 0;
        this.log = '';

        this.setPopulation(new GeneticAlgorithm.Population(this.seedFunction,
            this.fitnessFunction, sizeOfChromosome, sizeOfPopulation));

        // While loop until the solution is found.
        while (this.next(sizeOfChromosome, sizeOfPopulation,
            mutationProbability, crossoverMethod, isLog)) {
        }
    }

    // Continue the search.
    next(sizeOfChromosome, sizeOfPopulation, mutationProbability,
        crossoverMethod, isLog) {
        if (!this.population)
            this.setPopulation(new GeneticAlgorithm.Population(this.seedFunction,
                this.fitnessFunction, sizeOfChromosome, sizeOfPopulation));

        if (isLog)
            this.log += '\nGeneration: ' + this.generation +
                this.population.toString() + '\n';

        // Stop the search when either max fitness of solution or 
        // max limit for generations achived.
        if (this.population.getFittest().getFitness() == 100
            || this.generation > 10000)
            return false;

        // Select fittest parents to mate and produce a new generation.
        let newGeneration = this.selection(sizeOfChromosome, sizeOfPopulation);

        // Recombination: creates new individuals by taking the chromosomes 
        // from the fittest members of the population and modifing these 
        // chromosomes using crossover and/or mutation.
        this.crossover(newGeneration, sizeOfChromosome, crossoverMethod);
        this.mutation(newGeneration, mutationProbability);

        // Set population with new generation.
        this.setPopulation(newGeneration);
        this.generation++;

        return true;
    }
}