#include "tsp.h"

/////////////////////////////////////////////////////////////////////
// TSP

// vypocet dlzky kruznice reprezentovanej permutaciou
// pouzitim Hammingovej vzdialenosti (za velkost mriezky
// je povazovana odmocnina dlzky permutacie)
double TSP::hammingLen(const vectype &permut)
{
  int cnt = permut.size();
  int size = int(sqrt(cnt));
  int x0, y0,
      x1, y1, p1;
  double len = 0;

  x0 = permut[0] % size;
  y0 = permut[0] / size;
  
  for(int i = 1; i < cnt; i++)
  {
    p1 = permut[i];
    x1 = p1 % size;
    y1 = p1 / size;

    len += abs(x1 - x0) + abs(y1 - y0);

    x0 = x1; y0 = y1;
  }

  // kruznica - musime zaratat aj segment z koncoveho bodu
  // do zaciatocneho
  x1 = permut[0] % size;
  y1 = permut[0] / size;
  len += abs(x1 - x0) + abs(y1 - y0);

  return len;
}

void bulletLine(ostream &s, int x0, int y0, int x1, int y1)
{
    s << "\\put(" << x1 << "," << y1 <<"){\\circle{0.075}}";
    LaTeXLine(x0,y0,x1,y1,s);
    s << endl;
}
  
// vystup kruznice reprezentovanej permutaciou
// LaTeXovy obrazok
void TSP::printPermut(const vectype &permut, ostream &s)
{
  int cnt = permut.size();
  int size = int(sqrt(cnt));
  int x0, y0,
      x1, y1, p1;

  x0 = permut[0] % size;
  y0 = permut[0] / size;
  
  for(int i = 1; i < cnt; i++)
  {
    p1 = permut[i];
    x1 = p1 % size;
    y1 = p1 / size;

    bulletLine(s, x0, y0, x1, y1);
    
    x0 = x1; y0 = y1;
  }

  p1 = permut[0];
  x1 = p1 % size;
  y1 = p1 / size;

  bulletLine(s, x0, y0, x1, y1);
}

/////////////////////////////////////////////////////////////////////
// TSPperm

// nahodna inicializacia
void TSPperm::randomInit()
{
  int cnt = path->size();
  int i, swp, j;
    
  for(i = 0; i < cnt; i++)
    (*path)[i] = i;
  
  for(i = 0; i < (cnt-1); i++)
  {
    swp = (*path)[i];
    j = rnd(cnt - i - 1) + i + 1;
    (*path)[i] = (*path)[j];
    (*path)[j] = swp;
  }
}

// mutacia
void TSPperm::becomeMutationOf(const TSP &other)
{
  vectype *othp = (other.path);
  vectype *p = path;
  int cnt = othp->size();
  int i, j, swp;

  pMut = other.pMut;	// toto a sposob kopirovania su volene preto, ze *this
  			// moze byt vytvoreny bezparametrovym konstruktorom
  p->clear();
  for(i = 0; i < cnt; i++)
    p->push_back((*othp)[i]);

  for(i = 0; i < cnt; i++)
    if (rnd() < pMut)
    {
      j = rnd(cnt);
      swp = (*p)[i]; (*p)[i] = (*p)[j]; (*p)[j] = swp;
    }
}

// krizenie
void TSPperm::cross(const TSP &with, TSP &child1, TSP &child2)
{
  vectype *q = (with.path);
  vectype *p = path;
  vectype *pc = (child1.path);
  vectype *qc = (child2.path);
  int cnt = q->size();
  int i, a;
  vectype fpq(cnt,-1), fqp(cnt,-1);
#ifdef DEBUG
  cout<<"p:";
  for(i = 0; i < cnt; i++)
    cout<<(*p)[i]<<" ";
  cout <<endl <<"q:";
  for(i = 0; i < cnt; i++)
    cout<<(*q)[i]<<" ";
  cout<<endl;
#endif
  // jednoduche krizenie
  a = rnd(cnt);
#ifdef DEBUG
  cout <<a<<endl;
#endif
  pc->clear();
  qc->clear();
  for(i = 0; i < a; i++)
  {
#ifdef DEBUG
    cout<<(*p)[i]<<"-";
#endif
    pc->push_back((*p)[i]);
#ifdef DEBUG
    cout<<(*pc)[i]<<" "<<(*q)[i]<<"-";
#endif
    qc->push_back((*q)[i]);
#ifdef DEBUG
    cout<<(*qc)[i];
#endif
  }
  for(i = a; i < cnt; i++)
  {
#ifdef DEBUG
    cout<<(*q)[i]<<"-";
#endif
    pc->push_back((*q)[i]);
#ifdef DEBUG
    cout<<(*pc)[i]<<" "<<(*p)[i]<<"-";
#endif
    qc->push_back((*p)[i]);
#ifdef DEBUG
    cout<<(*qc)[i];
#endif
  }
#ifdef DEBUG
  cout<<endl<<"pc':";
  for(i = 0; i < cnt; i++)
    cout<<(*pc)[i]<<" ";
  cout <<endl <<"qc':";
  for(i = 0; i < cnt; i++)
    cout<<(*qc)[i]<<" ";
  cout<<endl;
#endif

  // funkcie f_{P->Q} a f_{Q->P}
  // ak su nedefinovana v i, f??[i] = -1
  for(i = a; i < cnt; i++)
  {
    fpq[(*p)[i]] = (*q)[i]; fqp[(*q)[i]] = (*p)[i];
  }
  // oprava
  for(i = 0; i < a; i++)
  {
    while(fqp[(*pc)[i]] != -1)
      (*pc)[i] = fqp[(*pc)[i]];
    while(fpq[(*qc)[i]] != -1)
      (*qc)[i] = fpq[(*qc)[i]];
  }
#ifdef DEBUG
  cout<<"pc:";
  for(i = 0; i < cnt; i++)
    cout<<(*pc)[i]<<" ";
  cout <<endl <<"qc:";
  for(i = 0; i < cnt; i++)
    cout<<(*qc)[i]<<" ";
  cout<<endl;
#endif
}

// ucelova funkcia
double TSPperm::purpFun()
{
  return hammingLen(*path);
}

void TSPperm::print(ostream &s)
{
  printPermut(*path, s);
}

/////////////////////////////////////////////////////////////////////
// TSPvect

// nahodna inicializacia
// aby sme dodrzali odporucany sposob, budeme inicializovat nahodnymi
// cislami <0,2^k) (velkost_mriezky^2) < 2^k
void TSPvect::randomInit()
{
  int pow2k = 1; // 2^k
  vectype &p = (*path);
  int cnt = p.size();
  int i;
  
  while(cnt > pow2k)
    pow2k <<= 1;	// shift vlavo = nasobenie 2
  
  for(i = 0; i < cnt; i++)
    p[i] = rnd(pow2k);
}

// mutacia
void TSPvect::becomeMutationOf(const TSP &other)
{
  vectype &p = (*path);
  vectype &othp = *(other.path);
  int cnt = othp.size();
  int i, j;

  pMut = other.pMut;
  
  p.clear();
  for(i = 0; i < cnt; i++)
  {
    p.push_back(othp[i]);
    j = 1;		// 2^(cislo mutovaneho bitu)
    while(j < cnt)
    {
      if (rnd() < pMut)
      	p[i] ^= j;	// exkluzivne alebo
      j <<= 1;		// j = 2*j
    }
  }
}
  
// krizenie
// na rozdiel od mutacie nebudeme taki precizni a nespravime
// krizenie bitovych vektorov
void TSPvect::cross(const TSP &with, TSP &child1, TSP &child2)
{
  vectype &othp = *(with.path);
  vectype &myp = *path;
  vectype &p = *(child1.path);
  vectype &q = *(child2.path);
  int cnt = othp.size();
  int i, a;

  a = rnd(cnt);
  p.clear();
  q.clear();
  for(i = 0; i < a; i++)
  {
    p.push_back(myp[i]);
    q.push_back(othp[i]);
  }
  for(i = a; i < cnt; i++)
  {
    p.push_back(othp[i]);
    q.push_back(myp[i]);
  }
}

// ucelova funkcia
// aby sme vedeli urcit hammingovu dlzku hamiltonovskej kruznice
// reprezentovanej vektorom, musime najst najprv medzikrok -- permutaciu
// urcenu vektorom a urcujucu kruznicu
double TSPvect::purpFun()
{
  return hammingLen(vect2perm(*path));
}

// podobne ako pri urcovani ucelovej funkcie
void TSPvect::print(ostream &s)
{
  printPermut(vect2perm(*path), s);
}

// hladame permutaciu, ktora usporiada vektor vzostupne
// pouzijeme linearny algoritmus -- counting sort
TSP::vectype TSPvect::vect2perm(const TSP::vectype &v)
{
  int cnt = v.size();
  vectype permut(cnt);	// permutacia ma rovnaku dlzku ako vektor
  int pow2k = 1;
  int i;

  while(cnt > pow2k)
    pow2k <<= 1;	// ostre horne ohranicenie cisel vo vektore

  TSP::vectype counts(pow2k,0);	// pocty jednotlivych prvkov
  /* vectype out(cnt);		// pomocne pole, keby sme naozaj triedili */
  for(i = 0; i < cnt; i++)
    counts[v[i]]++;		// counts[i] = pocet prvkov == i
  for(i = 1; i < pow2k; i++)
    counts[i] += counts[i-1];	// counts[i] = pocet prvkov <= i
  for(i = cnt - 1; i >= 0; i--)
  {
    /*out[counts[v[i]]-1] = v[i];	// keby sme naozaj triedili, polozime prvok
     					// z i-tej pozicie na counts[v[i]]-tu */
    permut[i] = counts[v[i]] - 1;	// my len zaznamename tuto vymenu do permutacie
    counts[v[i]]--;			// - 1 kvoli cislovaniu poli od 0
  }
#ifdef DEBUG6
  for(i=0; i<cnt; i++) cout<<v[i]<<" "; cout<<endl;
  for(i=0; i<cnt; i++) cout<<permut[i]<<" ";cout<<endl;
#endif
  return permut;
}