*Create a funcion named ramove2() that removes a given number in the linkedbag while maintaining the order*

Node.h

#pragma once

#include

template < class ItemType>

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;

};

template < class ItemType>

Node::Node() : next(nullptr)

{

} // end default constructor

template < class ItemType>

Node::Node(const ItemType& anItem) : item(anItem), next(nullptr)

{

} // end constructor

template < class ItemType>

Node::Node(const ItemType& anItem, Node* nextNodePtr) :

item(anItem), next(nextNodePtr)

{

} // end constructor

template < class ItemType>

void Node::setItem(const ItemType& anItem)

{

item = anItem;

} // end setItem

template < class ItemType>

void Node::setNext(Node* nextNodePtr)

{

next = nextNodePtr;

} // end setNext

template < class ItemType>

ItemType Node::getItem() const

{

return item;

} // end getItem

template < class ItemType>

Node* Node::getNext() const

{

return next;

}

BagInterface.h

#pragma once

#include

using namespace std;

template

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 toVector() const = 0;

LinkedBag.h

#pragma once

#include "BagInterface.h"

#include "Node.h"

template < class ItemType>

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 add2(const ItemType& newEntry);

bool remove(const ItemType& anEntry);

void printPtr();

void clear();

bool contains(const ItemType& anEntry) const;

int getFrequencyOf(const ItemType& anEntry) const;

vector toVector() const;

};

template

LinkedBag::LinkedBag() : headPtr(nullptr), itemCount(0)

{

cout << "Copy Costructor" << endl;

} // 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();

nodeToDeletePtr->setNext(nullptr);

delete nodeToDeletePtr;

nodeToDeletePtr = headPtr;

}

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);

}

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;

}

template

void LinkedBag::printPtr()

{

Node* disPtr = headPtr;

while (disPtr != nullptr)

{

cout << disPtr->getItem() << ", ";

disPtr = disPtr->getNext();

}

cout << endl;

}

template

bool LinkedBag::add2(const ItemType& newEntry)

{

Node* nextNodePtr = new Node();

Node* lastPtr = headPtr;

nextNodePtr->setItem(newEntry);

nextNodePtr->setNext(nullptr);

if (this->isEmpty())

headPtr = nextNodePtr;

else {

for (int i = 1; i < itemCount; i++)

lastPtr = lastPtr->getNext();

lastPtr->setNext(nextNodePtr);

}

itemCount++;

return true;

}

LinkedBagMain.cpp

#include"LinkedBag.h"

#include

using namespace std;

int main() {

LinkedBag bag;

LinkedBag copy(bag);

copy.printPtr();

cout << "Adding numbers at the beginning of the list." << endl;

bag.add(10);

bag.add(13);

bag.add(66);

bag.add(42);

bag.add(31);

bag.add(9);

bag.printPtr();

cout << endl;

cout << "Validating the existance of the number 66 in the list(prints how many times the number is on the list)"<< endl;

cout << "The number 66 is " << bag.contains(66) << " times in the list" << endl << endl;

cout << "Validating the existance of the number 32 in the list(prints how many times the number is on the list)" << endl;

cout << "The number 32 is " << bag.contains(32) << " times in the list" << endl << endl;

cout << "Removing the number 31 from the list." << endl;

bag.remove(31);

bag.printPtr();

cout << endl;

cout << "Adding a number a the end of the list." << endl;

bag.add2(45);

bag.printPtr();

cout << endl;

system("pause");

return 0;

}