1 files changed, 573 insertions, 0 deletions
diff --git a/utils/DList.cc b/utils/DList.cc
new file mode 100644
index 0000000..5d34f7b
--- /dev/null
+++ b/utils/DList.cc
@@ -0,0 +1,573 @@
+/*
+ *	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
+
+\dessin{CcuDList}{Internal structure of \typ{CcuDList}s}
+
+?*/
+
+#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;
+}
+