PWLib
1.10.10
|
00001 /* 00002 * lists.h 00003 * 00004 * List Container Classes 00005 * 00006 * Portable Windows Library 00007 * 00008 * Copyright (c) 1993-1998 Equivalence Pty. Ltd. 00009 * 00010 * The contents of this file are subject to the Mozilla Public License 00011 * Version 1.0 (the "License"); you may not use this file except in 00012 * compliance with the License. You may obtain a copy of the License at 00013 * http://www.mozilla.org/MPL/ 00014 * 00015 * Software distributed under the License is distributed on an "AS IS" 00016 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 00017 * the License for the specific language governing rights and limitations 00018 * under the License. 00019 * 00020 * The Original Code is Portable Windows Library. 00021 * 00022 * The Initial Developer of the Original Code is Equivalence Pty. Ltd. 00023 * 00024 * Portions are Copyright (C) 1993 Free Software Foundation, Inc. 00025 * All Rights Reserved. 00026 * 00027 * Contributor(s): ______________________________________. 00028 * 00029 * $Log: lists.h,v $ 00030 * Revision 1.32 2005/11/25 03:43:47 csoutheren 00031 * Fixed function argument comments to be compatible with Doxygen 00032 * 00033 * Revision 1.31 2005/01/25 06:35:27 csoutheren 00034 * Removed warnings under MSVC 00035 * 00036 * Revision 1.30 2005/01/09 06:35:03 rjongbloed 00037 * Fixed ability to make Clone() or MakeUnique() of a sorted list. 00038 * 00039 * Revision 1.29 2004/04/09 03:42:34 csoutheren 00040 * Removed all usages of "virtual inline" and "inline virtual" 00041 * 00042 * Revision 1.28 2004/04/04 07:39:57 csoutheren 00043 * Fixed cut-and-paste typo in VS.net 2003 changes that made all PLists sorted. Yikes! 00044 * 00045 * Revision 1.27 2004/04/03 23:53:09 csoutheren 00046 * Added various changes to improce compatibility with the Sun Forte compiler 00047 * Thanks to Brian Cameron 00048 * Added detection of readdir_r version 00049 * 00050 * Revision 1.26 2004/04/03 06:54:21 rjongbloed 00051 * Many and various changes to support new Visual C++ 2003 00052 * 00053 * Revision 1.25 2004/02/15 03:04:52 rjongbloed 00054 * Fixed problem with PSortedList nil variable and assignment between instances, 00055 * pointed out by Ben Lear. 00056 * 00057 * Revision 1.24 2004/02/09 06:23:32 csoutheren 00058 * Added fix for gcc 3.3.1 problem. Apparently, it is unable to correctly resolve 00059 * a function argument that is a reference to a const pointer. Changing the argument 00060 * to be a pointer to a pointer solves the problem. Go figure 00061 * 00062 * Revision 1.23 2004/02/08 11:13:10 rjongbloed 00063 * Fixed crash in heavily loaded multi-threaded systems using simultaneous sorted 00064 * lists, Thanks Federico Pinna, Fabrizio Ammollo and the gang at Reitek S.p.A. 00065 * 00066 * Revision 1.22 2003/08/31 22:11:29 dereksmithies 00067 * Fix from Diego Tartara for the SetAt function. Many thanks. 00068 * 00069 * Revision 1.21 2002/11/12 08:55:53 robertj 00070 * Changed scope of PAbstraSortedList::Element class so descendant classes 00071 * can get at it. 00072 * 00073 * Revision 1.20 2002/09/16 01:08:59 robertj 00074 * Added #define so can select if #pragma interface/implementation is used on 00075 * platform basis (eg MacOS) rather than compiler, thanks Robert Monaghan. 00076 * 00077 * Revision 1.19 2000/04/14 07:19:32 craigs 00078 * Fixed problem with assert when dequeueing from an empty queue 00079 * 00080 * Revision 1.18 1999/08/22 12:13:43 robertj 00081 * Fixed warning when using inlines on older GNU compiler 00082 * 00083 * Revision 1.17 1999/03/09 02:59:50 robertj 00084 * Changed comments to doc++ compatible documentation. 00085 * 00086 * Revision 1.16 1999/02/16 08:12:00 robertj 00087 * MSVC 6.0 compatibility changes. 00088 * 00089 * Revision 1.15 1998/09/23 06:20:49 robertj 00090 * Added open source copyright license. 00091 * 00092 * Revision 1.14 1997/06/08 04:49:12 robertj 00093 * Fixed non-template class descendent order. 00094 * 00095 * Revision 1.13 1997/04/27 05:50:10 robertj 00096 * DLL support. 00097 * 00098 * Revision 1.12 1997/02/14 13:53:59 robertj 00099 * Major rewrite of sorted list to use sentinel record instead of NULL pointers. 00100 * 00101 * Revision 1.11 1996/07/15 10:32:50 robertj 00102 * Fixed bug in sorted list (crash on remove). 00103 * 00104 * Revision 1.10 1996/05/26 03:25:13 robertj 00105 * Compatibility to GNU 2.7.x 00106 * 00107 * Revision 1.9 1996/01/23 13:13:32 robertj 00108 * Fixed bug in sorted list GetObjectsIndex not checking if is same object 00109 * 00110 * Revision 1.8 1995/08/24 12:35:00 robertj 00111 * Added assert for list index out of bounds. 00112 * 00113 * Revision 1.7 1995/06/17 11:12:43 robertj 00114 * Documentation update. 00115 * 00116 * Revision 1.6 1995/03/14 12:41:41 robertj 00117 * Updated documentation to use HTML codes. 00118 * 00119 * Revision 1.5 1995/02/22 10:50:30 robertj 00120 * Changes required for compiling release (optimised) version. 00121 * 00122 * Revision 1.4 1995/02/05 00:48:05 robertj 00123 * Fixed template version. 00124 * 00125 * Revision 1.3 1995/01/15 04:49:23 robertj 00126 * Fixed errors in template version. 00127 * 00128 * Revision 1.2 1994/12/21 11:53:12 robertj 00129 * Documentation and variable normalisation. 00130 * 00131 * Revision 1.1 1994/12/12 09:59:35 robertj 00132 * Initial revision 00133 * 00134 */ 00135 00136 #ifdef P_USE_PRAGMA 00137 #pragma interface 00138 #endif 00139 00140 00142 // PList container class 00143 00164 class PAbstractList : public PCollection 00165 { 00166 PCONTAINERINFO(PAbstractList, PCollection); 00167 00168 public: 00176 PINLINE PAbstractList(); 00178 00179 // Overrides from class PObject 00207 virtual Comparison Compare(const PObject & obj) const; 00208 00218 virtual BOOL SetSize( 00219 PINDEX newSize 00220 ); 00222 00231 virtual PINDEX Append( 00232 PObject * obj 00233 ); 00234 00247 virtual PINDEX Insert( 00248 const PObject & before, 00249 PObject * obj 00250 ); 00251 00259 virtual PINDEX InsertAt( 00260 PINDEX index, 00261 PObject * obj 00262 ); 00263 00270 virtual BOOL Remove( 00271 const PObject * obj 00272 ); 00273 00283 virtual PObject * RemoveAt( 00284 PINDEX index 00285 ); 00286 00298 virtual BOOL SetAt( 00299 PINDEX index, 00300 PObject * val 00301 ); 00302 00313 virtual BOOL ReplaceAt( 00314 PINDEX index, 00315 PObject * val 00316 ); 00317 00328 virtual PObject * GetAt( 00329 PINDEX index 00330 ) const; 00331 00339 virtual PINDEX GetObjectsIndex( 00340 const PObject * obj 00341 ) const; 00342 00351 virtual PINDEX GetValuesIndex( 00352 const PObject & obj 00353 ) const; 00355 00356 00357 protected: 00368 PINLINE PObject & GetReferenceAt( 00369 PINDEX index 00370 ) const; 00371 00381 BOOL SetCurrent( 00382 PINDEX index 00383 ) const; 00384 00385 class Element { 00386 public: 00387 friend class Info; 00388 Element(PObject * theData); 00389 Element * prev; 00390 Element * next; 00391 PObject * data; 00392 }; 00393 00394 class Info { 00395 public: 00396 Info() { head = tail = lastElement = NULL; } 00397 Element * head; 00398 Element * tail; 00399 Element * lastElement; 00400 PINDEX lastIndex; 00401 } * info; 00402 }; 00403 00404 00405 #ifdef PHAS_TEMPLATES 00406 00413 template <class T> class PList : public PAbstractList 00414 { 00415 PCLASSINFO(PList, PAbstractList); 00416 00417 public: 00425 PList() 00426 : PAbstractList() { } 00428 00434 virtual PObject * Clone() const 00435 { return PNEW PList(0, this); } 00437 00451 T & operator[](PINDEX index) const 00452 { return (T &)GetReferenceAt(index); } 00454 00455 protected: 00456 PList(int dummy, const PList * c) 00457 : PAbstractList(dummy, c) { } 00458 }; 00459 00460 00472 #define PLIST(cls, T) typedef PList<T> cls 00473 00485 #define PDECLARE_LIST(cls, T) \ 00486 PLIST(cls##_PTemplate, T); \ 00487 PDECLARE_CLASS(cls, PList<T>) \ 00488 protected: \ 00489 cls(int dummy, const cls * c) \ 00490 : PList<T>(dummy, c) { } \ 00491 public: \ 00492 cls() \ 00493 : PList<T>() { } \ 00494 virtual PObject * Clone() const \ 00495 { return PNEW cls(0, this); } \ 00496 00497 00510 template <class T> class PQueue : public PAbstractList 00511 { 00512 PCLASSINFO(PQueue, PAbstractList); 00513 00514 public: 00523 PQueue() 00524 : PAbstractList() { DisallowDeleteObjects(); } 00526 00532 virtual PObject * Clone() const 00533 { return PNEW PQueue(0, this); } 00535 00541 virtual void Enqueue( 00542 T * obj 00543 ) { PAbstractList::Append(obj); } 00549 virtual T * Dequeue() 00550 { if (GetSize() == 0) return NULL; else return (T *)PAbstractList::RemoveAt(0);} 00552 00553 protected: 00554 PQueue(int dummy, const PQueue * c) 00555 : PAbstractList(dummy, c) 00556 { reference->deleteObjects = c->reference->deleteObjects; } 00557 }; 00558 00559 00572 #define PQUEUE(cls, T) typedef PQueue<T> cls 00573 00574 00587 #define PDECLARE_QUEUE(cls, T) \ 00588 PQUEUE(cls##_PTemplate, T); \ 00589 PDECLARE_CLASS(cls, cls##_PTemplate) \ 00590 protected: \ 00591 cls(int dummy, const cls * c) \ 00592 : cls##_PTemplate(dummy, c) { } \ 00593 public: \ 00594 cls() \ 00595 : cls##_PTemplate() { } \ 00596 virtual PObject * Clone() const \ 00597 { return PNEW cls(0, this); } \ 00598 00599 00612 template <class T> class PStack : public PAbstractList 00613 { 00614 PCLASSINFO(PStack, PAbstractList); 00615 00616 public: 00625 PStack() 00626 : PAbstractList() { DisallowDeleteObjects(); } 00628 00634 virtual PObject * Clone() const 00635 { return PNEW PStack(0, this); } 00637 00644 virtual void Push( 00645 T * obj 00646 ) { PAbstractList::InsertAt(0, obj); } 00647 00653 virtual T * Pop() 00654 { return (T *)PAbstractList::RemoveAt(0); } 00655 00662 virtual T & Top() 00663 { PAssert(GetSize() > 0, PStackEmpty); return *(T *)GetAt(0); } 00665 00666 protected: 00667 PStack(int dummy, const PStack * c) 00668 : PAbstractList(dummy, c) 00669 { reference->deleteObjects = c->reference->deleteObjects; } 00670 }; 00671 00672 00685 #define PSTACK(cls, T) typedef PStack<T> cls 00686 00687 00700 #define PDECLARE_STACK(cls, T) \ 00701 PSTACK(cls##_PTemplate, T); \ 00702 PDECLARE_CLASS(cls, cls##_PTemplate) \ 00703 protected: \ 00704 cls(int dummy, const cls * c) \ 00705 : cls##_PTemplate(dummy, c) { } \ 00706 public: \ 00707 cls() \ 00708 : cls##_PTemplate() { } \ 00709 virtual PObject * Clone() const \ 00710 { return PNEW cls(0, this); } \ 00711 00712 00713 #else // PHAS_TEMPLATES 00714 00715 00716 #define PLIST(cls, T) \ 00717 class cls : public PAbstractList { \ 00718 PCLASSINFO(cls, PAbstractList); \ 00719 protected: \ 00720 inline cls(int dummy, const cls * c) \ 00721 : PAbstractList(dummy, c) { } \ 00722 public: \ 00723 inline cls() \ 00724 : PAbstractList() { } \ 00725 virtual PObject * Clone() const \ 00726 { return PNEW cls(0, this); } \ 00727 inline T & operator[](PINDEX index) const \ 00728 { return (T &)GetReferenceAt(index); } \ 00729 } 00730 00731 #define PDECLARE_LIST(cls, T) \ 00732 PLIST(cls##_PTemplate, T); \ 00733 PDECLARE_CLASS(cls, cls##_PTemplate) \ 00734 protected: \ 00735 cls(int dummy, const cls * c) \ 00736 : cls##_PTemplate(dummy, c) { } \ 00737 public: \ 00738 cls() \ 00739 : cls##_PTemplate() { } \ 00740 virtual PObject * Clone() const \ 00741 { return PNEW cls(0, this); } \ 00742 00743 00744 #define PQUEUE(cls, T) \ 00745 class cls : public PAbstractList { \ 00746 PCLASSINFO(cls, PAbstractList); \ 00747 protected: \ 00748 inline cls(int dummy, const cls * c) \ 00749 : PAbstractList(dummy, c) \ 00750 { reference->deleteObjects = c->reference->deleteObjects; } \ 00751 public: \ 00752 inline cls() \ 00753 : PAbstractList() { DisallowDeleteObjects(); } \ 00754 virtual PObject * Clone() const \ 00755 { return PNEW cls(0, this); } \ 00756 virtual void Enqueue(T * t) \ 00757 { PAbstractList::Append(t); } \ 00758 virtual T * Dequeue() \ 00759 { if (GetSize() == 0) return NULL; else return (T *)PAbstractList::RemoveAt(0);} \ 00760 } 00761 00762 #define PDECLARE_QUEUE(cls, T) \ 00763 PQUEUE(cls##_PTemplate, T); \ 00764 PDECLARE_CLASS(cls, cls##_PTemplate) \ 00765 protected: \ 00766 cls(int dummy, const cls * c) \ 00767 : cls##_PTemplate(dummy, c) { } \ 00768 public: \ 00769 cls() \ 00770 : cls##_PTemplate() { } \ 00771 virtual PObject * Clone() const \ 00772 { return PNEW cls(0, this); } \ 00773 00774 #define PSTACK(cls, T) \ 00775 class cls : public PAbstractList { \ 00776 PCLASSINFO(cls, PAbstractList); \ 00777 protected: \ 00778 inline cls(int dummy, const cls * c) \ 00779 : PAbstractList(dummy, c) \ 00780 { reference->deleteObjects = c->reference->deleteObjects; } \ 00781 public: \ 00782 inline cls() \ 00783 : PAbstractList() { DisallowDeleteObjects(); } \ 00784 virtual PObject * Clone() const \ 00785 { return PNEW cls(0, this); } \ 00786 virtual void Push(T * t) \ 00787 { PAbstractList::InsertAt(0, t); } \ 00788 virtual T * Pop() \ 00789 { PAssert(GetSize() > 0, PStackEmpty); return (T *)PAbstractList::RemoveAt(0); } \ 00790 virtual T & Top() \ 00791 { PAssert(GetSize() > 0, PStackEmpty); return *(T *)GetAt(0); } \ 00792 } 00793 00794 #define PDECLARE_STACK(cls, T) \ 00795 PSTACK(cls##_PTemplate, T); \ 00796 PDECLARE_CLASS(cls, cls##_PTemplate) \ 00797 protected: \ 00798 cls(int dummy, const cls * c) \ 00799 : cls##_PTemplate(dummy, c) { } \ 00800 public: \ 00801 cls() \ 00802 : cls##_PTemplate() { } \ 00803 virtual PObject * Clone() const \ 00804 { return PNEW cls(0, this); } \ 00805 00806 00807 #endif // PHAS_TEMPLATES 00808 00809 00811 // Sorted List of PObjects 00812 00839 class PAbstractSortedList : public PCollection 00840 { 00841 PCONTAINERINFO(PAbstractSortedList, PCollection); 00842 00843 public: 00851 PAbstractSortedList(); 00853 00883 virtual Comparison Compare(const PObject & obj) const; 00885 00895 virtual BOOL SetSize( 00896 PINDEX newSize // New size for the sorted list, this is ignored. 00897 ); 00899 00908 virtual PINDEX Append( 00909 PObject * obj // New object to place into the collection. 00910 ); 00911 00921 virtual PINDEX Insert( 00922 const PObject & before, // Object value to insert before. 00923 PObject * obj // New object to place into the collection. 00924 ); 00925 00935 virtual PINDEX InsertAt( 00936 PINDEX index, // Index position in collection to place the object. 00937 PObject * obj // New object to place into the collection. 00938 ); 00939 00950 virtual BOOL Remove( 00951 const PObject * obj // Existing object to remove from the collection. 00952 ); 00953 00963 virtual PObject * RemoveAt( 00964 PINDEX index // Index position in collection to place the object. 00965 ); 00966 00973 virtual void RemoveAll(); 00974 00981 virtual BOOL SetAt( 00982 PINDEX index, // Index position in collection to set. 00983 PObject * val // New value to place into the collection. 00984 ); 00985 00992 virtual PObject * GetAt( 00993 PINDEX index // Index position in the collection of the object. 00994 ) const; 00995 01007 virtual PINDEX GetObjectsIndex( 01008 const PObject * obj 01009 ) const; 01010 01019 virtual PINDEX GetValuesIndex( 01020 const PObject & obj 01021 ) const; 01023 01024 struct Element { 01025 friend class Info; 01026 Element * parent; 01027 Element * left; 01028 Element * right; 01029 PObject * data; 01030 PINDEX subTreeSize; 01031 enum { Red, Black } colour; 01032 }; 01033 01034 protected: 01035 struct Info { 01036 Info(); 01037 01038 Element * root; 01039 Element * lastElement; 01040 PINDEX lastIndex; 01041 Element nil; 01042 01043 Element * Successor(const Element * node) const; 01044 Element * Predecessor(const Element * node) const; 01045 Element * OrderSelect(Element * node, PINDEX index) const; 01046 } * info; 01047 01048 // New functions for class 01049 void RemoveElement(Element * node); 01050 void LeftRotate(Element * node); 01051 void RightRotate(Element * node); 01052 void DeleteSubTrees(Element * node, BOOL deleteObject); 01053 PINDEX ValueSelect(const Element * node, const PObject & obj, const Element ** lastElement) const; 01054 }; 01055 01056 01057 #ifdef PHAS_TEMPLATES 01058 01066 template <class T> class PSortedList : public PAbstractSortedList 01067 { 01068 PCLASSINFO(PSortedList, PAbstractSortedList); 01069 01070 public: 01078 PSortedList() 01079 : PAbstractSortedList() { } 01081 01087 virtual PObject * Clone() const 01088 { return PNEW PSortedList(0, this); } 01090 01103 T & operator[](PINDEX index) const 01104 { return *(T *)GetAt(index); } 01106 01107 protected: 01108 PSortedList(int dummy, const PSortedList * c) 01109 : PAbstractSortedList(dummy, c) { } 01110 }; 01111 01112 01124 #define PSORTED_LIST(cls, T) typedef PSortedList<T> cls 01125 01126 01139 #define PDECLARE_SORTED_LIST(cls, T) \ 01140 PSORTED_LIST(cls##_PTemplate, T); \ 01141 PDECLARE_CLASS(cls, PSortedList<T>) \ 01142 protected: \ 01143 cls(int dummy, const cls * c) \ 01144 : PSortedList<T>(dummy, c) { } \ 01145 public: \ 01146 cls() \ 01147 : PSortedList<T>() { } \ 01148 virtual PObject * Clone() const \ 01149 { return PNEW cls(0, this); } \ 01150 01151 01152 #else // PHAS_TEMPLATES 01153 01154 01155 #define PSORTED_LIST(cls, T) \ 01156 class cls : public PAbstractSortedList { \ 01157 PCLASSINFO(cls, PAbstractSortedList); \ 01158 protected: \ 01159 inline cls(int dummy, const cls * c) \ 01160 : PAbstractSortedList(dummy, c) { } \ 01161 public: \ 01162 inline cls() \ 01163 : PAbstractSortedList() { } \ 01164 virtual PObject * Clone() const \ 01165 { return PNEW cls(0, this); } \ 01166 inline T & operator[](PINDEX index) const \ 01167 { return *(T *)GetAt(index); } \ 01168 } 01169 01170 #define PDECLARE_SORTED_LIST(cls, T) \ 01171 PSORTED_LIST(cls##_PTemplate, T); \ 01172 PDECLARE_CLASS(cls, cls##_PTemplate) \ 01173 protected: \ 01174 cls(int dummy, const cls * c) \ 01175 : cls##_PTemplate(dummy, c) { } \ 01176 public: \ 01177 cls() \ 01178 : cls##_PTemplate() { } \ 01179 virtual PObject * Clone() const \ 01180 { return PNEW cls(0, this); } \ 01181 01182 01183 #endif // PHAS_TEMPLATES 01184 01185 01186 // End Of File ///////////////////////////////////////////////////////////////