For the following C++ code, please do the following... Justification for selecte
ID: 3825901 • Letter: F
Question
For the following C++ code, please do the following...Justification for selected algorithms.
Discussion of the time complexity of searching and deleting algorithms in terms
of Big O notation.
A discussion of the memory efficiency of the used algorithms.
--------------------------- Code--------------------------------------------
#include<iostream>
#include<string>
#include<fstream>
#include <iomanip>
#include <cassert>
using namespace std;
class StateData
{
private:
string myStateName;
string myStateCap;
int myStateUNum;
int myStateJYear;
int myStateAra;
public:
StateData(string myName1 = " ", string capN1 = " ", int uNum1 = 0, int yrN1 = 0, int areaN1 = 0)
{
myStateName = myName1;
myStateCap = capN1;
myStateUNum = uNum1;
myStateJYear = yrN1;
myStateAra = areaN1;
}
string getMyStateName()
{
return myStateName;
}
void setMyStateName(string n)
{
myStateName = n;
}
string getMyStateCap()
{
return myStateCap;
}
void setMyStateCap(string c)
{
myStateCap = c;
}
int getMyStateUNum()
{
return myStateUNum;
}
void setMyStateUNum(int n)
{
myStateUNum = n;
}
int getMyStateJYear()
{
return myStateJYear;
}
void setMyStateJYear(int y)
{
myStateJYear = y;
}
int getMyStateArea()
{
return myStateAra;
}
void setArea(int aa)
{
myStateAra = aa;
}
friend ostream& operator<<(ostream& myOut, StateData& myStateInfo)
{
if (myStateInfo.getMyStateArea() > 0)
{
myOut << myStateInfo.getMyStateName() << " , ";
myOut << myStateInfo.getMyStateCap() << " , ";
myOut << myStateInfo.getMyStateJYear() << ", ";
myOut << myStateInfo.getMyStateUNum() << " , ";
myOut << myStateInfo.getMyStateArea();
}
return myOut;
}
friend istream& operator>>(istream& myIn, StateData& myStateInfo)
{
getline(myIn, myStateInfo.myStateName);
getline(myIn, myStateInfo.myStateCap);
myIn >> myStateInfo.myStateAra >> myStateInfo.myStateJYear >> myStateInfo.myStateUNum;
char myChh;
myIn.get(myChh);
return myIn;
}
StateData& operator=(const StateData& otherStateInfo)
{
myStateName = otherStateInfo.myStateName;
myStateCap = otherStateInfo.myStateCap;
myStateUNum = otherStateInfo.myStateUNum;
myStateJYear = otherStateInfo.myStateJYear;
myStateAra = otherStateInfo.myStateAra;
return *this;
}
//operators overloading
bool operator!=(const StateData& otherStateInfo) const
{
return myStateName != otherStateInfo.myStateName;
}
bool operator==(const StateData& otherStateInfo) const
{
return myStateName == otherStateInfo.myStateName;
}
bool operator>(const StateData& otherStateInfo) const
{
return myStateName > otherStateInfo.myStateName;
}
bool operator>=(const StateData& otherStateInfo) const
{
return myStateName >= otherStateInfo.myStateName;
}
bool operator<(const StateData& otherStateInfo) const
{
return myStateName < otherStateInfo.myStateName;
}
bool operator<=(const StateData& otherStateInfo) const
{
return myStateName <= otherStateInfo.myStateName;
}
};
template <class infoType>
class STATEHASHTABLE
{
private:
infoType *MYHASHTABLE;
int *itemStatus;
int myHashLen;
int myTableSize;
public:
STATEHASHTABLE(int myHashSze= 101)
{
MYHASHTABLE = new infoType[myHashSze];
itemStatus = new int[myHashSze];
for (int kk = 0; kk < myHashSze; kk++) {
itemStatus[kk] = 0;
myTableSize = myHashSze;
myHashLen = 0;
}
}
~STATEHASHTABLE()
{
delete[] MYHASHTABLE;
delete[] itemStatus;
}
int hashFunc(string myStateName);
void displayMystateHashTable() const;
void InsertMyState(int myHashIndx, const infoType& myStateRec);
void getMyState(int myHashIndx, infoType& myStateRec) const;
void searchState(int& myHashIndx, string stateName, bool& myItemFound) const;
bool checkStates(int myHashIndx, const infoType& myStateRec) const;
void clearMyStateInfo(int& myHashIndx, string stateName, bool& myItemFound);
};
template <class infoType>
int STATEHASHTABLE<infoType>::hashFunc(string myStateName)
{
int aa, myHSum;
int len;
aa = 0;
myHSum = 0;
len = myStateName.length();
for (int k = 0; k < 15 - len; k++)
myStateName = myStateName + ' ';
for (int k = 0; k < 5; k++)
{
myHSum = myHSum + static_cast<int>(myStateName[aa]) * 128 * 128
+ static_cast<int>(myStateName[aa + 1]) * 128
+ static_cast<int>(myStateName[aa + 2]);
aa = aa + 3;
}
return myHSum % myTableSize;
}
template <class infoType>
void STATEHASHTABLE<infoType>::InsertMyState(int myHashIndx, const infoType& myStateRec)
{
int incCntt=1;
int myInc=1;
while(itemStatus[myHashIndx] == 1 && incCntt < myTableSize / 2)
{
myHashIndx = (myHashIndx + myInc ) % myTableSize;
myInc = myInc + 2;
incCntt++;
}
if(itemStatus[myHashIndx] != 1)
{
MYHASHTABLE[myHashIndx] = myStateRec;
itemStatus[myHashIndx] = 1;
myHashLen++;
}
else
{
if(MYHASHTABLE[myHashIndx] == myStateRec)
cout<<"Already present"<<endl;
else
cout<<"HASH TABLE FULL"<<endl;
}
}
template <class infoType>
void STATEHASHTABLE<infoType>::searchState(int& myHashIndx, string stateName, bool& myItemFound) const
{
int incCntt=1;
int myInc=1;
while (itemStatus[myHashIndx] != 0 && incCntt < myTableSize / 2)
{
if (MYHASHTABLE[myHashIndx].getMyStateName().compare(stateName) == 0 && itemStatus[myHashIndx] == 1) {
cout<<MYHASHTABLE[myHashIndx]<<endl;
myItemFound = true;
break;
}
myHashIndx = (myHashIndx + myInc) % myTableSize;
incCntt++;
myInc = myInc + 2;
}
}
template <class infoType>
bool STATEHASHTABLE<infoType>::checkStates(int myHashIndx, const infoType& myStateRec) const
{
if (itemStatus[myHashIndx] != 1) {
cout << "EMPTY!" << endl;
return false;
}
return MYHASHTABLE[myHashIndx] == myStateRec;
}
template <class infoType>
void STATEHASHTABLE<infoType>::getMyState(int myHashIndx, infoType& myStateRec) const
{
if (itemStatus[myHashIndx] != 1) {
cout << "EMPTY!" << endl;
}
else
myStateRec = MYHASHTABLE[myHashIndx];
}
template <class infoType>
void STATEHASHTABLE<infoType>::clearMyStateInfo(int& myHashIndx, string stateName, bool& myItemFound)
{
int incCntt=1;
int myInc=1;
while (itemStatus[myHashIndx] != 0 && incCntt < myTableSize / 2)
{
if (MYHASHTABLE[myHashIndx].getMyStateName().compare(stateName) == 0 && itemStatus[myHashIndx] == 1) {
cout<<MYHASHTABLE[myHashIndx]<<endl;
itemStatus[myHashIndx]=0;
myHashLen--;
myItemFound = true;
break;
}
myHashIndx = (myHashIndx + myInc) % myTableSize;
incCntt++;
myInc = myInc + 2;
}
}
template <class infoType>
void STATEHASHTABLE<infoType>::displayMystateHashTable() const
{
for (int kk = 0; kk < myTableSize-1; kk++) {
if (itemStatus[kk] == 1) {
cout << MYHASHTABLE[kk] << endl;
}
}
}
void SearchState()
{
STATEHASHTABLE<StateData> myHashTable(100);
ifstream fID1("Kyles_State_Data.txt");
if(fID1.is_open())
{
StateData myState;
while(fID1)
{
fID1>>myState;
int myIndx=myHashTable.hashFunc(myState.getMyStateName());
myHashTable.InsertMyState(myIndx, myState);
}
fID1.close();
string stateName;
cout<<"Enter myStateName to look into the hash table"<< endl;
cout<<"(Please use Capital letter for first letter of the state)"<< endl;
cout<<"State Name = ";
cin>>stateName;
cout<< endl;
int myIndx=myHashTable.hashFunc(stateName);
bool myItemFound=false;
myHashTable.searchState(myIndx, stateName, myItemFound) ;
if(!myItemFound)
cout<<"Item not Found."<<endl;
}
}
void DeleteState()
{
STATEHASHTABLE<StateData> myHashTable(100);
ifstream fID1("Kyles_State_Data.txt");
if(fID1.is_open())
{
StateData myState;
while(fID1)
{
fID1>>myState;
int myIndx=myHashTable.hashFunc(myState.getMyStateName());
myHashTable.InsertMyState(myIndx, myState);
}
fID1.close();
string stateName;
cout<<"Enter myStateName to delete state info"<< endl;
cout<<"(Please use Capital letter for first letter of the state)"<< endl;
cout<<"State Name = ";
cin>>stateName;
cout<< endl;
int myIndx=myHashTable.hashFunc(stateName);
bool myItemFound=false;
myHashTable.clearMyStateInfo(myIndx, stateName, myItemFound);
cout<<stateName<<" has been deleted from the hash table"<<endl<<endl; cout<<"Displaying Updated Hash Table:"<<endl;
if(!myItemFound)
cout<<"Item not Found."<<endl;
} fID1.close();
myHashTable.displayMystateHashTable() ; }
void DisplayHashTable()
{
STATEHASHTABLE<StateData> myHashTable(100);
ifstream fID1("Kyles_State_Data.txt");
if(fID1.is_open())
{
StateData myState;
while(fID1)
{
fID1>>myState;
int myIndx=myHashTable.hashFunc(myState.getMyStateName());
myHashTable.InsertMyState(myIndx, myState);
}
fID1.close();
myHashTable.displayMystateHashTable() ;
//if(!myItemFound)
//cout<<"Item not Found."<<endl;
}}
int main()
//{
//STATEHASHTABLE<StateData> myHashTable(100);
//ifstream fID1("Kyles_State_Data.txt");
//if(fID1.is_open())
//{
//StateData myState;
//while(fID1)
//{
//fID1>>myState;
//int myIndx=myHashTable.hashFunc(myState.getMyStateName());
//myHashTable.InsertMyState(myIndx, myState);
//}
{
int input;
cout<<"1. SearchState ";
cout<<"2. DeleteState ";
cout<<"3. DisplayHashTable ";
cout<<"Selection: ";
cin>> input;
switch ( input ) {
case 1: // Note the colon, not a semicolon
SearchState(); cout<<endl; main();
break;
case 2: // Note the colon, not a semicolon
DeleteState(); cout<<endl; main(); break;
case 3: // Note the colon, not a semicolon
DisplayHashTable(); cout<<endl; main(); break;
default: // Note the colon, not a semicolon
cout<<"Error, bad input, Try Again "; cout<<endl; main(); break;
} return 0;
}
For the following C++ code, please do the following...
Justification for selected algorithms.
Discussion of the time complexity of searching and deleting algorithms in terms
of Big O notation.
A discussion of the memory efficiency of the used algorithms.
--------------------------- Code--------------------------------------------
#include<iostream>
#include<string>
#include<fstream>
#include <iomanip>
#include <cassert>
using namespace std;
class StateData
{
private:
string myStateName;
string myStateCap;
int myStateUNum;
int myStateJYear;
int myStateAra;
public:
StateData(string myName1 = " ", string capN1 = " ", int uNum1 = 0, int yrN1 = 0, int areaN1 = 0)
{
myStateName = myName1;
myStateCap = capN1;
myStateUNum = uNum1;
myStateJYear = yrN1;
myStateAra = areaN1;
}
string getMyStateName()
{
return myStateName;
}
void setMyStateName(string n)
{
myStateName = n;
}
string getMyStateCap()
{
return myStateCap;
}
void setMyStateCap(string c)
{
myStateCap = c;
}
int getMyStateUNum()
{
return myStateUNum;
}
void setMyStateUNum(int n)
{
myStateUNum = n;
}
int getMyStateJYear()
{
return myStateJYear;
}
void setMyStateJYear(int y)
{
myStateJYear = y;
}
int getMyStateArea()
{
return myStateAra;
}
void setArea(int aa)
{
myStateAra = aa;
}
friend ostream& operator<<(ostream& myOut, StateData& myStateInfo)
{
if (myStateInfo.getMyStateArea() > 0)
{
myOut << myStateInfo.getMyStateName() << " , ";
myOut << myStateInfo.getMyStateCap() << " , ";
myOut << myStateInfo.getMyStateJYear() << ", ";
myOut << myStateInfo.getMyStateUNum() << " , ";
myOut << myStateInfo.getMyStateArea();
}
return myOut;
}
friend istream& operator>>(istream& myIn, StateData& myStateInfo)
{
getline(myIn, myStateInfo.myStateName);
getline(myIn, myStateInfo.myStateCap);
myIn >> myStateInfo.myStateAra >> myStateInfo.myStateJYear >> myStateInfo.myStateUNum;
char myChh;
myIn.get(myChh);
return myIn;
}
StateData& operator=(const StateData& otherStateInfo)
{
myStateName = otherStateInfo.myStateName;
myStateCap = otherStateInfo.myStateCap;
myStateUNum = otherStateInfo.myStateUNum;
myStateJYear = otherStateInfo.myStateJYear;
myStateAra = otherStateInfo.myStateAra;
return *this;
}
//operators overloading
bool operator!=(const StateData& otherStateInfo) const
{
return myStateName != otherStateInfo.myStateName;
}
bool operator==(const StateData& otherStateInfo) const
{
return myStateName == otherStateInfo.myStateName;
}
bool operator>(const StateData& otherStateInfo) const
{
return myStateName > otherStateInfo.myStateName;
}
bool operator>=(const StateData& otherStateInfo) const
{
return myStateName >= otherStateInfo.myStateName;
}
bool operator<(const StateData& otherStateInfo) const
{
return myStateName < otherStateInfo.myStateName;
}
bool operator<=(const StateData& otherStateInfo) const
{
return myStateName <= otherStateInfo.myStateName;
}
};
template <class infoType>
class STATEHASHTABLE
{
private:
infoType *MYHASHTABLE;
int *itemStatus;
int myHashLen;
int myTableSize;
public:
STATEHASHTABLE(int myHashSze= 101)
{
MYHASHTABLE = new infoType[myHashSze];
itemStatus = new int[myHashSze];
for (int kk = 0; kk < myHashSze; kk++) {
itemStatus[kk] = 0;
myTableSize = myHashSze;
myHashLen = 0;
}
}
~STATEHASHTABLE()
{
delete[] MYHASHTABLE;
delete[] itemStatus;
}
int hashFunc(string myStateName);
void displayMystateHashTable() const;
void InsertMyState(int myHashIndx, const infoType& myStateRec);
void getMyState(int myHashIndx, infoType& myStateRec) const;
void searchState(int& myHashIndx, string stateName, bool& myItemFound) const;
bool checkStates(int myHashIndx, const infoType& myStateRec) const;
void clearMyStateInfo(int& myHashIndx, string stateName, bool& myItemFound);
};
template <class infoType>
int STATEHASHTABLE<infoType>::hashFunc(string myStateName)
{
int aa, myHSum;
int len;
aa = 0;
myHSum = 0;
len = myStateName.length();
for (int k = 0; k < 15 - len; k++)
myStateName = myStateName + ' ';
for (int k = 0; k < 5; k++)
{
myHSum = myHSum + static_cast<int>(myStateName[aa]) * 128 * 128
+ static_cast<int>(myStateName[aa + 1]) * 128
+ static_cast<int>(myStateName[aa + 2]);
aa = aa + 3;
}
return myHSum % myTableSize;
}
template <class infoType>
void STATEHASHTABLE<infoType>::InsertMyState(int myHashIndx, const infoType& myStateRec)
{
int incCntt=1;
int myInc=1;
while(itemStatus[myHashIndx] == 1 && incCntt < myTableSize / 2)
{
myHashIndx = (myHashIndx + myInc ) % myTableSize;
myInc = myInc + 2;
incCntt++;
}
if(itemStatus[myHashIndx] != 1)
{
MYHASHTABLE[myHashIndx] = myStateRec;
itemStatus[myHashIndx] = 1;
myHashLen++;
}
else
{
if(MYHASHTABLE[myHashIndx] == myStateRec)
cout<<"Already present"<<endl;
else
cout<<"HASH TABLE FULL"<<endl;
}
}
template <class infoType>
void STATEHASHTABLE<infoType>::searchState(int& myHashIndx, string stateName, bool& myItemFound) const
{
int incCntt=1;
int myInc=1;
while (itemStatus[myHashIndx] != 0 && incCntt < myTableSize / 2)
{
if (MYHASHTABLE[myHashIndx].getMyStateName().compare(stateName) == 0 && itemStatus[myHashIndx] == 1) {
cout<<MYHASHTABLE[myHashIndx]<<endl;
myItemFound = true;
break;
}
myHashIndx = (myHashIndx + myInc) % myTableSize;
incCntt++;
myInc = myInc + 2;
}
}
template <class infoType>
bool STATEHASHTABLE<infoType>::checkStates(int myHashIndx, const infoType& myStateRec) const
{
if (itemStatus[myHashIndx] != 1) {
cout << "EMPTY!" << endl;
return false;
}
return MYHASHTABLE[myHashIndx] == myStateRec;
}
template <class infoType>
void STATEHASHTABLE<infoType>::getMyState(int myHashIndx, infoType& myStateRec) const
{
if (itemStatus[myHashIndx] != 1) {
cout << "EMPTY!" << endl;
}
else
myStateRec = MYHASHTABLE[myHashIndx];
}
template <class infoType>
void STATEHASHTABLE<infoType>::clearMyStateInfo(int& myHashIndx, string stateName, bool& myItemFound)
{
int incCntt=1;
int myInc=1;
while (itemStatus[myHashIndx] != 0 && incCntt < myTableSize / 2)
{
if (MYHASHTABLE[myHashIndx].getMyStateName().compare(stateName) == 0 && itemStatus[myHashIndx] == 1) {
cout<<MYHASHTABLE[myHashIndx]<<endl;
itemStatus[myHashIndx]=0;
myHashLen--;
myItemFound = true;
break;
}
myHashIndx = (myHashIndx + myInc) % myTableSize;
incCntt++;
myInc = myInc + 2;
}
}
template <class infoType>
void STATEHASHTABLE<infoType>::displayMystateHashTable() const
{
for (int kk = 0; kk < myTableSize-1; kk++) {
if (itemStatus[kk] == 1) {
cout << MYHASHTABLE[kk] << endl;
}
}
}
void SearchState()
{
STATEHASHTABLE<StateData> myHashTable(100);
ifstream fID1("Kyles_State_Data.txt");
if(fID1.is_open())
{
StateData myState;
while(fID1)
{
fID1>>myState;
int myIndx=myHashTable.hashFunc(myState.getMyStateName());
myHashTable.InsertMyState(myIndx, myState);
}
fID1.close();
string stateName;
cout<<"Enter myStateName to look into the hash table"<< endl;
cout<<"(Please use Capital letter for first letter of the state)"<< endl;
cout<<"State Name = ";
cin>>stateName;
cout<< endl;
int myIndx=myHashTable.hashFunc(stateName);
bool myItemFound=false;
myHashTable.searchState(myIndx, stateName, myItemFound) ;
if(!myItemFound)
cout<<"Item not Found."<<endl;
}
}
void DeleteState()
{
STATEHASHTABLE<StateData> myHashTable(100);
ifstream fID1("Kyles_State_Data.txt");
if(fID1.is_open())
{
StateData myState;
while(fID1)
{
fID1>>myState;
int myIndx=myHashTable.hashFunc(myState.getMyStateName());
myHashTable.InsertMyState(myIndx, myState);
}
fID1.close();
string stateName;
cout<<"Enter myStateName to delete state info"<< endl;
cout<<"(Please use Capital letter for first letter of the state)"<< endl;
cout<<"State Name = ";
cin>>stateName;
cout<< endl;
int myIndx=myHashTable.hashFunc(stateName);
bool myItemFound=false;
myHashTable.clearMyStateInfo(myIndx, stateName, myItemFound);
cout<<stateName<<" has been deleted from the hash table"<<endl<<endl; cout<<"Displaying Updated Hash Table:"<<endl;
if(!myItemFound)
cout<<"Item not Found."<<endl;
} fID1.close();
myHashTable.displayMystateHashTable() ; }
void DisplayHashTable()
{
STATEHASHTABLE<StateData> myHashTable(100);
ifstream fID1("Kyles_State_Data.txt");
if(fID1.is_open())
{
StateData myState;
while(fID1)
{
fID1>>myState;
int myIndx=myHashTable.hashFunc(myState.getMyStateName());
myHashTable.InsertMyState(myIndx, myState);
}
fID1.close();
myHashTable.displayMystateHashTable() ;
//if(!myItemFound)
//cout<<"Item not Found."<<endl;
}}
int main()
//{
//STATEHASHTABLE<StateData> myHashTable(100);
//ifstream fID1("Kyles_State_Data.txt");
//if(fID1.is_open())
//{
//StateData myState;
//while(fID1)
//{
//fID1>>myState;
//int myIndx=myHashTable.hashFunc(myState.getMyStateName());
//myHashTable.InsertMyState(myIndx, myState);
//}
{
int input;
cout<<"1. SearchState ";
cout<<"2. DeleteState ";
cout<<"3. DisplayHashTable ";
cout<<"Selection: ";
cin>> input;
switch ( input ) {
case 1: // Note the colon, not a semicolon
SearchState(); cout<<endl; main();
break;
case 2: // Note the colon, not a semicolon
DeleteState(); cout<<endl; main(); break;
case 3: // Note the colon, not a semicolon
DisplayHashTable(); cout<<endl; main(); break;
default: // Note the colon, not a semicolon
cout<<"Error, bad input, Try Again "; cout<<endl; main(); break;
} return 0;
}
For the following C++ code, please do the following...
Justification for selected algorithms.
Discussion of the time complexity of searching and deleting algorithms in terms
of Big O notation.
A discussion of the memory efficiency of the used algorithms.
--------------------------- Code--------------------------------------------
#include<iostream>
#include<string>
#include<fstream>
#include <iomanip>
#include <cassert>
using namespace std;
class StateData
{
private:
string myStateName;
string myStateCap;
int myStateUNum;
int myStateJYear;
int myStateAra;
public:
StateData(string myName1 = " ", string capN1 = " ", int uNum1 = 0, int yrN1 = 0, int areaN1 = 0)
{
myStateName = myName1;
myStateCap = capN1;
myStateUNum = uNum1;
myStateJYear = yrN1;
myStateAra = areaN1;
}
string getMyStateName()
{
return myStateName;
}
void setMyStateName(string n)
{
myStateName = n;
}
string getMyStateCap()
{
return myStateCap;
}
void setMyStateCap(string c)
{
myStateCap = c;
}
int getMyStateUNum()
{
return myStateUNum;
}
void setMyStateUNum(int n)
{
myStateUNum = n;
}
int getMyStateJYear()
{
return myStateJYear;
}
void setMyStateJYear(int y)
{
myStateJYear = y;
}
int getMyStateArea()
{
return myStateAra;
}
void setArea(int aa)
{
myStateAra = aa;
}
friend ostream& operator<<(ostream& myOut, StateData& myStateInfo)
{
if (myStateInfo.getMyStateArea() > 0)
{
myOut << myStateInfo.getMyStateName() << " , ";
myOut << myStateInfo.getMyStateCap() << " , ";
myOut << myStateInfo.getMyStateJYear() << ", ";
myOut << myStateInfo.getMyStateUNum() << " , ";
myOut << myStateInfo.getMyStateArea();
}
return myOut;
}
friend istream& operator>>(istream& myIn, StateData& myStateInfo)
{
getline(myIn, myStateInfo.myStateName);
getline(myIn, myStateInfo.myStateCap);
myIn >> myStateInfo.myStateAra >> myStateInfo.myStateJYear >> myStateInfo.myStateUNum;
char myChh;
myIn.get(myChh);
return myIn;
}
StateData& operator=(const StateData& otherStateInfo)
{
myStateName = otherStateInfo.myStateName;
myStateCap = otherStateInfo.myStateCap;
myStateUNum = otherStateInfo.myStateUNum;
myStateJYear = otherStateInfo.myStateJYear;
myStateAra = otherStateInfo.myStateAra;
return *this;
}
//operators overloading
bool operator!=(const StateData& otherStateInfo) const
{
return myStateName != otherStateInfo.myStateName;
}
bool operator==(const StateData& otherStateInfo) const
{
return myStateName == otherStateInfo.myStateName;
}
bool operator>(const StateData& otherStateInfo) const
{
return myStateName > otherStateInfo.myStateName;
}
bool operator>=(const StateData& otherStateInfo) const
{
return myStateName >= otherStateInfo.myStateName;
}
bool operator<(const StateData& otherStateInfo) const
{
return myStateName < otherStateInfo.myStateName;
}
bool operator<=(const StateData& otherStateInfo) const
{
return myStateName <= otherStateInfo.myStateName;
}
};
template <class infoType>
class STATEHASHTABLE
{
private:
infoType *MYHASHTABLE;
int *itemStatus;
int myHashLen;
int myTableSize;
public:
STATEHASHTABLE(int myHashSze= 101)
{
MYHASHTABLE = new infoType[myHashSze];
itemStatus = new int[myHashSze];
for (int kk = 0; kk < myHashSze; kk++) {
itemStatus[kk] = 0;
myTableSize = myHashSze;
myHashLen = 0;
}
}
~STATEHASHTABLE()
{
delete[] MYHASHTABLE;
delete[] itemStatus;
}
int hashFunc(string myStateName);
void displayMystateHashTable() const;
void InsertMyState(int myHashIndx, const infoType& myStateRec);
void getMyState(int myHashIndx, infoType& myStateRec) const;
void searchState(int& myHashIndx, string stateName, bool& myItemFound) const;
bool checkStates(int myHashIndx, const infoType& myStateRec) const;
void clearMyStateInfo(int& myHashIndx, string stateName, bool& myItemFound);
};
template <class infoType>
int STATEHASHTABLE<infoType>::hashFunc(string myStateName)
{
int aa, myHSum;
int len;
aa = 0;
myHSum = 0;
len = myStateName.length();
for (int k = 0; k < 15 - len; k++)
myStateName = myStateName + ' ';
for (int k = 0; k < 5; k++)
{
myHSum = myHSum + static_cast<int>(myStateName[aa]) * 128 * 128
+ static_cast<int>(myStateName[aa + 1]) * 128
+ static_cast<int>(myStateName[aa + 2]);
aa = aa + 3;
}
return myHSum % myTableSize;
}
template <class infoType>
void STATEHASHTABLE<infoType>::InsertMyState(int myHashIndx, const infoType& myStateRec)
{
int incCntt=1;
int myInc=1;
while(itemStatus[myHashIndx] == 1 && incCntt < myTableSize / 2)
{
myHashIndx = (myHashIndx + myInc ) % myTableSize;
myInc = myInc + 2;
incCntt++;
}
if(itemStatus[myHashIndx] != 1)
{
MYHASHTABLE[myHashIndx] = myStateRec;
itemStatus[myHashIndx] = 1;
myHashLen++;
}
else
{
if(MYHASHTABLE[myHashIndx] == myStateRec)
cout<<"Already present"<<endl;
else
cout<<"HASH TABLE FULL"<<endl;
}
}
template <class infoType>
void STATEHASHTABLE<infoType>::searchState(int& myHashIndx, string stateName, bool& myItemFound) const
{
int incCntt=1;
int myInc=1;
while (itemStatus[myHashIndx] != 0 && incCntt < myTableSize / 2)
{
if (MYHASHTABLE[myHashIndx].getMyStateName().compare(stateName) == 0 && itemStatus[myHashIndx] == 1) {
cout<<MYHASHTABLE[myHashIndx]<<endl;
myItemFound = true;
break;
}
myHashIndx = (myHashIndx + myInc) % myTableSize;
incCntt++;
myInc = myInc + 2;
}
}
template <class infoType>
bool STATEHASHTABLE<infoType>::checkStates(int myHashIndx, const infoType& myStateRec) const
{
if (itemStatus[myHashIndx] != 1) {
cout << "EMPTY!" << endl;
return false;
}
return MYHASHTABLE[myHashIndx] == myStateRec;
}
template <class infoType>
void STATEHASHTABLE<infoType>::getMyState(int myHashIndx, infoType& myStateRec) const
{
if (itemStatus[myHashIndx] != 1) {
cout << "EMPTY!" << endl;
}
else
myStateRec = MYHASHTABLE[myHashIndx];
}
template <class infoType>
void STATEHASHTABLE<infoType>::clearMyStateInfo(int& myHashIndx, string stateName, bool& myItemFound)
{
int incCntt=1;
int myInc=1;
while (itemStatus[myHashIndx] != 0 && incCntt < myTableSize / 2)
{
if (MYHASHTABLE[myHashIndx].getMyStateName().compare(stateName) == 0 && itemStatus[myHashIndx] == 1) {
cout<<MYHASHTABLE[myHashIndx]<<endl;
itemStatus[myHashIndx]=0;
myHashLen--;
myItemFound = true;
break;
}
myHashIndx = (myHashIndx + myInc) % myTableSize;
incCntt++;
myInc = myInc + 2;
}
}
template <class infoType>
void STATEHASHTABLE<infoType>::displayMystateHashTable() const
{
for (int kk = 0; kk < myTableSize-1; kk++) {
if (itemStatus[kk] == 1) {
cout << MYHASHTABLE[kk] << endl;
}
}
}
void SearchState()
{
STATEHASHTABLE<StateData> myHashTable(100);
ifstream fID1("Kyles_State_Data.txt");
if(fID1.is_open())
{
StateData myState;
while(fID1)
{
fID1>>myState;
int myIndx=myHashTable.hashFunc(myState.getMyStateName());
myHashTable.InsertMyState(myIndx, myState);
}
fID1.close();
string stateName;
cout<<"Enter myStateName to look into the hash table"<< endl;
cout<<"(Please use Capital letter for first letter of the state)"<< endl;
cout<<"State Name = ";
cin>>stateName;
cout<< endl;
int myIndx=myHashTable.hashFunc(stateName);
bool myItemFound=false;
myHashTable.searchState(myIndx, stateName, myItemFound) ;
if(!myItemFound)
cout<<"Item not Found."<<endl;
}
}
void DeleteState()
{
STATEHASHTABLE<StateData> myHashTable(100);
ifstream fID1("Kyles_State_Data.txt");
if(fID1.is_open())
{
StateData myState;
while(fID1)
{
fID1>>myState;
int myIndx=myHashTable.hashFunc(myState.getMyStateName());
myHashTable.InsertMyState(myIndx, myState);
}
fID1.close();
string stateName;
cout<<"Enter myStateName to delete state info"<< endl;
cout<<"(Please use Capital letter for first letter of the state)"<< endl;
cout<<"State Name = ";
cin>>stateName;
cout<< endl;
int myIndx=myHashTable.hashFunc(stateName);
bool myItemFound=false;
myHashTable.clearMyStateInfo(myIndx, stateName, myItemFound);
cout<<stateName<<" has been deleted from the hash table"<<endl<<endl; cout<<"Displaying Updated Hash Table:"<<endl;
if(!myItemFound)
cout<<"Item not Found."<<endl;
} fID1.close();
myHashTable.displayMystateHashTable() ; }
void DisplayHashTable()
{
STATEHASHTABLE<StateData> myHashTable(100);
ifstream fID1("Kyles_State_Data.txt");
if(fID1.is_open())
{
StateData myState;
while(fID1)
{
fID1>>myState;
int myIndx=myHashTable.hashFunc(myState.getMyStateName());
myHashTable.InsertMyState(myIndx, myState);
}
fID1.close();
myHashTable.displayMystateHashTable() ;
//if(!myItemFound)
//cout<<"Item not Found."<<endl;
}}
int main()
//{
//STATEHASHTABLE<StateData> myHashTable(100);
//ifstream fID1("Kyles_State_Data.txt");
//if(fID1.is_open())
//{
//StateData myState;
//while(fID1)
//{
//fID1>>myState;
//int myIndx=myHashTable.hashFunc(myState.getMyStateName());
//myHashTable.InsertMyState(myIndx, myState);
//}
{
int input;
cout<<"1. SearchState ";
cout<<"2. DeleteState ";
cout<<"3. DisplayHashTable ";
cout<<"Selection: ";
cin>> input;
switch ( input ) {
case 1: // Note the colon, not a semicolon
SearchState(); cout<<endl; main();
break;
case 2: // Note the colon, not a semicolon
DeleteState(); cout<<endl; main(); break;
case 3: // Note the colon, not a semicolon
DisplayHashTable(); cout<<endl; main(); break;
default: // Note the colon, not a semicolon
cout<<"Error, bad input, Try Again "; cout<<endl; main(); break;
} return 0;
}
Explanation / Answer
a> Algorithm selected to insert, search and delete the data is Hashing
Hash Indexes is the general recommendation for equality based lookups, as it doesn't need to traverse any b tree or an array to search any element.
Hashing also makes it easy to add and delete elements from the collection that is being searched.
b> A suitably sized hash table can very well give an amortized O(1) cost for lookup operations (search)
As per the algorithm, deletion is also based on generating the hash index and then deleting it using the same search algorithm.
Refer to clearMyStateInfo and STATEHASHTABLE<infoType>::searchState methods of the template class
Average case: O(1)
Worst case: O(n)
c> As the memory is preallocated using below statement:
STATEHASHTABLE<StateData> myHashTable(100);
program is memory efficient.
For Hash function, hash index is based on the string and myTableSize/has size, this is also memory opimized