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:

  • bubbleSort - a method to sort the array in ascending order using the bubble sort
  • binarySearchIterative - a repetitive version of the binary search
  • binarySearchRecursive - a recursive version of the binary search (You should use a helper or middle-man method that calls the recursive method so the client code does not have to provide the extra parameters. Client calls to both of the methods should be identical other than the method name.)

Your client code should give the user the option to:

  • display the contents of the bag using the class method "toVector"
  • add values to the bag
  • remove values from the bag
  • sort the bag
  • search for a value using the iterative search or the recursive search

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.

Starter Code

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
Academic Honesty!
It is not our intention to break the school's academic policy. Posted solutions are meant to be used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly complete the form. Please provide a valid email address and we will get back to you within 24 hours. Payment is through PayPal, Buy me a Coffee or Cryptocurrency. We are a nonprofit organization however we need funds to keep this organization operating and to be able to complete our research and development projects.