Dynamic ADT Implementation help. I need help fixing my BagTester.cpp/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: /** 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 f ills 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.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

#include

#include

#include "LinkedBag.h"

using namespace std;

void displayBag(LinkedBag& bag);

void bagTester(LinkedBag& bag);

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)

{

/*

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

*/

LinkedBag sack; //a sack is a bag too, right?

LinkedBag newBag;

cout << " Populating first bag... ";

int a[] = {1,1,2,4,5,3,7,8,9,1,1,6};

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

bag.add(a[i]);

cout << "done." << endl;

displayBag(bag);

cout << " Creating second bag and populating... ";

int b[] = {20, 30, 40, 50, 1, 18, 1, 15, 9, 8, 7, 2};

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

sack.add(b[i]);

cout << "done." << endl;

displayBag(sack);

cout << " Testing the union of the two bags: " << endl;

newBag = bag.bagUnion(sack);

displayBag(newBag);

cout << "Done. Testing the difference of the first bag from the second: " << endl;

newBag = bag.bagDifference(sack);

displayBag(newBag);

cout << "Done. Testing the difference of the second bag from the first: " << endl;

newBag = sack.bagDifference(bag);

displayBag(newBag);

cout << "Done. Testing the intersection of the two bags: " << endl;

newBag = bag.bagIntersection(sack);

displayBag(newBag);

} // end bagTester

int main()

{

LinkedBag bag;

copyConstructorTester();

bagTester(bag);

return 0;

} // end main