Dynamic ADT Implementation help. I need help fixing my BagTester.cpp/main progra
ID: 3587320 • 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
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/main program
#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
Solution:
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
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.