/*
Selah Lynch   population.cc   August 2004 

Class Population Definitions, see .h file for class description
*/

#include <mpi.h>
#include <stdio.h>
#include "population.h" 


Population::Population(int popsizearg, Problem& probarg):prob(probarg){
  MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
  MPI_Comm_size(MPI_COMM_WORLD, &sizeofcluster);

  int r=rand(); srand(r+myrank);
  //desynchronizes classes
  //if it gets called twice it will seed the classes with 
  //a new number each time

  popsize=popsizearg;

  numpoints=prob.GetNumPoints();

  sol=new Solution[popsize](numpoints);

  fitnesses = new double [popsize];
  iskilled = new bool [popsize];
  check(iskilled!=NULL, "Pointer allocation for iskilled failed.");
  check(fitnesses!=NULL, "Pointer allocation for fitnesses failed.");

  for(int i=0; i<popsize; i++) iskilled[i]=false;
  fitnessset=false;

  //printf("END Population(int, Problem&)\n");
}

Population::Population(Population& pop):prob(pop.prob){
  //printf("BEGIN Population(Population&)\n");
  check(3==2,"Population too large to be copied, please pass by reference.");
}


Population::~Population(){
  //printf("BEGIN ~Population()\n");
  delete [] sol;
  delete [] fitnesses;
  delete [] iskilled;
}


Solution& Population::GetSln(int index){
  return sol[index];
}

Solution& Population::BestSln(){
  SetFitness();
  int minindex=0;
  for(int i=0; i<popsize; i++){
    bool isbetter = fitnesses[i]>fitnesses[minindex];
    //fitness = -distance
    if(isbetter) minindex=i;
  }
  return sol[minindex];
}

void Population::SetFitness(){
  if(!fitnessset){
    for(int i=0; i<popsize; i++)
      fitnesses[i]=0-GetSln(i).GetDist(prob);
    //fitness = -distance  (shorter distance is better and thus higher fitness)
    fitnessset=true;
  }
  //else cout<<"WARNING - fitness is already set\n";
}


void Population::BreedAndReplace(int percent){
  
  SetFitness();

  for(int i=0; i<popsize; i++){ 
    iskilled[i]=false;
  }

  numkilled=0;

  KillSome(percent);
  ReplaceWithChildren();
  
  for(int ii=0; ii<popsize; ii++) iskilled[ii]=false;
  numkilled=0;

  fitnessset=false;
  
}
//for fitnesses, each index corresponds to one of
//the solutions, the one that has the same index
//kill some and then make children


void Population::Mutate(int percent){
  int howmany, whichone, how;
  howmany=(popsize*percent)/100;

  for(int i=0; i<howmany; i++){
    whichone = rand()%popsize;
    how = rand()%3;
    switch(how){
    case 0: sol[whichone].MutateSwt(); break;
    case 1: sol[whichone].MutateInv(); break;
    case 2: sol[whichone].MutateRot(); break;
    }
  }
  fitnessset=false;
}

void Population::Display(ostream& o){
  for(int i=0; i<popsize; i++){
    sol[i].Display(o); 
    if(fitnessset) o<<"  "<<0-fitnesses[i];
    if(numkilled>0&&iskilled[i]) o<<"\tKilled";
    o<<endl;
  }
}

int Population::GetPopSize(){return popsize;}


void Population::MixPopulations(){
  //must send and recieve populations appropriately in order to mix

  int soltosend,n,numtosend[sizeofcluster],numtorecv[sizeofcluster],
    bufsize,*buffer;

  soltosend=popsize/sizeofcluster;
  n=popsize%sizeofcluster;
  //how many solutions to send to each computer,
  //'n' computers get one extra if number doesnt divide evenly

  for(int i=0; i<sizeofcluster; i++){
    numtosend[i]=soltosend;
    numtorecv[i]=soltosend;
  }
  for(int ii=1; ii<=n; ii++){
    numtosend[(myrank+ii)%sizeofcluster]++;
    numtorecv[(myrank-ii+sizeofcluster)%sizeofcluster]++;
  }
  //numtosend[rank] = <how many solutions i'm sending to that computer rank>

  bufsize=numpoints*(soltosend+1);
  buffer= new int [bufsize];

  srand(rand()*myrank);

  SendSome(numtosend,buffer, bufsize);
  RecvSome(numtorecv,buffer, bufsize);

}


void Population::SendSome(int howmany[], int* &buffer, int bufsize){
  //if(myrank==err) cerr<<"BEGIN SendSome()\n";

  int idx, sendtorank, tag, position;

  idx=rand()%popsize;  //index to start sending from, from winners[]
  for(int iii=1; iii<=sizeofcluster; iii++ ){
    sendtorank=(myrank+iii)%sizeofcluster;
    tag=myrank;
    //pack stuff
    position=0;
    for(int m=0; m<howmany[sendtorank]; m++){
      sol[idx].SpitOutOrder(buffer+position);
      position+=numpoints;
      idx=(idx+1)%popsize;
    }
    //send
    //if(myrank==err) cerr<<"CHECK1 SendSome()\n";

    MPI_Send(buffer,bufsize, MPI_INT, sendtorank, tag, MPI_COMM_WORLD);
  }
  //if(myrank==err) cerr<<"END SendSome()\n";
}

void Population::RecvSome(int howmany[], int* &buffer, int bufsize){
  int idx, recvfromrank, tag, position;

  idx=0;
  for(int iiii=1; iiii<=sizeofcluster; iiii++){

    //recieve
    recvfromrank=(sizeofcluster+(myrank-iiii))%sizeofcluster;
    tag=recvfromrank;
    MPI_Status s;
    MPI_Recv(buffer,bufsize,MPI_INT,recvfromrank,tag,MPI_COMM_WORLD, &s);

    //unpack stuff
    position=0;
    for(int m=0; m<howmany[recvfromrank]; m++){

      sol[idx].SetAsString(buffer+position);

      position+=numpoints;
      idx=(idx+1)%popsize;
    }
  }

}



void Population::KillSome(int percent){

  // printf("BEGIN KillSome()\n");


  int howmanytokill, contestant1, contestant2, loser;
  double dist1, dist2;

  //random tornament style
  howmanytokill=popsize*percent/100;

  // cout<<"Attempting to kill "<<howmanytokill<<" solutions.\n";

  //cout<<"cont1\tcont2\tloser\n";
  while(numkilled<howmanytokill){

    contestant1=rand()%popsize;
    contestant2=((rand()%popsize-1)+contestant1)%popsize;

    dist1=(0.0-fitnesses[contestant1]); dist2=(0.0-fitnesses[contestant2]);

    if(dist1<dist2) loser=contestant2;
    else loser=contestant1;

    if(!iskilled[loser]){
      iskilled[loser]=true;
      numkilled++;
    }
    // cout<<dist1<<'\t'<<dist2<<'\t'<<loser<<'\n';
  }

  /*
    //DISPLAY
  cout<<"Killed: ";
  for(int ii=0; ii<popsize; ii++){
    if(iskilled[ii]) cout<<"Y ";
    else cout<<"N ";
  }
  cout<<"count="<<numkilled<<endl;
  */

  //printf("END KillSome()\n");


}


void Population::ReplaceWithChildren(){

  check(popsize-numkilled>=2,"Remaining Population is too small for ReplaceWithChildren()");
  
  //picks amongst the live population for children
  int parent1indx, parent2indx, unique1, unique2, childindx;
  for(int i=0; i<numkilled; i++){ 
 
    unique1=rand()%(popsize-numkilled);
    unique2=(rand()%(popsize-numkilled-1))+unique1+1;
    unique2=unique2%(popsize-numkilled);


    parent1indx=BoolIndex(iskilled, false, unique1);
    parent2indx=BoolIndex(iskilled, false, unique2);

    childindx=BoolIndex(iskilled, true, i);

    sol[childindx].SetAsChild(sol[parent1indx],sol[parent2indx]);
  }
  
}


int Population::BoolIndex(bool* boolarr, bool trueorfalse, int virtindex){

  //check that the index is within range
  int virtsize=0, realindex=0;
  for(int i=0; i<popsize; i++) if(trueorfalse==boolarr[i]) virtsize++;
  char* string = new char [100];
  sprintf(string,"Index [%d] out of range size %d in Bool Indx()",virtindex,virtsize);
  check(virtindex<virtsize, "Index out of range in BoolIndx()");

  while(!boolarr[realindex]==trueorfalse)  realindex++;

  for(int i=0; i<virtindex; i++){
    //at this point we are at a <trueorfalse>
    realindex++;
    while(boolarr[realindex]!=trueorfalse)  realindex++;
  }
  return realindex;
}

void Population::check(bool b, char* mess){
  if(!b) {
    printf("\n\nERROR[Population] - %s \n\n\n", mess);
    exit(0);
  }
}