//filename:   hw1Class.cpp

#include<fstream.h> 
#include<iostream.h> 
#include<stdlib.h> 
#include<time.h> 

double eval(int *);

//--------------------------------------------------------------
//     Class: for single chromosome:
//        declaration and definition
//--------------------------------------------------------------
class Chromosome {

public:

  int *chrom;
  double fitness;

  Chromosome(int chromSize);
  Chromosome() { };
  void initialize(int);

private:

  int size;

};
/*
Chromosome::Chromosome(int chromSize)
{

  size = chromSize;
  chrom = new int [chromSize];

}
*/
void Chromosome::initialize(int chromSize)
{
  
  size = chromSize;
  chrom = new int [chromSize];

  for (int i = 0; i < size; i++)
    chrom[i] = rand() % 2;

  return;

}



//--------------------------------------------------------------
//     Class: for whole population
//        declaration and definition
//--------------------------------------------------------------

class Population {

public:

  Population(int, int, int);
  void initialize(double, double);
  

  //private:

  Chromosome *oldChroms;
  Chromosome *newChroms;
  Chromosome *temp;            //for temporary use

  Chromosome maxChrom;
  double maxFitness;

  double currentMaxFit;
  int currentMaxChromIndex;

  int chromLength;
  int popSize;
  int totalNumGenerations;
  int currentGenNum;
  
  double sumFitness;
  double avgFitness;

  double crossProbability;
  double mutateProbability;

  void swapPop();
  int flip(double);
  void mutate(Chromosome *);
  void evaluate();
  void statistics();
  int roulette();
  void crossover(int, int, int, int);
  void generateNewPop();
  void update();
  void evolution();


};

Population::Population(int chromL, int popS, int totalNumGens)
{

  int i;

  oldChroms = new Chromosome [popS];
  newChroms = new Chromosome [popS];
  totalNumGenerations = totalNumGens;

  popSize = popS;
  chromLength = chromL;
  
}

void Population::initialize(double crossP, double mutateP)
{

  int i;
  
  srand(time(0));
  srand48(time(0));

  crossProbability = crossP;
  mutateProbability = mutateP;

  for (i = 0; i < popSize; i++) {
    oldChroms[i].initialize(chromLength);
    newChroms[i].initialize(chromLength);  
  }

  maxChrom.initialize(chromLength);
  maxFitness = 0.0;

  currentMaxFit = 0.0;
  currentMaxChromIndex = -1;

  currentGenNum = 0;

  sumFitness = 0.0;
  avgFitness = 0.0;

  
  return;
}

void Population::swapPop()
{

  temp = oldChroms;
  oldChroms = newChroms;
  newChroms = temp;

  return;

}


void Population::evaluate()
{
  for (int i = 0; i < popSize; i++)
    oldChroms[i].fitness = eval(oldChroms[i].chrom);

}


//calculate sumFitness avgFitness, and 
//   the maxFitness and its corresponding
//   chromosome
void Population::statistics()
{
  int i;

  currentMaxFit = 0.0;
  currentMaxChromIndex = -1;
  sumFitness = 0.0;
  avgFitness = 0.0;

  for (i = 0; i < popSize; i++) {
    sumFitness += oldChroms[i].fitness;
    if (oldChroms[i].fitness > currentMaxFit) {
      currentMaxFit = oldChroms[i].fitness;
      currentMaxChromIndex = i;
    }
  }

  avgFitness = sumFitness / popSize;

}

void Population::update()
{
  if (currentMaxFit > maxFitness) {
    maxFitness = currentMaxFit;
    maxChrom.fitness = maxFitness;
    cout<<"Fitness changed at generation = "<<currentGenNum;
    cout<<"       fitness =  "<<maxFitness<<" the sequence is : "<<endl;
    for (int i = 0; i < chromLength; i++) {
      maxChrom.chrom[i] = oldChroms[currentMaxChromIndex].chrom[i];
      cout<<maxChrom.chrom[i];
    }
    cout<<endl;
  }
}
int Population::flip(double prob)
{

  if (prob == 1.0)
    return 1;
  else
    return (drand48() <= prob);

}

void Population::mutate(Chromosome *chr)
{
  if (flip(mutateProbability)) {
    int k;
    k = rand() % chromLength;
    chr->chrom[k] = (chr->chrom[k] + 1) % 2;
  }
}


int Population::roulette()
{
  int k;
  double hitSum, randNum, accumulateSum;

  hitSum = drand48() * sumFitness;
  accumulateSum = 0.0; 
  k = 0;

  while ((k < popSize) && (accumulateSum <= hitSum)) {
    k++;
    accumulateSum += oldChroms[k].fitness;
  }

  k--;
  
  return k;

}

void Population::crossover(int p1, int p2, int c1, int c2)
{
  int i, k;

  if (flip(crossProbability)) {
    k = rand() % chromLength;
    for (i = 0; i < k; i++) {
      newChroms[c1].chrom[i] = oldChroms[p1].chrom[i];
      newChroms[c2].chrom[i] = oldChroms[p2].chrom[i];
    }
    for (i = k; i < chromLength; i++) {
      newChroms[c1].chrom[i] = oldChroms[p2].chrom[i];
      newChroms[c2].chrom[i] = oldChroms[p1].chrom[i];
    }
  }
  else 
    for (i = 0; i < chromLength; i++) {
      newChroms[c1].chrom[i] = oldChroms[p1].chrom[i];
      newChroms[c2].chrom[i] = oldChroms[p2].chrom[i];
    }

  mutate(&newChroms[c1]);
  mutate(&newChroms[c2]);

}

void Population::generateNewPop()
{
  int i, p1, p2;
  
  for (i = 0; i< popSize; i += 2) {
    p1 = roulette();
    p2 = roulette();
    crossover(p1, p2, i, i+1);
  }
}


void Population::evolution()
{
  for (int i = 0; i < totalNumGenerations; i++) {
    currentGenNum = i;
    evaluate();
    statistics();
    update();
    generateNewPop();
    swapPop();
  }

}