#include <iostream>
#include <cmath>
#include "generic_individual.h"
#include "../rand/randomc.h"
#include "individual.h"
#include "population_block.h"
#include "fresh_list_block.h"
#include "population.h"

using namespace std;

/**
 * a constructor which prepares all the necessary structures for
 * a population of the given size
 */
population::population(int p_max_size) {
  size = 0;
  fresh = 0;
  max_size = p_max_size;

  ind_tab = new individual * [max_size];
  for(int i = 0; i < max_size; i++) ind_tab[i] = 0;
  fresh_lst = 0;
}

/**
 * a copy constructor
 */
population::population(population *p_parent) {
  size = 0;
  fresh = 0;
  max_size = p_parent->get_maximum_size();

  ind_tab = new individual * [max_size];
  for(int i = 0; i < max_size; i++) ind_tab[i] = 0;
  fresh_lst = 0;
}

/**
 * a destructor which frees all of the dynamically allocated memory
 */
population::~population() {
  // dispose of the individuals table
  for(int i = 0; i < max_size; i++) delete ind_tab[i];
  delete [] ind_tab;

  // dispose of the fresh list
  while(fresh_lst != 0) {
    fresh_list_block *tmp_blk = fresh_lst;
    fresh_lst = fresh_lst->get_next();
    delete tmp_blk;
  }
}

/**
 * recreates a random population of the maximum size possible;
 * size of individuals is specified by the parameter
 */
void population::refill(char p_ind_type, int p_ind_cells,
    float p_extr_ratio, float p_ones_ratio, RANDOM_GENERATOR *p_rg) {
  // clean the individuals table
  if(size > 0) {
    for(int i = 0; i < max_size; i++)
      delete ind_tab[i];

    size = 0;
  }

  // clean the fresh list
  refresh();

  // fill the population with random individuals
  int extremists = (int) floor(max_size * p_extr_ratio);
  int extr_indeces [extremists];
  int extr_idx = 0;

  quick_sort(random_tuple(extr_indeces, extremists, max_size, p_rg),
      extremists);

  for(int i = 0; i < max_size; i++) {
    individual *tmp_ind;

    // create a new individual ...
    if((extr_idx < extremists)
        && (i == extr_indeces[extr_idx])) {
      // this one's an extremist
      tmp_ind = new individual (p_ind_type, p_ind_cells, p_rg,
          p_ones_ratio);
      extr_idx++;
    }
    else tmp_ind = new individual (p_ind_type, p_ind_cells, p_rg);

    // ... and add it into the population
    add_individual(tmp_ind);
    delete tmp_ind;
  }
}

/**
 * regenerates the fresh list which is used to determine which
 * individuals haven't been accessed yet
 */
void population::refresh() {
  // delete the fresh list if it already exists ...
  while(fresh_lst != 0) {
    fresh_list_block *tmp_blk = fresh_lst;
    fresh_lst = fresh_lst->get_next();
    delete tmp_blk;
  }

  // ... and recreate it from scratch
  // (take note that the block with the highest index
  // comes first in the result list)
  for(int i = 0; i < size; i++)
    fresh_lst = new fresh_list_block (i, fresh_lst);

  fresh = size;
}

/**
 * copies an individual into a population
 */
void population::add_individual(individual *p_ind) {
  // check if the population is already full
  if(size == max_size) return;

  // copy in the given individual
  ind_tab[size] = new individual (p_ind);
  fresh_lst = new fresh_list_block (size, fresh_lst);
  size++;
  fresh++;
}

/**
 * copies out an individual denoted by it's individual table index
 * specified in the first parameter
 */
individual *population::pick_individual(int p_index) {
  // check if the population is empty
  // or its fresh list doesn't exist
  if((size == 0) || (fresh == 0)) return 0;

  // find a fresh block that corresponds
  // to the desired individual and delete it
  fresh_list_block *iter = fresh_lst;
  fresh_list_block *last_iter = iter;

  while((iter != 0)
      && (iter->get_table_index() != p_index)) {
    last_iter = iter;
    iter = iter->get_next();
  }

  // did we find it?
  if(iter != 0) {
    if(iter == fresh_lst) // removing the first block
      fresh_lst = iter->get_next();
    else last_iter->set_next(iter->get_next());

    delete iter;
    fresh--;

    // return a copy of the desired individual
    return new individual (ind_tab[p_index]);
  }
  else return 0;
}

/**
 * copies out the first fresh individual
 */
individual *population::pick_first_fresh() {
  // check if the population is empty
  // or its fresh list doesn't exist
  if((size == 0) || (fresh == 0)) return 0;

  // return a copy of the desired individual
  int tmp_idx = fresh_lst->get_table_index();

  fresh_list_block *tmp_blk = fresh_lst;
  fresh_lst = fresh_lst->get_next();
  delete tmp_blk;

  fresh--;
  return new individual (ind_tab[tmp_idx]);
}

/**
 * copies out a number of the fittest, cream of the crop
 * individuals without modifying the fresh list
 */
population_block *population::get_best(int p_count) {
  // check if the population is empty
  // or its fresh list doesn't exist
  if((size == 0) || (fresh == 0)) return 0;
  
  // create the structures needed to retain information
  // about the best ...
  int *indeces_tab = new int [p_count];
  float *fitness_tab = new float [p_count];

  // ... and initialize them
  for(int i = 0; i < p_count; i++) {
    indeces_tab[i] = DEFAULT_INDEX;
    fitness_tab[i] = DEFAULT_FITNESS;
  }

  // analyze the fresh list
  fresh_list_block *lst_iter = fresh_lst;

  while(lst_iter != 0) {
    int tmp_index = lst_iter->get_table_index();
    float tmp_fitness = ind_tab[tmp_index]->get_fitness();

    // find the best candidate to replace in the info tables
    int worst_pos = 0;
    float worst_fitness = fitness_tab[0];

    // an individual with the default fitness is automatically
    // considered as the best one to replace
    if(worst_fitness != DEFAULT_FITNESS)
      // try the remaining candidates
      for(int i = 1; i < p_count; i++) {
        if(fitness_tab[i] < worst_fitness) {
          worst_pos = i;
          worst_fitness = fitness_tab[i];
        }
      }

    // is the selected candidate really worse than
    // the currently inspected individual?
    if(worst_fitness < tmp_fitness) {
      indeces_tab[worst_pos] = tmp_index;
      fitness_tab[worst_pos] = tmp_fitness;
    }

    lst_iter = lst_iter->get_next();
  }

  // prepare the output data
  population_block *res_lst = 0;

  for(int i = 0; i < p_count; i++) {
    int tmp_index = indeces_tab[i];

    // check if this cell contains a valid index
    if((tmp_index >= 0) && (tmp_index < max_size))
      res_lst = new population_block (ind_tab[tmp_index], res_lst);
  }

  // destroy all of the info structures
  delete [] indeces_tab;
  delete [] fitness_tab;

  return res_lst;
}

/**
 * generates a random ordered tuple of integers from the given range
 */
int *population::random_tuple(int *p_buffer, int p_size,
    int p_available, RANDOM_GENERATOR *p_rg) {
  // check if we want the same amount of numbers as available
  // or even more than that
  if(p_size >= p_available) {
    for(int i = 0; i < p_size; i++) {
      if(i < p_available) p_buffer[i] = i;
      else p_buffer[i] = DEFAULT_INDEX;
    }
  }
  else {
    // fill the buffer with unique random indeces
    for(int i = 0; i < p_size; i++) {
      int tmp_index;
      bool used;

      do {
        tmp_index = p_rg->IRandom(0, p_available - 1);
        used = false;

        for(int j = 0; j < i; j++)
          used |= (p_buffer[j] == tmp_index);
      } while(used);

      p_buffer[i] = tmp_index;
    }
  }

  return p_buffer;
}

/**
 * sorts an array of integers with quick-sort
 */
int *population::quick_sort(int *p_buffer, int p_size) {
  if(p_size == 1) return p_buffer; // always sorted
  else {
    int pivot = p_buffer[p_size / 2];
    int left = 0;
    int right = p_size - 1;

    while(left <= right) {
      // if both values are placed wrong ...
      if((p_buffer[left] >= pivot)
          && (p_buffer[right] <= pivot)) {
        // ... switch them and update the left and right indeces
        int tmp_value = p_buffer[left];
        p_buffer[left++] = p_buffer[right];
        p_buffer[right--] = tmp_value;
      }
      // else continue searching for other wrong placed values
      else {
        if(p_buffer[left] < pivot) left++;
        if(p_buffer[right] > pivot) right--;
      }
    }

    // apply the same proc. on the buffer's partitions recursively
    if(right >= 0) quick_sort(p_buffer, (right + 1));
    if(left < p_size) quick_sort(p_buffer + left, p_size - left);

    return p_buffer;
  }
}

/**
 * copies out a random tuple of individuals
 */
population_block *population::pick_random_tuple(int p_size,
    RANDOM_GENERATOR *p_rg) {
  // check if the population is empty
  // or its fresh list doesn't exist
  if((size == 0) || (fresh == 0)) return 0;

  // get an indeces tuple and sort it, ...
  int *indeces_tab = new int [p_size];
  quick_sort(random_tuple(indeces_tab, p_size, fresh, p_rg), p_size);

  population_block *res_lst = 0;
  fresh_list_block *selector = fresh_lst;
  fresh_list_block *last_sel = selector;
  int last_index = 0;

  // ... remove the corresponding blocks from the fresh list
  // and make a copy of the individuals pointed to by these blocks
  for(int i = 0; i < p_size; i++) {
    int fresh_index = indeces_tab[i];

    // did we get a valid index?
    if(fresh_index != DEFAULT_INDEX) {
      // skip to the block denoted by the index
      while(last_index < fresh_index) {
        last_sel = selector;
        selector = selector->get_next();
        last_index++;
      }

      // store a copy of the individual it points to
      int tab_index = selector->get_table_index();
      res_lst = new population_block (ind_tab[tab_index], res_lst);

      // finally, remove the block
      if(selector == fresh_lst) {
        fresh_lst = selector->get_next();
        last_sel = fresh_lst;
        last_index++; // shift one position to the right
      }
      else last_sel->set_next(selector->get_next());

      delete selector;
      selector = last_sel; // fall back one position
      fresh--;
    }
  }

  // dispose of the indeces table
  delete [] indeces_tab;

  return res_lst;
}

/**
 * computes the total fitness of a population
 */
float population::get_total_fitness() {
  float res = 0;

  for(int i = 0; i < size; i++)
    res += ind_tab[i]->get_fitness();

  return res;
}

/**
 * computes the average fitness of a population
 */
float population::get_average_fitness() {
  float res = 0;

  for(int i = 0; i < size; i++)
    res += ind_tab[i]->get_fitness();

  return ((res == 0) ? res : (res / size));
}

/**
 * counts the number of distinct genotypes in a population;
 * if the argument is a positive number, the elite's share
 * in a population is counted as well
 */
float population::get_diversity(float& p_elite) {
  if(size != fresh) refresh();
  int count = 0; // a unique individuals counter
  int copies = 0; // a copy counter
  int elite = 0; // an elite individuals counter
  
  // process the fresh list
  while(fresh_lst != 0) {
    // get the first index
    int tmp_index = fresh_lst->get_table_index();
    count++;

    // it's the first copy itself
    copies = 1;

    // did we get an elite individual?
    if((float) tmp_index < p_elite) {
      elite++;
      copies = 0;
    }

    // delete the first block
    fresh_list_block *tmp_blk = fresh_lst;
    fresh_lst = fresh_lst->get_next();
    delete tmp_blk;

    // go through the rest of the blocks and delete all blocks
    // corresponding to the same individual
    tmp_blk = fresh_lst;
    fresh_list_block *tmp_last = tmp_blk;

    while(tmp_blk != 0) {
      if(ind_tab[tmp_blk->get_table_index()]->compare(
          ind_tab[tmp_index])) {
        // register the copy
        copies++;

        // did we find a copy of an elite individual?
        if((float) tmp_blk->get_table_index() < p_elite) {
          elite += copies;
          copies = 0;
        }

        // delete the block
        if(tmp_blk == fresh_lst) {
          fresh_list_block *tmp = fresh_lst->get_next();
          delete tmp_blk;
          tmp_blk = tmp;
          tmp_last = tmp;
          fresh_lst = tmp;
        }
        else {
          tmp_last->set_next(tmp_blk->get_next());
          delete tmp_blk;
          tmp_blk = tmp_last->get_next();
        }
      }
      else {
        // skip to the next block
        tmp_last = tmp_blk;
        tmp_blk = tmp_blk->get_next();
      }
    }
  }

  p_elite = ((p_elite > 0) ? ((float) elite / size) : p_elite);
  refresh();

  return ((float) count / size);
}

/**
 * prints a population to the standard output
 */
void population::print() {
  cout << "Population (S " << size << ", M "
    << max_size << ")" << endl;

  for(int i = 0; i < size; i++)
    ind_tab[i]->print();

  cout << endl;
}

