The focus of these problems will be working with information extracted from a municipal government data feed containing bids submitted for auction of property. The data set is provided in two comma-separated files:

1. eBid_Monthly_Sales.csv (larger set of 17,937 bids)
2. eBid_Monthly_Sales_Dec_2016.csv (smaller set of 179 bids)

This assignment is designed to explore hashing algorithms by implementing a hash with chaining of collisions for bids loaded from a CSV file.

We provide a starter console program that uses a menu to enable testing of the hash table logic you will complete. It also allows you to pass in the path to the bids CSV file to be loaded, enabling you to try both files. In this version the following menu is presented when the program is run:

Menu:

1. Load Bids

2. Display All Bids

3. Find Bid

4. Remove Bid

9. Exit

Enter choice:

The HashTable.cpp program is partially completed - it contains empty methods representing the programming interface used to interact with a hash table. You will need to add logic to the methods to implement the necessary behavior. Here is the public API for HashTable that you have to complete:

public:

HashTable();

virtual ~HashTable();

void Insert(Bid bid);

void PrintAll();

void Remove(string bidId);

Bid Search(string bidId);

You will need to perform the following steps to complete this activity:

Setup: Begin by creating a new C++ Project with a Project Type of "Hello World C++ Project"

1. Name the project HashTable, remember to pick the correct compiler in Toolchains and click Finish. This will create a simple HashTable.cpp source file under the /src directory.
2. Download the starter program files and copy them to the projects /src directory, replacing the existing auto-generated one. Remember to right-click on the project in the Project Explorer pane on the left and 'Refresh' the project so it adds all the new files to the src folder underneath.
3. Because this activity uses C++ 11 features you must follow the instructions under C++ Compiler Version in the C++ Development Installation guide to add -std=c++11 compiler switch to the Miscellaneous settings.

Task 1: Define structures to hold bids

Hint: You may choose either an array or a vector for storage. Note that Lab2-2 and Lab4-2 both used vectors for their storage and Lab3-3 used a Node structure for implementing a linked list. Reusing code from these labs may save you time.

Task 2: Initialize the structures used to hold bids

Task 3: Implement logic to free storage when class is destroyed

Task 4: Implement logic to calculate a hash value using the bid Id as the source for calculating the key

Task 5: Implement logic to insert a bid

Be sure to check for key collisions and use the chaining technique with a linked list to store the additional bids

Task 6: Implement logic to print all bids

Task 7: Implement logic to remove a bid

Task 8: Implement logic to search for and return a bid

//============================================================================

#include #include #include #include // atoi #include

#include "CSVparser.hpp"

using namespace std;

//============================================================================ // Global definitions visible to all methods and classes //============================================================================

const unsigned int DEFAULT_SIZE = 179;

// forward declarations double strToDouble(string str, char ch);

// define a structure to hold bid information struct Bid { string bidId; // unique identifier string title; string fund; double amount; Bid() { amount = 0.0; } };

//============================================================================ // Hash Table class definition //============================================================================

/** * Define a class containing data members and methods to * implement a hash table with chaining. */ class HashTable {

private: // FIXME (1): Define structures to hold bids

unsigned int hash(int key);

public: HashTable(); virtual ~HashTable(); void Insert(Bid bid); void PrintAll(); void Remove(string bidId); Bid Search(string bidId); };

/** * Default constructor */ HashTable::HashTable() { // FIXME (2): Initialize the structures used to hold bids }

/** * Destructor */ HashTable::~HashTable() { // FIXME (3): Implement logic to free storage when class is destroyed }

/** * Calculate the hash value of a given key. * Note that key is specifically defined as * unsigned int to prevent undefined results * of a negative list index. * * @param key The key to hash * @return The calculated hash */ unsigned int HashTable::hash(int key) { // FIXME (4): Implement logic to calculate a hash value }

/** * Insert a bid * * @param bid The bid to insert */ void HashTable::Insert(Bid bid) { // FIXME (5): Implement logic to insert a bid }

/** * Print all bids */ void HashTable::PrintAll() { // FIXME (6): Implement logic to print all bids }

/** * Remove a bid * * @param bidId The bid id to search for */ void HashTable::Remove(string bidId) { // FIXME (7): Implement logic to remove a bid }

/** * Search for the specified bidId * * @param bidId The bid id to search for */ Bid HashTable::Search(string bidId) { Bid bid;

// FIXME (8): Implement logic to search for and return a bid

return bid; }

//============================================================================ // Static methods used for testing //============================================================================

/** * Display the bid information to the console (std::out) * * @param bid struct containing the bid info */ void displayBid(Bid bid) { cout << bid.bidId << ": " << bid.title << " | " << bid.amount << " | " << bid.fund << endl; return; }

/** * Load a CSV file containing bids into a container * * @param csvPath the path to the CSV file to load * @return a container holding all the bids read */ void loadBids(string csvPath, HashTable* hashTable) { cout << "Loading CSV file " << csvPath << endl;

// initialize the CSV Parser using the given path csv::Parser file = csv::Parser(csvPath);

// read and display header row - optional vector header = file.getHeader(); for (auto const& c : header) { cout << c << " | "; } cout << "" << endl;

try { // loop to read rows of a CSV file for (unsigned int i = 0; i < file.rowCount(); i++) {

// Create a data structure and add to the collection of bids Bid bid; bid.bidId = file[i][1]; bid.title = file[i][0]; bid.fund = file[i][8]; bid.amount = strToDouble(file[i][4], '$');

//cout << "Item: " << bid.title << ", Fund: " << bid.fund << ", Amount: " << bid.amount << endl;

// push this bid to the end hashTable->Insert(bid); } } catch (csv::Error &e) { std::cerr << e.what() << std::endl; } }

/** * Simple C function to convert a string to a double * after stripping out unwanted char * * credit: http://stackoverflow.com/a/24875936 * * @param ch The character to strip out */ double strToDouble(string str, char ch) { str.erase(remove(str.begin(), str.end(), ch), str.end()); return atof(str.c_str()); }

/** * The one and only main() method */ int main(int argc, char* argv[]) {

// process command line arguments string csvPath, bidKey; switch (argc) { case 2: csvPath = argv[1]; bidKey = "98109"; break; case 3: csvPath = argv[1]; bidKey = argv[2]; break; default: csvPath = "eBid_Monthly_Sales_Dec_2016.csv"; bidKey = "98109"; }

// Define a timer variable clock_t ticks;

// Define a hash table to hold all the bids HashTable* bidTable;

Bid bid;

int choice = 0; while (choice != 9) { cout << "Menu:" << endl; cout << " 1. Load Bids" << endl; cout << " 2. Display All Bids" << endl; cout << " 3. Find Bid" << endl; cout << " 4. Remove Bid" << endl; cout << " 9. Exit" << endl; cout << "Enter choice: "; cin >> choice;

switch (choice) {

case 1: bidTable = new HashTable();

// Initialize a timer variable before loading bids ticks = clock();

// Complete the method call to load the bids loadBids(csvPath, bidTable);

// Calculate elapsed time and display result ticks = clock() - ticks; // current clock ticks minus starting clock ticks cout << "time: " << ticks << " clock ticks" << endl; cout << "time: " << ticks * 1.0 / CLOCKS_PER_SEC << " seconds" << endl; break;

case 2: bidTable->PrintAll(); break;

case 3: ticks = clock();

bid = bidTable->Search(bidKey);

ticks = clock() - ticks; // current clock ticks minus starting clock ticks

if (!bid.bidId.empty()) { displayBid(bid); } else { cout << "Bid Id " << bidKey << " not found." << endl; }

cout << "time: " << ticks << " clock ticks" << endl; cout << "time: " << ticks * 1.0 / CLOCKS_PER_SEC << " seconds" << endl; break;

case 4: bidTable->Remove(bidKey); break; } }

cout << "Good bye." << endl;

return 0; }