//---------------------------------------------------------------------
// File: stack.cpp
// Name: Sharon M. Tuttle
// last modified: 3-10-05
//
// Class name: stack
//
// Purpose: a collection of items such that entries can be
//    inserted and removed at only one end (called the top)
//    This version does NOT have a fixed capacity.
//
// Implementation notes: 
//     *   uses a dynamically-allocated linked list of
//         nodes
//     *   stack constructor and push can fail if new
//         cannot allocated sufficient space.
//---------------------------------------------------------------------

#include <cassert> // provides assert
#include "node.h"
#include "stack.h"
using namespace std;

/*****************************************************/
/* CONSTRUCTOR                                       */
/*****************************************************/

// constructor
//
// postcondition: creates an empty stack instance
//
stack::stack()
{
    used = 0;
    top = NULL;
}

// copy constructor
//
// (adapted from list_copy, Savitch and Main,
//    p. 241)
stack::stack(const stack& source)
{
    node *source_curr, *new_curr;

    top = NULL;
    
    used = source.used;

    // handle the case of the empty stack
    if (source.top == NULL)
    {
        return; // source is empty, so this copy is, too
    }

    // if source is NOT empty, make a copy of it

    // cause new copy to now have source top's data; 

    top = new node(source.top->get_data());

    // start a pointer walking through the new copy
    //    starting from its top
    new_curr = top;

    // is there another in the source left to be copied?
    source_curr = source.top->get_next();

    // while there is another node in the source left
    //     to be copied...
    while (source_curr != NULL)
    {
        // add a new node to the new copy with the data in
        //    that node;
        new_curr->set_next(new node(source_curr->get_data()));

        // move the new copy's pointer to the new node
        new_curr = new_curr->get_next();

        // is there another in the source left to be copied?
        source_curr = source_curr->get_next();
    }
}

// destructor
//
stack::~stack( )
{
    node *curr_ptr, *node_to_delete;

    curr_ptr = top;

    // need to deallocate EACH node in the stack
    while (curr_ptr != NULL)
    {
        node_to_delete = curr_ptr;
        curr_ptr = curr_ptr->get_next();
        delete node_to_delete;
    }

    // playing it safe...
    top = NULL;
    used = 0;
}
       
/*************************************************************/
/* ACCESSORS and other constant member functions (observers) */
/*************************************************************/

// is_empty
//
// postcondition: returns true if stack is empty, and
//    returns false otherwise
//
bool stack::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.
//
stack::value_type stack::get_top( ) const
{
    assert(is_empty() == false);

    return(top->get_data());
}

// get_size
//
// postcondition: returns the number of elements 
//    currently in the stack
//
int stack::get_size( ) const
{
    return used;
}

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

// push
//
// postcondition: a new copy of entry has been pushed
//    onto the (top of the) stack
//
void stack::push(const value_type& entry)
{
    node *temp;

    temp = new node(entry);

    // new top element's next field needs to point to 
    //    "old" top element
    temp->set_next(top);

    // now, top can safely be made to point to new top
    //    element
    top = temp;

    used++;
}

// pop
//
// precondition: is_empty() == false
//
// postcondition: the top item of the stack has been
//    removed, and its value is returned
//
stack::value_type stack::pop( )
{
    value_type popped_item;
    node*      temp;

    assert(is_empty() == false);

    used--;

    // remember: if we reach here, we KNOW that stack is 
    //    not empty
    
    popped_item = top->get_data();

    // keep track of item to be removed
    temp = top;

    // now it should be safe to make top point to the
    //    new top element
    top = top->get_next();

    // free the space for this popped node from the heap,
    //    so it be be re-allocated for other uses
    delete temp;

    return popped_item;
}