#ifndef __list_h__
#define __list_h__

extern int traceList;

template <class Type>
struct Node
{
	Type *prev;
	Type *next;
	inline void insert(Type *first,Type *second)
	{
		prev=first;
		next=second;
		first->next=(Type*) this;
		second->prev=(Type*) this;
	};
	inline void remove()
	{
		prev->next=next;
		next->prev=prev;
		next=this;
		prev=this;
	};
};

template <class Type>
struct List
{
	Node<Type> head[1];
	Node<Type> tail[1];

	inline void init()
	{
		head->prev=0;
		head->next=(Type*) tail;
		tail->prev=(Type*) head;
		tail->next=0;
	};

	inline void add(Type *n)
	{
		n->insert((Type*)head,head->next);
	}
	inline void queue(Type *n)
	{
		n->insert(tail->prev,(Type*)tail);
	};

	inline void add(List<Type> *l)
	{
		register Type *first;
		register Type *last;

		first=l->head->next;
		if(first->next)
		{
			last=l->tail->prev;
			// on vide l
			l->head->next=l->tail;
			l->tail->prev=l->head;
			// on insere les anciens noeuds de l au debut de this
			first->prev=head;
			last->next=head->next;
			head->next->prev=last;
			head->next=first;
		}
	}
	inline void queue(List<Type> *l)
	{
		register Type *first;
		register Type *last;

		first=(Type *)l->head->next;
		if(first->next)
		{
			last=(Type *)l->tail->prev;
			// on vide l
			l->head->next=l->tail;
			l->tail->prev=l->head;
			// on insere les anciens noeuds de l a la fin de this
			first->prev=tail->prev;
			last->next=tail;
			tail->prev->next=first;
			tail->prev=last;
		}
	};

	inline Type *get()
	{
		register Type *first;

		first=(Type *)head->next;
		if(!first->next)
			first=0;
		else
		{
			first->remove();
		}
		return first;
	};

	inline int count()
	{
		register int key;
		register Type *first, *next;
		register int count=0;

		first=head->next;
		while(next=first->next)
		{
			count++;
			first=next;
		}
		return count;
	};

	/*
		parcourt la liste a partir du noeud first inclu,
		pour chaque noeud, applique la fonction fnc.
		note : le noeud courant peut etre enleve de la liste et detruit car
		une copie de la reference sur le prochain noeud a ete faite
	*/

	typedef bool (*eachFunc)(Type *n,void *param);
	bool each(eachFunc func,void *param)
	{
		Type *cur, *next;

		cur=head->next;
		while(1)
		{
			next=cur->next;
			if(!next)
				return false;
			if((*func)((Type *)cur,param))
				return true;
			cur=next;
		}
	}

};

template <class Type>
struct ListIterator
{
	Type *cur,*next;

	inline ListIterator(List<Type> *list)
	{
		begin(list);
	}

	inline void begin(List<Type> *list)
	{
		cur=list->head->next;
	}
	inline bool end()
	{
		return (next=cur->next)==0;
	}
	inline operator bool ()
	{
		return !end();
	}
	inline ListIterator &operator++() // pre incrementation
	{
		cur=next;
		return *this;
	}
	inline ListIterator &operator++(int ) // post incrementation
	{
		cur=next;
		return *this;
	}
};

#endif /* __list_h__ */