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

\dessin{CcuList}{Internal structure of \typ{CcuList}s}

?*/

#ifdef CPLUS_BUG20
class CcuListLink {
static	CcuAllocator*	ListLinkMem;
static	void	ClassInit ();
public:
	CcuListItem*	Entry;
	CcuListLink*	Next;
inline		CcuListLink (CcuListItem* e, CcuListLink* n = 0)	{ Entry = e; Next = n ? n : this; }
	CcuListLink*	Previous ();
	void*	operator new (unsigned int);
	void	operator delete (void*);
};
#endif



#ifdef CPLUS_BUG20
CcuAllocator* CcuListLink::ListLinkMem = 0;
#else
CcuAllocator* CcuList::CcuListLink::ListLinkMem = 0;
#endif

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

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


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

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

/*?
Create a list with one element \var{e}.
?*/
CcuList :: CcuList (CcuListItem* e)
: LastLink (new CcuListLink (e)),
  StatusFlag (NoError)
{
}

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


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

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

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


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

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

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

/*?nextdoc?*/
void
CcuList :: Prepend (CcuListItem* e)
{
	if (LastLink)
		/* remember that LastLink->Next is the first */
		LastLink->Next = new CcuListLink (e, LastLink->Next);
	else
		LastLink = new CcuListLink (e);
}

/*?
Add an element at the beginning (resp. end) of a list.
?*/
void
CcuList :: Append (CcuListItem* e)
{
	if (LastLink) {
		LastLink = LastLink->Next = new CcuListLink (e, LastLink->Next);
	} else
		LastLink = new CcuListLink (e);
}

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

	/* Get the first element and its data */
	CcuListLink* first = LastLink->Next;
	CcuListItem* 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. This function has to locate the last
element, and hence has a linear cost.
?*/
CcuListItem*
CcuList :: 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 CcuListLink* newlast = LastLink->Previous ();

	/* Save the element to be deleted and its data */
	CcuListLink* del = LastLink;
	CcuListItem* 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.
?*/
void
CcuList :: InsertBeforeLink (CcuListLink* l, CcuListItem* e)
{
	CcuListLink* prev = l->Previous ();
	CcuListLink* newlink = new CcuListLink (e, l);
	prev->Next = newlink;
}


/*?
Insert an element after the link \var{l}.
?*/
void
CcuList :: InsertAfterLink (CcuListLink* l, CcuListItem* e)
{
	CcuListLink* newlink = new CcuListLink (e, l->Next);
	l->Next = newlink;
	if (LastLink == l)
		LastLink = 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.
?*/
CcuListItem*
CcuList :: RemoveAfterLink (CcuListLink* l)
{
	CcuListLink* del = l->Next;
	CcuListItem* 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
CcuList :: Remove (CcuListItem* entry, int num)
{
	int removed = 0;
	CcuListIter li (*this);
	CcuListIter 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
CcuList :: Remove (int (*p) (CcuListItem*), int num)
{
	int removed = 0;
	CcuListIter li (*this);
	CcuListIter lj (*this);
	while ((num < 0 || removed < num) && ++li) {
		if ((*p) (*li)) {
			RemoveAfter (lj);
			++removed;
			li = lj;
		} else
			++lj;
	}
	return removed;
}


/*?nextdoc?*/
void
CcuList :: InsertAfter (const CcuListIter& li, CcuListItem* e)
{
	if (li.TheList != this) {
		StatusFlag = BadIterator;
		return;
	}
	StatusFlag = NoError;
	if (!li.CurLink) {
		if (li.StatusFlag == CcuListIter::StartOfList) {
			Prepend (e);
		} else {
			fprintf (stderr, "abnormal status in CcuList::InsertAfter\n");
			abort ();
		}
	} else if (li.StatusFlag == CcuListIter::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{CcuList::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.
?*/
void
CcuList :: InsertBefore (const CcuListIter& li, CcuListItem* e)
{
	if (li.TheList != this) {
		StatusFlag = BadIterator;
		return;
	}
	StatusFlag = NoError;
	if (!li.CurLink) {
		if (li.StatusFlag == CcuListIter::StartOfList) {
			Prepend (e);
		} else {
			fprintf (stderr, "abnormal status in CcuList::InsertAfter\n");
			abort ();
		}
	} else if (li.StatusFlag == CcuListIter::EndOfList) {
		Append (e);
	} else {
		InsertBeforeLink (li.CurLink, e);
	}
}

/*?
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.
This function may be used
when one wants to iterate through a list and remove some elements:
    CcuListIter li (l);
    CcuListIter lj (l);
    while (++li)
        if (do_remove (*li)) {
        	RemoveAfter (lj);
        	li = lj;
        } else
        	++lj;
?*/
CcuListItem*
CcuList :: RemoveAfter (const CcuListIter& 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

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

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

/*?
Reset an iterator to the beginning of the list.
?*/
void
CcuListIter :: 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}.
?*/
CcuListItem*
CcuListIter :: operator * () const
{
	return (CurLink && StatusFlag == Normal) ? CurLink->Entry : 0;
}

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


/*?
Take one step of iteration.
?*/ 
CcuListIter&
CcuListIter :: 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 demonstrator: it was not tested because no known compiler implements that feature,
and its semantics is quite muddy.
?*/
CcuListIter&
CcuListIter :: 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
CcuListIter :: Find (CcuListItem* e)
{
	while (++(*this))
		if (**this == e)
			return 1;
	return 0;
}

#ifdef DOC

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


#endif	/* DOC */