-table: List* -size: int -hash (key : string) : int {query} +Hash Table(s : int)

Question

-table: List*
-size: int

-hash (key : string) : int {query}
+Hash Table(s : int) :
+~Hash Table() :
+clear() : void
+insert(key : string) : int
+find (key :string) : bool
+isFull() : bool {query}
+isEmpty() : bool {query}
+remove (key:string) : int
+print() : void {query}

Use the above UML diagram and descriptions below to write a class that implements a Hash table. Your implementation should use open chaining to resolve collisions. You may provide additional class attributes, as you see fit, to complete the class.

The above class has the following private attributes:

table: This is a pointer to the object's dynamically allocated hash table. Used to create an array of Linked List objects.

size - stores the number of elements in the hash table ( the capacity ).

hash - the hash function. It accepts the key string and returns the hash value.

The class has the following public attributes:

constructor - accepts an integer argument used to determine the number of elements in the hash table. Dynamically allocates the hash table.

destructor - deallocates all dynamically allocated memory.

insert - insert's it's argument into the hash table. calls the hash function to obtain an appropriate hash address. Returns 0 if successful, -1 otherwise.

remove - removes the first key matching it's argument from the hash table. Returns 0 if successful, -1 otherwise.

find - returns true if a key matching it's argument is found, false otherwise.

clear - resets the object to it's initial state.

isFull - returns true if the structure is full, false otherwise.

isEmpty - returns true if the structure has no keys, false otherwise.

print - displays all the keys currently stored in the structure.

PLEASE NOTE: FOLLOW AND USE THE ABOVE UML DIAGRAM (That includes function names as well) !! The class along with its function prototypes and its definitions should all be contained INSIDE THE HEADER FILE !!
YOUR ANSWER SHOULD BE A HEADER FILE WITH THE CLASS DECLERATION, FUNCTION PROTOTYPE AND FUNCTION DEFINITIONS !!!
DO NOR MAKE A .CPP PROGRAM !!!

-table: List*
-size: int

-hash (key : string) : int {query}
+Hash Table(s : int) :
+~Hash Table() :
+clear() : void
+insert(key : string) : int
+find (key :string) : bool
+isFull() : bool {query}
+isEmpty() : bool {query}
+remove (key:string) : int
+print() : void {query}

Explanation / Answer

#ifndef _DICTIONARY_H_
#define _DICTIONARY_H_

#include <iostream>
#include <string>

#include "bucket.h"

using namespace std;

template <class T>
class Dictionary
{
private:

Bucket<T>* mBuckets;

// Number of buckets
int mCount;

int hash(string key)
{
// Modular hashing algorithm

int value = 0;

for (int i = 0; i < key.length(); i++)
value += key[i];

return value % mCount;
}

public:
Dictionary();
Dictionary(int mCount);
~Dictionary();

bool containsKey(string key);
void display();
int getCount();
T getData(string key);
bool insert(string key, T value);
bool isEmpty();
};

///Constructor / Destructor

template <class T>
Dictionary<T>::Dictionary()
{
// Default mCount to 16
this->mCount = 16;

// Define mBins
mBuckets = new Bucket<Item<T>>[mCount];
}

template <class T>
Dictionary<T>::Dictionary(int mCount)
{
// Default mCount to 16 if invalid
this->mCount = (mCount >= 0 ? mCount : 16);

// Define mBins
mBuckets = new Bucket<T>[mCount];
}

template <class T>
Dictionary<T>::~Dictionary()
{
delete[] mBuckets;
}

// ********************************************************
// Functions
// ********************************************************

template <class T>
bool Dictionary<T>::containsKey(string key)
{
int bin = hash(key);

return mBuckets[bin].isExist(key);
}

template <class T>
void Dictionary<T>::display()
{
cout
<< " Dictionary - Items:" << getCount() << " "
<< "*********************** ";

for (int i = 0; i < mCount; i++)
{
cout << left << i << ": ";

mBuckets[i].display();

cout << " ";
}
}

template <class T>
void Dictionary<T>::displayDistribution()
{
cout
<< " Dictionary - Distribution:" << getCount() << " "
<< "*********************** ";

for (int i = 0; i < mCount; i++)
{
cout
<< left
<< i << ": " << mBuckets[i].getCount();

cout << " ";
}
}

template <class T>
int Dictionary<T>::getCount()
{
int count = 0;
for (int i = 0; i < mCount; i++)
{
count += mBuckets[i].getCount();
}

return count;
}

template <class T>
T Dictionary<T>::getData(string key)
{
int bin = hash(key);

return mBuckets[bin].getData(key);
}

template <class T>
bool Dictionary<T>::insert(string key, T value)
{
int bin = hash(key);

mBuckets[bin].insert(key, value);

return true;
}

template <class T>
bool Dictionary<T>::isEmpty()
{
return getCount() == 0;
}

#endif
Bucket class:

#ifndef _BUCKET_H_
#define _BUCKET_H_

#include <iostream>

using namespace std;

template <class T>
class Bucket
{
private:
template <class T>
struct Node
{
string mKey;
T mData;
Node<T> *mNext, *mPrevious;

Node()
{
mKey = "";
mData = T();
mNext = NULL;
mPrevious = NULL;
}

Node(string key, T data)
{
mKey = key;
mData = data;
mNext = NULL;
mPrevious = NULL;
}
};

Node<T> *mHead, *mTail;
int mCount;
public:
Bucket();
~Bucket();

int getCount();
bool isEmpty();
bool isExist(string searchKey);
bool remove(string searchKey);

void display();
void insert(string key, T data);

T getData(string key);
};

// ********************************************************
// Constructor / Destructor
// ********************************************************

template <class T>
Bucket<T>::Bucket()
{
mHead = NULL;
mTail = NULL;
mCount = 0;
}

template <class T>
Bucket<T>::~Bucket()
{
Node<T> *tmp, *toBeDeleted;

tmp = mHead;

// removing node by node
while (tmp != NULL)
{
toBeDeleted = tmp;
tmp = tmp->mNext;
toBeDeleted->mNext = NULL;

delete toBeDeleted;
}

// reinitialize the pointers
mHead = NULL;
mTail = NULL;
mCount = 0;
}

// ********************************************************
// Functions
// ********************************************************

template <class T>
int Bucket<T>::getCount()
{
return mCount;
}

template <class T>
bool Bucket<T>::isEmpty()
{
return mCount == 0;
}

template <class T>
bool Bucket<T>::isExist(string searchKey)
{
Node<T> *tmp = mHead;

while (tmp != NULL)
{
if (tmp->mKey == searchKey)
return true;

tmp = tmp->mNext;
}

return false;
}

template <class T>
bool Bucket<T>::remove(string searchKey)
{
Node<T> *tmp, *prev;

if (mHead == NULL)
return false;
else if (searchKey < mHead->mKey || searchKey > mTail->mKey)
return false;

tmp = mHead;
prev = NULL;

for (int i = 0; i < mCount; i++)
{
if (searchKey == tmp->mKey)
break;

prev = tmp;
tmp = tmp->mNext;
}

if (tmp != NULL)
{
if (tmp == mHead)
{
tmp = mHead;

mHead = mHead->mNext;
if (mHead == NULL)
mTail = NULL;

tmp->mNext = NULL;
}
else if (tmp == mTail)
{
prev->mNext = NULL;
mTail = prev;
}
else
{
prev->mNext = tmp->mNext;
tmp->mNext = NULL;
}

delete tmp;
mCount--;

return true;
}

return false;
}

template <class T>
void Bucket<T>::display()
{
Node<T> *tmp;

if (mHead == NULL)
{
cout << "{ } ";
return;
}

cout << "{ ";
tmp = mHead;
while (tmp != NULL)
{
cout
<< "["
<< tmp->mKey
<< ", "
<< tmp->mData
<< "]"
<< (tmp != mTail ? ", " : " }");

tmp = tmp->mNext;
}
cout << " ";
}
template <class T>
void Bucket<T>::insert(string key, T data)
{
Node<T> *tmp, *oneBefore, *newNode;

newNode = new Node<T>(key, data);
if (newNode == NULL)
return;

if (mHead == NULL)
{
mHead = newNode;
mTail = newNode;
}
else
{
if (key < mHead->mKey) // Put at head
{
newNode->mNext = mHead;

newNode->mPrevious = NULL;

mHead = newNode;
}
else if (key > mTail->mKey) // Put at tail
{
mTail->mNext = newNode;

newNode->mPrevious = mTail;

mTail = newNode;
}
else if (key == mHead->mKey || key == mTail->mKey) // Dont insert if already added
{
delete newNode;
return;
}
else
{
tmp = mHead;
>