#ifndef BoDList_HH #define BoDList_HH ////////////////////////////////////////////////////////////////////////// //! file="amma/Contain/DList/BoDList.hh" //! lib=Mlist //! userlevel=Develop //! author="Radek Marik" //! date="22.08.94" //! docentry="Containers.Lists.DList" //! rcsid="$Id: BoDList.hh,v 1.11 1999/02/19 09:43:16 ees1cg Exp $" #include "amma/DLinkDat.hh" #include "amma/BDList.hh" template class BaseBodyConstDLIterC; template class RefBodyDListC; class ostream; //=========================================================================== //========== BodyDListC ===================================================== //=========================================================================== //: Body of double-linked circular list // The BodyDListC class represents double-linked list of elements // The list contains a head element and a chain of // elements. Empty list contains just its head element. // Because of efficiency references to elements of a list are not // checked if they are proper elements of a list or its head. // The class serves as a base class for refernce counted double-linked list. // Implementation notes: // The class BaseDListC must be defined as a base class of the class // BodyDListC to make a cast from the head structure to the whole // list structure possible. template class BodyDListC: protected BaseDListC // the base list { public: //----------- Constructors/Destructor/Assigment --------- inline BodyDListC(); // An empty list. BodyDListC(const BodyDListC & li); // Copy constructor. The physical copy of the list 'li' is created. inline BodyDListC Copy() const; // Create a copy of this list. inline const BodyDListC & operator=(const BodyDListC & list); // An assigment of a list. This list will contain a new copy // of the 'list'. At first the list is emptied. At second // copies of all elements of the 'list' are inserted to this // list. inline const BodyDListC & List() const; // Self identification. inline ~BodyDListC(); // The destructor of the list, each list element is destroyed. //---------- Status information --------------------------------- BaseDListC::IsEmpty; // see the class BaseDListC BaseDListC::Size; // see the class BaseDListC BaseDListC::ConsistencyCheck; // see the class BaseDListC inline BooleanT operator==(const BodyDListC & list) const; // Returns TRUE if both lists represent the same list. inline BooleanT operator!=(const BodyDListC & list) const; // Returns TRUE if both lists are independent. //---------- Access to the elements ----------------------------- inline const DataC & First() const; // Returns the first element of the constant list. inline DataC & First(); // Returns the first element of the list. inline const DataC & Last() const; // Returns the last element of the constant list. inline DataC & Last(); // Returns the last element of the constant list. inline const DataC & operator[](IndexT i) const; // Returns the i-th element of the constant list. The first element has // the index 0. inline DataC & operator[](IndexT i); // Returns the i-th element of the list. The first element has // the index 0. //---------- Elementary changes in the list ------------- inline BodyDListC & InsFirst(const DataC & data); // Inserts the new element at the beginning of the list. // Returns the reference to the changed list. inline BodyDListC & InsLast(const DataC & data); // Inserts the new element at the end of the list. // Returns the pointer to the list. inline BodyDListC & DelFirst(); // Deletes the first element of the list. // Returns the reference to the list. inline BodyDListC & DelLast(); // Deletes the last element of the list. // Returns the reference to the list. inline DataC GetFirst(); // Removes the first element from the list. // Returns that removed element. inline DataC GetLast(); // Removes the last element from the list. // Returns that removed element. inline BodyDListC & MakeFirst(BaseBodyConstDLIterC & ptr); // Moves the head of the list to be the predeccessor of the element // pointed to be 'ptr'. // The iterator 'ptr' must belong to this list. // Returns the reference to the list. inline BodyDListC & MakeLast(BaseBodyConstDLIterC & ptr); // Moves the head of the list to be the successor of the element // pointed to by 'ptr'. // The iterator 'ptr' must belong to this list. // Returns the reference to the list. inline BodyDListC & MoveFirst(BaseBodyConstDLIterC & ptr); // Moves the list element pointed to by 'ptr' into the list // as the first element. The pointed list element need not to be // the element of this list, but it cannot be the head of any list. // Returns this list. inline BodyDListC & MoveLast(BaseBodyConstDLIterC & ptr); // Moves the list element, which 'ptr' points to, into the list // as the last element. The pointed list element need not to be // the element of this list, but it cannot be the head of any list. // Returns this list. //---------- Transformations of lists ----------------------------- inline BodyDListC & MoveFirst(BodyDListC & list); // Moves the whole 'list' to the beginning of this list. The 'list' // will be empty after the operation. Returns this list. inline BodyDListC & MoveLast(BodyDListC & list); // Moves the whole 'list' to the end of this list. The 'list' // will be empty after the operation. Returns this list. inline const BodyDListC & operator+=(const BodyDListC & list); // Concatenation. The operator adds the copy of the 'list to the end // of this list. // Returns this list. inline BodyDListC & Reverse(); // Reverses the list. Returns the list. inline BodyDListC Tail(BaseBodyConstDLIterC & ptr); // Splits the list into two parts. This list will contain the beginning // of the original list. The function returns the second part // of the original list including the element 'ptr'. inline BodyDListC Head(BaseBodyConstDLIterC & ptr); // Splits the list into two parts. This list will contain the second part // of the original list including the element 'ptr'. // The function returns the list containing the beginning of the original // list. inline BodyDListC & Empty(); // All elements of the list will be destroyed. inline void MergeSort(int (*LessOrEqual)(const DataC & el1, const DataC & el2)); // Sorts the list according to order defined by the function 'LessOrEqual'. inline void BubbleSort(int (*LessOrEqual)(const DataC & el1, const DataC & el2)); // Sorts the list according to order defined by // the function 'LessOrEqual'. NOT READY !!! private: // Special functions // ----------------- inline BodyDListC(int , BaseBodyConstDLIterC & ptr); // Constructor. The tail list is passed. inline BodyDListC(BaseBodyConstDLIterC & ptr, int); // Constructor. The head list is passed. void SetCopy(const BodyDListC & list); // Copies all elements from the 'list' into this list. inline const DataC & Data(const DChainC & elm) const; // Casts the link 'elm' to the structure containing data and returns // the data. inline DataC & Data(DChainC & elm); // Casts the link 'elm' to the structure containing data and returns // the data. friend class RefBodyDListC; friend class BaseBodyConstDLIterC; #ifndef NEWGCC friend ostream & operator<<(ostream & s, const BodyDListC & list); #else friend ostream & operator<< (ostream & s, const BodyDListC & list); #endif }; //template //ostream & operator<<(ostream & s, const BodyDListC & list); // Saves the list into the output stream. template class MergeSortC { public: static void Sort(BodyDListC& list); }; #include "amma/BBCDLIte.hh" // ------------------------------------------------------------------------- // ********** BodyDListC *************************************************** // ------------------------------------------------------------------------- template inline const DataC & BodyDListC::Data(const DChainC & elm) const //================================================ { if (&elm == ListHead()) { errAMMA << "An attempt to return a content of the head of the list:\n" << " elm = " << elm << '\n' << " head = " << (*ListHead()); errAMMA.Function("BodyDListC::Data(const DChainC & elm)const") .Exit(); } return ((const DLinkAndDataC &)elm).Data(); } template inline DataC & BodyDListC::Data(DChainC & elm) //==================================== { if (&elm == ListHead()) { errAMMA << "An attempt to return a content of the head of the list:\n" << " elm = " << elm << '\n' << " head = " << (*ListHead()); errAMMA.Function("BodyDListC::Data(DChainC & elm)") .Exit(); } return ((DLinkAndDataC &)elm).Data(); } template inline const BodyDListC & BodyDListC::List() const //============================= { return *this; } template inline BodyDListC::BodyDListC() //============================= {} template inline BooleanT BodyDListC::operator==(const BodyDListC & list) const //================================================================= { return BaseDListC::operator==(list); } template inline BooleanT BodyDListC::operator!=(const BodyDListC & list) const //================================================================= { return BaseDListC::operator!=(list); } template inline const DataC & BodyDListC::First() const //============================== { return Data(BaseDListC::First()); } template inline DataC & BodyDListC::First() //======================== { return Data(BaseDListC::First()); } template inline const DataC & BodyDListC::Last() const //============================= { return Data(BaseDListC::Last()); } template inline DataC & BodyDListC::Last() //======================= { return Data(BaseDListC::Last()); } template inline BodyDListC & BodyDListC::InsFirst(const DataC & data) //============================================= { LinkFirst(new DLinkAndDataC(data)); return *this; } template inline BodyDListC & BodyDListC::InsLast(const DataC & data) //============================================ { LinkLast(new DLinkAndDataC(data)); return *this; } template inline BodyDListC & BodyDListC::DelFirst() //=========================== { delete (DLinkAndDataC *) BaseDListC::First().Unlink(); return *this; } template inline BodyDListC & BodyDListC::DelLast() //========================== { delete (DLinkAndDataC *) BaseDListC::Last().Unlink(); return *this; } template inline DataC BodyDListC::GetFirst() //=========================== { DataC first = First(); DelFirst(); return first; } template inline DataC BodyDListC::GetLast() //========================== { DataC last = Last(); DelLast(); return last; } template inline BodyDListC & BodyDListC::MakeFirst(BaseBodyConstDLIterC & ptr) //============================================================= { BaseDListC::MakeFirst(ptr); return *this; } template inline BodyDListC & BodyDListC::MakeLast(BaseBodyConstDLIterC & ptr) //============================================================ { BaseDListC::MakeLast(ptr); return *this; } template inline BodyDListC & BodyDListC::MoveFirst(BaseBodyConstDLIterC & ptr) //============================================================= { BaseDListC::MoveFirst(ptr); return *this; } template inline BodyDListC & BodyDListC::MoveLast(BaseBodyConstDLIterC & ptr) //============================================================ { BaseDListC::MoveLast(ptr); return *this; } template inline BodyDListC::BodyDListC(const BodyDListC & li) //========================================================= { SetCopy(li); } template inline BodyDListC & BodyDListC::MoveFirst(BodyDListC & list) //==================================================== { BaseDListC::MoveFirst(list); return *this; } template inline BodyDListC & BodyDListC::MoveLast(BodyDListC & list) //=================================================== { BaseDListC::MoveLast(list); return *this; } template inline BodyDListC BodyDListC::Copy() const //============================= { return BodyDListC(*this); } template inline const BodyDListC & BodyDListC::operator+=(const BodyDListC & list) //=========================================================== { BodyDListC copy(list.Copy()); return MoveLast(copy); } template inline BodyDListC::BodyDListC(BaseBodyConstDLIterC & ptr, int) //=================================================================== : BaseDListC(ptr, 0) {} template inline BodyDListC::BodyDListC(int ,BaseBodyConstDLIterC & ptr) //=================================================================== : BaseDListC(0, ptr) {} template inline BodyDListC BodyDListC::Tail(BaseBodyConstDLIterC & ptr) //======================================================== { return BodyDListC(0,ptr); } template inline BodyDListC BodyDListC::Head(BaseBodyConstDLIterC & ptr) //======================================================== { return BodyDListC(ptr, 0); } template inline BodyDListC & BodyDListC::Reverse() //========================== { BaseDListC::Reverse(); return *this; } template inline BodyDListC::~BodyDListC() //============================== { Empty(); } template inline const DataC & BodyDListC::operator[](IndexT i) const //==================================== { return Data(BaseDListC::operator[](i)); } template inline DataC & BodyDListC::operator[](IndexT i) //===================================== { return Data(BaseDListC::operator[](i)); } template inline BodyDListC & BodyDListC::Empty() //======================== { while (!IsEmpty()) DelFirst(); return *this; } template inline const BodyDListC & BodyDListC::operator=(const BodyDListC & list) //========================================================== { Empty().SetCopy(list); return *this; } template inline void BodyDListC::BubbleSort( int (*Cmp) (const DataC&,const DataC&) ) //===================================================================== { BooleanT isChanged = FALSE; const DChainC * last = & BaseDListC::Last(); const DChainC * listHead = ListHead(); do { for (DChainC * ptr = (DChainC *) listHead; ptr != last && ptr != listHead; ptr = ptr->NextPtr()) if (Cmp(((const DLinkAndDataC *)ptr)->Data(), ((const DLinkAndDataC *)ptr->NextPtr())->Data())) { isChanged = TRUE; ptr->LinkBef(ptr->NextPtr()->Unlink()); } } while (!isChanged); } #include #include "amma/BoCDLIte.hh" // ------------------------------------------------------------------------ // ********** BodyDListC ************************************************** // ------------------------------------------------------------------------ template void BodyDListC::SetCopy(const BodyDListC & list) //======================================================== { const DChainC * listHead = list.ListHead(); for (const DChainC * ptr = listHead->NextPtr(); ptr != listHead; ptr = ptr->NextPtr()) LinkLast(new DLinkAndDataC( ((const DLinkAndDataC *)ptr)->Data())); } template ostream & operator<<(ostream & s, const BodyDListC & list) //===================================================== { BodyConstDLIterC ptr(list); for (; ptr.IsElm(); ptr.Next()) s << ptr.Data() << '\n'; return(s); } #include template class ListSortG { DLinkC** listsort(DLinkC* *head, unsigned n); int (*leq)(const T&, const T&); // gcc doesn't implement static data members for templates inline int LessOrEqual(const DLinkC* a,const DLinkC* b) { return leq((static_cast *>(a))->Data(), (static_cast *>(b))->Data()); } public: ListSortG(int (*aneq)(const T&, const T&)) : leq(aneq) {} void Sort(int(*usercmp)(const T&,const T&),DLinkC* *head, unsigned n); }; template void ListSortG:: Sort(int(*usercmp)(const T&,const T&),DLinkC* *head, unsigned n) { //#if !defined(VISUAL_CPP) leq = usercmp; // FIXME :- See above. //#endif listsort(head,n); } #define getlink(elm) ((elm)->succ) template DLinkC** ListSortG::listsort(DLinkC* *head, unsigned n) { register DLinkC* p1, *p2; DLinkC **h2, **t2; unsigned m; switch (n) { case 0: return head; case 1: return &getlink(*head); case 2: p2 = getlink(p1 = *head); if (LessOrEqual(p1, p2)) return &getlink(p2); getlink(p1) = getlink(*head=p2); return &getlink(getlink(p2) = p1); } n -= m = n / 2; t2 = listsort(h2 = listsort(head, n), m); if (LessOrEqual(p1 = *head, p2 = *h2)) { do { if (!--n) return *h2 = p2, t2; } while (LessOrEqual(p1=*(head=&getlink(p1)), p2)); } for (;;) { *head = p2; do { if (!--m) return *h2 = *t2, *t2 = p1, h2; } while (!LessOrEqual(p1, p2=*(head=&getlink(p2)))); *head = p1; do { if (!--n) return *h2 = p2, t2; } while (LessOrEqual(p1=*(head=&getlink(p1)), p2)); } } /*----------------------------------------------------------------------*/ template class ListSortCmpG { public: static DLinkC** listsort(DLinkC* *head, unsigned n); private: inline static int LessOrEqual(const DLinkC* a,const DLinkC* b) { return Cmp::cmp (((const DLinkAndDataC*)a)->Data(),((const DLinkAndDataC*)b)->Data()); } }; template DLinkC** ListSortCmpG::listsort(DLinkC* *head, unsigned n) { register DLinkC* p1, *p2; DLinkC **h2, **t2; unsigned m; switch (n) { case 0: return head; case 1: return &getlink(*head); case 2: p2 = getlink(p1 = *head); if (LessOrEqual(p1, p2)) return &getlink(p2); getlink(p1) = getlink(*head=p2); return &getlink(getlink(p2) = p1); } n -= m = n / 2; t2 = listsort(h2 = listsort(head, n), m); if (LessOrEqual(p1 = *head, p2 = *h2)) { do { if (!--n) return *h2 = p2, t2; } while (LessOrEqual(p1=*(head=&getlink(p1)), p2)); } for (;;) { *head = p2; do { if (!--m) return *h2 = *t2, *t2 = p1, h2; } while (!LessOrEqual(p1, p2=*(head=&getlink(p2)))); *head = p1; do { if (!--n) return *h2 = p2, t2; } while (LessOrEqual(p1=*(head=&getlink(p1)), p2)); } } /*----------------------------------------------------------------------*/ template void MergeSortC::Sort(BodyDListC& list) { DLinkC *prevLink = static_cast(&list); ListSortCmpG::listsort(&(prevLink->succ),list.Size()); FixBackward(prevLink); } template inline void BodyDListC::MergeSort( int (*cmp) (const DataC&,const DataC&) ) //===================================================================== { DLinkC * prevLink= (DLinkC *)this; ListSortG sortit(cmp); sortit.Sort(cmp, &(prevLink->succ), Size()); FixBackward(prevLink); } #endif // IAPS - Image analysis program system. // End of include file BoDList.hh