/******************************************/
/* KYBLE V1.0       PAA  1999     kyble.c */
/* Reseni zobecneneho problemu dvou kyblu */
/* Copyright (c) 1999 by KP CVUT-FEL      */
/******************************************/
/*
 * CHANGED
 * by Jakub Holy
 * 1. header file renamed to .hh
 * 2. removed headers conio.h and dos.h
 * 3. removed everything dealing with time (struct time t) - not linux
 */ // 	$Id: kyble.cc.html,v 1.1.1.1 2003/11/08 13:19:49 aja Exp $	

#include "kyble.hh"//CHANGED

#include <stdio.h>
#include <stdlib.h>
//#include <conio.h>//CHANGED
//#include <dos.h>//CHANGED

//ADDED-beg
#include <time.h>	// potrebujeme tisknout cas
//#include <map>		// multimap =?= hash tbl
#include <queue>	// priority_queue
#include <vector>	// vector underlying the priority_queue
#include <assert.h>
#include <iostream>	// cout, cin
#include <algorithm>	// max_element
using namespace std;
#define STARTNODE  1	// index pocatecniho uzlu ve vertices 
//ADDED-end

//#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[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 */
//CHANGED//struct time t;                     /* cas vypoctu */

//ADDED-beg --------------------------
// Used to get and print time
struct tm t;
// Element of the queue
class QueueElement{
public:
  unsigned state_index;
  unsigned penalty;
  QueueElement( unsigned state, unsigned pen ){ state_index = state; penalty = pen; }; 
  // Needed for the priority queue; the higher penalty the worse it is
  bool operator<( const QueueElement &e) const { return this->penalty > e.penalty; };
friend ostream& operator<<(ostream& out, const QueueElement &e){
  out<< "{p:"<< e.penalty << ", s:"<< e.state_index<<"}";
  return out;
}//print
};//QueueElement

// The priority queue
priority_queue< QueueElement > p_queue;
//ADDED-end ----------------------------

// ---------------------------------------------------------- INICIALIZACE aj.
//
// ------------------------------------------------------------

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

void set_final_buckets(void) {
final_buckets[0]=12;
final_buckets[1]=06;
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(void) {
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);

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]=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;
}

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

// ---------------------------------------------------------------- OPERACE ap.
//
// ----------------------------------------------------------------
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;
}

// ------------------------------------------------------------- POMOCNE
//
// -------------------------------------------------------------
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 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");

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

while (b!=0) {
   c++;
   if ((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;
   }
}

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

// ------------------------------------------------------------------ SEARCH
//
// ------------------------------------------------------------------
/** Pomocne fce 
 * Parametry: uzity abych stale znovu nealokoval pamet
 */
// Je stav [ffree] dosud nenavstiveny?
inline bool is_unique(unsigned &index){
  for(index = STARTNODE; index<ffree;index++){
    if( compare(index,ffree) ){ return false;}
  }//for all states visited so far
  return true;
}//is_unique

/** Viz penalty() 
 * Pole [0 az obsah nejvetsiho kyblu]
 * known_volumes[i] je true iff objem i jiz nekdy byl ziskan
 * Pole musi byt inicializovano v main.
 */
bool *known_volumes = NULL;
/**
 * Vypocti "trestne body" (negaci priority) pro stav [ffree]
 * Hodnoty urceny odhadem, bylo by zapotrebi testu.
 */
inline unsigned int penalty(unsigned short &bucket, unsigned &penaltyv){
  assert(known_volumes);	// ujisti se, ze je pole inicializovano
  penaltyv = 0;
  // pro vsechny kyble urci jejich trestne body
  for(bucket = 0; bucket < MAXBUCKET; bucket++){
    //FINAL
    if( (vertices+ffree)->bucket[bucket] == final_buckets[bucket] ){
      continue;		// 0 penalty for the final state
    } else if( isfull(ffree,bucket) || isempty(ffree,bucket) ){
      //EMPTY/FULL
      penaltyv += 25;	// max. penalty for the easiest volumes
    } else if( known_volumes[(vertices+ffree)->bucket[bucket]] ){
      //ZNAMY objem
      penaltyv += 15;
    } else {
      // NOVY objem
      penaltyv += 5;	// 0 vyhrazena konecnemu stavu
      known_volumes[(vertices+ffree)->bucket[bucket]] = true;
#ifdef DEBUG
      cout<<"PENALTY: new volume "<< (vertices+ffree)->bucket[bucket]<<endl;
#endif
    }//if-else ... objem kyblu
#ifdef DEBUGPN
    cout<<"PENALTY: penalty of bucket "<<bucket<<" is\t"<<penaltyv<<" for litres\t";
    cout<<(vertices+ffree)->bucket[bucket]<<".Known: "<<known_volumes[(vertices+ffree)->bucket[bucket]]<<endl;
#endif
  }//for,pro vsechny kyble
  return penaltyv;
}//penalty()

/** SEARCH
 * 1. Inicializuj (vloz pocatecni uzel)
 * 2. Vem celo fronty
 * 3. Je konecny stav? ANO' -> USPECH, uloz vysledek
 * 4. \-NE: ziskej vsechny potomky
 * 4.1  Stav  uz navstiven? ANO -> zahod;
 * 4.2  \-NE: uloz jej do fronty, do vertices
 * 5. Je fronta prazdna? ANO -> NEUSPECH(konec); NE-> bez na 2
 */
void search(void) {
  // 1.INIT: vloz pocatecni stav. Jeho penalty muze byt nastavena na 0, 
  //je to jediny prvek, tak je to jedno.
  assert( ffree == (STARTNODE+1) );// ujisti se,ze inicializace probehla
  p_queue.push( *(new QueueElement( STARTNODE ,0 ) ) );// stav 1, penalty 0
#ifdef DEBUGQ
  cout << "SEARCH: inserted INIT state\n";
#endif

  // SMYCKA algoritmu
  // Promenne uzite ve smycce (neni treba inicializovat)
  unsigned index;			// pouzito v is_unique()
  unsigned short bucket;		// pouzito v penalty()
  unsigned int penaltyv;
  unsigned short bucket1;
  unsigned short bucket2;
  QueueElement *best_state = NULL;
  do {
    // 2.VEM celo fronty -------------------------------------------
    best_state = new QueueElement( p_queue.top() );	// cti 1. prvek fronty
    p_queue.pop();			// odstran 1. prvek z fronty
#ifdef DEBUGQ
    cout << "SEARCH: vzato celo fronty: "<< *best_state << endl;
#endif 

    // 3.KONECNY stav? -------------------------------------------
    if( check(best_state->state_index) ){
      // save the solution into solution.txt; what shall be the 2nd param???
      save( best_state->state_index, (vertices+best_state->state_index)->backptr );
      return;
    }// if je to konecny stav

    // 4.POTOMCI - ziskej vsechny mozne potomky ------------------------------
    // A.POUR
    for(bucket1=0; bucket1 < MAXBUCKET; bucket1++){
      // prelivej jen je-li zdrojovy kybl neprazdny
      if( !isempty(best_state->state_index, bucket1 ) ){
	// pour( bucket1, bucket2 ) != pour( bucket2, bucket1 ):
	for(bucket2=0; bucket2 < MAXBUCKET; bucket2++){
	  // prelivej jen neni-li cilovy kybl plny a je-li ruzny od zdrojoveho
	  if( (bucket1 != bucket2) && !isfull(best_state->state_index,bucket2) ){
	    // Create new state [ffree] by pouring from bucket1 to bucket2
	    // ffree is only incremented in putvertex
	    pour(best_state->state_index, bucket1, bucket2);
	    if( is_unique(index) ){
	      // save it:
#ifdef DEBUGEP
	      cout<<"SEARCH: adding pour child: "<<(vertices+best_state->state_index)->bucket[bucket1]<<" l to "<<(vertices+best_state->state_index)->bucket[bucket2]<<"l, buckets "<<bucket1<<" to "<<bucket2<<endl;
#endif
	      // push in the queue; compute its penalty; 'bucket' param. unimportant
	      p_queue.push( *(new QueueElement( ffree , penalty(bucket, penaltyv) ) ) );
	      // musi byt az ZA PUSH - putvertex zmeni tj. zneplatni ffree
	      putvertex( best_state->state_index );	      
	    }//novy stav dosud nebyl navstiven
	  }//if 2 ruzne kyble
	}// pro vsechny kyble, vnitrni cyklus
      }//if zdojovy kybl neprazdny
    }// pro vsechny kyble, vnejsi cyklus

    //B.FILL
    for(bucket1=0; bucket1 < MAXBUCKET; bucket1++){
      if( !isfull( best_state->state_index, bucket1 ) ){
	fill( best_state->state_index, bucket1 );
	if( is_unique(index) ){
#ifdef DEBUGEP
	      cout<<"SEARCH: adding fill child, bucket "<< bucket1 <<endl;
#endif
	  // push in the queue; compute its penalty
	  p_queue.push( *(new QueueElement( ffree , penalty(bucket, penaltyv) ) ) );
	  // musi byt az ZA PUSH - putvertex zmeni tj. zneplatni ffree// save it:
	  putvertex( best_state->state_index );
	}//if novy stav dosud nebyl navstiven
      }//if neni plny
    }// pro vsechny kyble FILL 

    //C.EMTPY
    for(bucket1=0; bucket1 < MAXBUCKET; bucket1++){
     if( !isempty( best_state->state_index, bucket1 ) ){
       empty( best_state->state_index, bucket1 );
	if( is_unique(index) ){
#ifdef DEBUGEP
	      cout<<"SEARCH: adding empty child, bucket "<< bucket1 <<endl;
#endif

	  // push in the queue; compute its penalty
	  p_queue.push( *(new QueueElement( ffree , penalty(bucket, penaltyv) ) ) );
	  // musi byt az ZA PUSH - putvertex zmeni tj. zneplatni ffree// save it:
	  putvertex( best_state->state_index );
	}//if novy stav dosud nebyl navstiven
      }//if neni prazdny
    }// pro vsechny kyble EMTPY

  // 5.PRAZDNA? (je fronta prazdna?) ------------------------------------------
  // hlavni cyklus algoritmu

  }  while ( !(p_queue.empty()) ); // hl. smycka algoritmu

    // .......................................... KONEC
    printf("SEARCH: DONE\n");
    fprintf(trace,"SEARCH: DONE\n");

  //Search failed, queue is empty
  printf("SEARCH: FAILED - queue empty\n");
  fprintf(trace,"SEARCH: FAILED - queue empty\n");
}//search

// ------------------------------------------------------------------ MAIN
//
// ------------------------------------------------------------------
int main(void) {
/* Reseni zobecneneho problemu dvou kyblu */
unsigned a,b,c;
a=b=c=0;

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


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

//CHANGED
// 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);
//ADDED - replaces previous
 time_t *tmp_t;
 time( tmp_t );			// ziskej soucasny cas
 localtime_r( tmp_t, &t);	// zmen jej na neco citelnejsiho
 printf("%2i:%02i  MAIN: Starting search...\n",t.tm_hour,t.tm_min);
 fprintf(trace,"%2i:%02i  MAIN: Starting search...\n",t.tm_hour,t.tm_min);

 // Musi byt pred search
 // Inicializuj known_volumes[]
 {
 // Najdi nejobjemnejsi kybl (STL funkce)
   unsigned *maxp = max_element(full_buckets, full_buckets + MAXBUCKET);
   assert(maxp != full_buckets + MAXBUCKET);	// kdyz max. prvek neni nalezen
   // Vytvor pole tak dlouhe jaky je max. objem vyskytujici se u kyblu
#ifdef DEBUG
   cout << "MAIN: initializing known_volumes to the length " << *maxp <<endl;
#endif
   known_volumes = new bool[ *maxp ];
   for(unsigned i=0; i<(*maxp); i++){ known_volumes[i] = false; }
   //Oznac max. objemy kyblu za zname
   for(unsigned bucket = 0; bucket < MAXBUCKET; bucket++){
     known_volumes[ full_buckets[bucket] ] = true;
   }//for
   //Objem 0 tez jiz znam
   known_volumes[0] = true;
 }// inic. known_volumes 
//ADDED-end
 search(); /* uplne prochazeni stav. prostoru */

//CHANGED
// 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);
//ADDED - replaces previous
 time( tmp_t );			// ziskej soucasny cas
 localtime_r( tmp_t, &t);	// zmen jej na neco citelnejsiho
printf("%2i:%02i  MAIN: DONE AFTER EXPLORING %i VERTICES \n\n",t.tm_hour,t.tm_min,ffree-1);
 fprintf(trace,"%2i:%02i  MAIN: DONE AFTER EXPLORING %i VERTICES \n",t.tm_hour,t.tm_min,ffree-1);
//ADDED-end
printf("\n\n\n\n");
dump_vertices();
save_vertices(); /* ulozeni stav. prostoru */

fclose(trace);
fclose(fv);

}