//**************************************
//     
// Name: An implementation of Hashing
//     
// Description:The purpose of this progr
//     am is to insert numbers into an hash arr
//     ay dynamically.
// 
//
// Inputs:Size of hash table and numbers
//     to be inserted are the inputs
//
// Returns:Program prints hash table and
//     number of probes for each number in orde
//     r to insert it into hash table. (Average
//     probe number is also printed)
//
//  
//     
//
//
//    
//    
// **************************************
//     

/*
	 
*/
#include "stdio.h"
#include "conio.h"
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
// defining booleans
#define true 1
#define false 0
// defining size of table, which is a pr
//     ime number
#define Prime 11
//***************************
// Prototypes
int HashIndex(int,int);
int HashKey(int, int);
void Initialization(void);
void Presedence(void);
void InsertKey(int,int);
int ComputeNextPotentialAddress(int,int,int);
int Try(int,int,int,int,int);
void InsertAccordingTo(int, int, int, int, int);
void WasteBrent(int);
void PrintHashArray(int,int);
int CalculateRetrieve(int,int);
//***************************
// Global Variables
int hash[15]; // hash table
int pres[2][16]; // array for presedence
int n;// size of table (required for hash and key functions)
int needcheck=true; // a boolean
//***********************************
// THIS FUNCTION PRINTS THE HASH ARRAY W
//     ITH NUMBER OF RETRIEVES
void PrintHashArray(int usernumarray[],int numbercounter)


    {
    int totalprobe=0;
    int probe;
    int i;
    int counter=0;
    for(i=0;i<n;i++)


        {


            	if(hash[i]!=-1){
            		probe=CalculateRetrieve(hash[i],n);
            		printf("\n|%d\t%d\t|\tĪ\tprobe = %d",i,hash[i],probe);
            		totalprobe+=probe;
            		counter++;
            	 }
            else
            		printf("\n|%d\t^\t|\tĪ\tprobe = N/A",i);
        }
        printf("\nAverage Retrieve Number: %f",float (totalprobe)/counter);
        printf("\n\n");
    }
    // THIS FUNCTION FINDS THE NUMBER OF RET
    //     RIEVES WITH A GIVEN NUMBER AND SIZE OF H
    //     ASH ARRAY
    int CalculateRetrieve(int num,int n)


        {
        int index,next,retrieve=1;
        index=HashIndex(num,n);
        next=HashKey(num,n);


            while(hash[index]!=num){
            	 index=(index+next)%n;
            	 retrieve++;
        }
        return retrieve;
    }
    // THIS FUNCTION RUNS WHEN THERE IS NO P
    //     OSSIBLE WAY TO INSERT NUMBER BY BRENT HA
    //     SHING
    // IT PUTS THE NUMBER IN THE ARRAY ACCOR
    //     DING TO FIRST RETRIEVAL
    void WasteBrent(int number)


        {
        int num[3],index;
        num[0]=number;
        num[1]=HashIndex(number,n);
        num[2]=HashKey(number,n);
        index=num[1];


            while(hash[index]!=-1){
            	 index=(index+num[2])%n;
        }
        hash[index]=num[0];
    }
    // THIS FUNCTION INSERTS THE NUMBER ACCO
    //     RDING TO;
    /*
    i			=	i pair of presedence array
    j			= 	j pair of presedence array
    num		= 	number to be inserted
    index	= hash index of the number
    key		=	increment key
    */
    void InsertAccordingTo(int i, int j, int num, int index, int key)


        {
        int m;
        int newnum[3],newindex;


            for(m=1;m<i;m++){
            		index=(index+key)%n;
        }
        newnum[0]=hash[index];
        newnum[2]=HashKey(newnum[0],n);
        hash[index]=num;


            for(m=0;m<j;m++){
            	index=(index+newnum[2])%n;
        }
        hash[index]=newnum[0];
    }
    // IT TRIES TO INSERT NUMBER INTO HASH T
    //     ABLE ACCORDING TO i AND j VALUES
    // IF IT CAN, IT RETURNS 1 ELSE -1


        int Try(int i, int j, int num, int index, int key){
        int m;
        int newnum[3],newindex;
        int returnval;


            if(needcheck==true){


                if((i==1)&&(j==1)){
                newnum[0]=hash[index];
                newnum[1]=HashIndex(newnum[0],n);
                newnum[2]=HashKey(newnum[0],n);
                newindex=(newnum[1]+newnum[2])%n;
                if((hash[newindex]==-1)&&(newindex!=newnum[1]))
                	returnval=1;
                else
                	returnval=0;
            }


                else{


                    		for(m=1;m<i;m++){
                    			index=(index+key)%n;
                    		}
                    		newnum[0]=hash[index];
                    		newnum[1]=HashIndex(newnum[0],n);
                    		newnum[2]=HashKey(newnum[0],n);
                    		newindex=index;


                        		for(m=1;m<=j;m++){
                        			newindex=(newindex+newnum[2])%n;
                        		}
                        		if((hash[newindex]!=-1)||(newindex==index))
                        			returnval=-1;
                        		else returnval=1;
                        	}
                    }


                        else{
                        returnval=-1;
                    }
                    return returnval;
                }
                // THIS FUNCTION RUNS IF THE NUMBER CANN
                //     OT BE INSERTED AT ONE PROBE
                // IT CALCULATES THE NUMBER OF RETRIEVAL
                //     S ACCORDING TO STATIC HASHING


                    int ComputeNextPotentialAddress(int num, int index, int key){
                    int returnval=1;
                    int storedindex=index;


                        if (key==0){
                        	returnval=-1;
                    }


                        else{


                            	 while(hash[index]>=0){
                            		index=(index+key)%n;
                            		 if(index==storedindex)


                                		 {
                                			printf("Table is Full");
                                			getch();
                                			exit(0);
                                		 }
                                		 if(hash[index]==num)


                                    		 {
                                    			printf("Duplicate Record");
                                    			getch();
                                    			exit(0);
                                    		 }
                                    		returnval++;
                                    	 }
                                }
                                return returnval;
                            }
                            // INSERTS THE num INTO index INDEX OF H
                            //     ASH TABLE
                            // <%!--"NOT NECESSARY TO WRITE THIS 
                            //     CODE BUT ..."--%>
                            void InsertKey(int num, int index)


                                {
                                hash[index]=num;
                            }
                            // CALCULATES THE HASH INDEX OF NUMBER
                            int HashIndex(int num,int prime){ // number and p prime number
                            	int returnval;
                            	returnval=num%prime;
                            	return returnval;
                        }
                        // CALCULATES THE INCREMENT KEY OF NUMBE
                        //     R
                        int HashKey(int num, int prime){ // number and p prime number
                        int returnval;
                        returnval=((num/prime)%prime);
                        return returnval;
                    }
                    // CALCULATE PRESEDENCE ARRAY FOR BRENTS
                    //     HASHING
                    // 1-1, 1-2, 2-1, 1-3, 2-2, 3-1 .....


                        void Presedence(void){
                        int arrindex=0;
                        for(int k=2; k<7; k++)
                        	 for(int l=1; l<k; l++)


                            	 {
                            		 pres[0][arrindex]=l;
                            		 pres[1][arrindex]=k-l;
                            		 arrindex++;
                            	 }
                        }
                        // MAKE ARRAYS -1, (-1 IS A CONTROL NUMB
                        //     ER)


                            void Initialization(int arr[]){
                            int count;


                                for(count=0;count<15;count++){
                                hash[count]=-1;
                                arr[count]=-1;
                            }
                        }
                        // MAIN FUNCTION


                            void main(void){
                            int ok=true, usernum[3]; // usernum[0]=number, usernum[1]=hashindex usernum[2]=key
                            int s; // first probe
                            int i,j; // usual variables
                            int isfound,totalProbe=0,opdone=false,count=0;
                            char numstr[5];
                            int numbers[15];
                            textmode(C80);
                            textbackground(3);
                            textcolor(0);
                            clrscr();
                            Initialization(numbers);
                            Presedence();
                            n=Prime;
                            isfound=0;
                            printf("Enter size of hash table : ");
                            scanf("%d",&n);


                                while(ok){
                                	printf("Enter number : ");
                                	scanf("%s",numstr);
                                	if(isalpha(numstr[0])){ // exit command
                                	 ok=0;
                                	}
                                	else{ // brent operation starts
                                	 usernum[0]=atoi(numstr);// number
                                	 usernum[1]=HashIndex(usernum[0],n); // hash index
                                	 usernum[2]=HashKey(usernum[0],n); // hash key
                                	 numbers[count]=usernum[0];
                                	 printf("Hash Index = %d, Hash Increment Key= %d\n",usernum[1],usernum[2]);
                                	 count++;
                                	 if(hash[usernum[1]]<0){ // if home address is empty
                                		InsertKey(usernum[0],usernum[1]); // insert number into hash table
                                	 }
                                	 else{ // if home address is not empty


                                    	 if(hash[usernum[1]]==usernum[0]){
                                    		 printf("Duplicate number! Press Any key to exit");
                                    		 getch();
                                    		 exit(0);
                                    	 }
                                    	 s=ComputeNextPotentialAddress(usernum[0],usernum[1],usernum[2]);


                                        		 if (s<0){
                                        			printf("Increment key is zero, infinite loop! Press any key to exit");
                                        			getch();
                                        			exit(0);
                                        		 }


                                            		 else{
                                            			 i=0;
                                            				needcheck=true;
                                            				opdone=false;


                                                				for(i=0;i<15;i++){


                                                    					if(Try(pres[0][i],pres[1][i],usernum[0],usernum[1],usernum[2])==1){
                                                    					 needcheck=false;


                                                        						if((needcheck==false)&&(opdone==false)){


                                                            						 if ((pres[0][i]+pres[1][i])<s){
                                                            								
                                                            InsertAccordingTo(pres[0][i],pres[1][i],usernum[0],usernum[1],usernum[2]);
                                                            						 }
                                                            					if((needcheck==true)&&(opdone==false))


                                                                						 {
                                                                							 WasteBrent(usernum[0]);
                                                                						 }
                                                                						 opdone=true;
                                                                						}
                                                                					}
                                                                				}
                                                                		 }
                                                                	 }
                                                                	 PrintHashArray(numbers,count);
                                                                	}
                                                            }
                                                            getch();