diff options
Diffstat (limited to 'utils/DList.cc')
-rw-r--r-- | utils/DList.cc | 573 |
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; +} + |