//---------------------------------------------------------------------
// File: stack.template
// Name: Sharon M. Tuttle
// last modified: 1-27-05
//
// Template class name: stack
//
// Purpose: a collection of items such that entries can be
//    inserted and removed at only one end (called the top)
// 
// Implementation notes: 
//     * uses a dynamically-allocated array
//     * if there is insufficient dynamic memory, then the
//       following methods throw bad_alloc: push
//---------------------------------------------------------------------

#include <cassert> // provides assert
//
// note: because this is a template class, it is included
//    in the header file (at the bottom), and not compiled
//    separately. Thus, the header file is not included here!
//
using namespace std;

/*****************************************************/
/* CONSTRUCTORS and DESTRUCTOR                       */
/*****************************************************/

// constructor
//
// postcondition: creates an empty stack  instance
//
template <typename Item>
stack<Item>::stack()
{
    data = new Item[DEFAULT_CAPACITY];
    capacity = DEFAULT_CAPACITY;
    used = 0;
}

// copy constructor (because am using a pointer to
//    point to an array, so that array can be replaced with
//    a larger one as needed.
//
template <typename Item>
stack<Item>::stack(const stack<Item>& source)
{
    data = new Item[source.capacity];
    capacity = source.capacity;
    used = source.used;

    // copy over significant array contents
    for (int i=0; i<used; i++)
    {
        data[i] = source[i];
    }
}

// destructor (because am using a pointer to point to
//    an array, so that array can be replaced with a
//    larger one as needed.
//
template <typename Item>
stack<Item>::~stack()
{
    delete [] data;
}


/*************************************************************/
/* ACCESSORS and other constant member functions (observers) */
/*************************************************************/

// is_empty
//
// postcondition: returns true if stack is empty, and
//    returns false otherwise
//
template <typename Item>
bool    stack<Item>::is_empty( ) const
{
    return (used == 0);
}

// get_top
//
// precondition: is_empty() == false
//
// postcondition: returns the value of the top item of the
//    stack, BUT the stack is unchanged.
//
template <typename Item>
Item    stack<Item>::get_top( ) const
{
    assert(is_empty() == false);

    return(data[used-1]);
}

/*****************************************************/
/* MODIFIERS and other modifying member functions    */
/*****************************************************/

// push
//
// postcondition: a new copy of entry has been pushed
//    onto the (top of the) stack
//
template <typename Item>
void    stack<Item>::push(const Item& entry)
{
    Item *larger_data;	// IF need to create new, larger array

    if (used == capacity)
    {
        capacity += stack<Item>::INCR_AMT;
        larger_data = new Item[capacity];
        
        // copy data into new array
        for (int i=0; i<used; i++)
        {
            larger_data[i] = data[i];
        }

        // release the memory data currently pointing to
        delete [ ] data;

        // now make data point to the new, bigger array
        data = larger_data;
    }

    data[used] = entry;
    used++;
}

// pop
//
// precondition: is_empty() == false
//
// postcondition: the top item of the stack has been
//    removed, and a reference to it is returned
//
template <typename Item>
Item&   stack<Item>::pop( )
{
    assert(is_empty() == false);

    used--;
    return data[used];
}