#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: // Define structures to hold bids struct Node { Bid bid; unsigned int key; Node *next;

// default constructor Node() { key = UINT_MAX; next = nullptr; }

// initialize with a bid Node(Bid aBid) : Node() { bid = aBid; }

// initialize with a bid and a key Node(Bid aBid, unsigned int aKey) : Node(aBid) { key = aKey; } };

vector nodes;

unsigned int tableSize = DEFAULT_SIZE;

unsigned int hash(int key);

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

/** * Default constructor */ HashTable::HashTable() { // FIXME (1): Initialize the structures used to hold bids // Initalize node structure by resizing tableSize nodes.resize(tableSize); }

/** * Constructor for specifying size of the table * Use to improve efficiency of hashing algorithm * by reducing collisions without wasting memory. */ HashTable::HashTable(unsigned int size) { // invoke local tableSize to size with this-> // resize nodes size }

/** * Destructor */ HashTable::~HashTable() { // FIXME (2): Implement logic to free storage when class is destroyed // erase nodes beginning nodes.erase(nodes.begin()); }

/** * 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 (3): Implement logic to calculate a hash value // return key tableSize return key % tableSize; }

/** * Insert a bid * * @param bid The bid to insert */ void HashTable::Insert(Bid bid) { // FIXME (5): Implement logic to insert a bid // create the key for the given bid unsigned int key = hash(atoi(bid.bidId.c_str())); // retrieve node using key Node* node = &nodes[key]; // if no entry found for the key if (node->key == UINT_MAX) { // assign this node to the key position node->bid = bid; node->key = key; } // else if node is not used else if (node->key == UINT_MAX) { // assing old node key to UNIT_MAX, set to key, set old node to bid and old node next to null pointer node->key = UINT_MAX; node->next = new Node(bid, key); } // else find the next open node else{ Node * curr = node; while (curr->next != nullptr) { curr = curr->next; } // add new newNode to end curr->next = new Node(bid, key); }

/** * Print all bids */ void HashTable::PrintAll() { // FIXME (6): Implement logic to print all bids // for node begin to end iterate for (unsigned int i = 0; i key != UINT_MAX) { // output key, bidID, title, amount and fund cout key bid.bidId bid.title bid.amount bid.fund next; // while node not equal to nullptr while (node !+ nullptr) { // output key, bidID, title, amount and fund cout key bid.bidId bid.title bid.amount bid.fund next; } } }

}

/** * Remove a bid * * @param bidId The bid id to search for */ void HashTable::Remove(string bidId) { // FIXME (7): Implement logic to remove a bid // set key equal to hash atoi bidID cstring unsigned int key = hash(atoi(bidId.c_str())); // erase node begin and key nodes.erase(nodes.begin() + key); }

/** * 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

// create the key for the given bid unsigned int key = hash(atoi(bidId.c_str())); // if entry found for the key if (nodes[key].key != UINT_MAX) { //return node bid return nodes[key].bid; }

// if no entry found for the key // return bid Bid bid; // while node not equal to nullptr Node* node = nodes[key].next; while (node != nullptr) { // if the current node matches, return it if (node->bid.bidId == bidId) { /ode is equal to next node node = node->next; } } return bid; }

Prompt For this milestone, you will be creating pseudocode for loading data into a hash table and then using it to store and print that data. There will be no programming work in this milestone; you will be developing pseudocode that will help you implement your design in a future milestone. Please note: Throughout this milestone we are going to use the word "course" to refer to the courses in the curriculum versus "class," which has another meaning in object-oriented programming. For this milestone, you will: 1. Design pseudocode to define how the program opens the file, reads the data from the file, parses each line, and checks for file format errors. The Course Information document, linked in the Supporting Materials section, contains all the information about all of the courses required in the Computer Science curriculum for ABCU. Each line will consist of the information about a single course, including the course number, title, and prerequisites. The Course Information document includes the course data and a diagram of how the program will execute. Your pseudocode will need to validate the sample file to ensure it is formatted correctly and check for the following: - Ensure there are at least two parameters on each line (some courses may not have any prerequisites). - Ensure any prerequisite that is provided on a line exists as a course in the file. In other words, any prerequisite at the end of a line must have another line in the file that starts with that courseNumber. 2. Design pseudocode to show how to create course objects and store them in the appropriate data structure. Your pseudocode should show how to create course objects, so that one course object holds data from a single line from the input file. This should load the data into the hash table data structure. Knowing the file format will help you parse and store each token of data into the appropriate course instance variable. Hint: A loop will be needed to process all lines from the file. 3. Design pseudocode that will print out course information and prerequisites. In the Pseudocode Document, linked in the Supporting Materials section, pseudocode for printing course information using a vector data structure is provided as an example. Develop the pseudocode for printing course information for the hash table data structure using the base code that has been provided. What to Submit To complete this milestone, you must submit the following: Pseudocode Your submission should include your completed pseudocode formatted as a Word Document