The BinarySearchTree.cpp program is partially completed - it contains empty meth
ID: 3907024 • Letter: T
Question
The BinarySearchTree.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 BinarySearchTree that you have to complete:
public:
BinarySearchTree();
virtual ~BinarySearchTree();
void Insert(Bid bid);
void Remove(string bidId);
Bid Search(string bidId);
//============================================================================
// 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;
}
};
// FIXME (1): Internal structure for tree node
struct Node {
};
//============================================================================
// 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() {
// initialize housekeeping variables
}
/**
* Destructor
*/
BinarySearchTree::~BinarySearchTree() {
// recurse from root deleting every node
}
/**
* Traverse the tree in order
*/
void BinarySearchTree::InOrder() {
}
/**
* Insert a bid
*/
void BinarySearchTree::Insert(Bid bid) {
// FIXME (2a) Implement inserting a bid into the tree
}
/**
* Remove a bid
*/
void BinarySearchTree::Remove(string bidId) {
// FIXME (4a) Implement removing a bid from the tree
}
/**
* Search for a bid
*/
Bid BinarySearchTree::Search(string bidId) {
// FIXME (3) Implement searching the tree for a bid
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 (2b) Implement inserting a bid into the tree
}
void BinarySearchTree::inOrder(Node* node) {
}
//============================================================================
// 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, BinarySearchTree* bst) {
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
bst->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 binary search tree to hold all bids
BinarySearchTree* bst;
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:
bst = new BinarySearchTree();
// Initialize a timer variable before loading bids
ticks = clock();
// Complete the method call to load the bids
loadBids(csvPath, bst);
//cout << bst->Size() << " bids read" << endl;
// 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:
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 << "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:
bst->Remove(bidKey);
break;
}
}
cout << "Good bye." << endl;
return 0;
}
========================== CSVparser.cpp ===========================
#include <fstream>
#include <sstream>
#include <iomanip>
#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<Row *>::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<std::string>::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<std::string> 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<std::string> &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<std::string> &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<std::string>::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<std::string>::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;
}
}
=============================== CSVparser.hpp ===============================
#ifndef _CSVPARSER_HPP_
# define _CSVPARSER_HPP_
# include <stdexcept>
# include <string>
# include <vector>
# include <list>
# include <sstream>
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<std::string> &);
~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<std::string> _header;
std::vector<std::string> _values;
public:
template<typename T>
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<std::string> 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<std::string> &);
void sync(void) const;
protected:
void parseHeader(void);
void parseContent(void);
private:
std::string _file;
const DataType _type;
const char _sep;
std::vector<std::string> _originalFile;
std::vector<std::string> _header;
std::vector<Row *> _content;
public:
Row &operator[](unsigned int row) const;
};
}
#endif /*!_CSVPARSER_HPP_*/
Explanation / Answer
struct Bid {
string bidId; // unique identifier
string title;
string fund;
double amount;
Bid() {
amount = 0.0;
}
};
struct Node {
Bid data;
Node *left;
Node *right;
};
BinarySearchTree::BinarySearchTree() {
// initialize housekeeping variables
root = NULL;
}
void Node::DestroyRecursive(Node node)
{
if (node)
{
DestroyRecursive(node->left);
DestroyRecursive(node->right);
delete node;
}
}
BinarySearchTree::~BinarySearchTree() {
DestroyRecursive(node->root);
}
void BinarySearchTree::InOrder() {
if (root != NULL)
{
inorder(root->left);
cout << root->data.bidId);
inorder(root->right);
}
}
Node * minValueNode(Node* node)
{
Node* current = node;
while (current->left != NULL)
current = current->left;
return current;
}
Node* BinarySearchTree::deleteNode(Node *root,string bidId) {
if (root == NULL) return root;
if (bidId < root->data.bidId)
root->left = deleteNode(root->right,bidId);
else if (bidId > root->data.bidId)
root->right = deleteNode(root->right, bidId);
else
{
if (root->left == NULL)
{
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
struct node *temp = root->left;
free(root);
return temp;
}
struct node* temp = minValueNode(root->right);
root->data.bidId = temp->data.bidId;
root->right = deleteNode(root->right, temp->data.bidId);
}
}
void BinarySearchTree::Remove(string bidId) {
// FIXME (4a) Implement removing a bid from the tree
deleteNode(root,bidid);
}
Bid BinarySearchTree::Search(string bidId) {
// FIXME (3) Implement searching the tree for a bid
Bid bid;
if (root == NULL || root->data.bidId == bidId){
bid.bidId = bidId;
bid.title = root->data.title;
bid.fund = root->data.fund;
bid.amount = root->data.amount;
return bid;
}
if (root->data.bidId < bidId)
return search(root->right, bidId);
return search(root->left, bidId);
return bid;
}
Node *newNode(Bid bid)
{
Node *temp = (Node *)malloc(sizeof(Node));
temp->data.bid = bid.bidId;
temp->data.title = bid.title;
temp->data.amount = bid.amount;
temp->data.fund = bid.fund;
temp->left = temp->right = NULL;
return temp;
}
Node* BinarySearchTree::insertNode(Node* node, Bid bid) {
// FIXME (2b) Implement inserting a bid into the tree
if (node == NULL) return newNode(bid);
if (bid.bidId < node->data.bidId)
node->left = insertNode(node->left, bid);
else
node->right = insertNode(node->right, bid);
}
void BinarySearchTree::Insert(Bid bid) {
// FIXME (2a) Implement inserting a bid into the tree
Node p = insertNode(root, bid)
p->data.bidId = bid.bidId;
p->data.title = bid.title;
p->data.fund = bid.fund;
p->daat.amount = bid.amount;
}
void BinarySearchTree::addNode(Node* node, Bid bid) {
// FIXME (2b) Implement inserting a bid into the tree
Node p = insertNode(node, bid)
p->data.bidId = bid.bidId;
p->data.title = bid.title;
p->data.fund = bid.fund;
p->daat.amount = bid.amount;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.