// List class interface with Stack derived class
//
//     copy construction of List objects is DISALLOWED
//
// ******************PUBLIC OPERATIONS*********************
// int IsEmpty( )         --> Return 1 if empty; else return 0
// int IsFull( )          --> Return 1 if full; else return 0
// void MakeEmpty( )      --> Remove all items
//
// ******************PROTECTED OPERATIONS******************
// void Insert( Etype X ) --> Insert X after current position
// int Remove( )          --> Remove X
// void Zeroth( )         --> Set current position to prior to first
// Etype GetCurrent( )    --> Return item in current position
// void First( )          --> Set current position to first node
// ********************************************************

//#ifndef __List__
//#define __List__
#include <stdlib.h>

template <typename Etype>
class List 
{
  private:
    struct ListNode
    {
        Etype Element;
        ListNode *Next;
    };

	ListNode 	*Header;    	// Pointer to a header node
	ListNode 	*Current;		// Pointer to current node
	ListNode 	*Rear;			// Pointer to last node
	int			Size;			// Number of nodes in list
    int			Position;		// Node number of current

    List (const List &);        // Disable copy constructor
  public:
	List(void);
	~List(void);                        // Destroy whole list and header
	int IsEmpty (void) const;           // Check for empty
	int IsFull (void)  const;           // Assume never full
    void MakeEmpty (void);				// Erase all list elements

  protected:
	void Insert( const Etype & X );		// Add an element
	int Remove (void);					// Erase an element
	const Etype & GetCurrent (void) const;	// Return element at Current
	void Zeroth(void);					// Set Current to header
	void First(void);					// Set Current to first element

};

template <typename Etype>       // Constructor - set up header node
List<Etype>::List(void)
{
	Rear = Current = Header = new ListNode;
	Header->Next = NULL;
	Size = 0;
	Position = 0;
}

template <typename Etype>       // Empty the list; leave the header node
void List<Etype>::MakeEmpty(void)
{
    ListNode *Ptr;
    ListNode *NextNode;

    for( Ptr = Header->Next; Ptr != NULL; Ptr = NextNode )
    {
        NextNode = Ptr->Next;
		delete Ptr;              // Delete each node
    }
	Header->Next = NULL;         // Reset pointers
	Size = 0;
	Position = 0;
	Rear = Current = Header;
}

template <typename Etype>
List<Etype>::~List (void)		// Erase entire storage area
{
	MakeEmpty( );
	delete Header;
}

template <typename Etype>
int List<Etype>::IsEmpty (void) const	// Check for empty list
{ 
	return Header->Next == NULL; 
}

template <typename Etype>
int List<Etype>::IsFull (void) const	// Assume impossible
{
	return 0;
}

template <typename Etype>              // Add a node to the list
void List<Etype>::Insert( const Etype & X )
{
	ListNode 	*NewNode;

	NewNode = new ListNode;
	if (NewNode == NULL)			// Check for no more memory
	{   cout << "Memory is exhausted.\n";
	    exit(1);
        }
	NewNode->Element = X;
	NewNode->Next =  Current->Next;       // Attach after Current
	Current->Next = NewNode;
	if (Rear == Current) Rear = NewNode;
	Size++;
}

template <typename Etype>			// Remove node at Current
int List<Etype>::Remove( )
{
     ListNode	*p = Header;
     ListNode 	*DeletedNode = Current;

    if( Current == Header )		// Can't remove header
        return 0;

    while (p->Next != Current)	// Locate previous node
    	p = p->Next;
    if (Current == Rear) Rear = p;
    p->Next = p->Next->Next;
    delete DeletedNode;
    Size--;
    Position = 0;				// Reset Position and Current
    Current = Header;

    return 1;
}

template <typename Etype>			// Get value in current node
const Etype & List<Etype>::GetCurrent ( ) const
{
    if( Current == Header)
    {	cout << "Illegal access\n";    // Can't access header
	exit(1);
    }
    return Current->Element;
}

template <typename Etype>			// Set Current to first node
void List<Etype>::First( )
{
	if ( Header->Next == NULL)
	{	cout << "Illegal access - empty\n";	// Report empty access
		exit(1);
	}
	Current = Header->Next;
	Position = 1;
}

template <typename Etype>			// Set Current to Header
void List<Etype>::Zeroth( )
{
	Current = Header;
	Position = 0;
}

//#endif


// Stack class - derived from the List class

// ************** PUBLIC OPERATIONS *******************
// void Push (Etype &)	    --> Add an element to the stack
// Etype & Pop ( )			--> Remove an element from the stack
// Etype & Peek( )  		--> Return the element on top of stack
//*****************************************************

//#ifndef __ListStack__
//#define __ListStack__

template <typename Etype>
class Stack : public List<Etype>
{
    private:
	Stack(const Stack &);             // Disable copy constructor

    public:
	Stack(void);					// Stack constructor
	void Push (const Etype &);		// Add element to Stack
	Etype Pop (void);				// Remove top of Stack
	Etype Peek(void);			// Examine top of Stack
};


template <typename Etype>
Stack<Etype>::Stack (void)				// Construct empty stack
{
	List<Etype>();
}

template <typename Etype>
void Stack<Etype>::Push (const Etype & element)	// Add element 
{
	Zeroth();
	Insert(element);
}

template <typename Etype>
Etype Stack<Etype>::Pop (void)		// Remove stack element
{
	Etype	temp;

	First();
	temp = GetCurrent();
	Remove();
	return temp;
}

template <typename Etype>
Etype Stack<Etype>::Peek (void)	// Look at the top
{
	First();
	return GetCurrent();
}

//#endif