/*
 * This file gives the interface and implementation for
 * a stack using a linked list.
 * Author: Anthony Larrain
 */

#ifndef STACK_H
#define STACK_H

#include <cstdlib>
#include <stdexcept>
using namespace std;

namespace utils
{
    template <typename T>
    class Stack
    {                   
        private:
            struct Node
            {
                Node(const T& D, Node* N = NULL) :
                    data(D) , next(N) { }

				T data;
				Node *next;
            };
            int theSize;
            Node *topNode;
                        
        public:
            Stack() :
                theSize(0), topNode(NULL) {}
            Stack(const Stack & rhs) :
                theSize(0), topNode(NULL) { operator=(rhs); }            
            ~Stack()                  { clear();}
            void push(const T& );
            void pop();            
            T& top()    const;
            int size()   const  { return theSize; }
            bool empty() const  { return theSize == 0; }
            void clear();
            Stack<T>& operator=(const Stack& );            
            
	};


template <typename T>
void Stack<T>::push(const T& elt ){
    Node *newNode = new Node(elt);
    if ( empty() ){
        topNode = newNode;
    }else{
        newNode -> next = topNode;
        topNode = newNode;
    }
    ++theSize;
}

template <typename T>
void Stack<T>::pop( ){
	if (empty()){
        return;
    }
    Node *temp = topNode;
	topNode = topNode -> next;
	delete temp;
	--theSize;
}
template <typename T>
T& Stack<T>::top()    const  {
    if(empty()){
        throw runtime_error("Trying to top at an empty stack");
    }
    return topNode -> data; 
}
template <typename T>
void Stack<T>::clear(){
	for(Node* cursor = topNode; cursor != NULL; cursor = topNode){       
        topNode = cursor -> next;
        delete cursor;
    }
    theSize = 0;
}

 template <typename T>
    Stack<T>& Stack<T>::operator=(const Stack& rhs){
        if(this == &rhs){
            return *this;
        }
        clear();
        
        T tempHolding [rhs.size()];
        int index = 0;
        for(Node *cursor = rhs.topNode; cursor != NULL; cursor = cursor -> next){
            tempHolding[index++] = cursor -> data;
        }
        
        for(int i = index - 1; i >= 0; i--){
            push(tempHolding[i]);
        }
        return *this;
    }
} // end namespace 
#endif