/******************************************/
/* KYBLE V1.0       PAA  1999     kyble.c */
/* Reseni zobecneneho problemu dvou kyblu */
/* Copyright (c) 1999 by KP CVUT-FEL      */
/******************************************/

#include "kyble.h"

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <dos.h>
#include <time.h>
#include <direct.h>

/* #define DEBUG            /* Control prints */
/* #define DEBUGO           /* Control prints - operations */
/* #define DEBUGQ           /* 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 queue[1/*MAXQUEUE*/];          /* fronta rozpracovanych 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 */
//struct time t;                     /* cas vypoctu */


/* Konvence: prvni prvek v poli vertices (tj. 0) musi zustat prazdny */

/* nastaveni koncovych stavu */
void set_final_buckets(unsigned *data, unsigned count)
{
	for(unsigned i = 0; i < MAXBCKTS; i++)
	{
		if (i < count)
			final_buckets[i] = data[i];
		else
			final_buckets[i] = 3;
	}
/*
final_buckets[0]=12;
final_buckets[1]=6;
final_buckets[2]=4;
final_buckets[3]=1;
final_buckets[4]=8;
final_buckets[5]=3;
final_buckets[6]=3;
final_buckets[7]=3;
final_buckets[8]=3;
final_buckets[9]=3; /* */
}

void set_full_buckets(unsigned *data, unsigned count) 
{
	for(unsigned i = 0; i < MAXBCKTS; i++)
	{
		if (i < count)
			full_buckets[i] = data[i];
		else
			full_buckets[i] = 3;
	}
/*
full_buckets[0]=14;
full_buckets[1]=10;
full_buckets[2]=6;
full_buckets[3]=2;
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) {
/* ulozi novy stav do grafu */
(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);
   }
}

unsigned set_initial_buckets(unsigned *data, unsigned count) 
{
unsigned b=1;
ffree=1; /* pro jistotu */
vertex *vert = vertices + b;
vert->backptr=0;      /* pocatecni stav nema predchudce */
	for(unsigned i = 0; i < MAXBCKTS; i++)
	{
		if (i < count)
			vert->bucket[i] = data[i];
		else
			full_buckets[i] = 0;
	}
/*
(vertices+b)->bucket[0]=0;
(vertices+b)->bucket[1]=0;
(vertices+b)->bucket[2]=1;
(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);
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);
#ifdef DEBUGO
printf("EMPTY: ENTRY B %2i V %2i \n",which,buckets->bucket[which]);
fprintf(trace,"EMPTY: ENTRY B %2i V %2i \n",which,buckets->bucket[which]);
#endif
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 DEBUGO
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);
#ifdef DEBUGO
printf("FILL:  ENTRY B %2i V %2i \n",which,buckets->bucket[which]);
fprintf(trace,"FILL:  ENTRY B %2i V %2i \n",which,buckets->bucket[which]);
#endif
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 DEBUGO
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);
#ifdef DEBUGO
printf("POUR:  ENTRY B %2i V %2i B %2i V %2i \n",which1,buckets->bucket[which1],which2,buckets->bucket[which2]);
fprintf(trace,"POUR:  ENTRY B %2i V %2i B %2i V %2i \n",which1,buckets->bucket[which1],which2,buckets->bucket[which2]);
#endif
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 DEBUGO
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);
   }
}

void enqueue(unsigned b) {
/* vlozi dany uzel do fronty k dalsimu zpracovani */
static unsigned cnt=0;
#ifdef DEBUGB
unsigned a=0;
#endif
cnt++;
#ifdef DEBUGQ
printf("ENQUEUE: PASS %i MEMBERS %i\n",cnt,qcnt);
fprintf(trace,"ENQUEUE: PASS %i MEMBERS %i\n",cnt,qcnt);
#endif
#ifdef DEBUGB
printf("ENQUEUE: BUCKETS  ");
fprintf(trace,"ENQUEUE: BUCKETS  ");
for(a=0;a<MAXBUCKET;a++) {
   printf("%i ",(vertices+b)->bucket[a]);
   fprintf(trace,"%i ",(vertices+b)->bucket[a]);
   }
printf("\n");
fprintf(trace,"\n");
#endif
if (((last+1)%MAXQUEUE)==first) {
   printf("ENQUEUE: QUEUE IS FULL   PASS %i\n",cnt);
   fprintf(trace,"ENQUEUE: QUEUE IS FULL    PASS %i\n",cnt);
#ifdef HARDERR
   exit(1);
#else
   return;
#endif
   }
else qcnt++;
queue[last]=b;
last=(last+1)%MAXQUEUE;
}

unsigned dequeue(void) {
/* vybere uzel z fronty k dalsimu zpracovani */
static unsigned cnt=0;
unsigned b=0;
cnt++;
if (qcnt) qcnt--;       /* osetreni podteceni */
#ifdef DEBUGQ
printf("DEQUEUE: PASS %i MEMBERS %i\n",cnt,qcnt);
fprintf(trace,"DEQUEUE: PASS %i MEMBERS %i\n",cnt,qcnt);
#endif
if (first==last) {
   printf("DEQUEUE: QUEUE IS EMPTY    PASS %i\n",cnt);
   fprintf(trace,"DEQUEUE: QUEUE IS EMPTY    PASS %i\n",cnt);
   return(0);
   }
b=queue[first];
first=(first+1)%MAXQUEUE;
if (b==0) {
   printf("DEQUEUE: FATAL ERROR    PASS %i\n",cnt);
   fprintf(trace,"DEQUEUE: FATAL ERROR    PASS %i\n",cnt);
   exit(1);
   }
return(b);
}

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("  (%u steps)",vertices[temp].count);
fprintf(fv,"  (%u steps)",vertices[temp].count);

printf("\n");
fprintf(fv,"\n");

/* b=(vertices+b)->backptr; /* Old version */
/* if (!(b=(vertices+b)->backptr)) b=prev; /* asi to neni ono */

while (b!=0) {
   c++;
   if (true){//(vertices+b)->backptr!=0) { /* prvni uzel 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;
   }
}


/////////////////////////////////////////////////////////////////////////////
// Moje reseni --------------------------------------------------------------
// Konstanty ----------------------------------
/* Moznosti objemu - tridy */
enum EContents
{
	cEMPTY = 0,				/* prazdny - nula */
	cEMPTY_NEEDED,		/* prazdny a koncovy stav nejakeho je 0 */
	cFULL,						/* objem nejakeho kyble */
	cFULL_NEEDED,			/* objem nejakeho kyble a zaroven konec nejakeho */
	cTWO_MIX,					/* rozdil objemu dvou kbeliku */
	cTWO_MIX_NEEDED,	/*  -||- a konec nejakeho */
	cUNKNOWN,					/* neznamy objem - jiny nez ^ */
	cUNKNOWN_NEEDED		/*  -||- a konec nejakeho */
};

/* Ceny objemu - mozno stejne ceny pro ruzne tridy */
enum EContentPrices
{
	cpEMPTY_NEEDED			= 0,
	cpEMPTY_PLACED			= 2,
	cpFULL_NEEDED				= 1,
	cpFULL_PLACED				= 2,
	cpTWO_MIX_NEEDED		= 4,
	cpTWO_MIX_PLACED		= 5,
	cpUNKNOWN_NEEDED		= 9,
	cpUNKNOWN_PLACED		= 10
};

/* Vysledky kontroly noveho uzlu */
enum EPutResult
{
	FOUND,			//je resenim
	FINISH,			//vsechny tezke nalezeny - jen dokonceni
	CONTINUE		//pokracovat prelivani
};

// Datove struktury ----------------
/* Prvek v prioritni fronte */
struct SQueueItem
{
	unsigned		vertex;
	unsigned		price;
	SQueueItem	*prev;
	SQueueItem	*next;
};

// Data ----------------------------
/* fronta */
SQueueItem *head;
unsigned	qCount = 0;

/* objem max. kbeliku - velikost poli */
unsigned MAX_CONTENT;

/* pole vlastnosti objemu */
short 
	*needed,		/* kolikrat je objem potrebovan */
	*actual,		/* aktualni pocet kbeliku s danym objemem */
	*placed,		/* pocet aktualnich spravnych umisteni jednotlivych objemu */
	*types;			/* typy jednotlivych objemu */

// pomocne funkce -------------------------------------------
/* nastaveni obsahu daneho short pole na 0 */
void ZeroArray(short * array)
{
	for(unsigned i = 0; i <= MAX_CONTENT; i++)
		array[i] = 0;
}

// prace s frontou -----------------------------------------
/* vypocet ceny pro dany objem */
unsigned ContentPrice(short type, short count, short placed)
{
	short normal = count - placed;	//pocet neumistenych
	//mohou byt jen needed typy
	switch (type)
	{
		case cEMPTY_NEEDED:
			return (normal*cpEMPTY_NEEDED + placed*cpEMPTY_PLACED);
		case cFULL_NEEDED:
			return (normal*cpFULL_NEEDED + placed*cpFULL_PLACED);
		case cTWO_MIX_NEEDED:
			return (normal*cpTWO_MIX_NEEDED + placed*cpTWO_MIX_PLACED);
		case cUNKNOWN_NEEDED:
			return (normal*cpUNKNOWN_NEEDED + placed*cpUNKNOWN_PLACED);
		default:
			return 0;
	}
}

/* vypocet ceny stavu */
unsigned GetPrice(const vertex& stav)
{
	unsigned i;
	//nastaveni actual podle stavu
	ZeroArray(actual);
	ZeroArray(placed);
	for(i = 0; i < MAXBUCKET; i++)
	{
		//pripocteni stavu v kyblu
		unsigned cont = stav.bucket[i];
		actual[cont]++;
		//? je placed
		if (cont == final_buckets[i])
			placed[cont]++;
	}
	//vypocet ceny pres jednotlive objemy
	unsigned price = 0;
	for(i = 0; i <= MAX_CONTENT; i++)
	{
		short count = min(needed[i], actual[i]);
		if (count > 0)
			price += ContentPrice(types[i], count, placed[i]);
	}
	return price;
}

/* vytvoreni prvku fronty */
SQueueItem* CreateItem(unsigned vertex, unsigned price)
{
	qCount++;
	//nastaveni noveho
	SQueueItem *res = new SQueueItem();
	res->price = price;
	res->vertex = vertex;
	return res;
}

/* vlozeni noveho prvku do fronty pred cur */
void AddItem(SQueueItem *cur, unsigned vertex, unsigned price)
{
	//nastaveni noveho
	SQueueItem *newI = CreateItem(vertex, price);
//	printf("Enqued %6u: count = %6u, price = %6u\n", vertex, qCount, price);
	//zacleneni do fronty
	newI->prev = cur->prev;
	newI->next = cur;
	cur->prev = newI;
	//? vkladano pred head
	if (cur == head)
		head = newI;
	else
		newI->prev->next = newI;
}

/* vlozeni stavu s danym indexem do fronty, false pokud jiz existuje */
bool Enque(unsigned index)
{
	unsigned price = GetPrice(vertices[index]);
	SQueueItem *pom, *pom2 = NULL;
	for(pom = head; pom != NULL; pom = pom->next)
	{
		//shodnost cen - test neopakovani
//		if(pom->price == price)
//		{
			/*
			//test pritomnosti
			unsigned found = compare(index, pom->vertex);
			for(pom2 = pom->next; (pom2 != NULL) &&(!found) && (pom2->price == price); pom2 = pom2->next)
				found = compare(index, pom2->vertex);
			if(found)
				return false;
			*/
			//neni ve fronte - vlozeni pred pom
//			AddItem(pom, index, price);
//			return true;
//		}
		//jiznizsi cena -  vlozit pred
		/*else*/ if(pom->price < price)
		{
			AddItem(pom, index, price);		//vlozeni pred
			return true;
		}
		//hledame dal
		pom2 = pom;	//save last searched
	} //for
	//pozice nenalezena - prazdna fronta ci nakonec
	//? prazdna fronta
	if (pom2 == NULL)
	{
		head = CreateItem(index, price);
		head->next = NULL;
		head->prev = NULL;
	}
	//vlozeni na konec v pom2 ukazatel na posledni
	else
	{
		SQueueItem *newI = CreateItem(index, price);
		newI->next = NULL;
		newI->prev = pom2;
		pom2->next = newI;
	}
	return true;
}

/* vyjmuti prvku z fronty */
unsigned Deque()
{
	if (head == NULL)
		return 0;
	qCount--;
	//vyjmuti ze fronty
	SQueueItem *pom = head;
	head = head->next;
	if (head != NULL)
		head->prev = NULL;
	//zruseni prvku
	unsigned res = pom->vertex;
	delete pom;
	return res;
}

/* zruseni cele fronty */
void DestroyQueue()
{
	while(Deque() > 0);
}

// Iniciace --------------------------------------------------
/* iniciace - vytvari a plni pole, pocatek do fronty */
void Init()
{
	unsigned i;
	//zjisteni max objemu
	MAX_CONTENT = 0;
	for(i = 0; i < MAXBUCKET; i++)
	{
		if (full_buckets[i] > MAX_CONTENT)
			MAX_CONTENT = full_buckets[i];
	}
	//alokace poli
	needed = new short[MAX_CONTENT + 1];
	actual = new short[MAX_CONTENT + 1];
	placed = new short[MAX_CONTENT + 1];
	types = new short[MAX_CONTENT + 1];
	//nastaveni typu na UNKNOWN
	types[0] = cEMPTY;
	for(i = 1; i <= MAX_CONTENT; i++)
		types[i] = cUNKNOWN;
	//zjisteni typu objemu
	for(i = 0; i < MAXBUCKET; i++)
	{
		//nastaveni full
		unsigned cont = full_buckets[i];
		types[cont] = cFULL;
		//nastaveni two_mixed
		for(int j = i; j < MAXBUCKET; j++)
		{
			unsigned obj = abs(cont - full_buckets[j]);
			if(types[obj] == cUNKNOWN)
				types[obj] = cTWO_MIX;
		}
	}
	//nastaveni needed
	ZeroArray(needed);
	for(i = 0; i < MAXBUCKET; i++)
	{
		unsigned final = final_buckets[i];
		needed[final]++;
		//typ na needed - lichy
		if ((types[final] % 2) == 0)
			types[final]++;
	}
	//vlozeni pocatecniho stavu do fronty
	Enque(1);
}

// Zpracovani stavu --------------------------------------------------
/* je jiz dany stav prozkoumany */
bool AlreadyReached(unsigned index)
{
	for (unsigned i = ffree - 1; i > 0; i--)
	{
		if (compare(index, i))
			return true;
	}
	return false;
}

/* vlozeni do fronty a ulozeni stavu, pokud neni ve fronte pritomen */
EPutResult EnquePut(unsigned newV, unsigned backV)
{
	//? koncovy stav - ulozeni stavu a navrat
	if (check(newV)) {
		putvertex(backV);
		save(newV, backV);
		return FOUND;
	}
	//vlozeni, pokud jiz nebyl dosazen
	if (! AlreadyReached(newV) ) {
		Enque(newV);
		putvertex(backV);
	}
	return CONTINUE; //pokracujeme v hledani
}

/* preliti kyblu do vsech ostatnich */
EPutResult PourToAll(unsigned vertIndex, unsigned buckIndex)
{
	vertex *vert = vertices + vertIndex;
	unsigned my;
	EPutResult res;
	for(unsigned i = 0; i < MAXBUCKET; i++)
	{
		//? nelejeme do sebe sama
		if (i != buckIndex)
		{
			my = pour(vertIndex, buckIndex, i);
			res = EnquePut(my, vertIndex);
			if (res != CONTINUE)
				return res;
		}
	}
	return res;
}

/* Prozkoumani daneho uzlu, nasledniky dava do fronty */
EPutResult ExploreVertex(unsigned index)
{
	vertex *vert = vertices + index;	//akt. stav
	unsigned my;
	EPutResult res = CONTINUE;
	//prujezd kbeliky
	for(unsigned i = 0; i < MAXBUCKET; i++)
	{
		//? prazdny - naplnime
		if (isempty(index, i))
		{
			my = fill(index, i);	//novy stav
			res = EnquePut(my, index);
		}
		//? plny - vylit + prelit
		else if (isfull(index, i))
		{
			//? posledni operace nebyla naliti plneho - vyliti
			if ((vert->oper != 1) || (vert->which1 != i))
			{
				my = empty(index, i);
				res = EnquePut(my, index);
			}
			//preliti do vsech
			if (res == CONTINUE)
				res = PourToAll(index, i);
		}
		//poloprazdny
		else
		{
			//typ objemu akt. kbeliku
			switch (types[vert->bucket[i]])
			{
				//nejaky plny
				case cFULL:
				case cFULL_NEEDED:
					break;
				case cUNKNOWN:
					my = empty(index, i);
					res = EnquePut(my, index);
					if (res != CONTINUE)
						break;
				default:
					res = PourToAll(index, i);
					break;
			}
		} //poloprazdny
		//konec pokud neco nalezeno
		if (res != CONTINUE)
			return res;
	} //for
	return res;
}

/* Reseni problemu kyblu Vasi heuristikou */
void search(void) 
{
	Init();
	EPutResult res;
	do
	{
		unsigned index = Deque();
		res = ExploreVertex(index);
	} while (res == CONTINUE);


	printf("SEARCH: DONE\n");
	fprintf(trace,"SEARCH: DONE\n");
}

// ----------------------------------------------------------------------------
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);
}

// plneni dat ------------------------------
void null(unsigned *data) {
	data[0] = 0;
	data[1] = 0;
	data[2] = 0;
	data[3] = 0;
	data[4] = 0;
}
//1. zadani ----------------------------------
void full1(unsigned *data) {
	data[0] = 14;
	data[1] = 10;
	data[2] = 6;
	data[3] = 2;
	data[4] = 8;
}
void init1(unsigned *data) {
	null(data);
	data[2] = 1;
}
void final11(unsigned *data) {
	data[0] = 12;
	data[1] = 6;
	data[2] = 4;
	data[3] = 1;
	data[4] = 8;
}
void final12(unsigned *data) {
	data[0] = 14;
	data[1] = 4;
	data[2] = 5;
	data[3] = 0;
	data[4] = 4;
}
void final13(unsigned *data) {
	data[0] = 12;
	data[1] = 6;
	data[2] = 6;
	data[3] = 2;
	data[4] = 4;
}
void final14(unsigned *data) {
	data[0] = 0;
	data[1] = 2;
	data[2] = 1;
	data[3] = 2;
	data[4] = 8;
}
//2. zadani -----------------------------
void full2(unsigned *data) {
	data[0] = 15;
	data[1] = 12;
	data[2] = 8;
	data[3] = 4;
	data[4] = 6;
}
void init2(unsigned *data) {
	null(data);
}
void final21(unsigned *data) {
	data[0] = 5;
	data[1] = 5;
	data[2] = 5;
	data[3] = 0;
	data[4] = 1;
}
void final22(unsigned *data) {
	data[0] = 12;
	data[1] = 1;
	data[2] = 3;
	data[3] = 4;
	data[4] = 5;
}
void final23(unsigned *data) {
	data[0] = 11;
	data[1] = 1;
	data[2] = 3;
	data[3] = 4;
	data[4] = 5;
}
void final24(unsigned *data) {
	data[0] = 3;
	data[1] = 12;
	data[2] = 4;
	data[3] = 0;
	data[4] = 6;
}
void final25(unsigned *data) {
	data[0] = 2;
	data[1] = 0;
	data[2] = 4;
	data[3] = 3;
	data[4] = 6;
}
//3. zadani ---------------------------
void full3(unsigned *data) {
	data[0] = 14;
	data[1] = 10;
	data[2] = 12;
	data[3] = 3;
	data[4] = 8;
}
void init3(unsigned *data) {
	null(data);
}
void final31(unsigned *data) {
	data[0] = 13;
	data[1] = 9;
	data[2] = 12;
	data[3] = 2;
	data[4] = 7;
}
void final32(unsigned *data) {
	data[0] = 1;
	data[1] = 5;
	data[2] = 5;
	data[3] = 3;
	data[4] = 4;
}
void final33(unsigned *data) {
	data[0] = 0;
	data[1] = 9;
	data[2] = 6;
	data[3] = 3;
	data[4] = 1;
}
void final34(unsigned *data) {
	data[0] = 12;
	data[1] = 0;
	data[2] = 12;
	data[3] = 0;
	data[4] = 2;
}
void final35(unsigned *data) {
	data[0] = 7;
	data[1] = 3;
	data[2] = 7;
	data[3] = 0;
	data[4] = 0;
}
void final36(unsigned *data) {
	data[0] = 7;
	data[1] = 0;
	data[2] = 7;
	data[3] = 0;
	data[4] = 7;
}

// spousteni ---------------------------------------------
//nastaveni kbeliku
unsigned full[5];
unsigned final[5];
unsigned init[5];

/* jedna instance - nutno inicializovat pole^ a dobre menit adresar */
void runOnce(unsigned &explored, unsigned &opers, unsigned &milis) {
unsigned b = 0;
clock_t start, end;

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

set_full_buckets(full, 5);
b=set_initial_buckets(init, 5);
set_final_buckets(final, 5);
if (!initcheck(b)) {
   printf("MAIN: INITIAL STATE IS INVALID \n");
   fprintf(trace,"MAIN: INITIAL STATE IS INVALID \n");
   exit(1);
   }

//gettime(&t);
//printf("%2i:%02i  MAIN: Starting search...\n",t.ti_hour,t.ti_min);
//fprintf(trace,"%2i:%02i  MAIN: Starting search...\n",t.ti_hour,t.ti_min);
printf("MAIN: Starting search...\n");
fprintf(trace,"MAIN: Starting search...\n");
start = clock();

search(); /* uplne prochazeni stav. prostoru */

end = clock();

//vracene hodnoty
milis = (unsigned)((double)(end-start)*1000.0 / CLOCKS_PER_SEC);
explored = ffree - 1;
opers = vertices[explored].count;

//gettime(&t);
//printf("%2i:%02i  MAIN: DONE AFTER EXPLORING %i VERTICES \n\n",t.ti_hour,t.ti_min,ffree-1);
//fprintf(trace,"%2i:%02i  MAIN: DONE AFTER EXPLORING %i VERTICES \n",t.ti_hour,t.ti_min,ffree-1);
printf("MAIN: DONE AFTER EXPLORING %i VERTICES (%d ms)\n\n",ffree-1,milis);
fprintf(trace,"MAIN: DONE AFTER EXPLORING %i VERTICES (%d ms)\n",ffree-1,milis);
//printf("\n\n\n\n");
dump_vertices();
save_vertices(); /* ulozeni stav. prostoru */

//destroying data
DestroyQueue();		//zruseni dynamicke fronty
ffree = 1;				//"zruseni" stav. prostoru
fclose(trace);		//zavreni souboru
fclose(fv);
}

/* vypsani hodnot do tabulky */
void TablePrint(unsigned prik, unsigned zad, unsigned expl, unsigned opers, unsigned milis, FILE *table)
{
  fprintf(table, "%2u %2u    expl: %6u    opers: %4u    time: %6u ms\n", prik, zad, expl, opers, milis);
}

void ChangeDir(const char* name)
{
	mkdir(name);
	chdir(name);
}

/* spusteni jedne instance se zmenou adresare */
void Run(unsigned prik, unsigned zad, void (*FinalFill)(unsigned *), const char *dirName, FILE *table)
{
	unsigned 
		explored, opers, milis;
	ChangeDir(dirName);
	FinalFill(final);
	runOnce(explored, opers, milis);
	TablePrint(prik, zad, explored, opers, milis, table);
	chdir("..");
}

/* hlavni metoda */
void main()
{
	FILE * table;
	ChangeDir("data");
	table = fopen("table.txt", "w");
		ChangeDir("priklad1");
			full1(full);
			init1(init);
			Run(1, 1, final11, "zadani1", table);
			Run(1, 2, final12, "zadani2", table);
			Run(1, 3, final13, "zadani3", table);
			Run(1, 4, final14, "zadani4", table);
			chdir("..");
		ChangeDir("priklad2");
			full2(full);
			init2(init);
			Run(2, 1, final21, "zadani1", table);
			Run(2, 2, final22, "zadani2", table);
			Run(2, 3, final23, "zadani3", table);
			Run(2, 4, final24, "zadani4", table);
			Run(2, 5, final25, "zadani5", table);
			chdir("..");
		ChangeDir("priklad3");
			full3(full);
			init3(init);
			Run(3, 1, final31, "zadani1", table);
			Run(3, 2, final32, "zadani2", table);
			Run(3, 3, final33, "zadani3", table);
			Run(3, 4, final34, "zadani4", table);
			Run(3, 5, final35, "zadani5", table);
			Run(3, 6, final36, "zadani6", table);
			chdir("..");
	fclose(table);
	chdir("..");
}