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.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 ///////////////////////////////////////////////////////////////

Generated on Fri Sep 21 14:40:11 2007 for PWLib by  doxygen 1.5.3