Question

C++ only please

Description

A hash table is a data structure that is used to store keys/value pairs. It is perfect to use when you have a large amount of directory-type information and the operations you need to perform are to insert, delete, print, and search.

I am giving you all a lot more freedom in this program in that the value held in your hash table can be a pointer to any object created from your own custom class.

Files to Be Included In Your Submission

• HashTable.h – header file containing your HashTable class template.

• HashEntry.h – header file containing your HashEntry class template.

• Classname.h – the specification header file containing your class declaration (name it the same name as your class)

• Classname.cpp – the implementation file for your class (name it the same name as your class)

• dataFile.txt – a text file containing the data specific to the class you create. It should have enough data to create 10 objects. (you get 10 points subtracted if you forget to do this!)

• Main.cpp – contains the main function and any additional functions you created to make the program run

main program (main.cpp)

• Must contain the main function as well as four other functions.

• The main function should DYNAMICALLY create a new HashTable object of size 10, which should be created with the template type being a pointer to an object of your custom class.
  HashTable *myTable = new HashTable(10);

• You should have a menu of options to add data from a file, add one object manually, search for an object, delete an object, print the hash table, or end the program.

• Validate the user’s choice.

• Call the appropriate function depending on their choice.

  • You should have one function that will read in data from the file, DYNAMICALLY create an object of your custom class type, and then add this object to the hash table.

  • You should have another function that will allow the user to enter in an object’s data manually and then create an object from this data, and then add to the hash table.

  • The third function should allow the user to search for an object in the hash table.

  • The forth function should allow a user to delete an object from the hash table.

YOUR CUSTOM CLASS (CLASSNAME.H & CLASSNAME.CPP)

Whatever you choose for your class, your objects created from this class MUST have an integer idNum, (which will be used as the key in the hash table) and at least two other attributes. You should write appropriate functions for this class that you will need. You should also have a function that will overload the << (insertion operator) so that the HashTable class can print out your object data in the way that you want.

HASH TABLE TEMPLATE CLASS (HASHTABLE.H)

Your HashTable class must be a template class. The attributes include an integer table size and a pointer to an array of pointers to HashEntry.

You must implement the following functions for HashTable class:

• Constructor – dynamically allocate the hash table of the parameter size and initialize other variables as necessary.

• Destructor – release memory that was dynamically allocated in the HashTable class

• T getValue(int key) – send in a key, return the value in the hash table at that key

• void putValue(int key, T value) – inserts into the hash table using the hash function key%10.

• void removeValue(int key) – removes a value at the given key in the hash table

• void printHashTable() – prints out the hash table in a way that is easy to see which bucket objects were placed in and also indicates which buckets are still NULL

HASH ENTRY TEMPLATE CLASS (HASHENTRY.H)

Your HashEntry class must be a template class, which describes an entry into the hash table. The attributes include an integer key, and the value is of the template type. Also, since the HashTable class will be using chaining, then you will also have a pointer to the next HashEntry as an attribute.

You must implement the following functions for HashEntry class:

• Constructor – initializes the key, value, and next pointer. The key & value is sent to the constructor

• Getter functions (to get the key, to get the value, to get next pointer value)

• Setter functions (setNext & setValue)

Sample Output (I used the creature class for my class)

CREATURE MANAGEMENT MENU

1. Add Creatures From File

2. Add Creature Manually

3. Search for Creature

4. Delete a Creature

5. Print Hash Table

6. End Program

CHOOSE 1-6: 1

Entering creature with ID 797 and name Banshee

Entering creature with ID 841 and name Beholder

Entering creature with ID 988 and name Mike Wazowski

Entering creature with ID 412 and name Sasquatch

Entering creature with ID 358 and name Troll

Entering creature with ID 325 and name Unicorn

6 creatures from creatureFile.txt have been added to the hash table.

CREATURE MANAGEMENT MENU

1. Add Creatures From File

2. Add Creature Manually

3. Search for Creature

4. Delete a Creature

5. Print Hash Table

6. End Program

CHOOSE 1-6: 2

KEY: Siren

Invalid key. Must be an integer.

KEY: 111

NAME: Siren

DESCRIPTION: Beautiful, horrible monster

LIFE POINTS: 3945

HIT POINTS: 344

CREATURE MANAGEMENT MENU

1. Add Creatures From File

2. Add Creature Manually

3. Search for Creature

4. Delete a Creature

5. Print Hash Table

6. End Program

CHOOSE 1-6: 5

----------

BUCKET 0 NULL

BUCKET 1 ---->ID: 841, NAME: Beholder---->ID: 111, NAME: Siren

BUCKET 2 ---->ID: 412, NAME: Sasquatch

BUCKET 3 NULL

BUCKET 4 NULL

BUCKET 5 ---->ID: 325, NAME: Unicorn

BUCKET 6 NULL

BUCKET 7 ---->ID: 797, NAME: Banshee

BUCKET 8 ---->ID: 988, NAME: Mike Wazowski---->ID: 358, NAME: Troll

BUCKET 9 NULL

----------

CREATURE MANAGEMENT MENU

1. Add Creatures From File

2. Add Creature Manually

3. Search for Creature

4. Delete a Creature

5. Print Hash Table

6. End Program

CHOOSE 1-6: 2

KEY: 781

NAME: Pumpkin Face

DESCRIPTION: Horrible pumpkin-looking monster who likes to eat children.

LIFE POINTS: 321

HIT POINTS: 3945

CREATURE MANAGEMENT MENU

1. Add Creatures From File

2. Add Creature Manually

3. Search for Creature

4. Delete a Creature

5. Print Hash Table

6. End Program

CHOOSE 1-6: 5

----------

BUCKET 0 NULL

BUCKET 1 ---->ID: 841, NAME: Beholder---->ID: 111, NAME: Siren---->ID: 781, NAME: Pumpkin Face

BUCKET 2 ---->ID: 412, NAME: Sasquatch

BUCKET 3 NULL

BUCKET 4 NULL

BUCKET 5 ---->ID: 325, NAME: Unicorn

BUCKET 6 NULL

BUCKET 7 ---->ID: 797, NAME: Banshee

BUCKET 8 ---->ID: 988, NAME: Mike Wazowski---->ID: 358, NAME: Troll

BUCKET 9 NULL

----------

CREATURE MANAGEMENT MENU

1. Add Creatures From File

2. Add Creature Manually

3. Search for Creature

4. Delete a Creature

5. Print Hash Table

6. End Program

CHOOSE 1-6: 3

What is the key of the creature you are searching for? 3

There are no creatures with that key in the table.

CREATURE MANAGEMENT MENU

1. Add Creatures From File

2. Add Creature Manually

3. Search for Creature

4. Delete a Creature

5. Print Hash Table

6. End Program

CHOOSE 1-6: 3

What is the key of the creature you are searching for? 358

ID: 358

NAME: Troll

DESCRIPTION:

Ugly and big. Sometimes smell bad.

LIFE POINTS: 1500

HIT POINTS: 80

CREATURE MANAGEMENT MENU

1. Add Creatures From File

2. Add Creature Manually

3. Search for Creature

4. Delete a Creature

5. Print Hash Table

6. End Program

CHOOSE 1-6: 4

The following is a list of all the creatures you take care of:

----------

BUCKET 0 NULL

BUCKET 1 ---->ID: 841, NAME: Beholder---->ID: 111, NAME: Siren---->ID: 781, NAME: Pumpkin Face

BUCKET 2 ---->ID: 412, NAME: Sasquatch

BUCKET 3 NULL

BUCKET 4 NULL

BUCKET 5 ---->ID: 325, NAME: Unicorn

BUCKET 6 NULL

BUCKET 7 ---->ID: 797, NAME: Banshee

BUCKET 8 ---->ID: 988, NAME: Mike Wazowski---->ID: 358, NAME: Troll

BUCKET 9 NULL

----------

What is the ID of the creature you wish to remove?

CREATURE ID: 358

You have removed the creature.

CREATURE MANAGEMENT MENU

1. Add Creatures From File

2. Add Creature Manually

3. Search for Creature

4. Delete a Creature

5. Print Hash Table

6. End Program

CHOOSE 1-6: 5

----------

BUCKET 0 NULL

BUCKET 1 ---->ID: 841, NAME: Beholder---->ID: 111, NAME: Siren---->ID: 781, NAME: Pumpkin Face

BUCKET 2 ---->ID: 412, NAME: Sasquatch

BUCKET 3 NULL

BUCKET 4 NULL

BUCKET 5 ---->ID: 325, NAME: Unicorn

BUCKET 6 NULL

BUCKET 7 ---->ID: 797, NAME: Banshee

BUCKET 8 ---->ID: 988, NAME: Mike Wazowski

BUCKET 9 NULL

----------

CREATURE MANAGEMENT MENU

1. Add Creatures From File

2. Add Creature Manually

3. Search for Creature

4. Delete a Creature

5. Print Hash Table

6. End Program

CHOOSE 1-6: 6

GOODBYE!!

Answer 1

HashTable.h

#pragma once
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include "HashEntry.h"
template<class T>
class HashTable {
private:
   HashEntry<T> **tablepointer;
   int size;
   int count;
public:
   HashTable();
   HashTable(int size);
   void setsize(int s);
   int getsize();
   void putValue(int key, T val);
   void remove(int key);
   T getValue(int key);
   void printTable();
   ~HashTable();
};
template<class T>
HashTable<T>::HashTable()
{
   tablepointer = new HashEntry<T>*[10];
   size = 10;
   for (int i = 0; i < size; i++)
   {
       tablepointer[i] = NULL;
   }
   count = 0;
}
template<class T>
HashTable<T>::HashTable(int s)
{
   tablepointer = new HashEntry<T>*[s];
   size = s;
   for (int i = 0; i < size; i++)
   {
       tablepointer[i] = NULL;
   }
   count = 0;
}
template<class T>
void HashTable<T>::setsize(int s)
{
   size = s;
}
template<class T>
int HashTable<T>::getsize()
{
   return size;
}

template<class T>
void HashTable<T>::putValue(int key, T val)
{
   int pos = key % size;
   HashEntry<T> *newentry = new HashEntry<T>(key,val);
   if (tablepointer[pos] == NULL)
   {
       tablepointer[pos] = newentry;
   }
   else
   {
       HashEntry<T> *temp = tablepointer[pos];
       while (temp->getNext() != NULL)
       {
           temp = temp->getNext();
       }

       temp->setNext(newentry);
       newentry->setPrev(temp);
   }
   count++;
}

template<class T>
void HashTable<T>::remove(int key)
{
   int pos = key % size;
   bool flag = false;
   if (tablepointer[pos] != NULL)
   {

       HashEntry<T> *temp = tablepointer[pos];
       while (temp != NULL)
       {
           if (temp->getKey() == key)
           {
               flag = true;
               break;
           }
       }
       if (flag)
       {
           HashEntry<T> *prevtemp = temp->getPrev();
           HashEntry<T> *nexttemp = temp->getNext();
           if (prevtemp == NULL)
           {
               tablepointer[pos] = nexttemp;
           }
           else
           {
               prevtemp->setNext(nexttemp);
           }
           if (nexttemp != NULL)
           {
               nexttemp->setPrev(prevtemp);
           }
           cout << "Value removed : " << temp->getValue() << endl;
           count--;
       }
       else
       {
           cout << "Entry not found in the hash table\n";
       }
   }
}

template<class T>
T HashTable<T>::getValue(int key)
{
   int pos = key % size;
   if (tablepointer[pos] != NULL)
   {
       HashEntry<T> *temp = tablepointer[pos];
       while (temp != NULL)
       {
           if (temp->getKey() == key)
           {
               return temp->getValue();
           }
           temp = temp->getNext();
       }
   }
   return T();
}

template<class T>
void HashTable<T>::printTable()
{
   cout << "Count of elements : " << count << endl;
   for (int i = 0; i < size; i++)
   {
       HashEntry<T> *temp = tablepointer[i];
       cout << "BUCKET " << i;
       if (temp == NULL)
       {
           cout << "-->NULL" << endl;
       }
       else {

           while (temp != NULL)
           {
               cout << "-->" << temp->getValue();
               temp = temp->getNext();
           }
       }
       cout << endl;

   }
}

template<class T>
HashTable<T>::~HashTable()
{
   delete(tablepointer);
}

#endif // HASHTABLE_H

HashEntry.h

#pragma once
#ifndef HASHENTRY_H
#define HASHTENTRY_H

template<class T>
class HashEntry {
   T value;
   int key;
   HashEntry<T> *next;
   HashEntry<T> *prev;
public:
   HashEntry()
   {
       key = -1;
       next = NULL;
       prev = NULL;
   }
   HashEntry(int key_temp, T value_temp)
   {
       value = value_temp;
       key = key_temp;
       next = NULL;
       prev = NULL;
   }
   int getKey()
   {
       return key;
   }
   T getValue()
   {
       return value;
   }
   HashEntry<T>* getNext()
   {
       return next;
   }
   HashEntry<T>* getPrev()
   {
       return prev;
   }
   void setValue(T value_temp)
   {
       value = value_temp;
   }
   void setNext(HashEntry<T>* next_temp)
   {
       next = next_temp;
   }
   void setPrev(HashEntry<T>* prev_temp)
   {
       prev = prev_temp;
   }
};
#endif // HASHENTRY_H
Item.h//Classname.h

#pragma once
#pragma once
#ifndef ITEM_H
#define ITEM_H
#include<string>
using namespace std;
class Item {
private:
   int id;
   string name;
   int quan;

public:

   Item();
   Item(int id_temp, string name_temp, int quan_temp);
   int getId();
   void setId(int id_temp);
   string getName();
   void setName(string name_temp);
   int getQuan();
   void setQuan(int quan_temp);
   friend ostream & operator << (ostream &out, const Item &i);
   friend istream & operator >> (istream &in, Item &i);

};
#endif

Item.cpp//Classname.cpp

#pragma once
#include "Item.h"
#include <iostream>
using namespace std;
Item::Item()
{
   name = "";
   quan = 0;
}

Item::Item(int id_temp, string name_temp, int quan_temp)
{
   id = id_temp;
   name = name_temp;
   quan = quan_temp;
}

int Item::getId()
{
   return id;
}

void Item::setId(int id_temp)
{
   id = id_temp;
}

string Item::getName()
{
   return name;
}

void Item::setName(string name_temp)
{
   name = name_temp;
}

int Item::getQuan()
{
   return quan;
}

void Item::setQuan(int quan_temp)
{
   quan = quan_temp;
}

ostream & operator<<(ostream & out, const Item & i)
{
   out << "Item ID : " << i.id << ",";
   out << "Item Name : " << i.name << ",";
   out << "Item Quantity : " << i.quan << "\t";
   out << endl;
   return out;
}

istream & operator>>(istream & in, Item & i)
{
   cout << "\nEnter Item id : ";
   in >> i.id;
   cout << "\nEnter Name : ";
   in >> i.name;
   cout << "\nEnter Quantity :";
   in >> i.quan;
   return in;
}
Main.cpp

// Main.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <fstream>
#include "Item.h"
#include "HashTable.h"
using namespace std;

HashTable<Item> *myTable = new HashTable<Item>(10);

void readingFromfile() {
   string path;
   cout << "Enter path :";
   cin >> path;

   fstream file;
   file.open(path);
   string line;
   int id;
   string name;
   int quan;
   while (!file.eof())
   {
       file >> id >> name >> quan;
       Item temp(id, name, quan);
       myTable->putValue(temp.getId(), temp);
   }
   file.close();
}
void AddingManually() {
   Item temp;
   cin >> temp;
   myTable->putValue(temp.getId(), temp);
}
void Search() {
   int id;
   cout << "Enter Item Id" << endl;
   cin >> id;

   if (myTable->getValue(id).getName() == "")
   {
       cout << "Item not found" << endl;
   }
   else
   {

       cout << myTable->getValue(id);
   }
}
void Remove() {
   int id;
   cout << "Enter Item Id" << endl;
   cin >> id;
   myTable->remove(id);
}
int main()
{
   //HashTable<Item> table(10);

   while (true)
   {
       cout << "1. Add From File \n2.Add Manually\n3. Search \n4. Delete \n5. Print Hash Table \n6. End Program\n";
       int choice;
       cin >> choice;
       switch (choice)
       {
       case 1:
       {
           readingFromfile();
           break;
       }
       case 2:
       {
           AddingManually();
           break;
       }
       case 3:
       {
           Search();
           break;
       }
       case 4:
       {
           Remove();
           break;
       }
       case 5:
       {
           myTable->printTable();
           break;
       }
       case 6:
       {
           return 1;
       }
       }
   }
}
dataFile.txt

1001 Pencil 25
34 File 35

OUTPUT:

1. Add From File
2.Add Manually
3. Search
4. Delete
5. Print Hash Table
6. End Program
1
Enter path :data.txt
1. Add From File
2.Add Manually
3. Search
4. Delete
5. Print Hash Table
6. End Program
5
Count of elements : 2
BUCKET 0-->NULL

BUCKET 1-->Item ID : 1001,Item Name : Pencil,Item Quantity : 25

BUCKET 2-->NULL

BUCKET 3-->NULL

BUCKET 4-->Item ID : 34,Item Name : File,Item Quantity : 35

BUCKET 5-->NULL

BUCKET 6-->NULL

BUCKET 7-->NULL

BUCKET 8-->NULL

BUCKET 9-->NULL

1. Add From File
2.Add Manually
3. Search
4. Delete
5. Print Hash Table
6. End Program
2

Enter Item id : 56

Enter Name : Spray

Enter Quantity :54
1. Add From File
2.Add Manually
3. Search
4. Delete
5. Print Hash Table
6. End Program
3
Enter Item Id
56
Item ID : 56,Item Name : Spray,Item Quantity : 54
1. Add From File
2.Add Manually
3. Search
4. Delete
5. Print Hash Table
6. End Program
4
Enter Item Id
1001
Value removed : Item ID : 1001,Item Name : Pencil,Item Quantity : 25

1. Add From File
2.Add Manually
3. Search
4. Delete
5. Print Hash Table
6. End Program
5
Count of elements : 2
BUCKET 0-->NULL

BUCKET 1-->NULL

BUCKET 2-->NULL

BUCKET 3-->NULL

BUCKET 4-->Item ID : 34,Item Name : File,Item Quantity : 35

BUCKET 5-->NULL

BUCKET 6-->Item ID : 56,Item Name : Spray,Item Quantity : 54

BUCKET 7-->NULL

BUCKET 8-->NULL

BUCKET 9-->NULL

1. Add From File
2.Add Manually
3. Search
4. Delete
5. Print Hash Table
6. End Program
6