// FILE: bag.h (part of the namespace main_savitch_10)
// TEMPLATE CLASS PROVIDED: bag<ItemType>
//     (a container template class for a collection of items)
//
// TYPEDEFS for the bag<ItemType> class:
//   bag<ItemType>::ItemType
//     bag<ItemType>::ItemType 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, a copy constructor, an assignment operator, and a
//     less-than operator forming a strict weak ordering.
//
// CONSTRUCTOR for the bag<ItemType> class:
//   bag( )
//     Postcondition: The bag is empty.
//
// MODIFICATION MEMBER FUNCTIONS for the bag<ItemType> class:
//   int erase(const ItemType& target)
//     Postcondition: All copies of target have been removed from the bag. The
//     return value is the number of copies removed (which could be zero).
//
//   bool erase_one(const ItemType& target)
//     Postcondition: If target was in the bag, then one copy of target has been
//     removed from the bag; otherwise the bag is unchanged. A true return value
//     indicates that one copy was removed; false indicates that nothing was
//     removed.
//
//   void insert(const ItemType& entry)
//     Postcondition: A new copy of entry has been inserted into the bag.
//
//   void operator +=(const bag& addend)
//     Postcondition: Each item in addend has been added to this bag.
//
// CONSTANT MEMBER FUNCTIONS for the bag<ItemType> class:
//   int size( ) const
//     Postcondition: Return value is the total number of items in the bag.
//
//   int count(const ItemType& target) const
//     Postcondition: Return value is number of times target is in the bag.
//
// NONMEMBER FUNCTIONS for the bag class:
//   bag operator +(const bag& b1, const bag& b2)
//     Postcondition: The bag returned is the union of b1 and b2.
//
// VALUE SEMANTICS for the bag class:
//   Assignments and the copy constructor may be used with bag objects.
//
// DYNAMIC MEMORY USAGE by the bag: 
//   If there is insufficient dynamic memory, then the following functions
//   throw bad_alloc: The constructors, insert, operator +=, operator +, and
//   the assignment operator.

#ifndef BAG_H 
#define BAG_H
#include <cstdlib>     // Provides NULL and size_t
#include "bintree.h"   // Provides binary_tree_node and related functions
namespace main_savitch_10
{
    template <class ItemType>
    class bag
    {
    public:
        // CONSTRUCTORS and DESTRUCTOR
        bag( ) { root_ptr = NULL; }
        bag(const bag& source);
        ~bag( );
        
        // MODIFICATION functions
        int erase(const ItemType& target);
        bool erase_one(const ItemType& target);
        void insert(const ItemType& entry);
        void operator +=(const bag& addend);
        void operator =(const bag& source);	
        
        // CONSTANT functions
        int size( ) const;
        int count(const ItemType& target) const;
	    void debug( ) const { print(root_ptr, 0); }
	    
    private:
        binary_tree_node<ItemType> *root_ptr; // Root pointer of binary search tree
        void insert_all(binary_tree_node<ItemType>* addroot_ptr);
    };

    // NONMEMBER functions for the bag<ItemType> template class
    template <class ItemType>
    bag<ItemType> operator +(const bag<ItemType>& b1, const bag<ItemType>& b2);

}
#include "bag.cpp" // Include the implementation.
#endif
