path: root/utils/DList.cc

/*
 *	CENA C++ Utilities
 *
 *	by Stephane Chatty
 *
 *	Copyright 1992
 *	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 CcuDList

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

?*/

#ifdef CPLUS_BUG20
class CcuDListLink {
static	CcuAllocator*	DListLinkMem;
static	void	ClassInit ();
public:
	CcuDListItem*	Entry;
	CcuDListLink*	Previous;
	CcuDListLink*	Next;
inline		CcuDListLink (CcuDListItem* e, CcuDListLink* p) : Entry (e), Previous (p), Next (p->Next)	{ Previous->Next = Next->Previous = this; }
inline		CcuDListLink (CcuDListItem* e) : Entry (e), Previous (this), Next (this)	{}
	void*	operator new (unsigned int);
	void	operator delete (void*);
};
#endif


#ifdef CPLUS_BUG20
CcuAllocator* CcuDListLink::DListLinkMem = 0;
#else
CcuAllocator* CcuDList::CcuDListLink::DListLinkMem = 0;
#endif

/*?nodoc?*/
void*
#ifdef CPLUS_BUG20
CcuDListLink :: operator new (unsigned int)
#else
CcuDList::CcuDListLink :: operator new (unsigned int)
#endif
{
	if (!DListLinkMem)
#ifdef CPLUS_BUG20
		DListLinkMem = new CcuAllocator (sizeof (CcuDListLink));
#else
		DListLinkMem = new CcuAllocator (sizeof (CcuDList::CcuDListLink));
#endif
	return DListLinkMem->Alloc ();
}

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



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

/*?
Create a list with one element \var{e}.
?*/
CcuDList :: CcuDList (CcuDListItem* e)
: LastLink (new CcuDListLink (e)),
  StatusFlag (NoError)
{
}

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


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

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

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


/*?nextdoc?*/
CcuDListItem*
CcuDList :: 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}.
?*/
CcuDListItem*
CcuDList :: 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}.
?*/
CcuDListItem*
CcuDList :: Nth (int n)
{
	StatusFlag = NoError;
	if (n <= 0)
		return 0;
	CcuDListIter li (*this);
	while (n > 0 && ++li)
		--n;
	if (n != 0)
		StatusFlag = TooFar;
	return *li;
}

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

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

/*?nextdoc?*/
void
CcuDList :: Prepend (CcuDListItem* e)
{
	if (LastLink)
		new CcuDListLink (e, LastLink);
	else
		LastLink = new CcuDListLink (e);
}

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

/*?
Remove the first element of a list and return it.
?*/
CcuDListItem*
CcuDList :: 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.
?*/
CcuDListItem*
CcuDList :: 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
CcuDList :: InsertAfterLink (CcuDListLink* l, CcuDListItem* e)
{
	CcuDListLink* newlink = new CcuDListLink (e, l);
	if (LastLink == l)
		LastLink = newlink;
}

/*?
Remove a link.
?*/
CcuDListItem*
CcuDList :: RemoveLink (CcuDListLink* l)
{
	/* store its data */
	CcuDListItem* 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
CcuDList :: Remove (CcuDListItem* entry, int num)
{
	int removed = 0;
	CcuDListIter 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
CcuDList :: Remove (int (*p) (CcuDListItem*), int num)
{
	int removed = 0;
	CcuDListIter li (*this);
	while ((num < 0 || removed < num) && ++li) {
		if ((*p) (*li)) {
			RemoveAt (li);
			++removed;
		}
	}
	return removed;
}

/*?nextdoc?*/
void
CcuDList :: InsertAfter (const CcuDListIter& li, CcuDListItem* e)
{
	if (li.TheList != this) {
		StatusFlag = BadIterator;
		return;
	}
	if (!li.CurLink) {
		if (li.StatusFlag == CcuDListIter::StartOfList) {
			Prepend (e);
		} else {
			fprintf (stderr, "abnormal status in CcuDList::InsertAfter\n");
			abort ();
		}
	} else if (li.StatusFlag == CcuDListIter::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{CcuDList::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
CcuDList :: InsertBefore (const CcuDListIter& li, CcuDListItem* e)
{
	if (li.TheList != this) {
		StatusFlag = BadIterator;
		return;
	}
	if (!li.CurLink) {
		if (li.StatusFlag == CcuDListIter::StartOfList) {
			Prepend (e);
		} else {
			fprintf (stderr, "abnormal status in CcuDList::InsertAfter\n");
			abort ();
		}
	} else if (li.StatusFlag == CcuDListIter::EndOfList) {
		Append (e);
	} else {
		new CcuDListLink (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.
?*/
CcuDListItem*
CcuDList :: RemoveAfter (const CcuDListIter& 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:
    CcuDListIter li (l);
    while (++li) {
        if (do_remove (*li))
            l.RemoveAt (l);
    }
?*/
CcuDListItem*
CcuDList :: RemoveAt (CcuDListIter& li)
{
	if (li.TheList != this) {
		StatusFlag = BadIterator;
		return 0;
	}
	if (!li.CurLink) {
		StatusFlag = TooEarly;
		return 0;
	}
	if (li.StatusFlag == CcuDListIter::EndOfList) {
		StatusFlag = TooFar;
		return 0;
	}
	StatusFlag = NoError;
	CcuDListLink* del = li.CurLink;
	--li;
	return RemoveLink (del);
}


#ifdef DOC
/*?
Initialize an iterator associated to the list \var{l}. That iterator will point at the beginning
of the list, {\em before} the first element.
?*/
CcuDListIter :: CcuDListIter (CcuDList& l)
{
}

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

/*?
Reset an iterator to the beginning of the list.
?*/
void
CcuDListIter :: Reset ()
{
}
#endif


/*?
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}.
?*/
CcuDListItem*
CcuDListIter :: operator * () const
{
	return (CurLink && StatusFlag == Normal) ? CurLink->Entry : 0;
}

#ifdef DOC

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


/*?
Take one step of iteration.
?*/ 
CcuDListIter&
CcuDListIter :: 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.
?*/ 
CcuDListIter&
CcuDListIter :: 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
CcuDListIter :: Find (CcuDListItem* 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
CcuDListIter :: FindBack (CcuDListItem* e)
{
	while (--(*this))
		if (**this == e)
			return 1;
	return 0;
}