Dynamic ADT Implementation help. I need help fixing my BagTester.cpp/main progra
ID: 3587768 • Letter: D
Question
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 <vector>
using namespace std;
template<class ItemType>
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<ItemType> toVector() const = 0;
}; // end BagInterface
#endif
Node.h
#ifndef _NODE
#define _NODE
template<class ItemType>
class Node
{
private:
ItemType item; // A data item
Node<ItemType>* next; // Pointer to next node
public:
Node();
Node(const ItemType& anItem);
Node(const ItemType& anItem, Node<ItemType>* nextNodePtr);
void setItem(const ItemType& anItem);
void setNext(Node<ItemType>* nextNodePtr);
ItemType getItem() const ;
Node<ItemType>* getNext() const ;
}; // end Node
#include "Node.cpp"
#endif
LinkedBag.h
#ifndef _LINKED_BAG
#define _LINKED_BAG
#include "BagInterface.h"
#include "Node.h"
template<class ItemType>
class LinkedBag : public BagInterface<ItemType>
{
private:
Node<ItemType>* 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<ItemType>* getPointerTo(const ItemType& target) const;
public:
LinkedBag();
LinkedBag(const LinkedBag<ItemType>& 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<ItemType> toVector() const;
//My methods
LinkedBag<ItemType> bagUnion(const LinkedBag<ItemType> &otherBag) const;
LinkedBag<ItemType> bagIntersection(const LinkedBag<ItemType> &otherBag) const;
LinkedBag<ItemType> bagDifference(const LinkedBag<ItemType> &otherBag) const;
}; // end LinkedBag
#include "LinkedBag.cpp"
#endif
Node.cpp
#include "Node.h"
#include <cstddef>
template<class ItemType>
Node<ItemType>::Node() : next(nullptr)
{
} // end default constructor
template<class ItemType>
Node<ItemType>::Node(const ItemType& anItem) : item(anItem), next(nullptr)
{
} // end constructor
template<class ItemType>
Node<ItemType>::Node(const ItemType& anItem, Node<ItemType>* nextNodePtr) :
item(anItem), next(nextNodePtr)
{
} // end constructor
template<class ItemType>
void Node<ItemType>::setItem(const ItemType& anItem)
{
item = anItem;
} // end setItem
template<class ItemType>
void Node<ItemType>::setNext(Node<ItemType>* nextNodePtr)
{
next = nextNodePtr;
} // end setNext
template<class ItemType>
ItemType Node<ItemType>::getItem() const
{
return item;
} // end getItem
template<class ItemType>
Node<ItemType>* Node<ItemType>::getNext() const
{
return next;
} // end getNext
LinkedBag.cpp
#include "LinkedBag.h"
#include "Node.h"
#include <cstddef>
template<class ItemType>
LinkedBag<ItemType>::LinkedBag() : headPtr(nullptr), itemCount(0)
{
} // end default constructor
template<class ItemType>
LinkedBag<ItemType>::LinkedBag(const LinkedBag<ItemType>& aBag)
{
itemCount = aBag.itemCount;
Node<ItemType>* 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<ItemType>();
headPtr->setItem(origChainPtr->getItem());
// Copy remaining nodes
Node<ItemType>* 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<ItemType>* newNodePtr = new Node<ItemType>(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<class ItemType>
LinkedBag<ItemType>::~LinkedBag()
{
clear();
} // end destructor
template<class ItemType>
bool LinkedBag<ItemType>::isEmpty() const
{
return itemCount == 0;
} // end isEmpty
template<class ItemType>
int LinkedBag<ItemType>::getCurrentSize() const
{
return itemCount;
} // end getCurrentSize
template<class ItemType>
bool LinkedBag<ItemType>::add(const ItemType& newEntry)
{
// Add to beginning of chain: new node references rest of chain;
// (headPtr is null if chain is empty)
Node<ItemType>* nextNodePtr = new Node<ItemType>();
nextNodePtr->setItem(newEntry);
nextNodePtr->setNext(headPtr); // New node points to chain
// Node<ItemType>* nextNodePtr = new Node<ItemType>(newEntry, headPtr); // alternate code
headPtr = nextNodePtr; // New node is now first node
itemCount++;
return true;
} // end add
template<class ItemType>
vector<ItemType> LinkedBag<ItemType>::toVector() const
{
vector<ItemType> bagContents;
Node<ItemType>* 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<class ItemType>
bool LinkedBag<ItemType>::remove(const ItemType& anEntry)
{
Node<ItemType>* 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<ItemType>* 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<class ItemType>
void LinkedBag<ItemType>::clear()
{
Node<ItemType>* 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<class ItemType>
int LinkedBag<ItemType>::getFrequencyOf(const ItemType& anEntry) const
{
int frequency = 0;
int counter = 0;
Node<ItemType>* 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<class ItemType>
bool LinkedBag<ItemType>::contains(const ItemType& anEntry) const
{
return (getPointerTo(anEntry) != nullptr);
} // end contains
/* ALTERNATE 1
template<class ItemType>
bool LinkedBag<ItemType>::contains(const ItemType& anEntry) const
{
return getFrequencyOf(anEntry) > 0;
}
*/
/* ALTERNATE 2
template<class ItemType>
bool LinkedBag<ItemType>::contains(const ItemType& anEntry) const
{
bool found = false;
Node<ItemType>* curPtr = headPtr;
int i = 0;
while (!found && (curPtr != nullptr) && (i < itemCount))
{
if (anEntry == curPtr-<getItem())
{
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<class ItemType>
Node<ItemType>* LinkedBag<ItemType>::getPointerTo(const ItemType& anEntry) const
{
bool found = false;
Node<ItemType>* 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<class ItemType>
LinkedBag<ItemType> LinkedBag<ItemType>::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<ItemType>* curPtr = otherBag.headPtr;
while(curPtr != nullptr)
{
uni.add(curPtr->getItem());
curPtr = curPtr->getNext();
}
return uni;
}
template<class ItemType>
LinkedBag<ItemType> LinkedBag<ItemType>::bagIntersection(const LinkedBag &otherBag) const
{
int this_count, other_count;
int how_many;
Node<ItemType>* 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<class ItemType>
LinkedBag<ItemType> LinkedBag<ItemType>::bagDifference(const LinkedBag &otherBag) const
{
int this_count, other_count;
int how_many;
Node<ItemType>* 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 <iostream>
#include <string>
#include "LinkedBag.h"
using namespace std;
void displayBag(LinkedBag<int>& bag);
void bagTester(LinkedBag<int>& bag);
void displayBag(LinkedBag<string>& bag)
{
cout << "The bag contains " << bag.getCurrentSize()
<< " items:" << endl;
vector<string> 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<string> 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<string> copyOfBag(bag);
cout << "Copy of bag: ";
displayBag(copyOfBag);
cout << "The copied bag: ";
displayBag(bag);
} // end copyConstructorTester
void bagTester(LinkedBag<int>& bag)
{
/*
LinkedBag<string> 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<int> sack; //a sack is a bag too, right?
LinkedBag<int> 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<int> bag;
copyConstructorTester();
bagTester(bag);
return 0;
} // end main
Explanation / Answer
The code needed some fixes in LinkedBag class. Mainly it need the overloaded assignment operator =. Assignment operator is very important since local variables returned from functions get destroyed when the function exits. I have modified the code to include assignment operator and use that in copy constructor. Also minor fixes to intersection and difference functions and the displayBag().
Given below is the fixed code. Hope it helps. Post a comment in case of any issues. If the answer helped, please don't forget to rate it. Thank you.
LinkedBag.h
#ifndef _LINKED_BAG
#define _LINKED_BAG
#include "BagInterface.h"
#include "Node.h"
template<class ItemType>
class LinkedBag : public BagInterface<ItemType>
{
private:
Node<ItemType>* 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<ItemType>* getPointerTo(const ItemType& target) const;
public:
LinkedBag();
LinkedBag(const LinkedBag<ItemType>& aBag); // Copy constructor
LinkedBag& operator =(const LinkedBag<ItemType>& aBag); //assignment operator
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<ItemType> toVector() const;
//My methods
LinkedBag<ItemType> bagUnion(const LinkedBag<ItemType> &otherBag) const;
LinkedBag<ItemType> bagIntersection(const LinkedBag<ItemType> &otherBag) const;
LinkedBag<ItemType> bagDifference(const LinkedBag<ItemType> &otherBag) const;
}; // end LinkedBag
#include "LinkedBag.cpp"
#endif
LinkedBag.cpp
#include "LinkedBag.h"
#include "Node.h"
#include <cstddef>
template<class ItemType>
LinkedBag<ItemType>::LinkedBag() : headPtr(nullptr), itemCount(0)
{
} // end default constructor
template<class ItemType>
LinkedBag<ItemType>::LinkedBag(const LinkedBag<ItemType>& aBag)
{
headPtr = nullptr;
*this = aBag;
}
template<class ItemType>
LinkedBag<ItemType>& LinkedBag<ItemType>::operator =(const LinkedBag<ItemType>& aBag)
{
clear();
itemCount = aBag.itemCount;
Node<ItemType>* 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<ItemType>();
headPtr->setItem(origChainPtr->getItem());
// Copy remaining nodes
Node<ItemType>* 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<ItemType>* newNodePtr = new Node<ItemType>(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
return *this;
} // end assignment operator
template<class ItemType>
LinkedBag<ItemType>::~LinkedBag()
{
clear();
} // end destructor
template<class ItemType>
bool LinkedBag<ItemType>::isEmpty() const
{
return itemCount == 0;
} // end isEmpty
template<class ItemType>
int LinkedBag<ItemType>::getCurrentSize() const
{
return itemCount;
} // end getCurrentSize
template<class ItemType>
bool LinkedBag<ItemType>::add(const ItemType& newEntry)
{
// Add to beginning of chain: new node references rest of chain;
// (headPtr is null if chain is empty)
Node<ItemType>* nextNodePtr = new Node<ItemType>();
nextNodePtr->setItem(newEntry);
nextNodePtr->setNext(headPtr); // New node points to chain
// Node<ItemType>* nextNodePtr = new Node<ItemType>(newEntry, headPtr); // alternate code
headPtr = nextNodePtr; // New node is now first node
itemCount++;
return true;
} // end add
template<class ItemType>
vector<ItemType> LinkedBag<ItemType>::toVector() const
{
vector<ItemType> bagContents;
Node<ItemType>* 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<class ItemType>
bool LinkedBag<ItemType>::remove(const ItemType& anEntry)
{
Node<ItemType>* 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<ItemType>* 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<class ItemType>
void LinkedBag<ItemType>::clear()
{
Node<ItemType>* 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<class ItemType>
int LinkedBag<ItemType>::getFrequencyOf(const ItemType& anEntry) const
{
int frequency = 0;
int counter = 0;
Node<ItemType>* 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<class ItemType>
bool LinkedBag<ItemType>::contains(const ItemType& anEntry) const
{
return (getPointerTo(anEntry) != nullptr);
} // end contains
/* ALTERNATE 1
template<class ItemType>
bool LinkedBag<ItemType>::contains(const ItemType& anEntry) const
{
return getFrequencyOf(anEntry) > 0;
}
*/
/* ALTERNATE 2
template<class ItemType>
bool LinkedBag<ItemType>::contains(const ItemType& anEntry) const
{
bool found = false;
Node<ItemType>* curPtr = headPtr;
int i = 0;
while (!found && (curPtr != nullptr) && (i < itemCount))
{
if (anEntry == curPtr-<getItem())
{
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<class ItemType>
Node<ItemType>* LinkedBag<ItemType>::getPointerTo(const ItemType& anEntry) const
{
bool found = false;
Node<ItemType>* 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<class ItemType>
LinkedBag<ItemType> LinkedBag<ItemType>::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<ItemType>* curPtr = otherBag.headPtr;
while(curPtr != nullptr)
{
uni.add(curPtr->getItem());
curPtr = curPtr->getNext();
}
return uni;
}
template<class ItemType>
LinkedBag<ItemType> LinkedBag<ItemType>::bagIntersection(const LinkedBag &otherBag) const
{
int this_count, other_count;
int how_many;
Node<ItemType>* 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());
}
curPtr = curPtr->getNext();
}
return inter;
}
template<class ItemType>
LinkedBag<ItemType> LinkedBag<ItemType>::bagDifference(const LinkedBag &otherBag) const
{
int this_count, other_count;
int how_many;
Node<ItemType>* curPtr = 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());
}
}
curPtr = curPtr->getNext();
}
return diff;
}
BagTester.cpp
#include <iostream>
#include <string>
#include "LinkedBag.h"
using namespace std;
template <class T>
void displayBag(LinkedBag<T>& bag);
void bagTester(LinkedBag<int>& bag);
template <class T>
void displayBag(LinkedBag<T>& bag)
{
cout << "The bag contains " << bag.getCurrentSize()
<< " items:" << endl;
vector<T> 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<string> 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<string> copyOfBag(bag);
cout << "Copy of bag: ";
displayBag(copyOfBag);
cout << "The copied bag: ";
displayBag(bag);
} // end copyConstructorTester
void bagTester(LinkedBag<int>& bag)
{
/*
LinkedBag<string> 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<int> sack; //a sack is a bag too, right?
LinkedBag<int> 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<int> bag;
copyConstructorTester();
bagTester(bag);
return 0;
} // end main
Output
Adding zero
Adding one
Adding two
Adding three
Adding four
Adding five
The bag contains 6 items:
five four three two one zero
Copy of bag: The bag contains 6 items:
five four three two one zero
The copied bag: The bag contains 6 items:
five four three two one zero
Populating first bag... done.
The bag contains 12 items:
6 1 1 9 8 7 3 5 4 2 1 1
Creating second bag and populating... done.
The bag contains 12 items:
2 7 8 9 15 1 18 1 50 40 30 20
Testing the union of the two bags:
The bag contains 24 items:
20 30 40 50 1 18 1 15 9 8 7 2 6 1 1 9 8 7 3 5 4 2 1 1
Done.
Testing the difference of the first bag from the second:
The bag contains 6 items:
4 5 3 1 1 6
Done.
Testing the difference of the second bag from the first:
The bag contains 6 items:
20 30 40 50 18 15
Done.
Testing the intersection of the two bags:
The bag contains 6 items:
1 1 9 8 7 2
Program ended with exit code: 0
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.