// © Copyright1995, Joseph Bergin.  All rights reserved. 

#ifndef __stacks__
#define __stacks__

#include "Array.h"
#include "Error.h"
#include "Boolean.h"

// Stacks are dynamically sized. They grow when necessary to
// accomodate new push operations.  Popping from an empty stack
// or calling top when the stack is empty will cause your program
// to halt with the stack underflow message.  

template<class E>
class Stack
{	public:
		Stack(int size = ArrayDefaultLength)
		:	_elements(size),
			_top(-1),
			_currentLength(size)
		{
		}
	
		// Default copy constructor and assignment operator
		// are ok here.
	
		Boolean empty() const
		{	return Boolean(_top < 0);
		}
	
		void push(const E& e)
		{	if(_top == _currentLength - 1)
			{ 	_elements.extendBy(ArrayDefaultLength);
				_currentLength += ArrayDefaultLength;
			}
			_elements[++_top] = e;
		}
	
		E pop()
		{	if(empty()) userERROR("Stack underflow.");
			return _elements[_top--];
		}
	
		E top() const
		{	if(empty()) userERROR("Stack underflow.");
			return _elements[_top];
		}
	
		Array<E> asArray() const 
		{	Array<E> result(_top + 1);
			for(int i = 0; i <= _top; i++)
				result[i] = _elements[i];
			return result;
		}
	
	private:
		Array<E> _elements;
		int _top;
		int _currentLength;
	friend ostream & operator<<(ostream& os, const Stack<E> &S);
};

template <class E>
ostream & operator<<(ostream& os, const Stack<E> &S)
{	for(int i = 0; i <= S._top; i++)
		os << S._elements[i] << ' ';
	return os;
}

#endif