C++ Hash Dictionary

Implement a Hashed Dictionary. You will have to first implement the necessary functions in `HashedEntry.h` (which inherits from `Entry.h`). The Dictionary must maintain an array of HashedEntries. Look at the implemented Constructor and toVector functions for insights. You have to add new HashedEntries to front of the list when the key has the same hash index. Look at this link for insights on our implementation: https://en.wikipedia.org/wiki/Hash_table ## Files to work on * `HashedEntry.h` Implement the necessary functions * `HashedDictionary.h` Implement the necessary functions marked with T-O-D-O's * You can also modify `main.cpp` to debug your program. * `README.md` to add your name and badge 

HashedEntry.h File***************************************

#pragma once #include "Entry.h" template<class KeyType, class ItemType> class HashedEntry : public Entry { private: HashedEntry *nextPtr; public: HashedEntry(); HashedEntry(KeyType searchKey, ItemType newEntry); HashedEntry(KeyType searchKey, ItemType newEntry, HashedEntry *nextEntryPtr); void setNext(HashedEntry *nextEntryPtr); HashedEntry *getNext() const; void operator=(const ItemType&); }; template<class KeyType, class ItemType> void HashedEntry::operator=(const ItemType& newItem){ //DO NOT MODIFY this->setItem(newItem); }; 

HashedDictionary.h File********************************************

#pragma once #include "DictionaryInterface.h" #include "HashedEntry.h" #include #include #include #define DEFAULT_SIZE 101 /** * * This Hash table is of fixed max size 101 - which is a prime number (why?) */ template<class KeyType, class ItemType> class HashedDictionary : public DictionaryInterface { private: HashedEntry **hashTable; // Array of pointers to entries int itemCount; int hashTableSize; //Default value should be assigned to 101 int getHashIndex(const KeyType &itemKey) const; void destroyDictionary(); public: HashedDictionary(); virtual ~HashedDictionary(); void clear() override; bool isEmpty() const override; int getNumberOfItems() const override; bool add(const KeyType &searchKey, const ItemType &newItem) override; bool remove(const KeyType &searchKey) override; ItemType getItem(const KeyType &searchKey) const override; bool contains(const KeyType &searchKey) const override; void traverse(void (*visit)(ItemType &)) const override; std::vector toVector() const override; HashedEntry& operator[](KeyType key); }; template<class KeyType, class ItemType> int HashedDictionary::getHashIndex(const KeyType &key) const { //DO NOT MODIFY return static_cast<int>(key % hashTableSize); } template<class KeyType, class ItemType> void HashedDictionary::destroyDictionary() { //TODO } template<class KeyType, class ItemType> HashedDictionary::HashedDictionary() : itemCount(0), hashTableSize(DEFAULT_SIZE) { //DO NOT MODIFY hashTable = new HashedEntry *[DEFAULT_SIZE]; for (int i = 0; i < DEFAULT_SIZE; i++) hashTable[i] = nullptr; } template<class KeyType, class ItemType> HashedDictionary::~HashedDictionary() { //DO NOT MODIFY destroyDictionary(); } template<class KeyType, class ItemType> void HashedDictionary::clear() { //DO NOT MODIFY destroyDictionary(); } template<class KeyType, class ItemType> bool HashedDictionary::isEmpty() const { //TODO } template<class KeyType, class ItemType> int HashedDictionary::getNumberOfItems() const { //TODO } template<class KeyType, class ItemType> bool HashedDictionary::add(const KeyType &searchKey, const ItemType &newItem) { //TODO } template<class KeyType, class ItemType> bool HashedDictionary::remove(const KeyType &searchKey) { //TODO } template<class KeyType, class ItemType> ItemType HashedDictionary::getItem(const KeyType &searchKey) const { //TODO } template<class KeyType, class ItemType> bool HashedDictionary::contains(const KeyType &searchKey) const { //TODO } template<class KeyType, class ItemType> void HashedDictionary::traverse(void (*visit)(ItemType &)) const { //DO NOT MODIFY for (int index = 0; index < hashTableSize; index++) { HashedEntry *chainPtr = hashTable[index]; while (chainPtr != nullptr) { ItemType currentItem = chainPtr->getItem(); visit(currentItem); chainPtr = chainPtr->getNext(); } } } template<class KeyType, class ItemType> std::vector HashedDictionary::toVector() const { //DO NOT MODIFY std::vector returnVector; for (int index = 0; index < hashTableSize; index++) { HashedEntry *chainPtr = hashTable[index]; while (chainPtr != nullptr) { ItemType currentItem = chainPtr->getItem(); returnVector.push_back(currentItem); chainPtr = chainPtr->getNext(); } } return returnVector; }; template<class KeyType, class ItemType> HashedEntry& HashedDictionary::operator[](KeyType searchKey){ //DO NOT MODIFY int itemHashIndex = getHashIndex(searchKey); HashedEntry *chainPtr = hashTable[itemHashIndex]; // Short circuit evaluation is important here while ((chainPtr != nullptr) && (searchKey != chainPtr->getKey())) { chainPtr = chainPtr->getNext(); } // end while if (chainPtr == nullptr) throw std::exception(); return *chainPtr; }