/*Read the value from the file , and then hash the value, then the hashed value put into the table of the desired position,
    if the position is full, remove the exsisting element and do its linear probing */

#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

void alpha_value();
void method(int size);
void function1(long long int capacity);
void function2(long long int capacity);
void function3(long long int capacity);

int main()
{
    alpha_value();

    return 0;
}

void alpha_value()
{
    double load_alpha;
	cout << "Enter Load Alpha (0.25/0.50/0.75): " << endl;
	cin >> load_alpha;


	int x;
	if (load_alpha == 0.25)
	{		x = 1; 	}
	if (load_alpha == 0.50)
	{		x = 2;	}
	if (load_alpha == 0.75)
	{		x = 3;	}

	switch (x) {
		case 1: //4000037
		    method(20);
		    break;

		case 2: //2000003
		    method(20);
		    break;

		case 3: //1333357
		    method(20);
		    break;
	}

}

void method(int size)
{
	int choice;
	cout << "\nEnter Your Choice:\n";
	cout << "1. Method1: the LIFO \n";
	cout << "2. Method2: Double hashing \n";
	cout << "3. Method3 \n";
	cin >> choice;

	switch (choice) {
		case 1:
			cout << " Your Choice is: " << choice << endl << endl;
			function1(size);
			break;

		case 2:
			cout << " Your Choice is: " << choice << endl << endl;
			function2(size);
			break;

		case 3:
			cout << " Your Choice is: " << choice << endl << endl;
			function3(size);
			break;
	}

}



void function1(long long int capacity)
{	int copy=capacity;
	int counter=1;
	//int stopper2=0;
	int collisions=0;
    long long int *myarray=new long long int[capacity]; //capacity is the size of the array

    for (int i = 0; i < capacity; i ++)
		 {   //Setting NULL Values
		      myarray[i] = -1;
		 }

    int long long temp=0;
    ifstream infile; //Reading the values from the file
	infile.open("sample.txt");

    while (infile >> temp) //while reading values from the file
    {	int long long final=temp;

    	if (temp <=0) //converting the negative values to positive
    		temp = -temp;

		//int stopper =0;
    	int i =1;
        int key = temp % capacity; //hash key
        cout << i << ": " << temp << " The Hash Key is: " << key << endl;

        long long int my_index=key;

        //If there is a pre-exiting value in the hashIndex
        if (myarray[my_index]!=-1)
        {

			int long long temp_value = myarray[my_index]; //copying the exsisting key into temp_value
            myarray[my_index]=final;
            cout << my_index << " : Value Isnt Empty Since " << temp_value << "  Exsits there\n";
            cout << my_index << " Position replaced by " << myarray[my_index] << endl;
            ++collisions;

            //find next free space for linear  probing
			cout << "Linear Probing for : " << temp_value;
            while(myarray[my_index] != -1)
            {	my_index++;
				if (my_index >= copy) //if my_index reaches the end of the array, and hence resetting it to start from the array
            			my_index=0;

            }
            cout << "Empty at Index: " << my_index;
            //storing the temp_value key to the empty space.
            myarray[my_index]=temp_value;
            cout << "\nStored at index " << my_index << " Value which was taken: " << temp_value << "  New Value in Array: "<<  myarray[my_index];
            cout << "Done with the loop at " << my_index << "\n";
            //cin >> stopper;
        }

        else //if the if condition doesnt run that means the array at hashIndex is initially empty hence we directly copy the value
            {myarray[my_index]=final;}

			cout << "\nNo collision";
            counter++;
			i++;
			cout << "\nDone Adding the element in the loop\n\n";
            //cin >> stopper2;
    }

    cout << "\nCollisions: " << collisions;
    infile.close();
}


void function2(long long int capacity)
{	int collisions=0;
	int i=1;
	int counter=1;

    long long int *myarray=new long long int[capacity]; //capacity is the size of the array which we will get from option 4

    for (long long int i = 0; i < capacity; i ++)//initializing the array values to -1
		 {      //NULL
                myarray[i] = -1;
         }

    int long long temp=0;
    ifstream infile;
	infile.open("sample.txt");
    while (infile >> temp) //while reading values from the file
    {	long long int final = temp;
        if (temp <=0) //converting the negative values to positive
    		temp = -temp;

		long long int key = temp % capacity; //hash key
        cout << i << ":   Value: " << final << "    Hash Key:" << key << endl;

        string a;
        long long int my_index2=key;
        //finding whether there is any collision
            if (myarray[my_index2] != -1)
                    a = "TRUE";
            else
                    a = "FALSE";



        //If there is a pre-exiting value in the hashIndex
        if (a == "TRUE")
        {	 cout << "\nCouldnt Store at Index: " << my_index2 << " Due to collision\n";
			 cout << "Value Exsisting at Collision: " << myarray[my_index2];
            int j=1; //counter
            int q=5; //prime number
            long long int hashIndex;
            string b="BTRUE";
            cout << "\nFinding the Empty Index to store value : " << final;
			while(b=="BTRUE")
            {
                hashIndex = ((key+j*(q-(temp%q)))%capacity);
                j++;

                if (myarray[hashIndex] == -1)
                    b = "BFALSE";
            }
            cout << "\nEmpty Index Found at : " << hashIndex;
            myarray[hashIndex]=final;
            cout << "\nStored Value: " << final << " at index " << hashIndex;
            //cin >> stopper;
        }
         else
		 	{myarray[my_index2]=final;
			 cout << "Stored: " << myarray[my_index2] << "    At Index: " << my_index2;
			}

            counter++;
			i++;
            cout << "\nDone with This loop\n\n";
            //cin >> stopper2;
    }
    infile.close();
    cout << "Collisions: " << collisions;
}



void function3(long long int capacity)
{
	int long long capacity_copy=capacity;
	int stopping;
	int collision=0;
    long long int copy =capacity;
	long long int *myarray=new long long int[capacity]; //capacity is the size of the array which we will get from option 4

    for (long long int i = 0; i < capacity; i ++)  //setting all the values to -1 initially
		 {      //NULL
                myarray[i]= -1;
		 }

    int long long temp=0;
    //Opening the file
    ifstream infile;
	infile.open("sample.txt");
	int counter =1;
	int check=0;

    while (infile >> temp) //while reading values from the file
    {
		int long long key = 0;
        int long long final =temp;
        if (temp <=0)
        	temp =-temp;
        int checker =0;

		do{
		key=temp % capacity; //hash key
        long long int my_index3 = key;
		cout << endl << counter << ": 	Value:" << final << "  	Key:" << key << endl;

        checker=0;

		//finding whether there is any collision before storing into the array
            string a= "FALSE";
			if (myarray[my_index3]!= -1)
                    { a = "TRUE";}
                else
                    { a= "FALSE"; }
			cout << "Collision Status(False-No Collision/True-Collision) :" << a << endl;
        	//cin >> stopping;
		int n=1000000; //total number of keys

        //If theis a pre-exiting value in the array at the index then
        if (a == "TRUE")
        {
			//copying the current value present at the index
			long long int value_b=0;
            value_b= myarray[my_index3]; //value copied
			int long long b= value_b%capacity_copy; //calculating the key
            cout << "Present Value of B: " << value_b << endl;
            cout << "Present Value of K: " << final << endl;

            //finding the distance
            long long int distance_b= (abs(b%n - my_index3))%n;
            long long int distance_k= (abs(key%n - my_index3))%n;
            cout << "Present Key in Array:" << b << "    Distance:" << distance_b << endl; //the present value
            cout << "Calculated Key Value for Temp: " << key << "    Distance:" << distance_k <<  endl; //the key value which we calculated previously
            ++collision;

            if (distance_b<=distance_k)//b is closer than a in terms of home position
            {
                my_index3=my_index3+1;
                if (my_index3 >= copy) //if the index is in the end of the loop
            			my_index3=0;
            	cout << "Incremented the index, heading back to LOOP\n";
            	//cin >> stopping;

            }
            else  //if b>k, we swap and find new position for b's key
            {   cout << "Swapping the values (b to k) \n";

				/*saving the value of original k into the array, since b was already
				copied in the variable b, so can copy it without losing the value*/
                myarray[my_index3]=final;
                cout << "K's Key :" << key << "    Array: " << myarray[my_index3] << endl;
                final=value_b; //copying b' value to k
                temp =final;
				cout << "K's New Value :" << final;
				my_index3++;
				if (my_index3 >= copy)
            			my_index3=0;
            	cout << "\nSwapped.\n";
            	//cin >> stopping;

            }

        }

        else //if the if condition doesnt run that means the array at hashIndex is initially empty hence we directly copy the value
            {	myarray[my_index3]=final; checker=1;}
		counter++;
        cout << "Value Stored at Index:" << my_index3 << "   Value:" << myarray[my_index3];
		cout << endl;

    }while (checker!=1);
}
	cout << "\nTotal Collisions: " << collision;
    system("PAUSE");
}