#include <iostream>
#include <fstream>
using namespace std;
int aryi=0;
template <class T>
class Node{
public:
T data;
Node<T> * Next;
Node(){
data = aryi++;
Next = NULL;
}
};
template <class T>
class List{
public:
Node<T> * head;
List(){
head = new Node<T>;
}
void addnode(int & x){
Node<T> * cur = head;
if(cur==NULL){
//For first node
cur->data = x;
cur->Next = NULL;
}
else{
while(cur->Next != NULL){
cur = cur->Next;
}
//New Node Creation
Node<T> * NewNode = new Node<T>;
NewNode->data = x;
NewNode->Next = cur->Next;
cur->Next = NewNode;
}
}
void showdata(){
Node<T> * cur = head->Next;
while(cur!=NULL){
cout<<"--"<<cur->data;
cur=cur->Next;
}
}
};
int convertasc(string & word){
int asc = 0;
int total = 0; //FOR TOTAL THE WHOLE WORD IN ASCII
for(int i=0; i< (int)word.length(); i++){
asc = (int) word[i];
total += asc;
}
return total;
}
template <class T>
class OpenAddr{
T totsize, modin;
T * ary;
public:
OpenAddr(T modindex, T size){
ary = new T[modin];
modin=modindex;
totsize=size;
}
void createHash(string & word){
int total = convertasc(word);
int mod = total % modin;
ary[mod] = total;
}
void displayOpenAddr(){
for(int i=0; i<modin; i++){
cout<<"--"<<ary[i]<<"--\n";
}
}
void searchOpenAddr(string & word){
int total = convertasc(word);
int mod = total % modin;
if(ary[mod] == total){
cout<<"\nString :: "<<word<<" :: Index :: "<<mod;
return;
}else
cout<<"\n STRING NOT FOUND";
}
};
template <class T>
class SEPChain{
List<T> * ary;
T totsize, modin;
public:
SEPChain(T modindex, T size){
ary = new List<T>[modindex];
modin=modindex;
totsize=size;
}
void creatHash(string & word){
int total = convertasc(word);
int mod = total % modin;
ary[mod].addnode(total);
}
void displaySEPChain(){
for(int i=0; i<modin; i++){
Node<T> * curr = ary[i].head;
while(curr != NULL){
cout<<"--"<<curr->data;
curr = curr->Next;
}
cout<<"\n\n";
}
}
void serachSEPChain(string & word){
int total = convertasc(word);
int mod = total % modin;
Node<T> * curr = ary[mod].head->Next;
T index = 0;
while(curr != NULL){
if(curr->data == total){
cout<<"\n"<<"String :: "<<word<<" :: Index :: "<<mod<<" :: Chain Index ::"<<index;
return;
}
index++;
curr = curr->Next;
}
cout<<"\n String NOT FOUND\n";
}
};
int main(int argc, char **argv)
{
if(argc < 2){
cout<<"\n Please Enter a File Name:\n\n\n";
return 0;
}
argv++;
fstream input(*argv);
string word;
int count = 0, modindex;
cout<<"Your Input::->> ";
while(input>>word){
cout<<word<<" ";
count++;
}
cout<<"\n";
modindex= count * (0.75);
if(modindex < 1){
modindex = 1;
}
SEPChain<int> SEPC(modindex,count);
OpenAddr<int> OpenC(modindex,count);
cout<<"\nseparate chaining:\n";
fstream inp(*argv);
while(inp>>word){
SEPC.creatHash(word);
OpenC.createHash(word);
}
SEPC.displaySEPChain();
cout<<"\nOpen Addressing with Replacement:\n";
OpenC.displayOpenAddr();
cout<<"\nSearch Indexing of the string (both Sep. Chain & Open Addressing with Replacement:\n\n";
fstream in(*argv);
while(in>>word){
SEPC.serachSEPChain(word);
OpenC.searchOpenAddr(word);
cout<<"\n\n";
}
return 0;
}
