/////////////////
// BagInterface.h
/////////////////
#ifndef _BAG_INTERFACE
#define _BAG_INTERFACE

#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;
};

#endif


//////////////////
//Bag.h
//////////////////
#ifndef _BAG
#define _BAG

#include "BagInterface.h"

template<class T>
class Bag : public BagInterface<T>
{
private:
	static const int DEFAULT_BAG_SIZE = 6;
	T items[DEFAULT_BAG_SIZE];  // array of bag items
	int itemCount;				// current count of bag items
	int maxItems;				// max capacity of the bag
	int getIndexOf(const T& target) const;

public:
	Bag() : itemCount(0), maxItems(DEFAULT_BAG_SIZE) { }
	int getCurrentSize() const { return itemCount; }
	bool isEmpty() const { return itemCount == 0; }
	bool add(const T& newEntry);
	bool remove(const T& anEntry);
	void clear();
	bool contains(const T& anEntry) const;
	int getFrequencyOf(const T& anEntry) const;
	vector<T> toVector() const;
};  // end Bag

template<class T>
bool Bag<T>::add(const T& newEntry) {
	bool hasRoomToAdd = (itemCount < maxItems);
	if (hasRoomToAdd) {
		items[itemCount] = newEntry;
		itemCount++;
	}
	return hasRoomToAdd;
}

template<class T>
bool Bag<T>::remove(const T& anEntry) {
	int locatedIndex = getIndexOf(anEntry);
	bool canRemoveItem = !isEmpty() && (locatedIndex > -1);
	if (canRemoveItem) {
		itemCount--;
		items[locatedIndex] = items[itemCount];
	}

	return canRemoveItem;
}  // end remove

template<class T>
void Bag<T>::clear() {
	itemCount = 0;
}

template<class T>
int Bag<T>::getFrequencyOf(const T& anEntry) const {
	int frequency = 0;
	int searchIndex = 0;
	while (searchIndex < itemCount) {
		if (items[searchIndex] == anEntry) {
			frequency++;
		}
		searchIndex++;
	}
	return frequency;
}

template<class T>
bool Bag<T>::contains(const T& anEntry) const {
	return getIndexOf(anEntry) > -1;
}


template<class ItemType>
vector<ItemType> Bag<ItemType>::toVector() const
{
	vector<ItemType> bagContents;
	for (int i = 0; i < itemCount; i++)
		bagContents.push_back(items[i]);
	return bagContents;
}  // end toVector

// private
template<class ItemType>
int Bag<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
#endif


////////////////////
//usingBag.cpp
////////////////////
#include <iostream> // For cout and cin
#include <string> // For string objects
#include "Bag.h" // For ADT bag
using namespace std;

int main()
{
    string clubs[] = { "Joker", "Ace", "Two", "Three",
    "Four", "Five", "Six", "Seven",
    "Eight", "Nine", "Ten", "Jack",
    "Queen", "King" };
    // Create our bag to hold cards.
    Bag<string> grabBag;
    // Place six cards in the bag.
    grabBag.add(clubs[1]);
    grabBag.add(clubs[2]);
    grabBag.add(clubs[4]);
    grabBag.add(clubs[8]);
    grabBag.add(clubs[10]);
    grabBag.add(clubs[12]);
    // Get friend’s guess and check it.
    int guess = 0;
    while (!grabBag.isEmpty())
    {
        cout << "What is your guess?"
        << "(1 for Ace to 13 for King):";
        cin >> guess;
        // Is card in the bag?
        if (grabBag.contains(clubs[guess]))
        {
            // Good guess – remove card from the bag.
            cout << "You get the card!\n";
            grabBag.remove(clubs[guess]);
        }
        else
        {
            cout << "Sorry, card was not in the bag.\n";
        } // end if
    } // end while
    cout << "No more cards in the bag. Game over!\n";
    return 0;
}; // end main