#include <stdio.h>
#include <iostream>
#include <vector>
#include <map>
#include <fstream>
#include <time.h>
#include <math.h>
#include <algorithm>
#include <string>
#include <iomanip>
#include <list>
#include <stdlib.h>
#include <ctime>
#include "T_matrix.cpp"

#define MAX_RAND 32767

using namespace	std;

ifstream inn;
ofstream off;
ofstream off_graph;
//ofstream off_all;

T_matrix<short int> maticeC("matice C");// - dodelat naplneni
T_matrix<short int> maticeT("matice T");// dodelat naplneni
T_matrix<short int> maticeB("matice B");
T_matrix<short int> p_maticeB("pom. matice B");
T_matrix<short int> maticeD("matice D");
T_matrix<short int> maticeS("matice S");

// prorezana matice T - matice T po odstraneni podrizenych a prazdnych sloupcu
T_matrix<short int> maticeTP("matice TP");
//T_matrix<double> maticeLP("matice LP");
//T_matrix<double> maticeLN("matice LN");

// typ sloupce - R - reprezentativni, M - hlavni, S - podrizeny, E - prazdny
vector<char> columnsT_type;
int columnsT_empty;

// mapovani sloupcu matice T na sloupce matice TP - pouze reprezentativni sloupce - sirka = sirka TP
T_array<int> columnsTP_mapping("columnsTP_mapping");
T_array<double> columnsTP_avg_loss("columnsTP_avg_loss");

int sirkaT, sirkaC, vyskaT, vyskaC, sirkaTP;
time_t start_time, end_time;

T_array<int> CROW_COUNTER("CROW_COUNTER");
T_array<int> TROW_COUNTER("TROW_COUNTER");

T_matrix<long int> matches_statistics("statistika matches");
T_array<long int> matches_colTP_stat("matches_colTP_stat");
T_matrix<long int> rank_statistics("statistika rank");

char test_name[50];
char output_graph[50], output_out[50];
char output_dir[50];

bool first_phase;

/** ****************************** Logging ********************************* */

/** Vypis
- tamplaty a procedury k vypisu matic */
template<class InputIterator> void vypis(ostream &os, InputIterator zacatek,
         InputIterator konec)
{
  for(InputIterator i = zacatek; i != konec; i++)  {
    os << setw(2) << *i << " ";
  }
  os << endl;
}

void vypis_ns(ostream &os, vector<char> pole) {
  int i, j;
  for (i = 0; i < pole.size(); i++)
    os << pole[i];
}

template<class InputIterator> void vypisBinary(ostream &os, InputIterator zacatek, InputIterator konec) {
  for(InputIterator i = zacatek; i != konec; i++)
    if (*i == 0 || *i == 1) os << *i;
    else os << "-";
}

template<class AnyType> void vypisBinary(ostream &os, AnyType value) {
  if (value == 0 || value == 1) os << value;
  else os << "-";
}


void vypisCas(ostream &os, long int cas) {
  os << floor(cas / 3600) << ":" << right;
  os << setfill('0') << setw(2) <<  floor((cas % 3600) / 60) << ":";
  os << setfill('0') << setw(2) << (cas % 60) << endl;
  os << setfill(' ');
}

/** SortDoubleDesc
- pomocna procedura k sestupnemu setrizeni vektoru double */
bool SortDoubleDesc(const double &a, const double &b) {
  return a > b;
}

/** VypisOddelovac
- vypise oddelovac do prislusneho streamu */
void VypisOddelovac(ostream &os) {
  os << "-------------------------------------------------------------------------------" << endl;
}

/** VypisStatistiku
- vypise do prislusneho streamu statistiky */
void VypisStatistiku(ostream &os) {
  // spocitame statistiku
  vector<double> matches_variance(sirkaTP);
  vector<double> rank_variance(sirkaTP);

  for (int colTP=0; colTP<sirkaTP; colTP++) {
    long int max_hits = 0;
    long int tot_hits = 0;
    long int hits;

    // vypocet variace matches pro sloupce T
    for (int colC=0; colC<sirkaC; colC++) {
      hits = matches_statistics[colTP][colC];
      if (hits > max_hits) {
        max_hits = hits;
      }
      tot_hits += hits;
    }
    if (max_hits != 0) 
      matches_variance[colTP] = (double) max_hits / (double) tot_hits * (double) sirkaC;
    else
      matches_variance[colTP] = 0;

    max_hits = 0;
    tot_hits = 0;
    // vypocet variace matches pro sloupce T
    for (int r=0; r<sirkaTP; r++) {
      hits = rank_statistics[colTP][r];
      if (hits > max_hits) {
        max_hits = hits;
      }
      tot_hits += hits;
    }
    if (max_hits != 0) 
      rank_variance[colTP] = (double) max_hits / (double) tot_hits * (double) sirkaTP;
    else
      rank_variance[colTP] = 0;

  }

  os << "Variace pole matches pro sloupce T: " << endl;
  vypis(os, matches_variance.begin(), matches_variance.end());
  os << "Variace pole rank pro sloupce T: " << endl;
  vypis(os, rank_variance.begin(), rank_variance.end());

  os << "Matice vyberu kombinace T->C" << endl;
  matches_statistics.vypis(os);
  os << "Matice vyberu kombinace T->rank" << endl;
  rank_statistics.vypis(os);

}

double GetRandomInterval() {
   long int r = rand();
   double ret = (double) r / RAND_MAX;
   return ret;
}

/** ************************************ prace s listem pro tvoreni permutaci *******************************/

void InitList(list<int> &l, int size) {
  l.clear();
  for (int i = 0; i < size; i++) {
    l.push_back(i);
  }
}

void RemoveValue(list<int> &l, int value) {
  list<int>::iterator it;

  it = l.begin();
  while ( *it < value && it != l.end() ) it++;
  if (*it == value) l.erase(it);
}

int RemoveRandom(list<int> &l) {
  list<int>::iterator it;

  int r = rand() % l.size();
  int ret;

  // nahodne vybereme hodnotu
  it = l.begin();
  for (int j = 0; j < r; j++) it++;
  ret = *it;
  l.erase(it);

  return ret;
}

/** ****************************** Row Assignment ********************************* */

/** MakeRowAssignment
- pro globalni matici B zjisti, jestli je mozne provest prirazeni vsech radku C k radkum T
  a tim overi, jestli aktualni matice B muze byt resenim
- vraci true, pokud je prirazeni mozne, jinak false
- ve vystupnim vektoru X jsou dvojice radek T -> radek C, ma smysl pouze pri vraceni true
*/
bool MakeRowAssignment(vector<int> &X) {
  int c_crow, c_trow, min, crow, trow;

  X.resize(vyskaT);

  // vynulovani poli s poctem jednicek v sloupcich a radcich matice B (radkyB, sloupceB)
  CROW_COUNTER.SetConstValue(0);
  TROW_COUNTER.SetConstValue(0);

  // spocitam pocet jednicek ve sloupcich a radcich
  for (c_crow = 0; c_crow < vyskaC; c_crow++)
    for (c_trow = 0; c_trow < vyskaT; c_trow++)
      if (maticeB[c_crow][c_trow] == 1) {
          CROW_COUNTER[c_crow]++;
          TROW_COUNTER[c_trow]++;
       }

  // prirazeni provedu pro kazdy sloupec maticeB (coz reprezentuje radky matice T)
  for (int i = 0; i < vyskaT; i++) {

    min = vyskaC + 1;
    // vyber sloupce v matici B, ktery ma nejmene jednicek, tj. trow (radek T do matche)
    for (c_trow = 0; c_trow < vyskaT; c_trow++)
      if (TROW_COUNTER[c_trow] != -1 && TROW_COUNTER[c_trow] < min) {
        min = TROW_COUNTER[c_trow];
        trow = c_trow;
        }

    // nenasli jsme ke sloupci matice B zadny radek B, tzn. nenasli jsme k radku T radek C
    if (min == 0) return false;

    min = vyskaT + 1;
    // vyber radku matice B, ktery ma nejmene jednicek, tj. crow (radek C do matche)
    for (c_crow = 0; c_crow < vyskaC; c_crow++)
      if (CROW_COUNTER[c_crow] != -1 && maticeB[c_crow][trow] == 1 && CROW_COUNTER[c_crow] < min) {
        min = CROW_COUNTER[c_crow];
        crow = c_crow;
      }

    // zapamatuji match		
    X[trow] = crow;

    // projedu sloupec maticeB trow a dekrementuju counter CROW tam, kde existuje prirazeni = 1
    for (c_crow = 0; c_crow < vyskaC; c_crow++) 
      if (maticeB[c_crow][trow] == 1 && CROW_COUNTER[c_crow] != -1)
        CROW_COUNTER[c_crow]--;

    // projedu radek maticeB crow a dekrementuju counter TROW tam, kde existuje prirazeni = 1
    for (c_trow = 0; c_trow < vyskaT; c_trow++) 
      if (maticeB[crow][c_trow] == 1 && TROW_COUNTER[c_trow] != -1)
        TROW_COUNTER[c_trow]--;

    // odeberu radek a sloupec z matice B
    CROW_COUNTER[crow] = -1;
    TROW_COUNTER[trow] = -1;

  }

  // povedlo se najit prirazeni
  return true;
}

/** ********************************* Jedinec ******************************** */
class Jedinec {
private:
  // zakodovani
  vector<int> matches;		// prirazeni sloupcu matice C k sloupcum matice TP
  vector<int> NM;		// priznak negovani sloupcu matice TP
  vector<int> rank;		// poradi prirazeni sloupcu matice TP - index = poradi, hodnota = sloupec T

  // fitness a kvalita jedince
  double fitness;		// hodnota fitness (kvalita) jedince
  double potential;
  int level;
  int columnsT_matched;		// pocet nalezenych sparovani
  int direct_matches;
  int direct_neg_matches;
  double quality;
  int certain_matches;

  // informativni a pomocne
  vector<int> X;		// prirazeni radku matice C k radkum matice T - vypocitava se spolu s fitnes
  vector<int> columnsT_mapping;	// mapovani sloupcu T na sloupce TP - vypocitava se spolu s fitnes
  bool crossover_flag;		// flag indikujici, ze jedinec byl krizen

  vector<int> columnsT_matches; // prirazeni sloupcu matice C k sloupcum matice T
  vector<int> columnsT_NM;	// pole priznaku negovani sloupcu matice T

public:

/** Jedinec(bool init_chromozome);
- implicitni konstruktor - vytvori prazdneho jedince (pole rank je prazdne) */
  Jedinec(bool init_chromozome = true);

/** Jedinec(const Jedinec& puvodni)
- kopirovaci konstruktor */
  Jedinec(const Jedinec& puvodni);

/** CommonGenes(const Jedinec& puvodni)
- zjisti, jestli jedinci maji alespon polovinu spolecnych genu, aby mezi sebou souperili pri selekci */
  int CommonGenes(const Jedinec& s);

/** Vypis(ostream &os)
- vypise detaily o jedinci */
  void Vypis(ostream &os);

/** VypisMatches(ostream &os)
- vypise pole matches v trochu citelnem formatu T->C */
  void VypisMatches(ostream &os) const;

/** VypisRank(ostream &os)
- vypise pole rank */
  void VypisRank(ostream &os);

/** VypisFlags(ostream &os)
- vypise vsechny flagy za sebou */
  void VypisFlags(ostream &os);

/** Check() 
- zkontroluje jedince (pole rank, matches, row_assignement) */
  void Check();

/** void ResetColumnsTMapping()
- funkce resetuje pole columnsT_mapping
- nastavi mapovani u reprezentativnich sloupcu a u zavislych sloupcu nastavi hodnotu -1
*/
  void ResetColumnsTMapping();

/** void ResetColumnsTMatches()
- funkce resetuje pole columnsT_matches a columnsT_NM
- nastavi matche u prazdnych sloupcu na direct match, u ostatnich na -1
*/
  void ResetColumnsTMatches();

/** operator<(const Jedinec &druhy) 
- operator pro porovnavani jedincu */
  bool operator<(const Jedinec &druhy);

/** operator>(const Jedinec &druhy) 
- operator pro porovnavani jedincu */
  bool operator>(const Jedinec &druhy);

/** Get metody jedince */
  double GetFitness() const;
  int GetColumnsTMatched() const;
  int GetRankSize() const;
  int GetDirectMatches() const;
  int GetDirectNegMatches() const;
  double GetPotential() const;
  bool GetCrossoverFlag() const;
  double GetQuality() const;
  int GetRank(int r) const;
  int GetLevel() const;

/** Set metody jedince */
  void SetQuality(double qual);
  void SetCrossoverFlag(bool value);
  void SetCM(int r, int colTP, int colC, int neg, bool modify_certain_matches = true);

/** Metody pro vypocet fitness */

/** int Jedinec::AddDependentColumns(int colTP)
- funkce upravi pole columnsT_mapping u zavislych sloupcu na sloupci colTP 
- vraci pocet pridanych zavislych sloupcu */
  int AddDependentColumns(int colTP);

/** void Jedinec::OptimizeDependentColumns()
- funkce spocita pocet direct matchu a pokusi se prevesit zavisle sloupce
- na jine repr. sloupce, aby vznikl direct match */
  int OptimizeDependentColumns();

/** CountColumnsTMatches()
- jednorazove spocita pole columnsT_matches a columnsT_NM
**/
  void CountColumnsTMatches();

/** void CountFitness(bool use_discarding)
- spocita fitness  */
  void CountFitness(bool use_discarding);

/** void CountDirectMatches()
- spocita fitness  */
  void CountDirectMatches();

/** void CountDirectNegMatches()
- spocita fitness  */
  void CountDirectNegMatches();

/** Geneticke operatory */

/** bool Jedinec::DetectConflict(int tcol, int ccol, neg)
- zjisti, jestli by dalsi prirazeni tcol->ccol(neg) zbusobilo logickou kolizi v matches
- predpoklada, ze konec pole rank je naplnen -1-ckami
- false - vse ok
- true - chyba
**/
bool DetectConflict(int colTP, int colC, int neg);

/** in Jedinec::DetectConflictCM(int r, int tcol, int ccol)
- zjisti, jestli by nastaveni prirazeni tcol->ccol(neg) zbusobilo logickou kolizi
- r - pocet sloupcu T, u kterych bude provedena kontrola (poradi bude podle rank) - 1 - sirkaTP
- -1 - nelze priradit sloupec, 0 - lze priradit sloupec pouze pozitivni
- 1 - lze priradit sloupec pouze negativne, 2 - lze priradit sloupec jakkoli
**/
  int DetectConflictCM(int r, int colTP, int colC);

/** static Jedinec UniformCrossover(Jedinec &prvni, Jedinec &druhy);
- provede uniformni krizeni dvou jedincu -> vzniknou potomek1, potomek */
  static Jedinec UniformCrossover(Jedinec &prvni, Jedinec &druhy);

/** static Jedinec OnePointCrossover(Jedinec &rodic1, Jedinec &rodic2);
- provede 1-bodove krizeni dvou jedincu -> vzniknou potomek1, potomek */
  static Jedinec OnePointCrossover(Jedinec &rodic1, Jedinec &rodic2);

/** void MatchesMutation(double pm);
- provede mutaci pole matches */
  void MatchesMutation(double pm);

/** void RankInsertMutation(double pr1);
- provede mutaci pole rank - vlozeni v permutaci */
  void RankInsertMutation(double pr1);

/** void RankMoveMutation(double pr2);
- provede mutaci pole rank - vymena sousedu */
  void RankMoveMutation(double pr2);

/** void LocalMutation()
- nahodne naplni cast pole rank za urovni level */
  void LocalMutation();

/** Jedinec::AdjustStatistics()
- upravi statistiky pro pole rank a matches */
  void AdjustStatistics();

/** Jedinec::FinalOptimalization()
- pokusi se o prirazeni direct matche u zavislych sloupcu */
  void FinalOptimalization();

/** Jedinec::CreatePLAFile()
- vytvori vystupni PLA soubor z tohoto jedince */
  void CreatePLAFile();

/** Jedinec::CreateMatchesFile()
- vytvori vystupni soubor matches z tohoto jedince */
  void CreateMatchesFile();

/** Jedinec::CheckRank() 
- zkontroluje pole rank jedince, jestli v nem nejsou duplicitni sloupce T */
  bool CheckRank();

/** Jedinec::CheckMatches() 
- zkontroluje pole matches jedince, jestli v nem nejsou sloupce C zpusobujici kolizi */
  bool CheckMatches();

/** Jedinec::CheckRowAssignment()
- zkontroluje prirazeni radek ve vektoru X - jestli prorazane matice C odpovida sparovanym sloupcum a matici T */
  bool CheckRowAssignment();

};

/** ************************************ Populace - definice ************************************* */
//TODO dodelat komentare

class Populace {
public:
  int size;
  int generation;
  vector<Jedinec> vect;

  Jedinec best_jedinec;
  double best_fitness;
  int best_columnsT_matched;

  double avg_fitness;
  double avg_level;

  vector<int> genes_amount;

  Populace(int size);

  Populace(const Populace& s);

  void Evaluate(bool use_discarding);

  void CountProperties();

  void Sort();

  void GenerateNext(int ps, int crossover_method, double pc, 
                    double pm, double pr1, double pr2, bool use_thresholding = true);

  int SelectIndividual(bool use_threshold, int ps = 2);

  void ZeroAvgValues();

  void Vypis(ostream &os);

  void GraphLog(ostream &os);

  Jedinec Get(int i) const;

};

/** ************************************* Jedinec ************************************ */

/** Jedinec::Jedinec
- implicitni konstruktor - nahodne naplni pole matches, rank a NM + ostatni atributy vynuluje */
  Jedinec::Jedinec(bool init_chromozome)
    :fitness(-1), columnsT_matched(-1), direct_matches(-1), direct_neg_matches(-1),
    crossover_flag(0), potential(0), level(0), quality(0), certain_matches(0)
  {
    matches.resize(sirkaTP);
    NM.resize(sirkaTP);
    rank.resize(sirkaTP);

    if (!init_chromozome) {
      for (int i = 0; i < sirkaTP; i++) {
        matches[i] = -1;
        NM[i] = -1;
        rank[i] = -1;
      }
    } else {

      for (int colTP = 0; colTP < sirkaTP; colTP++) {
        NM[colTP] = rand() % 2;
      }

      // nahodne naplneni pole matches - nesmi obsahovat dve stejne hodnoty sloupce T
      list<int> columnsC;
      InitList(columnsC, sirkaC);
      for (int r = 0; r < sirkaTP; r++) {
        matches[r] = RemoveRandom(columnsC);
      }

      // nahodne naplneni pole rank - nesmi obsahovat dve stejne hodnoty sloupce T
      list<int> columnsTP;
      InitList(columnsTP, sirkaTP);
      for (int r = 0; r < sirkaTP; r++) {
        rank[r] = RemoveRandom(columnsTP);
      }
    }
  }

/** Jedinec::Jedinec(const Jedinec& puvodni)
- kopirovaci konstruktor */
  Jedinec::Jedinec(const Jedinec& puvodni): 
    matches(puvodni.matches), X(puvodni.X), columnsT_matches(puvodni.columnsT_matches),
    columnsT_NM(puvodni.columnsT_NM), level(puvodni.level), quality(puvodni.quality),
    NM(puvodni.NM), rank(puvodni.rank) , columnsT_mapping(puvodni.columnsT_mapping),
    fitness(puvodni.fitness), columnsT_matched(puvodni.columnsT_matched), direct_matches(puvodni.direct_matches),
    direct_neg_matches(puvodni.direct_neg_matches), certain_matches(puvodni.certain_matches),
    crossover_flag(puvodni.crossover_flag), potential(puvodni.potential) {}

/** Jedinec::CommonGenes(const Jedinec& puvodni)
- zjisti, jestli jedinci maji alespon polovinu spolecnych genu, aby mezi sebou souperili pri selekci */
  int Jedinec::CommonGenes(const Jedinec& s) {
    int cnt = 0;

    for (int r1 = 0; r1 < level; r1++)
      for (int r2 = 0; r2 < s.level; r2++)
        if ( rank[r1] == s.rank[r2] ) { 
          cnt++;
          break;
        }

    return cnt;

  }

/** void Jedinec::ResetColumnsTMapping()
- funkce resetuje pole columnsT_mapping
- nastavi mapovani u reprezentativnich sloupcu a u zavislych sloupcu nastavi hodnotu -1
*/
void Jedinec::ResetColumnsTMapping() {
    int col;
    // naplneni columnsT_mapping
    for (int i = 0; i < sirkaT; i++) {
      if ( columnsT_type[i] == 'E' ) columnsT_mapping[i] = -2;
      else columnsT_mapping[i] = -1; 
    }
    // naplneni mapovani reprezentativnich sloupcu
    for (int i = 0; i < sirkaTP; i++) {
      col = columnsTP_mapping[i];
      columnsT_mapping[col] = i;
    }
}

/** void Jedinec::ResetColumnsTMatches()
- funkce resetuje pole columnsT_matches a columnsT_NM
- nastavi matche u prazdnych sloupcu na direct match, u ostatnich na -1
*/
void Jedinec::ResetColumnsTMatches() {
  // vynulujeme columnsT_matches, u prazdnych sloupcu rovnou nastavime direct matche
  for (int i = 0; i < sirkaT; i++) {
    if ( columnsT_type[i] == 'E' ) {
      columnsT_matches[i] = i;
      columnsT_NM[i] = 0;
    } else {
      columnsT_matches[i] = -1;
      columnsT_NM[i] = -1;
    }
  }
}

/** Jedinec::Vypis(ostream &os)
- vypise detaily o jedinci */
void Jedinec::Vypis(ostream &os) {
    os << "Vypis kodovani jedince" << endl;
    os << "F, L, CM, DM, DNM, P: " << fitness << ", " << level << ", " << columnsT_matched << ", " << direct_matches << ", " << direct_neg_matches << ", " << potential << "    ";;
    os << "Flagy: ";
    VypisFlags(os);
    os << endl;
    os << "Matches: ";
    VypisMatches(os);
    os << "Rank: ";
    VypisRank(os);
    os << "X: ";
    vypis(os, X.begin(), X.end());
    os << "columnsTP_mapping: ";
    columnsTP_mapping.vypis(os);
    os << "columnsT_mapping: ";
    vypis(os, columnsT_mapping.begin(), columnsT_mapping.end());
    os << "columnsT_matches: ";
    vypis(os, columnsT_matches.begin(), columnsT_matches.end());
    os << endl;
    os << endl;
  }

/** Jedinec::VypisMatches(ostream &os)
- vypise pole matches v trochu citelnem formatu T->C */
  void Jedinec::VypisMatches(ostream &os) const {
    int colT, colC, colTP, r;
    for (r = 0; r < rank.size(); r++) {
      colTP = rank[r];
      colT = columnsTP_mapping[colTP];
      colC = matches[colTP];
      os << setw(2) << colTP << "->" << setw(2) << colC << "(" << NM[colTP] << ") ";
    }
    os << endl;
  }

/** Jedinec::VypisRank(ostream &os)
- vypise pole rank */
  void Jedinec::VypisRank(ostream &os) {
    vypis(os, rank.begin(), rank.end());
  }

/** Jedinec::VypisFlags(ostream &os)
- vypise vsechny flagy pekne za sebou */
  void Jedinec::VypisFlags(ostream &os) {
    os << this->crossover_flag;
  }

/** Jedinec::Check() 
*/
  void Jedinec::Check() {

    if (!CheckRowAssignment()) {
      cout << "Kontrola prirazeni radek jedince neprobehla v poradku, chyba algoritmu!!!!" << endl;
      exit(2);
    }

    if (!CheckRank()) {
       cout << "Kontrola pole rank edince neprobehla v poradku, chyba algoritmu!!!!" << endl;
       Vypis(cout);
       exit(2);
    }

    if (!CheckMatches()) {
       cout << "Kontrola pole matches jedince neprobehla v poradku, chyba algoritmu!!!!" << endl;
       Vypis(cout);
       exit(2);
    }
  }


/** Jedinec::CheckRank() 
- zkontroluje pole rank jedince, jestli v nem nejsou duplicitni sloupce T */
  bool Jedinec::CheckRank() {
    int i, j;
    bool once;

    for (int i=0; i<rank.size(); i++) {
      once = false;
      if (rank[i] >= sirkaTP || rank[i] < 0)
      for (int j=0; j<sirkaTP; j++) {
        if (i == rank[j]) {
          if (once) {
            return false;
          } else {
           once = true;
          }
    }}}
    return true;
  }

/** Jedinec::CheckMatches() 
- zkontroluje pole matches jedince, jestli v nem nejsou kolizni sloupce T */
  bool Jedinec::CheckMatches() {
    int colTP1, colTP2;
    for (int i=0; i<rank.size(); i++) {
      colTP1 = rank[i];
      for (int j=i+1; j<rank.size(); j++) {
        colTP2 = rank[j];
        if ( matches[colTP1] == matches[colTP2] ) {
          if (maticeS[colTP1][colTP2] == 0) return false;
          for (int trow = 0; trow < vyskaT; trow++) {
            if ( maticeTP[trow][colTP1] != 2 && maticeTP[trow][colTP2] != 2 &&
                 ( (maticeS[colTP1][colTP2] == 2 && maticeTP[trow][colTP1] != maticeTP[trow][colTP2]) ||
                   (maticeS[colTP1][colTP2] == 3 && maticeTP[trow][colTP1] == maticeTP[trow][colTP2]) ) )
              return false;
          }
        }
      }
    }
    return true;
  }

/** Jedinec::operator<(const Jedinec &druhy) 
- operator pro porovnavani jedincu */
  bool Jedinec::operator<(const Jedinec &druhy) {
    return fitness < druhy.fitness;
  }

/** Jedinec::operator>(const Jedinec &druhy) 
- operator pro porovnavani jedincu */
  bool Jedinec::operator>(const Jedinec &druhy) {
  return fitness > druhy.fitness;
  }

/** Get metody Jedince */
  double Jedinec::GetFitness() const {
    return fitness;
  }
  int Jedinec::GetColumnsTMatched() const {
    return columnsT_matched;
  }
  int Jedinec::GetRankSize() const {
    return rank.size();
  }
  int Jedinec::GetDirectMatches() const {
    return direct_matches;
  }
  int Jedinec::GetDirectNegMatches() const {
    return direct_neg_matches;
  }
  double Jedinec::GetPotential() const {
    return potential;
  }
  bool Jedinec::GetCrossoverFlag() const {
    return crossover_flag;
  }
  double Jedinec::GetQuality() const {
    return quality;
  }

  int Jedinec::GetRank(int r) const {
    return rank[r];
  }
  int Jedinec::GetLevel() const {
    return level;
  }

/** Set metody jedince */
  void Jedinec::SetQuality(double qual) {
    quality = qual;
  }
  void Jedinec::SetCrossoverFlag(bool value) {
    crossover_flag = value;
  }
  void Jedinec::SetCM(int r, int colTP, int colC, int neg, bool modify_certain_matches) {
    if (modify_certain_matches && r < certain_matches) certain_matches = r;
    rank[r] = colTP;
    matches[colTP] = colC;
    NM[colTP] = neg;
  }


/** int Jedinec::AddDependentColumns(int colTP)
- funkce upravi pole columnsT_mapping u zavislych sloupcu na sloupci colTP 
- vraci pocet pridanych zavislych sloupcu */
int Jedinec::AddDependentColumns(int colTP) {
  int ret = 0;
  int colT = columnsTP_mapping[colTP];
  for (int colT_dep = 0; colT_dep < sirkaT; colT_dep++) {
    if (columnsT_mapping[colT_dep] == -1 && maticeD[colT][colT_dep] > 0) {
      // pokud zavisly sloupec zatim nebyl prirazen nastavime mapovani
      columnsT_mapping[colT_dep] = colTP;
      ret++;
    } 
  }
  return ret;
}

/** void Jedinec::OptimizeDependentColumns()
- funkce spocita pocet direct matchu a pokusi se prevesit zavisle sloupce
- na jine repr. sloupce, aby vznikl direct match */
int Jedinec::OptimizeDependentColumns() {
  int colTP, colT, colTD, colC, dep;

  direct_matches += columnsT_empty;

  // dale se pokusime nastavit direct match u zavislych sloupcu 
  for (int r = 0; r < level; r++) {
    // postupujeme postupne podle ranku
    colTP = rank[r];
    colT = columnsTP_mapping[colTP];
    colTD = matches[colTP];

    dep = maticeD[colT][colTD];
    if ( (columnsT_type[colTD] == 'S' || columnsT_type[colTD] == 'M') && dep > 0) {
      // sloupec colTD je zavisly
      columnsT_mapping[colTD] = colTP;
      if ( (dep == 1 && NM[colTP] == 0) ||
           (dep == 2 && NM[colTP] == 1) ) {
        // stejne znamenkopozitivne zavisly
        direct_matches++;
      } else {
        // negativne zavisly
        direct_neg_matches++;
      }
    }
  }

}

/** CountColumnsTMatches()
- jednorazove spocita pole columnsT_matches a columnsT_NM
**/
void Jedinec::CountColumnsTMatches() {
  int colT, colTP, colTD, dep;

  columnsT_matches.resize(sirkaT);
  columnsT_NM.resize(sirkaT);

  ResetColumnsTMatches();

  // nastavime vazbu u reprezentativnich sloupcu, ktere se povedlo priradit
  for (int r = 0; r < level; r++) {
    // postupujeme postupne podle ranku, zjistime sloupec colT a colTP
    colTP = rank[r];
    colT = columnsTP_mapping[colTP];

    // nastavime columnsT_matches repr. sloupce
    columnsT_matches[colT] = matches[colTP];
    columnsT_NM[colT] = NM[colTP];

  }

  // spocitame columnsT_matches pro vedlejsi sloupce
  for (colTD = 0; colTD < sirkaT; colTD++) {
    colTP = columnsT_mapping[colTD];

    if ( (columnsT_type[colTD] == 'S' || columnsT_type[colTD] == 'M') && colTP >= 0  ) {
      // povedlo se je priradit

      colT = columnsTP_mapping[colTP];
      dep = maticeD[colT][colTD];

      columnsT_matches[colTD] = matches[colTP];
      if ( dep == 1 ) {
        columnsT_NM[colTD] = NM[colTP];
      } else if (dep == 2) {
        columnsT_NM[colTD] = (NM[colTP] + 1) % 2;
      }
    }
  }

}

/** void CountFitness(bool use_discarding)
- spocita fitness  */
  void Jedinec::CountFitness(bool use_discarding) {

    int rowC, rowT, cols_discarded;
    int colC, colTP, colT, neg;
    vector<int> p_X;
    bool assigned;
    clock_t c;
    long int total_ones, changed_ones, changed_ones_tot;

    columnsT_mapping.resize(sirkaT);
    ResetColumnsTMapping();

    p_X.resize(vyskaT);
    X.resize(vyskaT);

    // vsechna pole matice B nastavime na 1
    maticeB.SetConstValue(1);

    level = 0;
    cols_discarded = 0;
    columnsT_matched = columnsT_empty;
    direct_matches = 0;
    direct_neg_matches = 0;
    changed_ones_tot = 0;

    do {

//      cout << "CF1: " << level << ", " << certain_matches << endl;
      if (   (use_discarding && level >= certain_matches) ||
             (!use_discarding && level == certain_matches)   ) {
        // vytvoreni kopie matice B pokud pouzivame discarding a nejsme v oblasti jisteho sparovani
        p_maticeB.copy(maticeB);
      }

      // vybrani matche
      colTP = rank[level];	// dalsi sloupec T
      colC = matches[colTP];	// k nemu matchujici sloupec C
      neg = NM[colTP];		// k nemu priznak o negovani

      // uprava matice B - pri uprave matice B si spocitame pomer mezi poctem 1 a poctem nastavenych 1->0
      total_ones = 0; changed_ones = 0;
      for (rowC = 0; rowC < vyskaC; rowC++)
        for (rowT = 0; rowT < vyskaT; rowT++) {
          if (maticeB[rowC][rowT] == 1) 
          {total_ones++;
          if (((neg == 1) && (maticeTP[rowT][colTP] != 2) && (maticeC[rowC][colC] == maticeTP[rowT][colTP])) ||
            ((neg == 0) && (maticeTP[rowT][colTP] != 2) && (maticeC[rowC][colC] != maticeTP[rowT][colTP]))) {
              changed_ones++;
              maticeB[rowC][rowT] = 0;
            }
          }
          }

      if (level < certain_matches) {

        assigned = true;
      } else if (assigned = MakeRowAssignment(p_X)) {
        X = p_X;
      }

      if (assigned) {
        // povedlo se prirazeni, zapamatujeme X a budem zkouset matchovat dalsi sloupec T
//      cout << "CF2a: " << level << endl;

        level++;
        // mame o jedno sparovani vice
        columnsT_matched++;
        // pripocteme sparovani zavislych sloupcu, ktera jsou mozna
        columnsT_matched += AddDependentColumns(colTP);
        // odebereme sloupec C z listu nepouzitych sloupcu

        // pokud jde o direct match inkrementujeme direct_matches, resp. direct_neg_matches direct_matches
        colT = columnsTP_mapping[colTP];
        if ( colT == colC && neg == 0 ) direct_matches++;
        if ( colT == colC && neg == 1 ) direct_neg_matches++;

        // nastaveni columnsTP_loss
        changed_ones_tot+= changed_ones;

      } else {
        // nepovedlo se prirazeni
//      cout << "CF2b: " << level << endl;

        if (use_discarding) {
          // soucasny sloupec T jedince, na kterem prirazeni nevyslo zaradime nakonec (zahodime)
          for (int i = level; i < sirkaTP - 1; i++) {
            rank[i] = rank[i + 1];
          }
          rank[sirkaTP - 1] = colTP; 

          // inkrementujeme cislo urcujici pocet vymenenych sloupcu
          cols_discarded++;

          // obnovime puvodni matici B ze zalohy
          maticeB.copy(p_maticeB);
        }

      }

    } while ( (assigned && level < sirkaTP) || 
              (use_discarding && level < sirkaTP - cols_discarded) 
            );

    if (level == certain_matches && !assigned) {
      maticeB.copy(p_maticeB);
      if (MakeRowAssignment(p_X)) {
        X = p_X;
      } else {
        cout << "Chyba prirazeni radek po probehnuti sparovani!!!" << endl;
        exit(2);
      }
    }
    certain_matches = level;

    // - preskupi zavisle sloupce columnsT_mapping - vice direct matchu
    OptimizeDependentColumns();

    CountColumnsTMatches();

    double teoretical_loss = 1;
    for (int r = 0; r < level; r++) {
      colTP = rank[r];
      teoretical_loss *= columnsTP_avg_loss[colTP];
    }
    double real_loss = (double) ( (vyskaC * vyskaT) - changed_ones_tot) / (vyskaC * vyskaT);
    potential = pow( (double) real_loss / teoretical_loss, (double) 1 / level );

    quality = columnsT_matched + ((direct_matches + direct_neg_matches) / (double) sirkaT);
    //fitness = columnsT_matched + GetCrossoverFlag() + potential;
    fitness = quality + GetCrossoverFlag();

}

/** bool Jedinec::DetectConflict(int tcol, int ccol, neg)
- zjisti, jestli by dalsi prirazeni tcol->ccol(neg) zbusobilo logickou kolizi v matches
- predpoklada, ze konec pole rank je naplnen -1-ckami
- false - vse ok
- true - chyba
**/
bool Jedinec::DetectConflict(int colTP, int colC, int neg) {
  // zjistime, jestli bychom pri jednoduchem nastaveni sloupce C (new_colC) nezpusobili konflikt
  int p_colTP;
  bool conflict = false;
  int NM_sign = neg;

  // provedem kontrolu postupne pro r sloupcu TP v poradi pole rank
  int r = 0;
  while (rank[r] != -1 && r < sirkaTP) {

    p_colTP = rank[r];
    if (colTP == p_colTP) {
      // pokud se sloupec rovnaji vyhodi to chybu - !!! rozdilne od DetectConflictCM
      conflict = true;
      break;
    }
    if (colC == matches[p_colTP]) {
      if (maticeS[colTP][p_colTP] == 0) {
        // klasicka kolize na nedoplnujici se sloupec (dva reprezentativni sloupce se nedoplnuji)
        conflict = true;
        break;
      }
      // dalsi cast resi znamenko u pozitivne a negativne se doplnujicich sloupcu
      if (NM_sign == -1 && maticeS[colTP][p_colTP] > 1) {
        // v pripade presne zadaneho matche (EM) - vcetne znamenka se do teto vetve nedostaneme
        NM_sign = NM[colTP];
      } else if ( (maticeS[colTP][p_colTP] == 2 && NM_sign != NM[p_colTP]) ||   // pozitivni
                  (maticeS[colTP][p_colTP] == 3 && NM_sign == NM[p_colTP])      // negativni
                ) {
        conflict = true;
        break;
      }
    }

    r++;
  }
  return conflict;
}

/** in Jedinec::DetectConflictCM(int r, int tcol, int ccol)
- zjisti, jestli by dalsi prirazeni tcol->ccol(neg) zbusobilo logickou kolizi
- r - pocet sloupcu T, u kterych bude provedena kontrola (poradi bude podle rank) - 1 - sirkaTP
- -1 - nelze priradit sloupec, 0 - lze priradit sloupec pouze pozitivni
- 1 - lze priradit sloupec pouze negativne, 2 - lze priradit sloupec jakkoli
**/
int Jedinec::DetectConflictCM(int r, int colTP, int colC) {
  // zjistime, jestli bychom pri jednoduchem nastaveni sloupce C (new_colC) nezpusobili konflikt
  int p_colTP;
  bool conflict = false;
  int NM_sign = -1;
  if (r < 1 || r > sirkaTP) return false;  // tohle by snad nemelo nastat
  // provedem kontrolu postupne pro r sloupcu TP v poradi pole rank
  for (int i = 0; i < r; i++) {
    p_colTP = rank[i];
    if (colC == matches[p_colTP] && colTP != p_colTP) {
      // sloupce p_colTP a colTP musi mit v paru stejny sloupec C, aby zpusobili kolizi
      if (maticeS[colTP][p_colTP] == 0) {
        // klasicka kolize na nedoplnujici se sloupec (dva reprezentativni sloupce se nedoplnuji)
        conflict = true;
        break;
      }
      // dalsi cast resi znamenko u pozitivne a negativne se doplnujicich sloupcu
      if (NM_sign == -1 && maticeS[colTP][p_colTP] > 1) {
        NM_sign = NM[colTP];
      } else if ( (maticeS[colTP][p_colTP] == 2 && NM_sign != NM[p_colTP]) ||   // pozitivni
                  (maticeS[colTP][p_colTP] == 3 && NM_sign == NM[p_colTP])      // negativni
                ) {
        conflict = true;
        break;
      }
    }
  }
  if (conflict) return -1;
  else if (NM_sign == -1) return 2;
  else return NM_sign;
}

/** Jedinec Jedinec::UniformCrossover(Jedinec &prvni, Jedinec &druhy);
- provede uniformni krizeni dvou jedincu -> vzniknou potomek1, potomek */
Jedinec Jedinec::UniformCrossover(Jedinec &prvni, Jedinec &druhy) {
  int colTP, colC, neg, r, counter;
  list<int>::iterator it_basketTP, it_basketC, it_basketNM;
  list<int> basketTP, basketC, basketNM, columnsTP, columnsC;

  Jedinec potomek(false);

//  potomek.Vypis(cout);

  InitList(columnsTP, sirkaTP);
  InitList(columnsC, sirkaC);

  // do kose dame pary prvniho rodice
  for (r = 0; r<prvni.level; r++) {
    colTP = prvni.rank[r];
    basketTP.push_back(colTP);
    basketC.push_back(prvni.matches[colTP]);
    basketNM.push_back(prvni.NM[colTP]);
  }

  // do kose dame pary prvniho rodice
  for (r = 0; r<druhy.level; r++) {
    colTP = druhy.rank[r];
    basketTP.push_back(colTP);
    basketC.push_back(druhy.matches[colTP]);
    basketNM.push_back(druhy.NM[colTP]);
  }

  // dokud neni kos prazdny, tak z nej vybirame pary
  counter = 0;
  while (basketTP.size() > 0 && counter < sirkaTP) {
    // vybereme nahodny par
    r = rand() % basketTP.size();

    // zjistime hodnoty nahodneho paru
    it_basketTP = basketTP.begin();
    it_basketC = basketC.begin();
    it_basketNM = basketNM.begin();
    for (int i = 0; i < r; i++) {
      it_basketTP++; it_basketC++; it_basketNM++;
    }
    colTP = *it_basketTP;
    colC = *it_basketC;
    neg = *it_basketNM;

    // zkotrolujeme, jestli tento par muzeme do potomka pridat
    if ( !potomek.DetectConflict(colTP, colC, neg) ) {

      // neni konflikt - muzeme par pridat
      potomek.SetCM(counter, colTP, colC, neg);
      counter++;

      // odebereme sloupce C a TP ze zatim nepouzitych sloupcu
      RemoveValue(columnsTP, colTP);
      RemoveValue(columnsC, colC);
    }
    // vyhodime par z kose
    basketTP.erase(it_basketTP);
    basketC.erase(it_basketC);
    basketNM.erase(it_basketNM);
  }

  // doplnime ostatni sloupce ze zbyvajicich v T
  for (int i = counter; i < sirkaTP; i++) {
    // nahodne vybereme sloupec T a C - rovnou ho i odebereme z listu
    colTP = RemoveRandom(columnsTP);
    colC = RemoveRandom(columnsC);

    // priznak negovani je zcela nahodny
    neg = rand() % 2;

    // pridame par do potomka
    potomek.SetCM(i, colTP, colC, neg);
  }
  return potomek;
}

/** Jedinec Jedinec::OnePointCrossover(Jedinec &rodic1, Jedinec &rodic2);
- provede 1-bodove krizeni dvou jedincu -> vzniknou potomek1, potomek */
Jedinec Jedinec::OnePointCrossover(Jedinec &rodic1, Jedinec &rodic2) {
  int r, colTP, colC, neg, counter;
  list<int> columnsTP, columnsC;

  Jedinec potomek(false);
  InitList(columnsTP, sirkaTP);
  InitList(columnsC, sirkaC);

  int c = rand() % rodic1.level;
  for (r = 0; r < c; r++) {
    colTP = rodic1.rank[r];
    colC = rodic1.matches[colTP];
    neg = rodic1.NM[colTP];

    potomek.SetCM(r, colTP, colC, neg, false);
    RemoveValue(columnsTP, colTP);
    RemoveValue(columnsC, colC);
  }

  counter = c;
  for (r = 0; r < rodic2.level; r++) {
    colTP = rodic2.rank[r];
    colC = rodic2.matches[colTP];
    neg = rodic2.NM[colTP];

    if (!potomek.DetectConflict(colTP, colC, neg)) {
      colC = rodic2.matches[colTP];
      neg = rodic2.NM[colTP];

      potomek.SetCM(counter, colTP, colC, neg);
      counter++;

      RemoveValue(columnsTP, colTP);
      RemoveValue(columnsC, colC);
    }
  }

  // doplnime ostatni sloupce ze zbyvajicich v T
  for (int i = counter; i < sirkaTP; i++) {
    // nahodne vybereme sloupec T a C - rovnou ho i odebereme z listu
    colTP = RemoveRandom(columnsTP);
    colC = RemoveRandom(columnsC);

    // priznak negovani je zcela nahodny
    neg = rand() % 2;

    // pridame par do potomka
    potomek.SetCM(i, colTP, colC, neg);
  }
//  potomek.Vypis(cout);
  potomek.certain_matches = c;
  return potomek;

}

/** void MatchesMutation(double pm);
- provede mutaci pole matches */
void Jedinec::MatchesMutation(double pm) {
  int old_colC, new_colC, colTP;
  vector<bool> matches_changed;
  matches_changed.resize(sirkaTP);

  for (int i = 0; i < sirkaTP; i++) matches_changed[i] = false;

  for (colTP = 0; colTP < sirkaTP; colTP++) {
    if (GetRandomInterval() < pm) {

      old_colC = matches[colTP];
      new_colC = rand() % sirkaC;

      // zjistime, jestli bychom pri jednoduchem nastaveni sloupce C (new_colC) nezpusobili konflikt
      int NM_sign = DetectConflictCM(sirkaTP, colTP, new_colC);

      if (NM_sign == -1) {
        // konflikt - vymenime puvodni sloupec colC za novy colC v celem matches, znamenko nemenime
        for (int p_colTP = 0; p_colTP < sirkaTP; p_colTP++) {
          if (matches[p_colTP] == old_colC) {
            matches[p_colTP] = new_colC;
            matches_changed[p_colTP] = true;
          } else if (matches[p_colTP] == new_colC) {
            matches[p_colTP] = old_colC;
            matches_changed[p_colTP] = true;
          }
        }
      } else {
        // bez konfliktu - nastavime novy sloupec C
        matches[colTP] = new_colC;
        if (NM_sign == 2) {
          NM[colTP] = rand() % 2;
        } else {
          NM[colTP] = NM_sign;
        }
        matches_changed[colTP] = true;
      }
    }
  }

  for (int r = 0; r < sirkaTP; r++) {
    colTP = rank[r];
    if (r == certain_matches) break;
    if (matches_changed[colTP] == true ) {
      certain_matches = r;
      break;
    }
  }

}

/** void RankInsertMutation(double pr1);
- provede mutaci pole rank - vlozeni v permutaci */
void Jedinec::RankInsertMutation(double pr1) {
  int tmp, pos;
//  cout << "RIM" << endl;
//  VypisRank(cout);
  for (int r = 0; r < sirkaTP; r++) {
    if (GetRandomInterval() < pr1) {
      pos = rand() % sirkaTP;
//      cout << "r: " << r << "pos: " << pos << endl;
      if (pos > r) {
        tmp = rank[r];
        for (int i = r; i < pos; i++) rank[i] = rank[i+1];
        rank[pos] = tmp;
        if (r < certain_matches && pos >= level) certain_matches--; 
      } else if (pos < r) {
        tmp = rank[r];
        for (int i = r; i > pos; i--) rank[i] = rank[i-1];
        rank[pos] = tmp;
        if (pos < certain_matches && r >= certain_matches) certain_matches = pos;
      }
    }
  }
//  VypisRank(cout);
}

/** void RankMoveMutation(double pr2);
- provede mutaci pole rank - vymena sousedu */
void Jedinec::RankMoveMutation(double pr2) {
  int tmp;
  for (int r = 0; r < sirkaTP - 1; r++) {
    if (GetRandomInterval() < pr2) {
      tmp = rank[r];
      rank[r] = rank[r+1];
      rank[r+1] = tmp;
      if (certain_matches == r+1) certain_matches = r;
    }
  }
}

/** void LocalMutation()
- nahodne naplni cast pole rank za urovni level */
void Jedinec::LocalMutation() {
  int colTP, colC, neg;
  list<int> columnsC;

  InitList(columnsC, sirkaC);

  for (int i = 0; i < level; i++) {
    colTP = rank[i];
    colC = matches[colTP];

    RemoveValue(columnsC, colC);
  }

  for (int i = level; i < sirkaTP; i++) {

    // nahodne vybereme sloupec C - rovnou ho i odebereme z listu
    colC = RemoveRandom(columnsC);
    colTP = rank[i];
    neg = rand() % 2;

    SetCM(i, colTP, colC, neg);
  }
}

/** Jedinec::AdjustStatistics()
- upravi statistiky pro pole rank a matches */
void Jedinec::AdjustStatistics() {
  int colTP, colC, r;

  for (r=0; r<rank.size(); r++) {
    colTP = rank[r];
    colC = matches[colTP];
    rank_statistics[colTP][r]++;
    matches_statistics[colTP][colC]++;
    matches_colTP_stat[colTP]++;
  }
}

/** Jedinec::CheckRowAssignment()
- zkontroluje prirazeni radek ve vektoru X - jestli prorazane matice C odpovida sparovanym sloupcum a matici T */
bool Jedinec::CheckRowAssignment() {
  int r, colTP, colC, rowC, rowT;
  short int neg;

  if (X.size() > 0) {
    for (r = 0; r < level; r++) {
      colTP = rank[r];
      colC = matches[colTP];
      neg = NM[colTP];
      for (rowT = 0; rowT < vyskaT; rowT++) {
        rowC = X[rowT];
        if (maticeTP[rowT][colTP] != 2)
        if ((neg == 1 && maticeC[rowC][colC] == maticeTP[rowT][colTP]) ||
            (neg == 0 && maticeC[rowC][colC] != maticeTP[rowT][colTP]))
          return false;
      }
    }
  }
  return true;
}

/** Jedinec::FinalOptimalization()
- pokusi se o prirazeni direct matche u zavislych sloupcu */
void Jedinec::FinalOptimalization() {
  int colT, colTP, colC, rowC, rowT, r, neg, ndc_count;
  bool assigned;
  vector<int> p_X;

  p_X.resize(vyskaT);
  typedef multimap<int,int> T_HT;		// hash mapa
  T_HT ndc_tab;					// klic - pocet ne don't care hodnot (0, 1)
						// hodnota - sloupec T
  T_HT::iterator it;

//cout << "FO1" << endl;
  for (colT = 0; colT < sirkaT; colT++) {
    colC = columnsT_matches[colT];
    if ((columnsT_type[colT] == 'M' || columnsT_type[colT] == 'S') && colT != colC) {
      // zavisly sloupec bez direct matche - spocitame pocet 0 a 1 v matici T a pridame do hash mapy
      ndc_count = 0;
      for (rowT = 0; rowT < vyskaT; rowT++)
        if (maticeT[rowT][colT] != 2) ndc_count++;

      ndc_tab.insert(make_pair(ndc_count++, colT));
    }
  }

  // pripravime matici B - provedeme row assignement sparovanych reprezentativnich sloupcu
//cout << "FO2" << endl;

  // vsechna pole matice B nastavime na 1
  maticeB.SetConstValue(1);

//cout << "FO2" << endl;
  for (r = 0; r < level; r++) {
    colTP = rank[r];
    colC = matches[colTP];	// k nemu matchujici sloupec C
    neg = NM[colTP];

    // uprava matice B - zde pracujeme s matici TP stejne jako v CountFitness
    for (rowC = 0; rowC < vyskaC; rowC++)
      for (rowT = 0; rowT < vyskaT; rowT++) {
        if (((neg == 1) && (maticeTP[rowT][colTP] != 2) && (maticeC[rowC][colC] == maticeTP[rowT][colTP])) ||
          ((neg == 0) && (maticeTP[rowT][colTP] != 2) && (maticeC[rowC][colC] != maticeTP[rowT][colTP]))) {
            maticeB[rowC][rowT] = 0;
          }
        }
  }

  // pokusime se provest direct match sloupcu v hash mape v poradi poctu ne don't care hodnot
//cout << "FO3" << endl;
  for (it = ndc_tab.begin(); it != ndc_tab.end(); it++) {
    // direct match
    colT = it->second;
    colC = colT;

    // nejdrive pozitivni, pak negativni
    for (neg = 0; neg < 2; neg++) {

      // pokud se povede prirazeni u pozitivniho matche, tak se o negativni nepokousime
      if (assigned && neg == 1) break;
      else assigned = false;

      // vytvoreni kopie matice B - zaloha, kdyz se po direct matchi nepovede row assignment
      p_maticeB.copy(maticeB);

      // uprava matice B - zde uz pracujeme s matici T !!! - jsou to zavisle sloupce
      for (rowC = 0; rowC < vyskaC; rowC++)
        for (rowT = 0; rowT < vyskaT; rowT++) {
          if (((neg == 1) && (maticeT[rowT][colT] != 2) && (maticeC[rowC][colC] == maticeT[rowT][colT])) ||
            ((neg == 0) && (maticeT[rowT][colT] != 2) && (maticeC[rowC][colC] != maticeT[rowT][colT]))) {
              maticeB[rowC][rowT] = 0;
            }
          }


      if (assigned = MakeRowAssignment(p_X)) {
        // povedlo se prirazeni, zapamatujeme X a budem zkouset matchovat dalsi zavisly sloupec T
        X = p_X;

        if (neg == 0) direct_matches++;
        if (neg == 1) direct_neg_matches++;

        if (columnsT_matches[colT] == -1) columnsT_matched++;

        //cout << colT << "->" << colC << "(" << neg << ")" << endl;
        // upravime vystupni mapovani
        columnsT_matches[colT] = colC;
        columnsT_NM[colT] = neg;


      } else {

        // obnovime matici B ze zalohy
        maticeB.copy(p_maticeB);
      }
    }
  }

  quality = columnsT_matched + ((direct_matches + direct_neg_matches) / (double) sirkaT);
}


/** Jedinec::CreatePLAFile()
- vytvori vystupni PLA soubor z tohoto jedince */
void Jedinec::CreatePLAFile() {
  int r, cnt, rowC, rowT, colT, colTP;
  vector<int> not_matched_columns;
  short int value;
  char output_pla[50];
  ofstream os;

  sprintf(output_pla, "%s%s.pla", output_dir, test_name);

  os.open(output_pla);

  os << ".i " << sirkaC << endl;
  os << ".o " << sirkaT - columnsT_matched << endl;
  os << ".p " << vyskaT << endl;
  os << ".type fr" << endl;

  // vytvorime si serazene pole nesparovanych sloupcu - not_matched_columns
  not_matched_columns.resize(0);
  cnt = 0;

  // naplnime nesparovanymi sloupci
  for (colT = 0; colT < sirkaT; colT++) {
    if (columnsT_matches[colT] == -1) {
      not_matched_columns.push_back(colT);
      cnt++;
    }
  }
  // setridime
  sort(not_matched_columns.begin(), not_matched_columns.end());

  // po radcich matice T vypisujeme
  for (rowT = 0; rowT < vyskaT; rowT++) {
    rowC = X[rowT];
    maticeC.vypisRadek_bin(os, rowC, false);
    os << " ";

    for (r = 0; r < cnt; r++) {
      colT = not_matched_columns[r];
      vypisBinary(os, maticeT[rowT][colT]);
    }
    os << endl;
  }
  os << ".e" << endl;

  os.close();
}


/** Jedinec::CreateMatchesFile()
- vytvori vystupni soubor matches z tohoto jedince */
void Jedinec::CreateMatchesFile() {
  int colT, colC, neg, colTP;
  char output_matches[50];
  ofstream os;

  sprintf(output_matches, "%s%s.matches", output_dir, test_name);

  os.open(output_matches);

  for (colT = 0; colT < sirkaT; colT++) {
    colC = columnsT_matches[colT];
    if (colC >= 0) {
      neg = (columnsT_NM[colT] + 1) %2;
      os << colC << " -> " << colT << " (" << neg << ")" << endl;
    }
  }

  os.close();
}


/** ************************************ Populace  ************************************* */

bool SortOperator(const Jedinec& a, const Jedinec& b) {
//  cout << "a: " << a.GetFitness() << "b: " <<b.GetFitness()<< endl;
  return a.GetFitness() > b.GetFitness();
}

Populace::Populace(int pop_size) {

  size = pop_size;
  generation = 0;

  avg_fitness = -1;
  avg_level = -1;

  best_fitness = -1;
  best_columnsT_matched = -1;

  vect.resize(size);

  Jedinec *j;
  for (unsigned int i=0; i < size; i++) {
    j = new Jedinec();
     vect[i] = *j;
    delete j;
  }
}

Populace::Populace(const Populace& s):
  size(s.size), generation(s.generation), avg_fitness(s.avg_fitness), avg_level(s.avg_level),
  best_fitness(s.best_fitness), best_columnsT_matched(s.best_columnsT_matched),
  vect(s.vect), best_jedinec(s.best_jedinec) {}

void Populace::Evaluate(bool use_discarding) {

  for (int i = 0; i < size; i++) {
    vect[i].CountFitness(use_discarding);
  }

  Sort();

  CountProperties();
}

void Populace::Sort() {
  sort(vect.begin(), vect.end(), SortOperator);
}


void Populace::GenerateNext(int ps, int crossover_method, double pc, double pm, 
                            double pr1, double pr2, bool use_thresholding) {
  int rodic1, rodic2, i;
  Jedinec potomek(false);

  generation++;

//  cout << "GN0 " << endl;
  vector<Jedinec> new_vect;
  //krizeni + mutace
  while (new_vect.size() < size) {
//    cout << "GN1: " << new_vect.size() << endl;

    rodic1 = SelectIndividual(use_thresholding, ps);
    rodic2 = SelectIndividual(use_thresholding, ps);
//off << "---------------XXXXXXXXXXXXXXXXXXXXX0-------------------" << endl;
//vect[rodic1].Vypis(off);
//vect[rodic2].Vypis(off);
//    cout << "GN2: " << new_vect.size() << endl;

    if (GetRandomInterval() < pc) {
//      cout << "GN2a: " << new_vect.size() << endl;
      if (crossover_method == 1) {
        potomek = Jedinec::OnePointCrossover(vect[rodic1], vect[rodic2]);
      } else {
        potomek = Jedinec::UniformCrossover(vect[rodic1], vect[rodic2]);
      }
      potomek.SetCrossoverFlag(true);
    } else {
//      cout << "GN2b: " << new_vect.size() << endl;
      potomek = vect[rodic1];
      potomek.LocalMutation();
      potomek.SetCrossoverFlag(false);
    }

//    cout << "GN3: " << new_vect.size() << endl;
    potomek.MatchesMutation(pm);
    potomek.RankInsertMutation(pr1);
    potomek.RankMoveMutation(pr2);

//    cout << "GN4: " << new_vect.size() << endl;
    new_vect.push_back(potomek);
//potomek1.Vypis(off);
//potomek2.Vypis(off);
//off << "---------------XXXXXXXXXXXXXXXXXXXXX0-------------------" << endl;

//    cout << "GN4: " << new_vect.size() << endl;
  }

//  cout << "GN5: " << new_vect.size() << endl;
  vect = new_vect;
//  cout << "GN6: " << new_vect.size() << endl;

}

void Populace::CountProperties() {
  double suma_f, suma_level, f;
  Jedinec tmp(false);
  int colTP;
  suma_f = 0;
  suma_level = 0;
  best_fitness = 0;
  best_columnsT_matched = 0;

  genes_amount.resize(sirkaTP);
  for (colTP=0; colTP < sirkaTP; colTP++) genes_amount[colTP] = 0;

  for (int i=0; i<size; i++) {
    vect[i].AdjustStatistics();

    suma_level += vect[i].GetLevel();

    f = vect[i].GetFitness();
    suma_f += f;
    if (f > best_fitness) best_fitness = f;
    if (vect[i].GetColumnsTMatched() > best_columnsT_matched)
      best_columnsT_matched = vect[i].GetColumnsTMatched();

    if ( vect[i].GetQuality() > best_jedinec.GetQuality() ) {
      tmp = vect[i];
      tmp.FinalOptimalization();
      if (best_jedinec.GetColumnsTMatched() < tmp.GetColumnsTMatched() ||
          (best_jedinec.GetColumnsTMatched() == tmp.GetColumnsTMatched() &&
           best_jedinec.GetDirectMatches() + best_jedinec.GetDirectNegMatches() <
           tmp.GetDirectMatches() + tmp.GetDirectNegMatches()) ||
          (best_jedinec.GetColumnsTMatched() == tmp.GetColumnsTMatched() &&
           best_jedinec.GetDirectMatches() + best_jedinec.GetDirectNegMatches() ==
           tmp.GetDirectMatches() + tmp.GetDirectNegMatches() &&
           best_jedinec.GetDirectMatches() < tmp.GetDirectMatches())
      ) {
        best_jedinec = tmp;
        best_jedinec.Vypis(off);
        best_jedinec.CreatePLAFile();
        best_jedinec.CreateMatchesFile();
      }
    }

    avg_fitness = suma_f / size;
    avg_level = suma_level / size;

    for (int j = 0; j < vect[i].GetLevel(); j++) {
      colTP = vect[i].GetRank(j);
      genes_amount[colTP]++;
    }
  }
//  vypis(cout, genes_amount.begin(), genes_amount.end());
}

int Populace::SelectIndividual(bool use_thresholding, int ps) {
  int ret, next;

  int threshold;
  int shuffle_number = sirkaTP;
//  cout << "Tournament" <<  endl;
  ret = rand() % size;
//  cout << ret << endl;
  for (int c = 1; c < ps; c++) {
    if ( use_thresholding ) {
      for (int i = 0; i < shuffle_number; i++) {
        next = rand() % size;
//        cout << "NEXT: " << next << ", " << vect[next].GetLevel() << ", " << vect[ret].GetLevel() << ", " << vect[ret].GetLevel() * vect[next].GetLevel();
        threshold = (int) ceil((double) vect[ret].GetLevel() * vect[next].GetLevel() / sirkaTP);
//        cout << ", " << threshold << " vs " << vect[ret].CommonGenes(vect[next]) << endl;
        if (threshold <= vect[ret].CommonGenes(vect[next]) ) {
          // compete
//          cout << "competing: " << next << ", " << vect[ret].CommonGenes(vect[next]) << endl;
          if ( vect[next] > vect[ret] ) ret = next;
          break;
        }
      }
    } else {
      next = rand() % size;
//      cout << next;

      // compete
      if ( vect[next] > vect[ret] ) ret = next;
    }
  }

  return ret;
}

void Populace::ZeroAvgValues() {
  avg_level = 0;
  avg_fitness = 0;
}

void Populace::Vypis(ostream &os) {
  int x;
  VypisOddelovac(os);
  off << "Vypis populace " << generation << endl;

  if (size > 100) x = 100;
  else x = size;

  for (int i = 0; i<x; i++) {
    off << left << setw(7) << vect[i].GetFitness() << " " << setw(5) << vect[i].GetLevel();
    off << setw(5) << vect[i].GetColumnsTMatched();
    off << setw(5) << vect[i].GetDirectMatches() << setw(5) << vect[i].GetDirectNegMatches();
    off << setw(7) << vect[i].GetPotential();
    off << " " << setw(2) << vect[i].GetCrossoverFlag();
    off << ">>> ";
    vect[i].VypisMatches(off);
  }

}

Jedinec Populace::Get(int i) const {
  return vect[i];
}

/** GraphLog(ostream &os)
- zaloguje hodnoty do souboru se vstupnimi hodnotami pro graf */
void Populace::GraphLog(ostream &os) {
  os << generation;
  os.put(9);
  os << best_columnsT_matched;
  os.put(9);
  os << best_fitness;
  os.put(9);
  os << avg_fitness;
  os.put(9);
  os << avg_level << endl;
}


/** ************************************* MATICE a POLE ************************************** */

void NactiMatice(char nameC[], char nameT[]) {
  int znak;
  int pos;

  vector<vector<short int> > tmp_matrix;

  //nacetni matice C
  ifstream ifileC(nameC);
  do {
    // dalsi radek
    tmp_matrix.push_back(*new vector<short int>);
    pos=0;
    do {
      znak = ifileC.get();
      switch (znak) {
        case 48:
        case 49:
          tmp_matrix.back().push_back(znak - 48);
          pos++;
        break;
      }
    } while (ifileC && (znak!=10 || pos==0));
    if (tmp_matrix.back().size() == 0) tmp_matrix.pop_back();
  } while (ifileC);
  vyskaC = tmp_matrix.size();
  sirkaC = tmp_matrix[0].size();

  off << "vyska matice C: " << vyskaC << endl;
  off << "sirka matice C: " << sirkaC << endl;

  maticeC.CreateMatrix(vyskaC, sirkaC);
  for (int i=0; i < vyskaC; i++) {
    for (int j=0; j < sirkaC; j++) {
      maticeC[i][j] = tmp_matrix[i][j];
    }
  }

  tmp_matrix.resize(0);

    //nacetni matice T
  ifstream ifileT(nameT);
  do {
    // dalsi radek
    tmp_matrix.push_back(*new vector<short int>);
    pos=0;
    do {
      znak = ifileT.get();
      switch (znak) {
        case 48:
        case 49:
        case 50:

          tmp_matrix.back().push_back(znak - 48);
          pos++;
        break;
        case 45:
        case 88:
        case 120:
          tmp_matrix.back().push_back(2);
          pos++;
        break;
      }
    } while (ifileT && (znak!=10 || pos==0));
    if (tmp_matrix.back().size() == 0) tmp_matrix.pop_back();
  } while (ifileT);
  vyskaT = tmp_matrix.size();
  sirkaT = tmp_matrix[0].size();

  off << "vyska matice T: " << vyskaT << endl;
  off << "sirka matice T: " << sirkaT << endl;

  maticeT.CreateMatrix(vyskaT, sirkaT);
  for (int i=0; i < vyskaT; i++) {
    for (int j=0; j < sirkaT; j++) {
      maticeT[i][j] = tmp_matrix[i][j];
    }
  }

  // vytvoreni matice B
  maticeB.CreateMatrix(vyskaC, vyskaT);
  p_maticeB.CreateMatrix(vyskaC, vyskaT);
  CROW_COUNTER.CreateArray(vyskaC);
  TROW_COUNTER.CreateArray(vyskaT);

}

void AnalyseMatrixT() {

  bool positive, error, waiting;
  int tcol, trow, crow, cnt, max, tcold, i, j;
  vector<short int> dependent_columns(sirkaT), rank_dep(sirkaT), tmp_dependent_columns(sirkaT);

  // nastavime velikost matice D
  maticeD.CreateMatrix(sirkaT, sirkaT);

  cout << "R - reprezentativni sloupec" << endl;
  cout << "M - hlavni sloupec" << endl;
  cout << "S - zavisly sloupec" << endl;
  cout << "E - prazdny sloupec" << endl;

  for (tcol = 0; tcol < sirkaT; tcol++) {
    for (tcold = 0; tcold < sirkaT; tcold++) {
      if (tcol == tcold) {
        maticeD[tcol][tcold] = -1;
      } else  {
        waiting = true;
        positive = true;
        error = false;
        trow = 0;
        do {
          if ( maticeT[trow][tcold] == 2) {
          } else if ( waiting ) {
            if ( maticeT[trow][tcol] == 2 ) {
              error = true;
            } else if ( maticeT[trow][tcol] == maticeT[trow][tcold] ) {
              positive = true;
            } else {
              positive = false;
            }
            waiting = false;
          } else if ( (maticeT[trow][tcol] == 2 ) ||
                      (positive && maticeT[trow][tcol] != maticeT[trow][tcold]) ||
                      (!positive && maticeT[trow][tcol] == maticeT[trow][tcold]) ) {
            error = true;
          }
          trow++;
        } while ( !error && trow < vyskaT);
        if (error) {
          maticeD[tcol][tcold] = 0;
        } else if (positive) {
          maticeD[tcol][tcold] = 1;
        } else {
          // not error and negative
          maticeD[tcol][tcold] = 2;
        }
      }
    }
  }

//  cout << "AMT1" << endl;
  // naplnime pole columnsT_type - zatim pouze typ E - prazdny a X - neurceny (bude pozdeji dopocitan)
  columnsT_type.resize(sirkaT);

  bool empty;
  for (tcol = 0; tcol < sirkaT; tcol++) {
    empty = true;
    for (trow = 0; trow < vyskaT; trow++) {
      if (maticeT[trow][tcol] != 2) empty = false;
      if (!empty) break;
    }
    if (empty) columnsT_type[tcol] = 'E';
    else columnsT_type[tcol] = 'X';
  }

//  cout << "AMT2" << endl;

  // do dependent_columns se naplni pocty jednicek v radku matice D - maji pod sebou nejvice zavislych sloupcu
  // postupne se vybiraji ty, ktere maji nejvice jednicek (repr. sloupce) a urcuji k nim hlavni a zavisle sloupce
  // pokud je sloupec urcen, pak je mu nastaveno -1 do tmp_repr_columns
  for (tcol = 0; tcol < sirkaT; tcol++) {
    cnt = 0;
    for (tcold = 0; tcold < sirkaT; tcold++) {
      if (maticeD[tcol][tcold] > 0) cnt++;
    }
    if (columnsT_type[tcol] == 'X') dependent_columns[tcol] = cnt;
  }

//  cout << "AMT3" << endl;
  // insert sortem vytvorime pole poradi sloupcu T sestupne s poctem zavislych sloupcu - rank_dep
  for (i = 0; i < sirkaT; i++) {
    tmp_dependent_columns[i] = dependent_columns[i];
  }
  for (int inserted = 0; inserted < sirkaT; inserted++) {
    // na jakou pozici i mame vlozit sloupec
    for (i = 0; i < inserted; i++) {
      //cout << i << endl;
      if (dependent_columns[inserted] > tmp_dependent_columns[i]) { 
        break;
      }
    }
    // posunu pole v rank dep o 1 dozadu za pozici i
    for (j = inserted; j > i; j--) {
        rank_dep[j] = rank_dep[j-1];
        tmp_dependent_columns[j] = tmp_dependent_columns[j-1];
    }

    // na pozici i vlozim sloupec T
    rank_dep[i] = inserted;
    tmp_dependent_columns[i] = dependent_columns[inserted];

  }

//  cout << "AMT4" << endl;
  // nastavim typ sloupcu pro zbyle sloupce  - R - reprezentativni, M - hlavni, S - zavisly
  for (int r = 0; r < sirkaT; r++) {
    tcol = rank_dep[r];
    if (columnsT_type[tcol] == 'X') {
      // sloupec jeste nebyl zarazen do skupiny - protoze postupujeme sestupne jedna se o reprezentativni sloupec
      columnsT_type[tcol] = 'R';
      for (int tcold = 0; tcold < sirkaT; tcold++) {
        if (columnsT_type[tcold] == 'X' && maticeD[tcol][tcold] > 0) {
          // sloupec tcold je zavisly na tcol
          if (dependent_columns[tcol] == dependent_columns[tcold]) {
             // hlavni sloupec - ma stejne mnozstvi zavislych sloupcu jako sloupec reprezentativni
             columnsT_type[tcold] = 'M';
          } else {
             columnsT_type[tcold] = 'S';
          }
        }
      }
    }
  }
  vypis_ns(cout, columnsT_type);


//  cout << "AMT5" << endl;
  int pocetR = 0;
  columnsT_empty = 0;
  int pocetM = 0;
  int pocetS = 0;
  int max_size = 0;
  for (tcol = 0; tcol < sirkaT; tcol++) {
    if (columnsT_type[tcol] == 'R') pocetR++;
    else if (columnsT_type[tcol] == 'E') columnsT_empty++;
    else if (columnsT_type[tcol] == 'M') pocetM++;
    else if (columnsT_type[tcol] == 'S') pocetS++;

    // spocitam nejvetsi skupinu
    if (columnsT_type[tcol] == 'R') {
      cnt = 0;
      for (tcold = 0; tcold < sirkaT; tcold++) {
        if (columnsT_type[tcold] != 'E' && maticeD[tcol][tcold] > 0) cnt++;
      }
      cnt++; // pripoctu i sebe
      if (cnt > max_size) max_size = cnt;
    } 
  }
  cout << endl;
  cout << "Pocet sloupcu:                 " << sirkaT << endl;
  cout << "Pocet repr. sloupcu (skupin):  " << pocetR << endl;
  cout << "Pocet hlavnich sloupcu:        " << pocetM << endl;
  cout << "Pocet zavislych sloupcu:       " << pocetS << endl;
  cout << "Pocet prazdnych sloupcu:       " << columnsT_empty << endl;
  cout << "Velikost nejvetsi skupiny:     " << max_size << endl;

  // spocitame reprezentativni sloupce
  sirkaTP = 0;
  for (tcol = 0; tcol < sirkaT; tcol++) {
    if (columnsT_type[tcol] == 'R') {
      sirkaTP++;
    }
  }

  // vytvorime prazdne templaty matches a NM - na počátku naplneno samymi -1 (prazdna template)
  // vytvoreni matice TP - prorezana matice T - pouze reprezentativni sloupce matice T
  // vytvoreni columnsTP_mapping - mapovani reprezentativnich sloupcu
  columnsTP_mapping.CreateArray(sirkaTP);
  maticeTP.CreateMatrix(vyskaT, sirkaTP);

  i = 0;
  for (tcol = 0; tcol < sirkaT; tcol++) {
    if (columnsT_type[tcol] == 'R') {

      // nastavime columnsTP_mapping
      columnsTP_mapping[i] = tcol;

      // vyplnime sloupec matice TP
      for (trow = 0; trow < vyskaT; trow++) {
        maticeTP[trow][i] = maticeT[trow][tcol];
      }

      // inkrementujeme citac sloupcu TP
      i++;
    }
  }
  off << "matice TP" << endl;
  maticeTP.vypis_bin(off);

  off << "matice TP" << endl;
  columnsTP_mapping.vypis(off);

//  cout << "AMT7" << endl;

//  cout << "maticeTP: " << endl;
//  vypis(cout, maticeTP, vyskaT, sirkaTP);
//  cout << "columnsTP_mapping: " << endl;
//  vypis(cout, columnsTP_mapping, sirkaTP);

  // nastavime velikost matice S
  maticeS.CreateMatrix(sirkaTP, sirkaTP);

  // naplnie matici S - popisuje doplnujici se sloupce
  int supplement_type;
  cnt = 0;
  for (i = 0; i < sirkaTP; i++) {
    maticeS[i][i] = -1;
    supplement_type = 1;		// vychozi stav - sloupce se doplnuji nezavisle
    for (j = i+1; j < sirkaTP; j++) {
      for (trow = 0; trow < vyskaT; trow++) {
        if (supplement_type == 1 && maticeTP[trow][i] != 2 && maticeTP[trow][j] != 2) {
          if (maticeTP[trow][i] == maticeTP[trow][j]) {
            supplement_type = 2;
          } else {
            supplement_type = 3;
          }
        } else if (maticeTP[trow][i] != 2 && maticeTP[trow][j] != 2 &&
                  ( ( supplement_type = 2 && maticeTP[trow][i] != maticeTP[trow][j] ) ||
                    ( supplement_type = 3 && maticeTP[trow][i] == maticeTP[trow][j] ) ) ) {
          supplement_type = 0;
          break;
        }
      }
      if (supplement_type > 0) {
        cnt++;
      }
      maticeS[i][j] = supplement_type;
      maticeS[j][i] = supplement_type;
    }
  }
  cout << "Pomer doplnujicich se sloupcu: " << (double) cnt / (sirkaTP * (sirkaTP-1) / 2) << endl << endl;
  //vypis_ns(cout, maticeS, sirkaTP, sirkaTP);

//  cout << "AMT8" << endl;
  // vytvorime matice maticeLP a maticeLN - jedna se o matice ubytku jednicek sparovanim T->C
/*  maticeLP.CreateMatrix(sirkaTP, sirkaC);
  maticeLN.CreateMatrix(sirkaTP, sirkaC);

  int total_ones, changed_ones;
  total_ones = vyskaT * vyskaC;

/*  for (int tcol = 0; tcol < sirkaTP; tcol ++) 
      for (int ccol = 0; ccol < sirkaC; ccol ++) 
        for (int neg = 0; neg < 2; neg++) {

          // spocitame, kolik by se odebralo jednicek z matice B
          changed_ones = 0;
          for (crow = 0; crow < vyskaC; crow++)
            for (trow = 0; trow < vyskaT; trow++) {
              if (((neg == 1) && (maticeTP[trow][tcol] != 2) && (maticeC[crow][ccol] == maticeTP[trow][tcol])) ||
                ((neg == 0) && (maticeTP[trow][tcol] != 2) && (maticeC[crow][ccol] != maticeTP[trow][tcol]))) {
                  changed_ones++;
              }
            }

          if (neg == 0) maticeLP[tcol][ccol] = 1.0 - (double) changed_ones / total_ones;
            else maticeLN[tcol][ccol] = 1.0 - (double) changed_ones / total_ones;
        }
*/
  // spocitam pole columnsTP_DCs - pomer don't care hodnot ve sloupcich TP
  columnsTP_avg_loss.CreateArray(sirkaTP);

  for (i = 0; i < sirkaTP; i++) {
    cnt = 0;
    for (trow = 0; trow < vyskaT; trow++) {
      if (maticeTP[trow][i] == 2) cnt++;
    }
    columnsTP_avg_loss[i] = 0.5 + ((double) cnt / vyskaT / 2);
  }
//  cout << "AMT9" << endl;*/

}


/** *************************************** HLAVNI PROGRAM ******************************** */
int	main(int argc, char* argv[])
{

  for (int i = 0; i < argc; i++) cout << argv[i] << " ";
  cout << endl;

  if (argc < 2) {
    cout << endl;
    cout << "Pouziti: ./bist parameter_file" << endl;
    exit(1);
  }

  srand(time(NULL));

  sprintf(test_name, "%s", argv[1]);
  //sprintf(output_dir, "_%s/", test_name);
  sprintf(output_dir, "");
  sprintf(output_out, "%s%s.out", output_dir, test_name);
  sprintf(output_graph, "%s%s.graph", output_dir, test_name);

  inn.open(test_name);
  off.open(output_out);
  off_graph.open(output_graph);

  // zpracovani vstupnich parametru

  int pop_count, max_generations, pt, pop_size, max_duration, ps, crossover_method;
  bool estimate_pop_size, use_thresholding, use_discarding;
  double pc, pm, pr1, pr2;
  string tmp;
  char matrixC_name[50], matrixT_name[50];

  inn >> tmp; inn >> matrixC_name;
  inn >> tmp; inn >> matrixT_name;
  inn >> tmp; inn >> estimate_pop_size;
  inn >> tmp; inn >> max_duration;
  inn >> tmp; inn >> pop_size;
  inn >> tmp; inn >> max_generations;
  inn >> tmp; inn >> pt;
  inn >> tmp; inn >> ps;
  inn >> tmp; inn >> use_thresholding;
  inn >> tmp; inn >> crossover_method;
  inn >> tmp; inn >> pc;
  inn >> tmp; inn >> use_discarding;
  inn >> tmp; inn >> pm;
  inn >> tmp; inn >> pr1;
  inn >> tmp; inn >> pr2;
  pop_count = max_generations;

  // nacteni matice
  cout << "Nacitam matice ..." << endl;
  NactiMatice(matrixC_name, matrixT_name);
  cout << endl;

  cout << "Analyza matic ..." << endl;
  AnalyseMatrixT();
  cout << endl;

  // odhad doby vypoctu, nastaveni velikosti populace
  Jedinec *testj;
  clock_t start_ftime;
  double doba_vypoctu;
  int est_duration;

  testj = new Jedinec();
  cout << "Vypocet fitness testovaciho jedince ..." << endl;
  start_ftime = clock();
  testj->CountFitness(true);			// pro odhad pouzijeme discarding
  doba_vypoctu = (double) (clock() - start_ftime) / CLOCKS_PER_SEC;
  testj->Vypis(cout);

  cout << "Vypocet fitness trva priblizne " << doba_vypoctu << " s." << endl;

  // TODO odstranit - pouze pro testovaci ucely
  /*if (doba_vypoctu < 0.1) {
    pop_size = 1000;
  } else if (doba_vypoctu < 1) {
    pop_size = 500;
  } else if (doba_vypoctu < 6) {
    pop_size = 70;
  } else {
    pop_size = 20;
  }*/


  if (estimate_pop_size) {
    pop_size = sirkaTP * (sirkaTP-1) * sirkaC * (sirkaC-1) * 2  /
               testj->GetColumnsTMatched() / (testj->GetColumnsTMatched()-1);
    cout << "Odhadnuta velikost populace: " << pop_size << endl;
  } else {
    cout << "Velikost populace: " << pop_size << endl;
  }

  delete testj;

  est_duration = (int) (doba_vypoctu * pop_size * (pop_count+1));
  cout << "Odhadovana doba behu " << pop_count << " generaci: ";
  vypisCas(cout, est_duration);

  if (est_duration > max_duration * 60) {
    cout << "Pocet generaci bude upraven, aby vypocet nepresahl " << max_duration << " minut." << endl;
  }

  off << "Vstupni matice C:        " << matrixC_name << endl;
  off << "Vstupni matice T:        " << matrixT_name << endl;
  off << "Nazev testu:             " << test_name << endl;
  off << "Pocet populaci:          " << max_generations << endl;  
  off << "Velikost populace:       " << pop_size << endl;
  off << "Parametr ukonceni:       " << pt << endl;  
  off << "Parametr selekcee:       " << ps << endl;
  off << "Thresholding:            " << use_thresholding << endl;
  off << "Metoda krizeni:          " << crossover_method << endl;
  off << "Parametr krizeni:        " << pc << endl;
  off << "Discarding:              " << use_discarding << endl;
  off << "Parametr mutace matches: " << pm << endl;
  off << "Parametr mutace rank1:   " << pr1 << endl;
  off << "Parametr mutace rank2:   " << pr2 << endl;

  matches_statistics.CreateMatrix(sirkaTP, sirkaC);
  matches_statistics.SetConstValue(0);

  matches_colTP_stat.CreateArray(sirkaTP);
  matches_colTP_stat.SetConstValue(0);

  rank_statistics.CreateMatrix(sirkaTP, sirkaTP);
  rank_statistics.SetConstValue(0);

//////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////

  Populace* act_population = NULL;
  Jedinec best;
  int pt_counter = 0; 
  double best_avg_fitness = 0;
  first_phase = true;

  start_time = time(NULL);

  act_population = new Populace(pop_size);
  act_population->Evaluate(use_discarding);
  act_population->GraphLog(off_graph);
  act_population->Vypis(off);
  cout << "------------------------ " << act_population->generation << " ------------------------" << endl;

  if (max_generations > 0)
  do {

//    cout << "ML0: " << endl;
    act_population->GenerateNext(ps, crossover_method, pc, pm, pr1, pr2, use_thresholding);
//    cout << "ML1: " << endl;
    act_population->Evaluate(use_discarding);

//    cout << "ML2: " << endl;
    act_population->Get(0).Check();
//    cout << "ML3: " << endl;
    act_population->GraphLog(off_graph);
    cout << "------------------------ " << act_population->generation << " ------------------------" << endl;

    if (best.GetQuality() < act_population->best_jedinec.GetQuality()) 
      best = act_population->best_jedinec;

    if (best_avg_fitness + 0.0001 > act_population->avg_fitness) pt_counter++;
    else {
      pt_counter = 0;
      best_avg_fitness = act_population->avg_fitness;
    }
    if (pt_counter >= pt)
      /*if (first_phase) {
        first_phase = false;
        pt_counter = 0;
      } else*/ break;
    if (act_population->generation >= max_generations) break;
//    if ((int) best.GetFitness() == sirkaT + 1) break;
    if (time(NULL) - start_time >= max_duration * 60) break;

    if (act_population->generation % 5 == 1) act_population->Vypis(off);

  } while (1 == 1);

  act_population->Vypis(off);

  end_time = time(NULL);
  cout << "Vysledny cas: ";
  vypisCas(cout, end_time - start_time);
  cout << endl;

  best.FinalOptimalization();
  best.Check();
  best.Vypis(cout);
//  cout << "ML5: " << endl;

  ////////////////////////////////////////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////////////////////////////////////////
  ////////////////////////////////////////////////////////////////////////////////////////////

  // zalogujeme statistiky do detailniho vystupu
  VypisOddelovac(off);
//  cout << "ML6: " << endl;
  VypisStatistiku(off);
//  cout << "ML7: " << endl;
  VypisOddelovac(off);
  off << "Vysledny cas: ";
  vypisCas(off, end_time - start_time);
  off << endl;
  VypisOddelovac(off);
  off << "Nejlepsi nalezeny jedinec: columns_matched = " << best.GetColumnsTMatched() << endl;
  best.Vypis(off);
  VypisOddelovac(off);
// zalogujeme vysledky do souhurneho vystupu
/*  off_all.open("test_output", ios::app);
  off_all << left << setw(25) << matrixC_name << setw(25) << matrixT_name;
  off_all << left << setw(25) << test_name;
  off_all << right << setw(6) << pop_size << setw(6) << act_population->generation;
  off_all << setw(5) << ps;
  off_all << setw(5) << use_thresholding;
  off_all << setw(5) << crossover_method;
  off_all << setw(5) << pc;
  off_all << setw(5) << use_discarding;
  off_all << setw(5) << pm;
  off_all << setw(5) << pr1;
  off_all << setw(5) << pr2;
  off_all << setw(8) << best.GetFitness();
  off_all << setw(5) << best.GetColumnsTMatched();
  off_all << setw(5) << best.GetDirectMatches();
  off_all << setw(5) << best.GetDirectNegMatches();
  off_all << setw(10) << end_time - start_time << "   " << test_name << endl;*/

  best.CreatePLAFile();
  best.CreateMatchesFile();

  return 0;

}
