/*************************************************************************
* Project: Library of Evolutionary Algoriths
*************************************************************************
* Author: Changhe Li & Ming Yang
* Email: changhe.lw@google.com Or yangming0702@gmail.com
* Language: C++
*************************************************************************
*  This file is part of EAlib. This library is free software;
*  you can redistribute it and/or modify it under the terms of the
*  GNU General Public License as published by the Free Software
*  Foundation; either version 2, or (at your option) any later version.
*************************************************************************/
// Created: 07 Nov 2011
// Last modified:

#ifndef GAPOPULATION_H
#define GAPOPULATION_H

#include "../Population.h"
#include "../Optima.h"
#include "../../Problems/DOPs/DynamicProblem.h"
#include "../../Problems/DOPs/BinaryDOP.h"

template<class T>
class GAPopulation : public Population<T>
{
    public:
        GAPopulation& operator=( GAPopulation& other){
            if(this==&other) return *this;
            Population<T>::operator=(other);
            m_sumFit=other.m_sumFit;
            m_sel=other.m_sel;
            m_tournSize=other.m_tournSize;
            gCopy(mv_mPool,other.mv_mPool, this->m_popsize);
            return *this;
        }
        GAPopulation():Population<T>(){
            setDefaultPar();
        }
        virtual ~GAPopulation(){
            mv_mPool.clear();
        }

        GAPopulation(const int rPopsize,bool mode=true):Population<T>(rPopsize,mode){
			mv_mPool.resize(this->m_popsize);
            setDefaultPar();
            mapObj2Fitness();

        }
        GAPopulation(GAPopulation<T> &s):Population<T>(s){
            m_sumFit=s.m_sumFit;
            m_sel=s.m_sel;
            m_tournSize=s.m_tournSize;
			mv_mPool.resize(this->m_popsize);
            gCopy(mv_mPool,s.mv_mPool, this->m_popsize);

        }
        GAPopulation(Group<T> &g):Population<T>(g){
			mv_mPool.resize(this->m_popsize);
            setDefaultPar();
            mapObj2Fitness();
        }
        GAPopulation(Chromosome & center, double radius,const int rPopsize,bool mode=true):Population<T>(center,radius,rPopsize,mode){
			mv_mPool.resize(this->m_popsize);
            setDefaultPar();
            mapObj2Fitness();
        }

        void setDefaultPar(){
            setSelStrategy(SEL_TOURNAMENT);
            setTournSize(3);
            double p;
            switch( Global::gp_problem->getEncoding()){
            case C_DECIMAL:
                p=1./Global::g_dimNumber;
                break;
            case C_BINARY:
               if(Global::gp_problem->getId()==Binary_DOP){
                p=1./dynamic_cast<BinaryDOP*>(Global::gp_problem)->getLength();
               }
                break;
            default:
                Throw(Runtime_error("mutation not defined!"));
                break;
            }

            setMutationProbability(p);
            setXoverProbability(0.6);
			setMutationStrategy(MUTAT_POLYNOMIAL);

        }
        void mapObj2Fitness(){
            // map objective function values to fitness values.
            // see Goldberg's book, page 75-76
            double maxboj=this->getMaxObj();
            double minobj=this->getMinObj();
            m_sumFit=0;
             for(int i=0;i<this->m_popsize;i++){
                if(Global::gp_problem->getProblemType()==MIN_OPT){
                    this->mp_pop[i].m_fitness=maxboj-this->mp_pop[i].m_pself.getObj();
                }else{
                    this->mp_pop[i].m_fitness=this->mp_pop[i].m_pself.getObj()+fabs(minobj);
                }
                m_sumFit+=this->mp_pop[i].m_fitness;
             }
        }

        void rouletteWheel( ){
        //---------------------------------------------------
        // roulette wheel selection
        // see Goldberg, "Genetic Algorithms in Search, Optimization,
        // and Machine Learning", 1989
        // the individuals that survive reproduction are placed in the mating pool

          double rndpoint, partsum;  // random point on wheel, partial sum
          int    j;                  // population index

          for( int i=0; i< this->m_popsize; i++ )
           {
             partsum = 0; j = -1;   // Zero out counter and accumulator
             // Wheel point calc. uses random number [0,1]
             rndpoint = Global::gp_uniformAlg->Next() * m_sumFit;
             // find wheel slot
             do {
               j++;
               partsum += this->mp_pop[i].m_fitness;
             } while( (partsum < rndpoint) && (j< this->m_popsize -1 ));
             mv_mPool[i] = j;
           }
        }

        void makeShuffle( int *shufflearray, const int n ){
        // tournament selection without replacement
        // make a random n-permutation of the numbers 0,1,2,...,n-1
          int i;

          // initialize
          for( i=0; i<n; i++ ) shufflearray[i] = i;
          // shuffle
          for( i=0; i<n-1; i++ )
            {
              int other = gRandInt( i, n-1 );
              // swap( shufflearray[other], shufflearray[i] );
              int temp = shufflearray[other];
              shufflearray[other] = shufflearray[i];
              shufflearray[i] = temp;
            }
        }

        // set things up for tournament selection without replacement
        void preTselectWoRep( int *shufflearray, int &pick )
        {
          pick = 0;
          makeShuffle( shufflearray, this->m_popsize );
        }

        // tournment selection without replacement
        int getTWinner( int *shuffle, int &pick )
        {


         if (pick+m_tournSize > this->m_popsize) preTselectWoRep( shuffle, pick );
          int winner = shuffle[pick];
          for( int i=pick+1; i< pick+m_tournSize; i++ )
            if (this->mp_pop[ shuffle[i] ].m_fitness >= this->mp_pop[ winner ].m_fitness)
              winner = shuffle[i];
          pick += m_tournSize;
          return winner;
        }

        // tournament selection without replacement
        // the individuals that survive reproduction are placed in the mating pool
        void tSelectWoRep(  )
        {
          int *shufflearray;
          shufflearray = new int[this->m_popsize];
          int pick;
          preTselectWoRep( shufflearray, pick );
          for( int i=0; i< this->m_popsize; i++ )
           {
             mv_mPool[i] =getTWinner( shufflearray, pick );
           }
          delete [] shufflearray;
        }

        void addIndividual( T &p){
            Population<T>::addIndividual(p);
            mv_mPool.resize(this->m_popsize);
        }
        void addIndividual(Population<T> &s){
             Population<T>::addIndividual(s);
            mv_mPool.resize(this->m_popsize);
        }
        void addIndividual(const int num, const bool mode=true){
            Population<T>::addIndividual(num,mode);
            mv_mPool.resize(this->m_popsize);
        }
        void addIndividual( Optima &l){
            Population<T>::addIndividual(l);
            mv_mPool.resize(this->m_popsize);
        }
		void addIndividual(const int num, const bool mode=true, const bool insize=false){
			Population<T>::addIndividual(num,mode,insize);
            mv_mPool.resize(this->m_popsize);
		}
        void deleteIndividual(const int *id,const int num){
            Population<T>::deleteIndividual(id,num);
            mv_mPool.resize(this->m_popsize);
        }
		void addIndividual( vector<T> &indis){
			Population<T>::addIndividual(indis);
            mv_mPool.resize(this->m_popsize);
		}

        void setTournSize(const int size){
            m_tournSize=size;
            if(m_sel==SEL_TOURNAMENT){
                size_t start, end;
                start=this->m_algPar.str().find("tournament size:");
                for(size_t i=start;i<this->m_algPar.str().size();i++){
                    if(this->m_algPar.str()[i]==';') {
                        end=i;
                        break;
                    }
                }
                stringstream ss;
                ss<<"tournament size:"<<m_tournSize<<"; ";
                if(start!=string::npos){
                    string result=this->m_algPar.str();
                    result.replace(start,end-start+1, ss.str());
                     this->m_algPar.str(result);
                }else this->m_algPar<<ss.str();
            }
        }
        void setSelStrategy(GASelectionStrategy sel){
            m_sel=sel;
            size_t start, end;
            start=this->m_algPar.str().find("Selection strategy:");
            for(size_t i=start;i<this->m_algPar.str().size();i++){
                if(this->m_algPar.str()[i]==';') {
                    end=i;
                    break;
                }
            }
            stringstream ss;
            switch(m_sel){
                case SEL_TOURNAMENT:
                ss<<"Selection strategy:tournament selection; ";
                break;
                case SEL_ROULETTE_WHEEL:
                ss<<"Selection strategy:roulette wheel selection; ";
                break;

            }
            if(start!=string::npos){
                string result=this->m_algPar.str();
                result.replace(start,end-start+1, ss.str());
                 this->m_algPar.str(result);
            }else this->m_algPar<<ss.str();
        }
        void setMutationProbability(const double rw){

            size_t start, end;
            start=this->m_algPar.str().find("Mutation probability:");
            for(size_t i=start;i<this->m_algPar.str().size();i++){
                if(this->m_algPar.str()[i]==';') {
                    end=i;
                    break;
                }
            }
            stringstream ss;
            ss<<"Mutation probability:"<<rw<<"; ";
            if(start!=string::npos){
                string result=this->m_algPar.str();
                result.replace(start,end-start+1, ss.str());
                 this->m_algPar.str(result);
            }else this->m_algPar<<ss.str();

            for(int i=0;i<this->m_popsize;i++) this->mp_pop[i].setMutationProbability(rw);
        }
		void setMutationStrategy(GAMutationStrategy s){

            size_t start, end;
            start=this->m_algPar.str().find("Mutation strategy:");
            for(size_t i=start;i<this->m_algPar.str().size();i++){
                if(this->m_algPar.str()[i]==';') {
                    end=i;
                    break;
                }
            }
            stringstream ss;
			switch(m_sel){
                case MUTAT_POLYNOMIAL:
                ss<<"Mutation strategy:polynomial distribution; ";
                break;
                case MUTAT_NORMAL:
                ss<<"Mutation strategy:normal distribution; ";
                break;

            }

            if(start!=string::npos){
                string result=this->m_algPar.str();
                result.replace(start,end-start+1, ss.str());
                 this->m_algPar.str(result);
            }else this->m_algPar<<ss.str();

            for(int i=0;i<this->m_popsize;i++) this->mp_pop[i].setMutationStrategy(s);
        }
        void setMutationStep(const double step){
             size_t start, end;
            start=this->m_algPar.str().find("Mutation step:");
            for(size_t i=start;i<this->m_algPar.str().size();i++){
                if(this->m_algPar.str()[i]==';') {
                    end=i;
                    break;
                }
            }
            stringstream ss;
            ss<<"Mutation step:"<<step<<"; ";
            if(start!=string::npos){
                string result=this->m_algPar.str();
                result.replace(start,end-start+1, ss.str());
                 this->m_algPar.str(result);
            }else this->m_algPar<<ss.str();

            for(int i=0;i<this->m_popsize;i++) this->mp_pop[i].setXoverProbability(step);
        }
        void setXoverProbability(const double rw){

            size_t start, end;
            start=this->m_algPar.str().find("Crossover probability:");
            for(size_t i=start;i<this->m_algPar.str().size();i++){
                if(this->m_algPar.str()[i]==';') {
                    end=i;
                    break;
                }
            }
            stringstream ss;
            ss<<"Crossover probability:"<<rw<<"; ";
            if(start!=string::npos){
                string result=this->m_algPar.str();
                result.replace(start,end-start+1, ss.str());
                 this->m_algPar.str(result);
            }else this->m_algPar<<ss.str();

            for(int i=0;i<this->m_popsize;i++) this->mp_pop[i].setXoverProbability(rw);
        }

        int evolve(){
            int i;
          //  selection
            switch(m_sel){
                case SEL_ROULETTE_WHEEL:
                rouletteWheel();
                break;
                case SEL_TOURNAMENT:
                tSelectWoRep();
                break;
            }

          for( i=0; i< this->m_popsize; i++ ){
            this->mp_pop[i].m_backup=this->mp_pop[i].m_pself;
            this->mp_pop[i].m_pself=this->mp_pop[mv_mPool[i]].m_pself;
          }

          //
          //  crossover
          //
          i=0;
          while (i<this->m_popsize){
              this->mp_pop[i].xover(this->mp_pop[i+1]);
              i+=2; // next pair of mates
        }
          //
          //  mutation
          //
          for( i=0; i< this->m_popsize; i++ ) this->mp_pop[i].mutate();
          //
          //  compute objective function value of offspring
          //
          for( i=0; i< this->m_popsize; i++ ){
            this->mp_pop[i].m_pself.evaluate();
            if(gIsTerminate()) return 0;
            if(gIsDynamicAlg()&&Global::gp_problem->getEvaluations()%(dynamic_cast<DynamicProblem*>(Global::gp_problem)->getChangeFre())==0){
                if(dynamic_cast<DynamicProblem*> (Global::gp_problem)->getFlagDimensionChange()) return 2;

                 if(this->msp_subPop.size()>1){
                    this->updateMemoryAll();
                }else{
                    this->updateMemory();
                }
                return 1;
            }

          }
		  int best=this->findBest();
		  if(best!=-1&&this->mp_pop[best].m_pself>this->m_best)		  this->m_best=this->mp_pop[best].m_pself;
          mapObj2Fitness();
          return 0;
    }

    public:
        double m_sumFit;
        int m_tournSize;
        GASelectionStrategy m_sel;    // selection strategy
        vector<int> mv_mPool;       // mating pool
    private:

};

#endif // GAPOPULATION_H
