// © Copyright 1995, Joseph Bergin. All rights reserved.

#ifndef __QUEUE__
#define __QUEUE__

#include "LinkList.h"
#include "boolean.h"
#include <assert.h>

// Implements a double ended queue of E. Items may be inserted or removed
// from either end.  When used in only one direction it will implement FIFO 
// storage.  When used at only one end, it will implement LIFO storage.  
// Supply a dummy value when you create a Queue.  This value is returned whenever 
// n functional operation is illegal: e.g. dequeue from an empty queue.  To achieve
// termination upon illegal calls, define the symbol __QueueErrors__ before including
// this file

template <class E>
class Queue
{	public:
		Queue(const E& dummy):_elements(dummy){}
		
		void enqueue(const E& e) // Insert at rear
		{	_elements.insertFirst(e,rightLeft);
		}

		E dequeue()	// Remove from front.
		{
			#ifdef 	__QueueErrors__
				assert(!empty());
			#endif
			return _elements.removeFirst(leftRight);
		}

		void enqueueFront(const E& e)
		{	_elements.insertFirst(e,leftRight);
		}

		E dequeueRear()
		{
			#ifdef 	__QueueErrors__
				assert(!empty());
			#endif
			return _elements.removeFirst(rightLeft);
		}

		Boolean empty()
		{	return _elements.empty();
		}
		
		E atFront()
		{
			#ifdef 	__QueueErrors__
				assert(!empty());
			#endif
			return _elements.first(leftRight);
		}
		
		E atRear()
		{
			#ifdef 	__QueueErrors__
				assert(!empty());
			#endif
			return _elements.first(rightLeft);
		}
		
		void clear() 
		{	_elements.clear();
		}
		
		unsigned int length()
		{	return _elements.length();
		}
		
	private:
		LinkList<E> _elements;

	friend
	ostream & operator<<(ostream& os, const Queue<E>& Q);
};

template <class E>
ostream & operator<<(ostream& os, const Queue<E>& Q)
{	os << Q._elements;
	return os;
}
#endif