Implement the following functions inside the LinkedBag: -add a value at the end
ID: 3883895 • Letter: I
Question
Implement the following functions inside the LinkedBag:
-add a value at the end of the list
-eliminate a value from the list without losing the original order
-print the contents of the array
-in the main program, show how the copy constructor works
//////////////////////////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
// 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;
}; // 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
//////////////////////////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
/////////////////////////////////////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 fills 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
Explanation / Answer
Below is your code : -
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
// 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
main.cpp
#include "BagInterface.h"
#include "LinkedBag.h"
#include <iostream>
#include <string>
#include <cctype>
#include <vector>
using namespace std;
void displayBag(BagInterface<string> *bagPtr) {
cout << "The bag contains " << bagPtr->getCurrentSize() << " items:" << endl;
vector <string> bagItems;
bagItems = bagPtr->toVector();
int numberOfEntries = bagItems.size();
for (int i = 0; i < numberOfEntries; i++) {
cout << bagItems[i] << " ";
} // end for
cout << endl << endl;
} // end displayBag
void bagTester(BagInterface<string> *bagPtr) {
cout << "isEmpty: returns " << bagPtr->isEmpty() << "; should be 1 (true)" << endl;
string items[] = {"one", "two", "three", "four", "five", "one"};
cout << "Add 6 items to the bag: " << endl;
for (int i = 0; i < 6; i++) {
bagPtr->add(items[i]);
} // end for
displayBag(bagPtr);
cout << "isEmpty: returns " << bagPtr->isEmpty() << "; should be 0 (false)" << endl;
cout << "getCurrentSize returns : " << bagPtr->getCurrentSize() << "; should be 6" << endl;
cout << "Try to add another entry: add(extra) returns " << bagPtr->add("extra") << endl;
} // end bagTester
int
main() {
BagInterface<string> *bagPtr = nullptr;
bagPtr = new LinkedBag<string>();
cout << "Testing the Link-Based Bag:" << endl;
cout << "The initial bag is empty." << endl;
bagTester(bagPtr);
delete bagPtr;
bagPtr = nullptr;
cout << "All done!" << endl;
return 0;
} // end main