#pragma once #include "BagInterface.h" #include "DoubleNode.h"

template class LinkedBag : public BagInterface { private: DoubleNode* headPtr; int itemCount;

DoubleNode* 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; };

#include "LinkedBag.h" #include "DoubleNode.h" #include

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

template LinkedBag::LinkedBag(const LinkedBag& aBag) { itemCount = aBag.itemCount; DoubleNode* 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 DoubleNodeNode* 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) DoubleNode* nextNodePtr = new DoubleNode(); 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 std::vector LinkedBag::toVector() const { std::vector bagContents; DoubleNode* 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) { DoubleNode* 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 DoubleNode* 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() { DoubleNode* 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; DoubleNode* 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); }

#ifndef DOUBLE_NODE_ #define DOUBLE_NODE_ template class DoubleNode { private: ItemType item; // A data item DoubleNode* next; // Pointer to next node DoubleNode* prev; // Pointer to previous node public: DoubleNode(); DoubleNode(const ItemType& anItem); DoubleNode(const ItemType& anItem, DoubleNode* nextNodePtr, DoubleNode* previousNodePtr); void setItem(const ItemType& anItem); ItemType getItem() const; void setNext(DoubleNode* nextNodePtr); DoubleNode* getNext() const; void setPrevious(DoubleNode* previousNodePtr); DoubleNode* getPrevious() const; }; // end DoubleNode

#pragma once #ifndef _BAG_INTERFACE #define _BAG_INTERFACE

#include using namespace std;

template class BagInterface { public:

virtual int getCurrentSize() const = 0;

virtual bool isEmpty() const = 0;

virtual bool add(const ItemType& newEntry) = 0;

virtual bool remove(const ItemType& anEntry) = 0;

virtual void clear() = 0;

virtual int getFrequencyOf(const ItemType& anEntry) const = 0;

virtual bool contains(const ItemType& anEntry) const = 0;

virtual vector toVector() const = 0; }; #endif

#include "DoubleNode.h"

template DoubleNode::DoubleNode() : item(nullptr), next(nullptr) , prev(nullptr) { }

template DoubleNode::DoubleNode(const ItemType& anItem) : item(anItem), next(nullptr), prev(nullptr) { }

template DoubleNode::DoubleNode(const ItemType& anItem, DoubleNode* nextNodePtr, DoubleNode* previousNodePtr) : item(anItem), next(nextNodePtr), prev(previousNodePtr) {

} template void DoubleNode::setItem(const ItemType& anItem) { item = anItem; }

template ItemType DoubleNode::getItem() const { return item; }

template void DoubleNode::setNext(DoubleNode* nextNodePtr) { next = nextNodePtr; }

template DoubleNode* DoubleNode::getNext() const { return next; }

template void DoubleNode::setPrevious(DoubleNode*previousNodePtr) { next = previousNodePtr; }

template DoubleNode* DoubleNode::getPrevious() const { return prev; }

Please help me fixed it. THanks and implement to double linked the chain.