Main Page | Class Hierarchy | Class List | File List | Class Members | File Members

lists.h

Go to the documentation of this file.
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.29 2004/04/09 03:42:34 csoutheren 00031 * Removed all usages of "virtual inline" and "inline virtual" 00032 * 00033 * Revision 1.28 2004/04/04 07:39:57 csoutheren 00034 * Fixed cut-and-paste typo in VS.net 2003 changes that made all PLists sorted. Yikes! 00035 * 00036 * Revision 1.27 2004/04/03 23:53:09 csoutheren 00037 * Added various changes to improce compatibility with the Sun Forte compiler 00038 * Thanks to Brian Cameron 00039 * Added detection of readdir_r version 00040 * 00041 * Revision 1.26 2004/04/03 06:54:21 rjongbloed 00042 * Many and various changes to support new Visual C++ 2003 00043 * 00044 * Revision 1.25 2004/02/15 03:04:52 rjongbloed 00045 * Fixed problem with PSortedList nil variable and assignment between instances, 00046 * pointed out by Ben Lear. 00047 * 00048 * Revision 1.24 2004/02/09 06:23:32 csoutheren 00049 * Added fix for gcc 3.3.1 problem. Apparently, it is unable to correctly resolve 00050 * a function argument that is a reference to a const pointer. Changing the argument 00051 * to be a pointer to a pointer solves the problem. Go figure 00052 * 00053 * Revision 1.23 2004/02/08 11:13:10 rjongbloed 00054 * Fixed crash in heavily loaded multi-threaded systems using simultaneous sorted 00055 * lists, Thanks Federico Pinna, Fabrizio Ammollo and the gang at Reitek S.p.A. 00056 * 00057 * Revision 1.22 2003/08/31 22:11:29 dereksmithies 00058 * Fix from Diego Tartara for the SetAt function. Many thanks. 00059 * 00060 * Revision 1.21 2002/11/12 08:55:53 robertj 00061 * Changed scope of PAbstraSortedList::Element class so descendant classes 00062 * can get at it. 00063 * 00064 * Revision 1.20 2002/09/16 01:08:59 robertj 00065 * Added #define so can select if #pragma interface/implementation is used on 00066 * platform basis (eg MacOS) rather than compiler, thanks Robert Monaghan. 00067 * 00068 * Revision 1.19 2000/04/14 07:19:32 craigs 00069 * Fixed problem with assert when dequeueing from an empty queue 00070 * 00071 * Revision 1.18 1999/08/22 12:13:43 robertj 00072 * Fixed warning when using inlines on older GNU compiler 00073 * 00074 * Revision 1.17 1999/03/09 02:59:50 robertj 00075 * Changed comments to doc++ compatible documentation. 00076 * 00077 * Revision 1.16 1999/02/16 08:12:00 robertj 00078 * MSVC 6.0 compatibility changes. 00079 * 00080 * Revision 1.15 1998/09/23 06:20:49 robertj 00081 * Added open source copyright license. 00082 * 00083 * Revision 1.14 1997/06/08 04:49:12 robertj 00084 * Fixed non-template class descendent order. 00085 * 00086 * Revision 1.13 1997/04/27 05:50:10 robertj 00087 * DLL support. 00088 * 00089 * Revision 1.12 1997/02/14 13:53:59 robertj 00090 * Major rewrite of sorted list to use sentinel record instead of NULL pointers. 00091 * 00092 * Revision 1.11 1996/07/15 10:32:50 robertj 00093 * Fixed bug in sorted list (crash on remove). 00094 * 00095 * Revision 1.10 1996/05/26 03:25:13 robertj 00096 * Compatibility to GNU 2.7.x 00097 * 00098 * Revision 1.9 1996/01/23 13:13:32 robertj 00099 * Fixed bug in sorted list GetObjectsIndex not checking if is same object 00100 * 00101 * Revision 1.8 1995/08/24 12:35:00 robertj 00102 * Added assert for list index out of bounds. 00103 * 00104 * Revision 1.7 1995/06/17 11:12:43 robertj 00105 * Documentation update. 00106 * 00107 * Revision 1.6 1995/03/14 12:41:41 robertj 00108 * Updated documentation to use HTML codes. 00109 * 00110 * Revision 1.5 1995/02/22 10:50:30 robertj 00111 * Changes required for compiling release (optimised) version. 00112 * 00113 * Revision 1.4 1995/02/05 00:48:05 robertj 00114 * Fixed template version. 00115 * 00116 * Revision 1.3 1995/01/15 04:49:23 robertj 00117 * Fixed errors in template version. 00118 * 00119 * Revision 1.2 1994/12/21 11:53:12 robertj 00120 * Documentation and variable normalisation. 00121 * 00122 * Revision 1.1 1994/12/12 09:59:35 robertj 00123 * Initial revision 00124 * 00125 */ 00126 00127 #ifdef P_USE_PRAGMA 00128 #pragma interface 00129 #endif 00130 00131 00133 // PList container class 00134 00155 class PAbstractList : public PCollection 00156 { 00157 PCONTAINERINFO(PAbstractList, PCollection); 00158 00159 public: 00167 PINLINE PAbstractList(); 00169 00170 // Overrides from class PObject 00198 virtual Comparison Compare(const PObject & obj) const; 00199 00209 virtual BOOL SetSize( 00210 PINDEX newSize 00211 ); 00213 00222 virtual PINDEX Append( 00223 PObject * obj 00224 ); 00225 00238 virtual PINDEX Insert( 00239 const PObject & before, 00240 PObject * obj 00241 ); 00242 00250 virtual PINDEX InsertAt( 00251 PINDEX index, 00252 PObject * obj 00253 ); 00254 00261 virtual BOOL Remove( 00262 const PObject * obj 00263 ); 00264 00274 virtual PObject * RemoveAt( 00275 PINDEX index 00276 ); 00277 00289 virtual BOOL SetAt( 00290 PINDEX index, 00291 PObject * val 00292 ); 00293 00304 virtual BOOL ReplaceAt( 00305 PINDEX index, 00306 PObject * val 00307 ); 00308 00319 virtual PObject * GetAt( 00320 PINDEX index // Index position in the collection of the object. 00321 ) const; 00322 00330 virtual PINDEX GetObjectsIndex( 00331 const PObject * obj 00332 ) const; 00333 00342 virtual PINDEX GetValuesIndex( 00343 const PObject & obj 00344 ) const; 00346 00347 00348 protected: 00359 PINLINE PObject & GetReferenceAt( 00360 PINDEX index 00361 ) const; 00362 00372 BOOL SetCurrent( 00373 PINDEX index 00374 ) const; 00375 00376 class Element { 00377 public: 00378 friend class Info; 00379 Element(PObject * theData); 00380 Element * prev; 00381 Element * next; 00382 PObject * data; 00383 }; 00384 00385 class Info { 00386 public: 00387 Info() { head = tail = lastElement = NULL; } 00388 Element * head; 00389 Element * tail; 00390 Element * lastElement; 00391 PINDEX lastIndex; 00392 } * info; 00393 }; 00394 00395 00396 #ifdef PHAS_TEMPLATES 00397 00404 template <class T> class PList : public PAbstractList 00405 { 00406 PCLASSINFO(PList, PAbstractList); 00407 00408 public: 00416 PList() 00417 : PAbstractList() { } 00419 00425 virtual PObject * Clone() const 00426 { return PNEW PList(0, this); } 00428 00442 T & operator[](PINDEX index) const 00443 { return (T &)GetReferenceAt(index); } 00445 00446 protected: 00447 PList(int dummy, const PList * c) 00448 : PAbstractList(dummy, c) { } 00449 }; 00450 00451 00463 #define PLIST(cls, T) typedef PList<T> cls 00464 00476 #define PDECLARE_LIST(cls, T) \ 00477 PLIST(cls##_PTemplate, T); \ 00478 PDECLARE_CLASS(cls, PList<T>) \ 00479 protected: \ 00480 cls(int dummy, const cls * c) \ 00481 : PList<T>(dummy, c) { } \ 00482 public: \ 00483 cls() \ 00484 : PList<T>() { } \ 00485 virtual PObject * Clone() const \ 00486 { return PNEW cls(0, this); } \ 00487 00488 00501 template <class T> class PQueue : public PAbstractList 00502 { 00503 PCLASSINFO(PQueue, PAbstractList); 00504 00505 public: 00514 PQueue() 00515 : PAbstractList() { DisallowDeleteObjects(); } 00517 00523 virtual PObject * Clone() const 00524 { return PNEW PQueue(0, this); } 00526 00532 virtual void Enqueue( 00533 T * obj 00534 ) { PAbstractList::Append(obj); } 00540 virtual T * Dequeue() 00541 { if (GetSize() == 0) return NULL; else return (T *)PAbstractList::RemoveAt(0);} 00543 00544 protected: 00545 PQueue(int dummy, const PQueue * c) 00546 : PAbstractList(dummy, c) 00547 { reference->deleteObjects = c->reference->deleteObjects; } 00548 }; 00549 00550 00563 #define PQUEUE(cls, T) typedef PQueue<T> cls 00564 00565 00578 #define PDECLARE_QUEUE(cls, T) \ 00579 PQUEUE(cls##_PTemplate, T); \ 00580 PDECLARE_CLASS(cls, cls##_PTemplate) \ 00581 protected: \ 00582 cls(int dummy, const cls * c) \ 00583 : cls##_PTemplate(dummy, c) { } \ 00584 public: \ 00585 cls() \ 00586 : cls##_PTemplate() { } \ 00587 virtual PObject * Clone() const \ 00588 { return PNEW cls(0, this); } \ 00589 00590 00603 template <class T> class PStack : public PAbstractList 00604 { 00605 PCLASSINFO(PStack, PAbstractList); 00606 00607 public: 00616 PStack() 00617 : PAbstractList() { DisallowDeleteObjects(); } 00619 00625 virtual PObject * Clone() const 00626 { return PNEW PStack(0, this); } 00628 00635 virtual void Push( 00636 T * obj 00637 ) { PAbstractList::InsertAt(0, obj); } 00638 00644 virtual T * Pop() 00645 { return (T *)PAbstractList::RemoveAt(0); } 00646 00653 virtual T & Top() 00654 { PAssert(GetSize() > 0, PStackEmpty); return *(T *)GetAt(0); } 00656 00657 protected: 00658 PStack(int dummy, const PStack * c) 00659 : PAbstractList(dummy, c) 00660 { reference->deleteObjects = c->reference->deleteObjects; } 00661 }; 00662 00663 00676 #define PSTACK(cls, T) typedef PStack<T> cls 00677 00678 00691 #define PDECLARE_STACK(cls, T) \ 00692 PSTACK(cls##_PTemplate, T); \ 00693 PDECLARE_CLASS(cls, cls##_PTemplate) \ 00694 protected: \ 00695 cls(int dummy, const cls * c) \ 00696 : cls##_PTemplate(dummy, c) { } \ 00697 public: \ 00698 cls() \ 00699 : cls##_PTemplate() { } \ 00700 virtual PObject * Clone() const \ 00701 { return PNEW cls(0, this); } \ 00702 00703 00704 #else // PHAS_TEMPLATES 00705 00706 00707 #define PLIST(cls, T) \ 00708 class cls : public PAbstractList { \ 00709 PCLASSINFO(cls, PAbstractList); \ 00710 protected: \ 00711 inline cls(int dummy, const cls * c) \ 00712 : PAbstractList(dummy, c) { } \ 00713 public: \ 00714 inline cls() \ 00715 : PAbstractList() { } \ 00716 virtual PObject * Clone() const \ 00717 { return PNEW cls(0, this); } \ 00718 inline T & operator[](PINDEX index) const \ 00719 { return (T &)GetReferenceAt(index); } \ 00720 } 00721 00722 #define PDECLARE_LIST(cls, T) \ 00723 PLIST(cls##_PTemplate, T); \ 00724 PDECLARE_CLASS(cls, cls##_PTemplate) \ 00725 protected: \ 00726 cls(int dummy, const cls * c) \ 00727 : cls##_PTemplate(dummy, c) { } \ 00728 public: \ 00729 cls() \ 00730 : cls##_PTemplate() { } \ 00731 virtual PObject * Clone() const \ 00732 { return PNEW cls(0, this); } \ 00733 00734 00735 #define PQUEUE(cls, T) \ 00736 class cls : public PAbstractList { \ 00737 PCLASSINFO(cls, PAbstractList); \ 00738 protected: \ 00739 inline cls(int dummy, const cls * c) \ 00740 : PAbstractList(dummy, c) \ 00741 { reference->deleteObjects = c->reference->deleteObjects; } \ 00742 public: \ 00743 inline cls() \ 00744 : PAbstractList() { DisallowDeleteObjects(); } \ 00745 virtual PObject * Clone() const \ 00746 { return PNEW cls(0, this); } \ 00747 virtual void Enqueue(T * t) \ 00748 { PAbstractList::Append(t); } \ 00749 virtual T * Dequeue() \ 00750 { if (GetSize() == 0) return NULL; else return (T *)PAbstractList::RemoveAt(0);} \ 00751 } 00752 00753 #define PDECLARE_QUEUE(cls, T) \ 00754 PQUEUE(cls##_PTemplate, T); \ 00755 PDECLARE_CLASS(cls, cls##_PTemplate) \ 00756 protected: \ 00757 cls(int dummy, const cls * c) \ 00758 : cls##_PTemplate(dummy, c) { } \ 00759 public: \ 00760 cls() \ 00761 : cls##_PTemplate() { } \ 00762 virtual PObject * Clone() const \ 00763 { return PNEW cls(0, this); } \ 00764 00765 #define PSTACK(cls, T) \ 00766 class cls : public PAbstractList { \ 00767 PCLASSINFO(cls, PAbstractList); \ 00768 protected: \ 00769 inline cls(int dummy, const cls * c) \ 00770 : PAbstractList(dummy, c) \ 00771 { reference->deleteObjects = c->reference->deleteObjects; } \ 00772 public: \ 00773 inline cls() \ 00774 : PAbstractList() { DisallowDeleteObjects(); } \ 00775 virtual PObject * Clone() const \ 00776 { return PNEW cls(0, this); } \ 00777 virtual void Push(T * t) \ 00778 { PAbstractList::InsertAt(0, t); } \ 00779 virtual T * Pop() \ 00780 { PAssert(GetSize() > 0, PStackEmpty); return (T *)PAbstractList::RemoveAt(0); } \ 00781 virtual T & Top() \ 00782 { PAssert(GetSize() > 0, PStackEmpty); return *(T *)GetAt(0); } \ 00783 } 00784 00785 #define PDECLARE_STACK(cls, T) \ 00786 PSTACK(cls##_PTemplate, T); \ 00787 PDECLARE_CLASS(cls, cls##_PTemplate) \ 00788 protected: \ 00789 cls(int dummy, const cls * c) \ 00790 : cls##_PTemplate(dummy, c) { } \ 00791 public: \ 00792 cls() \ 00793 : cls##_PTemplate() { } \ 00794 virtual PObject * Clone() const \ 00795 { return PNEW cls(0, this); } \ 00796 00797 00798 #endif // PHAS_TEMPLATES 00799 00800 00802 // Sorted List of PObjects 00803 00830 class PAbstractSortedList : public PCollection 00831 { 00832 PCONTAINERINFO(PAbstractSortedList, PCollection); 00833 00834 public: 00842 PAbstractSortedList(); 00844 00874 virtual Comparison Compare(const PObject & obj) const; 00876 00886 virtual BOOL SetSize( 00887 PINDEX newSize // New size for the sorted list, this is ignored. 00888 ); 00890 00899 virtual PINDEX Append( 00900 PObject * obj // New object to place into the collection. 00901 ); 00902 00912 virtual PINDEX Insert( 00913 const PObject & before, // Object value to insert before. 00914 PObject * obj // New object to place into the collection. 00915 ); 00916 00926 virtual PINDEX InsertAt( 00927 PINDEX index, // Index position in collection to place the object. 00928 PObject * obj // New object to place into the collection. 00929 ); 00930 00941 virtual BOOL Remove( 00942 const PObject * obj // Existing object to remove from the collection. 00943 ); 00944 00954 virtual PObject * RemoveAt( 00955 PINDEX index // Index position in collection to place the object. 00956 ); 00957 00964 virtual void RemoveAll(); 00965 00972 virtual BOOL SetAt( 00973 PINDEX index, // Index position in collection to set. 00974 PObject * val // New value to place into the collection. 00975 ); 00976 00983 virtual PObject * GetAt( 00984 PINDEX index // Index position in the collection of the object. 00985 ) const; 00986 00998 virtual PINDEX GetObjectsIndex( 00999 const PObject * obj 01000 ) const; 01001 01010 virtual PINDEX GetValuesIndex( 01011 const PObject & obj 01012 ) const; 01014 01015 protected: 01016 struct Element { 01017 friend class Info; 01018 Element * parent; 01019 Element * left; 01020 Element * right; 01021 PObject * data; 01022 PINDEX subTreeSize; 01023 enum { Red, Black } colour; 01024 }; 01025 01026 struct Info { 01027 Element * root; 01028 Element * lastElement; 01029 PINDEX lastIndex; 01030 Element nil; 01031 } * info; 01032 01033 // New functions for class 01034 void RemoveElement(Element * node); 01035 void LeftRotate(Element * node); 01036 void RightRotate(Element * node); 01037 void DeleteSubTrees(Element * node, BOOL deleteObject); 01038 Element * Successor(const Element * node) const; 01039 Element * Predecessor(const Element * node) const; 01040 Element * OrderSelect(Element * node, PINDEX index) const; 01041 PINDEX ValueSelect(const Element * node, const PObject & obj, const Element ** lastElement) const; 01042 }; 01043 01044 01045 #ifdef PHAS_TEMPLATES 01046 01054 template <class T> class PSortedList : public PAbstractSortedList 01055 { 01056 PCLASSINFO(PSortedList, PAbstractSortedList); 01057 01058 public: 01066 PSortedList() 01067 : PAbstractSortedList() { } 01069 01075 virtual PObject * Clone() const 01076 { return PNEW PSortedList(0, this); } 01078 01091 T & operator[](PINDEX index) const 01092 { return *(T *)GetAt(index); } 01094 01095 protected: 01096 PSortedList(int dummy, const PSortedList * c) 01097 : PAbstractSortedList(dummy, c) { } 01098 }; 01099 01100 01112 #define PSORTED_LIST(cls, T) typedef PSortedList<T> cls 01113 01114 01127 #define PDECLARE_SORTED_LIST(cls, T) \ 01128 PSORTED_LIST(cls##_PTemplate, T); \ 01129 PDECLARE_CLASS(cls, PSortedList<T>) \ 01130 protected: \ 01131 cls(int dummy, const cls * c) \ 01132 : PSortedList<T>(dummy, c) { } \ 01133 public: \ 01134 cls() \ 01135 : PSortedList<T>() { } \ 01136 virtual PObject * Clone() const \ 01137 { return PNEW cls(0, this); } \ 01138 01139 01140 #else // PHAS_TEMPLATES 01141 01142 01143 #define PSORTED_LIST(cls, T) \ 01144 class cls : public PAbstractSortedList { \ 01145 PCLASSINFO(cls, PAbstractSortedList); \ 01146 protected: \ 01147 inline cls(int dummy, const cls * c) \ 01148 : PAbstractSortedList(dummy, c) { } \ 01149 public: \ 01150 inline cls() \ 01151 : PAbstractSortedList() { } \ 01152 virtual PObject * Clone() const \ 01153 { return PNEW cls(0, this); } \ 01154 inline T & operator[](PINDEX index) const \ 01155 { return *(T *)GetAt(index); } \ 01156 } 01157 01158 #define PDECLARE_SORTED_LIST(cls, T) \ 01159 PSORTED_LIST(cls##_PTemplate, T); \ 01160 PDECLARE_CLASS(cls, cls##_PTemplate) \ 01161 protected: \ 01162 cls(int dummy, const cls * c) \ 01163 : cls##_PTemplate(dummy, c) { } \ 01164 public: \ 01165 cls() \ 01166 : cls##_PTemplate() { } \ 01167 virtual PObject * Clone() const \ 01168 { return PNEW cls(0, this); } \ 01169 01170 01171 #endif // PHAS_TEMPLATES 01172 01173 01174 // End Of File ///////////////////////////////////////////////////////////////

Generated on Sat Jul 24 15:35:56 2004 for PWLib by doxygen 1.3.7