Write a class LinkedBag, which includes the following operations create an empty
ID: 3770136 • Letter: W
Question
Write a class LinkedBag, which includes the following operations
create an empty bag
test if a bag is empty
get the number of items of a bag
get the frequency of items in a bag
insert a new item into a bag
remove item(s) from a bag
check if a given item is in a bag
remove all items from a bag
get the entries that are in a bag and return them within a vector
The class specification "LinkedBag.h" and test driver "main.cpp" are given. Also, the class Node definition is provided in "Node.h". Please read them carefully and complete the class implementation
----------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------
Explanation / Answer
ArrayBag
ArrayBag
#ifndef ArrayBag_Header_h
#define ArrayBag_Header_h
#include "BagInterface.h"
#include<iostream>
using namespace std;
template<class ItemType>
class ArrayBag : public BagInterface<ItemType>
{
protected:
static const int DEFAULT_CAPACITY = 6; // Small size to test for a full bag
ItemType items[DEFAULT_CAPACITY]; // Array of bag items
int itemCount; // Current count of bag items
int maxItems; // Max capacity of the bag
int getIndexOf(const ItemType& target) const;
public:
bool add(const ItemType& newEntry);
ArrayBag();
int getCurrentSize() const;
bool isEmpty() const;
bool remove(const ItemType& anEntry);
void clear();
bool contains(const ItemType& anEntry) const;
int getFrequencyOf(const ItemType& anEntry) const;
vector<ItemType> toVector() const;
void crateBag();
virtual ~ArrayBag();
// end ArrayBag
};
template<class ItemType>
int ArrayBag<ItemType>::getIndexOf(const ItemType& target) const
{
bool found = false;
int result = -1;
int searchIndex = 0;
// If the bag is empty, itemCount is zero, so loop is skipped
while (!found && (searchIndex < itemCount))
{
if (items[searchIndex] == target)
{
found = true;
result = searchIndex;
}
else
{
searchIndex++;
}//end if
}//end while
return result;
}
template<class ItemType>
bool ArrayBag<ItemType>::add(const ItemType& newEntry)
{
bool hasRoomToAdd = (itemCount < maxItems);
if (hasRoomToAdd)
{
items[itemCount] = newEntry;
itemCount++;
} // end if
return hasRoomToAdd;
}// end add
template<class ItemType>
ArrayBag<ItemType>::ArrayBag()
{
itemCount = 0;
maxItems = DEFAULT_CAPACITY;
}
template<class ItemType>
int ArrayBag<ItemType>::getCurrentSize() const
{
return itemCount;
}// end getCurrentSize
template<class ItemType>
bool ArrayBag<ItemType>::isEmpty() const
{
return itemCount == 0;
}// end isEmpty
template<class ItemType>
bool ArrayBag<ItemType>::remove(const ItemType& anEntry)
{
int locatedIndex = getIndexOf(anEntry);
bool canRemoveItem = !isEmpty() && (locatedIndex > -1);
if (canRemoveItem)
{
itemCount--;
items[locatedIndex] = items[itemCount];
}
return canRemoveItem;
}// end remove
template<class ItemType>
void ArrayBag<ItemType>::clear()
{
itemCount = 0;
}// end Clear
template<class ItemType>
bool ArrayBag<ItemType>::contains(const ItemType& anEntry) const
{
bool found = false;
int curIndex = 0; // Current array index
while (!found && (curIndex < itemCount))
{
if (anEntry == items[curIndex])
{
found = true;
} // end if
curIndex++; // Increment to next entry
} // end while
return found;
} // end contains
template<class ItemType>
int ArrayBag<ItemType>::getFrequencyOf(const ItemType& anEntry) const
{
int frequency = 0;
int curIndex = 0; // Current array index
while (curIndex < itemCount)
{
if (items[curIndex] == anEntry) {
frequency++;
} // end if
curIndex++; // Increment to next entry
} // end while
return frequency;
}//end getFrequencyOf
template<class ItemType>
ostream& operator<<(ostream & out, const ArrayBag<ItemType> & Terms)
{
for(int i=0;i<Terms.itemCount;i++)
{
cout<<Terms.items[i];
}
return out;
}
template<class ItemType>
void ArrayBag<ItemType>::crateBag()
{
Term temp;
for(int i=0;i<this->itemCount;i++)
{
cin>>temp;
add(temp);
}
}
template<class ItemType>
vector<ItemType> ArrayBag<ItemType>::toVector() const
{
vector<ItemType> bagContents;
for (int i = 0; i < itemCount; i++)
bagContents.push_back(items[i]);
return bagContents;
}
template<class ItemType>
ArrayBag<ItemType>::~ArrayBag(){}
#endif
BagInterface.h
BagInterface.h
#ifndef ArrayBag_BagInterface_h
#define ArrayBag_BagInterface_h
#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;
virtual ~BagInterface(){}
}; // end BagInterface
#endif
-------------------------------------------------------------------------------------------------------------------------------------------------------------------
Linkedbag.h
#pragma once
#include "BagInterface.h"
#include "Node.h"
using namespace std;
#include<iostream>
template < class ItemType>
class LinkedBag : public BagInterface<ItemType>
{
private:
Node<ItemType>* headPtr; // Pointer to first node
int itemCount; // Current count of bag items
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();
void displayBag();
bool contains(const ItemType& anEntry) const;
int getFrequencyOf(const ItemType& anEntry) const;
vector<ItemType> toVector() const;
};
template < class ItemType>
LinkedBag<ItemType>::LinkedBag() : headPtr(nullptr), itemCount(0)
{
} // end default constructor
template < class ItemType>
bool LinkedBag<ItemType>::add(const ItemType& newEntry)
{
Node<ItemType>* newNodePtr = new Node<ItemType>();
newNodePtr->setItem(newEntry);
newNodePtr->setNext(headPtr); // New node points to chain
headPtr = newNodePtr; // 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>::isEmpty() const
{
return itemCount == 0;
} // end isEmpty
template < class ItemType>
int LinkedBag<ItemType>::getCurrentSize() const
{
return itemCount;
} // end getCurrentSize
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;
}
template < class ItemType>
Node<ItemType>* LinkedBag<ItemType>::
getPointerTo(const ItemType& target) const
{
bool found = false;
Node<ItemType>* curPtr = headPtr;
while (!found && (curPtr != nullptr))
{
if (target == curPtr->getItem())
found = true;
else
curPtr = curPtr->getNext();
} // end while
return curPtr;
}
template < class ItemType>
bool LinkedBag<ItemType>::contains(const ItemType& anEntry) const
{
return (getPointerTo(anEntry) != nullptr);
} // end contains
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;
cout << "Removing" << endl;
itemCount--;
} // end if
return canRemoveItem;
} // end remove
template < class ItemType>
void LinkedBag<ItemType>::clear()
{
Node<ItemType>* nodeToDeletePtr =NULL;
while (headPtr != nullptr)
{
Node<ItemType>* nodeToDeletePtr = headPtr;
headPtr = headPtr->getNext();
// Return node to the system
nodeToDeletePtr->setNext(nullptr);
delete nodeToDeletePtr;
} // end while
// headPtr is nullptr
nodeToDeletePtr = nullptr;
itemCount = 0;
} // end clear
template < class ItemType>
LinkedBag<ItemType>::~LinkedBag()
{
clear();
} // end destructor
template < class ItemType>
void LinkedBag<ItemType>::displayBag()
{
cout << "The bag contains " << this->getCurrentSize()
<< " items:" << endl;
Node<ItemType>*curPtr=this->headPtr;
Node<ItemType>*curPtr2 = this->headPtr;
int counter=0;
cout <<endl<< "Economy class" << endl;
cout << "--------------------------------------------" << endl << endl;
while (curPtr2 != nullptr)
{
if (curPtr2->getItem().getSitn() >5){
cout << curPtr2->getItem();
}
curPtr2 = curPtr2->getNext();
counter++;
}
cout <<endl<< "First Class" << endl;
cout << "--------------------------------------------" << endl << endl;
while(curPtr!=nullptr)
{
if (curPtr->getItem().getSitn() <= 5){
cout << curPtr->getItem();
}
curPtr = curPtr->getNext();
counter++;
}
cout << endl << endl;
}
template < class ItemType>
LinkedBag<ItemType>::LinkedBag(const LinkedBag<ItemType>& aBag)
{
itemCount = aBag->itemCount;
Node<ItemType>* origChainPtr = aBag->headPtr;
if (origChainPtr == nullptr)
headPtr = nullptr; // Original bag is empty; so is copy
else
{
// Copy first node
headPtr = new Node<ItemType>();
headPtr->setItem(origChainPtr->getItem());
// Copy remaining nodes
Node<ItemType>* newChainPtr = headPtr; // Last-node pointer
while (origPtr != nullptr)
{
origChainPtr = origChainPtr->getNext(); // Advance pointer
// 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();
} // end while
newChainPtr->setNext(nullptr);
} // end if
} // end copy constructor
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.