#include <cstring>
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <math.h>
#include<string>
#include <list>
using namespace std;
ifstream to_compress ("d:\\test.txt");
string a;
string b;
float A;
char r;
list<string> text;
//ofstream out("d:\\test2.txt");
int hash_function(string word, int m)
{
int sum=0;
for(int k=0;k<word.size();k=k+1)
{sum=sum+(((int)word[k])*pow(33,k));
}
return m*((sum*A)-(int)(sum*A));
}
void quad_prob(int index, int m, string hash_table[], string a)
{
int q=1;
while(!hash_table[(index+(q*q))%m].empty())
{q=q+1;}
hash_table[((index+(q*q)))%m]=a;
cout<<"placed "<<a<<" at "<<(index+(q*q))%m<<"Advanced by "<<q*q<<endl;
}
void initialize(int n, string hash_table[], int size)
{
char c='A';
a.clear();
while(c<='Z')
{
a=c;
if(hash_table[hash_function(a,size)].empty())
{hash_table[hash_function(a,size)]=a;
}
else
{quad_prob(hash_function(a,size),size,hash_table,a);
}
n=n+1;
a.clear();
c++;
}
c='a';
while(c<='z')
{
a=c;
if(hash_table[hash_function(a,size)].empty())
{hash_table[hash_function(a,size)]=a;}
else
{quad_prob(hash_function(a,size),size, hash_table,a);
}
a.clear();
c++;
n=n+1;
}
a=' ';
hash_table[hash_function(a,size)]=a;
n=n+1;
a='.';
hash_table[hash_function(a,size)]=a;
n=n+1;
int total=0;
}
int search(string hash_table[], string a, int size, int index)
{ int p=0;
while(hash_table[index+(p*p)]!=a)
{if(hash_table[index+(p*p)].empty())
{return -1;}
p=p+1;
}
return index+(p*p);
}
void compress(string hash_table[], int size)
{
while(to_compress.good() and to_compress.is_open())
{
r=to_compress.get();
a=r;
while(search(hash_table,a,size,hash_function(a,size))>=0)
{
b=a;
a=a+r;
r=to_compress.get();
}
hash_table[search(hash_table,b,size,hash_function(b,size))]=b;
a.clear();
b.clear();
}
}
int main()
{
A=(sqrt(5)-1)/2;
int size=256;
string hash_table[size];
int n=0; //number of elements entered in 'hash_table' array.
initialize(n, hash_table, size);
compress(hash_table,size);
/* for(int i=0;i<size;i=i+1)
{if(!hash_table[i].empty())
{cout<<"hash_table["<<i<<"]="<<hash_table[i]<<endl;}
} */
}