Dynamic ADT Implementation help. I need help dynamically implementing these thre
ID: 3586846 • Letter: D
Question
Dynamic ADT Implementation help. I need help dynamically implementing these three methods into my 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:
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<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/main program
#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);
displayBag(bag);
} // end bagTester
int main()
{
copyConstructorTester();
bagTester();
return 0;
} // end main
Explanation / Answer
template<class ItemType>
LinkedBag<ItemType> LinkedBag<ItemType>::bagUnion(const LinkedBag<ItemType> &otherBag)
{
int size1=getCurrentSize();
int size2=otherBag.getCurrentSize();
LinkedBag<ItemType> bag;
bag.clear();
Node<ItemType>* curPtr = headPtr;
int i = 0;
while ((curPtr != nullptr) && (i < size1))
{
bag.add(curPtr->getItem());
i++;
curPtr = curPtr->getNext();
}
Node<ItemType>* curPtr = otherbag.headPtr;
int i = 0;
while ((curPtr != nullptr) && (i < size2))
{
bag.add(curPtr->getItem());
i++;
curPtr = curPtr->getNext();
}
return bag;
}
template<class ItemType>
LinkedBag<ItemType> LinkedBag<ItemType>::bagDifference(const LinkedBag<ItemType> &otherBag)
{
int size1=getCurrentSize();
int size2=otherBag.getCurrentSize();
LinkedBag<ItemType> bag;
bag.clear();
Node<ItemType>* curPtr = headPtr;
int i = 0;
while ((curPtr != nullptr) && (i < size1))
{
if(!otherBag.contains(curPtr->getItem()))
bag.add(curPtr->getItem());
else{
if(getFrequencyOf(curPtr->getItem())!=bag.getFrequencyOf(curPtr->getItem())+otherBag.getFrequencyOf(curPtr->getItem())&&getFrequencyOf(curPtr->getItem())+bag.getFrequencyOf(curPtr->getItem())!=otherBag.getFrequencyOf(curPtr->getItem())){
while(getFrequencyOf(curPtr->getItem())==bag.getFrequencyOf(curPtr->getItem())+otherBag.getFrequencyOf(curPtr->getItem())||getFrequencyOf(curPtr->getItem())+bag.getFrequencyOf(curPtr->getItem())==otherBag.getFrequencyOf(curPtr->getItem())){
bag.add(curPtr->getItem());
}
}
}
i++;
curPtr = curPtr->getNext();
}
Node<ItemType>* curPtr = otherbag.headPtr;
int i = 0;
while ((curPtr != nullptr) && (i < size2))
{
if(!contains(curPtr->getItem()))
bag.add(curPtr->getItem());
else{
if(getFrequencyOf(curPtr->getItem())!=bag.getFrequencyOf(curPtr->getItem())+otherBag.getFrequencyOf(curPtr->getItem())&&getFrequencyOf(curPtr->getItem())+bag.getFrequencyOf(curPtr->getItem())!=otherBag.getFrequencyOf(curPtr->getItem())){
while(getFrequencyOf(curPtr->getItem())==bag.getFrequencyOf(curPtr->getItem())+otherBag.getFrequencyOf(curPtr->getItem())||getFrequencyOf(curPtr->getItem())+bag.getFrequencyOf(curPtr->getItem())==otherBag.getFrequencyOf(curPtr->getItem())){
bag.add(curPtr->getItem());
}
}
}
i++;
curPtr = curPtr->getNext();
}
return bag;
}
template<class ItemType>
LinkedBag<ItemType> LinkedBag<ItemType>::bagIntersection(const LinkedBag<ItemType> &otherBag)
{
int size1=getCurrentSize();
int size2=otherBag.getCurrentSize();
LinkedBag<ItemType> bag;
bag.clear();
Node<ItemType>* curPtr = headPtr;
int i = 0;
while ((curPtr != nullptr) && (i < size1))
{
if(otherBag.contains(curPtr->getItem())){
if(getFrequencyOf(curPtr->getItem())!=bag.getFrequencyOf(curPtr->getItem())&&bag.getFrequencyOf(curPtr->getItem())!=otherBag.getFrequencyOf(curPtr->getItem())){
while(getFrequencyOf(curPtr->getItem())==bag.getFrequencyOf(curPtr->getItem())||bag.getFrequencyOf(curPtr->getItem())==otherBag.getFrequencyOf(curPtr->getItem())){
bag.add(curPtr->getItem());
}
}
}
i++;
curPtr = curPtr->getNext();
}
Node<ItemType>* curPtr = otherbag.headPtr;
int i = 0;
while ((curPtr != nullptr) && (i < size2))
{
if(otherBag.contains(curPtr->getItem())){
if(getFrequencyOf(curPtr->getItem())!=bag.getFrequencyOf(curPtr->getItem())&&bag.getFrequencyOf(curPtr->getItem())!=otherBag.getFrequencyOf(curPtr->getItem())){
while(getFrequencyOf(curPtr->getItem())==bag.getFrequencyOf(curPtr->getItem())||bag.getFrequencyOf(curPtr->getItem())==otherBag.getFrequencyOf(curPtr->getItem())){
bag.add(curPtr->getItem());
}
}
}
i++;
curPtr = curPtr->getNext();
}
return bag;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.