#ifndef _INCLUDED_L3_QLIST_H
#define _INCLUDED_L3_QLIST_H

// *Quick List Library* Copyright (C) Krzysztof Bosak, 1998-03-20...2000-04-29.
// All rights reserved.
// kbosak@box43.pl
// http://www.kbosak.prv.pl

#include <string.h>

#include "l3_array.h"
#include "l3_stack.h"

class indexstack
{
		int _size;
		basearray<int> _freedata;
public:
		inline explicit indexstack(int initial_size) // EXCEPTION NEUTRAL
				: _size(0),
				_freedata(initial_size)
		{
		}
		inline void swap(indexstack& other) // NOTHROW
		{
				const int temp=_size;
				_size=other._size;
				other._size=temp;
				_freedata.swap(other._freedata);
		}
		inline indexstack& operator=(const indexstack& other) // EXCEPTION NEUTRAL
		{
				assert(this!=&other);// This line can be safely removed.
				indexstack temp(other);
				swap(temp);
				return *this;
		}
		inline void grow(int requested_size) // EXCEPTION NEUTRAL
		{
				assert(requested_size>=0);
				_freedata.resize(requested_size);
		}
		inline void push(int value) // NOTHROW
		{
				assert(value>=0);
				_freedata[_size]=value;
				_size++;
		}
		inline int top() const // NOTHROW
		{
				assert(_freedata[_size-1]>=0);
				return _freedata[_size-1];
		}
		inline void pop() // NOTHROW
		{
				assert(_size>0);
				_size--;
		}
		inline void clear() // NOTHROW
		{
				_size=0;
		}
		inline int size() const // NOTHROW
		{
				assert(_size>=0);
				return _size;
		}
		inline bool empty() const // NOTHROW
		{
				return _size==0;
		}
		inline void show() const // NOTHROW
		{
				for(int i=_size-1; i>=0; i--)
						cout<<_freedata[i]<<',';
		}
};

template<class type>
class qlist
{	   // Corresponds to std::list<>.
		int _size;
		int _front;
		int _back;
		int _capacity;
		basearray<int> _prevtab;
		basearray<int> _nexttab;
		indexstack _freestack;
		autoarray<type> _data;
public:
		inline void clear() // NOTHROW (yes and yes!)
		{
				_freestack.clear();
				for(int i=_capacity-1; i>=0; i--)
						_freestack.push(i);
				_size=0;
				_front=-1;
				_back=-1;
				_prevtab[0]=-1;
				_nexttab[0]=-1;
		}
		inline explicit qlist(int initial_size=1) // EXCEPTION NEUTRAL
				: _capacity(initial_size),
				_prevtab(initial_size),
				_nexttab(initial_size),
				_freestack(initial_size),
				_data(initial_size)
		{
				assert(initial_size>=1);
				clear();
		}
private:
		inline void _grow() // EXCEPTION NEUTRAL
		{
				const int new_capacity=_capacity<<1;
				//cout<<"GROW at:"<<_size<<"   "<<_capacity<<" TO "<<new_capacity<<endl;

				autoarray<type> typetab(new_capacity);
				_prevtab.resize(new_capacity);
				_nexttab.resize(new_capacity);
				_freestack.grow(new_capacity);

				int i;
				for(i=0; i<_capacity; i++)
						typetab[i]=_data[i];
				_data.swap(typetab);

				for(i=new_capacity-1; i>=_capacity; i--)
						_freestack.push(i);

				_capacity=new_capacity;
		}
public:
		inline void push_front(const type& d) // EXCEPTION NEUTRAL
		{
				if(_freestack.empty())
						_grow();
				const int pos=_freestack.top();
				_data[pos]=d;
				_freestack.pop();
				_nexttab[pos]=-1;
				_prevtab[pos]=_front;
				if(_front!=-1)
						_nexttab[_front]=pos;
				else
						_back=pos;
				_front=pos;
				_size++;
		}
		inline void pop_front() // NOTHROW
		{
				assert(_size>0);
				_freestack.push(_front);
				_size--;
				if(_size>0)
				{
						_front=_prevtab[_front];
						_nexttab[_front]=-1;
				}
				else
				{
						_front=-1;
						_back=-1;
				}
		}
		inline void push_back(const type& d) // EXCEPTION NEUTRAL
		{
				if(_freestack.empty())
						_grow();
				const int pos=_freestack.top();
				_data[pos]=d;
				_freestack.pop();
				_nexttab[pos]=_back;
				_prevtab[pos]=-1;
				if(_back!=-1)
						_prevtab[_back]=pos;
				else
						_front=pos;
				_back=pos;
				_size++;
		}
		inline void pop_back() // NOTHROW
		{
				assert(_size>0);
				_freestack.push(_back);
				_size--;
				if(_size>0)
				{
						_back=_nexttab[_back];
						_prevtab[_back]=-1;
				}
				else
				{
						_front=-1;
						_back=-1;
				}
		}
		inline type& front() // EXCEPTION NEUTRAL
		{
				return _data[_front];
		}
		inline const type& front() const // EXCEPTION NEUTRAL
		{
				return _data[_front];
		}
		inline type& back() // EXCEPTION NEUTRAL
		{
				return _data[_back];
		}
		inline const type& back() const // EXCEPTION NEUTRAL
		{
				return _data[_back];
		}
		inline int max_size() const // NOTHROW
		{	   // 2 times smaller than for std::allocator due to int
				return INT_MAX/sizeof(type);
		}
		inline int size() const // NOTHROW
		{
				return _size;
		}
		inline bool empty() const // NOTHROW
		{
				return _size==0;
		}
		inline int capacity() const // NOTHROW
		{
				return _capacity;
		}
		inline void swap(qlist<type>& other) // NOTHROW
		{
				int temp;

				temp=_size;
				_size=other._size;
				other._size=temp;

				temp=_front;
				_front=other._front;
				other._front=temp;

				temp=_back;
				_back=other._back;
				other._back=temp;

				temp=_capacity;
				_capacity=other._capacity;
				other._capacity=temp;

				_prevtab.swap(other._prevtab);
				_nexttab.swap(other._nexttab);
				_freestack.swap(other._freestack);
				_data.swap(other._data);
		}
		inline qlist<type>& operator=(const qlist<type>& other) // EXCEPTION NEUTRAL
		{
				assert(this!=&other);// This line can be safely removed.
				qlist<type> temp(other);
				swap(temp);
				return *this;
		}

		// The rest is still garbage:
		inline void insafter(int, const type& );
		inline void insbefore(int, const type& );
		inline void inssorted(int (*)(const type& , const type& ), const type& );
//	  inline void show(bool) const;
		inline int fndfirst(const type) const;
		inline int fndlast(const type) const;
		inline int fndnext(int, const type) const;
		inline int fndprev(int, const type) const;
		inline int first() const
		{
				return _front;
		}
		inline int last() const
		{
				return _back;
		}
		inline int prev(int p) const
		{
				return _prevtab[p];
		}
		inline int next(int p) const
		{
				return _nexttab[p];
		}
		inline const type& element(int p) const
		{
				return _data[p];
		}
		inline type& reference(int p)
		{
				return _data[p];
		}
};

template<class type>
void qlist<type>::insafter(int p, const type& d)
{
		assert(_size>0);
		if(p!=_back)
		{
				if(_freestack.empty())
						_grow();
				const int t=_prevtab[p];
				const int pos=_freestack.top();
				_freestack.pop();
				_data[pos]=d;
				_nexttab[pos]=p;
				_prevtab[pos]=t;
				_nexttab[t]=pos;
				_prevtab[p]=pos;
				_size++;
		}
		else
		{
				push_back(d);
		}
}

template<class type>
void qlist<type>::insbefore(int p, const type& d)
{
		assert(_size>0);
		if(_freestack.empty())
				_grow();
		if(p!=_front)
		{
				const int t=_nexttab[p];
				const int pos=_freestack.top();
				_freestack.pop();
				_data[pos]=d;
				_nexttab[pos]=t;
				_prevtab[pos]=p;
				_nexttab[p]=pos;
				_prevtab[t]=pos;
				_size++;
		}
		else
		{
				push_front(d);
		}
}

template<class type>
int qlist<type>::fndfirst(const type d) const
{
		assert(_size>0);
		int t=_front;
		do
		{
				if(d==_data[t])
						return t;
				if(_prevtab[t]!=-1)
						t=_prevtab[t];
				else
						return -1;
		}while(true);
}

template<class type>
void qlist<type>::inssorted(int (*fun)(const type& , const type& ), const type& val)
{
		if(_size==0)
				push_front(val);
		else
		{
				int t=_front, t2;
				int t3=0;
				while((t3=fun(val, _data[t]))!=0)
				{
						if((t2=_prevtab[t])!=-1)
						{
								t=t2;
						}
						else
						{
								push_back(val);
								return;
						}
				}
				if(t3!=0)
						insafter(t, val);
				else
						insbefore(t, val);
		}
}

/*
template<class type>
void qlist<type>::show(bool showfree) const
{
#ifndef NDEBUG
		cout<<"\n*_front* (first element (last put using stack notation))";
		int t=_front;
		if(_size>0)
		{
				do
				{
						cout<<"\n#"<<t<<"="<<_data[t]<<"\t\tnext:"<<_nexttab[t]<<"\t\tprev:"<<_prevtab[t];
						t=_prevtab[t];
				}while(t!=-1);
		}
#else
		cout<<"NDEBUG: no list content output...\n";
#endif
		cout<<"\n*_back*";

		if(showfree==true)
		{
				cout<<", _freestack: ";
				_freestack.show();
		}

		cout<<endl;
		cout<<"First	  _front="<<_front<<endl;
		cout<<"Last		_back="<<_back<<endl;
		cout<<"Length	_size="<<_size<<endl;
		cout<<"MaxLength   _capacity="<<_capacity<<endl;
		cout.flush();
}
*/

template<class type>
int qlist<type>::fndlast(const type d) const
{
		assert(_size>0);
		int t=_back;
		do
		{
				if(d==_data[t])
						return t;
				if(_nexttab[t]!=-1)
						t=_nexttab[t];
				else
						return -1;
		}while(true);
}

template<class type>
int qlist<type>::fndnext(int ind, const type d) const
{
		assert(_size>0);
		int t=ind;
		do
		{
				if(d==_data[t])
						return t;
				if(_nexttab[t]!=-1)
						t=_nexttab[t];
				else
						return -1;
		}while(true);
}

template<class type>
int qlist<type>::fndprev(int ind, const type d) const
{
		assert(_size>0);
		int t=ind;
		do
		{
				if(d==_data[t])
						return t;
				if(_prevtab[t]!=-1)
						t=_prevtab[t];
				else
						return -1;
		}while(true);
}

#endif //_INCLUDED_L3_QLIST_H