#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
 
int* createHashTable(void);
void getData(void);
void formatting(void);
int insertData(int);
float chkLoadFactor(int, int);
int collision_LinearProbing(int, int,int);
int generateKey(int);
void rehashing(void);
 
#define dataSize 15
#define empty -1
#define fail 0
#define success 1
 
int dataArray[dataSize];
int hashSize = 5;
int* head;
int* cur;
 
void main(void)
{
       int count, status;
       int filledSpaces = 0;
       float loadFactor = 0;
       clrscr();
       formatting();
       getData();
       head = createHashTable();
       for( count = 0; count < dataSize ; count++)
       {
		if(loadFactor > 0.5)
			rehashing();
	       status =	insertData(dataArray[count]);
	       if(status == success)
			filledSpaces++;
	       loadFactor = chkLoadFactor(status, filledSpaces);
 
	       if(loadFactor <= 0.5)
			printf("LF aftr %d is = %f\t", dataArray[count], loadFactor);
 
	       if(status == fail)
			printf("\nNo room left for  %d\n", dataArray[count]);
       }
       cur = head;
       printf("\n\nHash Table content = [");
       for(count = 0; count < hashSize ; count++)
       {
		printf("%d, ", *cur);
		cur++;
       }
       printf("\b\b]");
       getch();
}
 
int* createHashTable(void)
{
	int i;
 
/********************** Allocating Memory for Hash Table *********************/
 
	head = (int*)malloc(sizeof(hashSize*2));
	cur = head;
 
/********************** Initialize HashTable *********************************/
 
	for( i = 0; i <=hashSize; i++)
	{
		*cur = empty;
		cur++;
	}
	cur = head;
	return(head);
}
 
void getData(void)
{
	int i;
	randomize();
	printf("\n");
	printf("Data[]={");
	for(i =0; i < dataSize; i++)
	{
		dataArray[i] = random(50);
		printf("%d,", dataArray[i]);
	}
	printf("\b}\n\n");
}
 
void formatting(void)
{
	int i;
	printf("\n");
	for(i =0; i<=79 ; i++)
		printf("*");
 
	printf("\n......... Prgogram title\t\t# Hash Table");
	printf("\n......... Created by\t\t        # Romasa Qasim");
	printf("\n......... Description\t\t 	# Creation of Hash Table, generation of,");
	printf("\t\t\t\t\t  Key, Insertion, Searching and Deletion");
	printf("\t\t\t\t\t  of data in the Hash Table\n");
 
	for( i =0; i<=79 ; i++)
		printf("*");
}
 
int insertData(int data)
{
	int hashIndex,count = 0;
	hashIndex = generateKey(data);
	if( *(head+hashIndex) == empty)
	{
		*(head+hashIndex) = data;
		return(success);
	}
 
	else
		return(collision_LinearProbing((++hashIndex%hashSize), count, data));
 
}
 
float chkLoadFactor(int status, int filledSpaces)
{
	float loadFactor;
	if (status == success)
	{
		loadFactor = filledSpaces / (float)hashSize;
		return(loadFactor);
	}
	else
		return(1);
}
 
 
int collision_LinearProbing(int hashIndex, int count, int data)
{
	if(count == hashSize)
		return(fail);
 
	 if (*(head+hashIndex) == empty)
	 {
		*(head+hashIndex) = data;
		return(success);
	 }
	 else
	 {
		collision_LinearProbing((++hashIndex % hashSize), ++count, data);
	 }
 
}
 
int generateKey(int data)
{
	int key;
	key = data % hashSize;
	return(key);
}
 
void rehashing(void)
{
	int count;
	int status;
	hashSize = hashSize * 2;
	head = (int*)realloc(head, sizeof(hashSize*2));
 
	for( count = 0; count <hashSize; count++)
	{
		*(head+count) = -1;
	}
	for(count = 0; count < dataSize; count++)
	{
		status = insertData(dataArray[count]);
	}
}