Open Address Hash Table and BST

Part A Requirements

For this part, fork the HW 1 Part A project. This program uses an Open Address Hash Table to manage Person objects. To complete this part you'll need to complete the definition of the OpenAddressHashTable class as well as add an Undergraduate class with additional properties. For the hash table, complete the following:

• string generateKey() - this method already works, generating a key with keyLength characters, each a numeric digit or capital letter. Update this method so that it returns a randomized key with only lowercase letters from the alphabet.
• void putValue(string key, S* item) - this method should put the item into the hash table using the appropriate key location. Note, if an item with the key is already in the hash table item should replace it. If it does not exist yet and the hash table is full your function should double the size of the hash table and be sure not to lose any values, and then put the item into the hash table. Therefore, whenever putting an item into the hash table, even if the natural index is available, you'll need to check the whole hash table in case after removal of another item it could result in items not in their natural locations. In other words, this method needs to make sure you don't end up with two items in the table with the same key.
• S* getValue(string key) - this method should get the value in the hash table with the provided key. This method should try to do so efficiently, meaning by looking first at the key's natural hash table index. If not found then, it should search sequentially from that index up (and even wrapped around) until found. If not found, nullptr should be returned.
• void removeValue(string key) - this method should remove the the item in the hash table with the provided key.
• string toString() - this method should return a string containing a textual representation of the hash table. Example output is shown below. Note that the example hash table below would contain four objects, one a Person (John Lennon), one an Employee (Paul McCartney), one a student (George Harrison), and one an Undergraduate (Ringo Starr).

Undergraduates - Note that you should be careful to properly test your hash table. The example test program only does sampled testing, you should add tests to make sure all conditions are considered. In addition to the hash table, define a class called Undergraduate which should be a child class of Student. Undergraduates should have a standing which can be U1, U2, U3, or U4. You may store this data in any format you like. You should add additional tests as well to make sure your Undergraduate test is defined properly. Your Undergraduate class should contain:

[
0: (9CWIYTRB, Paul McCartney ($80000))
1: (4339VBOO, John Lennon)
2: nullptr
3: (103KB7UE, Ringo Starr (U4 - 3.7))
4: (R2YXYZH1, George Harrison (4.0))
]

Part B Requirements

Part B is very much like Part A except we're going to use a binary search tree instead. To start, fork the HW 1 Part B project. You will then need to complete the definition of the BinarySearchTree class, including defining a proper node class such that each node may have a left and/or right node where the tree is always kept in sorted order. Note, the tree does not need to be kept balanced, but nodes should always be added in their proper sorted location. Note that this BST uses nodes, not an array. Complete this part by defining the following:

• void putValue(string key, S* item) - this method should put the item into the BST using the appropriate key location. Note, the BST should be able to accommodate more data as needed. If an item already exists in the table with the same key, this item should replace it.
• S* getValue(string key) - this method should return the value in the tree corresponding to the key argument. If no item is found with the provided key then a nullptr should be returned.
• void removeValue(string key) - this method should find and remove the node with the corresponding key value. Note, you'll need to keep the node's children (if there are any) by promoting the left child, or if there is no left child, promote the right child.
• string toString() - this method should return a string containing a textual representation of the BST that contains the tree values simply listed in sorted order, sorted by key. Example output is shown below. Note that for such a tree, the root node should not be indented, but nodes for each level should be indented 2 additional spaces. So, for example, for a tree with 3 nodes, a root (IH8H14TA) that has a left (81PE5ZDK) child and a right (QA2WZ1E2) child, it would be represented by a string that looks like the example below. So note that the nodes appear in sorted order, but with proper indentation according to their level.

Once you have your linked list and its iterator defined properly let's two new classes: Student and Employee. Note that both of these classes should be child classes of Person, but a Student also has a GPA and an Employee also has a salary. Note that both a GPA and salary should be changeable so you must provide get and set methods for both. You must then provide toString() methods for both to include this information in their respective object summaries.

Finally, change the main.cpp so that George Harrison, and John Lennon are students with GPAs of 4.0 and 3.8, respectively, and Paul McCartney and Ringo Starr are employees earning $80,000 and $40,000, respectively. Do not change the way output is produced except via your own aforementioned toString methods. When you run your program it would now produce the output below.

  (81PE5ZDK, George Harrison (4)) 
(IH8H14TA, Ringo Starr ($40000)) 
  (QA2WZ1E2, Paul McCartney ($80000))

Starter Code

Employee.h

#pragma once

#include < string >
#include < sstream >

using namespace std;

#include "Person.h"

class Employee
: public Person
{
private:
double salary;

public:
Employee(string initKey, string firstName, string lastName, double initSalary)
: Person(initKey, firstName, lastName)
{
this->salary = initSalary;
}

double getSalary()
{
return this->salary;
}

void setSalary(double initSalary)
{
this->salary = initSalary;
}

string toString()
{
stringstream ss;
ss << this->getFirstName() << " " << this->getLastName() << " ($" << this->salary << ")";
return ss.str();
}
};

OpenAddressHashTable.h

#include < stdlib.h >
#include < ctime >
#include < string >
#include < sstream >
using namespace std;

template < class S >
class OpenAddressHashTable
{
class KeyValuePair
{
public:
// INSTANCE VARIABLES
string key;
S* value;

// CONSTRUCTOR
KeyValuePair(string initKey, S* initValue) {
key = initKey;
value = initValue;
}

// DESTRUCTOR
~KeyValuePair() {}

string toString() {
stringstream ss;
ss << "(" << this->key << "," << value->toString() << ")";
return ss.str();
}
};

private:
KeyValuePair** hashTable;
int length;
int size;
int keyLength;

public:

OpenAddressHashTable(int initLength, int initKeyLength)
{
this->length = initLength;
this->size = 0;
keyLength = initKeyLength;
hashTable = new KeyValuePair * [initLength];

for (int i = 0; i < length; i++)
hashTable[i] = nullptr;

srand((unsigned)time(0));
}

// Delete pointers
~OpenAddressHashTable()
{
for (int i = 0; i < length; i++)
if (hashTable[i] != nullptr)
delete hashTable[i];

delete[] hashTable;
}

int getSize()
{
return this->size;
}

int hashCode(string key)
{
int charsSum = 0;

for (auto it = key.cbegin(); it != key.cend(); ++it)
{
int num = (int)(*it);
charsSum += num;
}

return charsSum % length;
}

// @todo - YOU MUST UPDATE THIS METHOD SO A KEY ONLY HAS LOWERCASE LETTERS, NO NUMBERS
string generateKey()
{
}

// @todo - YOU MUST DEFINE THIS METHOD
S* getValue(string key)
{
}

// @todo - YOU MUST DEFINE THIS METHOD
void removeValue(string key)
{
}

// @todo - YOU MUST DEFINE THIS METHOD
void putValue(string key, S* item)
{
}

// @todo - YOU MUST DEFINE THIS METHOD
string toString()
{
}
};

main.cpp (Part A)

// FIRST WE INCLUDE ALL THE THINGS WE PLAN TO USE HERE

// FOR printf
#include < stdio.h >

// FOR cout
#include < iostream >
#include < string >
#include < sstream >
using namespace std;

// OUR STUFF
#include "Person.h"
#include "Student.h"
#include "Employee.h"
#include "Undergraduate.h"
#include "OpenAddressHashTable.h"

const int NUM_BINS = 5;
const int KEY_LENGTH = 8;

void printHashTable(string header, OpenAddressHashTable< Person >* hashTable);
void addPersonToHashTable(Person* person, OpenAddressHashTable< Person >* hashTable);

// EXECUTION OF OUR PROGRAM STARTS HERE
int main()
{
OpenAddressHashTable< Person >* hashTable = new OpenAddressHashTable< Person >(NUM_BINS, KEY_LENGTH);

// DEMONSTRATE ADDING VALUES TO THE HASH TABLE, WHICH INCLUDES THE NEED TO MAKE THE HASH TABLE BIGGER
addPersonToHashTable(new Student(hashTable->generateKey(), "George", "Harrison", 4.0), hashTable);
addPersonToHashTable(new Employee(hashTable->generateKey(), "Paul", "McCartney", 80000), hashTable);
addPersonToHashTable(new Undergraduate(hashTable->generateKey(), "Ringo", "Starr", 3.7, "U4"), hashTable);
addPersonToHashTable(new Person(hashTable->generateKey(), "Chuck", "Berry"), hashTable);
addPersonToHashTable(new Student(hashTable->generateKey(), "Mick", "Jagger", 3.5), hashTable);
addPersonToHashTable(new Student(hashTable->generateKey(), "Jimi", "Hendrix", 3.6), hashTable);
addPersonToHashTable(new Person(hashTable->generateKey(), "Roger", "Waters"), hashTable);

// DEMONSTRATE MAKING KEYS AND ADDING VALUES TO THE HASH TABLE
string jlKey = hashTable->generateKey();
hashTable->putValue(jlKey, new Student(jlKey, "John", "Lennon", 3.8));
string cwKey = hashTable->generateKey();
hashTable->putValue(cwKey, new Student(cwKey, "Charlie", "Watts", 3.1));
string dgKey = hashTable->generateKey();
hashTable->putValue(dgKey, new Employee(dgKey, "David", "Gilmour", 120000));
printHashTable("nAfter Changing 3 Items", hashTable);

// DEMONSTRATE GETTING VALUES FROM THE HASH TABLE
Person* p = hashTable->getValue(jlKey);
cout << endl << "get " << jlKey << ": " << p->toString() << endl;
p = hashTable->getValue(cwKey);
cout << "get " << cwKey << ": " << p->toString() << endl;
p = hashTable->getValue(dgKey);
cout << "get " << dgKey << ": " << p->toString() << endl;


// NOW LET'S TRY REPLACING THE DATA IN THE ABOVE THREE
hashTable->putValue(jlKey, new Student(jlKey, "Otis", "Redding", 3.5));
hashTable->putValue(cwKey, new Student(cwKey, "Keith", "Richards", 3.1));
hashTable->putValue(dgKey, new Student(dgKey, "Bill", "Withers", 3.4));
printHashTable("\nAfter Changing 3 Items", hashTable);

// AND DEMONSTRATE REMOVING ITEMS FROM THE HASH TABLE
hashTable->removeValue(jlKey);
hashTable->removeValue(cwKey);
hashTable->removeValue(dgKey);
printHashTable("\nAfter Removing 3 Items", hashTable);

return 0;
}

void addPersonToHashTable(Person* person, OpenAddressHashTable< Person >* hashTable)
{
hashTable->putValue(person->getKey(), person);
cout << hashTable->toString();
}

void printHashTable(string header, OpenAddressHashTable< Person >* hashTable)
{
string text = hashTable->toString();
cout << header << endl;
cout << text;
}

Person.h

#pragma once

#include < string >
#include < sstream >
using namespace std;

class Person
{
private:
string key;
string firstName;
string lastName;

public:
Person(string initKey, string initFirstName, string initLastName)
{
this->key = initKey;
this->firstName = initFirstName;
this->lastName = initLastName;
}

string getKey()
{
return this->key;
}

void setKey(string initKey)
{
this->key = initKey;
}

string getFirstName()
{
return this->firstName;
}

string getLastName()
{
return this->lastName;
}

virtual string toString()
{
stringstream ss;
ss << this->key << ": " << this->firstName << " " << this->lastName;
return ss.str();
}
};

Student.h

#pragma once

#include < string >
#include < sstream >

using namespace std;

#include "Person.h"

class Student
: public Person
{
private:
double gpa;

public:
Student(string initKey, string firstName, string lastName, double initGPA)
: Person(initKey, firstName, lastName)
{
this->gpa = initGPA;
}

double getGpa()
{
return this->gpa;
}

void setGpa(double initGpa)
{
this->gpa = initGpa;
}

virtual string toString()
{
stringstream ss;
ss << this->getFirstName() << " " << this->getLastName() << " (" << this->gpa << ")";
return ss.str();
}
};

Undergraduate.h

#pragma once

#include < string >
#include < sstream >

using namespace std;

#include "Student.h"

class Undergraduate
: public Student
{
private:
string standing;

public:
Undergraduate(string initKey, string firstName, string lastName, double initGPA, string standing)
: Student(initKey, firstName, lastName, initGPA)
{
this->standing = standing;
}

string getStanding()
{
return standing;
}

void setStanding(string standing)
{
this->standing = standing;
}

string toString()
{
stringstream ss;
ss << this->getFirstName() << " " << this->getLastName() << " (" << this->getStanding() << " - " << this->getGpa() << ")";
return ss.str();
}
};

BinarySearchTree.h

#pragma once

#include < cstdlib >

using namespace std;

template < class T >
class BinarySearchTree
{
// THIS INNER CLASS IS FOR OUR TREE NODES
class Node {
public:
string key;
T* data;
Node* left;
Node* right;

Node(string key, T* data)
{
this->key = key;
this->data = data;
left = nullptr;
right = nullptr;
}
};

private:
Node* root;
int size;
int keyLength;

public:

BinarySearchTree(int initKeyLength)
{
root = nullptr;
size = 0;
this->keyLength = initKeyLength;
}

~BinarySearchTree()
{
deleteNode(root);
}

string generateKey()
{
string key{ "" };
for (int i = 0; i < this->keyLength; i++) {
int randomNum = (rand() % 36);
char randomChar;
if (randomNum < 10) {
randomChar = (char)(randomNum + 48);
}
else {
randomChar = (char)(randomNum + 55);
}
key += randomChar;
}
return key;
}

int getSize() {
return this->size;
}

void putValue(string key, T* data)
{
}

T* getValue(string key)
{
}

void removeValue(string key) {
}

string toString()
{
}

};

main.cpp (Part B)

// FOR printf
#include < stdio.h >

// FOR cout
#include < iostream >
#include < string >
#include < sstream >
using namespace std;

// OUR STUFF
#include "Person.h"
#include "Student.h"
#include "Employee.h"
#include "BinarySearchTree.h"

const int KEY_LENGTH = 8;

void printBST(string header, BinarySearchTree< Person >* tree);
void addPersonToBST(Person* person, BinarySearchTree< Person >* tree);

// EXECUTION OF OUR PROGRAM STARTS HERE
int main()
{
BinarySearchTree< Person >* tree = new BinarySearchTree< Person >(KEY_LENGTH);

// DEMONSTRATE ADDING VALUES TO THE HASH TABLE, WHICH INCLUDES THE NEED TO MAKE THE HASH TABLE BIGGER
addPersonToBST(new Student(tree->generateKey(), "George", "Harrison", 4.0), tree);
addPersonToBST(new Employee(tree->generateKey(), "Paul", "McCartney", 80000), tree);
addPersonToBST(new Employee(tree->generateKey(), "Ringo", "Starr", 40000), tree);
addPersonToBST(new Person(tree->generateKey(), "Chuck", "Berry"), tree);
addPersonToBST(new Student(tree->generateKey(), "Mick", "Jagger", 3.5), tree);
addPersonToBST(new Student(tree->generateKey(), "Jimi", "Hendrix", 3.6), tree);
addPersonToBST(new Person(tree->generateKey(), "Roger", "Waters"), tree);

// DEMONSTRATE MAKING KEYS AND ADDING VALUES TO THE HASH TABLE
string jlKey = tree->generateKey();
tree->putValue(jlKey, new Student(jlKey, "John", "Lennon", 3.8));
string cwKey = tree->generateKey();
tree->putValue(cwKey, new Student(cwKey, "Charlie", "Watts", 3.1));
string dgKey = tree->generateKey();
tree->putValue(dgKey, new Employee(dgKey, "David", "Gilmour", 120000));
printBST("nAfter Changing 3 Items", tree);

// DEMONSTRATE GETTING VALUES FROM THE HASH TABLE
Person* p = tree->getValue(jlKey);
cout << endl << "get " << jlKey << ": " << p->toString() << endl;
p = tree->getValue(cwKey);
cout << "get " << cwKey << ": " << p->toString() << endl;
p = tree->getValue(dgKey);
cout << "get " << dgKey << ": " << p->toString() << endl;

// NOW LET'S TRY REPLACING THE DATA IN THE ABOVE THREE
tree->putValue(jlKey, new Student(jlKey, "Otis", "Redding", 3.5));
tree->putValue(cwKey, new Student(cwKey, "Keith", "Richards", 3.1));
tree->putValue(dgKey, new Student(dgKey, "Bill", "Withers", 3.4));
printBST("\nAfter Changing 3 Items", tree);

// AND DEMONSTRATE REMOVING ITEMS FROM THE TREEE
tree->removeValue(jlKey);
tree->removeValue(cwKey);
tree->removeValue(dgKey);
printBST("\nAfter Removing 3 Items", tree);

return 0;
}

void addPersonToBST(Person* person, BinarySearchTree< Person >* tree)
{
tree->putValue(person->getKey(), person);
cout << tree->toString();
}

void printBST(string header, BinarySearchTree< Person >* tree)
{
string text = tree->toString();
cout << header << endl;
cout << text;
}