/* * CENA C++ Utilities * * by Stephane Chatty * * Copyright 1992-1995 * 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 #include /*?class CcuList \begin{figure}[hbtp] \hfil \psfig{figure=FIGURES/CcuList.epsf}\par \caption{Internal structure of \typ{CcuList}s} \hfil \end{figure} ?*/ #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 (size_t); 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 (size_t) #else CcuList::CcuListLink :: operator new (size_t) #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. !*/ /*?hidden?*/ #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; } #ifdef DOC /*? Get the status flag of a list. This can be one of \var{CcuList::NoError, CcuList::WasEmpty, CcuList::TooEarly, CcuList::TooFar} or \var{CcuList::BadIterator}. The status flag is modified by most operations on lists. Those which modify it when errors are encountered also set it to \var{CcuList::NoError} when there is no error. ?*/ list_status CcuList :: GetStatus () const { } #endif /* DOC */ /*?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}: the status flag is set to \var{CcuList::WasEmpty} in the latter case. ?*/ 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{CcuList::TooFar}. If \var{n} is negative, this function returns 0 but sets the status to \var{CcuList::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. If \var{rank} is not null, it is filled with the rank of the first occurence of \var{e} in the list. ?*/ int CcuList :: Find (CcuListItem* e, int* rank) const { int rk = 0; int ret = 0; CcuListIter li (*this); while (++rk, ++li) if (*li == e) { ret = 1; break; } if (rank) *rank = ret ? rk : 0; return ret; } /*?nextdoc?*/ CcuListIndex 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); return LastLink; } /*? Add an element at the beginning (resp. end) of a list. ?*/ CcuListIndex CcuList :: Append (CcuListItem* e) { if (LastLink) { LastLink = LastLink->Next = new CcuListLink (e, LastLink->Next); } else LastLink = new CcuListLink (e); return LastLink; } /*? Remove the first element of a list and return it. The status flag is set to \var{CcuList::WasEmpty} when the list was empty. ?*/ 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. The status flag is set to \var{CcuList::WasEmpty} when the list was empty. 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. !*/ /*?hidden?*/ CcuListIndex CcuList :: InsertBeforeLink (CcuListLink* l, CcuListItem* e) { CcuListLink* prev = l->Previous (); CcuListLink* newlink = new CcuListLink (e, l); prev->Next = newlink; return newlink; } /*! Insert an element after the link \var{l}. !*/ /*?hidden?*/ CcuListIndex CcuList :: InsertAfterLink (CcuListLink* l, CcuListItem* e) { CcuListLink* newlink = new CcuListLink (e, l->Next); l->Next = newlink; if (LastLink == l) LastLink = newlink; return 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. !*/ /*?hidden?*/ 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?*/ CcuListIndex CcuList :: InsertAfter (const CcuListIter& li, CcuListItem* e) { if (li.TheList != this) { StatusFlag = BadIterator; return 0; } StatusFlag = NoError; CcuListIndex idx = 0; if (!li.CurLink) { if (li.StatusFlag == CcuListIter::StartOfList) { idx = Prepend (e); } else { fprintf (stderr, "abnormal status in CcuList::InsertAfter\n"); abort (); } } else if (li.StatusFlag == CcuListIter::EndOfList) { idx = Append (e); } else { idx = InsertAfterLink (li.CurLink, e); } return idx; } /*? 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. If \var{li} is not an iterator on this list, the status flag of the list is set to \var{CcuList::BadIterator}. ?*/ CcuListIndex CcuList :: InsertBefore (const CcuListIter& li, CcuListItem* e) { if (li.TheList != this) { StatusFlag = BadIterator; return 0; } StatusFlag = NoError; CcuListIndex idx = 0; if (!li.CurLink) { if (li.StatusFlag == CcuListIter::StartOfList) { idx = Prepend (e); } else { fprintf (stderr, "abnormal status in CcuList::InsertAfter\n"); abort (); } } else if (li.StatusFlag == CcuListIter::EndOfList) { idx = Append (e); } else { idx = InsertBeforeLink (li.CurLink, e); } return idx; } /*? 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 removed. If \var{li} points at the last element, the status flag is set to \var{CcuList::TooFar}. If the list is empty, the flag is set to \var{CcuList::EmptyList}. In both cases, the return value is null. If \var{li} is not an iterator on this list, the flag is set to \var{CcuList::BadIterator}. This function may be used when one wants to iterate through a list and remove some elements: \begin{ccode} CcuListIter li = l; CcuListIter lj = l; while (++li) if (do_remove (*li)) { l.RemoveAfter (lj); li = lj; } else { ++lj; } \end{ccode} ?*/ 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 /*?class CcuListIter The class \typ{CcuListIter} allows iterations on lists. Several iterators may be used at a time on the same list. It is dangerous to modify a list that is being iterated. Refer to the implementation figure for more details. Of course, the functions such as \var{InsertAfter} or \var{RemoveAfter} are designed to be harmless. However, they may be dangerous if another iterator is used at the same time on the same list. The basic usage of an iterator is the following: \begin{ccode} extern CcuList& l; CcuListIter li = l; while (++li) foo (*li); // *li is the value that was stored with Append \end{ccode} ?*/ /*? 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 (const CcuList& l) { } #endif /* DOC */ /*? Build an iterator on list \var{l}, pointing at the element denoted by \var{idx}. No check is done on whether \var{idx} is a valid index of list \var{l}. ?*/ CcuListIter :: CcuListIter (const CcuList& l, CcuListIndex idx) : TheList (&l), #ifdef CPLUS_BUG20 CurLink ((CcuListLink*) idx), #else CurLink ((CcuList::CcuListLink*) idx), #endif StatusFlag (idx ? Normal : StartOfList) { } #ifdef DOC /*? Get the status of an iterator. The status may be one of \var{CcuListIter::Normal, CcuListIter::StartOfList}, or \var{CcuListIter::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{CcuListIter::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 placeholder: it does the same thing as the previous one. ?*/ 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 & li, ITEM*it) { } /*?nextdoc?*/ void CcuListOf :: InsertBefore (const CcuListIterOf & 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*}. ?*/ ITEM* CcuListOf :: RemoveAfter (const CcuListIterOf & li) { } /*?nextdoc?*/ CcuListIterOf :: CcuListIterOf (const CcuListOf & 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 */