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 sort 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 LinkedList that you have to complete:

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

Begin by creating a new C++ Project with a Project Type of "Hello World C++ Project". Name the project 'HashTable' and click Finish. This will create a simple HashTable.cpp source file under the src directory. You can then download the starter program and copy the files to the 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.

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

(1): Define structures to hold bids You may choose either an array or a vector.

(2): Initialize the structures used to hold bids

(3): Implement logic to free storage when class is destroyed

(4): Implement logic to calculate a hash value Use the bid id as the source for calculating the key

(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

(6): Implement logic to print all bids

(7): Implement logic to remove a bid

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

Hint: Lab2-2 and Lab4-2 both used vectors for their storage and Lab3-3 used a Node structure for implementing a linked list.

//============================================================================ // Name : HashTable.cpp //============================================================================

#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; }

#ifndef _CSVPARSER_HPP_

# define _CSVPARSER_HPP_

# include

# include

# include

# include

# include

namespace csv

{

class Error : public std::runtime_error

{

public:

Error(const std::string &msg):

std::runtime_error(std::string("CSVparser : ").append(msg))

{

}

};

class Row

{

public:

Row(const std::vector &);

~Row(void);

public:

unsigned int size(void) const;

void push(const std::string &);

bool set(const std::string &, const std::string &);

private:

const std::vector _header;

std::vector _values;

public:

template

const T getValue(unsigned int pos) const

{

if (pos < _values.size())

{

T res;

std::stringstream ss;

ss << _values[pos];

ss >> res;

return res;

}

throw Error("can't return this value (doesn't exist)");

}

const std::string operator[](unsigned int) const;

const std::string operator[](const std::string &valueName) const;

friend std::ostream& operator<<(std::ostream& os, const Row &row);

friend std::ofstream& operator<<(std::ofstream& os, const Row &row);

};

enum DataType {

eFILE = 0,

ePURE = 1

};

class Parser

{

public:

Parser(const std::string &, const DataType &type = eFILE, char sep = ',');

~Parser(void);

public:

Row &getRow(unsigned int row) const;

unsigned int rowCount(void) const;

unsigned int columnCount(void) const;

std::vector getHeader(void) const;

const std::string getHeaderElement(unsigned int pos) const;

const std::string &getFileName(void) const;

public:

bool deleteRow(unsigned int row);

bool addRow(unsigned int pos, const std::vector &);

void sync(void) const;

protected:

void parseHeader(void);

void parseContent(void);

private:

std::string _file;

const DataType _type;

const char _sep;

std::vector _originalFile;

std::vector _header;

std::vector _content;

public:

Row &operator[](unsigned int row) const;

};

}

#endif /*!_CSVPARSER_HPP_*/

========================================================================= CSVparser.cpp

#include #include #include #include "CSVparser.hpp"

namespace csv {

Parser::Parser(const std::string &data, const DataType &type, char sep) : _type(type), _sep(sep) { std::string line; if (type == eFILE) { _file = data; std::ifstream ifile(_file.c_str()); if (ifile.is_open()) { while (ifile.good()) { getline(ifile, line); if (line != "") _originalFile.push_back(line); } ifile.close();

if (_originalFile.size() == 0) throw Error(std::string("No Data in ").append(_file)); parseHeader(); parseContent(); } else throw Error(std::string("Failed to open ").append(_file)); } else { std::istringstream stream(data); while (std::getline(stream, line)) if (line != "") _originalFile.push_back(line); if (_originalFile.size() == 0) throw Error(std::string("No Data in pure content"));

parseHeader(); parseContent(); } }

Parser::~Parser(void) { std::vector::iterator it;

for (it = _content.begin(); it != _content.end(); it++) delete *it; }

void Parser::parseHeader(void) { std::stringstream ss(_originalFile[0]); std::string item;

while (std::getline(ss, item, _sep)) _header.push_back(item); }

void Parser::parseContent(void) { std::vector::iterator it; it = _originalFile.begin(); it++; // skip header

for (; it != _originalFile.end(); it++) { bool quoted = false; int tokenStart = 0; unsigned int i = 0;

Row *row = new Row(_header);

for (; i != it->length(); i++) { if (it->at(i) == '"') quoted = ((quoted) ? (false) : (true)); else if (it->at(i) == ',' && !quoted) { row->push(it->substr(tokenStart, i - tokenStart)); tokenStart = i + 1; } }

//end row->push(it->substr(tokenStart, it->length() - tokenStart));

// if value(s) missing if (row->size() != _header.size()) throw Error("corrupted data !"); _content.push_back(row); } }

Row &Parser::getRow(unsigned int rowPosition) const { if (rowPosition < _content.size()) return *(_content[rowPosition]); throw Error("can't return this row (doesn't exist)"); }

Row &Parser::operator[](unsigned int rowPosition) const { return Parser::getRow(rowPosition); }

unsigned int Parser::rowCount(void) const { return _content.size(); }

unsigned int Parser::columnCount(void) const { return _header.size(); }

std::vector Parser::getHeader(void) const { return _header; }

const std::string Parser::getHeaderElement(unsigned int pos) const { if (pos >= _header.size()) throw Error("can't return this header (doesn't exist)"); return _header[pos]; }

bool Parser::deleteRow(unsigned int pos) { if (pos < _content.size()) { delete *(_content.begin() + pos); _content.erase(_content.begin() + pos); return true; } return false; }

bool Parser::addRow(unsigned int pos, const std::vector &r) { Row *row = new Row(_header);

for (auto it = r.begin(); it != r.end(); it++) row->push(*it); if (pos <= _content.size()) { _content.insert(_content.begin() + pos, row); return true; } return false; }

void Parser::sync(void) const { if (_type == DataType::eFILE) { std::ofstream f; f.open(_file, std::ios::out | std::ios::trunc);

// header unsigned int i = 0; for (auto it = _header.begin(); it != _header.end(); it++) { f << *it; if (i < _header.size() - 1) f << ","; else f << std::endl; i++; } for (auto it = _content.begin(); it != _content.end(); it++) f << **it << std::endl; f.close(); } }

const std::string &Parser::getFileName(void) const { return _file; } /* ** ROW */

Row::Row(const std::vector &header) : _header(header) {}

Row::~Row(void) {}

unsigned int Row::size(void) const { return _values.size(); }

void Row::push(const std::string &value) { _values.push_back(value); }

bool Row::set(const std::string &key, const std::string &value) { std::vector::const_iterator it; int pos = 0;

for (it = _header.begin(); it != _header.end(); it++) { if (key == *it) { _values[pos] = value; return true; } pos++; } return false; }

const std::string Row::operator[](unsigned int valuePosition) const { if (valuePosition < _values.size()) return _values[valuePosition]; throw Error("can't return this value (doesn't exist)"); }

const std::string Row::operator[](const std::string &key) const { std::vector::const_iterator it; int pos = 0;

for (it = _header.begin(); it != _header.end(); it++) { if (key == *it) return _values[pos]; pos++; } throw Error("can't return this value (doesn't exist)"); }

std::ostream &operator<<(std::ostream &os, const Row &row) { for (unsigned int i = 0; i != row._values.size(); i++) os << row._values[i] << " | ";

return os; }

std::ofstream &operator<<(std::ofstream &os, const Row &row) { for (unsigned int i = 0; i != row._values.size(); i++) { os << row._values[i]; if (i < row._values.size() - 1) os << ","; } return os; } }