Data Structures (C++) Add these functions to LinkedBag.h and build a main driver to execute the code:(1) Add a value at end of list (2) Delete a value of the list without disrupting its original order (3) Print contents of array (4) Call the Copy Constructor.

/* * * * * * * * LinkedBag File * * * * * * * * */

#ifndef _LINKED_BAG #define _LINKED_BAG #include "BagInterface.h" #include "Node.h"

template class LinkedBag : public BagInterface { private: Node* headPtr; // Pointer to first node int itemCount; // Current count of bag items // 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 ItemType& target) const; public: LinkedBag(); LinkedBag(const LinkedBag& aBag); // Copy constructor virtual ~LinkedBag(); // Destructor should be virtual int getCurrentSize() const; bool isEmpty() const; bool add(const ItemType& newEntry); bool remove(const ItemType& anEntry); void clear(); bool contains(const ItemType& anEntry) const; int getFrequencyOf(const ItemType& anEntry) const; vector toVector() const; bool insertAtEnd(const ItemType& newEntry); //I created this function, it compiles, but may be wrong }; // end LinkedBag //#include "LinkedBag.cpp" #endif

//#include "LinkedBag.h" //#include "Node.h" #include

template LinkedBag::LinkedBag() : headPtr(nullptr), itemCount(0) { } // end default constructor

template LinkedBag::LinkedBag(const LinkedBag& aBag) { itemCount = aBag.itemCount; Node* origChainPtr = aBag.headPtr; // Points to nodes in original chain if (origChainPtr == nullptr) headPtr = nullptr; // Original bag is empty else { // Copy first node headPtr = new Node(); headPtr->setItem(origChainPtr->getItem()); // Copy remaining nodes Node* newChainPtr = headPtr; // Points to last node in new chain origChainPtr = origChainPtr->getNext(); // Advance original-chain pointer while (origChainPtr != nullptr) { // Get next item from original chain ItemType nextItem = origChainPtr->getItem(); // Create a new node containing the next item Node* newNodePtr = new Node(nextItem); // Link new node to end of new chain newChainPtr->setNext(newNodePtr); // Advance pointer to new last node newChainPtr = newChainPtr->getNext(); // Advance original-chain pointer origChainPtr = origChainPtr->getNext(); } // end while newChainPtr->setNext(nullptr); // Flag end of chain } // end if } // end copy constructor

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

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

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

template bool LinkedBag::add(const ItemType& newEntry) { // Add to beginning of chain: new node references rest of chain; // (headPtr is null if chain is empty) Node* nextNodePtr = new Node(); nextNodePtr->setItem(newEntry); nextNodePtr->setNext(headPtr); // New node points to chain // Node* nextNodePtr = new Node(newEntry, headPtr); // alternate code headPtr = nextNodePtr; // New node is now first node itemCount++; return true; } // end add

template vector LinkedBag::toVector() const { vector bagContents; Node* curPtr = headPtr; int counter = 0; while ((curPtr != nullptr) && (counter < itemCount)) { bagContents.push_back(curPtr->getItem()); curPtr = curPtr->getNext(); counter++; } // end while return bagContents; } // end toVector

template bool LinkedBag::remove(const ItemType& anEntry) { Node* entryNodePtr = getPointerTo(anEntry); bool canRemoveItem = !isEmpty() && (entryNodePtr != nullptr); if (canRemoveItem) { // Copy data from first node to located node entryNodePtr->setItem(headPtr->getItem()); // Delete first node Node* nodeToDeletePtr = headPtr; headPtr = headPtr->getNext(); // Return node to the system nodeToDeletePtr->setNext(nullptr); delete nodeToDeletePtr; nodeToDeletePtr = nullptr; itemCount--; } // end if return canRemoveItem; } // end remove

template void LinkedBag::clear() { Node* nodeToDeletePtr = headPtr; while (headPtr != nullptr) { headPtr = headPtr->getNext(); // Return node to the system nodeToDeletePtr->setNext(nullptr); delete nodeToDeletePtr; nodeToDeletePtr = headPtr; } // end while // headPtr is nullptr; nodeToDeletePtr is nullptr itemCount = 0; } // end clear

template int LinkedBag::getFrequencyOf(const ItemType& anEntry) const { int frequency = 0; int counter = 0; Node* curPtr = headPtr; while ((curPtr != nullptr) && (counter < itemCount)) { if (anEntry == curPtr->getItem()) { frequency++; } // end if counter++; curPtr = curPtr->getNext(); } // end while return frequency; } // end getFrequencyOf

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

// private // 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 ItemType& anEntry) const { bool found = false; Node* curPtr = headPtr; while (!found && (curPtr != nullptr)) { if (anEntry == curPtr->getItem()) found = true; else curPtr = curPtr->getNext(); } // end while return curPtr; } // end getPointerTo

template bool LinkedBag::insertAtEnd(const ItemType& newEntry) //I created this function, it compiles, but may be wrong { // Add to end of chain Node* nextNodePtr = new Node(); nextNodePtr->setItem(newEntry); nextNodePtr->setNext(NULL); // New node points to chain // Node* nextNodePtr = new Node(newEntry, headPtr); // alternate code nextNodePtr = headPtr; // New node is now first node if(headPtr = NULL){ headPtr = nextNodePtr; return headPtr; } while (nextNodePtr->setNext() != NULL){ headPtr = headPtr -> setNext(); } headPtr -> setNext() = nextNodePtr; return headPtr; return true; } // end insertAtEnd

/* * * * * * * * BagInterface File * * * * * * * * */

#ifndef _BAG_INTERFACE #define _BAG_INTERFACE

#include using namespace std;

template class BagInterface { public: /** Gets the current number of entries in this bag. @return The integer number of entries currently in the bag. */ virtual int getCurrentSize() const = 0; /** Sees whether this bag is empty. @return True if the bag is empty, or false if not. */ virtual bool isEmpty() const = 0; /** Adds a new entry to this bag. @post If successful, newEntry is stored in the bag and the count of items in the bag has increased by 1. @param newEntry The object to be added as a new entry. @return True if addition was successful, or false if not. */ virtual bool add(const ItemType& newEntry) = 0; /** Removes one occurrence of a given entry from this bag, if possible. @post If successful, anEntry has been removed from the bag and the count of items in the bag has decreased by 1. @param anEntry The entry to be removed. @return True if removal was successful, or false if not. */ virtual bool remove(const ItemType& anEntry) = 0; /** Removes all entries from this bag. @post Bag contains no items, and the count of items is 0. */ virtual void clear() = 0; /** Counts the number of times a given entry appears in bag. @param anEntry The entry to be counted. @return The number of times anEntry appears in the bag. */ virtual int getFrequencyOf(const ItemType& anEntry) const = 0; /** Tests whether this bag contains a given entry. @param anEntry The entry to locate. @return True if bag contains anEntry, or false otherwise. */ virtual bool contains(const ItemType& anEntry) const = 0; /** Empties and then fills a given vector with all entries that are in this bag. @return A vector containing all the entries in the bag. */ virtual vector toVector() const = 0; }; // end BagInterface #endif

/* * * * * * * * * Node File * * * * * * * * * */

#ifndef _NODE #define _NODE

template class Node { private: ItemType item; // A data item Node* next; // Pointer to next node public: Node(); Node(const ItemType& anItem); Node(const ItemType& anItem, Node* nextNodePtr); void setItem(const ItemType& anItem); void setNext(Node* nextNodePtr); ItemType getItem() const ; Node* getNext() const ; }; // end Node

#include "Node.cpp" #endif