//
// CGeneration.cpp
//

#include "CGeneration.h"
//
// konstruktor
//
CGeneration::CGeneration(InnerForm * inner, int numGen, int numElite, int generationsCount, int fitnessSelected, int maxGenBestSolutionUnchanged)
{
  srand((unsigned int)time(0));

  if (numGen<1){numGen=1;} //populace ma alespon jednoho clena
  this->numGen=numGen;

  generation=new CString*[this->numGen];
  tempGen=new CString*[this->numGen];

  probability=new double[this->numGen];

  this->strlen=inner->numberOfVariables;

  if (numElite<0){numElite=0;} //pokud nenastaveno jinak, pocet elitaru je 0
  if (numElite>numGen){numElite=numGen;}
  this->numElite=numElite;

  if (generationsCount<1){generationsCount=1;} //pocet generaci, po ktere probiha vyvoj populace, je min. 1
  this->generationsCount=generationsCount;

  this->inner=inner;
  this->fitnessSelected=fitnessSelected;

  bestValue=averageValue=0;
  worstValue=1000;

  varImpTable=new int[inner->numberOfVariables];
  inner->weightTable=new int[inner->numberOfVariables];
  for(int ii=0; ii<inner->numberOfVariables;ii++)
  {
   inner->weightTable[ii]=1;
  }

  if (maxGenBestSolutionUnchanged<1){maxGenBestSolutionUnchanged=generationsCount;}
  this->maxGenBestSolutionUnchanged=maxGenBestSolutionUnchanged;
}


//
// destruktor
//
CGeneration::~CGeneration()
{
  delete generation;
  delete tempGen;
  delete probability;
  delete varImpTable;
  delete inner->weightTable;
}


//
// metoda vyberu jedincu z puvodni generace, urcenych ke krizeni
//
void CGeneration::selection(int method, int parameter)
{
  switch(method)
  {
    case 0:{selectionRoulette(); break;}
    case 1:{selectionTournament(parameter); break;}
    case 2:{selectionRandom(); break;}
    default:{break;}
  };
}

//
// systemem rulety vybere numGen retezcu z generation a nakopiruje je do tempGen
//
void CGeneration::selectionRoulette(void)
{
  double sum=0, val=0;

  // secte hodnoty vsech pravdepodobnosti a vypocte minimalni hodnotu
  for(int ii=0; ii<numGen;ii++)
  {
    val=generation[ii]->fitness(inner, fitnessSelected); //clausesSat(inner);

    probability[ii]=val;
    sum+=val;
  }

  if (sum==0)sum=1;
  eliteRoulette();

  //pravdepodobnosti vsech jedincu vydel souctem vsech pravdepodobnosti, tj. namapuje se na interval <0, 1>
  probability[0]=probability[0]/sum;
  for(int ii=1; ii<numGen;ii++)
  {
    probability[ii]=probability[ii-1]+probability[ii]/sum;
  }
  probability[numGen-1]=1;

  #ifdef consoleOut
    #ifndef testMethod
      cout << "Jedinci + pravdepodobnosti:" << endl;
      //  printGeneration(generation);
    #endif
  #endif

  //do tempGen nakopiruje nahodne vybrane retezce z generation
//  cout << "Vylosovane cislo + vybrany jedinec:" << endl;
  for(int ii=0; ii<numGen-numElite;ii++)
  {
    val=1.0*rand()/RAND_MAX;
    *tempGen[ii]=*binarySearch(val);
//    cout << val << ": " << *tempGen[ii] << endl;
  }

  //dokonci elitarstvi
  for(int jj=numGen-numElite;jj<numGen;jj++)
  {
    *tempGen[jj]=*generation[jj];
  }

//  cout << "Vybrana skupina + "<< numElite << " elite" << endl;
//  printGeneration(tempGen);
}

/*
//
// selekce turnajem
//
void CGeneration::selectionTournament(void)
{
  int x, y;
  eliteRoulette();

  for(int ii=0; ii<numGen-numElite;ii++)
  {
    x=random(numGen); //vybere nahodne dvojici ruznych cisel
    do{
      y=random(numGen);
    }while(x==y);     //pokud jsou tato cisla ruzna
    if (generation[x]->fitness(inner, fitnessSelected)<generation[y]->fitness(inner, fitnessSelected)){x=y;}  //tak vyber toho lepsiho jedince a nakopiruj ho do tempGen

    *tempGen[ii]=*generation[x];
  }
  //    probability[ii]=generation[x]->fitness(inner);

  //dokonci elitarstvi
  for(int jj=numGen-numElite;jj<numGen;jj++)
  {
    *tempGen[jj]=*generation[jj];
  }
}
*/

//
// selekce turnajem
//
void CGeneration::selectionTournament(int number)
{
  eliteRoulette();
  int maxFitness, index, val;

  for(int ii=0; ii<numGen-numElite;ii++)
  {
    for(int jj=0; jj<number;jj++) //vybere nahodne indexy retezcu, ktere pujdou do turnaje
    {
      varImpTable[jj]=random(numGen);
    }

    maxFitness=-999999999;
    for(int jj=0; jj<number;jj++) //vybere nejlepsiho jedince z vybranych
    {
      val=generation[varImpTable[jj]]->fitness(inner, fitnessSelected);
      if (val>maxFitness)
      {
        val=maxFitness;
        index=varImpTable[jj];
      }

    }
    *tempGen[ii]=*generation[index];
  }
  //    probability[ii]=generation[x]->fitness(inner);

  //dokonci elitarstvi
  for(int jj=numGen-numElite;jj<numGen;jj++)
  {
    *tempGen[jj]=*generation[jj];
  }
}


//
// selekce nahodnym vyberem
//
void CGeneration::selectionRandom(void)
{
  int x;
  eliteRoulette();
  for(int ii=0; ii<numGen-numElite;ii++)
  {
    x=random(numGen); //vybere nahodne dvojici ruznych cisel
    *tempGen[ii]=*generation[x];
  }
  //dokonci elitarstvi
  for(int jj=numGen-numElite;jj<numGen;jj++)
  {
    *tempGen[jj]=*generation[jj];
  }
}


//
// zajisti nahodne zmutovani genomu jedince
//
void CGeneration::mutation(double mutationProbability)
{
  for(int ii=0; ii<numGen-numElite; ii++)
  {
    for(int jj=0; jj<strlen;jj++)
    {
      if(1.0*rand()/RAND_MAX< mutationProbability)
      {
//        cout << *generation[ii] << " mutated to ";
        if ((*generation[ii])[jj]==0x01)(*generation[ii])[jj]=0x00;
        else (*generation[ii])[jj]=0x01;
//        cout << *generation[ii] << endl;
      }
    }
  }
}


//
// vyhledavani metodou puleni intervalu jedince s pravdepodobnosti vyskytu val
//
CString* CGeneration::binarySearch(double val)
{
  int l=0, r=numGen-1, tmp;
  if (val<=probability[0]) return generation[0];
  while(r-l>1){
   tmp=(r+l)/2;
   if (probability[tmp]>=val)r=tmp;
   else l=tmp;
  }
  return generation[r];
}

#ifdef consoleOut
//
// vypise celou generaci
//
ostream& operator<<(ostream& o, const CGeneration& cgen)
{
  for (int ii=0; ii<cgen.numGen; ii++)
  {
    o << *cgen.generation[ii] << "\t" << cgen.probability[ii] << "\n";
  }
  return o;
}
#endif

#ifdef consoleOut
//
// take vypise generaci
//
void CGeneration::printGeneration(CString** co)
{
  for (int ii=0; ii<numGen; ii++)
  {
    cout << *co[ii] << "\t" <<  co[ii]->fitness(inner, fitnessSelected) << "\t" << co[ii] << "\n";
  }
}
#endif

//
// vyplni celou generaci jedincu nahodnymi jedinci
//
void CGeneration::fillRandom()
{
  for (int ii=0; ii<this->numGen; ii++)
  {
    generation[ii]=new CString(strlen);
    tempGen[ii]=new CString(strlen);
    for (int jj=0; jj<strlen; jj++)
    {
     if (1.0*rand()/RAND_MAX<0.5){(*generation[ii])[jj]=1; }
     else {(*generation[ii])[jj]=0;}
    }
    probability[ii]=generation[ii]->fitness(inner, fitnessSelected);
  }

  #ifdef consoleOut
    #ifndef testMethod
      cout << "Po fillRandom:" << endl;
      printGeneration(generation);
    #endif
  #endif
}

//
// krizeni
//
void CGeneration::crossover(double crossoverProbability, int method)
{
  int remains=numGen-numElite-1;
  int selected;
  CString first(strlen), second(strlen), tmp(strlen);

  for(int ii=0; ii<(numGen-numElite)/2; ii++)
  {
    //vybere prvniho jedince na krizeni
    selected=random(remains+1);

    first=*tempGen[selected];
    *tempGen[selected]=*tempGen[remains];
//    *tempGen[remains]=NULL;
    remains--;

    //vybere druheho jedince na krizeni
    selected=random(remains+1);

    second=*tempGen[selected];
    *tempGen[selected]=*tempGen[remains];
//    *tempGen[remains]=NULL;
    remains--;

    if (1.0*rand()/RAND_MAX<=crossoverProbability)
    {
      switch(method)
      {
        case 0:{crossoverSimple(first, second, tmp); break;}
        case 1:{crossoverTwoPoint(first, second, tmp); break;}
        case 2:{crossoverUniform(first, second, tmp); break;}
        case 3:{crossoverImprovement(first, second, tmp); break;}
        default:{break;}
      };
    }

    *generation[2*ii]=first;
    *generation[2*ii+1]=second;
  }
  //pokud je v generaci lichy pocet jedincu, tak ten posledni se s nikym nekrizi, ale pouze se zkopiruje do dalsi generace
  if ((numGen-numElite)%2==1) {*generation[numGen-numElite-1]=*tempGen[0];} // tempGen[0]=NULL;}

  for(int jj=numGen-numElite; jj<numGen;jj++)
  {
    *generation[jj]=*tempGen[jj];
  }
}


//
// provede uniformni krizeni dvou jedincu
//
void CGeneration::crossoverUniform(CString& first, CString& second, CString& tmp)
{
  for(int ii=0 ; ii<strlen ; ii++)
  {
    if(1.0*rand()/RAND_MAX<0.5)
    {
      (tmp)[ii] = (first)[ii];
      (first)[ii] = (second)[ii];
      (second)[ii] = (tmp)[ii];
    }
  }
}


//
// provede dvoubodove krizeni dvou jedincu
//
void CGeneration::crossoverTwoPoint(CString& first, CString& second, CString& tmp)
{
    int selected1;
    int selected2;
    selected1=random(strlen);
    do{
      selected2=random(strlen);
    }while(selected1==selected2);
    if (selected1>selected2){int pom=selected1; selected1=selected2; selected2=pom;}

//    cout << first << "joins with " << second << " at " << selected1 << " and " << selected2;

    for(int ii=0;ii<strlen;ii++)
    {
      if(ii>selected1 && ii<=selected2)
      {
        (tmp)[ii] = (first)[ii];
        (first)[ii] = (second)[ii];
        (second)[ii] = (tmp)[ii];
      }
    }

//    cout << " and forms " << first << " and " << second <<  endl;
}


//
// provede jednobodove krizeni dvou jedincu
//
void CGeneration::crossoverSimple(CString& first, CString& second, CString& tmp)
{
    int selected=random(strlen);

//    cout << first << "joins with " << second << " at " << selected;
    for(int ii=0;ii<strlen;ii++)
    {
      if(ii<selected)
      {
        (tmp)[ii] = (first)[ii];
        (first)[ii] = (second)[ii];
        (second)[ii] = (tmp)[ii];
      }
    }
//    cout << " and forms " << first << " and " << second <<  endl;
}


//
// specialni krizeni s vylepsenim
//
void CGeneration::crossoverImprovement(CString& first, CString& second, CString& tmp)
{
//  int *varImpTable=new int[inner->numberOfVariables];
  for(int ii=0; ii<inner->numberOfVariables; ii++){varImpTable[ii]=0; tmp[ii]=0;}

  int lit, sign;
  bool badFirst, badSecond;

  for (int ii=0; ii < inner->numberOfClauses; ii++)
  {
    badFirst = badSecond = true;
    for (int jj=1; jj < inner->clauses[ii][0]+1; jj++)
    {
      lit = inner->clauses[ii][jj];
      sign = lit > 0 ? 1 : 0;
      if ( first[abs(lit)] == sign ){badFirst = false;}
      if ( second[abs(lit)] == sign ){badSecond = false;}
    }
    if (badFirst==true && badSecond==true) //pokud je klauzule nesplnena ve FIRST i SECOND
    {
      for(int kk=0; kk<3; kk++) //urci vsechny promenne ze vsech BC klauzuli, ktere budeme flipovat a pocitat zlepseni
      {
        varImpTable[abs(inner->clauses[ii][kk])-1]=1;
      }
    }
  }

  //do varImpTable uloz zlepseni pro vsechny promenne v BC(broken clauses)
  int maximumImprovement=-1000;
  for(int ii=0; ii<inner->numberOfVariables; ii++)
  {
    if (varImpTable[ii]==1)
    {
      varImpTable[ii]=first.improvement(inner, ii);
      varImpTable[ii]+=second.improvement(inner, ii);
      if (varImpTable[ii]>maximumImprovement) maximumImprovement=varImpTable[ii];
    }
  }

  //vygeneruj potomky
  for(int ii=0; ii<inner->numberOfVariables; ii++)
  {
    if (varImpTable[ii]!=maximumImprovement || maximumImprovement<=0)
    {
      if(first[ii]==second[ii]) //pokud se first a second shoduji v danem chromozomu, tak tento chromozom zkopiruj beze zmeny
      {
        tmp[ii]=first[ii];
      }else                     //jinak dopln nahodny chromozom
      {
        tmp[ii]=random(1);
      }
    }else //chromozomy s nejvetsim zlepsenim invertuj
    {
      tmp[ii]=1-first[ii];
//      cout << ".." << ii << endl;
    }
  }

//

//

  //nakonec horsi jedinec z dvojice FIRST, SECOND bude prepsan a do populace bude vracen druhy retezec a vysledny TMP
  if(first.fitness(inner, fitnessSelected) > second.fitness(inner, fitnessSelected))
  {
    second=tmp;
  }else
  {
    first=tmp;
  }

//  delete varImpTable;
}


//
// vrati nahodne cislo
//
int CGeneration::random(int max)
{
  return (int)((max-1)*rand()/RAND_MAX);
}


//
// elitarstvi
// (vybere numElite nejlepsich jedincu a zkopiruje je "na konec" generace,
//  prohodi je s jedinci umistenymi na konci)
//
void CGeneration::eliteRoulette()
{
  double maxVal;
  int unitIndex=-1;
  for(int ii=0; ii<numElite;ii++)
  {
    maxVal=-9E9;unitIndex=0;
    for(int jj=0; jj< numGen-ii; jj++) //vyber numElite nejlepsich jedincu
    {
       if(probability[jj]>maxVal)
       {
          maxVal=probability[jj];
          unitIndex=jj;
       }
    }
    if (unitIndex!=numGen-1-ii) //a prohod je, pokud ten nejlepsi neni ten posledni
    {
      CString pom(strlen);
      pom=*generation[numGen-1-ii];
      double pom2=probability[numGen-1-ii];

      *generation[numGen-1-ii]=*generation[unitIndex];
      probability[numGen-1-ii]=probability[unitIndex];

      *generation[unitIndex]=pom;
      probability[unitIndex]=pom2;

//      cout << "Elitar:" << *generation[numGen-1-ii] << "\t" << generation[numGen-1-ii]->fitness(inner, fitnessSelected) << endl;
    }
  }
}


//
// statistika (nejlepsi, nehorsi, prumerny jedinec apod.)
// navic jeste testuje, zda nalezeno konecne reseni(zda se ma uz skoncit nebo ne)
//
void CGeneration::statistics(int& solutionFound, int& solutionIndex)
{
  bestValue=-9E9;
  worstValue=9E9;
  averageValue=-9E9;
  int val=0;
  int sum=0;

  for(int ii=0; ii<numGen;ii++)
  {
    val=generation[ii]->fitness(inner, fitnessSelected); //clausesSat(inner);

    //pokud jsou vsechny klauzule splnene, pak ukonci prohledavani
//    if (val==inner->numberOfClauses){solutionFound=1; solutionIndex=ii;}
    if (generation[ii]->clausesSat(inner)==inner->numberOfClauses){solutionFound=1; solutionIndex=ii;}

    //pro statistiku(nejlepsi a nejhorsi jedinec)
    if (val>bestValue)bestValue=val;
    if (val<worstValue)worstValue=val;

    probability[ii]=val;
    sum+=val;
    probability[ii]=generation[ii]->fitness(inner, fitnessSelected);
  }
  //pro statistiku(prumerny jedinec)
  averageValue=sum/numGen;
}


//
// realizuje vyvoj populace
//
void CGeneration::evolution(double crossoverProbability, double mutationProbability, int selectionMethod, int crossoverMethod, int tournamentSize)
{
  int solutionFound=0, solutionIndex=0, numGenBestSolutionUnchanged=0, lastMax=-9E9;
  generationsEvolved=0;
  if (tournamentSize<2 || tournamentSize>inner->numberOfVariables){tournamentSize=2;}
  // na zacatku naplni populaci nahodnymi jedinci
  fillRandom();

  // kdyz zobrazuju do grafu, tak jsou osy normovany tak, aby se vykreslovane body objevovaly v intervalu <0%..100%>
  // v pripade normalniho SATu je vztaznou hodnotou pro svislou osu celkovy pocet klauzuli ve formuli, v pripade
  //  vazeneho SATu se jedna o celkovy soucet vah vsech promennych
  int divisor;
  switch (fitnessSelected)
  {
   case 0:
   {
      divisor= inner->numberOfClauses;
      break;
   }
   case 1:
   {
     #ifdef graphicOut
     //v pripade vazeneho SATu naparsuje dodatecne parametry a ulozi je do pole
     parseParameters(lineEdit9->text().ascii(), inner->weightTable, sumOfWeights, inner->numberOfVariables, inner->unsatPenalty);
     divisor=sumOfWeights;
     messageEdit->setText(messageEdit->text() + QString("Sum of weights of all variables...%1\n").arg(sumOfWeights));
     #endif
     break;
   }
  }
  int ii;
  for(ii=0; ii<generationsCount && numGenBestSolutionUnchanged<maxGenBestSolutionUnchanged; ii++)
  {
    Sleep(10);
    #ifdef consoleOut
      #ifndef testMethod
      cout << ii <<". generation evolved:" << endl;
      #endif
    #endif
    #ifdef graphicOut
    messageEdit->setText(messageEdit->text() + QString("%1.generation evolved\n").arg(ii));
    #endif

    selection(selectionMethod, tournamentSize);
//    cout << "Po selekci:" << endl;
//    printGeneration(tempGen);
    crossover(crossoverProbability, crossoverMethod);
    mutation(mutationProbability);
//    cout << "Po krizeni a mutaci:" << endl;
//    printGeneration(generation);
    statistics(solutionFound, solutionIndex);

    #ifdef consoleOut
      #ifndef testMethod
        cout << "best:" << bestValue << endl;
        cout << "average:" << averageValue << endl;
        cout << "worst:" << worstValue << endl;
        cout << endl;
      #endif
    #endif
    #ifdef graphicOut
    messageEdit->setText(messageEdit->text() + QString("best: %1\naverage: %1\nworst: %1\n").arg(bestValue).arg(averageValue).arg(worstValue));
    paintPane->paintPoint(100*ii/generationsCount, 100*worstValue/divisor, 2);
    paintPane->paintPoint(100*ii/generationsCount, 100*averageValue/divisor, 1);
    paintPane->paintPoint(100*ii/generationsCount, 100*bestValue/divisor, 0);
    #endif

    if(solutionFound==1)
    {
      #ifdef consoleOut
      cout << "Solution:: " << *generation[solutionIndex] << endl;
      #endif
      #ifdef graphicOut
      messageEdit->setText(messageEdit->text() + QString("Solution: ") + QString(generation[solutionIndex]->toString()).append("\n"));
      #endif

      if (fitnessSelected==0){ break;} //pri normalnim SATu ukonci vypocet pri nalezenem reseni, pri vazenem SATu zkus najit "lepsi" reseni, pokud existuje
      else{solutionFound=0;}
    }
    if (lastMax==bestValue) //pokud se v teto generaci nezmenila hodnota nejlepsiho jedince
    {
      numGenBestSolutionUnchanged++;
    }else{
      numGenBestSolutionUnchanged=0;
    }
    lastMax=bestValue;
  }
  generationsEvolved=ii;

  #ifdef testMethod
    cout << solutionFound << "\t" << bestValue << "\t" << (inner->numberOfClauses-bestValue) << "\t" << endl;
  #endif
}


//
// predani ukazatelu na textova pole
//
#ifdef graphicOut
void CGeneration::setQMessage(QTextEdit *messageEdit, QLineEdit *lineEdit9)
{
  this->messageEdit=messageEdit;
  this->lineEdit9=lineEdit9;
}


//
// predani ukazatele na vykreslovaci plochu
//
void CGeneration::setPaintPane(PaintPane *paintPane)
{
  this->paintPane=paintPane;
}
#endif


//
//
//
int CGeneration::getBestValue()
{
  return bestValue;
}


//
// vrati cislo udavajici pocet generaci, ktere uplynuly od spusteni algoritmu
//
int CGeneration::getGenerationsEvolved()
{
  return generationsEvolved;
}
