#ifndef _INCLUDED_L3_QUEUE_H
#define _INCLUDED_L3_QUEUE_H

// *Queue, Deque* Copyright (C) Krzysztof Bosak, 1999-01-18...2000-11-25
// All rights reserved.
// kbosak@box43.pl
// http://www.kbosak.prv.pl

// growing_arrayqueue is self growing, no auto-shrinking due to code efficiency
// fixed_arrayqueue has fixed size

#include "l3_array.h"

template<class type>
class growing_arrayqueue
{	// Corresponds to std::queue.
	// Is EXCEPTION NEUTRAL.
	autoarray<type> _data;
	int _indexins;
	int _indexrem;
	int _size;
public:
	inline growing_arrayqueue() // EXCEPTION NEUTRAL
		: _data(1),
		_indexins(0),
		_indexrem(0),
		_size(0)
	{
	}
	inline explicit growing_arrayqueue(int requested_size) // EXCEPTION NEUTRAL
		: _data(requested_size),
		_indexins(0),
		_indexrem(0),
		_size(0)
	{
	}
	inline void swap(growing_arrayqueue<type>& other) // NOTHROW
	{
		_data.swap(other._data);
		int temp;

		temp=_indexins;
		_indexins=other._indexins;
		other._indexins=temp;

		temp=_indexrem;
		_indexrem=other._indexrem;
		other._indexrem=temp;

		temp=_size;
		_size=other._size;
		other._size=temp;
	}
	inline growing_arrayqueue<type>& operator=(const growing_arrayqueue<type>& other) // EXCEPTION NEUTRAL
	{	// A must to ensure strong exception safety.
		assert(this!=&other);// This line can be safely removed.
		growing_arrayqueue<type> temp(other);
		swap(temp);
		return *this;
	}
	inline int size() const // NOTHROW
	{
		return _size;
	}
	inline bool empty() const // NOTHROW
	{
		return _size==0;
	}
	inline int capacity() const // NOTHROW
	{
		return _data.size();
	}
	inline type& front() // NOTHROW
	{
		assert(_size>0);
		return _data[_indexrem];
	}
	inline const type& front() const // NOTHROW
	{
		assert(_size>0);
		return _data[_indexrem];
	}
	inline type& back() // NOTHROW
	{
		assert(_size>0);
		return _data[_indexins-1];
	}
	inline const type& back() const // NOTHROW
	{
		assert(_size>0);
		return _data[_indexins-1];
	}
	inline void push(const type& val) // EXCEPTION NEUTRAL
	{
		if(_size+1>=_data.size())
			_grow();
		if(_indexins>=_data.size())
		{
			_data[0]=val;
			_indexins=0;
		}
		else
		{
			_data[_indexins]=val;
		}
		_indexins++;
		_size++;
	}
	inline void pop() // NOTHROW
	{
		assert(_size>0);
		_size--;
		_indexrem++;
		if(_indexrem>=_data.size())
			_indexrem=0;
	}
	inline void clear() // not STL // NOTHROW
	{
		_indexins=0;
		_indexrem=0;
		_size=0;
	}
	inline void free() // not STL // NOTHROW
	{
		_data.free();
		_indexins=0;
		_indexrem=0;
		_size=0;
	}
private:
	inline void _grow() // EXCEPTION NEUTRAL
	{
		//cout<<"GROW at:"<<_indexins<<" TO "<<_maxqueue<<endl;
		const int requested_size=_data.size()<<1;
		autoarray<type> tmparr(requested_size);
		if(_indexrem<_indexins)
		{
			for(int i=0; i<_size; i++)
				tmparr[i]=_data[_indexrem+i];
		}
		else
		{
			int j=_indexrem;
			int i=0;
			for(; j<_data.size(); j++, i++)
				tmparr[i]=_data[j];
			j=0;
			for(; i<_size; i++, j++)
				tmparr[i]=_data[j];
		}
		_data.swap(tmparr);
		_indexrem=0;
		_indexins=_size;
		assert(_size<=_data.size());
	}
};

template<class type>
class fixed_arrayqueue
{	// Warning: std::queue is self-growing, this one is not.
	// Is EXCEPTION NEUTRAL.
protected:
	autoarray<type> _data; // must have n+1 elements, (if not, _head==_tail when size()==0 OR size()==maxsize)
	int _head;
	int _tail;

public:
	inline fixed_arrayqueue() // EXCEPTION NEUTRAL
		: _data(1),
		_head(0),
		_tail(0)
	{
	}
	virtual ~fixed_arrayqueue()
	{
	}
	inline explicit fixed_arrayqueue(int requested_size) // EXCEPTION NEUTRAL
		: _data(requested_size+1),
		_head(0),
		_tail(0)
	{
		assert(requested_size>=0);
	}
	inline void swap(fixed_arrayqueue<type>& other) // NOTHROW
	{
		_data.swap(other._data);
		int temp;

		temp=_head;
		_head=other._head;
		other._head=temp;

		temp=_tail;
		_tail=other._tail;
		other._tail=temp;
	}
	inline fixed_arrayqueue<type>& operator=(const fixed_arrayqueue<type>& other) // EXCEPTION NEUTRAL
	{	// A must to ensure strong exception safety.
		assert(this!=&other);// This line can be safely removed.
		fixed_arrayqueue<type> temp(other);
		swap(temp);
		return *this;
	}
	inline int size() const // NOTHROW
	{
		if(_tail>=_head)
			return _tail-_head;
		else
			return _data.size()-_head+_tail;
	}
	inline bool empty() const // NOTHROW
	{
		return _head==_tail;
	}
	inline int capacity() const // NOTHROW
	{
		return _data.size()-1; // one element always is unused
	}
	inline type& front() // NOTHROW
	{
		assert(size()>0);
		return _data[_head];
	}
	inline const type& front() const // NOTHROW
	{
		assert(size()>0);
		return _data[_head];
	}
	inline type& back() // NOTHROW
	{
		assert(size()>0);
		if(_tail>0)
			return _data[_tail-1];
		return _data[_data.size()-1];
	}
	inline const type& back() const // NOTHROW
	{
		assert(size()>0);
		if(_tail>0)
			return _data[_tail-1];
		return _data[_data.size()-1];
	}
	inline void push(const type& element) // EXCEPTION NEUTRAL
	{//push_back
		assert(size()<_data.size()-1);
		_data[_tail]=element;
		_tail++;
		if(_tail>=_data.size())
			_tail=0;
	}
	inline void pop() // NOTHROW
	{// pop_front
		assert(size()>0);
		_head++;
		if(_head>=_data.size())
			_head=0;
	}
	inline void clear() // not STL // NOTHROW
	{
		_head=0;
		_tail=0;
	}
	inline void free() // not STL // NOTHROW
	{
		_data.free();
		_head=0;
		_tail=0;
	}

	inline int head_iterator() const
	{
		assert(_data.size()>1);
		return _head;
	}
	inline void advance_iterator(int & iterator) const
	{
		iterator++;
		if(iterator>=_data.size())
		{
			iterator=0;
		}
	}
	inline const type& value_iterator(int iterator) const
	{
		assert(_data.size()>1);
		return _data[iterator];
	}
};

template<class type>
class fixed_arraydeque: public fixed_arrayqueue<type>
{	// Warning: std::deque is self-growing, this one is not.
	// Is EXCEPTION NEUTRAL.
public:
	inline fixed_arraydeque() // EXCEPTION NEUTRAL
		: fixed_arrayqueue<type>()
	{
	}
	inline explicit fixed_arraydeque(int requested_size) // EXCEPTION NEUTRAL
		: fixed_arrayqueue<type>(requested_size)
	{
	}
	inline void push_front(const type& element) // EXCEPTION NEUTRAL
	{
		assert(size()<_data.size()-1);
		if(_head>0)
		{
			_data[_head-1]=element;
			_head--;
		}
		else
		{
			const int temp=_data.size()-1;
			_data[temp]=element;
			_head=temp;
		}
	}
	inline void push_back(const type& element) // EXCEPTION NEUTRAL
	{
		fixed_arrayqueue<type>::push(element);
	}
	inline void pop_front() // NOTHROW
	{
		assert(size()>0);
		fixed_arrayqueue<type>::pop();
	}
	inline void pop_back() // NOTHROW
	{
		assert(size()>0);
		_tail--;
		if(_tail<0)
		{
			_tail=_data.size()-1;
		}
	}
private:
	inline void push(const type& element);
	inline type pop();
};

#endif //_INCLUDED_L3_QUEUE_H