/******************************************/
/* KYBLE V1.0       PAA  1999     kyble.c */
/* Reseni zobecneneho problemu dvou kyblu */
/* Copyright (c) 1999 by KP CVUT-FEL      */
/* Decentne upraveno k uziti heuristiky   */
/* Tomas Kubes 2005                       */
/******************************************/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "kyble.h"

/*#define DBG_CONTROL            /* Control prints */
/*#define DBG_CONTROLO           /* Control prints - operations */
/*#define DBG_CONTROLQ           /* Control prints - queue */
#define HARDERR          /* Pri preteceni fronty program skonci */

#define MAXVERTEX 100000  /* max. pocet uzlu grafu stav. prostoru */
#define MAXQUEUE  30000   /* max. pocet rozpracovanych uzlu */
#define MAXBUCKET 5       /* run-time max. pocet kyblu */


unsigned full_buckets[MAXBCKTS];  /* objem jednotl. kyblu */
unsigned final_buckets[MAXBCKTS]; /* koncovy stav */

vertex vertices[MAXVERTEX];        /* souvisly seznam uzlu */
unsigned ffree=1;                  /* ukazatel na prvni volne misto v poli uzlu */

unsigned qcnt=0;                   /* pocet prvku ve fronte */
unsigned first=0,last=0;           /* prvni, posledni prvek fronty */
FILE* trace;                       /* ulozeni prubehu vypoctu */
FILE* fv;                          /* ulozeni reseni */


////////////////////////////////////////////////////////////////////
//pridane datove struktury

/*n rozmeru, kazdy tak velky, aby se do ni vesel i nejvetsi kybl*/
#define BITMAPSIZE 16*16*16*16*16

/*bitova mapa pro zjistovani navstivenosti stavu */
bool bitmap [BITMAPSIZE];

bst_prority_gueue *root;


///////////////////////////////////////////////////////////////////
//puvodni funkce kyble.c

/* Konvence: prvni prvek v poli vertices (tj. 0) musi zustat prazdny */
void set_final_buckets(void) {
final_buckets[0]=7;
final_buckets[1]=0;
final_buckets[2]=7;
final_buckets[3]=0;
final_buckets[4]=7;
final_buckets[5]=3;
final_buckets[6]=3;
final_buckets[7]=3;
final_buckets[8]=3;
final_buckets[9]=3; /* */
}
void set_full_buckets(void) {
full_buckets[0]=14;
full_buckets[1]=10;
full_buckets[2]=12;
full_buckets[3]=3;
full_buckets[4]=8;
full_buckets[5]=3;
full_buckets[6]=3;
full_buckets[7]=3;
full_buckets[8]=3;
full_buckets[9]=3; /* */
}
void putvertex(unsigned b, unsigned tento)
{
  /* ulozi novy stav do grafu */
  unsigned x=0, i;
  (vertices+ffree)->backptr=b;
  if (b) (vertices+ffree)->count=(vertices+b)->count+1;
  else (vertices+ffree)->count=0;
  (vertices+ffree)->hits=1;
  if ((ffree++)>MAXVERTEX)
  {
    printf("PUTVERTEX: MAXIMUM NUMBER OF VERTICES EXCEEDED \n");
    fprintf(trace,"PUTVERTEX: MAXIMUM NUMBER OF VERTICES EXCEEDED \n");
    exit(1);
  }
  for(i=0;i<MAXBUCKET;i++)
    x=16*x+(vertices+tento)->bucket[i];
  bitmap[x]=1;
}
unsigned set_initial_buckets(void) {
unsigned b=1;
ffree=1; /* pro jistotu */
(vertices+b)->backptr=0;      /* pocatecni stav nema predchudce */
(vertices+b)->bucket[0]=0;
(vertices+b)->bucket[1]=0;
(vertices+b)->bucket[2]=0;
(vertices+b)->bucket[3]=0;
(vertices+b)->bucket[4]=0;
(vertices+b)->bucket[5]=0;
(vertices+b)->bucket[6]=0;
(vertices+b)->bucket[7]=0;
(vertices+b)->bucket[8]=0;
(vertices+b)->bucket[9]=0; /* */
putvertex(0, 0);
return b;
}
unsigned isempty(unsigned b, unsigned which) {
/* zjisti, jestli dany kybl je prazdny */
return(!((vertices+b)->bucket[which]));
}
unsigned isfull(unsigned b, unsigned which) {
/* zjisti, jestli dany kybl je plny */
return(((vertices+b)->bucket[which])==full_buckets[which]);
}
unsigned empty(unsigned bk, unsigned which) {
/* Vyleje kybl, jehoz poradi je urceno cislem which */
unsigned a=0;
vertex *vert, *buckets;
if (which > MAXBUCKET) {
   printf("EMPTY: INVALID BUCKET NUMBER\n");
   fprintf(trace,"EMPTY: INVALID BUCKET NUMBER\n");
   exit(1);
   }
if (bk > MAXVERTEX) {
   printf("EMPTY: MAXIMUM NUMBER OF VERTICES EXCEEDED\n");
   fprintf(trace,"EMPTY: MAXIMUM NUMBER OF VERTICES EXCEEDED\n");
   exit(1);
   }
buckets=(vertices+bk);
vert=(vertices+ffree);
vert->backptr=bk;
vert->oper=0;
vert->count=0;
vert->which1=which;
vert->which2=0;
for(a=0;a<MAXBUCKET;a++) vert->bucket[a]=buckets->bucket[a];
vert->bucket[which]=0;
#ifdef DBG_CONTROLO
buckets=(vertices+ffree);
printf("EMPTY: EXIT  B %2i V %2i \n",which,buckets->bucket[which]);
fprintf(trace,"EMPTY: EXIT  B %2i V %2i \n",which,buckets->bucket[which]);
#endif
return ffree;
}

unsigned fill(unsigned bk, unsigned which) {
/* Naplni kybl, jehoz poradi je urceno cislem which */
unsigned a=0;
vertex *vert, *buckets;
if (which > MAXBUCKET) {
   printf("FILL: INVALID BUCKET NUMBER\n");
   fprintf(trace,"FILL: INVALID BUCKET NUMBER\n");
   exit(1);
   }
if (bk > MAXVERTEX) {
   printf("FILL: MAXIMUM NUMBER OF VERTICES EXCEEDED\n");
   fprintf(trace,"FILL: MAXIMUM NUMBER OF VERTICES EXCEEDED\n");
   exit(1);
   }
buckets=(vertices+bk);
vert=(vertices+ffree);
vert->backptr=bk;
vert->oper=1;
vert->count=0;
vert->which1=which;
vert->which2=0;
for(a=0;a<MAXBUCKET;a++) vert->bucket[a]=buckets->bucket[a];
vert->bucket[which]=full_buckets[which];
#ifdef DBG_CONTROLO
buckets=(vertices+ffree);
printf("FILL:  EXIT  B %2i V %2i \n",which,buckets->bucket[which]);
fprintf(trace,"FILL:  EXIT  B %2i V %2i \n",which,buckets->bucket[which]);
#endif
return ffree;
}

unsigned pour(unsigned bk, unsigned which1, unsigned which2) {
/* Preleje obsah kyblu do druheho */
/* which2=which1; which1=0;*/
unsigned a=0,pom1=0,pom2=0;
vertex *vert, *buckets;
if (which1 > MAXBUCKET) {
   printf("POUR: INVALID BUCKET NUMBER\n");
   fprintf(trace,"POUR: INVALID BUCKET NUMBER\n");
   exit(1);
   }
if (bk > MAXVERTEX) {
   printf("POUR: MAXIMUM NUMBER OF VERTICES EXCEEDED\n");
   fprintf(trace,"POUR: MAXIMUM NUMBER OF VERTICES EXCEEDED\n");
   exit(1);
   }

buckets=(vertices+bk);
vert=(vertices+ffree);
vert->backptr=bk;
vert->oper=2;
vert->count=0;
vert->which1=which1;
vert->which2=which2;
for(a=0;a<MAXBUCKET;a++) vert->bucket[a]=buckets->bucket[a];
/* vert->bucket[which2]=(vert->bucket[which1]>vert->bucket[which2])?full_buckets[which2]:vert->bucket[which1]; /* Old version */
pom1=full_buckets[which2]-vert->bucket[which2]; /* volne misto v druhem kyblu */
pom2=min(vert->bucket[which1],pom1);            /* bud se omezuje volnym mistem v druhem kyblu, nebo mnozstvim vody v prvnim kyblu */
vert->bucket[which1]=vert->bucket[which1]-pom2; /* odlit */
vert->bucket[which2]=vert->bucket[which2]+pom2; /* nalit */
#ifdef DBG_CONTROLO
buckets=(vertices+ffree);
printf("POUR:  EXIT  B %2i V %2i B %2i V %2i \n",which1,buckets->bucket[which1],which2,buckets->bucket[which2]);
fprintf(trace,"POUR:  EXIT  B %2i V %2i B %2i V %2i \n",which1,buckets->bucket[which1],which2,buckets->bucket[which2]);
#endif
return ffree;
}

unsigned check(unsigned b) {
/* Zkontroluje, jestli dany stav je pozadovane reseni */
unsigned a=0, flag=1;
vertex *buckets;
buckets=(vertices+b);
for(a=0;a<MAXBUCKET;a++) if (buckets->bucket[a]!=final_buckets[a]) flag=0;
return flag;
}

unsigned initcheck(unsigned b) {
/* Zkontroluje, jestli dany stav je pripustny stav stavoveho prostoru */
unsigned a=0, flag=1;
vertex *buckets;
buckets=(vertices+b);
for(a=0;a<MAXBUCKET;a++) if (buckets->bucket[a]>full_buckets[a]) flag=0;
return flag; /* 1..OK, 0..FAIL */
}

unsigned compare(unsigned b, unsigned bk) {
/* Zkontroluje, jestli jsou uzly shodne */
unsigned a=0, flag=1;
vertex *buckets1, *buckets2;
buckets1=(vertices+b);
buckets2=(vertices+bk);
if (b==bk) return 1; /* New version */
for(a=0;a<MAXBUCKET;a++) if (buckets1->bucket[a]!=buckets2->bucket[a]) flag=0;
return flag;
}

void assign_rewrite(FILE **F, const char *Name) {
/* otevre soubor na vystup */
if ((*F = fopen(Name,"wt")) == NULL) {
   printf("ASSIGN_REWRITE: UNABLE TO OPEN FILE %s\n", Name);
   exit(1);
   }
}



///////////////////////////////////////////////////////////////////
//nove a upravene funkce 


void ResetBitmap(void)
{
	for(unsigned int i=0;i<BITMAPSIZE;i++) bitmap[i]=0;
}

void BstInsert(bst_prority_gueue *node, double fce, unsigned b)
{
  bst_prority_gueue *tmp_node;
  if(fce<=(node->heurfce))
  {
    if(node->right!=NULL)
      BstInsert(node->right, fce, b);
    else
    {
      tmp_node=new(bst_prority_gueue);
      node->right=tmp_node;
      tmp_node->vertx=b;
      tmp_node->heurfce=fce;
      tmp_node->left=NULL;
      tmp_node->right=NULL;
    }
  }
  else
  {
    if(node->left!=NULL)
      BstInsert(node->left, fce, b);
    else
    {
      tmp_node=new(bst_prority_gueue);
      node->left=tmp_node;
      tmp_node->vertx=b;
      tmp_node->heurfce=fce;
      tmp_node->left=NULL;
      tmp_node->right=NULL;
    }
  }
}


void enqueue(unsigned b)
{
  bst_prority_gueue *node;
  int buc;
  unsigned a;
  double fce=0;

/* Heuristicka funkce */
  for(a=0;a<MAXBUCKET;a++)
  {
    buc=(vertices+b)->bucket[a]-final_buckets[a];
    buc*=buc;
    fce+=buc;
  }
  fce=sqrt(fce);
  if(root==NULL)
  {
    root=new(bst_prority_gueue);
    root->vertx=b;
    root->left=NULL;
    root->right=NULL;
    root->heurfce=fce;
  }
  else
  {
    node=root;
    BstInsert(node, fce, b);
  }
}

unsigned dequeue(void)
{
  unsigned nejlepsi;
  bst_prority_gueue *tmp_node, *node;
  if(root==NULL)
    return 0;
  if((root->left==NULL)&&(root->right==NULL))
  {
    nejlepsi=root->vertx;
    delete root;
    root=NULL;
    return nejlepsi;
  }
  if(root->right==NULL)
  {
    nejlepsi=root->vertx;
    tmp_node=root;
    delete root;
    root=tmp_node->left;
    return nejlepsi;
  }
  node=root;
  while(node->right!=NULL)
  {
    tmp_node=node;
    node=node->right;
  }
  nejlepsi=node->vertx;
  if(node->left!=NULL)
    tmp_node->right=node->left;
  else
    tmp_node->right=NULL;
  delete(node);
  return nejlepsi;
}

void save(unsigned temp, unsigned prev) {
/* zapise postup operaci pro nalezeni reseni do souboru */
/* prev je primy predchudce uzlu temp pro prave provadenou operaci */
/* je to kvuli osetreni vice zpusobu dosazeni reseni */
unsigned b=temp,c=0;
unsigned bb=0;
static unsigned cnt=0;
cnt++;
if ((temp!=prev)&&(prev!=(vertices+temp)->backptr)) {
   printf("SAVE: DUPLICATE SOLUTION   #%i\n",cnt);
   fprintf(fv,"SAVE: DUPLICATE SOLUTION   #%i\n",cnt);
   }

for(bb=0;bb<MAXBUCKET;bb++) {
   printf("%2i ",(vertices+temp)->bucket[bb]);
   fprintf(fv,"%2i ",(vertices+temp)->bucket[bb]);
   }
printf("\n");
fprintf(fv,"\n");

while (b!=0) {
   c++;
   if ((vertices+b)->backptr!=0) { /* prvni node je pocatecni stav a neni pro nej definovana operace */
      printf("#%2i %2i OPER %i  WHICH1 %i  ",cnt,c,(vertices+b)->oper,(vertices+b)->which1);
      if ((vertices+b)->oper==2) printf("WHICH2 %i   #%i ",(vertices+b)->which2,cnt);
      else printf("           #%i ",cnt);
      fprintf(fv,"#%2i %2i OPER %i  WHICH1 %i  ",cnt,c,(vertices+b)->oper,(vertices+b)->which1);
      if ((vertices+b)->oper==2) fprintf(fv,"WHICH2 %i   #%i ",(vertices+b)->which2,cnt);
      else fprintf(fv,"           #%i ",cnt);
      for(bb=0;bb<MAXBUCKET;bb++) {
         printf("%2i ",(vertices+b)->bucket[bb]);
         fprintf(fv,"%2i ",(vertices+b)->bucket[bb]);
         }
      printf("\n");
      fprintf(fv,"\n");
      }
   b=(vertices+b)->backptr;
   }
}


//zjisti, zda jsme jiz stav navstivili
//pokud ne, tak jej prida do fronty 
bool dupltest(unsigned tmp_node, unsigned node)
{
  //podle bitove mapy zjistit, jestli je jiz stav se stejnou plnosti vsech kyblu
  //spocte adresu staavu v mape

  unsigned int x=0;
  for(unsigned int i=0;i<MAXBUCKET;i++)
    x=16*x+(vertices+tmp_node)->bucket[i];

  //pokud stav nebyl navsdtiven zarad jej do fronty
  if(!bitmap[x])
  {
    putvertex(node, tmp_node);
    enqueue(tmp_node);
  }
  if(check(tmp_node))
  {
    save(tmp_node, node);
    return true;
  }
  else return false;
}


//smaze vyhledavaci strom
void DeleteTree(bst_prority_gueue *node)
{
	//nic k delani
	if(node==NULL)
	{
		return;
	}

	//osetrit smazani potomku
	if(node->left!=NULL)
	{
		DeleteTree(node->left);
	}

	if(node->right!=NULL)
	{
		DeleteTree(node->right);
	}

	//nakonec vyprazdnit i sebe sama
	delete(node);
}

void search(void)
{
/* Reseni problemu kyblu Vasi heuristikou */
unsigned node, x, y, tmp_node;
bool konec=false;

//zaradi prvni uzel
enqueue(1);

while((!konec)&&(node=dequeue()))
  for(x=0;x<MAXBUCKET;x++)
  {
    if(!isempty(node, x))
    {
      tmp_node=empty(node, x);
      if(dupltest(tmp_node, node))
        konec=true;
    }

    if(!isfull(node, x))
    {
      tmp_node=fill(node, x);
      if(dupltest(tmp_node, node))
        konec=true;
    }
    for(y=0;y<MAXBUCKET;y++)
      if((!isempty(node, x))&&(!isfull(node, y)))
        if(x!=y)
        {
          tmp_node=pour(node, x, y);
          if(dupltest(tmp_node, node))
           konec=true;
        }
/*  if(konec) break;*/
  }
  DeleteTree(root);
  if(konec)
  {
    printf("SEARCH: DONE\n");
    fprintf(trace,"SEARCH: DONE\n");
    return;
  }

  printf("SEARCH: HAVEN'T FOUND END STATE\n");
  fprintf(trace,"HAVEN'T FOUND END STATE\n");
  return;
}


void dump_vertices(void) {
unsigned a=0,b=0;
for (a=1;a<ffree;a++) {
   printf("#%2i BUCKETS: ",a);
   fprintf(trace,"#%2i BUCKETS: ",a);
   for(b=0;b<MAXBUCKET;b++) {
      printf("%2i ",(vertices+a)->bucket[b]);
      fprintf(trace,"%2i ",(vertices+a)->bucket[b]);
      }
   printf(" DIST: %2i  HITS: %2i\n",(vertices+a)->count,(vertices+a)->hits);
   fprintf(trace," DIST: %2i  HITS: %2i\n",(vertices+a)->count,(vertices+a)->hits);
   }
}

void save_vertices(void) {
FILE *mdl;
unsigned b=0;

if ((mdl = fopen("source.bin","wb")) == NULL) {
   printf("SAVE_VERTICES: ERROR OPENING FILE");
   exit(1);
   }
printf("Writing space \n");
fprintf(trace,"Writing space \n");

if (fwrite(&ffree,sizeof(int),1,mdl)==-1) {
   printf("SAVE_VERTICES: ERROR WRITING VERTEX COUNT");
   exit(1);
   }

for(b=0;b<ffree;b++) {
    if (fwrite((vertices+b),sizeof(vertex),1,mdl)==-1) {
       printf("SAVE_VERTICES: ERROR WRITING VERTEX");
       exit(1);
       }
    }


fclose(mdl);
}


int main(int argc, char* argv[])
{
  unsigned a, b, c;
  a=b=c=0;

  assign_rewrite(&trace,"trace.txt");
  assign_rewrite(&fv,"solution.txt");

  ResetBitmap();

  set_full_buckets();

  b=set_initial_buckets();

  set_final_buckets();

  if (!initcheck(b))
  {
    printf("MAIN: INITIAL STATE IS INVALID \n");
    fprintf(trace,"MAIN: INITIAL STATE IS INVALID \n");
    exit(1);
  }

  printf("MAIN: Starting search...\n");
  fprintf(trace,"MAIN: Starting search...\n");


  search();

  printf("MAIN: DONE AFTER EXPLORING %i VERTICES \n\n",ffree-1);
  fprintf(trace,"MAIN: DONE AFTER EXPLORING %i VERTICES \n",ffree-1);
  printf("\n\n\n\n");
  dump_vertices();
  save_vertices(); /* ulozeni stav. prostoru */

  fclose(trace);
  fclose(fv);
  return 0;
}