path: root/utils/DList.cc

/*
 *	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$
 */

#include "DList.h"
#include "Allocator.h"
#include <stdlib.h>
#include <stdio.h>

/*?class IvlDList

\begin{figure}[hbtp]
\hfil
\psfig{figure=FIGURES/IvlDList.epsf}\par \caption{Internal structure of \typ{IvlDList}s}
\hfil
\end{figure}

?*/

#ifdef CPLUS_BUG20
class IvlDListLink {
static	IvlAllocator*	DListLinkMem;
static	void	ClassInit ();
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

#ifdef CPLUS_BUG20
IvlAllocator* IvlDListLink::DListLinkMem = 0;
#else
IvlAllocator* IvlDList::IvlDListLink::DListLinkMem = 0;
#endif

/*?nodoc?*/
void*
#ifdef CPLUS_BUG20
IvlDListLink :: operator new (size_t)
#else
IvlDList::IvlDListLink :: operator new (size_t)
#endif
{
	if (!DListLinkMem)
#ifdef CPLUS_BUG20
		DListLinkMem = new IvlAllocator (sizeof (IvlDListLink));
#else
		DListLinkMem = new IvlAllocator (sizeof (IvlDList::IvlDListLink));
#endif
	return DListLinkMem->Alloc ();
}

/*?nodoc?*/
void
#ifdef CPLUS_BUG20
IvlDListLink :: operator delete (void* that)
#else
IvlDList::IvlDListLink :: operator delete (void* that)
#endif
{
	DListLinkMem->Free (that);
}

#ifdef DOC
/*?
Create an empty list.
?*/
IvlDList :: IvlDList ()
{
}
#endif

/*?
Create a list with one element \var{e}.
?*/
IvlDList :: IvlDList (IvlDListItem* e)
: LastLink (new IvlDListLink (e)),
  StatusFlag (NoError)
{
}

/*?nodoc?*/
IvlDList :: IvlDList (const IvlDList& l)
: LastLink (0),
  StatusFlag (NoError)
{
	IvlDListIter li (l);
	while (++li)
		Append (*li);
}

/*?
Destructor for lists. No operation is performed on the elements.
?*/
IvlDList :: ~IvlDList ()
{
	Clear ();
}

/*?
Empty a list.
?*/
void
IvlDList :: Clear ()
{
	IvlDListLink* del = LastLink;
	while (del) {
		IvlDListLink* next = del->Next;
		if (next == LastLink)
			next = 0;
		delete del;
		del = next;
	}
	LastLink = 0;
}

/*?nodoc?*/
IvlDList&
IvlDList :: operator = (const IvlDList& l)
{
	if (this != &l) {
		Clear ();
		IvlDListIter li (l);
		while (++li)
			Append (*li);
	}
	return *this;
}

/*?nextdoc?*/
IvlDListItem*
IvlDList :: First ()
{
	if (!LastLink) {
		StatusFlag = WasEmpty;
		return 0;
	} 
	StatusFlag = NoError;
	return LastLink->Next->Entry;
}

/*?
Return the first (resp. last) element in the list, or 0 if the list was empty.
The case of a null element can be distinguished from the case
when the list is empty with the function \fun{GetStatus}.
?*/
IvlDListItem*
IvlDList :: Last ()
{
	if (!LastLink) {
		StatusFlag = WasEmpty;
		return 0;
	} 
	StatusFlag = NoError;
	return LastLink->Entry;
}

/*?
Get the \var{n}-th element of a list. If \var{n} is greater than the length of the list
this function returns 0 and sets the status to \var{TooFar}. If \var{n} is negative,
this function returns 0 but sets the status to \var{NoError}.
?*/
IvlDListItem*
IvlDList :: Nth (int n)
{
	StatusFlag = NoError;
	if (n <= 0)
		return 0;
	IvlDListIter li (*this);
	while (n > 0 && ++li)
		--n;
	if (n != 0)
		StatusFlag = TooFar;
	return *li;
}

/*?
Compute the number of elements in a list.
?*/
int
IvlDList :: Length () const
{
	int result = 0;
	IvlDListIter li (*this);
	while (++li)
		++result;
	return result;
}

/*?
Check whether an item is present in a list.
?*/
int
IvlDList :: Find (IvlDListItem* e) const
{
	IvlDListIter li (*this);
	while (++li)
		if (*li == e)
			return 1;
	return 0;
}

/*?nextdoc?*/
void
IvlDList :: Prepend (IvlDListItem* e)
{
	if (LastLink)
		new IvlDListLink (e, LastLink);
	else
		LastLink = new IvlDListLink (e);
}

/*?
Add an element at the beginning (resp. end) of a list.
?*/
void
IvlDList :: Append (IvlDListItem* e)
{
	if (LastLink) {
		LastLink = new IvlDListLink (e, LastLink);
	} else
		LastLink = new IvlDListLink (e);
}

/*?
Remove the first element of a list and return it.
?*/
IvlDListItem*
IvlDList :: RemoveFirst ()
{
	/* Handle the case when the list is empty */
	if (!LastLink) {
		StatusFlag = WasEmpty;
		return 0;
	} 
	StatusFlag = NoError;

	return RemoveLink (LastLink->Next);
}

/*?
Remove the last element of a list and return it.
?*/
IvlDListItem*
IvlDList :: RemoveLast ()
{
	/* Handle the case when the list is empty */
	if (!LastLink) {
		StatusFlag = WasEmpty;
		return 0;
	}
	StatusFlag = NoError;

	return RemoveLink (LastLink);
}

/*?
Insert an element after the link \var{l}.
?*/
void
IvlDList :: InsertAfterLink (IvlDListLink* l, IvlDListItem* e)
{
	IvlDListLink* newlink = new IvlDListLink (e, l);
	if (LastLink == l)
		LastLink = newlink;
}

/*?
Remove a link.
?*/
IvlDListItem*
IvlDList :: RemoveLink (IvlDListLink* l)
{
	/* store its data */
	IvlDListItem* data = l->Entry;
	if (l->Next == l)
		LastLink = 0;
	else {
		l->Previous->Next = l->Next;
		l->Next->Previous = l->Previous;
		if (l == LastLink)
			LastLink = l->Previous;
	}
	/* delete it */
	delete l;
	/* return its data */
	return data;
}

/*?
Remove an element from a list. This function iterates through the list until it deletes
\var{num} appearances of \var{entry}. The actual number of removals is returned.
If \var{num} is \var{All} or is negative, all appearances of \var{entry} are deleted.
?*/
int
IvlDList :: Remove (IvlDListItem* entry, int num)
{
	int removed = 0;
	IvlDListIter li (*this);
	while ((num < 0 || removed < num) && ++li) {
		if (*li == entry) {
			RemoveLink (li.CurLink);
			removed++;
			break;
		}
	}
	return removed;
}

/*?
Remove elements from a list. This function iterates through the list until it deletes
\var{num} elements for which the function \var{p} returns a non-null value.
The actual number of removals is returned.
If \var{num} is \var{All} or is negative, all matching elements are deleted.
?*/
int
IvlDList :: Remove (int (*p) (IvlDListItem*), int num)
{
	int removed = 0;
	IvlDListIter li (*this);
	while ((num < 0 || removed < num) && ++li) {
		if ((*p) (*li)) {
			RemoveAt (li);
			++removed;
		}
	}
	return removed;
}

/*?nextdoc?*/
void
IvlDList :: InsertAfter (const IvlDListIter& li, IvlDListItem* e)
{
	if (li.TheList != this) {
		StatusFlag = BadIterator;
		return;
	}
	if (!li.CurLink) {
		if (li.StatusFlag == IvlDListIter::StartOfList) {
			Prepend (e);
		} else {
			fprintf (stderr, "abnormal status in IvlDList::InsertAfter\n");
			abort ();
		}
	} else if (li.StatusFlag == IvlDListIter::EndOfList) {
		Append (e);
	} else {
		InsertAfterLink (li.CurLink, e);
	}
}

/*?
Insert an element before (resp. after) the current position of the iterator \var{li}.
These functions are both equivalent to \fun{IvlDList::Prepend} if the iterator is at the 
beginning of the list (ie. before the first element).
\fun{InsertAfter} and \fun{InsertAfter} are performed in a constant time.
?*/
void
IvlDList :: InsertBefore (const IvlDListIter& li, IvlDListItem* e)
{
	if (li.TheList != this) {
		StatusFlag = BadIterator;
		return;
	}
	if (!li.CurLink) {
		if (li.StatusFlag == IvlDListIter::StartOfList) {
			Prepend (e);
		} else {
			fprintf (stderr, "abnormal status in IvlDList::InsertAfter\n");
			abort ();
		}
	} else if (li.StatusFlag == IvlDListIter::EndOfList) {
		Append (e);
	} else {
		new IvlDListLink (e, li.CurLink->Previous);
	}
}

/*?
Remove the element after the current element of the iterator \var{li}.
If \var{li} points before the beginning of the list, the first element is returned.
If \var{li} points at the last element, the status flag is set to \var{TooFar}.
If the list is empty, the flag is set to \var{EmptyList}. In both cases, the 
return value is null.
?*/
IvlDListItem*
IvlDList :: RemoveAfter (const IvlDListIter& li)
{
	if (li.TheList != this) {
		StatusFlag = BadIterator;
		return 0;
	}
	if (li.CurLink == LastLink) {
		StatusFlag = LastLink ? TooFar : WasEmpty;
		return 0;
	}
	StatusFlag = NoError;
	if (li.CurLink) {
		return RemoveLink (li.CurLink->Next);
	} else {
		return RemoveLink (LastLink->Next);
	}
}

/*?
Remove the element pointed at by the iterator \var{li}.
If \var{li} points before the beginning of the list, or has reached
its end, the return value is null, and the status flag is set to \var{TooEarly}
(resp. \var{TooFar}). In all other cases, \var{li} is rewinded by one step,
in order to allow such loops as:
\begin{ccode}
    IvlDListIter li (l);
    while (++li)
        if (do_remove (*li))
            l.RemoveAt (l);
\end{ccode}
?*/
IvlDListItem*
IvlDList :: RemoveAt (IvlDListIter& li)
{
	if (li.TheList != this) {
		StatusFlag = BadIterator;
		return 0;
	}
	if (!li.CurLink) {
		StatusFlag = TooEarly;
		return 0;
	}
	if (li.StatusFlag == IvlDListIter::EndOfList) {
		StatusFlag = TooFar;
		return 0;
	}
	StatusFlag = NoError;
	IvlDListLink* del = li.CurLink;
	--li;
	return RemoveLink (del);
}

#ifdef DOC
/*?class IvlDListIter
The class \typ{IvlDListIter} allows iterations on lists.
Several iterators may be used at a time on the same list. It is dangerous to modify
a list that is being iterated.
?*/

/*?
Initialize an iterator associated to the list \var{l}. That iterator will point at the beginning
of the list, {\em before} the first element.
?*/
IvlDListIter :: IvlDListIter (const IvlDList& l)
{
}

/*?
Get the status of an iterator. The status may be one of \var{Normal, StartOfList}, or
\var{EndOfList}
?*/
dlistiter_status
IvlDListIter :: GetStatus () const
{
}

/*?nextdoc?*/
void
IvlDListIter :: Reset ()
{
}

/*?
Reset an iterator to the beginning (resp. the end) of the list.
?*/
void
IvlDListIter :: GotoEnd ()
{
}
#endif	/* DOC */

/*?
Get the current entry pointed by an iterator. This operator returns 0 if the iterator is
at the beginning or the end of the list. To distinguish those cases from the
case when the entry is null, you can use the method \fun{GetStatus}.
?*/
IvlDListItem*
IvlDListIter :: operator * () const
{
	return (CurLink && StatusFlag == Normal) ? CurLink->Entry : 0;
}

#ifdef DOC

/*?
Check whether the status of an iterator is \var{Normal}.
?*/
IvlDListIter :: operator int () const
{
}
#endif

/*?
Take one step of iteration.
?*/ 
IvlDListIter&
IvlDListIter :: operator ++ ()
{
	/* This test covers all the cases :
		- the iteration has already begun, and is at its end.
		- the iteration has not begun, but the list is empty.
	*/
	if (CurLink == TheList->LastLink) {
		StatusFlag = EndOfList;
	} else {
		CurLink = CurLink ? CurLink->Next : TheList->LastLink->Next;
		StatusFlag = Normal;
	}
	return *this;
}

/*?
Rewind iteration by one step.
?*/ 
IvlDListIter&
IvlDListIter :: operator -- ()
{
	if (StatusFlag == Normal) {
		CurLink = CurLink->Previous;
		if (CurLink == TheList->LastLink)
			Reset ();
	} else if (StatusFlag == EndOfList) {
		StatusFlag = Normal;
	}
	return *this;
}

/*?
Try and find the element \var{e} in the list, starting from the
current position of the iterator (this position not included).
If \var{e} is present in the list, the iterator will
be correctly positionned. If not, it will have reached the end of the list.
?*/
int
IvlDListIter :: Find (IvlDListItem* e)
{
	while (++(*this))
		if (**this == e)
			return 1;
	return 0;
}

/*?
Try and find the element \var{e} in the list, searching backward from the
current position of the iterator (this position not included).
If \var{e} is present in the list, the iterator will
be correctly positionned. If not, it will have reached the end of the list.
?*/
int
IvlDListIter :: FindBack (IvlDListItem* e)
{
	while (--(*this))
		if (**this == e)
			return 1;
	return 0;
}

#ifdef DOC

/*?class IvlDListOf
The generic classes \typ{IvlDListOf} and \typ{IvlDListIterOf} are derived classes
of \typ{IvlDList} and \typ{IvlDListIter} that provide lists of pointers to class objects.
When parameterized by the class \typ{ITEM}, the following functions are redefined:
?*/

/*?nextdoc?*/
IvlDListOf :: IvlDListOf (ITEM* it)
{
}

/*?nextdoc?*/
ITEM*
IvlDListOf :: First ()
{
}

/*?nextdoc?*/
ITEM*
IvlDListOf :: Last ()
{
}

/*?nextdoc?*/
ITEM*
IvlDListOf :: Nth (int n)
{
}

/*?nextdoc?*/
int
IvlDListOf :: Find (ITEM* it) const
{
}

/*?nextdoc?*/
void
IvlDListOf :: Append (ITEM* it)
{
}

/*?nextdoc?*/
void
IvlDListOf :: Prepend (ITEM* it)
{
}

/*?nextdoc?*/
IvlDListOf&
IvlDListOf :: operator << (ITEM* it)
{
}

/*?nextdoc?*/
ITEM*
IvlDListOf :: RemoveFirst ()
{
}

/*?nextdoc?*/
ITEM*
IvlDListOf :: RemoveLast ()
{
}

/*?nextdoc?*/
int
IvlDListOf :: Remove (ITEM* it, int nb = 1)
{
}

/*?nextdoc?*/
int
IvlDListOf :: Remove (int (*p) (ITEM*), int nb = 1)
{
}

/*?nextdoc?*/
void
IvlDListOf :: InsertAfter (const IvlDListIterOf <ITEM>& li, ITEM*it)
{
}

/*?nextdoc?*/
void
IvlDListOf :: InsertBefore (const IvlDListIterOf <ITEM>& li, ITEM* it)
{
}

/*?nextdoc?*/
ITEM*
IvlDListOf :: RemoveAfter (const IvlDListIterOf <ITEM>& li)	
{
}

/*?
These functions are equivalent to their homonyms in the class \typ{IvlDList},
except that they are customized in order to manipulate pointers to \typ{ITEM}
instead of \typ{void*}.
?*/
ITEM*
IvlDListOf :: RemoveAt (IvlDListIterOf <ITEM>& li)	
{
}

/*?nextdoc?*/
IvlDListIterOf  :: IvlDListIterOf (const IvlDListOf <ITEM>& l)
{
}
	
/*?nextdoc?*/
ITEM*
IvlDListIterOf :: operator * () const
{
}

/*?nextdoc?*/
int
IvlDListIterOf :: Find (ITEM* it)	
{
}

/*?
These functions are equivalent to their homonyms in the class \typ{IvlDListIter},
except that they are customized in order to manipulate pointers to \typ{ITEM}
instead of \typ{void*}.
?*/
int
IvlDListIterOf :: FindBack (ITEM* it)	
{
}

#endif	/* DOC */