#include <stdlib.h>  // Provides size_t
#include <assert.h>  // Provides assert
template <class Item>
class Bag
{
   public:
        // MEMBER CONSTANTS
        enum { DEFAULT_CAPACITY = 30 }; // Or:
        // static const size_t DEFAULT_CAPACITY = 30;
        // CONSTRUCTORS and DESTRUCTOR
        Bag(size_t initial_capacity = DEFAULT_CAPACITY);
        Bag(const Bag& source);
        ~Bag( );
        // MODIFICATION MEMBER FUNCTIONS
        void resize(size_t capacity);
        void insert(const Item& entry);
        void remove(const Item& target);
        void operator +=(const Bag& addend);
        void operator =(const Bag& source);
        // CONSTANT MEMBER FUNCTIONS
        size_t size( ) const { return used; }
        size_t occurrences(const Item& target) const;
        Item grab( ) const;
        // FRIEND FUNCTIONS
        friend Bag<Item> operator +(const Bag<Item>& b1, const Bag<Item>& b2);
        friend void operator >> (istream& ins, Bag& b);
        friend void operator << (ostream& outs, Bag& b);
    private:
        Item *data;        // Pointer to partially filled dynamic array
        size_t used;       // How much of array is being used
        size_t capacity;   // Current capacity of the Bag
};

template <class Item>
Bag<Item>::Bag(size_t initial_capacity)
{
    data = new Item[initial_capacity];
    capacity = initial_capacity;
    used = 0;
}

template <class Item>
Bag<Item>::Bag(const Bag<Item>& source)
{
    size_t i;  // An array index

    data = new Item[source.capacity];
    capacity = source.capacity;
    used = source.used; 
    for (i = 0; i < used; i++)
        data[i] = source.data[i];                
}

template <class Item>
Bag<Item>::~Bag( )
{
     delete [ ] data;
}

template <class Item>
void Bag<Item>::resize(size_t new_capacity)
{
    size_t i;
    Item *larger_array;

    if (new_capacity == capacity)
        return; // The allocated memory is already the right size

    if (new_capacity < used)
        new_capacity = used; // Can't allocate less than we are using

    larger_array = new Item[new_capacity];
    for (i = 0; i < used; i++)
        larger_array[i] = data[i];
    delete [ ] data;
    data = larger_array;
    capacity = new_capacity;
}

template <class Item>
void Bag<Item>::insert(const Item& entry)
{   
    if (used == capacity)
        resize(used+1);
    data[used] = entry;
    used++;
}

template <class Item>
Item Bag<Item>::grab( ) const
{
    size_t i;

    assert(size( ) > 0);
    i = (rand( ) % size( )); // i is in the range of 0 to size( ) - 1
    return data[i];
}

template <class Item>
void Bag<Item>::remove(const Item& target)
{
    size_t index; // The location of target in the data array    

    for (index = 0; (index < used) && (data[index] != target); index++);

    if (index == used)
        return; // target isn't in the Bag, so no work to do

    used--;
    data[index] = data[used];
}

template <class Item>
void Bag<Item>::operator +=(const Bag<Item>& addend)
{
    size_t i; // An array index
    size_t other_bag_size = addend.used;

    if (used + other_bag_size < capacity)
        resize(used + other_bag_size);
    for (i = 0; i < other_bag_size; i++)
    {
        data[used] = addend.data[i];
        used++;
    }
}

template <class Item>
void Bag<Item>::operator =(const Bag<Item>& source)
{
    size_t i;
    Item *new_data;

    if (capacity != source.capacity)
    { 
        new_data = new Item[source.capacity];
        delete [ ]data;
        data = new_data;
        capacity = source.capacity;
    }
    used = source.used;
    for (i = 0; i < used; i++)
        data[i] = source.data[i];
}

template <class Item>
size_t Bag<Item>::occurrences(const Item& target) const
{
    size_t answer;  // Number of times target occurs
    size_t i;       // An array index

    answer = 0;
    for (i = 0; i < used; i++)
        if (target == data[i])
            answer++;
    return answer;
}

template <class Item>
Bag<Item> operator +(const Bag<Item>& b1, const Bag<Item>& b2)
{
    Bag<Item> answer(b1.capacity + b2.capacity);

    answer += b1; 
    answer += b2;
    return answer;
}

template <class Item>
void operator >> (istream& ins, Bag<Item>& b)
{
    Item number;
    cout << "Enter numbers, a negative number when you are done: ";
    ins >> number;
    while (number >= 0)
    {
        if (b.size( ) < b.capacity)
            b.insert(number);
        else
            cout << "I have run out of room and can't add that number." << endl;
        cin >> number;
    }
}

template <class Item>
void operator << (ostream& outs, Bag<Item>& b)
{
    outs << "( ";
    for(int i = 0; i < b.used; i++)
       outs << b.data[i] << " ";
    outs << ")" << endl;
}