/*      File Name:      stackll.cpp
        Author:         R.P. Patillo
        Instructor:     Dr. Ames
        Due Date:       Oct. 23, 2008
        Complilation:   g++ stackclient.cpp -o stackclient.out
        Execution:      ./stackclient.out
*/

// Implementation file for Stack ADT.
// Class definition is in "stackll.h".

// Class is templated; implementation is linked.
// ItemType is determined when a specific Stack class is instantiated.

//-------------------------------------------------------------------------------
// NodeType for nodes in linked list
//-------------------------------------------------------------------------------

template <class ItemType>
struct NodeType
{
   ItemType info;
   NodeType<ItemType>* next;
};

//-------------------------------------------------------------------------------
// Stack Constructor - initializes an empty stack
//-------------------------------------------------------------------------------

template<class ItemType>
StackType<ItemType>::StackType()
{
    topPtr = NULL;
}

//-------------------------------------------------------------------------------
// Stack Destructor - releases memory used by nodes
//-------------------------------------------------------------------------------

template <class ItemType>
StackType<ItemType>::~StackType()
{
    NodeType<ItemType>* tempPtr;

    while (topPtr != NULL)
    {
	    tempPtr = topPtr;
	    topPtr = topPtr->next;
	    delete tempPtr;
    }
}

//-------------------------------------------------------------------------------
// IsEmpty - tests for empty stack
//-------------------------------------------------------------------------------

template <class ItemType>
bool StackType<ItemType>::IsEmpty() const
{
    return (topPtr == NULL);
}

//-------------------------------------------------------------------------------
// IsFull - tests for full stack  (linked implementation "never" full!)
//-------------------------------------------------------------------------------

template<class ItemType>
bool StackType<ItemType>::IsFull() const
{
    return false;
}

//-------------------------------------------------------------------------------
// Push  - adds item to top of stack
//-------------------------------------------------------------------------------
// Accepts:   Item to be added
//-------------------------------------------------------------------------------

template <class ItemType>
void StackType<ItemType>::Push(ItemType newItem)
{
    NodeType<ItemType>* ptr;
    ptr = new NodeType<ItemType>;
    ptr->info = newItem;
    ptr->next = topPtr;
    topPtr = ptr;
}

//-------------------------------------------------------------------------------
// Pop - removes top item from stack
//-------------------------------------------------------------------------------

template<class ItemType>
void StackType<ItemType>::Pop()
{
    if (!IsEmpty())
    {
        NodeType<ItemType>* tempPtr;
        tempPtr = topPtr;
        topPtr = topPtr->next;
        delete tempPtr;
    }
    else 
        cout << "\nError - attempting to pop empty stack!";
}

//-------------------------------------------------------------------------------
// Top - shows copy of top stack item leaving stack structure intact
//-------------------------------------------------------------------------------
// Returns:  copy of top item
//-------------------------------------------------------------------------------

template<class ItemType>
ItemType StackType<ItemType>::Top()
{
    if (!IsEmpty())
        return topPtr->info;
    else
        cout << "\nError - viewing top of empty stack - returned item ??";
}

//-------------------------------------------------------------------------------
// CopyNth - returns a copy of the item located in the Nth position of a stack
//-------------------------------------------------------------------------------
// Returns:  copy of top item
//-------------------------------------------------------------------------------

template <class ItemType>
void StackType<ItemType> :: CopyNth (int N, ItemType& copyitem)
{
    NodeType <ItemType>* tempPtr = topPtr;
 
    for(int i=0; i<N-1; i++)		// moves tempPtr down list desired N times (which is N-1)
	tempPtr = tempPtr->next;
    copyitem = tempPtr->info;
}