Similarly to what you did with the array-based implementation, you'll start with the LinkedBag code from the links below and make the needed edits to change it to a link-based Set.

The vast majority of your code will be copied directly from the LinkedBag class from the links below. You just need to make minor adjustments to reflect the fact that duplicate elements are not allowed. Also, we won't have a frequencyOf() member function.

Your LinkedSet class must be derived from a "SetInterface" abstract class. You should be able to reuse your SetInterface class from the last assignment.

You must provide the big-3. If you are not familiar with the term "big-3," please take a few minutes to review lesson 17. The LinkedBag from the links below provides a copy constructor but does not provide an overloaded assignment operator, so you will need to add that to your class.

I strongly suggest the following as a review of the function of the copy constructor: Compile and run the LinkedBag code provided below. Then comment out the copy constructor from both LinkedBag.h and LinkedBag.cpp, and observe what happens. Study the copyConstructorTester() function to make sure you understand what is happening.

Here's my suggestion about the big-3. Change the given copy constructor into a function named "copy()". This won't require any changes to the code inside the function. Then create a new copy constructor that does nothing except call the copy() function. Once you have tested that carefully, then you can call copy() from the assignment operator to do the work of making the copy. (The assignment operator will also need to call clear(), check for self-assignment, and return the appropriate object.)

A subtle point about the copy() function I'm suggesting: It should be a private function, because it won't be appropriate for the client to call this function, because a copy() function intended for client use would need to deallocate the already existing LinkedBag object that is being copied into.

Here is the source code that you are to use as a starting point:

Revise the public method add in the class LinkedBag so that the new node is inserted at the end of the linked chain.

//LinkedBag.cpp #include "Node.h" #include  namespace cs_bag { template LinkedBag::LinkedBag() { headPtr = nullptr; itemCount = 0; } template LinkedBag::LinkedBag(const LinkedBag& aBag) { itemCount = aBag.itemCount; Node* origChainPtr = aBag.headPtr; if (origChainPtr == nullptr) { headPtr = nullptr; } else { // Copy first node headPtr = new Node(); headPtr->setItem(origChainPtr->getItem()); // Copy remaining nodes Node* newChainPtr = headPtr; origChainPtr = origChainPtr->getNext(); 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(); } newChainPtr->setNext(nullptr); } } template LinkedBag::~LinkedBag() { clear(); } template bool LinkedBag::isEmpty() const { return itemCount == 0; } template int LinkedBag::getCurrentSize() const { return itemCount; } template void LinkedBag::add(const ItemType& newEntry) { Node* nextNodePtr = new Node(); nextNodePtr->setItem(newEntry); nextNodePtr->setNext(headPtr); headPtr = nextNodePtr; // New node is now first node itemCount++; } template std::vector LinkedBag::toVector() const { std::vector bagContents; Node* curPtr = headPtr; while ((curPtr != nullptr)) { bagContents.push_back(curPtr->getItem()); curPtr = curPtr->getNext(); } return bagContents; } template void LinkedBag::remove(const ItemType& anEntry) { Node* entryNodePtr = getPointerTo(anEntry); if (entryNodePtr == nullptr) { throw ItemNotFoundError(); } else { // replace data of node to delete with data from first node entryNodePtr->setItem(headPtr->getItem()); // Delete first node Node* nodeToDeletePtr = headPtr; headPtr = headPtr->getNext(); delete nodeToDeletePtr; itemCount--; } } template void LinkedBag::clear() { Node* nodeToDeletePtr = headPtr; while (headPtr != nullptr) { headPtr = headPtr->getNext(); delete nodeToDeletePtr; nodeToDeletePtr = headPtr; } headPtr = nullptr; itemCount = 0; } 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++; } counter++; curPtr = curPtr->getNext(); } return frequency; } template bool LinkedBag::contains(const ItemType& anEntry) const { return (getPointerTo(anEntry) != nullptr); } // private // Returns either a pointer to the node containing a given entry // or nullptr 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(); } } return curPtr; } } 

//LinkedBag.h

#ifndef LINKED_BAG_ #define LINKED_BAG_ #include "BagInterface.h" #include "Node.h" namespace cs_bag { template class LinkedBag : public BagInterface { private: Node* headPtr; int itemCount; // Returns either a pointer to the node containing a given entry // or nullptr if the entry is not in the bag. Node* getPointerTo(const ItemType& target) const; public: class ItemNotFoundError {}; LinkedBag(); LinkedBag(const LinkedBag& aBag); virtual ~LinkedBag(); int getCurrentSize() const; bool isEmpty() const; void add(const ItemType& newEntry); void remove(const ItemType& anEntry); void clear(); bool contains(const ItemType& anEntry) const; int getFrequencyOf(const ItemType& anEntry) const; std::vector toVector() const; }; } #include "LinkedBag.cpp" #endif

//Node.h

#ifndef NODE_ #define NODE_ namespace cs_bag { template class Node { private: ItemType item; Node* next; public: Node(const ItemType& anItem = ItemType(), Node* nextNodePtr = nullptr); void setItem(const ItemType& anItem); void setNext(Node* nextNodePtr); ItemType getItem() const ; Node* getNext() const ; }; } #include "Node.cpp" #endif

//Node.cpp

namespace cs_bag { template Node::Node(const ItemType& anItem, Node* nextNodePtr) { item = anItem; next = nextNodePtr; } template void Node::setItem(const ItemType& anItem) { item = anItem; } template void Node::setNext(Node* nextNodePtr) { next = nextNodePtr; } template ItemType Node::getItem() const { return item; } template Node* Node::getNext() const { return next; } }

//bagtester.cpp

#include  #include  #include "LinkedBag.h" using namespace std; using namespace cs_bag; void displayBag(LinkedBag& bag) { vector bagItems = bag.toVector(); int numberOfEntries = bagItems.size(); for (int i = 0; i < numberOfEntries; i++) { cout << bagItems[i] << " "; } } void copyConstructorTester() { cout << "Testing copy constructor:" << endl; LinkedBag bag; string items[] = {"zero", "one", "two", "three", "four", "five"}; for (int i = 0; i < 6; i++) { cout << "Adding " << items[i] << endl; bag.add(items[i]); } cout << "The original bag: "; displayBag(bag); cout << endl; LinkedBag copyOfBag(bag); cout << "Copy of bag: "; displayBag(copyOfBag); cout << endl; cout << "Removing 'one' from copy of bag." << endl; copyOfBag.remove("one"); cout << "The original bag: "; displayBag(bag); cout << endl; cout << "Copy of bag: "; displayBag(copyOfBag); cout << endl; } void bagTester() { LinkedBag bag; cout << "Testing the Link-Based Bag:" << endl; cout << "isEmpty: returns " << bag.isEmpty() << "; should be 1 (true)" << endl; displayBag(bag); cout << endl; 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]); } displayBag(bag); cout << endl; cout << "isEmpty: returns " << bag.isEmpty() << "; should be 0 (false)" << endl; cout << "getCurrentSize: returns " << bag.getCurrentSize() << "; should be 6" << endl; cout << "Add another entry: add(\"extra\") " << endl; bag.add("extra"); 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; try { cout << "remove(\"one\")... "; bag.remove("one"); cout << "shouldn't cause exception and didn't!" << endl; } catch (LinkedBag::ItemNotFoundError e) { cout << "shouldn't cause exception but did." << endl; } cout << "getFrequencyOf(\"one\"): returns " << bag.getFrequencyOf("one") << " should be 1" << endl; try { cout << "remove(\"one\")... "; bag.remove("one"); cout << "shouldn't cause exception and didn't!" << endl; } catch (LinkedBag::ItemNotFoundError e) { cout << "shouldn't cause exception but did." << endl; } try { cout << "remove(\"one\")... "; bag.remove("one"); cout << "should cause exception but didn't" << endl; } catch (LinkedBag::ItemNotFoundError e) { cout << "should cause exception and did!" << endl; } cout << endl; displayBag(bag); cout << endl; cout << "After clearing the bag, "; bag.clear(); cout << "isEmpty: returns " << bag.isEmpty() << "; should be 1 (true)" << endl; } int main() { copyConstructorTester(); bagTester(); }

Part 2:

Add member functions setUnion(), setIntersection(), and setDifference().

The functions should all return the resulting LinkedSet object. We won't need to throw an exception in the setUnion() function, because the Set will have unlimited capacity.

You may use contains() and the Node class accessors and mutators, but, other than those, do not use any explicit function calls in your definitions of these three functions! The operations must be coded without explicitly calling any other functions to help. The practice manipulating the pointers directly will be extremely valuable.

You may also use calls to constructors and the assignment operator. (The word "explicitly" in the above paragraph is intended to allow for you to call constructors and the assignment operator, since those are not explicit function calls.)

Name your source code files SetInterface.h,LinkedSet.h, and LinkedSet.cpp