/*	CS665 Analysis of Algorithms
	Lee Tze Meng
	Menu Driven Program that uses hash tables
	for indexing
	Graduation is Dec. 4th 1999....
*/

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include <time.h>
#include <curses.h>

const int MAX_SIZE = 997;

typedef struct node
{
	int value;
	struct node *next;
};

long noCollisions = 0;
long noComparisons = 0;

int func2(int k,int probe);
void chaining(float loadfactor);
void linear_probing(float loadfactor);

void main()
{
	float loadfactor;
	int query;

	cout << "\n1. Chaining\n2. Linear probing\n3. Double Hashing\n4. Quit\n" <<
	"\t\t\tSelection : ";
	cin >> query;
	switch(query)
	{
		case 1:
			cout << "Enter the load factor: ";
			cin >> loadfactor;
			chaining(loadfactor);
			break;
		case 2:
			cout << "Enter the load factor: ";
			cin >> loadfactor;
			linear_probing(loadfactor);
			break;
		case 3:
		case 4:
		default:
			break;
	}
}

//=========================================================================
// Using Chaining

void chaining(float loadfactor)
{
	int k;								//key
	int hashresult;					//result of the hash function (division)
	int i;								//loop counters
	int j;								//loop counters
	int Sucess = 0;					// No. of comparisons in a Success
											//	 search(total for 50 search)
	int Fail = 0;                 // No. of comparisons in an Unsuccess
											// search(total for 50 search)
	node *Array[MAX_SIZE],*temp;

		ifstream fin("data.dat");

		for(i=0;i<MAX_SIZE;i++)
			Array[i] = NULL;

		//read from file and store in the table

		for (i=0; i< int(loadfactor*MAX_SIZE);i++ )
		{
			fin >> k;
			hashresult = k % MAX_SIZE;
			if(Array[hashresult] != NULL)
			{
				//there is a collision, do your stuff
				noCollisions++;				//increment
			}
			temp = (node *)calloc(1,sizeof(node));
			temp->value = k;
			temp->next = Array[hashresult];
			Array[hashresult] = temp;
		}
		cout <<"The method used is Chaining\n";
		cout << "MAX_SIZE = " << MAX_SIZE <<
		"\nNo. of collisions = " << noCollisions << endl;

		// Searching for in range successiful keys.
 /*		for ( j=5; j<55; j++)
		{
			hashresult = j % MAX_SIZE;
			temp = Array[hashresult];
			Sucess++;		// for the last comparison it is not counted in the loop
			while (temp->value!=j && temp!= NULL)
			{
				Sucess++;
				temp = temp->next;

			}

		}
*/
		// Searching for in range successiful keys.
		// We need to make sure that the keys we are using already exists in the
		//	Cain
		fin.close();
		fin.open ("data.dat");				// Go to thebegining of the file

		// Read the first 50 elements form the input file
		for ( j=0; j<50; j++)
		{
			fin >> k;
			hashresult = k % MAX_SIZE;
			temp = Array[hashresult];
		//	Sucess++;		// for the last comparison it is not counted in the loop
			while (temp!= NULL &&temp->value!=j)
			{
				Sucess++;
				temp = temp->next;

			}

		}


		// Searching for out of range unsuccessiful keys.
		for ( j=2001; j<2051; j++)
		{
			hashresult = j % MAX_SIZE;
			temp = Array[hashresult];
			Fail++;		// for the last comparison it is not counted in the loop
			while ((temp!= NULL)&&(temp->value!=j) )
			{
				Fail++;
				temp = temp->next;

			}

		}

		cout << "The Average No of successiful searches = " << Sucess/50.0 <<
		"\nThe average No. of Unsuccessiful searches = " << Fail/50.0 << endl;

}


/////////////////////////////////////////////////////////////////////////////

void linear_probing(float loadfactor)
{
	int i,j,k,hashresult,Success=0,Fail=0;
	int lpArray[2][MAX_SIZE + 100],tempArray[898]; //the first column is to hold info
								//whether the second column is full or not
	int temprand;

	for(i = 0; i < MAX_SIZE;i++)
		lpArray[0][i] = lpArray[1][i] = 0;

	ifstream fin("data.dat");
	if (! fin.good())
	{
		cerr << "File not found";
		exit (0);
	}

	for(i=0;i<897;i++)
		fin >> tempArray[i];

	fin.close();
	fin.open("data.dat");
	if (! fin.good())
	{
		cerr << "File not found";
		exit (0);
	}

	for (i=0; i< (int)(loadfactor*MAX_SIZE);i++ )
	{
		fin >> k;
		j= -1;
		do
		{
			j++;
			hashresult = func2(k,j);
		}while(lpArray[0][hashresult] == 1);

		lpArray[0][hashresult] = 1;	//tell everybody that it is filled
		lpArray[1][hashresult] = k;	//fill it up!!!
		cout << "hashresult " << hashresult <<"\t";
		cout << lpArray[0][hashresult] << "  " << lpArray[1][hashresult] << endl;
	}

	///////sucessful searching starts here///////////

	// Read the first 50 elements form the input file
//	time_t t;

//	srand(0);//(unsigned) time(&t));
	srand(0);


	for ( j=0; j<50; j++)
	{
	        temprand= ((unsigned)rand())%(int)(loadfactor * MAX_SIZE);
	        k = tempArray[temprand];
		i = -1;
		
		do
		{
			i++;
			Success++;
			hashresult = func2(k,i);
			cout << "Success Key = " << k << "\tLocation  "<< temprand<<
			  "\tArray Val "<<lpArray[1][hashresult] << "\ti = "<<i<< endl;
		}while((lpArray[1][hashresult] != k) && (lpArray[0][hashresult] == 1));
	}
	/////////////////////UNSUCCESSFUL///////////////////
	// Searching for out of range unsuccessiful keys.
	for ( j=30001; j<30051; j++)
	{
		i = -1;
		do
		{
			i++;
			Fail++;
			hashresult = func2(j,i);
		}while((lpArray[1][hashresult] != j) && (lpArray[0][hashresult] == 1));
	}

	fin.close();
	cout << "The Average No of successful searches = " << Success/50.0
<<  "\nThe average No. of Unsuccessiful searches = " << Fail/50.0 <<endl;

}

int func1(int k)
{
	return k % MAX_SIZE;
}

int func2(int k,int probe)
{
	return ((func1(k) + probe) % MAX_SIZE);
}