/*  stack_312_LL.h
  CS 312 Fall 2018
  
  a very simple linked list Stack ADT
  
*/

#ifndef STACK_312_H
#define STACK_312_H

#include <cstdlib>  // Provides size_t
#include <cassert>

using namespace std;

template<class ItemType>
class Stack_312 {
 public:
        
   // typedef int value_type;
    typedef int size_type;
    
    Stack_312();
    
    //Copy constructor
    Stack_312(const Stack_312 & src);
    
/****************************  
makeEmpty
  
Function: Removes all the items from the stack. 
Preconditions: Stack has been initialized 
Postconditions: All the items have been removed
*****************************/        
    void makeEmpty();
    
/****************************  
isEmpty
  
Function: Checks to see if there are any items on the stack. 
Preconditions: Stack has been initialized
Postconditions: Returns true if there are no items on the stack, else false.
*****************************/        
    bool isEmpty() const;
    
/****************************  
isFull
  
Function: Determines if you have any more room to add items to the stack
Preconditions: Stack has been initialized
Postconditions: Returns true if there is no more room to add items, else false
*****************************/        
    bool isFull() const;

/****************************  
push
  
Function: Adds newItem to the top of the stack. 
Preconditions: Stack has been initialized and is not full.
Postconditions: newItem is at the top of the stack.
*****************************/    
 	void push(const ItemType &);
 	
/****************************  
pop
  
Function: Removes topItem from stack and returns it.
Preconditions: Stack has been initialized and is not empty.
Postconditions: Top element has been removed from stack and item is a copy of the removed element. 
*****************************/  	
ItemType pop();
    
    
 private:
    struct Node {
       ItemType value;
       Node *next;
    };  
    
    Node *head;

}; 

/*******************************
/ Function implementations
********************************/

template<class ItemType>
Stack_312<ItemType>::Stack_312 ()
{
   head = NULL;  
}

template<class ItemType>
Stack_312<ItemType>::Stack_312(const Stack_312 & src)
{
         if (src.head == NULL)
         {
            head = NULL;
         }
         else
         {
            Node *temp;
            Node *prev = NULL;

            for (Node *p = src.head; p != NULL; p=p->next)
            {
               temp = new Node;
               temp->value = p->value;
               temp->next = NULL;
         
               if (prev == NULL)
                  prev = temp;
               else
               {
                  prev->next = temp;
                  prev = temp;
               }
 
               if (p == src.head)
                  head = temp;
            }
         }
}


template<class ItemType>
void Stack_312 <ItemType>::makeEmpty()
{

         Node *p = head;

         while (head != NULL)
         {
            head = head->next;
            delete p;
            p = head;
         }
   
}

template<class ItemType>
bool Stack_312 <ItemType>::isEmpty() const
{  
   return head == NULL;   
}

template<class ItemType>
bool Stack_312 <ItemType>::isFull() const
{
   return false; //temporary (could use the try/catch memory allocation)    
}


template<class ItemType>
void Stack_312 <ItemType>::push(const ItemType& newItem)
{
   assert(!isFull());

   Node *p = new Node;
   p->value = newItem;
   p->next = head;
   head = p;

}


template<class ItemType>
ItemType Stack_312 <ItemType>::pop()
{
   assert(!isEmpty());

   ItemType temp = head->value;

   Node *p = head;
   head = head->next;
   delete p;

   return temp;
   
}

#endif