C++ ADT Bag Union Help. I need to write the following program but I\'m having tr
ID: 3673475 • Letter: C
Question
C++ ADT Bag Union Help. I need to write the following program but I'm having trouble with implementation files methods and calling these methods from main().
The following 3 methods are to be added to the Linked-based implementation of a Bag ADT. 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. The algorithms are the same as in the previous lab. However, the syntax will change due to the implementation.
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 ArrayBag 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 ArrayBag 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 that would be left in one bag after removing those that also occur in the second. Design and specify a method difference for the ArrayBag that returns as a new bag the difference of the bag receiving the call to the method and the bag that is the method's parameter. Note that the difference of two bags might contain duplicate items. For example, if object x occurs five times in one bag and twice in another, the difference of these bags contains x three times.
My current method headers in the implementation file are:
template<class ItemType>
bool LinkedBag<ItemType>::bagUnion(const ItemType& bag1 ,const ItemType& bag2)
{
// needs to union bag1 and bag2 and put it in a unionBag to return to main()
}
template<class ItemType>
bool LinkedBag<ItemType>::bagIntersection(const ItemType& unionBag)
{
//finds the intersection of unionBag
}
template<class ItemType>
bool LinkedBag<ItemType>::bagDifference(const ItemType& unionBag)
{
//finds the difference of unionBag
}
Explanation / Answer
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;
LinkedBag<ItemType>bagUnion(const LinkedBag& input) const; // Lab 4-1
LinkedBag<ItemType> intersect(const LinkedBag& input) const; //Lab 4-2
LinkedBag<ItemType> trueIntersect(const LinkedBag& input) const;
LinkedBag<ItemType> difference(const LinkedBag& input) const; // Lab 4-3
LinkedBag<ItemType> trueDifference(const LinkedBag& input) const;
}; // end LinkedBag
#include "LinkedBag.cpp"
#endif
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
BagTester.cpp
#include <iostream>
#include <string>
#include "LinkedBag.h"
using namespace std;
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<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);
cout << "isEmpty: returns " << bag.isEmpty()
<< "; should be 0 (false)" << endl;
cout << "getCurrentSize: returns " << bag.getCurrentSize()
<< "; should be 6" << endl;
cout << "Try to add another entry: add("extra") returns "
<< bag.add("extra") << endl;
cout << "contains("three"): returns " << bag.contains("three")
<< "; should be 1 (true)" << endl;
cout << "contains("ten"): returns " << bag.contains("ten")
<< "; should be 0 (false)" << endl;
cout << "getFrequencyOf("one"): returns "
<< bag.getFrequencyOf("one") << " should be 2" << endl;
cout << "remove("one"): returns " << bag.remove("one")
<< "; should be 1 (true)" << endl;
cout << "getFrequencyOf("one"): returns "
<< bag.getFrequencyOf("one") << " should be 1" << endl;
cout << "remove("one"): returns " << bag.remove("one")
<< "; should be 1 (true)" << endl;
cout << "remove("one"): returns " << bag.remove("one")
<< "; should be 0 (false)" << endl;
cout << endl;
displayBag(bag);
cout << "After clearing the bag, ";
bag.clear();
cout << "isEmpty: returns " << bag.isEmpty()
<< "; should be 1 (true)" << endl;
} // end bagTester
void newMethodTester()
{
LinkedBag<string> bag;
LinkedBag<string> bag2;
string items[] = {"the", "fox", "fox", "fox", "fox", "fox"};
//string items[] = {"one", "two", "three", "four", "five", "one"};
for (int i = 0; i < 6; i++)
{
bag.add(items[i]);
} // end for
displayBag(bag);
string items2[]= {"the", "quick", "fox", "fox"};
//string items2[] = {"one", "shell", "beach", "two"};
for (int i = 0; i < 4; i++)
{
bag2.add(items2[i]);
} // end for
displayBag(bag2);
LinkedBag<string> unionResult = bag.bagUnion(bag2);
LinkedBag<string> intersectResult = bag.intersect(bag2);
LinkedBag<string> diffResult = bag.difference(bag2);
LinkedBag<string> diffResult2 = bag.trueDifference(bag2);
LinkedBag<string> intersectResult2 = bag.trueIntersect(bag2);
displayBag(unionResult);
displayBag(intersectResult);
displayBag(intersectResult2);
displayBag(diffResult);
displayBag(diffResult2);
}
int main()
{
//copyConstructorTester();
//bagTester();
newMethodTester();
return 0;
} // end main
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) // origChainPtr is used as our counting pointer to traverse
// the old chain
{
// 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
template<class ItemType>
LinkedBag<ItemType> LinkedBag<ItemType>::bagUnion(const LinkedBag& input) const{
// make a new LinkedBag that will hold the union
// copy input values into the union bag using copy constructor
LinkedBag<ItemType> theUnion = LinkedBag(input);
// add the caller values
Node<ItemType>* origChainPtr = headPtr; // Points to nodes in original chain
while (origChainPtr != nullptr) // only add if second chain isn't empty.
{
// Copy first node
theUnion.add(origChainPtr->getItem());
origChainPtr=origChainPtr->getNext();
}
return theUnion;
}
//Lab 4-2
template<class ItemType>
LinkedBag<ItemType> LinkedBag<ItemType>::intersect(const LinkedBag& input) const{
// make a new LinkedBag that will hold the intersect
LinkedBag<ItemType> theIntersect;
// traverse the existing linked list
Node<ItemType>* callerPtr = headPtr;
Node<ItemType>* paramPtr = input.headPtr;
while (callerPtr != nullptr)
{
//cout<<"caller: "<<callerPtr->getItem()<<endl;
while(paramPtr != nullptr){
// compare item entries
//cout<<"input: "<<paramPtr->getItem()<<endl;
if(callerPtr->getItem() == paramPtr->getItem()){ //if there's a match
//add to intersect
theIntersect.add(callerPtr->getItem());
// stop looking for this value
paramPtr = paramPtr->getNext();
break;
}
//advance to next item in paramPtr
paramPtr = paramPtr->getNext();
}
//reset paramPtr
paramPtr = input.headPtr;
//advance to next item in callerPtr
callerPtr = callerPtr->getNext();
}
return theIntersect;
}
//Lab 4-2 extension: true intersect
template<class ItemType>
LinkedBag<ItemType> LinkedBag<ItemType>::trueIntersect(const LinkedBag& input) const{
// make a new LinkedBag that will hold the intersect
LinkedBag<ItemType> theIntersect;
// traverse the existing linked list
Node<ItemType>* callerPtr = headPtr;
Node<ItemType>* paramPtr = input.headPtr;
int callerCount = 0;
int inputCount = 0;
int intersect = 0;
int sectCount = 0;
while (callerPtr != nullptr)
{
//cout<<"caller: "<<callerPtr->getItem()<<endl;
while(paramPtr != nullptr){
// compare item entries
//cout<<"input: "<<paramPtr->getItem()<<endl;
if(callerPtr->getItem() == paramPtr->getItem()){ //if there's a match
//check to see if already in intersect
sectCount = theIntersect.getFrequencyOf(callerPtr->getItem());
// if already in difference, break
if(sectCount > 0)
break;
callerCount = getFrequencyOf(callerPtr->getItem());
//cout<<"callerCount is: "<<callerCount<<endl;
inputCount = input.getFrequencyOf(paramPtr->getItem());
//cout<<"inputCount is: "<<inputCount<<endl;
if(callerCount < inputCount)
intersect = callerCount;
else if (inputCount < callerCount)
intersect = inputCount;
else
// they're the same
intersect = inputCount;
//add to intersect
for(int i=0; i<intersect; i++)
theIntersect.add(callerPtr->getItem());
// stop looking for this value
paramPtr = paramPtr->getNext();
break;
}
//advance to next item in paramPtr
paramPtr = paramPtr->getNext();
}
//reset paramPtr
paramPtr = input.headPtr;
//advance to next item in callerPtr
callerPtr = callerPtr->getNext();
}
return theIntersect;
}
//Lab 4-3
template<class ItemType>
LinkedBag<ItemType> LinkedBag<ItemType>::difference(const LinkedBag& input) const{
// make a new LinkedBag that will hold the difference
LinkedBag<ItemType> theDiff;
// traverse the existing linked list
Node<ItemType>* callerPtr = headPtr;
Node<ItemType>* paramPtr = input.headPtr;
while (callerPtr != nullptr)
{
while(paramPtr != nullptr){
// compare item entries
if(callerPtr->getItem() == paramPtr->getItem()){
//do nothing and stop looking
break;
}
//if we get to the end of input and don't find it.
if(paramPtr->getNext() == nullptr){
// items are not equivalent.
//add to difference
theDiff.add(callerPtr->getItem());
break;
}
//advance to next item in paramPtr
paramPtr = paramPtr->getNext();
}
//reset paramPtr
paramPtr = input.headPtr;
//advance to next item in callerPtr
callerPtr = callerPtr->getNext();
}
return theDiff;
}
//Lab 4-3 extension- true difference
template<class ItemType>
LinkedBag<ItemType> LinkedBag<ItemType>::trueDifference(const LinkedBag& input) const{
// make a new LinkedBag that will hold the difference
LinkedBag<ItemType> theDiff;
// traverse the existing linked list
Node<ItemType>* callerPtr = headPtr;
Node<ItemType>* paramPtr = input.headPtr;
int callerCount = 0;
int inputCount = 0;
int diff = 0;
int diffCount = 0;
while (callerPtr != nullptr)
{
while(paramPtr != nullptr){
// compare item entries
if(callerPtr->getItem() == paramPtr->getItem()){
//check to see if already in difference
diffCount = theDiff.getFrequencyOf(callerPtr->getItem());
// if already in difference, break
if(diffCount > 0)
break;
callerCount = getFrequencyOf(callerPtr->getItem());
//cout<<"callerCount is: "<<callerCount<<endl;
inputCount = input.getFrequencyOf(paramPtr->getItem());
//cout<<"inputCount is: "<<inputCount<<endl;
diff = callerCount - inputCount;
//cout<<"diff is: "<<diff<<endl;
if (diff < 0)
diff = 0;
if (diff > 0){
for(int i=0; i<diff; i++)
theDiff.add(callerPtr->getItem());
}
break;
}
//if we get to the end of input and don't find it.
if(paramPtr->getNext() == nullptr){
// items are not equivalent.
//add to difference
theDiff.add(callerPtr->getItem());
break;
}
//advance to next item in paramPtr
paramPtr = paramPtr->getNext();
}
//reset paramPtr
paramPtr = input.headPtr;
//advance to next item in callerPtr
callerPtr = callerPtr->getNext();
}
return theDiff;
}
// 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
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;
LinkedBag<ItemType>bagUnion(const LinkedBag& input) const; // Lab 4-1
LinkedBag<ItemType> intersect(const LinkedBag& input) const; //Lab 4-2
LinkedBag<ItemType> trueIntersect(const LinkedBag& input) const;
LinkedBag<ItemType> difference(const LinkedBag& input) const; // Lab 4-3
LinkedBag<ItemType> trueDifference(const LinkedBag& input) const;
}; // end LinkedBag
#include "LinkedBag.cpp"
#endif
Node.cpp
#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;
LinkedBag<ItemType>bagUnion(const LinkedBag& input) const; // Lab 4-1
LinkedBag<ItemType> intersect(const LinkedBag& input) const; //Lab 4-2
LinkedBag<ItemType> trueIntersect(const LinkedBag& input) const;
LinkedBag<ItemType> difference(const LinkedBag& input) const; // Lab 4-3
LinkedBag<ItemType> trueDifference(const LinkedBag& input) const;
}; // end LinkedBag
#include "LinkedBag.cpp"
#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
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.