path: root/utils/List.cc

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

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

/*?class IvlList

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

?*/

#ifdef CPLUS_BUG20
class IvlListLink {
static	IvlAllocator*	ListLinkMem;
static	void	ClassInit ();
public:
	IvlListItem*	Entry;
	IvlListLink*	Next;
inline		IvlListLink (IvlListItem* e, IvlListLink* n = 0)	{ Entry = e; Next = n ? n : this; }
	IvlListLink*	Previous ();
	void*	operator new (size_t);
	void	operator delete (void*);
};
#endif

#ifdef CPLUS_BUG20
IvlAllocator* IvlListLink::ListLinkMem = 0;
#else
IvlAllocator* IvlList::IvlListLink::ListLinkMem = 0;
#endif

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

/*?nodoc?*/
void
#ifdef CPLUS_BUG20
IvlListLink :: operator delete (void* that)
#else
IvlList::IvlListLink :: operator delete (void* that)
#endif
{
	ListLinkMem->Free (that);
}

/*!
Get the link whose next link is this one.
!*/
/*?hidden?*/
#ifndef CPLUS_BUG20
IvlList::IvlListLink*
IvlList::IvlListLink :: Previous ()
#else
IvlListLink*
IvlListLink :: Previous ()
#endif
{
#ifndef CPLUS_BUG20
	register IvlList::IvlListLink* pl = this;
#else
	register IvlListLink* pl = this;
#endif
	while (pl->Next != this)
		pl = pl->Next;
	return pl;
}

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

/*?
Create a list with one element \var{e}.
?*/
IvlList :: IvlList (IvlListItem* e)
: LastLink (new IvlListLink (e)),
  StatusFlag (NoError)
{
}

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

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

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

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

#ifdef DOC
/*?
Get the status flag of a list. This can be one of \var{IvlList::NoError, IvlList::WasEmpty,
IvlList::TooEarly, IvlList::TooFar} or \var{IvlList::BadIterator}.
The status flag is modified by most operations on lists. Those which
modify it when errors are encountered also set it to \var{IvlList::NoError}
when there is no error.
?*/
list_status
IvlList :: GetStatus () const
{
}
#endif	/* DOC */

/*?nextdoc?*/
IvlListItem*
IvlList :: 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}: the status flag is
set to \var{IvlList::WasEmpty} in the latter case.
?*/
IvlListItem*
IvlList :: 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{IvlList::TooFar}. If \var{n} is negative,
this function returns 0 but sets the status to \var{IvlList::NoError}.
?*/
IvlListItem*
IvlList :: Nth (int n)
{
	StatusFlag = NoError;
	if (n <= 0)
		return 0;
	IvlListIter li (*this);
	while (n > 0 && ++li)
		--n;
	if (n != 0)
		StatusFlag = TooFar;
	return *li;
}

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

/*?
Check whether an item is present in a list. If \var{rank} is not null, it is filled with the
rank of the first occurence of \var{e} in the list.
?*/
int
IvlList :: Find (IvlListItem* e, int* rank) const
{
	int rk = 0;
	int ret = 0;

	IvlListIter li (*this);
	while (++rk, ++li)
		if (*li == e) {
			ret = 1;
			break;
		}

	if (rank)
		*rank = ret ? rk : 0;
	return ret;
}

/*?nextdoc?*/
IvlListIndex
IvlList :: Prepend (IvlListItem* e)
{
	if (LastLink)
		/* remember that LastLink->Next is the first */
		LastLink->Next = new IvlListLink (e, LastLink->Next);
	else
		LastLink = new IvlListLink (e);
	return LastLink;
}

/*?
Add an element at the beginning (resp. end) of a list.
?*/
IvlListIndex
IvlList :: Append (IvlListItem* e)
{
	if (LastLink) {
		LastLink = LastLink->Next = new IvlListLink (e, LastLink->Next);
	} else
		LastLink = new IvlListLink (e);
	return LastLink;
}

/*?
Remove the first element of a list and return it. The status flag is set to
\var{IvlList::WasEmpty} when the list was empty.
?*/
IvlListItem*
IvlList :: RemoveFirst ()
{
	/* Handle the case when the list is empty */
	if (!LastLink) {
		StatusFlag = WasEmpty;
		return 0;
	} 
	StatusFlag = NoError;

	/* Get the first element and its data */
	IvlListLink* first = LastLink->Next;
	IvlListItem* data = first->Entry;
	/* Remove it from the chain */
	if (LastLink == first)
		LastLink = 0;
	else
		LastLink->Next = first->Next;
	/* delete it */
	delete first;
	/* return its data */
	return data;
}

/*?
Remove the last element of a list and return it. The status flag is set to
\var{IvlList::WasEmpty} when the list was empty. This function has to locate the last
element, and hence has a linear cost.
?*/
IvlListItem*
IvlList :: RemoveLast ()
{
	/* Handle the case when the list is empty */
	if (!LastLink) {
		StatusFlag = WasEmpty;
		return 0;
	}
	StatusFlag = NoError;

	/* Find the element that will be the new LastLink */
	register IvlListLink* newlast = LastLink->Previous ();

	/* Save the element to be deleted and its data */
	IvlListLink* del = LastLink;
	IvlListItem* data = LastLink->Entry;
	/* Remove it from the chain */
	if (newlast == LastLink)
		LastLink = 0;
	else {
		newlast->Next = LastLink->Next;
		LastLink = newlast;
	}
	/* delete it */
	delete del;
	/* return its data */
	return data;
}

/*!
Insert an element before the link \var{l}. This function has a linear cost.
!*/
/*?hidden?*/
IvlListIndex
IvlList :: InsertBeforeLink (IvlListLink* l, IvlListItem* e)
{
	IvlListLink* prev = l->Previous ();
	IvlListLink* newlink = new IvlListLink (e, l);
	prev->Next = newlink;
	return newlink;
}

/*!
Insert an element after the link \var{l}.
!*/
/*?hidden?*/
IvlListIndex
IvlList :: InsertAfterLink (IvlListLink* l, IvlListItem* e)
{
	IvlListLink* newlink = new IvlListLink (e, l->Next);
	l->Next = newlink;
	if (LastLink == l)
		LastLink = newlink;
	return newlink;
}

/*!
Remove the link which is after \var{l} and return its entry. If \var{l} is the last link of
the list, the first one is removed.
!*/
/*?hidden?*/
IvlListItem*
IvlList :: RemoveAfterLink (IvlListLink* l)
{
	IvlListLink* del = l->Next;
	IvlListItem* data = del->Entry;
	if (del == l)  {
		LastLink = 0;
	} else {
		l->Next = del->Next;
		if (LastLink == del)
			LastLink = l;
	}
	delete del;
	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
IvlList :: Remove (IvlListItem* entry, int num)
{
	int removed = 0;
	IvlListIter li (*this);
	IvlListIter lj (*this);
	while ((num < 0 || removed < num) && ++li) {
		if (*li == entry) {
			RemoveAfter (lj);
			++removed;
			li = lj;
		} else
			++lj;
	}
	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
IvlList :: Remove (int (*p) (IvlListItem*), int num)
{
	int removed = 0;
	IvlListIter li (*this);
	IvlListIter lj (*this);
	while ((num < 0 || removed < num) && ++li) {
		if ((*p) (*li)) {
			RemoveAfter (lj);
			++removed;
			li = lj;
		} else
			++lj;
	}
	return removed;
}

/*?nextdoc?*/
IvlListIndex
IvlList :: InsertAfter (const IvlListIter& li, IvlListItem* e)
{
	if (li.TheList != this) {
		StatusFlag = BadIterator;
		return 0;
	}
	StatusFlag = NoError;
	IvlListIndex idx = 0;
	if (!li.CurLink) {
		if (li.StatusFlag == IvlListIter::StartOfList) {
			idx = Prepend (e);
		} else {
			fprintf (stderr, "abnormal status in IvlList::InsertAfter\n");
			abort ();
		}
	} else if (li.StatusFlag == IvlListIter::EndOfList) {
		idx = Append (e);
	} else {
		idx = InsertAfterLink (li.CurLink, e);
	}
	return idx;
}

/*?
Insert an element before (resp. after) the current position of the iterator \var{li}.
These functions are both equivalent to \fun{IvlList::Prepend} if the iterator is at the 
beginning of the list (ie. before the first element).
\fun{InsertAfter} is performed in a constant time, while \fun{InsertBefore}
has a linear cost. If \var{li} is not an iterator on this list, the status flag of the list
is set to \var{IvlList::BadIterator}.
?*/
IvlListIndex
IvlList :: InsertBefore (const IvlListIter& li, IvlListItem* e)
{
	if (li.TheList != this) {
		StatusFlag = BadIterator;
		return 0;
	}
	StatusFlag = NoError;
	IvlListIndex idx = 0;
	if (!li.CurLink) {
		if (li.StatusFlag == IvlListIter::StartOfList) {
			idx = Prepend (e);
		} else {
			fprintf (stderr, "abnormal status in IvlList::InsertAfter\n");
			abort ();
		}
	} else if (li.StatusFlag == IvlListIter::EndOfList) {
		idx = Append (e);
	} else {
		idx = InsertBeforeLink (li.CurLink, e);
	}
	return idx;
}

/*?
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 removed.
If \var{li} points at the last element, the status flag is set to \var{IvlList::TooFar}.
If the list is empty, the flag is set to \var{IvlList::EmptyList}. In both cases, the 
return value is null. If \var{li} is not an iterator
on this list, the flag is set to \var{IvlList::BadIterator}.
This function may be used
when one wants to iterate through a list and remove some elements:
\begin{ccode}
    IvlListIter li = l;
    IvlListIter lj = l;
    while (++li)
        if (do_remove (*li)) {
            l.RemoveAfter (lj);
            li = lj;
        } else {
            ++lj;
        }
\end{ccode}
?*/
IvlListItem*
IvlList :: RemoveAfter (const IvlListIter& 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 RemoveAfterLink (li.CurLink);
	} else {
		return RemoveAfterLink (LastLink);
	}
}

#ifdef DOC

/*?class IvlListIter
The class \typ{IvlListIter} 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. Refer to the implementation figure for more details.
Of course, the functions such as \var{InsertAfter} or \var{RemoveAfter} are designed
to be harmless. However, they may be dangerous if another iterator is used at the same
time on the same list.
The basic usage of an iterator is the following:
\begin{ccode}
    extern IvlList& l;
    IvlListIter li = l;
    while (++li)
        foo (*li);    // *li is the value that was stored with Append
\end{ccode}
?*/

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

/*?
Build an iterator on list \var{l}, pointing at the element denoted by \var{idx}. No check is done on whether 
\var{idx} is a valid index of list \var{l}.
?*/
IvlListIter :: IvlListIter (const IvlList& l, IvlListIndex idx)
 : TheList (&l),
#ifdef CPLUS_BUG20
  CurLink ((IvlListLink*) idx),
#else
  CurLink ((IvlList::IvlListLink*) idx),
#endif
  StatusFlag (idx ? Normal : StartOfList)
{
}

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

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

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

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

/*?
Take one step of iteration.
?*/ 
IvlListIter&
IvlListIter :: 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;
}

#ifndef CPLUS_BUG16
/*?
Post-increment equivalent of the previous operator. This operator is just here
as a placeholder: it does the same thing as the previous one.
?*/
IvlListIter&
IvlListIter :: operator ++ (int)
{
	++(*this);
	return *this;
}
#endif

/*?
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
IvlListIter :: Find (IvlListItem* e)
{
	while (++(*this))
		if (**this == e)
			return 1;
	return 0;
}

#ifdef DOC

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#endif	/* DOC */