/*
  Example GA Code only - necessary header files not included.
  (c) Copyright 2002: Douglas B. Cameron

*/

#ifndef ReadBool_h
  #include "ReadBool.h"      
#endif
#include "GeneticA.h"
#include "ProfileTimers.h" 

#ifndef Pair_h                  
  #include "Pair.h"             // for PairOf<>
#endif
#ifndef RandomPermutation_h
  #include "RandomPermutation.h"
#endif
#ifndef Sort_h
  #include "Sort.h"  // for SortX<>()
#endif
#ifndef Sequence_h
  #include "Sequence.h" // for SetVector()
#endif

namespace GA {


  // ------ Individual ------------------------------------

    Fitness Individual::EvaluateFitness() { // returns cached value or calls _EvaluateFitness()
  profileTimers.Individual_EvaluateFitnessTimer.Start();    
      if (!possibleExactFitness.IsValid()) 
        possibleExactFitness = _EvaluateFitness();
  profileTimers.Individual_EvaluateFitnessTimer.Stop();    
      return possibleExactFitness->value;
      }

    override_ void Individual::ReadOn(istream& is) {
      // 3rd version, 0xa00c, saving fittness in hex for exact restore 10/12/01, 1/1/02 same but using Streamable2Eq
      // 2nd version, 0xa00b, added generationalAge 9/21/01, first version 0xa00a 2/19/01
      try {
        BaseT::ReadOn(is);
      } catch ( Version::Exception& ve ) {

        if ( ve.failedNumberRead==0xa00b ) { // - as double
          bool validFitness;
          ExactlyStreamed<Fitness> ef;
          is >> validFitness >> ef.value;
          if (validFitness)
            possibleExactFitness = ef;
          else
            possibleExactFitness.Invalidate();  
          is >> generationalAge;
        } else
          rethrow;
      }
      }

  // --------- GenerationInfo ---------------------

    GenerationInfo::GenerationInfo()
      : BaseT(&GenerationInfo::newIndividuals, &GenerationInfo::inbredCount, 201071537 ),
        newIndividuals(0), inbredCount(0), ageStats() {
      }
    override_ void GenerationInfo::ReadOn( istream& is ) {  // to catch old versions
      try {
        BaseT::ReadOn(is);
      } catch (Version::Exception& e ) {
        if (e.failedNumberRead==112271251) { // currently same format
          is >> newIndividuals >> inbredCount;
        } else 
          rethrow;
      }
      ageStats.Reset(); // client must repeat EachIndividual() call.
      }

  // --------- Population<IType> ---------------------

    template <class T>
    struct SortTraitsDecreasingFitness {		
      // Use to sort Array<> of Individuals for descending fitness.
      // T must have t.GetFitness()
      typedef T ElementT;
	    static bool Before( const T& t1, const T& t2 ) {
		    return t1.GetFitness()>t2.GetFitness();
		    }
	    static void Swap( T& t1, T& t2 ) { swap( t1, t2 );  }
	    static void Assign( T& t1, const T& t2 ) { t1 = t2; }
    };

  /* currently unused
  template <class IType>
  void Population<IType>::SortDescendingFitness() {
    SortX( set, SortTraitsDecreasingFitness<IType>() );
    // To avoid copying/moving many objects use indirect sort,
    // see Genetic\Tournament.h:OrganismSubsetWithFitness for basic idea.
    }
  */


  // ------ PopFitnesses ------------------------------------

    PopFitnesses::PopFitnesses() 
      : BaseT( &PopFitnesses::fitnessArray, &PopFitnesses::statsAccumulator, &PopFitnesses::generationAge, 201092025 ),
        fitnessArray(), statsAccumulator(), generationAge(0) { 
      }

    PopFitnesses::PopFitnesses( const PopFitnesses& sr ) 
      : BaseT( &PopFitnesses::fitnessArray, &PopFitnesses::statsAccumulator, &PopFitnesses::generationAge, 201092025 ),
        fitnessArray( MakeCopy, sr.fitnessArray ),  
        statsAccumulator( sr.statsAccumulator ),
        generationAge( sr.generationAge ) {
      }

    void PopFitnesses::operator= ( const PopFitnesses& sr ) {
      fitnessArray.Assign( MakeNewCopy, sr.fitnessArray );
      statsAccumulator = sr.statsAccumulator;
      generationAge = sr.generationAge;
      }

    void PopFitnesses::SetFrom( const AbstractPopulation& pop ) {
      statsAccumulator = StatsAccumulator();                                    // added 1/14/02
        // crude 'reset', this would slice if statsAccumulator type changed!
      fitnessArray.SetSize( pop.Size_Abstract() );
      for (int i=0; i<fitnessArray.Size(); ++i) {
        const Individual& indiv = pop.GetIndividual_Abstract(i);
        fitnessArray[i] = indiv.GetFitness();
        statsAccumulator << indiv.GetFitness();
      }
      generationAge = pop.NumGenerations();
      }

    void PopFitnesses::Reset() {
      fitnessArray.SetSize(0);
      statsAccumulator = StatsAccumulator(); 
        // crude 'reset', this would slice if statsAccumulator type changed!
      generationAge = 0;
      }

    override_ void PopFitnesses::ReadOn(istream& is) { // catch old versions
      // Version 201092025 - added generationAge
      // version 0xAAAA original
      try {
        BaseT::ReadOn(is);
      } catch (Version::Exception& e ) {
        if (e.failedNumberRead==0xAAA) {
          is >> fitnessArray >> statsAccumulator;
          generationAge = 0; 
        } else
          rethrow;
      }
      }

  // ---------- Tournament ----------------------
  
    // Needed for Tournament::Apply()

      struct Little {
        Little( int size, RRef<RandomIntSource> randomSource_ ) 
          : indices(size), randomSource(randomSource_) { 
          }

        void Little::Do( AbstractPopulation& pop, const Array<Fitness>& fitnesses ) {
          // Set values in indices[] before calling!
          // Using fitnesses[ indices[] ], replaces worst half of individuals pop[ indices[] ] using randomly
          // selected parents from best half. Uses AbstractPopulation::ReplaceIndividualUsingParents().
          // Uses local indices[] for indirection and sorting.

          // Sorts indices[] based on fitnesses[indices[]]
          TourSortTraitsDecreasingFitness traits( &fitnesses );
          SortX( indices, traits );

          // replace 2nd half sorted individuals using randomly selected parents from first half
          const int nKeep = indices.Size()/2;
          AlphaSquaredLib::Assert( nKeep>1, "Tournament:Little: Tournament too small." );
          for (int i=nKeep; i<indices.Size(); ++i) {  
            PairOf<int> ranIntPair = GetUniqueRandomIntPair0To( nKeep-1 );
            pop.ReplaceIndividualUsingParents( indices[i], indices(ranIntPair.first), indices(ranIntPair.second) );
          } 
          }
        private:
          struct TourSortTraitsDecreasingFitness {		
            // Use to sort indirect Array<> of Individuals for descending fitness.
            // Returns ordering of i's based on fitness of set(i)'s.
            TourSortTraitsDecreasingFitness( const Array<Fitness>* fitnesses_ )
              : fitnesses(*fitnesses_) { 
              }
            typedef int ElementT;
	          bool Before( const int& t1, const int& t2 ) const {
		          return fitnesses(t1) > fitnesses(t2);
		          }
	          static void Swap( int& t1, int& t2 ) { swap( t1, t2 );  }
	          static void Assign( int& t1, const int& t2 ) { t1 = t2; }
            private:
              const Array<Fitness>& fitnesses;
          };

          PairOf<int> GetUniqueRandomIntPair0To( int maxValue ) {
            // Return a random PairOf<int> with each unique and <=maxValue.
            // must be maxValue > 0 or endless loop
            int i1 = randomSource.Get0To( maxValue );
            int i2 = i1;
            while (i2==i1)   // other any but same 
              i2 = randomSource.Get0To( maxValue );
            return PairOf<int>(i1,i2);
            }

        public:
          Array<int>        indices; // retained structure only to avoid frequent creation
          RandomIntSource&  randomSource;
      };


    void Tournament::Apply( AbstractPopulation& pop, const Settings& settings ) {
      // Modifies an AbstractPopulation using tournament selection. Individuals are randomly grouped
      // into tournaments. In each tournament approximately half of worst individuals
      // are replaced using parents from better half.

      // make array of transformed fitnesses
      Array<Fitness> fitnesses( pop.Size_Abstract() ); 
      for (int i=0; i<fitnesses.Size(); ++i) {
        Fitness f = pop.GetIndividual_Abstract(i).GetFitness();
        fitnesses[i] = settings.TournamentFitnessTransform( f );
      }

      // make random permutation of index array - sequential 'settings.size' pieces make tournaments
      Vector<int> indices( pop.Size_Abstract() );
      SetVector( indices, Sequence<int>( StartStepCount, 0, 1, indices.Size() ) );
      RandomIntSource randomSource;
      randomSource.Randomize();
      RandomPermutation( &indices, randomSource );
      DebugAssert( indices.Min()>=0 and indices.Max()<pop.Size_Abstract() );

      // Do as many tournaments as possible in population
      const int tSize = settings.size;
      Little littleTournament(tSize,GrantRef(randomSource));
      for (int i=0; i<pop.Size_Abstract()-tSize+1; i+=tSize) {
        // pop[ indices[i..i+tSize-1] ] are tournament
        littleTournament.indices.CopyData( indices, i, tSize );
        littleTournament.Do( pop, fitnesses );
      }
      }


      /*
      // Size 4 optimization - not sure significant speedup. Use this if tournament speed is issue
      if (settings.size==4) { // can't resist this optimization
        for (int i=0; i+3<pop.Size_Abstract(); i+=4) {
          // pop[ indices[i..i+3] ] are tournament
          tourIndices.CopyData( indices, i, settings.size );
          Little4( indices(i), indices[i+1], indices[i+2], indices(i+3) );
        }
      } else { // general algorithm

        struct TourSortTraitsDecreasingFitness4 {		
          // Use to sort indirect Array<> of Individuals for descending fitness.
          // Returns ordering of i's based on fitness of set(i)'s.
          typedef Fitness Fitness4[4];
          TourSortTraitsDecreasingFitness4( const Fitness4* fa_ )
            : fa(*fa_) { 
            }
	        bool Before( int t1, int t2 ) const {
		        return fa[t1] > fa[t2];
		        }
	        static void Swap( int& t1, int& t2 ) { swap( t1, t2 );  }
          private:
            const Fitness4& fa;
        };

      void Little4( int i1, int i2, int i3, int i4 ) {
        // discard 2 worst, create from 2 best using recombination/crossover and mutation
    
        Fitness fa[4];
          fa[0] = pop.GetIndividual_Abstract(i1).GetFitness();    fa[1] = pop.GetIndividual_Abstract(i2).GetFitness();
          fa[2] = pop.GetIndividual_Abstract(i3).GetFitness();    fa[3] = pop.GetIndividual_Abstract(i4).GetFitness();
        int     ia[4];
          ia[0] = i1;  ia[1] = i2;   
          ia[2] = i3;  ia[3] = i4;

        // Sort ia[] based on fa[]
        TourSortTraitsDecreasingFitness4 traits( &fa );
        SortBySelection( ia, traits );

        for (int i=2; i<4; ++i)   // replace by one 
          if (Randomly(0.5f))
            pop.ReplaceIndividualUsingParents( ia(i), ia[0], ia[1] );
          else
            pop.ReplaceIndividualUsingParents( ia(i), ia[1], ia[0] );
        } end size 4 optimization */

}