/*
 *	CENA C++ Utilities
 *
 *	by Stephane Chatty
 *
 *	Copyright 1992-1995
 *	Centre d'Etudes de la Navigation Aerienne (CENA)
 *
 *	plain and generic double-linked lists (original ideas by Yves Berteaud)
 *
 *	$Id$
 *	$CurLog$
 */

#ifndef DList_H_
#define DList_H_

#include "cplus_bugs.h"
#include <sys/types.h>

class IvlAllocator;

typedef void IvlDListItem;

#ifdef CPLUS_BUG20
class IvlDListLink;
#endif

class IvlDList {
friend	class	IvlDListIter;

#ifndef CPLUS_BUG20
	class IvlDListLink {
	static	IvlAllocator*	DListLinkMem;
	public:
		IvlDListItem*	Entry;
		IvlDListLink*	Previous;
		IvlDListLink*	Next;
	inline		IvlDListLink (IvlDListItem* e, IvlDListLink* p) : Entry (e), Previous (p), Next (p->Next)	{ Previous->Next = Next->Previous = this; }
	inline		IvlDListLink (IvlDListItem* e) : Entry (e), Previous (this), Next (this)	{}
		void*	operator new (size_t);
		void	operator delete (void*);
	};
#endif

public:
	enum	dlist_status	{ NoError, WasEmpty, TooEarly, TooFar, BadIterator };
	enum	dlist_remove	{ All = -1 };

private:

	IvlDListLink*	LastLink;
	dlist_status	StatusFlag;

	void	InsertAfterLink (IvlDListLink*, IvlDListItem*);
	IvlDListItem*	RemoveLink (IvlDListLink*);

public:
inline		IvlDList () : LastLink (0), StatusFlag (NoError)				{ }
		IvlDList (IvlDListItem*);
		IvlDList (const IvlDList&);
		~IvlDList ();
		IvlDList&	operator = (const IvlDList&);
inline	dlist_status	GetStatus () const		{ return StatusFlag; }

inline	int	IsEmpty () const			{ return !LastLink; }
	IvlDListItem*	First ();
	IvlDListItem*	Last ();
	IvlDListItem*	Nth (int n);
	int	Length () const;
	int	Find (IvlDListItem*) const;

	void	Append (IvlDListItem*);
	void	Prepend (IvlDListItem*);
inline	IvlDList&	operator << (IvlDListItem* it)	{ Append (it); return *this; }

	IvlDListItem*	RemoveFirst ();
	IvlDListItem*	RemoveLast ();
	int	Remove (IvlDListItem*, int = 1);
	int	Remove (int (*) (IvlDListItem*), int = 1);
	void	Clear ();

	void	InsertAfter (const IvlDListIter&, IvlDListItem*);
	void	InsertBefore (const IvlDListIter&, IvlDListItem*);
	IvlDListItem*	RemoveAfter (const IvlDListIter&);
	IvlDListItem*	RemoveAt (IvlDListIter&);
};

class IvlDListIter {
friend	class	IvlDList;

public:
	enum	dlistiter_status	{ Normal, StartOfList, EndOfList };

private:
	const IvlDList*	TheList;
#ifdef CPLUS_BUG20
	IvlDListLink*	CurLink;
#else
	IvlDList::IvlDListLink*	CurLink;
#endif
	dlistiter_status	StatusFlag;

public:
inline		IvlDListIter (const IvlDList& l) : TheList (&l), CurLink (0), StatusFlag (StartOfList)	{}
inline	void	Reset ()		{ CurLink = 0; StatusFlag = StartOfList; }
inline	void	GotoEnd ()		{ CurLink = TheList->LastLink; StatusFlag = CurLink ? EndOfList : StartOfList; }
inline	IvlDListIter&	operator = (const IvlDList& l)	{ TheList = &l; CurLink = 0; StatusFlag = StartOfList; return *this; }
inline	IvlDListIter&	operator = (const IvlDListIter& li)	{ TheList = li.TheList; CurLink = li.CurLink; StatusFlag = li.StatusFlag; return *this; }
	IvlDListIter&	operator ++ ();
	IvlDListIter&	operator -- ();
	int	Find (IvlDListItem*);
	int	FindBack (IvlDListItem*);
	IvlDListItem*	operator * () const;
inline	dlistiter_status	GetStatus () const		{ return StatusFlag; }
inline	operator int () const	{ return StatusFlag == Normal; }
};

#ifndef CPLUS_BUG19
template <class ITEM> class IvlDListIterOf;

template <class ITEM> class IvlDListOf : public IvlDList {
public:
inline		IvlDListOf () : IvlDList ()	{}
inline		IvlDListOf (ITEM* it) : IvlDList (it)	{}
inline	ITEM*	First ()	{ return (ITEM*) (IvlDList::First ()); }
inline	ITEM*	Last ()	{ return (ITEM*) (IvlDList::Last ()); }
inline	ITEM*	Nth (int n)	{ return (ITEM*) (IvlDList::Nth (n)); }
inline	int	Find (ITEM* it) const	{ return IvlDList::Find (it); }

inline	void	Append (ITEM* it)	{ IvlDList::Append (it); }
inline	void	Prepend (ITEM* it)	{ IvlDList::Prepend (it); }
inline	IvlDListOf <ITEM>&	operator << (ITEM* it)	{ IvlDList::Append (it); return *this; }

inline	ITEM*	RemoveFirst ()	{ return (ITEM*) (IvlDList::RemoveFirst ()); }
inline	ITEM*	RemoveLast ()	{ return (ITEM*) (IvlDList::RemoveLast ()); }
inline	int	Remove (ITEM* it, int nb = 1)	{ return IvlDList::Remove (it, nb); }
inline	int	Remove (int (*p) (ITEM*), int nb = 1)	{ return IvlDList::Remove ((int (*) (ITEM*)) p, nb); }

inline	void	InsertAfter (const IvlDListIterOf <ITEM>& li, ITEM*it)	{ IvlDList::InsertAfter (li, it); }
inline	void	InsertBefore (const IvlDListIterOf <ITEM>& li, ITEM* it)	{ IvlDList::InsertBefore (li, it); }
inline	ITEM*	RemoveAfter (const IvlDListIterOf <ITEM>& li)		{ return (ITEM*) IvlDList::RemoveAfter (li); }
inline	ITEM*	RemoveAt (IvlDListIterOf <ITEM>& li)		{ return (ITEM*) IvlDList::RemoveAfter (li); }
};

template <class ITEM> class IvlDListIterOf : public IvlDListIter {
public:
inline		IvlDListIterOf (const IvlDListOf <ITEM>& l) : IvlDListIter (l)	{ }
inline	IvlDListIterOf <ITEM>&	operator =  (const IvlDListOf <ITEM>& l)	{ return (IvlDListIterOf <ITEM>&) IvlDListIter::operator = (l); }
inline	IvlDListIterOf <ITEM>&	operator =  (const IvlDListIterOf <ITEM>& li)	{ return (IvlDListIterOf <ITEM>&) IvlDListIter::operator = (li); }
inline	ITEM*	operator * () const	{ return (ITEM*) IvlDListIter::operator * (); }
inline	int	Find (ITEM* it)	{ return IvlDListIter::Find (it); }
inline	int	FindBack (ITEM* it)	{ return IvlDListIter::FindBack (it); }
};
#endif	/* CPLUS_BUG19 */

#endif	/* DList_H_ */