Dynamic ADT Implementation help. I don\'t know how to dynamically implement thes
ID: 3585228 • Letter: D
Question
Dynamic ADT Implementation help. I don't know how to dynamically implement these methods.
Methods must compose a new Bag object by accessing the elements of the underlying linked list of the Bag objects. You may not convert the Bags to vectors. The main method must also be updated to thoroughly test the newly added methods.
1. bagUnion(): The union of two bags is a new bag containing the combined contents of the original two bags. Design and specify a method union for the LinkedBag that returns as a new bag the union of the bag receiving the call to the method and the bag that is the method's parameter. Note that the union of two bags might contain duplicate items. For example, if object x occurs five times in one bag and twice in another, the union of these bags contains x seven times. The union does not affect the contents of the original bags.
2. bagIntersection(): The intersection of two bags is a new bag containing the entries that occur in both of the original bags. Design and specify a method intersection for the LinkedBag that returns as a new bag the intersection of the bag receiving the call to the method and the bag that is the method's parameter. Note that the intersection of two bags might contain duplicate items. For example, if object x occurs five times in one bag and twice in another, the intersection of these bags contains x two times. The intersection does not affect the contents of the original bags.
3. bagDifference(): The difference of two bags is a new bag containing the entries (from both bag) that would be unique in one bag (not duplicated in its own bag, also not another bag). Design and specify a method difference for the LinkedBag that returns as a new bag the difference from the two bags (the bag receiving the call to the method and the bag that is the method's parameter). Note that the difference of two bags does not contain duplicate items. For example, if object x occurs more than one time in one bag and no in another, the difference of these bags contains x only one time.
For testing the new methods, please output original contents in two bags and clear message for each testing, for example:
Bag 1 contains: 1 2 3 4 5 1
Bag 2 contains: 4 5 6 7 8 8
Test union method … 1 2 3 4 5 1 4 5 6 7 8 8
Test intersection method … 4 5
Test difference method … 1 2 3 6 7 8
BagInterface.h
#ifndef _BAG_INTERFACE
#define _BAG_INTERFACE
#include
using namespace std;
template
class BagInterface
{
public:
virtual int getCurrentSize() const = 0;
virtual bool isEmpty() const = 0;
virtual bool add(const ItemType& newEntry) = 0;
virtual bool remove(const ItemType& anEntry) = 0;
virtual void clear() = 0;
virtual int getFrequencyOf(const ItemType& anEntry) const = 0;
virtual bool contains(const ItemType& anEntry) const = 0;
virtual vector toVector() const = 0;
}; // end BagInterface
#endif
Node.h
#ifndef _NODE
#define _NODE
template
class Node
{
private:
ItemType item; // A data item
Node* next; // Pointer to next node
public:
Node();
Node(const ItemType& anItem);
Node(const ItemType& anItem, Node* nextNodePtr);
void setItem(const ItemType& anItem);
void setNext(Node* nextNodePtr);
ItemType getItem() const ;
Node* getNext() const ;
}; // end Node
#include "Node.cpp"
#endif
LinkedBag.h
#ifndef _LINKED_BAG
#define _LINKED_BAG
#include "BagInterface.h"
#include "Node.h"
template
class LinkedBag : public BagInterface
{
private:
Node* headPtr; // Pointer to first node
int itemCount; // Current count of bag items
// Returns either a pointer to the node containing a given entry
// or the null pointer if the entry is not in the bag.
Node* getPointerTo(const ItemType& target) const;
public:
LinkedBag();
LinkedBag(const LinkedBag& aBag); // Copy constructor
virtual ~LinkedBag(); // Destructor should be virtual
int getCurrentSize() const;
bool isEmpty() const;
bool add(const ItemType& newEntry);
bool remove(const ItemType& anEntry);
void clear();
bool contains(const ItemType& anEntry) const;
int getFrequencyOf(const ItemType& anEntry) const;
vector toVector() const;
//My methods
LinkedBag bagUnion(const LinkedBag &otherBag) const;
LinkedBag bagIntersection(const LinkedBag &otherBag) const;
LinkedBag bagDifference(const LinkedBag &otherBag) const;
}; // end LinkedBag
#include "LinkedBag.cpp"
#endif
Node.cpp
#include "Node.h"
#include
template
Node::Node() : next(nullptr)
{
} // end default constructor
template
Node::Node(const ItemType& anItem) : item(anItem), next(nullptr)
{
} // end constructor
template
Node::Node(const ItemType& anItem, Node* nextNodePtr) :
item(anItem), next(nextNodePtr)
{
} // end constructor
template
void Node::setItem(const ItemType& anItem)
{
item = anItem;
} // end setItem
template
void Node::setNext(Node* nextNodePtr)
{
next = nextNodePtr;
} // end setNext
template
ItemType Node::getItem() const
{
return item;
} // end getItem
template
Node* Node::getNext() const
{
return next;
} // end getNext
LinkedBag.cpp
#include "LinkedBag.h"
#include "Node.h"
#include
template
LinkedBag::LinkedBag() : headPtr(nullptr), itemCount(0)
{
} // end default constructor
template
LinkedBag::LinkedBag(const LinkedBag& aBag)
{
itemCount = aBag.itemCount;
Node* origChainPtr = aBag.headPtr; // Points to nodes in original chain
if (origChainPtr == nullptr)
headPtr = nullptr; // Original bag is empty
else
{
// Copy first node
headPtr = new Node();
headPtr->setItem(origChainPtr->getItem());
// Copy remaining nodes
Node* newChainPtr = headPtr; // Points to last node in new chain
origChainPtr = origChainPtr->getNext(); // Advance original-chain pointer
while (origChainPtr != nullptr)
{
// Get next item from original chain
ItemType nextItem = origChainPtr->getItem();
// Create a new node containing the next item
Node* newNodePtr = new Node(nextItem);
// Link new node to end of new chain
newChainPtr->setNext(newNodePtr);
// Advance pointer to new last node
newChainPtr = newChainPtr->getNext();
// Advance original-chain pointer
origChainPtr = origChainPtr->getNext();
} // end while
newChainPtr->setNext(nullptr); // Flag end of chain
} // end if
} // end copy constructor
template
LinkedBag::~LinkedBag()
{
clear();
} // end destructor
template
bool LinkedBag::isEmpty() const
{
return itemCount == 0;
} // end isEmpty
template
int LinkedBag::getCurrentSize() const
{
return itemCount;
} // end getCurrentSize
template
bool LinkedBag::add(const ItemType& newEntry)
{
// Add to beginning of chain: new node references rest of chain;
// (headPtr is null if chain is empty)
Node* nextNodePtr = new Node();
nextNodePtr->setItem(newEntry);
nextNodePtr->setNext(headPtr); // New node points to chain
// Node* nextNodePtr = new Node(newEntry, headPtr); // alternate code
headPtr = nextNodePtr; // New node is now first node
itemCount++;
return true;
} // end add
template
vector LinkedBag::toVector() const
{
vector bagContents;
Node* curPtr = headPtr;
int counter = 0;
while ((curPtr != nullptr) && (counter < itemCount))
{
bagContents.push_back(curPtr->getItem());
curPtr = curPtr->getNext();
counter++;
} // end while
return bagContents;
} // end toVector
template
bool LinkedBag::remove(const ItemType& anEntry)
{
Node* entryNodePtr = getPointerTo(anEntry);
bool canRemoveItem = !isEmpty() && (entryNodePtr != nullptr);
if (canRemoveItem)
{
// Copy data from first node to located node
entryNodePtr->setItem(headPtr->getItem());
// Delete first node
Node* nodeToDeletePtr = headPtr;
headPtr = headPtr->getNext();
// Return node to the system
nodeToDeletePtr->setNext(nullptr);
delete nodeToDeletePtr;
nodeToDeletePtr = nullptr;
itemCount--;
} // end if
return canRemoveItem;
} // end remove
template
void LinkedBag::clear()
{
Node* nodeToDeletePtr = headPtr;
while (headPtr != nullptr)
{
headPtr = headPtr->getNext();
// Return node to the system
nodeToDeletePtr->setNext(nullptr);
delete nodeToDeletePtr;
nodeToDeletePtr = headPtr;
} // end while
// headPtr is nullptr; nodeToDeletePtr is nullptr
itemCount = 0;
} // end clear
template
int LinkedBag::getFrequencyOf(const ItemType& anEntry) const
{
int frequency = 0;
int counter = 0;
Node* curPtr = headPtr;
while ((curPtr != nullptr) && (counter < itemCount))
{
if (anEntry == curPtr->getItem())
{
frequency++;
} // end if
counter++;
curPtr = curPtr->getNext();
} // end while
return frequency;
} // end getFrequencyOf
template
bool LinkedBag::contains(const ItemType& anEntry) const
{
return (getPointerTo(anEntry) != nullptr);
} // end contains
/* ALTERNATE 1
template
bool LinkedBag::contains(const ItemType& anEntry) const
{
return getFrequencyOf(anEntry) > 0;
}
*/
/* ALTERNATE 2
template
bool LinkedBag::contains(const ItemType& anEntry) const
{
bool found = false;
Node* curPtr = headPtr;
int i = 0;
while (!found && (curPtr != nullptr) && (i < itemCount))
{
if (anEntry == curPtr-
{
found = true;
}
else
{
i++;
curPtr = curPtr->getNext();
} // end if
} // end while
return found;
} // end contains
*/
// private
// Returns either a pointer to the node containing a given entry
// or the null pointer if the entry is not in the bag.
template
Node* LinkedBag::getPointerTo(const ItemType& anEntry) const
{
bool found = false;
Node* curPtr = headPtr;
while (!found && (curPtr != nullptr))
{
if (anEntry == curPtr->getItem())
found = true;
else
curPtr = curPtr->getNext();
} // end while
return curPtr;
} // end getPointerTo
//My methods
LinkedBag LinkedBag::bagUnion(const LinkedBag &otherBag) const
{
}
LinkedBag LinkedBag::bagIntersection(const LinkedBag &otherBag) const
{
}
LinkedBag LinkedBag::bagDifference(const LinkedBag &otherBag) const
{
}
BagTester.cpp
#include
#include
#include "LinkedBag.h"
using namespace std;
void displayBag(LinkedBag& bag)
{
cout << "The bag contains " << bag.getCurrentSize()
<< " items:" << endl;
vector bagItems = bag.toVector();
int numberOfEntries = (int) bagItems.size();
for (int i = 0; i < numberOfEntries; i++)
{
cout << bagItems[i] << " ";
} // end for
cout << endl << endl;
} // end displayBag
void copyConstructorTester()
{
LinkedBag bag;
string items[] = {"zero", "one", "two", "three", "four", "five"};
for (int i = 0; i < 6; i++)
{
cout << "Adding " << items[i] << endl;
bool success = bag.add(items[i]);
if (!success)
cout << "Failed to add " << items[i] << " to the bag." << endl;
}
displayBag(bag);
LinkedBag copyOfBag(bag);
cout << "Copy of bag: ";
displayBag(copyOfBag);
cout << "The copied bag: ";
displayBag(bag);
} // end copyConstructorTester
void bagTester()
{
LinkedBag bag;
cout << "Testing the Link-Based Bag:" << endl;
cout << "isEmpty: returns " << bag.isEmpty()
<< "; should be 1 (true)" << endl;
displayBag(bag);
string items[] = {"one", "two", "three", "four", "five", "one"};
cout << "Add 6 items to the bag: " << endl;
for (int i = 0; i < 6; i++)
{
bag.add(items[i]);
} // end for
displayBag(bag);
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
int main()
{
copyConstructorTester();
bagTester();
return 0;
} // end main
Explanation / Answer
Here is the code for the above question,
#include <algorithm>
#include <iostream>
#include <string>
#include "LinkedBag.h"
using namespace std;
template<class ItemType> void displayBag(LinkedBag<ItemType>& bag);
template<class ItemType> void bagTester(LinkedBag<ItemType>& bag);
void newOpsTester();
/**
* main() function.
*/
int main()
{
LinkedBag<string> bag;
cout << "Testing the Vector-Based Bag:" << endl;
cout << "The initial bag is empty." << endl;
bagTester(bag);
newOpsTester();
cout << "All done!" << endl;
return 0;
}
/**
* Display the contents of a LinkedBag, which can hold
* any kind of element. The elements are displayed in sorted order.
* (This means that the ItemType must be one for which
* the "<" operation is defined.)
* @param bag The bag to be displayed.
*/
template<class ItemType>
void displayBag(LinkedBag<ItemType>& bag)
{
cout << "The bag contains " << bag.getCurrentSize()
<< " items:" << endl;
vector<ItemType> bagItems = bag.toVector();
int numberOfEntries = static_cast<int>(bagItems.size());
sort(bagItems.begin(), bagItems.end());
for (int i = 0; i < numberOfEntries; i++)
cout << bagItems[i] << " ";
cout << endl << endl;
} // end displayBag
/**
* In addition to testing the original operations that are
* implemented from BagInterface code, test the operations
* of union, intersection, and difference.
* @param bag The bag to be tested.
*/
template<class ItemType> void bagTester(LinkedBag<ItemType>& bag)
{
cout << "isEmpty: returns " << bag.isEmpty()
<< "; should be 1 (true)" << endl;
displayBag(bag);
string items[] = {"one", "two", "three", "four", "five", "one"};
int itemsSize = sizeof(items)/sizeof(char*);
cout << "Adding " << itemsSize << " items to the bag: " << endl;
for (unsigned int i = 0; i < itemsSize; i++)
bag.add(items[i]);
displayBag(bag);
cout << "isEmpty: returns " << bag.isEmpty()
<< "; should be 0 (false)" << endl;
cout << "getCurrentSize: returns " << bag.getCurrentSize()
<< "; should be " << itemsSize << 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
template<class ItemType>
LinkedBag<ItemType>
LinkedBag<ItemType>::operator+(LinkedBag<ItemType> anotherBag){
LinkedBag<ItemType> newBag;
int Size = sizeof(secondItems)/sizeof(int);
for (int i = 0; i < Size; i++)
firstBag.add(secondItems[i]);
}
/**
* Test the new LinkedBag operations (union, intersection, difference)
*/
void newOpsTester()
{
cout << " Let's test the new bag operations. ";
int firstItems[] = {2, 4, 6, 6, 8, 10, 12, 15, 15};
LinkedBag<int> firstBag;
int firstSize = sizeof(firstItems)/sizeof(int);
cout << "Adding " << firstSize << " items to first bag: " << endl;
for (int i = 0; i < firstSize; i++)
firstBag.add(firstItems[i]);
cout << "First bag: ";
displayBag(firstBag);
int secondItems[] = {3, 6, 9, 12, 12, 15, 15, 18};
LinkedBag<int> secondBag;
int secondSize = sizeof(secondItems)/sizeof(int);
cout << "Adding " << secondSize << " items to second bag: " << endl;
for (int i = 0; i < secondSize; i++)
secondBag.add(secondItems[i]);
cout << "Second bag: ";
displayBag(secondBag);
LinkedBag<int> unionBag = firstBag + secondBag;
cout << "firstBag union secondBag: ";
displayBag(unionBag);
LinkedBag<int> intersectBag = firstBag * secondBag;
cout << "firstBag intersect secondBag: ";
displayBag(intersectBag);
LinkedBag<int> diffBag = firstBag - secondBag;
cout << "firstBag minus secondBag: ";
displayBag(diffBag);
diffBag = secondBag - firstBag;
cout << "secondBag minus firstBag: ";
displayBag(diffBag);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.