#include "utility.h"
#include "key.h"
#include <list>
#include <algorithm>
int flipdigits2(int i);
int mod (int x, int hashtablesize);
int search100(int a, int b);
void loadhash(int a, int b);
list<Key> hashtable[97];
list<Key>::iterator current;
int temp;
Key temp2, temp3, tempkey;
int searcharr[300];
int main()
{
ifstream fin;
fin.open("lab6a.txt");
for(int i=0; i<300; i++) //load up all the values in the file
{
fin>>searcharr[i];
}
fin.close();
Key::comparisons=0;
loadhash(0,20);
cout<<search100(200, 300);
cout<<"compares\n";
cout<<"THIS IS THE AVERAGE UNSUCCESSFUL SEARCH WORK\n";
Key::comparisons=0;
cout<<search100(0, 20);
cout<<"compares\n";
cout<<"THIS IS THE AVERAGE successful SEARCH WORK\n";
Key::comparisons=0;
loadhash(20, 50);
cout<<search100(200, 300);
cout<<"compares\n";
cout<<"THIS IS THE AVERAGE UNsuccessful SEARCH WORK\n";
Key::comparisons=0;
cout<<search100(0, 50);
cout<<"compares\n";
cout<<"THIS IS THE AVERAGE successful SEARCH WORK\n";
Key::comparisons=0;
loadhash(50, 100);
cout<<search100(200, 300);
cout<<"compares\n";
cout<<"THIS IS THE AVERAGE UNsuccessful SEARCH WORK\n";
Key::comparisons=0;
cout<<search100(0, 100);
cout<<"compares\n";
cout<<"THIS IS THE AVERAGE successful SEARCH WORK\n";
Key::comparisons=0;
loadhash(100, 200);
cout<<search100(200, 300);
cout<<"compares\n";
cout<<"THIS IS THE AVERAGE UNsuccessful SEARCH WORK\n";
Key::comparisons=0;
cout<<search100(0, 100);
cout<<"compares\n";
cout<<"THIS IS THE AVERAGE successful SEARCH WORK\n";
return 0;
}
int flipdigits2(int i)
{
char a[5];
if (i<10) sprintf(a, "000%d", i); //I wish I could find a prettier way then if statements.
else if (i<100) sprintf(a, "00%d", i);
else if (i<1000) sprintf(a, "0%d", i);
else sprintf(a, "%d", i);
//i = atoi(data[0]) + atoi(data[1])*10 + (atoi(data[2])*10 + atoi(data[3]))*100; //Don't work.
i = (a[0]-'0')*10 + (a[1]-'0') + ((a[2]-'0')*10 + (a[3]-'0'))*100;
return i;
}
int mod(int x, int hashtablesize)
{
return (x % hashtablesize);
}
int search100(int a, int b)
{
for (int x=a; x<b; x++) //search for the defined values
{
temp = flipdigits2(searcharr[x]);
temp = mod(temp, 97);
//cout<<"searching hash position : " <<temp <<"for value " <<searcharr[x] <<endl;
int i=0;
if (hashtable[temp].empty())
{
//cout<<"list is empty!\n";
}
else
{
current = hashtable[temp].begin();
while(current !=hashtable[temp].end())
{
if (*current == searcharr[x])
{
//cout<<"success, found at position " <<i <<endl;
break;
}
else
{
//cout<<"not found\n";
}
i++;
current++;
}
}
}
return (Key::comparisons);
}
void loadhash(int a, int b)
{
for(int i=a; i<b; i++) //load up the hashtable to load factor specified by a and b
{
tempkey = searcharr[i];
//cout<<"the value to be inserted is " <<tempkey.the_key() <<endl;
temp=flipdigits2(tempkey.the_key());
//cout<<"flipped: " <<temp <<endl;
temp = mod(temp, 97);
//cout<<"hashing to " <<temp <<endl;
hashtable[temp].push_front(tempkey);
//cout<<"value inserted ";
//cout<<hashtable[temp].front().the_key();
//cout<<endl;
}
}