Codes:

LinkedBagTest.cpp code:

#include "LinkedBag.h"

#include

#include

#include

void printVector(vector& v)

{

for (vector::iterator i = v.begin(); i != v.end(); ++i)

{

cout

}

cout

}

int main()

{

LinkedBag bag;

cout

cout

bag.add("aa");

bag.add("bb");

bag.add("cc");

bag.add("dd");

bag.add("aa");

cout

cout

cout

vector v = bag.toVector();

printVector(v);

cout

bag.remove("aa");

bag.remove("cc");

cout

v = bag.toVector();

printVector(v);

} // end main

LinkedBag.h code:

#ifndef LINKED_BAG_

#define LINKED_BAG_

#include

#include

#include "Node.h"

using namespace std;

class LinkedBag

{

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(); // Default constructor

// Copy constructor

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 new chain

} // end if

} // end copy constructor

~LinkedBag(); // Destructor

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;

}; // end LinkedBag

#endif

LinkedBag.cpp code:

#include "LinkedBag.h"

LinkedBag::LinkedBag() : headPtr(nullptr), itemCount(0)

{

} // end default constructor

bool LinkedBag::add(const ItemType& newEntry)

{

// (headPtr is null if chain is empty)

Node* nextNodePtr = new Node();

nextNodePtr->setItem(newEntry);

nextNodePtr->setNext(headPtr); // New node points to chain

// alternate code: Node* nextNodePtr = new Node(newEntry, headPtr);

headPtr = nextNodePtr; // New node is now first node

itemCount++;

return true; // The method is always successful

} // end add

int LinkedBag::getCurrentSize() const

{

return itemCount;

} // end getCurrentSize

bool LinkedBag::isEmpty() const

{

return itemCount == 0;

} // end isEmpty

int LinkedBag::getFrequencyOf(const ItemType& anEntry) const

{

int frequency = 0;

int counter = 0;

Node* curPtr = headPtr;

while ((curPtr != nullptr) && (counter

{

if (anEntry == curPtr->getItem())

{

frequency++;

} // end if

counter++;

curPtr = curPtr->getNext();

} // end while

return frequency;

} // end getFrequencyOf

// Returns either a pointer to the node containing a given entry

// or the null pointer if the entry is not in the bag.

Node* LinkedBag::getPointerTo(const ItemType& target) const

{

bool found = false;

Node* curPtr = headPtr;

while (!found && (curPtr != nullptr))

{

if (target == curPtr->getItem())

found = true;

else

curPtr = curPtr->getNext();

} // end while

return curPtr;

} // end getPointerTo

bool LinkedBag::contains(const ItemType& anEntry) const

{

return (getPointerTo(anEntry) != nullptr);

} // end contains

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

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

vector LinkedBag::toVector() const

{

std::vector bagContents;

Node* curPtr = headPtr;

int counter = 0;

while ((curPtr != nullptr) && (counter

{

bagContents.push_back(curPtr->getItem());

curPtr = curPtr->getNext();

counter++;

} // end while

return bagContents;

} // end toVector

LinkedBag::~LinkedBag()

{

clear();

} // end destructor

Node.cpp code:

#include "Node.h"

Node::Node() : next(nullptr)

{

} // end default constructor

Node::Node(const ItemType& anItem) : item(anItem), next(nullptr)

{

} // end constructor

Node::Node(const ItemType& anItem, Node* nextNodePtr) :

item(anItem), next(nextNodePtr)

{

} // end constructor

void Node::setItem(const ItemType& anItem)

{

item = anItem;

} // end setItem

void Node::setNext(Node* nextNodePtr)

{

next = nextNodePtr;

} // end setNext

ItemType Node::getItem() const

{

return item;

} // end getItem

Node* Node::getNext() const

{

return next;

} // end getNext

Node.h code:

#include "Node.h"

Node::Node() : next(nullptr)

{

} // end default constructor

Node::Node(const ItemType& anItem) : item(anItem), next(nullptr)

{

} // end constructor

Node::Node(const ItemType& anItem, Node* nextNodePtr) :

item(anItem), next(nextNodePtr)

{

} // end constructor

void Node::setItem(const ItemType& anItem)

{

item = anItem;

} // end setItem

void Node::setNext(Node* nextNodePtr)

{

next = nextNodePtr;

} // end setNext

ItemType Node::getItem() const

{

return item;

} // end getItem

Node* Node::getNext() const

{

return next;

} // end getNext

For this project, we will add to the LinkedBag class we discussed in class. Code for the LinkedBag has been posted. Add the following 3 methods to the LinkedBag class: LinkedBag union (const LinkedBag&otherBag) Returns a new LinkedBag that has the contents of the calling bag combined with the contents of bag otherBag Calling bag Other Bag New Bag (order does not matter) LinkedBag intersection (const LinkedBag& otherBag) Returns a new LinkedBag that has only those elements that are in both the calling bag and in otherBag. Calling bag Other Bag New Bag (order does not matter) LinkedBag difference (const LinkedBag& otherBag) Returns a new LinkedBag that has the contents of the calling bag with any item removed that also occurs in otherBag Calling bag Other Bag New Bag (order does not matter) Note: You will need the Copy Constructor for the LinkedBag class as discussed in class