1 files changed, 426 insertions, 0 deletions
diff --git a/utils/Chain.cc b/utils/Chain.cc
new file mode 100644
index 0000000..e9cd14f
--- /dev/null
+++ b/utils/Chain.cc
@@ -0,0 +1,426 @@
+/*
+ *	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;
+}