Stuff

#include "utility.h"

#include "key.h"

#include <list>

#include <algorithm>

#include "iomanip"

using namespace std;



int FlipDigits(int i);

int mod (int x, int hashtablesize);

double Hash_Search(int a, int b, list<Key> hashtable[]);

void Hash_LoadUp(int a, int b, list<Key> hashtable[]);



list<Key> hashtable[97];	

list<Key>::iterator current;

Key tempkey;



int temp;

int Hash_Table[750];

int hashtablesize=97;



const int HASHTABLE_SIZE1 = 97;

const int HASHTABLE_SIZE2 = 241;

double Sucessful_comparisons = 0;

double Unsucessful_comparisons = 0;



int FlipDigits(int value) 

{ 

	int array[4];

	array[0] = value % 10;

	array[1] = ((value - array[0]) / 10) % 10;

	array[2] = (((value - (array[0] + array[1] * 10)) / 100) % 10);

	array[3] = (value-(array[0] + array[1] * 10 + array[2] * 100)) / 1000;

	return ((array[0] * 100) + (array[1] * 1000) + (array[2]) + (array[3] * 10));

}



int mod(int x, int hashtablesize)

{

	return (x % hashtablesize);

}



double Hash_Search(int a, int b, list<Key> hashtable[])

{

	for (int x=a; x<b; x++)  //search for the defined values

	{

		temp = FlipDigits(Hash_Table[x]);

		temp = mod(temp, 97);

		int i=0;



		if(hashtable[temp].empty())

		{

	

		}

		else

		{

			current = hashtable[temp].begin();

			while(current!=hashtable[temp].end())

			{

				if (*current == Hash_Table[x])

				{

					break;

				}

				i++;

				current++;

			}

		}

	}

	return (Key::comparisons);

}



void Hash_LoadUp(int a, int b, list<Key> hashtable[])

{

	for(int i=a; i<b; i++)  //load up the hashtable to load factor specified by a and b

	{

		tempkey = Hash_Table[i];

		temp = FlipDigits(tempkey.the_key());

		temp = mod(temp, hashtablesize);

		hashtable[temp].push_front(tempkey);

	}

}



int main()

{

	cout.setf(ios::fixed);   //presision stuff

	cout.setf(ios::showpoint);

	cout.precision(3);



	char file[] = "lab6a.txt";

	ifstream File_input;

	File_input.open(file);



	for(int i=0; i<300; i++)  //load up all the values in the file

	{

		File_input>>Hash_Table[i];

	}

	File_input.close();



	cout<<"Searching hash table size of 97, and with values from lab6a.txt" << endl;

	cout<<"Unsuccessful searches with 100 values from end of 300 value list" << endl;

	cout<<"Successful searches with first 20, 50, 100, 200 elements" << endl << endl;

	Key::comparisons=0;    



	Hash_LoadUp(0,20,hashtable);  //hash size 20

	Key::comparisons=0;   





	cout<<"loadfactor --- unsuccessful---successful\n";\

	cout<<"20(.2)"  <<setw(15) ;         

	cout<<Hash_Search(200, 300, hashtable) / 100 <<setw(15);

	Key::comparisons=0;   

	cout<<Hash_Search(0, 20, hashtable) / 20 <<endl;

	Key::comparisons=0;   



	Hash_LoadUp(20, 50, hashtable);   //hash size50

	Key::comparisons=0;   

	cout<<"50(.5)"  <<setw(15) ;  

	cout<<Hash_Search(200, 300, hashtable) / 100<<setw(15);

	Key::comparisons=0;   

	cout<<Hash_Search(0, 50, hashtable) / 50 <<endl;

	Key::comparisons=0;   



	Hash_LoadUp(50, 100, hashtable); //hash size 100

	Key::comparisons=0;   

	cout<<"100(1)"  <<setw(15) ;  

	cout<<Hash_Search(200, 300, hashtable) / 100<<setw(15);

	Key::comparisons=0;   

	cout<<Hash_Search(0, 100, hashtable) / 100 <<endl;

	Key::comparisons=0;   



	Hash_LoadUp(100, 200, hashtable); //hash size 200

	cout<<"200(2)"  <<setw(15) ;  

	Key::comparisons=0;   

	cout<<Hash_Search(200, 300, hashtable) / 100<<setw(15);

	Key::comparisons=0;   

	cout<<Hash_Search(0, 200, hashtable) / 200 <<endl;

	Key::comparisons=0;   



//############################################################################################################################

	

	cout<< endl;

	cout<<"Repeating with hash table size of 241, and with values from lab6b.txt" << endl;

	cout<<"Unsuccessful searches with 250 values from end of 750 value list" << endl;

	cout<<"Successful searches with first 50, 125, 250, 500 elements" << endl << endl;



	for (int a=0; a<97; a++)//clear out the hash table for next run

	hashtable[a].clear();



	hashtablesize=241;

	list<Key> hashtable2[241];	 //new bigger hash table



	File_input.open("lab6b.txt");

	for(int i=0; i<750; i++)  //load up all the values in the file

	{

		File_input>>Hash_Table[i];

	}

	File_input.close();





	Key::comparisons=0;    

	



	Hash_LoadUp(0,50, hashtable2);  //hash tablesize 50





	cout<<"loadfactor --- unsuccessful---successful\n";\

	cout<<setw(5)<<" 50(.2)  "  <<setw(15) ;         

	cout<<Hash_Search(500, 750, hashtable2) / 250  <<setw(15) ;

	Key::comparisons=0;   

	cout<<Hash_Search(0, 50, hashtable2) / 50  <<endl ;

	Key::comparisons=0;   





	Hash_LoadUp(50,125, hashtable2);  //hash table size 125



	cout<<setw(10)<<"125(.5)  "<<setw(15) ;

	cout<<Hash_Search(500, 750, hashtable2) / 250 <<setw(15) ;

	Key::comparisons=0;   

	cout<<Hash_Search(0, 125, hashtable2) / 125 <<endl;

	Key::comparisons=0;   



	Hash_LoadUp(125,250, hashtable2);  //hash table size 250



	cout<<setw(10)<<"250(1)"<<setw(15) ;

	cout<<Hash_Search(500, 750, hashtable2) / 250 <<setw(15) ;

	Key::comparisons=0;   

	cout<<Hash_Search(0, 250, hashtable2) / 250 <<endl;

	Key::comparisons=0;   



	Hash_LoadUp(250,500, hashtable2);  //hash table size 500



	cout<<setw(10)<<"500(2)"<<setw(15) ;

	cout<<Hash_Search(500, 750, hashtable2) / 250 <<setw(15) ;

	Key::comparisons=0;   

	cout<<Hash_Search(0, 500, hashtable2) / 500  <<endl;

	Key::comparisons=0;   



	return 0;

}