diff options
Diffstat (limited to 'utils/List.cc')
| -rw-r--r-- | utils/List.cc | 724 |
1 files changed, 724 insertions, 0 deletions
diff --git a/utils/List.cc b/utils/List.cc new file mode 100644 index 0000000..1bbfd8e --- /dev/null +++ b/utils/List.cc @@ -0,0 +1,724 @@ +/* + * 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 */ |