package ac.essex.gp;

import ac.essex.gp.tree.TreeOptimiser;
import ac.essex.gp.params.GPParams;
import ac.essex.gp.util.DeepCopy;
import ac.essex.gp.tree.Node;
import ac.essex.gp.util.FoundBestIndividualException;
import ac.essex.gp.interfaces.GPActionListener;
import ac.essex.gp.interfaces.console.ConsoleListener;
import ac.essex.gp.individuals.Individual;
import ac.essex.gp.problems.*;
import ac.essex.gp.problems.CoevolutionProblem;
import ac.essex.gp.selection.Selector;
import ac.essex.gp.genetics.Mutation;
import ac.essex.gp.genetics.OperationCounter;
import ac.essex.gp.genetics.Crossover;
import ac.essex.gp.treebuilders.TreeBuilder;
import ac.essex.ooechs.imaging.commons.fast.FastStatistics;

import java.util.Vector;
import java.util.Collections;
import java.util.Random;
import java.util.Arrays;

/**
 * <p/>
 * The main entry point to start Genetic Programming, contains the code for the main GP loop. Initialise it
 * by giving an instance of the problem you want to solve in the constructor. You may
 * also supply a GP params instance and listener if you don't want to use the defaults.
 * </p>
 * <p/>
 * <p/>
 * This class is a Thread so it can run in the background if you want. If you want to do
 * this then call the start() method. If you don't want it to run in parallel, call the
 * run() method to get the evolution process going
 * </p>
 * <p/>
 * <p/>
 * Evolution is dependent on the params in the GPParams object. If you don't supply your own
 * then the default parameters will be used (see GPParams.java). If you want to change params but
 * enjoy GUIs, then consider the GP start dialog (util.GPStartDialog)
 * </p>
 *
 * @author Olly Oechsle, University of Essex, Date: 15-Jan-2007
 * @version 0.1.06 Made the code easier to execute and read, standardised and improved the algorithms.
 */
public class Evolve extends Thread {

    public static void main(String[] args) {
        System.out.println("This is " + APP_NAME);
        //new GPStartDialog(null, new CoevolvedMathsProblem(), new ConsoleListener());
        //Evolve e  = new Evolve(new CoevolvedMathsProblem());
        //e.run();
    }

    public static long seed = 2357;
    protected static Random r = null;

    public static double getRandomNumber() {

        if (r == null) {
            initialiseRandomNumberGenerator();
        }

        return r.nextDouble();

    }

    public static void initialiseRandomNumberGenerator() {
        if (seed == -1) {
            r = new Random();
        } else {
            r = new Random(seed);
        }
    }

    public void setSeed(long seed) {
        r = null;
        Evolve.seed = seed;
    }

    public static final String APP_NAME = "sxGP v0.1.08";

    /**
     * The problem that has to be solved
     */
    protected Problem p;

    /**
     * The object which holds all the parameter values we need
     */
    protected GPParams params;

    /**
     * The action listener which displays results and feedback to the user
     */
    public GPActionListener gpinterface;

    /**
     * Should the program stop its execution prematurely?
     */
    public boolean stopFlag = false;

    /**
     * Has something terrible happened?
     */
    public boolean fatal = false;

    /**
     * Is the problem requesting a fresh (random) generation?
     */
    protected boolean requestFreshPopulation = false;

    /**
     * How long is this all taking?
     */
    protected long totalTime = -1;

    /**
     * What is the best individual we've found so far?
     */
    protected Individual bestIndividual;

    /**
     * How many individuals were evaluated?
     */
    protected int totalEvaluations = 0;

    // Copies individuals
    private DeepCopy copier;

    /**
     * Starts the evolve object with a standard GP params object
     * and the console listener.
     */
    public Evolve(Problem p) {
        this(p, new ConsoleListener(), null);
    }

    /**
     * Starts the evolve object with a standard GP params object and whatever
     * problem and listener you supply.
     */
    public Evolve(Problem p, GPActionListener listener) {
        this(p, listener, null);
    }

    /**
     * Starts the evolve object. You supply the problem, an instance of a GP params
     * object and the listener you want to use (console or graphical is available).
     */
    public Evolve(Problem p, GPActionListener gpInterface, GPParams params) {
        this.p = p;
        this.gpinterface = gpInterface;
        if (params == null) {
            // problem usually initialises the params
            this.params = new GPParams();
        } else {
            this.params = params;

        }
        // initialise the problem - this is where nodes are registered and training data loaded
        if (!this.params.hasBeenInitialised) {
            p.initialise(this, this.params);
            this.params.hasBeenInitialised = true;
        }

        // initialise any custom parameters - changing population size etc.
        if (!this.params.hasBeenCustomised) {
            p.customiseParameters(this.params);
            this.params.hasBeenCustomised = true;
        }

        copier = new DeepCopy();

    }

    int treeIndex = 0;
    long startTime;

    // The population
    private Individual[] population;

    /**
     * Call this method to start the evolution. If you're using SXGP from within a GUI
     * and you prefer to have your mouse still working while you wait, use the start() method
     * to call this method as a thread.
     */
    public void run() {

        initialiseRandomNumberGenerator();

        // reset the number of evaluations
        totalEvaluations = 0;

        // reset the operation counter (counts how many genetic operations occur, a debugging mechanism)
        OperationCounter.reset();

        p.clearFitnessCache();

        try {
            // check that the params don't have any silly values
            params.check();
        } catch (Exception err) {
            gpinterface.fatal(err.getMessage());
            return;
        }

        if (fatal) {
            // perhaps some fatal error will stop the GP before we even begin...
            System.err.println("Fatal: Evolve stopped.");
            return;
        }

        // make a note of the time
        startTime = System.currentTimeMillis();

        // tell the gp interface that we're ready to start
        gpinterface.onStartEvolution(this, p);

        // for coevolution problems...
        if (p instanceof CoevolutionProblem) {
            // Create the ADF nodes that will be coevolved. These ADF nodes are then inserted
            // into the GP params object as normal nodes so they can be accessed by the GP system
            // in the regular manner.            
            ((CoevolutionProblem) p).initialiseClassifiers(params);
        }

        // create an intial population
        population = new Individual[params.getPopulationSize()];
        new TreeBuilder().generatePopulation(population, params);

        // allow the problem to process the new generation
        p.processNewGeneration(population);

        // now crack on for however many generations it is
        for (int g = 0; g < params.getGenerations() && !stopFlag; g++) {

            // check nothing has gone wrong at the beginning of each generation
            if (fatal) {
                System.err.println("Fatal: Evolve stopped.");
                return;
            }

/*            Hashtable<Integer, Vector<Individual>> mappings = new Hashtable<Integer, Vector<Individual>>();
            Vector<Integer> lisps = new Vector<Integer>(population.size());
            for (int i = 0; i < population.size(); i++) {
                Individual individual = population.elementAt(i);
                String lisp = individual.toLisp();
                int hashcode = lisp.hashCode();
                if (!lisps.contains(hashcode))  {
                    lisps.add(hashcode);
                    Vector<Individual> individuals = new Vector<Individual>(5);
                    individuals.add(individual);
                    mappings.put(hashcode, individuals);
                } else {
                    mappings.get(hashcode).add(individual);
                }
            }*/

            //System.out.println("Pop size: " + population.size());
            //System.out.println("Unique trees: " + lisps.size());

            // now tell the gp interface that we're starting a new generation. Let the problem know too.
            gpinterface.onGenerationStart(g);
            p.onGenerationStart();

            // dynamic size limiting.
            // Proposed in paper "Reducing Bloat in GP" (Monsieurs/Flerackers, 2001)
            if (params.isDynamicSizeLimitingOn()) {
                if (bestIndividual == null) {
                    // set the size limit to the initial size
                    params.setCutoffSize(params.getDynamicSizeLimitingInitSize());
                } else {
                    // is the best individual smaller than the initial size
                    if (bestIndividual.getTreeSize() < params.getDynamicSizeLimitingInitSize()) {
                        // make the cutoff size double the best individual's tree size
                        params.setCutoffSize(bestIndividual.getTreeSize() * 2);
                    } else {
                        // make the cutoff size the size of the best individual x some weighting
                        params.setCutoffSize((int) (params.getDynamicSizeLimitingMaxNewWeight() * bestIndividual.getTreeSize()));
                    }
                }
            }

            // evaluate all the individuals. This is farmed out to a method in problem. In most situations
            // this is fine, but in some problems where evaluation takes place from human input, the hook
            // is there for it to be changed by overriding this metehod directly from the problem.
            totalEvaluations += p.evaluateIndividuals(population, this, params, gpinterface);

            // sometimes a fresh population can be requested by the problem. This essentially
            // resets the GP and starts again from scratch.
            if (requestFreshPopulation) {

                // stop asking
                requestFreshPopulation = false;

                gpinterface.onGenerationEnd(g);

                gpinterface.message("Generating fresh population");

                // recreate the initial population
                population = new Individual[params.getPopulationSize() + 10];
                new TreeBuilder().generatePopulation(population, params);

                // allow the problem to process the new generation
                p.processNewGeneration(population);

                // try to clear up the mess we are inevitably leaving in our wake
                System.gc();

            } else {

                // But most of the time we update the population by breeding:

                // arrange the evaluated population by fitness (for elitism, and to find best individual)
                Arrays.sort(population);

                // Get the best individual
                bestIndividual = p.getBestIndividual(population);

                /*if (params.isERCOptimisationEnabled()) {
                    try {
                        ERCOptimiser.optimise(bestIndividual, p, this);
                    } catch (FoundBestIndividualException e) {
                        // do nothing - it will be dealt with later.
                    }
                }*/

                // let the gp interface know what we've got. The graphical listener will kindly display
                // the individual as java code

                gpinterface.setBestIndividual(bestIndividual);
                gpinterface.onGenerationEnd(g);

                // Coevolution requires an additional couple of steps
                if (p instanceof CoevolutionProblem) {

                    // use the fitness data from the population to update the co-evolved ADFs
                    ((CoevolutionProblem) p).updateClassifierFitness(population);

                    // cause the ADFs themselves to be evolved
                    ((CoevolutionProblem) p).evolveClassifiers(params);

                }

                // if the best individual isn't perfect, and if we've still got generations to go...
                if (bestIndividual.getKozaFitness() > 0 && g < params.getGenerations() - 1) {

                    // this object makes deep copies of objects. We have to copy everything properly
                    // otherwise everything would go horribly wrong

                    // start generating the next generation
                    Individual[] nextGeneration = new Individual[params.getPopulationSize()];
                    int c = 0;

                 // add any elites (best in generation) first, these guys get injected straight into the next
                        // generation without any genetic freakery
                        for (int i = 0; i < params.getEliteCount(); i++) {
                            nextGeneration[c] = (copier.copyIndividual(population[i]));
                            c++;
                            OperationCounter.REPRODUCTION_COUNT++;
                        }

                    // use a selector to choose the parents.
                    Selector selector = params.getSelector();
                    selector.setPopulation(population);
                    selector.initialise(params);

                    try {

                        // BREEDING:
                        Crossover crossover = params.getCrossoverOperator();

                        // build the next generation

                        while (c < nextGeneration.length) {

                            treeIndex++;

                            // choose the tree index to mutate randomly
                            if (treeIndex > params.getTreeCount() - 1) {
                                treeIndex = 0;
                            }

                            // select the generic operator probabilistically.
                            int operator = params.getOperator();

                            // by default, select individuals from any niche
                            selector.setNiche(Selector.ANY_NICHE);

                            switch (operator) {
                                case GPParams.CROSSOVER:

                                    // choose the first parent
                                    Individual ind1 = getParent(selector, params);
                                    // make sure that the second parent is in the same niche
                                    selector.setNiche(ind1.getNicheID());
                                    // choose the second parent
                                    Individual ind2 = getParent(selector, params);
                                    Node[] offspring = crossover.produceOffspring(params, ind1.getTree(treeIndex), ind2.getTree(treeIndex));

                                    if (offspring != null) {
                                        for (int i = 0; i < offspring.length; i++) {

                                            // Create the full complement of trees
                                            Node[] trees = new Node[ind1.getTreeCount()];

                                            for (int j = 0; j < trees.length; j++) {
                                                if (j == treeIndex) {
                                                    trees[j] = offspring[i];
                                                } else {
                                                    // copy other trees from a parent
                                                    if (i == 0) {
                                                        trees[j] = ind1.getTree(j);
                                                    } else {
                                                        trees[j] = ind2.getTree(j);
                                                    }
                                                }
                                            }

                                            if (c < nextGeneration.length) {
                                                Individual child = new Individual(trees, ind1.getReturnType());
                                                nextGeneration[c] = child;
                                                c++;
                                            }

                                        }
                                    }

                                    break;

                                case GPParams.MUTATION:
                                    // mutation needs just one sacrificial lamb
                                    Individual ind3 = getParent(selector, params);

                                    // select the mutation operator probabilistically
                                    int mutationOperator = params.getMutationOperator();

                                    switch (mutationOperator) {
                                        case GPParams.POINT_MUTATION:
                                            Mutation.pointMutate(ind3.getTree(treeIndex), params);
                                            break;
                                        case GPParams.ERC_MUTATION:
                                            Mutation.mutateERCs(ind3.getTree(treeIndex), params);
                                            break;
                                        case GPParams.ERC_JITTERING:
                                            Mutation.jitterERCs(ind3.getTree(treeIndex), params);
                                            break;
                                    }

                                    nextGeneration[c] = ind3;
                                            c++;
                                    break;
                                case GPParams.REPRODUCTION:
                                    // lucky individuals who are reproduced get put straight into the next gen
                                    Individual ind4 = getParent(selector, params);
                                    nextGeneration[c] = ind4;
                                            c++;
                                    OperationCounter.REPRODUCTION_COUNT++;
                            }

                        }



                    } catch (FoundBestIndividualException e) {
                        // did we find the best invidual while optimising ERCs? It can happen...
                        gpinterface.setIdeal(true);
                        bestIndividual = e.getInd();
                        break;
                    }

                    if (params.getGenerationGapMethod() == GPParams.GENERATION_GAP_OVERLAP_OFF) {
                        // (N,N) evolution
                        // Children always completely replace the parents
                        // simple - just switch the populations and continue
                        population = nextGeneration;
                    } else {

                        // (N+N) evolution
                        // The parents compete with children to stay in the population
                        // This means we have to evaluate the children first
                        p.evaluateIndividuals(nextGeneration, this, params, gpinterface);

                        // create an intermediate population that we can sort
                        Individual[] intermediatePopulation = new Individual[population.length + nextGeneration.length];
                        System.arraycopy(population, 0, intermediatePopulation, 0, population.length);
                        System.arraycopy(nextGeneration, 0, intermediatePopulation, population.length, intermediatePopulation.length);
                        Arrays.sort(intermediatePopulation);

                        // cream off the best individuals from the intermediate population
                        for (int i = 0; i < params.getPopulationSize(); i++) {
                            population[i] = intermediatePopulation[i];
                        }

                    }


                } else {
                    // found the best individual?
                    if (bestIndividual.getKozaFitness() == 0) gpinterface.setIdeal(true);
                    gpinterface.onEndEvolution(g, params);
                    p.onFinish(bestIndividual, this);
                    break;
                }

            }

            //System.out.println("Gen " + g + " Evaluations avoided: "  + p.evaluationsAvoided);
            //p.evaluationsAvoided = 0;
            p.clearFitnessCache();

            // also - check if we are out of time
            if (params.getMaxTime() > 0) {
                long time = (System.currentTimeMillis() - startTime) / 1000;
                if (time >= params.getMaxTime()) {
                    stopFlag = true;
                }
            }

        }



        // record how long it took.
        totalTime = System.currentTimeMillis() - startTime;

        // if it stopped because of a user interaction - reflect this in the user interface.
        if (stopFlag) {
            gpinterface.onStopped();
        }

        // finish
        p.onFinish(null, this);
        gpinterface.onStopped();

    }

    /**
     * Gets statistics about the population.
     */
    public FastStatistics getPopulationSizeStatistics() {
        FastStatistics f = new FastStatistics();
        for (int i = 0; i < population.length; i++) {
            Individual individual = population[i];
            //System.out.println(individual.getTreeSize());
            f.addData(individual.getTreeSize());
        }
        return f;
    }

    /**
     * Returns the individual selected via the selection mechanism. Returned individual is a copy
     * of the original so it may be changed in any way without affecting the previous generation.
     *
     * @throws FoundBestIndividualException If the ERC optimiser is run and optimises to fitness of 0.
     */
    private Individual getParent(Selector s, GPParams params) throws FoundBestIndividualException {
        Individual i = copier.copyIndividual((Individual) s.select());
        if (params.isOptimisationEnabled()) {
            TreeOptimiser.optimise(i, params);
        }
        if (i == null) {
            fatal("Selector did not select individual successfully. Is t > 0?");
        }
        return i;
    }

    /**
     * Allows access to the best of generation.
     */
    public Individual getBestIndividual() {
        return bestIndividual;
    }


    /**
     * Gets the params file which contains all the GP settings
     */
    public GPParams getParams() {
        return this.params;
    }

    /**
     * Gets the problem that Evolve is trying to solve.
     */
    public Problem getProblem() {
        return p;
    }

    /**
     * Gets the listener
     */
    public GPActionListener getListener() {
        return gpinterface;
    }

    /**
     * Can be used by a problem if it encounters a serious problem (such as having no
     * training data, from which it cannot continue. Evolve sends this message to the interface
     * and then exits.
     *
     * @param message The error message to display
     */
    public void fatal(String message) {
        gpinterface.fatal(message);
        fatal = true;
    }

    /**
     * Allows access to the interface to print out or display a message of some kind.
     */
    public void message(String message) {
        gpinterface.message(message);
    }

    /**
     * Called when the GP system wants a new population. Used by GP with partial solutions.
     */
    public void requestFreshPopulation() {
        requestFreshPopulation = true;
    }

    /**
     * @return How long it took to evaluate the population. -1 if the population was not evaluated.
     */
    public long getTotalTime() {
        return totalTime;
    }

    public long getTimeElapsed() {
        return System.currentTimeMillis() - startTime;
    }

    /**
     * Returns the number of individuals evaluated.
     */
    public int getTotalEvaluations() {
        return totalEvaluations;
    }
}