//-----------------------------------------------------------
// File: set.h
// Name: Michael Main, Walter Savitch
//       (adapted by Sharon M. Tuttle)
// last modified: 4-28-05 
//
// Template Class: set (a container template class for a collection
//                of items with NO duplicates)
//
// VALUE SEMANTICS for the set class:
//    Assignments and the copy constructor may be used 
//       with set objects.
//
// DYNAMIC MEMORY USAGE by the set:
//    If there is insufficient dynamic memory, then the
//       following functions throw bad_alloc:
//          The constructors, reserve, insert, operator +=,
//          operator +, and the assignment operator. 
//-----------------------------------------------------------

#ifndef SET_H
#define SET_H

#include <cstdlib>  // Provides size_t
using namespace std;

template <typename Item>
class set
{
    public:

        /****************************************************/
        /* TYPEDEFS and MEMBER CONSTANTS for the set class  */
        /****************************************************/

        // set::value_type is the data type of the items in the
        //    set. 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).
        //
        typedef Item value_type;

        // set::DEFAULT_CAPACITY is the initial capacity of a
        //    set that is created by the default constructor.
        //
        static const size_t DEFAULT_CAPACITY = 30; 

        // set::INCR_AMT is how much additional capacity is
        //    added when one tries to add to a "full" set
        //
        // (here, the guess is that, after the initial burst,
        //    graphs do not grow by MANY vertices at a time;
        //
        static const size_t INCR_AMT = 5;
            
        /****************************************************/
        /* CONSTRUCTORS and DESTRUCTOR                      */
        /****************************************************/

        // assumption regarding set capacity:
        //    The insert member function will work efficiently
        //    (without allocating new memory) until this
        //    capacity is reached.
    
        // postcondition: creates an empty set instance with an 
        //    initial capacity of DEFAULT_CAPACITY
        //
        set();

        // copy constructor
        //
        set(const set& source);
            
        // destructor
        //
        ~set( );
    
        /*************************************************************/
        /* ACCESSORS and other constant member functions (observers) */
        /*************************************************************/
    
        // postcondition: returns the number of items in the set.
        // 
        size_t get_size( ) const;

        // postcondition: returns true if the target is in the set,
        //    and returns false if it is not.
        // 
        bool contains(const Item& target) const;
    
        // postcondition: returns true if there is a valid "current"
        //     item that may be returned by the current member function.
        //     Returns false if there is no valid current item.
        //
        bool is_item() const;

        // precondition: is_item() == true
        // postcondition: returns the current item in the set's
        //     internal iterator.
        //
        value_type current() const;
    
        /****************************************************/
        /* MODIFIERS and other modifying member functions   */
        /****************************************************/

        // postcondition: if target was in the set, remove it and
        //    return true; otherwise, return false (and the set is
        //    unchanged)
        //
        bool remove(const Item& target);

        // postcondition: if entry is not already in the set,
        //    then add it to the set; otherwise, set is unchanged.
        // 
        void add(const Item& entry);
    
        // postcondition: one of the items in the set becomes 
        //     the current item (but if the set is empty, there
        //     is no current item)
        //
        void start();

        // precondition: is_item() == true
        // postcondition: if the current item is the last in the
        //     set's internal iterator, then there is no longer
        //     any current item. Otherwise, the new current item
        //     is another set element that has not yet been current
        //     during this internal iterator.
        //
        void advance(); 

        /*************************************************************/
        /* OTHER METHODS                                             */
        /*************************************************************/
        
        // postcondition: this returns a new set whose membership is
        //    the set-theoretic (classic) union of the calling set
        //    and <set2>
        //
        set<Item> unionWith(set<Item> set2);

        // postcondition: this returns a new set whose membership
        //    is the set-theoretic (classic) intersection of the
        //    calling set and <set2>
        //
        set<Item> intersect(set<Item> set2);

        /****************************************************/
        /* OVERLOADED OPERATORS                             */
        /****************************************************/
    
        // postcondition: for each item in addend:
        //    *   if that item is not already in this set, it is
        //        added to this set.
        //    *   if that item is already in this set, then 
        //        this set is unchanged.
        //
        void operator +=(const set& addend);
    
        // postcondition: the set that activated this function
        //    has the same items and capacity as source.
        //
        void operator =(const set& source);
            
    private:
                
        value_type *data;     // Pointer to partially filled dynamic array
        size_t used;          // How much of array is being used
        size_t capacity;      // Current capacity of the set
        size_t current_index;     // index of current element in
                                  //    internal iterator --- this
                                  //    is == to used if there is
                                  //    no current item.
};
    
/*************************************************/
/* NONMEMBER FUNCTIONS for the set class         */
/*************************************************/

// +
//
// postcondition: the set returned is the union of
//       s1 and s2.
//
template <typename Item>
set<Item> operator +(const set<Item>& s1, const set<Item>& s2);

#include "set.template"
#endif