// © Copyright 1997. Joseph Bergin. All rights reserved.

#ifndef __LinkStack__
#define __LinkStack__

template <class T> class LinkStackIterator;
template <class T> class LinkStack;

template <class T>
class LinkNode
{	private:
		LinkNode(T val, LinkNode<T>* next = NULL)
		:	_value(val),
			_next(next)
		{
		}
		
		LinkNode<T>* copyAll()
		{	if(_next == NULL)
				return new LinkNode<T>(_value);
			else
				return new LinkNode<T>(_value, _next->copyAll());
		}
		
		T _value;
		LinkNode<T>* _next;
	friend class LinkStack<T>;
	friend class LinkStackIterator<T>;
};

template <class T>
class LinkStack
{	public:
		
		typedef LinkStackIterator<T> iterator;
		
		LinkStack()
		:	_first(NULL)
		{
		}
		
		~LinkStack(){ free();}
		
		LinkStack(const LinkStack<T>& S)
		{	copy(S);
		}
		
		LinkStack<T>& operator= (const LinkStack<T>& S)
		{	if(this != &S)
			{	free();
				copy(S);
			}
			return *this;
		}
		void push(const T& v){ _first = new LinkNode<T>(v, _first);}
		
		T pop()
		{ 	T temp = _first->_value;
			LinkNode<T>* oldnode = _first;
			_first = oldnode->_next;
			delete oldnode;
			return temp;
		}
		
		 T& top()const{ return _first->_value; }

		bool empty()const{ return _first == NULL; }
		
		bool full()const{ return false; }
		
		iterator begin()const
		{	return LinkStackIterator<T>(_first);
		}
		
		iterator end()const
		{	return LinkStackIterator<T>(NULL);
		}
		
	private:
		LinkNode<T>* _first;
		void copy(const LinkStack& S)
		{	if(S._first == NULL)
				_first = NULL;
			else
				_first = S._first->copyAll();
		}
		
		void free()
		{	while(_first != NULL)
			{	LinkNode<T>* temp = _first;
				_first = temp->_next;
				delete temp;
			}
		}
	friend class LinkStackIterator<T>;
};

template <class T>
class LinkStackIterator
{	public:

		typedef T value_type;

		LinkStackIterator(LinkNode<T>* where)
		:	_where(where)
		{
		}
		
		T& operator*()
		{	return _where->_value;
		}
		
		bool operator<(const LinkStackIterator<T>& i)
		{ 	if(_where != NULL && i._where == NULL)return true;
			if(_where == NULL || _where == i._where) return false;
			LinkNode<T>* temp = _where->_next;
			while(temp != NULL)
			{	if( temp == i._where) return true;
				temp = temp->_next; 
			}
			return false;
		}
		
		LinkStackIterator<T> operator+(int i)
		{	LinkNode<T>* temp = _where;
			for(int x = 0; x < i; x++)
				temp = temp->_next;
			return LinkStackIterator<T>(temp); 
		}
		
		T& operator++(){ _where = _where->_next; return _where->_value; }
		T& operator++(int) 
		{	LinkNode<T>* temp = _where; 
			_where = _where->_next;
			return temp->_value; 
		}
		
	private:
		LinkNode<T>* _where;
};

#endif