package competitive.programming.genetic;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @author Manwe
 *
 * Class providing an implementation of a genetic algorithm.
 * 
 * @see <a href="https://en.wikipedia.org/wiki/Genetic_algorithm">Genetic algorithm</a>
 *
 * @param <Genotype>
 *  The class representing one candidate
 */
public class GeneticAlgorithm<Genotype> {
	//protected to be not random during unit testing.
    protected interface IShuffler<Genotype> {
        void shuffle(List<? extends Genotype> list);
    }

    private final FitnessFunction<Genotype> fitnessFunction;
    private final CandidateGenerator<Genotype> generator;
    private final CandidateMerger<Genotype> merger;
    private final CandidateMutator<Genotype> mutator;

    private final Map<Genotype, Double> cachedScores = new HashMap<>();
    private final List<Genotype> candidates = new ArrayList<>();

    private IShuffler<Genotype> shuffler = (c) -> Collections.shuffle(c);

    /**
     * Constructor
     * 
     * @param fitnessFunction
     * an implementation of the fitness function in charge of evaluating genotype quality
     * @param generator
     * an implementation of a generator in charge of randomly generating new candidates
     * @param merger
     * an implementation of a merger in charge of creating a new genotype from two already existing genotype
     * @param mutator
     * an implementation of a mutator in charge of creating a new genotype from an existing genotype but modifying some characteristics
     */
    public GeneticAlgorithm(FitnessFunction<Genotype> fitnessFunction, CandidateGenerator<Genotype> generator, CandidateMerger<Genotype> merger,
            CandidateMutator<Genotype> mutator) {
        this.fitnessFunction = fitnessFunction;
        this.generator = generator;
        this.merger = merger;
        this.mutator = mutator;
    }

    private void addRandomCandidates(int initialPoolSize) {
        for (int i = 0; i < initialPoolSize; i++) {
            candidates.add(generator.generateRandomly());
        }
    }

    
    /**
     * @return
     * The current best genotype that has been found during the iterations
     */
    public Genotype best() {
        return candidates.get(0);
    }

    private Map<Genotype, Double> computeScores() {
        final Map<Genotype, Double> scores = new HashMap<>();

        for (final Genotype candidate : candidates) {
            if (cachedScores.containsKey(candidate)) {
                scores.put(candidate, cachedScores.get(candidate));
            } else {
                double score = fitnessFunction.evaluate(candidate);
                scores.put(candidate, score);
                cachedScores.put(candidate, score);
            }
        }
        
        return scores;
    }

    private void dropUnselected(int selectionNumber) {
        final List<Genotype> retained = new ArrayList<>(candidates.subList(0, selectionNumber));
        candidates.clear();
        candidates.addAll(retained);
    }

    /**
     * Clear the candidate list and use the generator to generate a fixed number of genotypes
     * Do not use it between iterations, or you will lose all the previous iterations results!
     * @param initialPoolSize
     * the number of genotype to be generated
     */
    public void initialize(int initialPoolSize) {
        candidates.clear();
        addRandomCandidates(initialPoolSize);
    }

    /**
     * Performs a fixed number of iterations.
     * Each iteration will do successively:
     *    add iterationAdditionalRandomGenerated randomly generated candidates
     *    generate a mergedNumber from the merge process with two candidates that has been randomly selected
     * 	  mutate a mutatedNumber of randomly selected candidates
     *    evaluate all the instances quality and retain only the selectionNumber best
     * @param numberOfIterations
     * 		the number of iterations to perform
     * @param iterationAdditionalRandomGenerated
     * 		the number of fully random candidate that will be generated
     * @param selectionNumber
     *      the number of candidates that will be kept for the next iterations
     * @param mergedNumber
     * 		the number of candidate to be generated from a merge of randomly selected parents
     * @param mutatedNumber
     * 		the number of candidates to be generated by mutation of randomly selected candidates
     */
    public void iterate(int numberOfIterations, int iterationAdditionalRandomGenerated, int selectionNumber, int mergedNumber, int mutatedNumber) {
        for (int i = 0; i < numberOfIterations; i++) {
            runOneIteration(iterationAdditionalRandomGenerated, selectionNumber, mergedNumber, mutatedNumber);
        }
    }

    private void merge(int mergedNumber) {
        for (int i = 0; i < mergedNumber; i++) {
            final int firstIndex = (2 * i) % candidates.size();
            final int secondIndex = (2 * i + 1) % candidates.size();
            candidates.add(merger.merge(candidates.get(firstIndex), candidates.get(secondIndex)));
        }
    }

    private void mutate(int mutatedNumber) {
        for (int i = 0; i < mutatedNumber; i++) {
            final int index = i % candidates.size();
            candidates.add(mutator.mutate(candidates.get(index)));
        }
    }

    protected void printTo(PrintStream err) {
        err.println(candidates.size());
        err.println(candidates);
    }

    private void removeDuplicates() {
        final Set<Genotype> set = new HashSet<>(candidates);
        candidates.clear();
        candidates.addAll(set);
    }

    private double runOneIteration(int iterationAdditionalRandomGenerated, int selectionNumber, int mergedNumber, int mutatedNumber) {
        addRandomCandidates(iterationAdditionalRandomGenerated);
        shuffle();
        merge(mergedNumber);
        shuffle();
        mutate(mutatedNumber);
        removeDuplicates();
        final Map<Genotype, Double> scores = computeScores();
        sortByScore(scores);
        dropUnselected(selectionNumber);
        return scores.get(best());
    }

    protected void setShuffler(IShuffler<Genotype> shuffler) {
        this.shuffler = shuffler;
    }

    private void shuffle() {
        shuffler.shuffle(candidates);
    }

    private void sortByScore(final Map<Genotype, Double> scores) {
        Collections.sort(candidates, new Comparator<Genotype>() {
            @Override
            public int compare(Genotype o1, Genotype o2) {
                final double v1 = scores.get(o1);
                final double v2 = scores.get(o2);
                if (v1 > v2) {
                    return -1;
                } else if (v1 < v2) {
                    return 1;
                }
                return 0;
            }
        });
    }

	/**
	 * Allows you to add in the candidates an already defined genotype you already know is valuable
	 * Hint: this instance might come from previous iterations and you want to continue with it
	 * @param reference
	 * the instance to be added to the candidate list
	 */
	public void addReference(Genotype reference) {
		candidates.add(reference);
	}
}

@@ -1189,16 +1189,43 @@
 fle(c);%0D
+%0A%09private int evaluations;%0D
 %0A%0D%0A    /
@@ -2918,24 +2918,56 @@
 andidate);%0D%0A
+                evaluations++;%0D%0A
             
@@ -7608,12 +7608,73 @@
 e);%0D%0A%09%7D%0D
+%0A%0D%0A%09public int getEvaluations() %7B%0D%0A%09%09return evaluations;%0D%0A%09%7D%0D
 %0A%7D%0D%0A

Add evaluations counter in genetic algorithm