You will use the array bag code that we reviewed in the text book. This code is provided with this assignment. In this code I have added one new method to the class for you to use as a guide. You should remove all traces of the "doSomething" method in all the files.
You will write 3 new methods in the ArrayBag class:
Your client code should give the user the option to:
Allow the user to keep doing these things until they are done.
Do not automatically sort the bag if the user chooses to search. Your program should give the user a message telling them they must first sort the bag before they can search. You decide what the user interface will be. Make it clear and easy to use. It can be very basic; nothing fancy. A menu driven program works well.
Each value in your array should be unique - no value will appear in the array multiple times.
Your array elements can be any data type - use a template class put in place in the code provided. You can write your client code to process a bag holding any data type you want.
Write your client code in a modular, structured fashion. Make sure you perform input validation where appropriate. This program should be bullet-proof and well documented.
ArrayBag.h
#ifndef ARRAY_BAG_
#define ARRAY_BAG_
#include "BagInterface.h"
template< class ItemType >
class ArrayBag : public BagInterface< ItemType >
{
private:
static const int DEFAULT_CAPACITY = 20; // 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
// Returns either the index of the element in the array items that
// contains the given target or -1, if the array does not contain
// the target.
int getIndexOf(const ItemType& target) const;
public:
ArrayBag();
// Example of adding a new method
void doSomething();
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;
std::vector< ItemType > toVector() const;
}; // end ArrayBag
#include "ArrayBag.cpp"
#endif
ArrayBag.cpp
#include "ArrayBag.h"
#include < iostream >
#include < cstddef >
// Example of adding a new method
template< class ItemType >
void ArrayBag< ItemType >::doSomething()
{
std::cout < < "doing somethingn";
} // end isEmpty
template< class ItemType >
ArrayBag< ItemType >::ArrayBag(): itemCount(0), maxItems(DEFAULT_CAPACITY)
{
} // end default constructor
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 >::add(const ItemType& newEntry)
{
bool hasRoomToAdd = (itemCount < maxItems);
if (hasRoomToAdd)
{
items[itemCount] = newEntry;
itemCount++;
} // end if
return hasRoomToAdd;
} // end add
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];
} // end if
return canRemoveItem;
} // end remove
template< class ItemType >
void ArrayBag< ItemType >::clear()
{
itemCount = 0;
} // end clear
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 >
bool ArrayBag< ItemType >::contains(const ItemType& anEntry) const
{
return getIndexOf(anEntry) > -1;
} // end contains
template< class ItemType >
std::vector< ItemType > ArrayBag< ItemType >::toVector() const
{
std::vector< ItemType > bagContents;
for (int i = 0; i < itemCount; i++)
bagContents.push_back(items[i]);
return bagContents;
} // end toVector
// private
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;
} // end getIndexOf
BagInterface.h
#ifndef BAG_INTERFACE_
#define BAG_INTERFACE_
#include < vector >
template< class ItemType >
class BagInterface
{
public:
// Example of adding a new method
virtual void doSomething() = 0;
// Gets the current number of entries in this bag.
// Returns the integer number of entries currently in the bag
virtual int getCurrentSize() const = 0;
// Sees whether this bag is empty.
// Returns True if the bag is empty, or false if not
virtual bool isEmpty() const = 0;
// Adds a new entry to this bag.
// If successful, newEntry is stored in the bag and
// the count of items in the bag has increased by 1.
// Input: newEntry The object to be added as a new entry.
// Returns 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.
// If successful, anEntry has been removed from the bag
// and the count of items in the bag has decreased by 1.
// Input: anEntry The entry to be removed.
// Returns: True if removal was successful, or false if not
virtual bool remove(const ItemType& anEntry) = 0;
// Removes all entries from this bag.
// Result: 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.
// Input: anEntry The entry to be counted
// Returns: 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.
// Input: anEntry The entry to locate
// Returns: 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.
// Returns: A vector containing all the entries in the bag
virtual std::vector< ItemType > toVector() const = 0;
// Destroys object and frees memory allocated by object.
virtual ~BagInterface () { }
}; // end BagInterface
#endif
ArrayBagClient.cpp
#ifndef BAG_INTERFACE_
#define BAG_INTERFACE_
#include < vector >
template< class ItemType >
class BagInterface
{
public:
// Example of adding a new method
virtual void doSomething() = 0;
// Gets the current number of entries in this bag.
// Returns the integer number of entries currently in the bag
virtual int getCurrentSize() const = 0;
// Sees whether this bag is empty.
// Returns True if the bag is empty, or false if not
virtual bool isEmpty() const = 0;
// Adds a new entry to this bag.
// If successful, newEntry is stored in the bag and
// the count of items in the bag has increased by 1.
// Input: newEntry The object to be added as a new entry.
// Returns 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.
// If successful, anEntry has been removed from the bag
// and the count of items in the bag has decreased by 1.
// Input: anEntry The entry to be removed.
// Returns: True if removal was successful, or false if not
virtual bool remove(const ItemType& anEntry) = 0;
// Removes all entries from this bag.
// Result: 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.
// Input: anEntry The entry to be counted
// Returns: 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.
// Input: anEntry The entry to locate
// Returns: 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.
// Returns: A vector containing all the entries in the bag
virtual std::vector< ItemType > toVector() const = 0;
// Destroys object and frees memory allocated by object.
virtual ~BagInterface () { }
}; // end BagInterface
#endif
#include < iostream >
#include < string >
#include "ArrayBag.h"
using namespace std;
void bagTester(ArrayBag< int >& bag);
int main()
{
// This is one way you can get values in the bag.
// You could also read the values from a file.
// You pick - but you should load up the bag with values.
ArrayBag< int > bag;
int items[] = {1, 33, 6, 9, 2, 65, 4, 29, 5, 8, 39, 88, 7, 25, 51, 3, 99, 14, 11, 10};
cout << "Adding positive integers to the bag: " << endl;
for (int i = 0; i < 20; i++)
{
bag.add(items[i]);
} // end for
// You will remove this sample funciton from your program
bagTester(bag);
// This shows the client program invoking the new method "doSomething"
// You will remove all traces of "doSomething" from all program files
bag.doSomething();
return 0;
} // end main
void bagTester(ArrayBag< int >& bag)
{
// This is just some sample code processing the bag.
// You should remove this function from your program completely.
cout << "The bag is not empty; isEmpty: returns " << bag.isEmpty() << endl;
cout << "About to clear the bag, ";
bag.clear();
cout << "isEmpty: returns " << bag.isEmpty() << endl;
} // end bagTester