// FILE: bag.h
//
// Written by: Michael Main (main@colorado.edu), April 22, 1997.
//
// TEMPLATE CLASS PROVIDED:
//   Bag<Item> (a container template class for a collection of items)
//   The template parameter, Item, is the data type of the items in the Bag.
//   It may be any of the C++ built-in types (int, char, etc.), or a class
//   with a default constructor, an assignment operator, and operators to test
//   for equality (x == y) and non-equality (x != y).
// NOTE: This version of the Bag has an internal iterator.
//
// MEMBER CONSTANT for the Bag<Item> template class:
//   static const size_t DEFAULT_CAPACITY = _____
//    Bag<Item>::DEFAULT_CAPACITY is the initial capacity of a Bag that is
//    created by the default constructor. 
//
// CONSTRUCTOR for the Bag<Item> template class:
//   Bag(size_t initial_capacity = DEFAULT_CAPACITY)
//     Postcondition: The Bag is empty with an initial capacity given by the
//     parameter. The insert function will work efficiently (without allocating
//     new memory) until this capacity is reached.
//
// MODIFICATION MEMBER FUNCTIONS for the Bag<Item> template class:
//   void resize(size_t new_capacity)
//     Postcondition: The Bag's current capacity is changed to new_capacity
//     (but not less than the number of items currently in the Bag). The insert
//     function will work efficiently without allocating new memory) until the
//     capacity is reached.
//
//   void insert(const Item& entry)
//     Postcondition: A new copy of entry has been added to the Bag.
//     If there is a valid iterator, then the newly inserted item will be
//     inserted among the items that have not yet been iterated over.
//
//   void remove(const Item& target)
//     Postcondition: If target was in the Bag, then one copy of target has
//     been removed from the Bag; otherwise the Bag is unchanged.
//     After a successful removal, the internal iterator is no longer valid.
//
//   void operator +=(const Bag<Item>& addend)
//     Postcondition: Each item in addend has been added to this Bag.
//     If there is a valid iterator, then the newly inserted items will be
//     inserted among the items that have not yet been iterated over.
//
//   void start( )
//     Postcondition: The Bag's internal iterator has been started, so that a
//     programmer may step through the Bag's items one at a time.
//
//   void advance( )
//     Precondition: is_item returns true.
//     Postcondition: If there are more items for the internal iterator to step
//     through, then the internal iterator moves to a new item, and is_item
//     still returns true. Otherwise, is_item now returns false.
//
//   void remove_current( )
//     Precondition: is_item returns true.
//     Postcondition: The current item of the internal iterator has been
//     removed. If there are more items for the internal iterator to step
//     through, then the internal iterator has also been moved to a new item,
//     and is_item still returns true. Otherwise, is_item now returns false.
//
// CONSTANT MEMBER FUNCTIONS for the Bag<Item> template class:
//   size_t size( ) const
//     Postcondition: Return value is the total number of items in the Bag.
//
//   size_t occurrences(const Item& target) const
//     Postcondition: Return value is number of times target is in the Bag.
//
//   Item grab( ) const
//     Postcondition: The return value is a randomly selected from the Bag.
//
//   Item current( ) const
//     Precondition: is_item returns true.
//     Postcondition: The return value is the current item of the internal
//     iterator.
//
//   bool is_item( ) const
//     Postcondition: A true return value indicates that the internal iterator
//     has a valid current item that may be retrieved by the current member
//     function. A false return value indicates that there is no valid current
//     item.
//
// NON-MEMBER FUNCTIONS for the Bag<Item> template class:
//   template <class Item>
//   Bag<Item> operator +(const Bag<Item>& b1, const Bag<Item>& b2)
//     Postcondition: The Bag returned is the union of b1 and b2.
//     This returned Bag has no current item.
//
// VALUE SEMANTICS for the Bag<Item> template class:
//   Assignments and the copy constructor may be used with Bag objects.
//
// DYNAMIC MEMORY USAGE by the Bag<Item> template class: 
//   If there is insufficient dynamic memory, then the following functions call
//   new_handler: the constructors, resize, insert, operator += , operator +,
//   and the assignment operator.

#ifndef BAG_H
#define BAG_H

#include <cstdlib>

using namespace std;

template <class Item>
class Bag {
  public:
    static const size_t DEFAULT_CAPACITY = 30;
    Bag(size_t initial_capacity = DEFAULT_CAPACITY);
    Bag(const Bag& source);
    ~Bag( );
    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);
    void start( ) {
      current_index = 0; }
    void advance( );
    void remove_current( );
    size_t size( ) const {
      return used; }
    size_t occurrences(const Item& target) const;
    Item grab( ) const;
    bool is_item( ) const {
      return (current_index < used); }
    Item current( ) const;
    friend Bag<Item> operator + <> (const Bag<Item>& b1, const Bag<Item>& b2);
  private:
    Item *data;
    size_t used;
    size_t capacity;
    size_t current_index;
};

#include "bag.cpp"
#endif