path: root/utils/Chain.cc

/*
 *	CENA C++ Utilities
 *
 *	Copyright 1992
 *	Centre d'Etudes de la Navigation Aerienne (CENA)
 *
 *	generic chains of objects - to be updated
 *
 *	$Id$
 *	$CurLog$
 */

#include "Chain.h"
#include <stdlib.h>
#include <stdio.h>

CcuChain :: ~CcuChain ()
{
}

CcuChainItem*
CcuChain :: GetPrevious (CcuChainItem* i)
{
	register CcuChainItem* c = LastLink;
	register CcuChainItem* n;
	while ((n = GetNext (c)) != i)
		c = n;
	return c;
}

/*?
Empty a list.
?*/
void
CcuChain :: Clear ()
{
	CcuChainItem* del = LastLink;
	while (del) {
		CcuChainItem* next = GetNext (del);
		if (next == LastLink)
			next = 0;
		Delete (del);
		del = next;
	}
	LastLink = 0;
}


/*?nextdoc?*/
CcuChainItem*
CcuChain :: First ()
{
	if (!LastLink) {
		StatusFlag = WasEmpty;
		return 0;
	} 
	StatusFlag = NoError;
	return GetNext (LastLink);
}

/*?
Return the first/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}.
?*/
CcuChainItem*
CcuChain :: Last ()
{
	if (!LastLink) {
		StatusFlag = WasEmpty;
		return 0;
	} 
	StatusFlag = NoError;
	return LastLink;
}

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

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

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

/*?nextdoc?*/
void
CcuChain :: Prepend (CcuChainItem* e)
{
	if (LastLink) {
		/* remember that LastLink->Next is the first */
		SetNext (e, GetNext (LastLink));
		SetNext (LastLink, e);
	} else {
		LastLink = e;
		SetNext (e, e);
	}
}

/*?
Insert an element at the beginning/end of a list.
?*/
void
CcuChain :: Append (CcuChainItem* e)
{
	if (LastLink) {
		SetNext (e, GetNext (LastLink));
		SetNext (LastLink, e);
		LastLink = e;
	} else {
		LastLink = e;
		SetNext (e, e);
	}
}

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

	/* Get the first element */
	CcuChainItem* first = GetNext (LastLink);

	/* Remove it from the chain */
	if (LastLink == first)
		LastLink = 0;
	else
		SetNext (LastLink, GetNext (first));
	return first;
}


/*?
Remove the last element of a list and return it. This function has to locate the last
element, and hence has a linear cost.
?*/
CcuChainItem*
CcuChain :: 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 CcuChainItem* newlast = GetPrevious (LastLink);

	/* Save the element to be deleted and its data */
	CcuChainItem* last = LastLink;
	/* Remove it from the chain */
	if (newlast == LastLink)
		LastLink = 0;
	else {
		SetNext (newlast, GetNext (LastLink));
		LastLink = newlast;
	}
	return last;
}

/*?
Insert an element before the link \var{l}. This function has a linear cost.
?*/
void
CcuChain :: InsertBefore (CcuChainItem* l, CcuChainItem* e)
{
	CcuChainItem* prev = GetPrevious (l);
	SetNext (prev, e);
	SetNext (e, l);
}


/*?
Insert an element after the link \var{l}.
?*/
void
CcuChain :: InsertAfter (CcuChainItem* l, CcuChainItem* e)
{
	SetNext (e, GetNext (l));
	SetNext  (l, e);
	if (LastLink == l)
		LastLink = e;
}

/*?
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.
?*/
CcuChainItem*
CcuChain :: RemoveAfter (CcuChainItem* l)
{
	CcuChainItem* del = GetNext (l);
	if (del == l)  {
		LastLink = 0;
	} else {
		SetNext (l, GetNext (l));
		if (LastLink == del)
			LastLink = l;
	}
	return del;
}

/*?
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
CcuChain :: Remove (CcuChainItem* entry)
{
	int removed = 0;
	CcuChainIter li (*this);
	CcuChainIter lj (*this);
	while (++li) {
		if (*li == entry) {
			RemoveAfter (lj);
			return 1;
		} else
			++lj;
	}
	return 0;
}

/*?
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
CcuChain :: Remove (int (*p) (CcuChainItem*))
{
	int removed = 0;
	CcuChainIter li (*this);
	CcuChainIter lj (*this);
	while (++li) {
		if ((*p) (*li)) {
			RemoveAfter (lj);
			return 1;
		} else
			++lj;
	}
	return 0;
}


/*?nextdoc?*/
void
CcuChain :: InsertAfter (const CcuChainIter& li, CcuChainItem* e)
{
	if (li.TheChain != this) {
		StatusFlag = BadIterator;
		return;
	}
	StatusFlag = NoError;
	if (!li.CurLink) {
		if (li.StatusFlag == CcuChainIter::StartOfChain) {
			Prepend (e);
		} else {
			fprintf (stderr, "abnormal status in CcuChain::InsertAfter\n");
			abort ();
		}
	} else if (li.StatusFlag == CcuChainIter::EndOfChain) {
		Append (e);
	} else {
		InsertAfter (li.CurLink, e);
	}
}

/*?
Insert an element before (resp. after) the current position of the iterator \var{li}.
These functions are both equivalent to \fun{CcuChain::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
CcuChain :: InsertBefore (const CcuChainIter& li, CcuChainItem* e)
{
	if (li.TheChain != this) {
		StatusFlag = BadIterator;
		return;
	}
	StatusFlag = NoError;
	if (!li.CurLink) {
		if (li.StatusFlag == CcuChainIter::StartOfChain) {
			Prepend (e);
		} else {
			fprintf (stderr, "abnormal status in CcuChain::InsertBefore\n");
			abort ();
		}
	} else if (li.StatusFlag == CcuChainIter::EndOfChain) {
		Append (e);
	} else {
		InsertBefore (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{EmptyChain}. 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:
    CcuChainIter li (l);
    CcuChainIter lj (l);
    while (++li)
        if (do_remove (*li)) {
        	RemoveAfter (lj);
        	li = lj;
        } else
        	++lj;
?*/
CcuChainItem*
CcuChain :: RemoveAfter (const CcuChainIter& li)
{
	if (li.TheChain != this) {
		StatusFlag = BadIterator;
		return 0;
	}
	if (li.CurLink == LastLink) {
		StatusFlag = LastLink ? TooFar : WasEmpty;
		return 0;
	}
	StatusFlag = NoError;
	if (li.CurLink) {
		return RemoveAfter (li.CurLink);
	} else {
		return RemoveAfter (LastLink);
	}
}


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


/*?
Take one step of iteration.
?*/ 
CcuChainIter&
CcuChainIter :: 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 == TheChain->LastLink) {
		StatusFlag = EndOfChain;
	} else {
		CurLink = CurLink ? TheChain->GetNext (CurLink) : TheChain->GetNext (TheChain->LastLink);
		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, the iterator will
be correctly positionned. If not, it will have reached the end of the list.
?*/
int
CcuChainIter :: Find (CcuChainItem* e)
{
	while (++(*this))
		if (**this == e)
			return 1;
	return 0;
}