// FILE: bag.cpp
//
// TEMPLATE CLASS IMPLEMENTED: Bag<Item> (see bag.h for documentation)
//
// This file should be included by the header file, & 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.
//  4. If the internal iterator has a current item, then that item is
//     at data[current_index]; if there is no current item, then
//     current_index==used.

#include <cassert>
#include <cstdlib>

using namespace std;

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

template <class Item>
Bag<Item>::Bag(const Bag<Item>& source) {
  size_t i;
  data = new Item[source.capacity];
  capacity = source.capacity;
  used = source.used;
  current_index = source.current_index;
  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 ;
  if (new_capacity < used)
    new_capacity = used;
  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;
  if (current_index == used)
    current_index++;
  used++;
}

template <class Item>
Item Bag<Item>::grab( ) const {
  size_t i;
  assert(size( ) > 0);
  i = (rand( ) % size( ));
  return data[i];
}

template <class Item>
void Bag<Item>::remove(const Item& target) {
  size_t index;
  for (index = 0; (index < used) && (data[index] != target); index++)
    ;
  if (index == used)
    return ;
  used--;
  data[index] = data[used];
  current_index = used;
}

template <class Item>
void Bag<Item>::operator +=(const Bag<Item>& addend) {
  size_t i;
  size_t other_bag_size = addend.used;
  if (used + other_bag_size < capacity)
    resize(used + other_bag_size);
  if (!is_item( ))
    current_index = 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;
  current_index = source.current_index;
  for (i = 0; i < used; i++)
    data[i] = source.data[i];
}

template <class Item>
void Bag<Item>::advance( ) {
  assert(is_item( ));
  current_index++;
}

template <class Item>
void Bag<Item>::remove_current( ) {
  assert(is_item( ));
  data[current_index] = data[--used];
}

template <class Item>
Item Bag<Item>::current( ) const {
  assert(is_item( ));
  return data[current_index];
}

template <class Item>
size_t Bag<Item>::occurrences(const Item& target) const {
  size_t answer;
  size_t i;
  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;
}