#include <iostream>
#include "genetic_operators.h"
#include "result_table.h"
#include "../rand/randomc.h"
#include "individual.h"
#include "population_block.h"
#include "population.h"
#include "evolution.h"

using namespace std;

/**
 * a constructor
 */
evolution::evolution(unsigned long p_rg_seed) {
  rg = new RANDOM_GENERATOR (p_rg_seed);
  rt = new result_table (EV_DEFAULT_GENERATIONS);
}

/**
 * implements tournament selection; fills up a new population with
 * the winners of a small tournaments held between a few randomly
 * picked individuals from an old population (and thus does not
 * depend on the fresh list orientation)
 */
population *evolution::tournament_selection(population *p_pop,
    population *p_res_pop, int p_pick_cnt) {
  // while the new population is not full, repeat ...
  while(!p_res_pop->is_full()) {
    // refresh the old population for a new tournament round
    p_pop->refresh();

    // hold a tournament round
    while(p_pop->fresh_left()
        && !p_res_pop->is_full()) {
      // pick a bunch of individuals from the old population, ...
      population_block *picked = p_pop->pick_random_tuple(
          p_pick_cnt, rg);

      // ... choose the best one, ...
      individual *best_ind = picked->get_individual();

      population_block *tmp_blk = picked;
      picked = picked->get_next();
      delete tmp_blk;

      while(picked != 0) {
        individual *tmp_ind = picked->get_individual();

        if(tmp_ind->get_fitness()
            > best_ind->get_fitness()) {
          delete best_ind;
          best_ind = tmp_ind;
        }
        else delete tmp_ind;

        tmp_blk = picked;
        picked = picked->get_next();
        delete tmp_blk;
      }

      // ... and add it to the new population
      p_res_pop->add_individual(best_ind);
      delete best_ind;
    }
  }

  // finally, return the new population
  return p_res_pop;
}

/**
 * implements roulette-wheel selection; fills up a new population
 * with the individuals selected by a roulette wheel from an old
 * population (the ball goes from the old population's tail because
 * of the fresh list orientation; this gives the elite
 * a disadvantage)
 */
population *evolution::roulette_selection(population *p_pop,
    population *p_res_pop) {
  // get the total fitness of the old population
  float tot_fitness = p_pop->get_total_fitness();

  // while the new population is not full, repeat ...
  while(!p_res_pop->is_full()) {
    // spin the wheel and determine the marble position
    float marble_pos = tot_fitness * rg->Random();

    // refresh the old population and select the corresponding
    // individual, ...
    p_pop->refresh();
    individual *res_ind = p_pop->pick_first_fresh();
    float part_fitness = res_ind->get_fitness();

    while((part_fitness < marble_pos)
        && p_pop->fresh_left()) {
      delete res_ind;
      res_ind = p_pop->pick_first_fresh();
      part_fitness += res_ind->get_fitness();
    }

    // ... and add it to the new population
    p_res_pop->add_individual(res_ind);
    delete res_ind;
  }

  // finally, return the new population
  return p_res_pop;
}

/**
 * prepares a mating population from a given population
 * using elitism and one of the selection mechanisms
 * (does not depend on the fresh list orientation)
 */
population *evolution::get_mating_population(population *p_pop,
    int p_elite_cnt, char p_sel_type, int p_pick_cnt) {
  // refresh the old population and select the elite individuals
  p_pop->refresh(); // might not be necessary
  population_block *elite = p_pop->get_best(p_elite_cnt);

  // create a new population and add in the elite
  population *res_pop = new population (p_pop);

  while(elite != 0) {
    individual *tmp_ind = elite->get_individual();
    res_pop->add_individual(tmp_ind);
    delete tmp_ind;

    population_block *tmp_blk = elite;
    elite = elite->get_next();
    delete tmp_blk;
  }

  // fill the rest of the new population from the old one
  // using the chosen selection mechanism
  switch(p_sel_type) {
    // tournament
    case SEL_TYPE_TOURNAMENT:
      res_pop = tournament_selection(p_pop, res_pop, p_pick_cnt);
      break;

    // roulette wheel
    case SEL_TYPE_ROULETTE:
      res_pop = roulette_selection(p_pop, res_pop);
      break;

    default:
      break;
  }

  // finally, return the new population
  return res_pop;
}

/**
 * breeds a new population from a mating population using
 * cross-over and mutation on the couples of individuals
 * from the mating population (goes through the old population from
 * its head and does not depend on the fresh list orientation)
 */
population *evolution::get_new_population(population *p_pop,
    int p_elite_cnt, char p_co_type, float p_cross_odds,
    float p_mutation_odds) {
  // refresh the old population and create an empty one
  p_pop->refresh(); // might not be necessary
  population *res_pop = new population (p_pop);
  int iter = 0;
  individual *last_ind = 0;

  // process the whole old population
  while(p_pop->fresh_left()) {
    // pick an individual
    individual *tmp_ind = p_pop->pick_individual(iter);

    // process the individual: is it an elite individual?
    // (elite is usually stored at the beginning of a mating pop.)
    if(iter < p_elite_cnt) {
      // copy the individual referenced to by the iterator
      // directly into the new population
      res_pop->add_individual(tmp_ind);
      delete tmp_ind;
    }
    else {
      // cross-breed this individual with the last one picked
      if(last_ind == 0) last_ind = tmp_ind;
      else {
        // get offsprings
        population_block *tmp_blk = 0;

        // will cross-over take place?
        if(rg->Random() < p_cross_odds)
          tmp_blk = genetic_operators::cross_over(p_co_type,
              last_ind, tmp_ind, rg);
        else {
          tmp_blk = new population_block (last_ind, tmp_blk);
          tmp_blk = new population_block (tmp_ind, tmp_blk);
        }

        // add the offsprings into the new population
        while(tmp_blk != 0) {
          individual *tmp_offspr = tmp_blk->get_individual();

          // will mutation take place?
          if(rg->Random() < p_mutation_odds) {
            individual *tmp_mutated = genetic_operators::mutate(
                tmp_offspr, rg);

            delete tmp_offspr;
            res_pop->add_individual(tmp_mutated);
            delete tmp_mutated;
          }
          else {
            res_pop->add_individual(tmp_offspr);
            delete tmp_offspr;
          }

          population_block *tmp = tmp_blk;
          tmp_blk = tmp_blk->get_next();
          delete tmp;
        }

        // delete the parents
        delete last_ind;
        last_ind = 0;
        delete tmp_ind;
      }
    }

    iter++;
  }

  // did we get a single individual at the end of the mating?
  if(last_ind != 0) {
    // add it to the new population if we still can
    if(!res_pop->is_full()) res_pop->add_individual(last_ind);
    delete last_ind;
  }

  // finally, return the new population
  return res_pop;
}

/**
 * evolves a population for a number of generations
 */
individual *evolution::get_solution(int p_pop_size, char p_ind_type,
    int p_ind_cells, float p_elite_ratio, float p_extr_ratio,
    float p_ones_ratio, int p_pick_cnt, float p_cross_odds,
    float p_mutation_odds, int p_gen_cnt, char p_sel_type,
    char p_co_type, bool p_verbose) {
  // create and init a population
  int elite_cnt = (int) floor(p_pop_size * p_elite_ratio);
  population *pop = new population (p_pop_size);
  pop->refill(p_ind_type, p_ind_cells, p_extr_ratio,
      p_ones_ratio, rg);

  // create structures for a simple automaton used to control
  // the number of generations dynamically
  float step_ref = DEFAULT_FITNESS;
  int step_cnt = 1;

  // evolve for a number of generations
  for(int clock = 0; clock < p_gen_cnt; clock++) {
    // print the current population's statistics
    float tmp_ref = print_generation(p_verbose, clock, pop,
        elite_cnt);

    // every different value is stored and the counter reset
    if(step_ref != tmp_ref) {
      step_ref = tmp_ref;
      step_cnt = 1;
    }
    else step_cnt++; // the same value increments the counter

    // if the counter reaches a predefined value, stop the evolution
    if(step_cnt == EV_STALE_GENERATION) break;

    // prepare a mating population
    population *mating_pop = get_mating_population(pop, elite_cnt,
        p_sel_type, p_pick_cnt);

    delete pop;

    // breed a new population from the mating one
    population *new_pop = get_new_population(mating_pop, elite_cnt,
        p_co_type, p_cross_odds, p_mutation_odds);

    delete mating_pop;

    // replace the old population with the new one
    pop = new_pop;
  }

  // select the best individual from the last population
  // as a solution
  population_block *best_blk = pop->get_best(1);
  individual *best_ind = best_blk->get_individual();
  delete best_blk;

  // delete the population and return the solution
  delete pop;

  return best_ind;
}

/**
 * prints all concievable information on a given generation
 * to the standard output
 */
float evolution::print_generation(bool p_verbose, int p_num,
    population *p_pop, int p_elite_cnt) {
  // get the statistics
  population_block *best_blk = p_pop->get_best(1);
  individual *best_ind = best_blk->get_individual();
  delete best_blk;

  float tmp_best = best_ind->get_fitness();
  delete best_ind;

  float tmp_average = p_pop->get_average_fitness();
  float tmp_elite = (float) p_elite_cnt;
  float tmp_diversity = p_pop->get_diversity(tmp_elite);

  // print the statistics if desirable
  if(p_verbose) {
    cout << "  ";
    cout.width(4);
    cout << p_num << ":\t";

    cout << "BF ";
    cout.width(10);
    cout << tmp_best << '\t';

    cout << "AF ";
    cout.width(10);
    cout << tmp_average << '\t';

    cout << "DIV ";
    cout.width(10);
    cout << tmp_diversity << '\t';

    cout << "ELT ";
    cout.width(10);
    cout << tmp_elite << endl;
  }

  // update the result table
  rt->update_row(p_num, tmp_average, tmp_best, tmp_diversity,
      tmp_elite);

  // finally, return the best fitness
  return tmp_best;
}

/**
 * resets the result table
 */
void evolution::reset_results() {
  // just a quick fix:
  delete rt;
  rt = new result_table (EV_DEFAULT_GENERATIONS);
}

/**
 * flushes the result table to a file
 */
void evolution::flush_results(char *p_filename) {
  if(p_filename != 0)
    rt->print(p_filename);
  else rt->print();
}

