// Author : Lillian Martinez
//
// Due Date : November 28th , 2022
//
// Programming Assignment Number 7
//
// Fall 2022 - CS 3358 - 001
//
// Instructor: Husain Gholoom.
//
// <Brief description of the purpose of the program>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <string>
#include <iomanip> // std::setw
using namespace std;
/*******************************************************************************
* hash class declaration: *
*******************************************************************************/
class hashtable
{
private:
int hash_pos;
static const int ARR_SIZE = 27;
string array[ARR_SIZE];
int linearProbes = 0;
int collisions = 0;
public:
hashtable();
//~hashtable();
void insert(string);
int Hash(string);
int reHash(int);
void Display();
void Search(string);
void Delete(string);
int getProbes();
int getCollisions();
void generate();
void greeting();
void convert();
};
/*******************************************************************************
* hash class implementation: *
*******************************************************************************/
/*
hashtable::~hashtable()
{
for(int i=0;i<ARR_SIZE;i++)
delete array;
}
*/
// Constructor:
hashtable::hashtable()
{
linearProbes = 0;
collisions = 0;
for(int i=0; i<ARR_SIZE; i++)
{
array[i] = '-';
}
}
int hashtable::Hash(string key)
{
linearProbes++;
//return key % ARR_SIZE;
int value = 0 ;
for (int i = 0; i < key.length(); i++)
value = value * 37 + key[i];
return value % ARR_SIZE;
}
int hashtable::reHash(int key)
{
collisions++;
return (key+1) % ARR_SIZE;
/*int value = 0 ;
for (int i = 0; i < key.length(); i++)
value = value * 37 + key[i];
return (value+1) % ARR_SIZE;*/
}
void hashtable::insert(string key){
cout << "\n\nInserting a new word (" << key << ") in the table. ";
int count = 0;
hash_pos = Hash(key);
//linearProbes += 1;
if(hash_pos > ARR_SIZE){
hash_pos = 0;
}
while(array[hash_pos] != "-"){
hash_pos = reHash(hash_pos);
count++;
if(count >= ARR_SIZE){
cout << "\nMemory Full!! No space is available for storage."<<endl<<endl;
break;
}
}
if(array[hash_pos] == "-"){
array[hash_pos] = key;
cout<<"\nThe word (" << key << ") is inserted in location " << hash_pos<<endl<<endl;
}
}
void hashtable::Delete(string key){
cout << "\n\nDelete the word (" << key << ") from the table. ";
bool found = false;
int count = 0;
cout<< hash_pos<<endl<<endl;
hash_pos = Hash(key);
cout<< hash_pos<<endl<<endl;
//linearProbes += 1;
if(array[hash_pos] == key){
found = true;
count++;
}
else{
while(count < ARR_SIZE){
hash_pos = reHash(hash_pos);
cout<< hash_pos<<endl;
//collisions += 1;
count++;
if(array[hash_pos] == key){
found = true;
break;
}
else{
if(count > ARR_SIZE){
break;
}
}
}
}
if(found){
array[hash_pos] = "-";
cout<<"\nThe word (" << key << ") has been deleted " <<endl<<endl;
}
else{
cout<<"\nThe word (" << key << ") is not found " <<endl<<endl;
}
}
void hashtable::Search(string key){
cout << "\n\nSearching for a word (" << key << ") in the table. ";
bool found = false;
int count = 0;
hash_pos = Hash(key);
//linearProbes += 1;
if(array[hash_pos] == key){
found = true;
}
else{
while(count < ARR_SIZE){
hash_pos = reHash(hash_pos);
count++;
if(array[hash_pos] == key){
found = true;
break;
}
else{
if(count > ARR_SIZE){
break;
}
}
}
}
if(found){
cout << "\nThe word (" << key << ") was found in location "
<< hash_pos << endl << endl;
}
else{
cout << "\nNo record found!!" << endl << endl;
}
}
void hashtable::generate()
{
string filename = "Words.txt";
string words; // To read each line from code
int i=0; // Variable to keep count of each line
int lines;
ifstream mFile;
mFile.open(filename);
while(mFile >> words){
lines = Hash(words);
array[lines] = words;
}
mFile.close();
}
void hashtable::Display()
{
cout << endl;
for(int i=0; i < ARR_SIZE; i++)
{
cout << array[i] <<"\t"; //displays first half of the array
if ((i + 1) % 4 == 0)
{
cout << "\n";
}
}
cout << endl;
}
int hashtable::getProbes()
{
return linearProbes;
}
int hashtable::getCollisions()
{
return collisions;
}
void hashtable::greeting()
{
cout << "Hashing Program\n"
<< "\n"
<< "------------------\n"
<< "\n"
<< "1. Creates an integer array of size 27. Assigning - to each\n"
<< " location in the array indicating that the array is empty.\n"
<< "2. Populates 26 elements of the array with words\n"
<< "3. If a collision occurs, linear probing will find the next\n"
<< " available position / location\n"
<< "4. The generated array will be displayed in 7 lines.\n"
<< " Each line contains 4 words separated by a tab space.\n" //need to do the tabs
<< "\n";
}
/*******************************************************************************
* main function: *
*******************************************************************************/
int main()
{
// Hold a user choice for main menu:
string choice = "";
// create a hash object:
hashtable h;
// Say the greeting:
h.greeting();
// Generate the array:
h.generate();
// Display the array:
cout << "\nThe generated Array\n"
<< "---------------\n"
<< "\n";
h.Display();
// Search the array:
h.Search("Zulu");
// Search the array:
h.Search("Hulu");
// Insert the array:
h.insert("Mayday");
// Insert the array:
h.insert("Bonanza");
// Display the array:
cout << "\n\nThe Table After the words were inserted:\n\n";
h.Display();
// Delete the array:
h.Delete("Zulu");
// Delete the array:
h.Delete("Delta");
// Delete the array:
h.Delete("Bonanza");
// Display the array:
h.Display();
/*
// Display the probes and collisions data:
cout << "\nThe number of times each position / location is hashed when"
<< endl << "adding an element in the array is " << h.getProbes()
<< endl << endl
<< "The number of linear probes when each number is hashed and "
<< "collision " << endl << "occurred when adding an element in the "
<< "array is " << h.getCollisions() << endl;
*/
// Say goodbye:
cout << endl << "This hashing program was implemented by" << endl
<< "Lillian Martinez" << endl
<< "11-28-2022" << endl << endl;
//h.~hashtable();
return 0;
}