Dynamic ADT Implementation help. I need help dynamically implementing these three methods into my main program.

Methods must compose a new Bag object by accessing the elements of the underlying linked list of the Bag objects. You may not convert the Bags to vectors. The main method must also be updated to thoroughly test the newly added methods.

1. bagUnion(): The union of two bags is a new bag containing the combined contents of the original two bags. Design and specify a method union for the LinkedBag that returns as a new bag the union of the bag receiving the call to the method and the bag that is the method's parameter. Note that the union of two bags might contain duplicate items. For example, if object x occurs five times in one bag and twice in another, the union of these bags contains x seven times. The union does not affect the contents of the original bags.

2. bagIntersection(): The intersection of two bags is a new bag containing the entries that occur in both of the original bags. Design and specify a method intersection for the LinkedBag that returns as a new bag the intersection of the bag receiving the call to the method and the bag that is the method's parameter. Note that the intersection of two bags might contain duplicate items. For example, if object x occurs five times in one bag and twice in another, the intersection of these bags contains x two times. The intersection does not affect the contents of the original bags.

3. bagDifference(): The difference of two bags is a new bag containing the entries (from both bag) that would be unique in one bag (not duplicated in its own bag, also not another bag). Design and specify a method difference for the LinkedBag that returns as a new bag the difference from the two bags (the bag receiving the call to the method and the bag that is the method's parameter). Note that the difference of two bags does not contain duplicate items. For example, if object x occurs more than one time in one bag and no in another, the difference of these bags contains x only one time.

For testing the new methods, please output original contents in two bags and clear message for each testing, for example:

Bag 1 contains: 1 2 3 4 5 1

Bag 2 contains: 4 5 6 7 8 8

Test union method 1 2 3 4 5 1 4 5 6 7 8 8

Test intersection method 4 5

Test difference method 1 2 3 6 7 8

BagInterface.h

#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; }; // end BagInterface #endif

Node.h

#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

LinkedBag.h

#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;

//My methods

LinkedBag bagUnion(const LinkedBag &otherBag) const;

LinkedBag bagIntersection(const LinkedBag &otherBag) const;

LinkedBag bagDifference(const LinkedBag &otherBag) const;

}; // end LinkedBag

#include "LinkedBag.cpp"

#endif

Node.cpp

#include "Node.h" #include

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

template Node::Node(const ItemType& anItem) : item(anItem), next(nullptr) { } // end constructor

template Node::Node(const ItemType& anItem, Node* nextNodePtr) : item(anItem), next(nextNodePtr) { } // end constructor

template void Node::setItem(const ItemType& anItem) { item = anItem; } // end setItem

template void Node::setNext(Node* nextNodePtr) { next = nextNodePtr; } // end setNext

template ItemType Node::getItem() const { return item; } // end getItem

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

LinkedBag.cpp

#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

/* ALTERNATE 1

template

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

{

return getFrequencyOf(anEntry) > 0;

}

*/

/* ALTERNATE 2

template

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

{

bool found = false;

Node* curPtr = headPtr;

int i = 0;

while (!found && (curPtr != nullptr) && (i < itemCount))

{

if (anEntry == curPtr-

{

found = true;

}

else

{

i++;

curPtr = curPtr->getNext();

} // end if

} // end while

return found;

} // 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

//My methods

template

LinkedBag LinkedBag::bagUnion(const LinkedBag &otherBag) const

{

LinkedBag uni(*this);//create a bag with this bag's contents

//traverse the other bag and each of the nodes

Node* curPtr = otherBag.headPtr;

while(curPtr != nullptr)

{

uni.add(curPtr->getItem());

curPtr = curPtr->getNext();

}

return uni;

}

template

LinkedBag LinkedBag::bagIntersection(const LinkedBag &otherBag) const

{

int this_count, other_count;

int how_many;

Node* curPtr = otherBag.headPtr;

LinkedBag inter;

while(curPtr != nullptr)

{

if(!inter.contains(curPtr->getItem())) //only if we have not already process the current item

{

//get the counts of the current item in both the bags, and add occurences as many as the lowest of the 2 counts

this_count = getFrequencyOf(curPtr->getItem());

other_count = otherBag.getFrequencyOf(curPtr->getItem());

if(this_count < other_count)

how_many = this_count;

else

how_many = other_count;

for(int i = 1; i <= how_many; i++)

inter.add(curPtr->getItem());

}

}

}

template

LinkedBag LinkedBag::bagDifference(const LinkedBag &otherBag) const

{

int this_count, other_count;

int how_many;

Node* curPtr = otherBag.headPtr;

LinkedBag diff;

while(curPtr != nullptr)

{

if(!diff.contains(curPtr->getItem())) //only if we have not already process the current item

{

//get the counts of the current item in both the bags, and add occurences as many as the lowest of the 2 counts

this_count = getFrequencyOf(curPtr->getItem());

other_count = otherBag.getFrequencyOf(curPtr->getItem());

if(this_count > other_count) //we need to add only if we get 1 or more difference between the counts

{

how_many = this_count - other_count;

for(int i = 1; i <= how_many; i++)

diff.add(curPtr->getItem());

}

}

}

}

BagTester.cpp/main program

#include

#include

#include "LinkedBag.h"

using namespace std;

void displayBag(LinkedBag& bag)

{

cout << "The bag contains " << bag.getCurrentSize()

<< " items:" << endl;

vector bagItems = bag.toVector();

int numberOfEntries = (int) bagItems.size();

for (int i = 0; i < numberOfEntries; i++)

{

cout << bagItems[i] << " ";

} // end for

cout << endl << endl;

} // end displayBag

void copyConstructorTester()

{

LinkedBag bag;

string items[] = {"zero", "one", "two", "three", "four", "five"};

for (int i = 0; i < 6; i++)

{

cout << "Adding " << items[i] << endl;

bool success = bag.add(items[i]);

if (!success)

cout << "Failed to add " << items[i] << " to the bag." << endl;

}

displayBag(bag);

LinkedBag copyOfBag(bag);

cout << "Copy of bag: ";

displayBag(copyOfBag);

cout << "The copied bag: ";

displayBag(bag);

} // end copyConstructorTester

void bagTester()

{

LinkedBag bag;

cout << "Testing the Link-Based Bag:" << endl;

cout << "isEmpty: returns " << bag.isEmpty()

<< "; should be 1 (true)" << endl;

displayBag(bag);

string items[] = {"one", "two", "three", "four", "five", "one"};

cout << "Add 6 items to the bag: " << endl;

for (int i = 0; i < 6; i++)

{

bag.add(items[i]);

} // end for

displayBag(bag);

displayBag(bag);

} // end bagTester

int main()

{

copyConstructorTester();

bagTester();

return 0;

} // end main