diff options
Diffstat (limited to 'utils/Chain.cc')
| -rw-r--r-- | utils/Chain.cc | 123 |
1 files changed, 58 insertions, 65 deletions
diff --git a/utils/Chain.cc b/utils/Chain.cc index e9cd14f..badc7fc 100644 --- a/utils/Chain.cc +++ b/utils/Chain.cc @@ -14,15 +14,15 @@ #include <stdlib.h> #include <stdio.h> -CcuChain :: ~CcuChain () +IvlChain :: ~IvlChain () { } -CcuChainItem* -CcuChain :: GetPrevious (CcuChainItem* i) +IvlChainItem* +IvlChain :: GetPrevious (IvlChainItem* i) { - register CcuChainItem* c = LastLink; - register CcuChainItem* n; + register IvlChainItem* c = LastLink; + register IvlChainItem* n; while ((n = GetNext (c)) != i) c = n; return c; @@ -32,11 +32,11 @@ CcuChain :: GetPrevious (CcuChainItem* i) Empty a list. ?*/ void -CcuChain :: Clear () +IvlChain :: Clear () { - CcuChainItem* del = LastLink; + IvlChainItem* del = LastLink; while (del) { - CcuChainItem* next = GetNext (del); + IvlChainItem* next = GetNext (del); if (next == LastLink) next = 0; Delete (del); @@ -45,10 +45,9 @@ CcuChain :: Clear () LastLink = 0; } - /*?nextdoc?*/ -CcuChainItem* -CcuChain :: First () +IvlChainItem* +IvlChain :: First () { if (!LastLink) { StatusFlag = WasEmpty; @@ -63,8 +62,8 @@ Return the first/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}. ?*/ -CcuChainItem* -CcuChain :: Last () +IvlChainItem* +IvlChain :: Last () { if (!LastLink) { StatusFlag = WasEmpty; @@ -79,13 +78,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}. ?*/ -CcuChainItem* -CcuChain :: Nth (int n) +IvlChainItem* +IvlChain :: Nth (int n) { StatusFlag = NoError; if (n <= 0) return 0; - CcuChainIter li (*this); + IvlChainIter li (*this); while (n > 0 && ++li) --n; if (n != 0) @@ -97,10 +96,10 @@ CcuChain :: Nth (int n) Compute the number of elements in a list. ?*/ int -CcuChain :: Length () const +IvlChain :: Length () const { int result = 0; - CcuChainIter li (*this); + IvlChainIter li (*this); while (++li) ++result; return result; @@ -110,9 +109,9 @@ CcuChain :: Length () const Check whether an item is present in a list. ?*/ int -CcuChain :: Find (CcuChainItem* e) const +IvlChain :: Find (IvlChainItem* e) const { - CcuChainIter li (*this); + IvlChainIter li (*this); while (++li) if (*li == e) return 1; @@ -121,7 +120,7 @@ CcuChain :: Find (CcuChainItem* e) const /*?nextdoc?*/ void -CcuChain :: Prepend (CcuChainItem* e) +IvlChain :: Prepend (IvlChainItem* e) { if (LastLink) { /* remember that LastLink->Next is the first */ @@ -137,7 +136,7 @@ CcuChain :: Prepend (CcuChainItem* e) Insert an element at the beginning/end of a list. ?*/ void -CcuChain :: Append (CcuChainItem* e) +IvlChain :: Append (IvlChainItem* e) { if (LastLink) { SetNext (e, GetNext (LastLink)); @@ -152,8 +151,8 @@ CcuChain :: Append (CcuChainItem* e) /*? Remove the first element of a list and return it. ?*/ -CcuChainItem* -CcuChain :: RemoveFirst () +IvlChainItem* +IvlChain :: RemoveFirst () { /* Handle the case when the list is empty */ if (!LastLink) { @@ -163,7 +162,7 @@ CcuChain :: RemoveFirst () StatusFlag = NoError; /* Get the first element */ - CcuChainItem* first = GetNext (LastLink); + IvlChainItem* first = GetNext (LastLink); /* Remove it from the chain */ if (LastLink == first) @@ -173,13 +172,12 @@ CcuChain :: RemoveFirst () return first; } - /*? Remove the last element of a list and return it. This function has to locate the last element, and hence has a linear cost. ?*/ -CcuChainItem* -CcuChain :: RemoveLast () +IvlChainItem* +IvlChain :: RemoveLast () { /* Handle the case when the list is empty */ if (!LastLink) { @@ -189,10 +187,10 @@ CcuChain :: RemoveLast () StatusFlag = NoError; /* Find the element that will be the new LastLink */ - register CcuChainItem* newlast = GetPrevious (LastLink); + register IvlChainItem* newlast = GetPrevious (LastLink); /* Save the element to be deleted and its data */ - CcuChainItem* last = LastLink; + IvlChainItem* last = LastLink; /* Remove it from the chain */ if (newlast == LastLink) LastLink = 0; @@ -207,19 +205,18 @@ CcuChain :: RemoveLast () Insert an element before the link \var{l}. This function has a linear cost. ?*/ void -CcuChain :: InsertBefore (CcuChainItem* l, CcuChainItem* e) +IvlChain :: InsertBefore (IvlChainItem* l, IvlChainItem* e) { - CcuChainItem* prev = GetPrevious (l); + IvlChainItem* prev = GetPrevious (l); SetNext (prev, e); SetNext (e, l); } - /*? Insert an element after the link \var{l}. ?*/ void -CcuChain :: InsertAfter (CcuChainItem* l, CcuChainItem* e) +IvlChain :: InsertAfter (IvlChainItem* l, IvlChainItem* e) { SetNext (e, GetNext (l)); SetNext (l, e); @@ -231,10 +228,10 @@ CcuChain :: InsertAfter (CcuChainItem* l, CcuChainItem* e) 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. ?*/ -CcuChainItem* -CcuChain :: RemoveAfter (CcuChainItem* l) +IvlChainItem* +IvlChain :: RemoveAfter (IvlChainItem* l) { - CcuChainItem* del = GetNext (l); + IvlChainItem* del = GetNext (l); if (del == l) { LastLink = 0; } else { @@ -251,11 +248,11 @@ Remove an element from a list. This function iterates through the list until it If \var{num} is \var{All} or is negative, all appearances of \var{entry} are deleted. ?*/ int -CcuChain :: Remove (CcuChainItem* entry) +IvlChain :: Remove (IvlChainItem* entry) { int removed = 0; - CcuChainIter li (*this); - CcuChainIter lj (*this); + IvlChainIter li (*this); + IvlChainIter lj (*this); while (++li) { if (*li == entry) { RemoveAfter (lj); @@ -273,11 +270,11 @@ The actual number of removals is returned. If \var{num} is \var{All} or is negative, all matching elements are deleted. ?*/ int -CcuChain :: Remove (int (*p) (CcuChainItem*)) +IvlChain :: Remove (int (*p) (IvlChainItem*)) { int removed = 0; - CcuChainIter li (*this); - CcuChainIter lj (*this); + IvlChainIter li (*this); + IvlChainIter lj (*this); while (++li) { if ((*p) (*li)) { RemoveAfter (lj); @@ -288,10 +285,9 @@ CcuChain :: Remove (int (*p) (CcuChainItem*)) return 0; } - /*?nextdoc?*/ void -CcuChain :: InsertAfter (const CcuChainIter& li, CcuChainItem* e) +IvlChain :: InsertAfter (const IvlChainIter& li, IvlChainItem* e) { if (li.TheChain != this) { StatusFlag = BadIterator; @@ -299,13 +295,13 @@ CcuChain :: InsertAfter (const CcuChainIter& li, CcuChainItem* e) } StatusFlag = NoError; if (!li.CurLink) { - if (li.StatusFlag == CcuChainIter::StartOfChain) { + if (li.StatusFlag == IvlChainIter::StartOfChain) { Prepend (e); } else { - fprintf (stderr, "abnormal status in CcuChain::InsertAfter\n"); + fprintf (stderr, "abnormal status in IvlChain::InsertAfter\n"); abort (); } - } else if (li.StatusFlag == CcuChainIter::EndOfChain) { + } else if (li.StatusFlag == IvlChainIter::EndOfChain) { Append (e); } else { InsertAfter (li.CurLink, e); @@ -314,13 +310,13 @@ CcuChain :: InsertAfter (const CcuChainIter& li, CcuChainItem* e) /*? Insert an element before (resp. after) the current position of the iterator \var{li}. -These functions are both equivalent to \fun{CcuChain::Prepend} if the iterator is at the +These functions are both equivalent to \fun{IvlChain::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 -CcuChain :: InsertBefore (const CcuChainIter& li, CcuChainItem* e) +IvlChain :: InsertBefore (const IvlChainIter& li, IvlChainItem* e) { if (li.TheChain != this) { StatusFlag = BadIterator; @@ -328,13 +324,13 @@ CcuChain :: InsertBefore (const CcuChainIter& li, CcuChainItem* e) } StatusFlag = NoError; if (!li.CurLink) { - if (li.StatusFlag == CcuChainIter::StartOfChain) { + if (li.StatusFlag == IvlChainIter::StartOfChain) { Prepend (e); } else { - fprintf (stderr, "abnormal status in CcuChain::InsertBefore\n"); + fprintf (stderr, "abnormal status in IvlChain::InsertBefore\n"); abort (); } - } else if (li.StatusFlag == CcuChainIter::EndOfChain) { + } else if (li.StatusFlag == IvlChainIter::EndOfChain) { Append (e); } else { InsertBefore (li.CurLink, e); @@ -349,8 +345,8 @@ If the list is empty, the flag is set to \var{EmptyChain}. 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: - CcuChainIter li (l); - CcuChainIter lj (l); + IvlChainIter li (l); + IvlChainIter lj (l); while (++li) if (do_remove (*li)) { RemoveAfter (lj); @@ -358,8 +354,8 @@ when one wants to iterate through a list and remove some elements: } else ++lj; ?*/ -CcuChainItem* -CcuChain :: RemoveAfter (const CcuChainIter& li) +IvlChainItem* +IvlChain :: RemoveAfter (const IvlChainIter& li) { if (li.TheChain != this) { StatusFlag = BadIterator; @@ -377,24 +373,22 @@ CcuChain :: RemoveAfter (const CcuChainIter& li) } } - /*? 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}. ?*/ -CcuChainItem* -CcuChainIter :: operator * () const +IvlChainItem* +IvlChainIter :: operator * () const { return (CurLink && StatusFlag == Normal) ? CurLink : 0; } - /*? Take one step of iteration. ?*/ -CcuChainIter& -CcuChainIter :: operator ++ () +IvlChainIter& +IvlChainIter :: operator ++ () { /* This test covers all the cases : - the iteration has already begun, and is at its end. @@ -409,7 +403,6 @@ CcuChainIter :: operator ++ () return *this; } - /*? Try and find the element \var{e} in the list, starting from the current position of the iterator (this position not included). @@ -417,7 +410,7 @@ If \var{e} is present, the iterator will be correctly positionned. If not, it will have reached the end of the list. ?*/ int -CcuChainIter :: Find (CcuChainItem* e) +IvlChainIter :: Find (IvlChainItem* e) { while (++(*this)) if (**this == e) |