diff options
Diffstat (limited to 'utils/DList.cc')
| -rw-r--r-- | utils/DList.cc | 247 |
1 files changed, 117 insertions, 130 deletions
diff --git a/utils/DList.cc b/utils/DList.cc index 9ccae7b..889087c 100644 --- a/utils/DList.cc +++ b/utils/DList.cc @@ -17,51 +17,50 @@ #include <stdlib.h> #include <stdio.h> -/*?class CcuDList +/*?class IvlDList \begin{figure}[hbtp] \hfil -\psfig{figure=FIGURES/CcuDList.epsf}\par \caption{Internal structure of \typ{CcuDList}s} +\psfig{figure=FIGURES/IvlDList.epsf}\par \caption{Internal structure of \typ{IvlDList}s} \hfil \end{figure} ?*/ #ifdef CPLUS_BUG20 -class CcuDListLink { -static CcuAllocator* DListLinkMem; +class IvlDListLink { +static IvlAllocator* 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) {} + IvlDListItem* Entry; + IvlDListLink* Previous; + IvlDListLink* Next; +inline IvlDListLink (IvlDListItem* e, IvlDListLink* p) : Entry (e), Previous (p), Next (p->Next) { Previous->Next = Next->Previous = this; } +inline IvlDListLink (IvlDListItem* e) : Entry (e), Previous (this), Next (this) {} void* operator new (size_t); void operator delete (void*); }; #endif - #ifdef CPLUS_BUG20 -CcuAllocator* CcuDListLink::DListLinkMem = 0; +IvlAllocator* IvlDListLink::DListLinkMem = 0; #else -CcuAllocator* CcuDList::CcuDListLink::DListLinkMem = 0; +IvlAllocator* IvlDList::IvlDListLink::DListLinkMem = 0; #endif /*?nodoc?*/ void* #ifdef CPLUS_BUG20 -CcuDListLink :: operator new (size_t) +IvlDListLink :: operator new (size_t) #else -CcuDList::CcuDListLink :: operator new (size_t) +IvlDList::IvlDListLink :: operator new (size_t) #endif { if (!DListLinkMem) #ifdef CPLUS_BUG20 - DListLinkMem = new CcuAllocator (sizeof (CcuDListLink)); + DListLinkMem = new IvlAllocator (sizeof (IvlDListLink)); #else - DListLinkMem = new CcuAllocator (sizeof (CcuDList::CcuDListLink)); + DListLinkMem = new IvlAllocator (sizeof (IvlDList::IvlDListLink)); #endif return DListLinkMem->Alloc (); } @@ -69,21 +68,19 @@ CcuDList::CcuDListLink :: operator new (size_t) /*?nodoc?*/ void #ifdef CPLUS_BUG20 -CcuDListLink :: operator delete (void* that) +IvlDListLink :: operator delete (void* that) #else -CcuDList::CcuDListLink :: operator delete (void* that) +IvlDList::IvlDListLink :: operator delete (void* that) #endif { DListLinkMem->Free (that); } - - #ifdef DOC /*? Create an empty list. ?*/ -CcuDList :: CcuDList () +IvlDList :: IvlDList () { } #endif @@ -91,27 +88,26 @@ CcuDList :: CcuDList () /*? Create a list with one element \var{e}. ?*/ -CcuDList :: CcuDList (CcuDListItem* e) -: LastLink (new CcuDListLink (e)), +IvlDList :: IvlDList (IvlDListItem* e) +: LastLink (new IvlDListLink (e)), StatusFlag (NoError) { } /*?nodoc?*/ -CcuDList :: CcuDList (const CcuDList& l) +IvlDList :: IvlDList (const IvlDList& l) : LastLink (0), StatusFlag (NoError) { - CcuDListIter li (l); + IvlDListIter li (l); while (++li) Append (*li); } - /*? Destructor for lists. No operation is performed on the elements. ?*/ -CcuDList :: ~CcuDList () +IvlDList :: ~IvlDList () { Clear (); } @@ -120,11 +116,11 @@ CcuDList :: ~CcuDList () Empty a list. ?*/ void -CcuDList :: Clear () +IvlDList :: Clear () { - CcuDListLink* del = LastLink; + IvlDListLink* del = LastLink; while (del) { - CcuDListLink* next = del->Next; + IvlDListLink* next = del->Next; if (next == LastLink) next = 0; delete del; @@ -134,22 +130,21 @@ CcuDList :: Clear () } /*?nodoc?*/ -CcuDList& -CcuDList :: operator = (const CcuDList& l) +IvlDList& +IvlDList :: operator = (const IvlDList& l) { if (this != &l) { Clear (); - CcuDListIter li (l); + IvlDListIter li (l); while (++li) Append (*li); } return *this; } - /*?nextdoc?*/ -CcuDListItem* -CcuDList :: First () +IvlDListItem* +IvlDList :: First () { if (!LastLink) { StatusFlag = WasEmpty; @@ -164,8 +159,8 @@ 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 () +IvlDListItem* +IvlDList :: Last () { if (!LastLink) { StatusFlag = WasEmpty; @@ -180,13 +175,13 @@ Get the \var{n}-th element of a list. If \var{n} is greater than the length of t 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) +IvlDListItem* +IvlDList :: Nth (int n) { StatusFlag = NoError; if (n <= 0) return 0; - CcuDListIter li (*this); + IvlDListIter li (*this); while (n > 0 && ++li) --n; if (n != 0) @@ -198,10 +193,10 @@ CcuDList :: Nth (int n) Compute the number of elements in a list. ?*/ int -CcuDList :: Length () const +IvlDList :: Length () const { int result = 0; - CcuDListIter li (*this); + IvlDListIter li (*this); while (++li) ++result; return result; @@ -211,9 +206,9 @@ CcuDList :: Length () const Check whether an item is present in a list. ?*/ int -CcuDList :: Find (CcuDListItem* e) const +IvlDList :: Find (IvlDListItem* e) const { - CcuDListIter li (*this); + IvlDListIter li (*this); while (++li) if (*li == e) return 1; @@ -222,31 +217,31 @@ CcuDList :: Find (CcuDListItem* e) const /*?nextdoc?*/ void -CcuDList :: Prepend (CcuDListItem* e) +IvlDList :: Prepend (IvlDListItem* e) { if (LastLink) - new CcuDListLink (e, LastLink); + new IvlDListLink (e, LastLink); else - LastLink = new CcuDListLink (e); + LastLink = new IvlDListLink (e); } /*? Add an element at the beginning (resp. end) of a list. ?*/ void -CcuDList :: Append (CcuDListItem* e) +IvlDList :: Append (IvlDListItem* e) { if (LastLink) { - LastLink = new CcuDListLink (e, LastLink); + LastLink = new IvlDListLink (e, LastLink); } else - LastLink = new CcuDListLink (e); + LastLink = new IvlDListLink (e); } /*? Remove the first element of a list and return it. ?*/ -CcuDListItem* -CcuDList :: RemoveFirst () +IvlDListItem* +IvlDList :: RemoveFirst () { /* Handle the case when the list is empty */ if (!LastLink) { @@ -258,13 +253,11 @@ CcuDList :: RemoveFirst () return RemoveLink (LastLink->Next); } - - /*? Remove the last element of a list and return it. ?*/ -CcuDListItem* -CcuDList :: RemoveLast () +IvlDListItem* +IvlDList :: RemoveLast () { /* Handle the case when the list is empty */ if (!LastLink) { @@ -276,14 +269,13 @@ CcuDList :: RemoveLast () return RemoveLink (LastLink); } - /*? Insert an element after the link \var{l}. ?*/ void -CcuDList :: InsertAfterLink (CcuDListLink* l, CcuDListItem* e) +IvlDList :: InsertAfterLink (IvlDListLink* l, IvlDListItem* e) { - CcuDListLink* newlink = new CcuDListLink (e, l); + IvlDListLink* newlink = new IvlDListLink (e, l); if (LastLink == l) LastLink = newlink; } @@ -291,11 +283,11 @@ CcuDList :: InsertAfterLink (CcuDListLink* l, CcuDListItem* e) /*? Remove a link. ?*/ -CcuDListItem* -CcuDList :: RemoveLink (CcuDListLink* l) +IvlDListItem* +IvlDList :: RemoveLink (IvlDListLink* l) { /* store its data */ - CcuDListItem* data = l->Entry; + IvlDListItem* data = l->Entry; if (l->Next == l) LastLink = 0; else { @@ -310,17 +302,16 @@ CcuDList :: RemoveLink (CcuDListLink* l) 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) +IvlDList :: Remove (IvlDListItem* entry, int num) { int removed = 0; - CcuDListIter li (*this); + IvlDListIter li (*this); while ((num < 0 || removed < num) && ++li) { if (*li == entry) { RemoveLink (li.CurLink); @@ -338,10 +329,10 @@ 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) +IvlDList :: Remove (int (*p) (IvlDListItem*), int num) { int removed = 0; - CcuDListIter li (*this); + IvlDListIter li (*this); while ((num < 0 || removed < num) && ++li) { if ((*p) (*li)) { RemoveAt (li); @@ -353,20 +344,20 @@ CcuDList :: Remove (int (*p) (CcuDListItem*), int num) /*?nextdoc?*/ void -CcuDList :: InsertAfter (const CcuDListIter& li, CcuDListItem* e) +IvlDList :: InsertAfter (const IvlDListIter& li, IvlDListItem* e) { if (li.TheList != this) { StatusFlag = BadIterator; return; } if (!li.CurLink) { - if (li.StatusFlag == CcuDListIter::StartOfList) { + if (li.StatusFlag == IvlDListIter::StartOfList) { Prepend (e); } else { - fprintf (stderr, "abnormal status in CcuDList::InsertAfter\n"); + fprintf (stderr, "abnormal status in IvlDList::InsertAfter\n"); abort (); } - } else if (li.StatusFlag == CcuDListIter::EndOfList) { + } else if (li.StatusFlag == IvlDListIter::EndOfList) { Append (e); } else { InsertAfterLink (li.CurLink, e); @@ -375,28 +366,28 @@ CcuDList :: InsertAfter (const CcuDListIter& li, CcuDListItem* 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 +These functions are both equivalent to \fun{IvlDList::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) +IvlDList :: InsertBefore (const IvlDListIter& li, IvlDListItem* e) { if (li.TheList != this) { StatusFlag = BadIterator; return; } if (!li.CurLink) { - if (li.StatusFlag == CcuDListIter::StartOfList) { + if (li.StatusFlag == IvlDListIter::StartOfList) { Prepend (e); } else { - fprintf (stderr, "abnormal status in CcuDList::InsertAfter\n"); + fprintf (stderr, "abnormal status in IvlDList::InsertAfter\n"); abort (); } - } else if (li.StatusFlag == CcuDListIter::EndOfList) { + } else if (li.StatusFlag == IvlDListIter::EndOfList) { Append (e); } else { - new CcuDListLink (e, li.CurLink->Previous); + new IvlDListLink (e, li.CurLink->Previous); } } @@ -407,8 +398,8 @@ 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) +IvlDListItem* +IvlDList :: RemoveAfter (const IvlDListIter& li) { if (li.TheList != this) { StatusFlag = BadIterator; @@ -433,14 +424,14 @@ 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: \begin{ccode} - CcuDListIter li (l); + IvlDListIter li (l); while (++li) if (do_remove (*li)) l.RemoveAt (l); \end{ccode} ?*/ -CcuDListItem* -CcuDList :: RemoveAt (CcuDListIter& li) +IvlDListItem* +IvlDList :: RemoveAt (IvlDListIter& li) { if (li.TheList != this) { StatusFlag = BadIterator; @@ -450,20 +441,19 @@ CcuDList :: RemoveAt (CcuDListIter& li) StatusFlag = TooEarly; return 0; } - if (li.StatusFlag == CcuDListIter::EndOfList) { + if (li.StatusFlag == IvlDListIter::EndOfList) { StatusFlag = TooFar; return 0; } StatusFlag = NoError; - CcuDListLink* del = li.CurLink; + IvlDListLink* del = li.CurLink; --li; return RemoveLink (del); } - #ifdef DOC -/*?class CcuDListIter -The class \typ{CcuDListIter} allows iterations on lists. +/*?class IvlDListIter +The class \typ{IvlDListIter} 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. ?*/ @@ -472,7 +462,7 @@ a list that is being iterated. 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 (const CcuDList& l) +IvlDListIter :: IvlDListIter (const IvlDList& l) { } @@ -481,13 +471,13 @@ Get the status of an iterator. The status may be one of \var{Normal, StartOfList \var{EndOfList} ?*/ dlistiter_status -CcuDListIter :: GetStatus () const +IvlDListIter :: GetStatus () const { } /*?nextdoc?*/ void -CcuDListIter :: Reset () +IvlDListIter :: Reset () { } @@ -495,19 +485,18 @@ CcuDListIter :: Reset () Reset an iterator to the beginning (resp. the end) of the list. ?*/ void -CcuDListIter :: GotoEnd () +IvlDListIter :: GotoEnd () { } #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}. ?*/ -CcuDListItem* -CcuDListIter :: operator * () const +IvlDListItem* +IvlDListIter :: operator * () const { return (CurLink && StatusFlag == Normal) ? CurLink->Entry : 0; } @@ -517,17 +506,16 @@ CcuDListIter :: operator * () const /*? Check whether the status of an iterator is \var{Normal}. ?*/ -CcuDListIter :: operator int () const +IvlDListIter :: operator int () const { } #endif - /*? Take one step of iteration. ?*/ -CcuDListIter& -CcuDListIter :: operator ++ () +IvlDListIter& +IvlDListIter :: operator ++ () { /* This test covers all the cases : - the iteration has already begun, and is at its end. @@ -545,8 +533,8 @@ CcuDListIter :: operator ++ () /*? Rewind iteration by one step. ?*/ -CcuDListIter& -CcuDListIter :: operator -- () +IvlDListIter& +IvlDListIter :: operator -- () { if (StatusFlag == Normal) { CurLink = CurLink->Previous; @@ -565,7 +553,7 @@ 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) +IvlDListIter :: Find (IvlDListItem* e) { while (++(*this)) if (**this == e) @@ -580,7 +568,7 @@ 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) +IvlDListIter :: FindBack (IvlDListItem* e) { while (--(*this)) if (**this == e) @@ -590,137 +578,136 @@ CcuDListIter :: FindBack (CcuDListItem* e) #ifdef DOC -/*?class CcuDListOf -The generic classes \typ{CcuDListOf} and \typ{CcuDListIterOf} are derived classes -of \typ{CcuDList} and \typ{CcuDListIter} that provide lists of pointers to class objects. +/*?class IvlDListOf +The generic classes \typ{IvlDListOf} and \typ{IvlDListIterOf} are derived classes +of \typ{IvlDList} and \typ{IvlDListIter} that provide lists of pointers to class objects. When parameterized by the class \typ{ITEM}, the following functions are redefined: ?*/ /*?nextdoc?*/ -CcuDListOf :: CcuDListOf (ITEM* it) +IvlDListOf :: IvlDListOf (ITEM* it) { } /*?nextdoc?*/ ITEM* -CcuDListOf :: First () +IvlDListOf :: First () { } /*?nextdoc?*/ ITEM* -CcuDListOf :: Last () +IvlDListOf :: Last () { } /*?nextdoc?*/ ITEM* -CcuDListOf :: Nth (int n) +IvlDListOf :: Nth (int n) { } /*?nextdoc?*/ int -CcuDListOf :: Find (ITEM* it) const +IvlDListOf :: Find (ITEM* it) const { } /*?nextdoc?*/ void -CcuDListOf :: Append (ITEM* it) +IvlDListOf :: Append (ITEM* it) { } /*?nextdoc?*/ void -CcuDListOf :: Prepend (ITEM* it) +IvlDListOf :: Prepend (ITEM* it) { } /*?nextdoc?*/ -CcuDListOf& -CcuDListOf :: operator << (ITEM* it) +IvlDListOf& +IvlDListOf :: operator << (ITEM* it) { } /*?nextdoc?*/ ITEM* -CcuDListOf :: RemoveFirst () +IvlDListOf :: RemoveFirst () { } /*?nextdoc?*/ ITEM* -CcuDListOf :: RemoveLast () +IvlDListOf :: RemoveLast () { } /*?nextdoc?*/ int -CcuDListOf :: Remove (ITEM* it, int nb = 1) +IvlDListOf :: Remove (ITEM* it, int nb = 1) { } /*?nextdoc?*/ int -CcuDListOf :: Remove (int (*p) (ITEM*), int nb = 1) +IvlDListOf :: Remove (int (*p) (ITEM*), int nb = 1) { } /*?nextdoc?*/ void -CcuDListOf :: InsertAfter (const CcuDListIterOf <ITEM>& li, ITEM*it) +IvlDListOf :: InsertAfter (const IvlDListIterOf <ITEM>& li, ITEM*it) { } /*?nextdoc?*/ void -CcuDListOf :: InsertBefore (const CcuDListIterOf <ITEM>& li, ITEM* it) +IvlDListOf :: InsertBefore (const IvlDListIterOf <ITEM>& li, ITEM* it) { } /*?nextdoc?*/ ITEM* -CcuDListOf :: RemoveAfter (const CcuDListIterOf <ITEM>& li) +IvlDListOf :: RemoveAfter (const IvlDListIterOf <ITEM>& li) { } /*? -These functions are equivalent to their homonyms in the class \typ{CcuDList}, +These functions are equivalent to their homonyms in the class \typ{IvlDList}, except that they are customized in order to manipulate pointers to \typ{ITEM} instead of \typ{void*}. ?*/ ITEM* -CcuDListOf :: RemoveAt (CcuDListIterOf <ITEM>& li) +IvlDListOf :: RemoveAt (IvlDListIterOf <ITEM>& li) { } /*?nextdoc?*/ -CcuDListIterOf :: CcuDListIterOf (const CcuDListOf <ITEM>& l) +IvlDListIterOf :: IvlDListIterOf (const IvlDListOf <ITEM>& l) { } /*?nextdoc?*/ ITEM* -CcuDListIterOf :: operator * () const +IvlDListIterOf :: operator * () const { } /*?nextdoc?*/ int -CcuDListIterOf :: Find (ITEM* it) +IvlDListIterOf :: Find (ITEM* it) { } /*? -These functions are equivalent to their homonyms in the class \typ{CcuDListIter}, +These functions are equivalent to their homonyms in the class \typ{IvlDListIter}, except that they are customized in order to manipulate pointers to \typ{ITEM} instead of \typ{void*}. ?*/ int -CcuDListIterOf :: FindBack (ITEM* it) +IvlDListIterOf :: FindBack (ITEM* it) { } - #endif /* DOC */ |