From 3a4838bed13b767132cbdf06364b2658da6cc356 Mon Sep 17 00:00:00 2001 From: chatty Date: Tue, 15 Dec 1992 10:55:33 +0000 Subject: Initial revision --- utils/Chain.cc | 426 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 426 insertions(+) create mode 100644 utils/Chain.cc (limited to 'utils/Chain.cc') diff --git a/utils/Chain.cc b/utils/Chain.cc new file mode 100644 index 0000000..e9cd14f --- /dev/null +++ b/utils/Chain.cc @@ -0,0 +1,426 @@ +/* + * CENA C++ Utilities + * + * Copyright 1992 + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * generic chains of objects - to be updated + * + * $Id$ + * $CurLog$ + */ + +#include "Chain.h" +#include +#include + +CcuChain :: ~CcuChain () +{ +} + +CcuChainItem* +CcuChain :: GetPrevious (CcuChainItem* i) +{ + register CcuChainItem* c = LastLink; + register CcuChainItem* n; + while ((n = GetNext (c)) != i) + c = n; + return c; +} + +/*? +Empty a list. +?*/ +void +CcuChain :: Clear () +{ + CcuChainItem* del = LastLink; + while (del) { + CcuChainItem* next = GetNext (del); + if (next == LastLink) + next = 0; + Delete (del); + del = next; + } + LastLink = 0; +} + + +/*?nextdoc?*/ +CcuChainItem* +CcuChain :: First () +{ + if (!LastLink) { + StatusFlag = WasEmpty; + return 0; + } + StatusFlag = NoError; + return GetNext (LastLink); +} + +/*? +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 () +{ + if (!LastLink) { + StatusFlag = WasEmpty; + return 0; + } + StatusFlag = NoError; + return LastLink; +} + +/*? +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}. +?*/ +CcuChainItem* +CcuChain :: Nth (int n) +{ + StatusFlag = NoError; + if (n <= 0) + return 0; + CcuChainIter li (*this); + while (n > 0 && ++li) + --n; + if (n != 0) + StatusFlag = TooFar; + return *li; +} + +/*? +Compute the number of elements in a list. +?*/ +int +CcuChain :: Length () const +{ + int result = 0; + CcuChainIter li (*this); + while (++li) + ++result; + return result; +} + +/*? +Check whether an item is present in a list. +?*/ +int +CcuChain :: Find (CcuChainItem* e) const +{ + CcuChainIter li (*this); + while (++li) + if (*li == e) + return 1; + return 0; +} + +/*?nextdoc?*/ +void +CcuChain :: Prepend (CcuChainItem* e) +{ + if (LastLink) { + /* remember that LastLink->Next is the first */ + SetNext (e, GetNext (LastLink)); + SetNext (LastLink, e); + } else { + LastLink = e; + SetNext (e, e); + } +} + +/*? +Insert an element at the beginning/end of a list. +?*/ +void +CcuChain :: Append (CcuChainItem* e) +{ + if (LastLink) { + SetNext (e, GetNext (LastLink)); + SetNext (LastLink, e); + LastLink = e; + } else { + LastLink = e; + SetNext (e, e); + } +} + +/*? +Remove the first element of a list and return it. +?*/ +CcuChainItem* +CcuChain :: RemoveFirst () +{ + /* Handle the case when the list is empty */ + if (!LastLink) { + StatusFlag = WasEmpty; + return 0; + } + StatusFlag = NoError; + + /* Get the first element */ + CcuChainItem* first = GetNext (LastLink); + + /* Remove it from the chain */ + if (LastLink == first) + LastLink = 0; + else + SetNext (LastLink, GetNext (first)); + 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 () +{ + /* 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 CcuChainItem* newlast = GetPrevious (LastLink); + + /* Save the element to be deleted and its data */ + CcuChainItem* last = LastLink; + /* Remove it from the chain */ + if (newlast == LastLink) + LastLink = 0; + else { + SetNext (newlast, GetNext (LastLink)); + LastLink = newlast; + } + return last; +} + +/*? +Insert an element before the link \var{l}. This function has a linear cost. +?*/ +void +CcuChain :: InsertBefore (CcuChainItem* l, CcuChainItem* e) +{ + CcuChainItem* prev = GetPrevious (l); + SetNext (prev, e); + SetNext (e, l); +} + + +/*? +Insert an element after the link \var{l}. +?*/ +void +CcuChain :: InsertAfter (CcuChainItem* l, CcuChainItem* e) +{ + SetNext (e, GetNext (l)); + SetNext (l, e); + if (LastLink == l) + LastLink = 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) +{ + CcuChainItem* del = GetNext (l); + if (del == l) { + LastLink = 0; + } else { + SetNext (l, GetNext (l)); + if (LastLink == del) + LastLink = l; + } + return del; +} + +/*? +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 +CcuChain :: Remove (CcuChainItem* entry) +{ + int removed = 0; + CcuChainIter li (*this); + CcuChainIter lj (*this); + while (++li) { + if (*li == entry) { + RemoveAfter (lj); + return 1; + } else + ++lj; + } + return 0; +} + +/*? +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 +CcuChain :: Remove (int (*p) (CcuChainItem*)) +{ + int removed = 0; + CcuChainIter li (*this); + CcuChainIter lj (*this); + while (++li) { + if ((*p) (*li)) { + RemoveAfter (lj); + return 1; + } else + ++lj; + } + return 0; +} + + +/*?nextdoc?*/ +void +CcuChain :: InsertAfter (const CcuChainIter& li, CcuChainItem* e) +{ + if (li.TheChain != this) { + StatusFlag = BadIterator; + return; + } + StatusFlag = NoError; + if (!li.CurLink) { + if (li.StatusFlag == CcuChainIter::StartOfChain) { + Prepend (e); + } else { + fprintf (stderr, "abnormal status in CcuChain::InsertAfter\n"); + abort (); + } + } else if (li.StatusFlag == CcuChainIter::EndOfChain) { + Append (e); + } else { + InsertAfter (li.CurLink, 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 +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) +{ + if (li.TheChain != this) { + StatusFlag = BadIterator; + return; + } + StatusFlag = NoError; + if (!li.CurLink) { + if (li.StatusFlag == CcuChainIter::StartOfChain) { + Prepend (e); + } else { + fprintf (stderr, "abnormal status in CcuChain::InsertBefore\n"); + abort (); + } + } else if (li.StatusFlag == CcuChainIter::EndOfChain) { + Append (e); + } else { + InsertBefore (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{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); + while (++li) + if (do_remove (*li)) { + RemoveAfter (lj); + li = lj; + } else + ++lj; +?*/ +CcuChainItem* +CcuChain :: RemoveAfter (const CcuChainIter& li) +{ + if (li.TheChain != this) { + StatusFlag = BadIterator; + return 0; + } + if (li.CurLink == LastLink) { + StatusFlag = LastLink ? TooFar : WasEmpty; + return 0; + } + StatusFlag = NoError; + if (li.CurLink) { + return RemoveAfter (li.CurLink); + } else { + return RemoveAfter (LastLink); + } +} + + +/*? +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 +{ + return (CurLink && StatusFlag == Normal) ? CurLink : 0; +} + + +/*? +Take one step of iteration. +?*/ +CcuChainIter& +CcuChainIter :: 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 == TheChain->LastLink) { + StatusFlag = EndOfChain; + } else { + CurLink = CurLink ? TheChain->GetNext (CurLink) : TheChain->GetNext (TheChain->LastLink); + 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, the iterator will +be correctly positionned. If not, it will have reached the end of the list. +?*/ +int +CcuChainIter :: Find (CcuChainItem* e) +{ + while (++(*this)) + if (**this == e) + return 1; + return 0; +} -- cgit v1.1