#include <time.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
//#include <conio.h>

#define SOGLIA 5   /*per l'algoritmo del Mio Domino*/


struct tessera {
		char elem[2];
	       };

typedef struct {
	  struct tessera tx;
	  int num;
	  int assetto;
	}TipoDepo;

int indice;
TipoDepo *dep;

typedef struct {
	  TipoDepo *p;
	  struct tessera *t;
	  int allo;
	  int dimmax;
	  int dimdomino;
      }TipoDomino;

TipoDomino domino;
struct tessera tess_gen;

char c;

 /*prototipi di funzione utilizzate*/


 int CostrDepo(int,int);
 void Ruota(struct tessera *);
 int Genera(int);
 void Visdep(int);
 void Insert(struct tessera *, int);
 void Elim(struct tessera *, int);
 int DominRand(int);
 int DominGreedy(int);
 int MioDomin(int);
 void MostraDomin(void);
 void Esperimento(int, int, int);
 int Compact(TipoDepo *, TipoDepo *);
 int NumCompa(TipoDepo *, TipoDepo *, int);


void clrscr(void)
 {
  system ("clear");
  }


 /*funzione che controlla la compatibilita' delle tessere*/

int Compact(TipoDepo *tx1, TipoDepo *tx2)
{
 int j;

 for(j=0; j<2; j++)
  if(tx2->tx.elem[j] == tx1->tx.elem[0])
      return 1;
 return 0;
}



/*funzione che calcola il numero di tessere compatibili*/


int NumCompa(TipoDepo *tx, TipoDepo *d, int size)
{
 int j, n=0;

 for(j=0; j<size; j++)
 {
  if(tx == &d[j])
  {
   n += d[j].num-1;
     continue;
   }
  if(Compact(tx, &d[j]) == 1)
    n += d[j].num;
  }
 return n;

}



 /*funzione che genera il domino greedy*/


int DominGreedy(int n)
{

  int j, o, k, l, s;
  TipoDepo *d2;
  struct tessera t1, *t2;

  d2 = malloc( sizeof(TipoDepo) * (domino.allo+1));
  memcpy( d2, dep, sizeof(TipoDepo) * (domino.allo+1));
  domino.t = malloc( n * sizeof( struct tessera));

  l=0;

  t2 = NULL;
  for(j=0; j<domino.allo; j++)
  {
   k = NumCompa(&d2[j],d2,n);
   if(k > l)
   {
    l=k;
    t2=&d2[j].tx;
   }
  }

  memcpy( &domino.t[0], t2, sizeof( struct tessera));
  d2->num--;
  for(j=1; j<n; j++)
  {
   s=0;
   t2=NULL;
   for( k=0; k<domino.allo; k++)
    {
     if (d2[k].num < 1)
       continue;
     if ( (domino.t[j-1].elem[0] != d2[k].tx.elem[0]) &&
	(domino.t[j-1].elem[0] != d2[k].tx.elem[1]))
	 continue;

     l = NumCompa(&d2[k],d2,n);
     if(l>s)
      {
       s=n;
       t2 = &d2[k].tx;
       o = k;
      }
    }
    if(t2 == NULL)
     break;
    while ( domino.t[j-1].elem[0] != t2->elem[1])
	Ruota( t2);
    memcpy(&domino.t[j], t2, sizeof( struct tessera));
    d2[o].num--;
   }
 free(d2);
 return domino.dimdomino = j;
}


 /*funzione che genera il Mio Domino*/

int MioDomin(int n)
{

  int j, o, k, l;
  TipoDepo *d2;
  struct tessera t1, *t2;
  int soglia, trov;

  d2 = malloc( sizeof(TipoDepo) * (domino.allo+1));
  memcpy( d2, dep, sizeof(TipoDepo) * (domino.allo+1));
  domino.t = malloc( n * sizeof( struct tessera));

  l=0;

  t2 = NULL;
  for(j=0; j<domino.allo; j++)
  {
   k = NumCompa(&d2[j],d2,n);
   if(k > l)
   {
    l=k;
    t2=&d2[j].tx;
   }
  }

  memcpy( &domino.t[0], t2, sizeof( struct tessera));
  d2->num--;
  for(j=1; j<n; j++)
  {

   t2=NULL;
   trov = 0;
   for( soglia=SOGLIA; soglia >=0; soglia--) {
	for( k=0; k<domino.allo; k++)
	{
	if (d2[k].num < 1)
		continue;
	if ( (domino.t[j-1].elem[0] != d2[k].tx.elem[0]) &&
		(domino.t[j-1].elem[0] != d2[k].tx.elem[1]))

			continue;
	l = NumCompa(&d2[k],d2,n);
	if(l>soglia)
	{
		t2 = &d2[k].tx;
		o = k;
		trov = 1;
		break;
	}
	if (trov) break;
    }
   }
   if(t2 == NULL)
     break;
   while ( domino.t[j-1].elem[0] != t2->elem[1])
	Ruota( t2);
   memcpy(&domino.t[j], t2, sizeof( struct tessera));
   d2[o].num--;
 }
 free(d2);
 return domino.dimdomino = j;
}




/*funzione che genera il Domino Random*/

int DominRand(int n)
{
  int j, k, l, e, trov;
  TipoDepo *d2;
  struct tessera t1;

  d2 = malloc( sizeof(TipoDepo) * (domino.allo+1));
  memcpy( d2, dep, sizeof(TipoDepo) * (domino.allo+1));
  domino.t = malloc( n * sizeof( struct tessera));

  j = rand() % (domino.allo + 1);
  k = rand() % 2;
  memcpy( &t1, &d2[j].tx, sizeof( struct tessera));
  d2[j].num--;
  for( e=0; e<k; e++) Ruota( &t1);
    memcpy( &domino.t[0], &t1, sizeof( struct tessera));
  for( j=1; j<n; j++)
   {
    trov = 0;
    for( k=0; k<= domino.allo; k++)
     {
      if (( domino.t[j-1].elem[0] == d2[k].tx.elem[1]) && ( d2[k].num >= 1))
       {
	memcpy( &domino.t[j], &d2[k].tx, sizeof( struct tessera));
	d2[k].num--;
	trov = 1;
	break;
       }
     }
   if (!trov) break;
  }
 free( d2);
 return domino.dimdomino = j;
}




/*funzione che visualizza l'ultimo domino creato*/

void MostraDomin()
{
 int cont, num, j;

 cont = 6;
 for( j=domino.dimdomino-1; j>=0; j--)
   {
    if(cont == 0)
    {
     cont=6;
     printf("\n\n INVIO per continuare a visualizzare il domino...\n");
     c = getchar();

    }
    printf("\n");
    printf(" ---------\n");
    printf("|  %d   %d |\n", domino.t[j].elem[0], domino.t[j].elem[1]);
    printf(" ---------");
    --cont;

 }
 printf("\n\n Numero di tessere collocate nel domino : %d\n", domino.dimdomino);

}



/*funzione che inserisce nuove tessere nel deposito*/

void Insert(struct tessera *t, int num_tess)
{
  int trov, i, j, k, e;

  trov = 0;
  
    for( e=0; e<domino.allo; e++)
     {
      if ((( t->elem[0] == dep[e].tx.elem[0]) &&
	   ( t->elem[1] == dep[e].tx.elem[1])) || 
	   ((t->elem[0] == dep[e].tx.elem[1]) && 
	   (t->elem[1] == dep[e].tx.elem[0])))
       {
	 dep[e].num += num_tess;
	 trov = 1;
	 return;
	 }
       }
      
      
     
   if(!trov)
   {
     realloc(domino.p, domino.dimmax * sizeof( struct tessera));
     dep = domino.p;
     dep[domino.allo].tx.elem[0] = t->elem[0];
     dep[domino.allo].tx.elem[1] = t->elem[1];
     dep[domino.allo].num = num_tess;
     dep[domino.allo].assetto = 0;
     domino.allo++;
    }
}



/*funzione che elimina  tessere nel deposito*/

void Elim(struct tessera *t, int eli_tess)
{
  int trov, i, j, k, e;

  trov = 0;
  for( k=0; k<1; k++)
   {
    for( e=0; e<=domino.allo; e++)
     {
      if (( t->elem[0] == dep[e].tx.elem[0]) &&
	  ( t->elem[1] == dep[e].tx.elem[1]))
	{
	 if (dep[e].num < eli_tess)
	   {
	    clrscr();
	    printf("\n\n ERRORE : vi sono solo %d tessere del tipo [%d,%d]\n\n", dep[e].num,
	     dep[e].tx.elem[0], dep[e].tx.elem[1]);
	    printf("\n INVIO per tornare alla schermata iniziale... ");
	    c = getchar();
	    }
	  dep[e].num -= eli_tess;

	 if (dep[e].num < 0)
	   dep[e].num = 0;
	 trov = 1;
	 return;
	}
      }
    }
 clrscr();
 printf("\n\n ERRORE : la tessera da eliminare non fa parte del deposito di tessere \n\n");
 printf("\n INVIO per tornare alla schermata iniziale... ");
 c = getchar();
}



/*funzione che genera a random i valori delle etichette delle tessera*/

int Genera(int m)
{
  int k;

  k = rand()%(m+1);
  return k;
}



/*funzione che ruota la tessera appena creata*/

void Ruota(struct tessera *tess_gen)
 {
  struct tessera tx;

  tx.elem[0] = tess_gen->elem[1];
  tx.elem[1] = tess_gen->elem[0];
  memcpy( tess_gen, &tx, sizeof( struct tessera));

}



/*funzione che genera il deposito di tessere*/

int CostrDepo(int n, int m)
{
  int i, j, e, k;
  int trov, inx;

  dep = malloc(sizeof(TipoDepo) * n);
  if (!dep)
    {
      printf( "Errore di allocazione\n");
      exit(0);
     }
  inx = 0;
  for( i=0; i<n; i++)
   {
    
    tess_gen.elem[0] = Genera(m);
    tess_gen.elem[1] = Genera(m);
    trov = 0;
    
    
      for( e=0; e<inx; e++)
       {
	if ((( tess_gen.elem[0] == dep[e].tx.elem[0]) &&
	   ( tess_gen.elem[1] == dep[e].tx.elem[1])) || 
	   ((tess_gen.elem[0] == dep[e].tx.elem[1]) && 
	   (tess_gen.elem[1] == dep[e].tx.elem[0])))

	 { 
	   dep[e].num++;
	   trov = 1;
	   break;
	  }
	}
      
    if ( trov) continue;
    dep[inx].tx.elem[0] = tess_gen.elem[0];
    dep[inx].tx.elem[1] = tess_gen.elem[1];
    dep[inx].num = 1;
    dep[inx].assetto = 0;
    inx++;
  }
return inx;
}



/*funzione che visualizza il deposito creato*/

void Visdep(int n)
{
  int cont;

  for(cont=0, indice = 0; indice < domino.allo;cont += dep[indice].num, indice++);
  printf("\n\nLe tessere occupate sono : %d\n", n);
  cont=16;
  for(indice=0; indice < domino.allo; indice++)
    {
    if(cont == 0)
     {
       cont=16;
       printf("\n\n INVIO per continuare a visualizzare il deposito...\n\n");
       c = getchar();
      }
     if (dep[indice].num > 0)
      printf("\n %d%s%d%s%d%s", dep[indice].num ,"tessere del tipo [", dep[indice].tx.elem[0],",",
	      dep[indice].tx.elem[1],"]");
     --cont;
    }
}


/*funzione che calcola i valori relativi all'esperimento*/

void Esperimento(int m, int n, int cicli)
{
 clock_t start;
 clock_t stop;
 
 double cps = (double) CLOCKS_PER_SEC;
 int i;
 int  G, R, M;
 double tCD, tG, tR, tM;
 int cont_G, cont_R, cont_M;
 float mediaG, mediaR, mediaM;
 
 
 
 G = R = M = 0;
 tCD = tG = tR = tM = 0;
 cont_G = cont_R = cont_M = 0;
 
 for(i=0; i<cicli; i++)
 {
   clrscr();
   printf("\n    >>>   TEMPI DI ESECUZIONE   <<<   \n");
   start = clock();
   CostrDepo(n,m);
   tCD = (double)((stop-start)/cps);
   printf("\n Costruzione del deposito di tessere   > %.1f secondi\n", tCD);

   start = clock();
   G = DominGreedy(n);
   stop = clock();
   tG = (double)((stop-start)/cps);
   printf(" Costruzione del Domino Greedy         > %.1f secondi\n", tG);

   start = clock();
   R = DominRand(n);
   stop = clock();
   tR = (double)((stop-start)/cps);
   printf(" Costruzione del Domino Random         > %.1f secondi\n", tR);

   start = clock();
   M = MioDomin(n);
   stop = clock();
   tM = (double)((stop-start)/cps);
   printf(" Costruzione del Mio Domino            > %.1f secondi\n", tM);


   printf("\n");
   printf("\n   >>>   RAPPORTI FRA LE ALTEZZE DEI DOMINI  <<<  \n");
   printf("\n Rapporto  Domino  Greedy/Random     > %d", G/R );
   printf("\n Rapporto  Domino  Mio/Random        > %d", M/R );

   cont_G +=G;
   cont_R +=R;
   cont_M +=M;

   printf("\n\n INVIO %d volte per proseguire nella visualizzazione dei risultati ...", cicli);
   c = getchar();
  }
 
 mediaG = (double)((double)cont_G/cicli);
 mediaR = (double)((double)cont_R/cicli);
 mediaM = (double)((double)cont_M/cicli);
 
 printf("\n   >>>   VALORI MEDI DELLE ALTEZZE DEI DOMINI   <<< \n");
 printf("\n I valori medi delle altezze dei domini dopo %d cicli sono : \n\n", cicli);
 printf(" Domino Greedy    > %.1f\n", mediaG);
 printf(" Domino Random    > %.1f\n", mediaR);
 printf(" Domino Mio       > %.1f\n", mediaM);

 printf("\n INVIO per tornare alla schermata iniziale... ");
 c = getchar();

}




  /*FUNZIONE PRINCIPALE*/


void main()
{
 char ch;
 int m, n, eli_tess, num_tess, cicli;
 struct tessera tess;
 int u, d, t , q;


 srand((unsigned)time(NULL));  /* inizializza il generatore di numeri casuali*/

  do
  {
    printf("\n\n\n\n");
    printf("       ###############################################################\n");
    printf("       ###                                                         ###\n");
    printf("       ###                   PROGETTO DOMINO 2                     ###\n");
    printf("       ###                                                         ###\n");
    printf("       ###    a _ Creazione di un nuovo deposito di tessere        ###\n");
    printf("       ###    b _ Visualizzazione del deposito di tessere          ###\n");
    printf("       ###    c _ Inserimento di alcune tessere nel deposito       ###\n");
    printf("       ###    d _ Eliminazione di alcune tessere nel deposito      ###\n");
    printf("       ###    e _ Creazione di un Domino Greedy                    ###\n");
    printf("       ###    f _ Creazione di un Domino Random                    ###\n");
    printf("       ###    g _ Creazione di un Mio Domino                       ###\n");
    printf("       ###    h _ Visualizzazione del Domino corrente              ###\n");
    printf("       ###    i _ Visulizzazione della tabella dell'esperimento    ###\n");
    printf("       ###                                                         ###\n");
    printf("       ###    E _ USCITA                                           ###\n");
    printf("       ###                                                         ###\n");
    printf("       ###############################################################\n\n\n");
    printf("           Digita il carattere corrispondente all'operazione \n");
    printf("           desiderata >  ");

    scanf("%c", &ch);
    c = getchar();
    switch(ch)
     {
      case 'a' :
	   clrscr();
	   printf("\n     >>>   COSTRUZIONE DEL DEPOSITO DI TESSERE  <<< \n");
	   printf("\n\n\n%s\n","  Inserire il range massimo delle tessere del deposito");
	   printf("%s","     (inserire un numero intero positivo)  >  ");
	   scanf("%d", &m);
	   c = getchar();
	   printf("\n%s","  Inserire il numero di tessere che si vuole avere nel deposito > ");
	   scanf("%d", &n);
	   c = getchar();
	   domino.allo = CostrDepo(n, m);
	   domino.p = dep;
	   domino.dimmax = n * sizeof( struct tessera);
	   printf("\n\n\n  >>>     Un nuovo deposito si e' costituito !!   <<<\n");
	   printf("\n\n INVIO per tornare alla schermata iniziale... ");
	   c = getchar();
	   break;

      case 'b' :
	   clrscr();
	   printf("\n     >>>  VISUALIZZAZIONE DEL DEPOSITO CORRENTE  <<< \n");
	   Visdep(n);
	   printf("\n\n INVIO per tornare alla schermata iniziale...");
	   c = getchar();
	   break;

      case 'c' :
	   clrscr();
	   printf("\n    >>>  INSERIMENTO DI NUOVE TESSERE NEL DEPOSITO   <<< \n");
	   printf("\n\n Inserisci il tipo di tessera che vuoi inserire nel deposito\n");
	   printf(" (Ricordati che puoi inserire tessere di range massimo da 0 a %d) > ", m);
	   scanf("%d %d", &u, &d);
	   tess.elem[0] = u;
	   tess.elem[1] = d;
	   printf("\n\n Inserisci la quantita' di tessere da inserire > ");
	   scanf("%d", &num_tess);
	   c = getchar();
	   Insert(&tess, num_tess);
	   n += num_tess;
	   break;

      case 'd' :
	   clrscr();
	   printf("\n    >>>  ELIMINAZIONE DI TESSERE NEL DEPOSITO   <<< \n");
	   printf("\n\n Inserisci il tipo di tessera che vuoi eliminare nel deposito\n");
	   printf(" (Ricordati che puoi inserire tessere di range massimo da 0 a %d) > ", m);
	   scanf("%d %d", &u, &d);
	   tess.elem[0] = u;
	   tess.elem[1] = d;
	   printf("\n\n Inserisci la quantita' di tessere da eliminare > ");
	   scanf("%d", &eli_tess);
	   c = getchar();
	   Elim(&tess, eli_tess);
	   n -= eli_tess;
	   break;

      case 'e' :
	   clrscr();
	   DominGreedy(n);
	   printf("\n\n\n >>> Il Domino Greedy e' stato generato <<< \n");
	   printf("\n INVIO per tornare alla schermata iniziale... ");
	   c = getchar();
	   break;

      case 'f' :
	   clrscr();
	   DominRand(n);
	   printf("\n\n\n >>> Il Domino Random e' stato generato <<< \n");
	   printf("\n INVIO per tornare alla schermata iniziale... ");
	   c = getchar();
	   break;

      case 'g' :
	   clrscr();
	   MioDomin(n);
	   printf("\n\n\n >>> Il Mio Domino e' stato generato <<< \n");
	   printf("\n INVIO per tornare alla schermata iniziale... ");
	   c = getchar();
	   break;

      case 'h' :
	   clrscr();
	   printf("\n >>> VISUALIZZAZIONE DELL'ULTIMO DOMINO GENERATO  <<< \n");
	   MostraDomin();
	   printf("\n INVIO per tornare alla schermata iniziale... ");
	   c = getchar();
	   break;

      case 'i' :
	   clrscr();
	   printf("\n                >>>  ESPERIMENTO  <<<  \n");
	   printf("\n\n\n%s\n","  Inserire il range massimo delle tessere del deposito");
	   printf("%s","     (inserire un numero intero positivo)  >  ");
	   scanf("%d", &m);
	   c = getchar();
	   printf("\n%s","  Inserire il numero di tessere che si vuole avere nel deposito > ");
	   scanf("%d", &n);
	   c = getchar();
	   printf("\n  Indicare il numero di cicli che si devono eseguire per l'esperimento > ");
	   scanf("%d", &cicli);
	   c = getchar();
	   Esperimento(m,n,cicli);
	   break;

     } /*switch*/
    }
    while(ch != 'E');
  }