//Program to test hash functions for social security numbers

#include <iostream>
#include <cstring>
#include <fstream>
#include <ctime>

using namespace std;

long seedGen() {
	//seedGen function will generate a random number 
	//seed that is more random than the clock.
	//Must include the time.h library header file
	srand(time(NULL)); //Use the clock to seed the RNG
	long newseed = rand();	//1st random number
	newseed = rand();		//2nd random number
	newseed = rand();		//3rd random number
	newseed = newseed*newseed;	//square 3rd rand num
					//and use the result for the new seed
	//Use the new seed to get better random numbers
	return newseed;
}//end seedGen

long rand2() {
	//rand2 is a random number generator that returns an integer
	//between 0 and 2^30-1 (30 bit)
	//It is based on the C++ rand function that returns an integer 
	//between 0 and 32767 (15 bit)
	return rand()+32768*rand();
}//end rand2

long hash1(long SSN, long HTSize) {
	return SSN % HTSize-1;
}//end hash1


//Function to generate random SSNs
void genSSNs(long SSNs [], unsigned long numSSNs) {
	srand(seedGen());
	long maxRand = 999999999;
	for (int i = 0; i < numSSNs; i++) {
		long nextRand = maxRand*(rand2()/1073741823.0);
		//cout << nextRand << endl;
		SSNs[i]=nextRand;
	}//end for
}//end function

//Function to search overflow table

int main() {
	const float defLoadFactor=.5;
	char goAgain='Y'; unsigned long numSSNs; 
	float loadFactor = defLoadFactor;

  //Program to store SSNs using hashing
  //Intro
	cout << "This program will generate random SSNs, store and retrieve them";
	cout <<"using hashing" << endl << endl;
	while (goAgain=='Y') {
  //while user wants to go again
	//ask user for number of SSNs
		cout << "Enter number of SSNs to store. ";
		cin >> numSSNs;
	//Ask user for load factor
	   //load factor is ratio of number of items to be stored in hash table
	   //divided by number of slots in hash table
		cout <<"Enter load factor (>0 and < 1 or use 0 for default) ";
		cin >> loadFactor;
		if (loadFactor==0) loadFactor=defLoadFactor;
		cout << "Number of SSNs = " << numSSNs << endl;
		cout << "Load Factor = " << loadFactor << endl;
	//Create an array to hold SSNs generated
		long* SSNs = new long[numSSNs];
	//Load SSN array with randomly generated SSNs
		genSSNs(SSNs, numSSNs);
	//Create hash table array, HT
		long HTSize = numSSNs/loadFactor;
		long* HT = new long[HTSize];
	//Create overflow table
	long numLookups=0;
	//for each SSN load into hash table
	for (int i = 0; i<numSSNs; i++) {
		//  Load next SSN from SSN array into hash table
		HT[hash1(SSNs[i], HTSize)] = SSNs[i];
	}//end for
	//start clock
	clock_t startTime = clock();	//start the timer
	//for each SSN
	long collisions = 0;
	for (i=0; i<numSSNs; i++) {
		//Look up ith SSN from SSN table in HT
		if (HT[hash1(SSNs[i], HTSize)] != SSNs[i]) {
			collisions++;
		};
		//acumulate total lookups
	}//end for
	//stop clock and get time diff.
	clock_t endTime = clock();	//start the timer
	float elapsedTime = endTime - startTime;
	//Report average number of lookups ((total SSNs)/(total lookups))
	cout << "Elapsed Time = " << elapsedTime/CLOCKS_PER_SEC << endl;
	cout << "# of collisions = " << collisions << endl;
	//ask user if user wants another run
		cout << "Do you want to run program again (Y/N)? ";
		cin >> goAgain;
		goAgain = toupper(goAgain);
	};//end while
	return 0;
}//end main