#include <iostream>
#include <winbgim.h>
#include <cmath>
#define ARRAYSIZE 10000
using namespace std;

/*ALGORITMI ZA MANIPULACIJU SA STABLIMA*/
/*REALIZACIJA PREKO POLJA*/

struct tdata{
  char label[20];
  int firstChild;
  int nextSibling;
};

struct tree{
  tdata data[ARRAYSIZE];
  int first;
};

void createChild(int x, tree *t){
    cout << "Uneiste ime djeteta: ";
    cin >> t->data[x].label;
    t->data[x].firstChild = -1;
    t->data[x].nextSibling = -1;
}

int Root(tree *t){
  return t->first;
}

tree* Init(int x, tree *t){
  t = new tree;
  t->first = x;
  createChild(x,t);
  for(int i=0; i<ARRAYSIZE; i++){
  if(i==x) continue;
  strcpy(t->data[i].label,"");
  t->data[i].firstChild = -1;
  t->data[i].nextSibling = -1;       
  }
  return t;
}

char* Label(int n, tree *t){
  return t->data[n].label;
}

void ChangeLabel(char *x, int n, tree *t){
  strcpy(t->data[n].label,x);
}

void Create(int x, int n, tree *t){
  if(t->data[n].firstChild==-1){
    t->data[n].firstChild = x;
    createChild(x,t);
    cout << "Djete " << t->data[x].label << " je pridruzeno roditelju " << t->data[n].label << endl;
    return;
  }
  int brother = t->data[n].firstChild;
  while(true)
    if(t->data[brother].nextSibling==-1)
      break;
    else
      brother = t->data[brother].nextSibling;
  t->data[brother].nextSibling = x;
  createChild(x,t);
  cout << "Djete " << t->data[x].label << " je pridruzeno roditelju " << t->data[n].label << endl;
}

int Parent(int n, tree *t){
  if(t->first==n)
    return -1;
  else
    for(int i=0; i<ARRAYSIZE; i++)
      if(t->data[i].firstChild==n)
        return i;
      else if(t->data[i].nextSibling==n)
        return Parent(i,t);
  return -1;
}

int FirstChild(int n, tree *t){
  return t->data[n].firstChild;
}

int NextSibling(int n, tree *t){
  return t->data[n].nextSibling;
}

void Delete(int n, tree *t, bool prvi=true){
  if(t->data[n].firstChild != -1){
    Delete(t->data[n].firstChild,t, false);
    t->data[n].firstChild = -1;
    strcpy(t->data[n].label,"");
  }
  if(t->data[n].nextSibling != -1){
    if(prvi){ // ukoliko je prvi krug
      if(t->data[Parent(n,t)].firstChild==n){ //ukoliko sam ja prvo djete, onda je moj brat sljedece djete
        t->data[Parent(n,t)].firstChild=t->data[n].nextSibling;
        t->data[n].nextSibling = -1;
        strcpy(t->data[n].label,"");
      } else {//Inace pronađi ko ima pokazivač na mene
          int brother = t->data[Parent(n,t)].firstChild; //Ovo je prvo djete mojeg roditelja
          while(true)
            if(t->data[brother].nextSibling==n)
              break;
            else
              brother = t->data[brother].nextSibling;
          t->data[brother].nextSibling = t->data[n].nextSibling;
          t->data[n].nextSibling = -1;
          strcpy(t->data[n].label,"");                 
      }
    } else {
        Delete(t->data[n].nextSibling,t, false);
        t->data[n].nextSibling = -1;
        strcpy(t->data[n].label,"");
    }
  }
  if(t->data[n].firstChild==t->data[n].nextSibling)
    strcpy(t->data[n].label,"");
}

/*ALGORITMI OBILASKA STABLA*/

void Preorder(tree *t, int n){
   if(n==-1) return;
   cout << t->data[n].label << endl;
   Preorder(t, FirstChild(n, t));
   Preorder(t, NextSibling(n, t));     
}

void Inorder(tree *t, int n){
   if(n==-1)return;
   Inorder(t, FirstChild(n, t));
   cout << t->data[n].label << endl;
   Inorder(t, NextSibling(n, t));
}

void Postorder(tree *t, int n){
   if(n==-1)return;
   Preorder(t, FirstChild(n, t));
   Preorder(t, NextSibling(n, t));
   cout << t->data[n].label << endl;     
}

/*ALGORITAM ZA CRTANJE STABLA*/
/*Napomena:
   -algoritam za iscrtavanje koji je naveden u ovom primjeru je prvi algoritam kojega sam napisao za ovu svrhu, te kao takav je dosta ne strukturiran. Ukoliko želite bolje strukturirani kod, pogledajte kod za iscrtavanje binarnog stabla
*/

int indeks_prepisa, num;

void pomCrtaj(tree *t, int m[][5]){
/*Iscrtavanje sadržaja na ekran prema prosljeđenim parametrima*/
    int gdrive = 9;
    int gmode = 2;
    initgraph(&gdrive, &gmode, "");
    setbkcolor(WHITE);
    setcolor(BLACK);
    cleardevice();   
    for(int i=0; i<num; i++){
       circle(m[i][1], m[i][2], 10);
       if(m[i][4])line(m[i][1], m[i][2], m[i][3], m[i][4]);
       outtextxy(m[i][1]-5,m[i][2]-7,Label(m[i][0],t));       
    }
    getch();
    closegraph();   
}

void Prepisi(tree *t, int n, int p[]){
/*Prepis binarnog stabla u polje*/
   if(n==-1) return;
   Prepisi(t, FirstChild(n,t),p);
   if(strcmp(t->data[n].label,"")) p[indeks_prepisa++] = n;
   Prepisi(t, NextSibling(n,t),p);     
}

void Prebroji(tree *t, int n){
   if(n==-1) return;
   Prebroji(t, FirstChild(n,t));
   if(strcmp(t->data[n].label,"")) num++;
   Prebroji(t, NextSibling(n,t));     
}

void Poravnaj(int m[][5]){
/*Provjera koeficijenata smjera, ukoliko susjedi imaju isti koeficijent smjera
to znači da se nalaze na istom pravcu i to treba promjeniti*/
     for(int i=1; i<num-1; i++){
       float k1 = ((m[i][4]-m[i][2])*1.00)/(m[i][3]-m[i][1]);
       float k2 = ((m[i+1][4]-m[i+1][2])*1.00)/(m[i+1][3]-m[i+1][1]);
       //cout << endl << k1 << "\t" << k2 << endl << endl;
       if(k1==k2){
        int _x = m[i+1][1], _y = m[i+1][2];
        int n_x = _x+25, n_y = _y+25;
        m[i+1][1] = n_x;
        m[i+1][2] = n_y;
        for(int j=0; j<num; j++)
          if(m[j][3]==_x && m[j][4]==_y ){
            m[j][3]= n_x;
            m[j][4]= n_y;
          }
       }
}         
/*Provjeri udaljenost dali su preblizu, ako da udalji ih*/
    for(int i=1; i<num-1; i++){
       float udaljenost = sqrt((m[i][3]-m[i][1])*(m[i][3]-m[i][1])+(m[i][4]-m[i][2])*(m[i][4]-m[i][2]));
       if(udaljenost<60){
        int _x = m[i][1], _y = m[i][2];
        int n_x = _x+75, n_y = _y+75;
        m[i][1] = n_x;
        m[i][2] = n_y;
        for(int j=0; j<num; j++)
          if(m[j][3]==_x && m[j][4]==_y ){
            m[j][3]= n_x;
            m[j][4]= n_y;
          }
       }       
     }     
}

void Crtaj(tree *t){
    num = 0;
    Prebroji(t, Root(t));
    int p[num];
    int m[num][5];
    indeks_prepisa=0;
    Prepisi(t,Root(t),p); //prepisuje bin. stablo u polje
    /*Izračunaj x,y koordinate za krug i početak linije*/   
    for(int i=0; i<num; i++){
      m[i][0] = p[i];                //vrjednost
      m[i][1] = 50+20*m[i][0];       //x - krug i crta
      m[i][2] = num*50-i*50;             //y - krug i crta
    }
    /*Izračunaj x,y za kraj linije*/
    for(int i=0; i<num; i++){
      int j;
      int par = Parent(m[i][0],t);
      if (par==-1){//Ukoliko nema linije početak i kraj su isti
         m[i][3] = m[i][1];          //x - crta kraj
         m[i][4] = m[i][2];          //y - crta kraj
         continue;
      }
      for(j=0; j<num; j++)
         if(par==m[j][0])
            break;
      m[i][3] = m[j][1];
      m[i][4] = m[j][2];
    }
    Poravnaj(m); // presloži sadržaj
    /*Ispis tablice stanja*/
    cout << "L\tV\tX\tY\tX\tY\tK\tU\n";
    cout << endl;
        for(int i=0; i<num; i++){
        cout << Label(m[i][0],t) << "\t";
        cout << m[i][0] << "\t"
             << m[i][1] << "\t" << m[i][2] << "\t"
             << m[i][3] << "\t" << m[i][4] << "\t";
        if((m[i][3]-m[i][1])!=0){
          float rez = ((m[i][4]-m[i][2])*1.00)/(m[i][3]-m[i][1]);
          float rez2 = sqrt((m[i][3]-m[i][1])*(m[i][3]-m[i][1])+(m[i][4]-m[i][2])*(m[i][4]-m[i][2]));
          cout << rez << "\t" << rez2;
        }
        cout << endl;
    }
    pomCrtaj(t,m); //Poziv crtanja       
}