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
005n 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
005n 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: