#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define clrscr() system ("cls")
#define pause() system ("pause")

//costante di grandezza della tabella
#define DIM_TABELLA 20

int hash(char *chiave)
	{
		int indice=0, base=128;
		for(;*chiave!='\0';chiave++)
		indice=(base*indice+*chiave)%DIM_TABELLA;
		return indice;
	}



int scan(char* k, char* tabella[], char* sentinella)
	{
		int indice, //punta alla chiave corrente
			 primo, 	//se indice torna ad assumere il suo valore
						//il ciclo di scansione si considera terminato

			 terminato; //nel while varrà true quando
							//primo==indice

	//inizializzazione
		primo=indice=hash(k);
		terminato=0;

	//ciclo di scansione
		while(!terminato && strcmp(tabella[indice],sentinella)!=0)
		//ci sono due vie per uscire dal ciclo:
		//1) quando si ritorna alla chiave di partenza (terminato)
		//2) quando si trova la prima chiave libera
			{
				//calcolo del prox indice
				indice=(indice+1)%DIM_TABELLA;

				//se l'indice corrente coincide col primo
				//allora considero il ciclo terminato
				if(primo==indice)
				terminato=1;
			} //fine del ciclo while

	//esito della scansione
		if(terminato)
      //se non si trova un posto libero per la chiave
		//allora si restituisce un valore di indice non ammissibile
		//che sarà interpretato all'esterno della funzione
			return DIM_TABELLA;
		else
		//altrimenti è implicito che sia stata trovata una locazione
		//libera e quindi se ne restituisce l'indice
			return indice;
	}

void stampa_tab_hash(char* tabella[])
	{
      for(int i=0;i<DIM_TABELLA;i++)//inizializzazione della tabella hash
			printf("\n tab_hash[%d]= %s ",i,tabella[i]);

		printf("\n");
   }

int main()
	{
      char* libero="0:FREE:0"; //la scelta della stringa di inizializzazione
      								 //è arbitraria, l'importante è che non coincida
                               //con una delle possibili chiavi.

		char* tab_hash[DIM_TABELLA];//dichiarazione della tabella hash

      for(int i=0;i<DIM_TABELLA;i++)//inizializzazione della tabella hash
      	tab_hash[i]=libero;

		//in questo punto occorre definire il modo con cui
      //dare in pasto al programma una serie di chiavi,
      //l'input può essere un problema, perchè la traccia
      //può chiederti di leggere da un file (è molto probabile)
      //oppure può chiederti un input da tastiera
      //purtroppo non ho il tempo di spiegarti questi due casi
      //ci vorrebbe un tutorial fatto apposta.
      //tuttavia per testare il programma userò un vettore di stringhe
      //che è più semplice (ma purtroppo meno utile per le applicazioni hash)
      //anche per non appesantirti la comprensione del codice
      //introducendo una struct

		char* elenco_id[]=//tabella dei token di 8 elementi
			{
				"pippo",
    			"pluto",
            "paperino",
    			"topolino",
    			"provolino",
    			"geppo",
    			"pbolo",  //non può mancare lui!!!ehehehehe
    			"ciccio"
         };

   	int cella; //contiene l'indice in cui sarà posizionata la chiave corrente

      for(int i=0;i<8;i++)
      //sottopongo a scan gli 8 elementi di elenci_id
      //poichè la dimensione della tab hash è 7 l'ultimo elemento (ciccio)
      //non sarà inserito e verrà fuori il messaggio di tab satura
         {
      		cella=scan(elenco_id[i],tab_hash,libero);

      		if(cella<DIM_TABELLA)
					tab_hash[cella]=elenco_id[i];
		   	else
   				printf("\n La tabella e' satura!");
         }

      stampa_tab_hash(tab_hash);
      system("PAUSE");
	}