· 8 years ago · Jun 14, 2018, 12:56 AM
1//============================================================================
2// Name : HashTable.cpp
3// Author : John Watson
4// Version : 1.0
5// Copyright : Copyright © 2017 SNHU COCE
6// Description : Hello World in C++, Ansi-style
7//============================================================================
8
9#include <algorithm>
10#include <climits>
11#include <iostream>
12#include <string> // atoi
13#include <time.h>
14
15#include "CSVparser.hpp"
16
17using namespace std;
18
19//============================================================================
20// Global definitions visible to all methods and classes
21//============================================================================
22
23const unsigned int DEFAULT_SIZE = 179;
24
25// forward declarations
26double strToDouble(string str, char ch);
27
28// define a structure to hold bid information
29struct Bid {
30 string bidId; // unique identifier
31 string title;
32 string fund;
33 double amount;
34 Bid() {
35 amount = 0.0;
36 }
37};
38
39//============================================================================
40// Hash Table class definition
41//============================================================================
42
43/**
44 * Define a class containing data members and methods to
45 * implement a hash table with chaining.
46 */
47class HashTable {
48
49private:
50 struct Node {
51 Bid bid;
52 unsigned int key;
53 Node *next;
54 // default constructor
55 Node() {
56 key = UINT_MAX;
57 next = nullptr;
58 }
59 // initialize with a bid
60 Node(Bid aBid) : Node() {
61 bid = aBid;
62 }
63 // initialize with a bid and a key
64 Node(Bid aBid, unsigned int aKey) : Node(aBid) {
65 key = aKey;
66 }
67 };
68 vector<Node> nodes;
69 unsigned int tableSize = DEFAULT_SIZE;
70
71 unsigned int hash(int key);
72
73public:
74 HashTable();
75 HashTable(unsigned int size);
76 virtual ~HashTable();
77 void Insert(Bid bid);
78 void PrintAll();
79 void Remove(string bidId);
80 Bid Search(string bidId);
81 size_t Size();
82};
83
84/**
85 * Default constructor
86 */
87HashTable::HashTable() {
88 nodes.resize(tableSize);
89}
90
91
92/**
93 * Destructor
94 */
95HashTable::HashTable(unsigned int size) {
96 this->tableSize = size;
97 nodes.resize(size);
98}
99/**
100 * Calculate the hash value of a given key.
101 * Note that key is specifically defined as
102 * unsigned int to prevent undefined results
103 * of a negative list index.
104 *
105 * @param key The key to hash
106 * @return The calculated hash
107 */
108unsigned int HashTable::hash(int key) {
109 unsigned int hash_value=key%tableSize;
110 return hash_value;
111}
112
113/**
114 * Insert a bid
115 *
116 * @param bid The bid to insert
117 */
118void HashTable::Insert(Bid bid) {
119 unsigned int key = hash(atoi(bid.bidId.c_str()));//hash value for key
120 unsigned int bucket=key;
121 Node* oldNode = &(nodes.at(key));//checks to see if node exists at key
122 unsigned int bucketsProbed=0;
123 while (bucketsProbed<tableSize)
124 if (oldNode == nullptr) {
125 // assign this node to the key position
126 Node* newNode = new Node(bid, key);
127 nodes.insert(nodes.begin() + key, (*newNode));
128 }
129 bucket=(bucket+1)%tableSize;
130 ++bucketsProbed;
131
132 }
133
134
135/**
136 * Print all bids
137 */
138void HashTable::PrintAll() {
139 // FIXME (6): Implement logic to print all bids
140}
141
142/**
143 * Remove a bid
144 *
145 * @param bidId The bid id to search for
146 */
147void HashTable::Remove(string bidId) {
148 unsigned int key = hash(atoi(bidId.c_str()));
149 unsigned int bucket=hash(key);
150 int bucketsProbed=0;
151 unsigned int* EmptyAfterRemoval=nullptr;
152 unsigned int* EmptySinceStart=nullptr;
153 while ((HashTable[bucket] is not EmptySinceStart) and
154 (bucketsProbed<tableSize)){
155 if ((HashTable[bucket] is not Empty) and
156 (HashTable[bucket].key==key)){
157 HashTable[bucket]=EmptyAfterRemoval;
158 return;
159 }
160 bucket=(bucket+1)%tableSize;
161 ++bucketsProbed;
162
163 }
164}
165
166/**
167 * Search for the specified bidId
168 *
169 * @param bidId The bid id to search for
170 */
171Bid HashTable::Search(string bidId) {
172 Bid bid;
173 unsigned int key = hash(atoi(bidId.c_str()));
174 unsigned int bucket=hash(key);
175 int bucketsProbed=0;
176
177 while ((HashTable[bucket] is not EmptySinceStart) and
178 (bucketsProbed<tableSize)){
179 if ((HashTable[bucket] is not Empty) and
180 (HashTable[bucket].key==key)){
181 return HashTable[bucket];
182 }
183 bucket=(bucket+1)%tableSize;
184 ++bucketsProbed;
185 }
186
187 return bid;
188}
189
190//============================================================================
191// Static methods used for testing
192//============================================================================
193
194/**
195 * Display the bid information to the console (std::out)
196 *
197 * @param bid struct containing the bid info
198 */
199void displayBid(Bid bid) {
200 cout << bid.bidId << ": " << bid.title << " | " << bid.amount << " | "
201 << bid.fund << endl;
202 return;
203}
204
205/**
206 * Load a CSV file containing bids into a container
207 *
208 * @param csvPath the path to the CSV file to load
209 * @return a container holding all the bids read
210 */
211void loadBids(string csvPath, HashTable* hashTable) {
212 cout << "Loading CSV file " << csvPath << endl;
213
214 // initialize the CSV Parser using the given path
215 csv::Parser file = csv::Parser(csvPath);
216
217 // read and display header row - optional
218 vector<string> header = file.getHeader();
219 for (auto const& c : header) {
220 cout << c << " | ";
221 }
222 cout << "" << endl;
223
224 try {
225 // loop to read rows of a CSV file
226 for (unsigned int i = 0; i < file.rowCount(); i++) {
227
228 // Create a data structure and add to the collection of bids
229 Bid bid;
230 bid.bidId = file[i][1];
231 bid.title = file[i][0];
232 bid.fund = file[i][8];
233 bid.amount = strToDouble(file[i][4], '$');
234
235 //cout << "Item: " << bid.title << ", Fund: " << bid.fund << ", Amount: " << bid.amount << endl;
236
237 // push this bid to the end
238 hashTable->Insert(bid);
239 }
240 } catch (csv::Error &e) {
241 std::cerr << e.what() << std::endl;
242 }
243}
244
245/**
246 * Simple C function to convert a string to a double
247 * after stripping out unwanted char
248 *
249 * credit: http://stackoverflow.com/a/24875936
250 *
251 * @param ch The character to strip out
252 */
253double strToDouble(string str, char ch) {
254 str.erase(remove(str.begin(), str.end(), ch), str.end());
255 return atof(str.c_str());
256}
257
258/**
259 * The one and only main() method
260 */
261int main(int argc, char* argv[]) {
262
263 // process command line arguments
264 string csvPath, bidKey;
265 switch (argc) {
266 case 2:
267 csvPath = argv[1];
268 bidKey = "98109";
269 break;
270 case 3:
271 csvPath = argv[1];
272 bidKey = argv[2];
273 break;
274 default:
275 csvPath = "eBid_Monthly_Sales_Dec_2016.csv";
276 bidKey = "98109";
277 }
278
279 // Define a timer variable
280 clock_t ticks;
281
282 // Define a hash table to hold all the bids
283 HashTable* bidTable;
284
285 Bid bid;
286
287 int choice = 0;
288 while (choice != 9) {
289 cout << "Menu:" << endl;
290 cout << " 1. Load Bids" << endl;
291 cout << " 2. Display All Bids" << endl;
292 cout << " 3. Find Bid" << endl;
293 cout << " 4. Remove Bid" << endl;
294 cout << " 9. Exit" << endl;
295 cout << "Enter choice: ";
296 cin >> choice;
297
298 switch (choice) {
299
300 case 1:
301 bidTable = new HashTable();
302
303 // Initialize a timer variable before loading bids
304 ticks = clock();
305
306 // Complete the method call to load the bids
307 loadBids(csvPath, bidTable);
308
309 // Calculate elapsed time and display result
310 ticks = clock() - ticks; // current clock ticks minus starting clock ticks
311 cout << "time: " << ticks << " clock ticks" << endl;
312 cout << "time: " << ticks * 1.0 / CLOCKS_PER_SEC << " seconds" << endl;
313 break;
314
315 case 2:
316 bidTable->PrintAll();
317 break;
318
319 case 3:
320 ticks = clock();
321
322 bid = bidTable->Search(bidKey);
323
324 ticks = clock() - ticks; // current clock ticks minus starting clock ticks
325
326 if (!bid.bidId.empty()) {
327 displayBid(bid);
328 } else {
329 cout << "Bid Id " << bidKey << " not found." << endl;
330 }
331
332 cout << "time: " << ticks << " clock ticks" << endl;
333 cout << "time: " << ticks * 1.0 / CLOCKS_PER_SEC << " seconds" << endl;
334 break;
335
336 case 4:
337 bidTable->Remove(bidKey);
338 break;
339 }
340 }
341
342 cout << "Good bye." << endl;
343
344 return 0;
345}