// FILE: bag4.tem
// TEMPLATE CLASS IMPLEMENTED: Bag<Item> (see bag4.h for documentation)
// This file should be included in the header file, and not compiled separately.
// INVARIANT for the Bag ADT:
//  1. The number of items in the Bag is in the member variable used;
//  2. The actual items of the Bag are stored in a partially filled array.
//     The array is a dynamic array, pointed to by the member variable data.
//  3. The size of the dynamic array is in the member variable capacity.

#include <assert.h>  // Provides assert
#include <stdlib.h>  // Provides size_t, rand

template <class Item>
Bag<Item>::Bag(size_t initial_capacity)
// Library facilities used: stdlib.h
{
    data = new Item[initial_capacity];
    capacity = initial_capacity;
    used = 0;
}

template <class Item>
Bag<Item>::Bag(const Bag<Item>& source)
// Library facilities used: stdlib.h
{
    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( )
// Library facilities used: assert.h
{   
     delete [ ] data;
}

template <class Item>
void Bag<Item>::resize(size_t new_capacity)
// Library facilities used: stdlib.h
{
    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
// Library facilities used: assert.h, stdlib.h
{
    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    

    // First, set index to the location of target in the data array,
    // which could be as small as 0 or as large as used-1.
    // If target is not in the array, then index will be set equal to used.
    for (index = 0; (index < used) && (data[index] != target); index++);

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

    // When execution reaches here, target is in the Bag at data[index].
    // So, reduce used by 1 and copy the last item onto data[index].
    used--;
    data[index] = data[used];    
}

template <class Item>
void Bag<Item>::operator +=(const Bag<Item>& addend)
// Library facilities used: assert.h, stdlib.h
{
    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)
// Library facilities used: stdlib.h
{
    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
// Library facilities used: stdlib.h
{
    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;
}