/*********************************************************************
 * This file is part of the cpplibs suite.
 *
 * Copyright (C) 2001 Topi Mäenpää
 * All rights reserved.
 *
 * This program is free software. You can redistribute and/or modify
 * it under the terms of the free software licence found in the
 * accompanying file "COPYING". The licence terms must always be
 * redistributed with this source file. The above copyright notice
 * must be reproduced in all modified and unmodified copies of this
 * source file.
 *
 * $Revision: 1.5 $
 *********************************************************************/

#ifndef _GENETICENGINE_H
#define _GENETICENGINE_H

#include <List.h>
#include <Matrix.h>
#include <Heap.h>
#include <Event.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include "Individual.h"

namespace prapi { namespace ga {
	/**
	 * A class that is used to notify listeners about the progress of an
	 * evolution.
	 **/
	template <class T> class EvolutionEvent
	{
	public:
		EvolutionEvent(int index, util::List<Individual<T> >& pop) :
			generationIndex(index), population(pop) {}
		
		/**
		 * The index of the generation that was just produced. Indices
		 * start from zero.
		 **/
		int generationIndex;
		/**
		 * A reference to the current population.
		 **/
		util::List<Individual<T> >& population;
	};

	
	/**
	 * An interface for different survivor selection schemes.
	 **/
	template <class T=double> class SurvivorSelector
	{
	public:
		/**
		 * Select some fit individuals that survive to the next
		 * generation.
		 *
		 * @param from the list from which individuals are to be selected.
		 *        createNextGeneration always sorts <i>from</i> prior to
		 *        calling this method (ascending fitness order).
		 * @param to the list that stores the selected individuals
		 **/
		virtual void selectSurvivors(const util::List<Individual<T> >& from, util::List<Individual<T> >& to) = 0;
	};

	/**
	 * RankSelector implements tye SurvivorSelection intereface by a
	 * rank order selection scheme.
	 **/
	template <class T=double> class RankSelector : public SurvivorSelector<T>
	{
	public:
		/**
		 * Create a new RankSelector with the given survivor selection
		 * probability and survival rate. If you are using a
		 * CrossingOverBreeder or similar, you need to make sure that the
		 * selection rates of these objects sum up to unity. Otherwise
		 * your population will either shrink or grow.
		 **/
		RankSelector(double selectionProbability = 0.25, double rate = 0.2) :
			survivorSelectionProbability(selectionProbability), survivalRate(rate) {}
		/**
		 * Select some fit individuals that survive to the next
		 * generation. This implementation selects
		 * <i>survivalRate*from.getLength()</i> individuals from
		 * <i>from</i> using a rank selection method. That is, the most
		 * fit individual is selected to the next generation with the
		 * probability <i>selectionProbability</i> in the first round. If
		 * it is not selected, the second most fit individual is selected
		 * with the same probability. This continues until an individual
		 * is selected. The same procedure is repeated for the remaining
		 * individuals until the needed number of individuals is selected.
		 *
		 * @param from the list from which individuals are to be selected.
		 *        createNextGeneration always sorts <i>from</i> prior to
		 *        calling this method (ascending fitness order).
		 * @param to the list that stores the selected individuals
		 **/
		virtual void selectSurvivors(const util::List<Individual<T> >& from, util::List<Individual<T> >& to);
		/**
		 * A value in the range [0,1] that tells how probable it is for
		 * the fittest individual to be first selected as a survivor.
		 **/
		double survivorSelectionProbability;
		/**
		 * A value in the range [0,1] that indicates the fraction of a
		 * population that survives to the next generation.
		 **/
		double survivalRate;
	};

	/**
	 * An interface for different offspring production schemes.
	 **/
	template <class T=double> class Breeder
	{
	public:
		/**
		 * Select some pairs of parents and breed them to produce some
		 * offspring.
		 *
		 * @param from the list from which individuals are to be selected.
		 *        createNextGeneration always sorts <i>from</i> prior to
		 *        calling this method (ascending fitness order).
		 * @param to the list that stores the selected individuals
		 **/
		virtual void createChildren(const util::List<Individual<T> >& from, util::List<Individual<T> >& to) = 0;
	};

	/**
	 * CrossingOverBreeder randomly takes some individuals from a
	 * population, mates them using crossing over, and produces two
	 * offspring for each pair of parents.
	 **/
	template <class T=double> class CrossingOverBreeder : public Breeder<T>
	{
	public:
		/**
		 * Create a new CrossingOverBreeder with the given parent
		 * selection probability and selection rate. If you are using a
		 * RankSelector or similar, you need to make sure that the
		 * selection rates of these objects sum up to unity. Otherwise
		 * your population will either shrink or grow.
		 **/
		CrossingOverBreeder(double selectionProbability = 0.25, double rate = 0.8) :
			parentSelectionProbability(selectionProbability), parentSelectionRate(rate) {}
		/**
		 * Select <i>parentSelectionRate/2*from.getLength()</i> pairs of
		 * parents and breed them producing two children for each pair.
		 * Parents are selected using a rank selection method.
		 *
		 * @param from the list from which individuals are to be selected.
		 *        createNextGeneration always sorts <i>from</i> prior to
		 *        calling this method (ascending fitness order).
		 * @param to the list that stores the selected individuals
		 **/
		virtual void createChildren(const util::List<Individual<T> >& from, util::List<Individual<T> >& to);
		/**
		 * Mate two individuals and produce some offspring. This
		 * implementation makes a random number of crossing overs to the
		 * genes of the parents and returns a list containing two new
		 * individuals. You may want to override this method to produce
		 * different mating schemes.
		 *
		 * @param parent1 the first parent
		 * @param parent2 the second parent
		 * @return a list containing the children bred
		 **/
		virtual util::List<Individual<T> > mate(const Individual<T>& parent1, const Individual<T>& parent2);

		/**
		 * A value in the range [0,1] that tells how probable it is for
		 * the fittest individual to get selected for mating first.
		 **/
		double parentSelectionProbability;
		/**
		 * A value in the range [0,1] that tells how large fraction of the
		 * population is selected for mating.
		 **/
		double parentSelectionRate;
	};

	/**
	 * FitnessCalculator calculates fitness for each individual in a
	 * population.
	 **/
	template <class T> class FitnessCalculator
	{
	public:
		/**
		 * Calculate a fitness value for each individual in a population.
		 * There is no default implementation for this method, and
		 * subclasses must override it. All old fitness values in each
		 * individual must be replaced.
		 **/
		virtual void calculateFitness(util::List<Individual<T> >& population) = 0;
	};
	
	/**
	 * Mutator is responsible for making mutations in a population.
	 **/
	template <class T=double> class Mutator
	{
	public:
		/**
		 * Create a new mutator with the given mutation probability.
		 **/
		Mutator(double probability=0.02) : mutationProbability(probability) {}
		/**
		 * Make random mutations to a population. The default
		 * implementation loops through all individuals in a population
		 * and randomly mutates some genes in each.
		 **/
		virtual void mutate(util::List<Individual<T> >& population);
		/**
		 * Mutate a single "synthetic base pair". The default
		 * implementation returns T(drand48()).
		 *
		 * @param value the old value of a gene slot
		 * @return new, mutated value for the gene slot
		 **/
		virtual T mutate(T value) { return T(drand48()); }
		/**
		 * A value in the range [0,1] indicating the probability for a
		 * gene to change when mutating a population.
		 **/
		double mutationProbability;
	};

	/**
	 * GeneticEngine loops through a predefined number of evolution
	 * cycles by creating a new population from an old one.
	 **/
	template <class T=double> class GeneticEngine : public util::EventSource<EvolutionEvent<T> >
	{
	public:
		/**
		 * Create a new genetic engine with the given number of
		 * generations and a set of pluggable behaviors. If
		 * <i>generations</i> is -1, the engine will run forever unless
		 * explicitly stopped.
		 **/
		GeneticEngine(int generations,
									FitnessCalculator<T>& calculator,
									Mutator<T>& mutator,
									SurvivorSelector<T>& selector,
									Breeder<T>& breeder) :
			_iGenerations(generations), _bRunning(false),
			_fitnessCalculator(calculator), _mutator(mutator),
			_survivorSelector(selector), _breeder(breeder) {}

		virtual ~GeneticEngine() {};
		
		/**
		 * Start the evolution. Until the maximum generation count is
		 * reached or the evolution is explicitly stopped, the engine will
		 * create new generations as follows.
		 * <ol>
		 * <li>Calculate the fitness of each individual by calling the
		 * calculateFitness method of the internal fitness calculator.
		 * <li>Fire an evolution event that informs interested listeners
		 * about the state of the evolution
		 * <li>Ff the evolution is not stopped and the generations is not
		 * the last one, create a new generation, mutate it and proceed to
		 * a new cycle.
		 * </ul>
		 *
		 * @param population the population to evolve. Note that the contents
		 *        of this population change for each generation.
		 **/
		void start(util::List<Individual<T> >& population);

		/**
		 * Create a new generation of individuals by replacing the current
		 * contents of the population by new individuals. The default
		 * implementation first sorts the population in ascending fitness
		 * order and calls the selectSurvivors method in the internal
		 * SurvivorSelector. Second, the age of each individual is
		 * incremented by one. Finally, the internal Breeder is required
		 * to produce some new offspring.
		 *
		 * @param population the population that is to be converted to a
		 * new generation
		 * @param index the index of the generation
		 **/
		virtual void createNextGeneration(util::List<Individual<T> >& population, int index);

		/**
		 * Stop the evolution. The evolution will stop after the currently
		 * generating population has finished.
		 **/
		void stop(void) { _bRunning = false; }

	private:
		int _iGenerations;
		bool _bRunning;

		FitnessCalculator<T>& _fitnessCalculator;
		Mutator<T>& _mutator;
		SurvivorSelector<T>& _survivorSelector;
		Breeder<T>& _breeder;
	};

	template <class T> void GeneticEngine<T>::start(util::List<Individual<T> >& population)
	{
		_bRunning = true;
		int i = 0;
		srand48(time(NULL));
		while (_bRunning &&
					 (i < _iGenerations || _iGenerations == -1))
			{
				_fitnessCalculator.calculateFitness(population);
				fireEvent(new EvolutionEvent<T>(i,population));
				if (i != _iGenerations-1 && _bRunning) //do not mutate last or after stopping an evolution
					{
						createNextGeneration(population,i);
						_mutator.mutate(population);
					}
				i++;
			}
	}
	
	template <class T> void RankSelector<T>::selectSurvivors(const util::List<Individual<T> >& from,
																													 util::List<Individual<T> >& to)
	{
		int len=from.getLength();
		bool selected[len];
		memset(selected,0,len*sizeof(bool));
		//cerr << "Selecting " << int(survivalRate*len) << " individuals out of " << len << endl;
		for (int i=0;i<survivalRate*len;i++)
			{
				bool chosen = false;
				do
					{
						for (int j=len;j--;)
							{
								if (!selected[j] && drand48() < survivorSelectionProbability)
									{
										to += from.getElementAt(j);
										selected[j] = true;
										chosen = true;
										break;
									}
							}
					} while (!chosen);
			}
	}

	template <class T> void GeneticEngine<T>::createNextGeneration(util::List<Individual<T> >& population, int index)
	{
		util::Heap<Individual<T> > sorted(population.getLength());
		sorted.addElements(population);
		sorted.sort();
		population.clear();
		
		//First, select the individuals that survive to the next generation
		_survivorSelector.selectSurvivors(sorted,population);

		//cerr << "Survivors selected" << endl;

		//Make them one generation older
		for (int i=population.getLength();i--;)
			population[i].age++;

		//Create some new children
		_breeder.createChildren(sorted,population);
	}

	template <class T> util::List<Individual<T> > CrossingOverBreeder<T>::mate(const Individual<T>& parent1, const Individual<T>& parent2)
	{
		int len = parent1.getLength();
		util::List<Gene<T> > genotype1(parent1), genotype2(parent2), tmp1(len), tmp2(len);
		
		int crossOvers = (int)(drand48()*(len-2))+1;
		for (int i=0;i<crossOvers;i++)
			{
				int crossOverPoint = ((int)(drand48()*(len-1))+1);
				tmp1 = genotype1(0,crossOverPoint) + genotype2(crossOverPoint,len-crossOverPoint);
				tmp2 = genotype2(0,crossOverPoint) + genotype1(crossOverPoint,len-crossOverPoint);
				genotype1 = tmp1;
				genotype2 = tmp2;
			}

		Individual<T> child1(genotype1),child2(genotype2);
		util::List<Individual<T> > result(2);
		result += child1;
		result += child2;
		return result;
	}

	template <class T> void CrossingOverBreeder<T>::createChildren(const util::List<Individual<T> >& from,
																																 util::List<Individual<T> >& to)
	{
		int len = from.getLength();
		util::Matrix<bool> selected(len);

		//Allow no mating with oneself.
		for (int i=0;i<len;i++)
			selected(i,i) = true;

		//We select n different pairs
		for (int i=0;i<parentSelectionRate*len/2;i++)
			{
				Individual<T> mom, dad;

				//Let's choose dad first
				int dadIndex = -1;
				do
					{
						for (int j=len;j--;)
							{
								if (drand48() < parentSelectionProbability)
									{
										int k;
										//Check that this dad has an unused pair
										for (k=len;k--;)
											if (!selected(j,k))
												break;

										//If yes, we can proceed to the selection of mother
										if (k >= 0)
											{
												dad = from.getElementAt(j);
												dadIndex = j;
												break;
											}
									}
							}
					} while (dadIndex == -1);
				
				//Then we choose mom
				int momIndex = -1;
				do
					{
						for (int j=len;j--;)
							{
								if (!selected(dadIndex,j) && drand48() < parentSelectionProbability)
									{
										momIndex = j;
										mom = from.getElementAt(j);
										selected(dadIndex,j) = true;
										selected(j,dadIndex) = true;
										break;
									}
							}
					} while (momIndex == -1);

				//Finally, we mate the two selected parents and add the produced children
				//to the result list.
				to.addElements(mate(dad,mom));
			}
	}
	
	template <class T> void Mutator<T>::mutate(util::List<Individual<T> >& population)
	{
		for (int p=population.getLength();p--;)
			{
				Individual<T> &individual = population[p];
				for (int i=individual.getLength();i--;)
					{
						for (int j=individual[i].getLength();j--;)
							if (drand48() < mutationProbability)
								individual[i][j] = mutate(individual[i][j]);
					}
			}
	}
}}

#endif