//============================================================================ // Name : BinarySearchTree.cpp // Author : JYour name // Version : 1.0 // Copyright : Copyright 2017 SNHU COCE // Description : Hello World in C++, Ansi-style //============================================================================

#include #include

#include "CSVparser.hpp"

using namespace std;

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

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

// Internal structure for tree node struct Node { Bid bid; Node *left; Node *right;

// default constructor Node() { left = nullptr; right = nullptr; }

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

//============================================================================ // Binary Search Tree class definition //============================================================================

/** * Define a class containing data members and methods to * implement a binary search tree */ class BinarySearchTree {

private: Node* root;

void addNode(Node* node, Bid bid); void inOrder(Node* node); Node* removeNode(Node* node, string bidId);

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

/** * Default constructor */ BinarySearchTree::BinarySearchTree() { // FixMe (1): initialize housekeeping variables //root is equal to nullptr }

/** * Destructor */ BinarySearchTree::~BinarySearchTree() { // recurse from root deleting every node }

/** * Traverse the tree in order */ void BinarySearchTree::InOrder() { // FixMe (2): In order root // call inOrder fuction and pass root }

/** * Traverse the tree in post-order */ void BinarySearchTree::PostOrder() { // FixMe (3): Post order root // postOrder root }

/** * Traverse the tree in pre-order */ void BinarySearchTree::PreOrder() { // FixMe (4): Pre order root // preOrder root }

/** * Insert a bid */ void BinarySearchTree::Insert(Bid bid) { // FIXME (5) Implement inserting a bid into the tree // if root equarl to null ptr // root is equal to new node bid // else // add Node root and bid }

/** * Remove a bid */ void BinarySearchTree::Remove(string bidId) { // FIXME (6) Implement removing a bid from the tree // remove node root bidID }

/** * Search for a bid */ Bid BinarySearchTree::Search(string bidId) { // FIXME (7) Implement searching the tree for a bid // set current node equal to root

// keep looping downwards until bottom reached or matching bidId found // if match found, return current bid

// if bid is smaller than current node then traverse left // else larger so traverse right Bid bid; return bid; }

/** * Add a bid to some node (recursive) * * @param node Current node in tree * @param bid Bid to be added */ void BinarySearchTree::addNode(Node* node, Bid bid) { // FIXME (8) Implement inserting a bid into the tree // if node is larger then add to left // if no left node // this node becomes left // else recurse down the left node // else // if no right node // this node becomes right //else // recurse down the left node } void BinarySearchTree::inOrder(Node* node) { // FixMe (9): Pre order root //if node is not equal to null ptr //InOrder not left //output bidID, title, amount, fund //InOder right } void BinarySearchTree::postOrder(Node* node) { // FixMe (10): Pre order root //if node is not equal to null ptr //postOrder left //postOrder right //output bidID, title, amount, fund

}

void BinarySearchTree::preOrder(Node* node) { // FixMe (11): Pre order root //if node is not equal to null ptr //output bidID, title, amount, fund //postOrder left //postOrder right }

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

/** * 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, BinarySearchTree* bst) { cout

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

try { // loop to read rows of a CSV file for (unsigned int i = 0; 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

// push this bid to the end bst->Insert(bid); } } catch (csv::Error &e) { std::cerr

/** * 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 binary search tree to hold all bids BinarySearchTree* bst; bst = new BinarySearchTree(); Bid bid;

int choice = 0; while (choice != 9) { cout > choice;

switch (choice) {

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

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

//cout Size()

// Calculate elapsed time and display result ticks = clock() - ticks; // current clock ticks minus starting clock ticks cout

case 2: bst->InOrder(); break;

case 3: ticks = clock();

bid = bst->Search(bidKey);

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

if (!bid.bidId.empty()) { displayBid(bid); } else { cout

cout

break;

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

cout

return 0; }

This assignment is designed to explore linked lists, so you will implement a singly linked list to hold a collection of 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 BinarySearchTree.cpp program is partially completed. It contains empty methods representing the programming interface used to interact with a binary search tree. You will need to add logic to the methods to implement the necessary behavior. Here is the public API for BinarySearchTree.cpp that you have to complete: public: BinarySearchTree(); virtual BinarySearchTree(); void Insert(Bid bid); void Remove(string bidId); Bid Search(string bidId); Prompt 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". a. Name the project "BinarySearchTree". Remember to pick the correct compiler in Toolchains and click Finish. This will create a simple BinarySearchTree.cpp source file under the /src directory. b. Download the starter program files and copy them to the project's /src directory, replacing the existing auto-generated ones. 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. c. Because this activity uses C++11 features, you may need to add the -std=c++11 compiler switch to the miscellaneous settings. Task 1: Define structures for tree node and housekeeping variables. Task 2: Implement inserting a bid into the tree. Task 3: Implement removing a bid from the tree. Task 4: Implement searching the tree for a bid. Task 5: Complete the function to display all bids. Note that you may be able to reuse a portion of your code from a previous assignment to save you time. Look for where you have used a Node structure to implement a linked list. Here is sample output from running the completed program: > ./BinarySearchTree /Downloads/eBid_Monthly_Sales.csv > BinarySearchTree.exe Downloads\eBid_Monthly_Sales.csv Load bids from CSV and display the hash table contents: Your submission must address the following rubric criteria: - Code Reflection: A brief explanation of the code and its purpose, and a brief discussion of your experience in developing it, including any issues that you encountered while completing the exercise and what approaches you took to solve them - Pseudocode or Flowchart: A pseudocode or flowchart description of the code that is clear and understandable and captures accurate logic to translate to the programming language - Specifications and Correctness: Source code must meet its specifications and behave as desired. Correct code produces the correct output as defined by the data and problem; however, you should also produce fully functioning code (with no errors) that aligns with as many of the specifications as possible. You should write your code in such a way that the submitted file executes, even if it does not produce the correct output. You will be given credit for partially correct output that can be viewed and seen to be partially correct. - Annotation / Documentation: All code should also be well-commented. This is a practiced art that requires striking a balance between commenting everything, which adds a great deal of unneeded noise to the code, and commenting nothing. Well-annotated code requires you to: - Explain the purpose of lines or sections of your code, detailing the approach and method you took to achieve a specific task in the code. - Document any section of code that is producing errors or incorrect results. - Modular and Reusable: Programmers should develop code that is modular and reusable. If it contains functionality and responsibility in distinct methods, code is more flexible and maintainable. Your code should adhere to the single responsibility principle-classes and methods should do only one job. If you can replace a method with another that uses a different technique or implementation without impacting (having to refactor or rewrite) other parts of your code, then you have succeeded in creating modular methods. - Readability: Code needs to be readable to a knowledgeable programmer. In this course, readable code requires: - Consistent, appropriate whitespace (blank lines, spaces) and indentation to separate distinct parts of the code and operations - Explicit, consistent variable names, which should clearly indicate the data they hold and be formatted consistently: for example, numOrders (camelCase) or item_cost (underscored) - Organized structure and clear design that separates components with different responsibilities or grouping-related code into blocks Guidelines for Submission To complete this assignment, submit the CPP code files and a code reflection and associated pseudocode or flowchart. Your written portion should be 1-2 paragraphs in length. Submit the written portion by typing in the Text Submission box, and submit the code as a separate file attachment