/*                                                                    */
/* 					       Programma  sviluppato  da	   					 */
/*                                                                    */
/*      							  Giovanni DI CECCA                  		 */
/*                                                                    */
/*                         http://www.dicecca.net                     */
/*                                                                    */

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

typedef enum {falso, vero} logical;
logical hash_search(int *table, int tablesize, int key);
void hash (int *array, int *table, int dim, int tablesize); /* Prototipo di funzione */

main()
{
	/*dichiarazione di variabili */
 	int *array, *table, i, tablesize, dim, key;

	printf("\nInserire il numero di elementi del vettore: ");
	scanf("%d", &dim);

	array =(int *)calloc(dim, sizeof(int));

	for(i=0; i<dim; i++)
	{
		printf("\nInserire l'elemento %d: \n", i+1);
		scanf("%d", &array[i]);
	}

	tablesize = dim + (dim*25/100)+1;

	table =(int *)calloc(tablesize, sizeof(int));

	for(i=0; i<tablesize; i++)
		table[i]=NULL;

	hash(array, table, dim, tablesize);

	printf("\nDigitare l'elemento da cercare: ");
	scanf("%d", &key);

   if(hash_search(table, tablesize, key))
		printf("\nL'elemento e' presente nel vettore");
	else
		printf("\nL'elemento non e' presente nel vettore");
}

/*--------------------------*/
/* Funzione di ricerca HASH */
/*--------------------------*/

void hash(int *array, int *table, int dim, int tablesize)
{
	int *vett_app, n, j, k, i;

	vett_app=(int *)calloc(dim, sizeof(int));

	n=0;

	for(i=0; i<dim; i++)
	{
		j = array[i] % tablesize;

		if (table[j]==NULL)
			table[j]=array[i];
	   else
  		{
   		vett_app[n]=array[i];
		   n++;
	   }
	}

	for(i=0; i<n; i++)
	{
		k = vett_app[i] % tablesize;

		while(table[k] != NULL)
			k++;

		table[k]=vett_app[i];
	}

	free (vett_app);
}


/*--------------------------*/
/* Funzione di LOGICAL_HASH */
/*--------------------------*/

logical hash_search(int *table, int tablesize, int key)
{
	logical active, found;
	int start, position, temp;

	active=vero;
	found = falso;
	start = key % tablesize;
	position =start;

   if (table[position]==key)
	{
		active = falso;
		found = vero;
		temp = table[position];
	}

	else
	{
		temp = table[position];
		table[position]=key;
	}

   while(active)
	{
		position =(position+1) % tablesize;
		if(table[position]==key)
		{
      	active = falso;
         if(position != start)
				found =vero;
  		}

  		else
   		if(table[position]==NULL)
    			active = falso;

   	table[start]=temp;
 	}

	return found;
}