How to write the insert, search, and remove functions for this hash table program? I'm stuck...

This program is written in C++

Hash Tables

Hash Table Header File

Copy and paste the following code into a header file named HashTable.h

Please do not alter this file in any way or you may not receive credit for this lab

For this lab, you will implement each of the hash table functions whose prototypes are in HashTable.h.

Write these functions in a file named HashTable.cpp.

Please test each hash table function as you write it in a file named HashTableTest.cpp (which should include your main function).

Additionally, you will need to include your templated, doubly-linked List.h and the files Book.h and Book.cpp from Lab 7 in the same project as your Hash Table.

#ifndef HASHTABLE_H_ #define HASHTABLE_H_ #include #include "List.h" #include "Book.h" using namespace std; class HashTable { public: /**Constructors*/ HashTable(); //constructor ~HashTable();

//destructor

HashTable(const HashTable& ht); //copy constructor /**Access Functions*/ int hash(string key); //returns the hash value for the given key //the hash value is the sum of //of the ASCII values of each char in the key //% the size the of the table //Key for this table: title + author int countBucket(int index); //counts the number of Books at this index //returns the count //pre: 0<= index < SIZE int search(Book b); //Searches for b in the table //returns the index at which b is located //returns -1 if b is not in the table /**Manipulation Procedures*/ void insert(Book b); //inserts a new book into the table //calls the hash function on the key to determine //the correct bucket void remove(Book b); //removes b from the table //calls the hash function on the key to determine //the correct bucket /**Additional Functions*/ void printBucket(int index); //Prints all the books at index //pre: 0<= index < SIZE

//Should print according to the following formula:

//"Printing index

//skips two lines

//Next, prints each book at that index in the format: //

by //$ //ISBN: //followed by a blank line void printTable(); //Prints the first book at each index //along with a count of the total books //at each index by calling count_bucket //as a helper function //Prints in the format: //<-----------------------> //Bucket: //by //$ //ISBN: //Number of books at this bucket: //<-----------------------> private: static const int SIZE = 10; List Table[SIZE]; }; #endif /* HASHTABLE_H_ */

Hash Table Constructor and Destructor

These functions should be left blank in HashTable.cpp.

The List constructor is already called inside of the HashTable.h, at the following line:

List Table;

Likewise, the destructor should be left blank, as the List destructor will automatically be called once Table goes out of scope.

Calling the Hash Function

For the purposes of this assignment, we will be using the algorithm defined in class which sums the ASCII values of all the characters in the string key and scales the result to indices of the table.

You are welcome to use this or an alternate hash algorithm for your course project. However, please use the provided hash algorithm for Lab 8

The key that you should pass to the hash function is the Book's title concatenated with the Book's author. This key should provide enough unique information to differentiate among each book, even if the books have the same title or the same author. If both author and title are the same as another book's title and author, we can assume the book would be a duplicate entry in the table.

Adding Values to the Hash Table

The next step in the process is to be able to add a value to the hash table.

Since we are using the separate chaining approach to collisions, we are using an array of Lists to represent our table.

Each time we insert a new book into the table, we need to complete these steps:

Call the hash function to determine at which index or bucket to place the Book inside the table

Insert the Book at this index of the Table array.

Note that you need to call the correct function from the List class to insert this book onto the end of the chain of books.

Each time you insert a new book, it should be added onto the end of the chain.

Test Values for insert

You can test your insert function by making the following function calls inside main of your Hash_Table_Test.cpp:

HashTable ht; Book pp("Pride and Prejudice", "Jane Austen", 1234567, 4.95); Book c("Contact", "Carl Sagan", 99993339, 9.95); Book hg("The Hunger Games", "Suzanne Collins", 12388888, 13.55); Book hp("Harry Potter", "J.K. Rowlings", 55555678, 12.99); Book mhc("The Man in the High Castle", "Philip K DILL", 95959595, 15.95); Book bh("Bleak House", "Charles DILL", 473890238, 8.00); ht.insert(pp); ht.insert(c); ht.insert(hg); ht.insert(mhc); ht.insert(bh);

Printing Using printBucket:

To verify your Hash Table functions are working properly, you need to be able to print the values contained in the Table.

Therefore, your next step - after writing insert - should be to write a print function.

There are two print functions you need to write for this lab; each one is used in a different way.

printBucket is used to display all of the values stored at a single bucket (a "row" in the table).

In contrast, printTable will display the first value stored at each index or bucket in the table (the "first column" in the table).

The printBucket function will allow us to dig more deeply into what is contained at a particular bucket.

You can think of printTable as providing a vertical cross section of values in the Table whereas printBucket gives us a horizontal cross section.

For example, a call to printBucket(9); in main should display the following (assuming you have inserted the values provided above).

Printing bucket: 9 The Hunger Games by Suzanne Collins $13.55 ISBN: 12388888 The Man in the High Castle by Philip K DILL $15.95 ISBN: 95959595

Printing the Hash Table Using printTable

printTable displays the first value stored at each index in the table.

If you are following along with my example, we want our printTable function to print the following to the console given the values we have already inserted:

<-----------------------> Bucket: 0 Bleak House by Charles DILL $8.00 ISBN#: 473890238 Number of books at this bucket: 1 <-----------------------> <-----------------------> Bucket: 2 Pride and Prejudice by Jane Austen $4.95 ISBN: 1234567 Number of books at this bucket: 1 <-----------------------> <-----------------------> Bucket: 4 Contact by Carl Sagan $9.95 ISBN: 99993339 Number of books at this bucket: 1 <-----------------------> <-----------------------> Bucket: 9 The Hunger Games by Suzanne Collins $13.55 ISBN: 12388888 Number of books at this bucket: 2 <----------------------->

In other words, for each bucket in the table, we are going to output the following to the console:

<-----------------------> Bucket: by $ ISBN : Number of books at this bucket: <----------------------->

Note that this function prints nothing for a bucket containing no books.

Counting items at a bucket using the countBucket function

For this function, you will need to count the number of Books at a specific index or bucket.

Note that this function is a helper to printTable, which provides a tally of how many books are stored at each index as part of its output (see above).

Note that you will need to make use of your cursor from the List class to count how many books are stored at a particular index.

Searching the Table

Our search function will search for a particular book to determine at which bucket it is stored in the Table.

Our first step will be to call the hash function to determine which index the book would be hashed to.

Next, you will need to search through the values at this bucket to determine if the book is stored at that bucket.

Note: It will be sufficient simply to compare the isbn number of the book you are searching for to that of the books stored at that bucket to determine if that book is in the table.

If you find the book, return the bucket or index.

If the book is not in the table, your function should return -1.

Removing a Book from the Table

To remove a book, you will need to complete these steps:

Pass the book's title and author to the hash function to determine at which index this book is located.

Search for the book in the chain at that bucket

Once you have located it, call the appropriate List removal function to remove the book from that bucket .

Here is the List.h :

#ifndef LIST_H_ #define LIST_H_

#include #include #include #include using namespace std;

template class List { private: struct Node { listdata data; Node* next; Node* previous;

Node(listdata data) : data(data), next(NULL), previous(NULL) { } };

typedef struct Node* Nodeptr;

Nodeptr first; Nodeptr last; Nodeptr iterator; void reverse(Nodeptr node); bool isSorted(Nodeptr node); int binarySearch(int low, int high, listdata data); int size; public:

/**Constructors and Destructors*/

List(); //Default constructor; initializes and empty list //Postcondition:create a link list.

List(const List &list);

~List(); //Destructor. Frees memory allocated to the list //Postcondition:frees the memory associated with the linked list.

/**Accessors*/

listdata getFirst(); //Returns the first element in the list //Precondition:first should not be empty.

listdata getLast(); //Returns the last element in the list //Precondition:last should not be empty.

bool isEmpty(); //Determines whether a list is empty.

int getSize(); //Returns the size of the list

/**Manipulation Procedures*/

void removeLast(); //Removes the value of the last element in the list //Precondition:list should not be empty. //Postcondition:Remove the last element of the list.

void removeFirst(); //Removes the value of the first element in the list //Precondition:list should not be empty //Postcondition:Remove the last element of the list.

void insertLast(listdata data); //Inserts a new element at the end of the list //If the list is empty, the new element becomes both first and last //Postcondition:insert the new element at the end of the list.

void insertFirst(listdata data); //Inserts a new element at the start of the list //If the list is empty, the new element becomes both first and last //Postcondition:insert the new element at the beginning of the list.

/**Additional List Operations*/

void printList(); //Prints to the console the value of each element in the list sequentially //and separated by a blank space //Prints nothing if the list is empty

void startIterator(); //postcondition: set the beginning of the element equal to iterator.

void removeIterator(); // postcondition: Remove the iterator.

void insertIterator(listdata data); //precondition: list should not be empty. //postcondition: insert the new iterator.

void advanceIterator();

listdata getIterator();

bool offEnd();

bool operator==(const List &list);

void printReverse(); //Wrapper function that calls the reverse helper function to print a list in reverse //prints nothing if the List is empty

bool isSorted(); //Wrapper function that calls the isSorted helper function to determine whether //a list is sorted in ascending order. //We will consider that a list is trivially sorted if it is empty. //Therefore, no precondition is needed for this function

int getIndex(); //Indicates the index of the Node where the iterator is currently pointing //Nodes are numbered from 1 to size of the list //Pre: size != 0 //Pre: !off_end()

void advanceToIndex(int index); //Moves the iterator to the node whose index number is specified in the parameter //Pre: size != 0 //Pre: index <= size

int linearSearch(listdata data); //Searchs the list, element by element, from the start of the List to the end of the List //Returns the index of the element, if it is found in the List //Calls the above indexing functions in its implementation //Returns -1 if the element is not in the List //Pre: size != 0

int binarySearch(listdata data); //Returns the index where data is located in the List //Calls the private helper function binarySearch to perform the search //Pre: size != 0 //Pre: List is sorted (must test on a sorted list) }; template List::List() : first(NULL), last(NULL), iterator(NULL), size(0) { } template List::List(const List &list) : size(list.size) { if (list.first == NULL) { first = last = iterator = NULL; } else { first = new Node(list.first->data); Nodeptr temp = list.first; iterator = first;

while (temp->next != NULL) { temp = temp->next; iterator->next = new Node(temp->data); iterator = iterator->next;

} last = iterator; iterator = NULL; } } template List::~List() { Nodeptr cursor = first; Nodeptr temp; while (cursor != NULL) { temp = cursor->next;

delete cursor;

cursor = temp; } } template void List::reverse(Nodeptr node) { node = last; while (node->previous != NULL) { cout << node->data << " "; node = node->previous; } cout << first->data << endl; } template void List::printList() { Nodeptr temp = first; while (temp != NULL) {

cout << temp->data << " "; temp = temp->next; } cout << endl; } template void List::printReverse() { Nodeptr temp = last; reverse(temp);

} template void List::insertFirst(listdata data) { if (size == 0) { first = new Node(data); last = first; } else { Nodeptr N = new Node(data); N->next = first; first->previous = N; first = N; } size++; } template void List::insertLast(listdata data) { if (size == 0) { Nodeptr N = new Node(data); first = last = N; } else { Nodeptr N = new Node(data); last->next = N; N->previous = last; last = N; } size++; } template void List::removeFirst() { assert(size != 0); if (size == 1) { delete first; first = last = NULL; size = 0; } else { Nodeptr temp = first; first = first->next; delete temp; first->previous = NULL; size--; } } template void List::removeLast() { assert(size != 0); if (size == 1) { delete last; last = first = NULL; size = 0; }

else {

Nodeptr temp = last; last = last->previous; cout << last->data << endl; delete temp; last->next = NULL; size--; } } template void List::insertIterator(listdata data) { assert(size != 0); assert(iterator!= NULL); if (iterator == last) { insertLast(data); } else { Nodeptr N = new Node(data); N->next = iterator->next; N->previous = iterator; iterator->next->previous = N; iterator->next = N; } size++; } template void List::startIterator() { iterator = first; } template void List::advanceIterator() { assert(iterator != NULL); assert(size != 0); iterator = iterator->next; } template void List::removeIterator() { assert(iterator != NULL); assert(size != 0);

if (size == 1) { delete iterator; iterator = first = last = NULL; size = 0; } else if (iterator == first) { removeFirst(); } else if (iterator == last) { removeLast(); } else { iterator->previous->next = iterator->next; iterator->next->previous = iterator->previous; delete iterator; iterator = NULL; size--; } } template void List::advanceToIndex(int index) {

assert(size != 0); assert(index <= size); iterator = first; for (int i = 1; i < index; i++) { iterator = iterator->next; } }

template int List::getIndex() { assert(size != 0); assert(!offEnd()); Nodeptr n = first; int count = 1; while (n != iterator) { n = n->next; count++; } return count; } template bool List::isEmpty() { return (size == 0); } template int List::getSize() { return size; } template listdata List::getFirst() { assert(first != NULL); return first->data; } template listdata List::getLast() { assert(last != NULL); return last->data; } template bool List::offEnd() { if (iterator == NULL) { return true; } else { return false; } }

template listdata List::getIterator() { assert(iterator!= NULL); return iterator->data; } template bool List::operator==(const List &list) { if (size != list.size) return false; Nodeptr temp1 = first; Nodeptr temp2 = list.first; while (temp1 != NULL) { if (temp1->data != temp2->data) return false; temp1 = temp1->next; temp2 = temp2->next; } return true; } template bool List::isSorted(Nodeptr node) { if(node == last) { return true; } else if((node->data) > (node->next->data)) { return false; } else { return isSorted(node->next); } } template int List::binarySearch(int low, int high, listdata data) { if (high < low) { return -1; } int mid = low + (high - low) / 2;

advanceToIndex(mid);

if (getIterator() == data) { return mid; } else if (getIterator() > data) { return binarySearch(low, mid - 1, data); } else { return binarySearch(mid + 1, high, data); } } template bool List::isSorted() { Nodeptr temp = first; return isSorted(temp); } template int List::linearSearch(listdata data) { assert(size != 0); int count = 0; Nodeptr N = first; while (N != NULL) { count++; if (N->data == data) { cout << count << endl; return count; } N = N->next; } return -1; } template int List::binarySearch(listdata data) { assert(size != 0); assert(isSorted()); return binarySearch(1, size, data); } #endif /* LIST_H_ */

Here is the Books.h:

#include #include

#include

using namespace std;

class Book { private: string title; string author; unsigned isbn; double price;

public:

/**Constructors*/ Book(); Book(string t, string a, unsigned i, double p);

/**Access Functions*/ string get_title(); string get_author(); unsigned get_isbn(); double get_price();

/**Manipulation Procedures*/ void set_title(string t); void set_author(string a); void set_isbn(unsigned i); void set_price(double p);

/**Additional Functions*/

friend ostream& operator<<(ostream& os, const Book& book); //prints out a book to the designated stream in the following format //

by //$ //isbn # //note that the << is required to be a friend function, not a member function //note2: do not print out the <> as part of the output

bool operator==(const Book& book); //compares two books to determine if they are the same book

bool operator<(const Book& book); //compares two books to determine if one comes before the other //alphabetically by title and secondarily by author if the two //books contain the same title //returns false if the two books are the same

bool operator>(const Book& book); //compares two books to determine if one comes after the other //alphabetically by title and secondarily by author if the two //books contain the same title //returns false if the two books are the same

};

Book::Book():title(""), author(""), isbn(0), price(0.0){};

Book::Book(string t, string a, unsigned i, double p) { title = t; author = a; isbn = i; price = p; }

/**Access Functions*/

string Book::get_title() { return title; }

string Book::get_author() { return author; }

unsigned Book::get_isbn() { return isbn; }

double Book::get_price() { return price; }

/**Manipulation Procedures*/

void Book::set_title(string t){ title = t; }

void Book::set_author(string a) { author = a; }

void Book::set_isbn(unsigned i) { isbn = i; }

void Book::set_price(double p) { price = p; }

/**Additional Functions*/

bool Book::operator==(const Book& book) { return (title == book.title && author==book.author); }

bool Book::operator<(const Book& book) { //compares two books to determine if one comes before the other //alphabetically by title and secondarily by author if the two //books contain the same title //returns false if the two books are the same if(title == book.title && author==book.author) { return false; } else { return (title < book.title && author < book.author); } }

bool Book::operator>(const Book& book) { if(title == book.title && author==book.author) { return false; } else { return (title > book.title && author > book.author); } } ostream& operator<<(ostream& os, const Book& book)

{ os << "title:" << book.title << "/n " << "author:" << book.author << "/n" << "price:" << book.price << "/n" << "ISBN:" << book.isbn; return os;

}

#endif /* BOOK_H_ */