This is a c++ class utilizing class templates and linked lists. I need to implement the following member function(s) to LinkedBag.cpp. Node.hpp/cpp should be fine but if you feel like there needs to be a change for compilation or testing, feel free to do so but make sure to comment on why it was done.

/** @param a_bag whose contents are to be copied to this (the calling) bag @post this (the calling) bag has same contents as a_bag */

void operator= (const LinkedBag& a_bag);

Node.hpp

----------------------------------------------- /** @file Node.h Listing 4-1 */ #ifndef NODE_ #define NODE_

template class Node { public: Node(); Node(const T& an_item_); Node(const T& an_item, Node* next_node_ptr); void setItem(const T& an_item); void setNext(Node* next_node_ptr); T getItem() const ; Node* getNext() const ;

private: T item_; // A data item_ Node* next_; // Pointer to next_ node }; // end Node

//#include "Node.cpp" //Unsure if this should be included or not #endif -----------------------------------------------

Node.cpp

-----------------------------------------------

#include "Node.hpp" //#include

template Node::Node() : next_(nullptr) { } // end default constructor

template Node::Node(const T& an_item) : item_(an_item), next_(nullptr) { } // end constructor

template Node::Node(const T& an_item, Node* next_node_ptr) : item_(an_item), next_(next_node_ptr) { } // end constructor

template void Node::setItem(const T& an_item) { item_ = an_item; } // end setItem

template void Node::setNext(Node* next_node_ptr) { next_ = next_node_ptr; } // end setNext

template T Node::getItem() const { return item_; } // end getItem

template Node* Node::getNext() const { return next_; } // end getNext

-----------------------------------------------

LinkedBag.hpp

-----------------------------------------------

/** ADT bag: Link-based implementation. @file LinkedBag.h Listing 4-3 */ #ifndef LINKED_BAG_ #define LINKED_BAG_

#include #include #include #include "Node.hpp"

template class LinkedBag { public: LinkedBag(); LinkedBag(const LinkedBag& a_bag); // Copy constructor ~LinkedBag(); // Destructor int getCurrentSize() const; bool isEmpty() const; bool add(const T& new_entry); bool remove(const T& an_entry); void clear(); bool contains(const T& an_entry) const; int getFrequencyOf(const T& an_entry) const; std::vector toVector() const;

private: Node* head_ptr_; // Pointer to first node int item_count_; // Current count of bag items

/** @return Returns either a pointer to the node containing a given entry or the null pointer if the entry is not in the bag. */ Node* getPointerTo(const T& target) const;

}; // end LinkedBag

//#include "LinkedBag.cpp" //Unsure if this should be included or not #endif -----------------------------------------------

LinkedBag.hpp

-----------------------------------------------

#include "LinkedBag.hpp" #include "Node.hpp" #include

template LinkedBag::LinkedBag() : head_ptr_(nullptr), item_count_(0) { } // end default constructor

template LinkedBag::LinkedBag(const LinkedBag& a_bag) { item_count_ = a_bag.item_count_; Node* orig_chain_ptr = a_bag.head_ptr_; // Points to nodes in original chain

if (orig_chain_ptr == nullptr) head_ptr_ = nullptr; // Original bag is empty else { // Copy first node head_ptr_ = new Node(); head_ptr_->setItem(orig_chain_ptr->getItem());

// Copy remaining nodes Node* new_chain_ptr = head_ptr_; // Points to last node in new chain orig_chain_ptr = orig_chain_ptr->getNext(); // Advance original-chain pointer

while (orig_chain_ptr != nullptr) { // Get next item from original chain T next_item = orig_chain_ptr->getItem();

// Create a new node containing the next item Node* new_node_ptr = new Node(next_item);

// Link new node to end of new chain new_chain_ptr->setNext(new_node_ptr);

// Advance pointer to new last node new_chain_ptr = new_chain_ptr->getNext();

// Advance original-chain pointer orig_chain_ptr = orig_chain_ptr->getNext(); } // end while

new_chain_ptr->setNext(nullptr); // Flag end of chain } // end if } // end copy constructor

template LinkedBag::~LinkedBag() { clear(); } // end destructor

template bool LinkedBag::isEmpty() const { return item_count_ == 0; } // end isEmpty

template int LinkedBag::getCurrentSize() const { return item_count_; } // end getCurrentSize

template bool LinkedBag::add(const T& new_entry) { // Add to beginning of chain: new node references rest of chain; // (head_ptr_ is null if chain is empty) Node* next_node_ptr = new Node(); next_node_ptr->setItem(new_entry); next_node_ptr->setNext(head_ptr_); // New node points to chain // Node* next_node_ptr = new Node(new_entry, head_ptr_); // alternate code

head_ptr_ = next_node_ptr; // New node is now first node item_count_++;

return true; } // end add

template std::vector LinkedBag::toVector() const { std::vector bag_contents; Node* cur_ptr = head_ptr_; while ((cur_ptr != nullptr)) { bag_contents.push_back(cur_ptr->getItem()); cur_ptr = cur_ptr->getNext(); } // end while

return bag_contents; } // end toVector

template bool LinkedBag::remove(const T& an_entry) { Node* entry_node_ptr = getPointerTo(an_entry); bool can_remove = !isEmpty() && (entry_node_ptr != nullptr); if (can_remove) { // Copy data from first node to located node entry_node_ptr->setItem(head_ptr_->getItem());

// Delete first node Node* node_to_delete = head_ptr_; head_ptr_ = head_ptr_->getNext();

// Return node to the system node_to_delete->setNext(nullptr); delete node_to_delete; node_to_delete = nullptr;

item_count_--; } // end if

return can_remove; } // end remove

template void LinkedBag::clear() { Node* node_to_delete = head_ptr_; while (head_ptr_ != nullptr) { head_ptr_ = head_ptr_->getNext();

// Return node to the system node_to_delete->setNext(nullptr); delete node_to_delete;

node_to_delete = head_ptr_; } // end while // head_ptr_ is nullptr; node_to_delete is nullptr

item_count_ = 0; } // end clear

template int LinkedBag::getFrequencyOf(const T& an_entry) const { int frequency = 0; int counter = 0; Node* cur_ptr = head_ptr_; while ((cur_ptr != nullptr) && (counter < item_count_)) { if (an_entry == cur_ptr->getItem()) { frequency++; } // end if

counter++; cur_ptr = cur_ptr->getNext(); } // end while

return frequency; } // end getFrequencyOf

template bool LinkedBag::contains(const T& an_entry) const { return (getPointerTo(an_entry) != nullptr); } // end contains

// private

/** @return Returns either a pointer to the node containing a given entry or the null pointer if the entry is not in the bag. */ template Node* LinkedBag::getPointerTo(const T& an_entry) const { bool found = false; Node* cur_ptr = head_ptr_;

while (!found && (cur_ptr != nullptr)) { if (an_entry == cur_ptr->getItem()) found = true; else cur_ptr = cur_ptr->getNext(); } // end while

return cur_ptr; } // end getPointerTo

-----------------------------------------------