include/ptlib/lists.h

   1 /*
   2  * lists.h
   3  *
   4  * List Container Classes
   5  *
   6  * Portable Windows Library
   7  *
   8  * Copyright (c) 1993-1998 Equivalence Pty. Ltd.
   9  *
  10  * The contents of this file are subject to the Mozilla Public License
  11  * Version 1.0 (the "License"); you may not use this file except in
  12  * compliance with the License. You may obtain a copy of the License at
  13  * http://www.mozilla.org/MPL/
  14  *
  15  * Software distributed under the License is distributed on an "AS IS"
  16  * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
  17  * the License for the specific language governing rights and limitations
  18  * under the License.
  19  *
  20  * The Original Code is Portable Windows Library.
  21  *
  22  * The Initial Developer of the Original Code is Equivalence Pty. Ltd.
  23  *
  24  * Portions are Copyright (C) 1993 Free Software Foundation, Inc.
  25  * All Rights Reserved.
  26  *
  27  * Contributor(s): ______________________________________.
  28  *
  29  * $Log$
  30  * Revision 1.25  2004/02/15 03:04:52  rjongbloed
  31  * Fixed problem with PSortedList nil variable and assignment between instances,
  32  *   pointed out by Ben Lear.
  33  *
  34  * Revision 1.24  2004/02/09 06:23:32  csoutheren
  35  * Added fix for gcc 3.3.1 problem. Apparently, it is unable to correctly resolve
  36  * a function argument that is a reference to a const pointer. Changing the argument
  37  * to be a pointer to a pointer solves the problem. Go figure
  38  *
  39  * Revision 1.23  2004/02/08 11:13:10  rjongbloed
  40  * Fixed crash in heavily loaded multi-threaded systems using simultaneous sorted
  41  *   lists, Thanks Federico Pinna, Fabrizio Ammollo and the gang at Reitek S.p.A.
  42  *
  43  * Revision 1.22  2003/08/31 22:11:29  dereksmithies
  44  * Fix from Diego Tartara for the SetAt function. Many thanks.
  45  *
  46  * Revision 1.21  2002/11/12 08:55:53  robertj
  47  * Changed scope of PAbstraSortedList::Element class so descendant classes
  48  *   can get at it.
  49  *
  50  * Revision 1.20  2002/09/16 01:08:59  robertj
  51  * Added #define so can select if #pragma interface/implementation is used on
  52  *   platform basis (eg MacOS) rather than compiler, thanks Robert Monaghan.
  53  *
  54  * Revision 1.19  2000/04/14 07:19:32  craigs
  55  * Fixed problem with assert when dequeueing from an empty queue
  56  *
  57  * Revision 1.18  1999/08/22 12:13:43  robertj
  58  * Fixed warning when using inlines on older GNU compiler
  59  *
  60  * Revision 1.17  1999/03/09 02:59:50  robertj
  61  * Changed comments to doc++ compatible documentation.
  62  *
  63  * Revision 1.16  1999/02/16 08:12:00  robertj
  64  * MSVC 6.0 compatibility changes.
  65  *
  66  * Revision 1.15  1998/09/23 06:20:49  robertj
  67  * Added open source copyright license.
  68  *
  69  * Revision 1.14  1997/06/08 04:49:12  robertj
  70  * Fixed non-template class descendent order.
  71  *
  72  * Revision 1.13  1997/04/27 05:50:10  robertj
  73  * DLL support.
  74  *
  75  * Revision 1.12  1997/02/14 13:53:59  robertj
  76  * Major rewrite of sorted list to use sentinel record instead of NULL pointers.
  77  *
  78  * Revision 1.11  1996/07/15 10:32:50  robertj
  79  * Fixed bug in sorted list (crash on remove).
  80  *
  81  * Revision 1.10  1996/05/26 03:25:13  robertj
  82  * Compatibility to GNU 2.7.x
  83  *
  84  * Revision 1.9  1996/01/23 13:13:32  robertj
  85  * Fixed bug in sorted list GetObjectsIndex not checking if is same object
  86  *
  87  * Revision 1.8  1995/08/24 12:35:00  robertj
  88  * Added assert for list index out of bounds.
  89  *
  90  * Revision 1.7  1995/06/17 11:12:43  robertj
  91  * Documentation update.
  92  *
  93  * Revision 1.6  1995/03/14 12:41:41  robertj
  94  * Updated documentation to use HTML codes.
  95  *
  96  * Revision 1.5  1995/02/22  10:50:30  robertj
  97  * Changes required for compiling release (optimised) version.
  98  *
  99  * Revision 1.4  1995/02/05  00:48:05  robertj
 100  * Fixed template version.
 101  *
 102  * Revision 1.3  1995/01/15  04:49:23  robertj
 103  * Fixed errors in template version.
 104  *
 105  * Revision 1.2  1994/12/21  11:53:12  robertj
 106  * Documentation and variable normalisation.
 107  *
 108  * Revision 1.1  1994/12/12  09:59:35  robertj
 109  * Initial revision
 110  *
 111  */
 112
 113 #ifdef P_USE_PRAGMA
 114 #pragma interface
 115 #endif
 116
 117
 118 ///////////////////////////////////////////////////////////////////////////////
 119 // PList container class
 120
 121 /**This class is a collection of objects which are descendents of the
 122    #PObject# class. It is implemeted as a doubly linked list.
 123
 124    The implementation of a list allows very fast inserting and deleting of
 125    objects in the collection, but has severe penalties for random access. All
 126    object access should be done sequentially to avoid these speed penalties.
 127
 128    The class remembers the last accessed element. This state information is
 129    used to optimise access by the "virtual array" model of collections. If
 130    access via ordinal index is made sequentially there is little overhead.
 131
 132    The PAbstractList class would very rarely be descended from directly by
 133    the user. The #PDECLARE_LIST# and #PLIST# macros would normally
 134    be used to create descendent classes. They will instantiate the template
 135    based on #PList# or directly declare and define the class (using
 136    inline functions) if templates are not being used.
 137
 138    The #PList# class or #PDECLARE_LIST# macro will define the
 139    correctly typed operators for subscript access (#operator[]#).
 140  */
 141 class PAbstractList : public PCollection
 142 {
 143   PCONTAINERINFO(PAbstractList, PCollection);
 144
 145   public:
 146   /**@name Construction */
 147   //@{
 148     /**Create a new, empty, list.
 149
 150        Note that by default, objects placed into the list will be deleted when
 151        removed or when all references to the list are destroyed.
 152      */
 153     PINLINE PAbstractList();
 154   //@}
 155
 156   // Overrides from class PObject
 157     /**Get the relative rank of the two lists. The following algorithm is
 158        employed for the comparison:
 159 \begin{description}
 160        \item[#EqualTo#] if the two lists are identical in length
 161        and each objects values, not pointer, are equal.
 162
 163        \item[#LessThan#] if the instances object value at an
 164        ordinal position is less than the corresponding objects value in the
 165        #obj# parameters list.
 166
 167        This is also returned if all objects are equal and the instances list
 168        length is less than the #obj# parameters list length.
 169
 170        \item[#GreaterThan#] if the instances object value at an
 171        ordinal position is greater than the corresponding objects value in the
 172        #obj# parameters list.
 173
 174        This is also returned if all objects are equal and the instances list
 175        length is greater than the #obj# parameters list length.
 176 \end{description}
 177
 178        @return
 179        comparison of the two objects, #EqualTo# for same,
 180        #LessThan# for #obj# logically less than the
 181        object and #GreaterThan# for #obj# logically
 182        greater than the object.
 183      */
 184     virtual Comparison Compare(const PObject & obj) const;
 185
 186   /**@name Overrides from class PContainer */
 187   //@{
 188     /**This function is meaningless for lists. The size of the collection is
 189        determined by the addition and removal of objects. The size cannot be
 190        set in any other way.
 191
 192        @return
 193        Always TRUE.
 194      */
 195     virtual BOOL SetSize(
 196       PINDEX newSize  /// New size for the list, this is ignored.
 197     );
 198   //@}
 199
 200   /**@name Overrides from class PCollection */
 201   //@{
 202     /**Append a new object to the collection. This places a new link at the
 203        "tail" of the list.
 204
 205        @return
 206        index of the newly added object.
 207      */
 208     virtual PINDEX Append(
 209       PObject * obj   /// New object to place into the collection.
 210     );
 211
 212     /**Insert a new object immediately before the specified object. If the
 213        object to insert before is not in the collection then the equivalent of
 214        the #Append()# function is performed.
 215
 216        Note that the object values are compared for the search of the
 217        #before# parameter, not the pointers. So the objects in the
 218        collection must correctly implement the #PObject::Compare()#
 219        function.
 220
 221        @return
 222        index of the newly inserted object.
 223      */
 224     virtual PINDEX Insert(
 225       const PObject & before,   /// Object value to insert before.
 226       PObject * obj             /// New object to place into the collection.
 227     );
 228
 229     /**Insert a new object at the specified ordinal index. If the index is
 230        greater than the number of objects in the collection then the
 231        equivalent of the #Append()# function is performed.
 232
 233        @return
 234        index of the newly inserted object.
 235      */
 236     virtual PINDEX InsertAt(
 237       PINDEX index,   /// Index position in collection to place the object.
 238       PObject * obj   /// New object to place into the collection.
 239     );
 240
 241     /**Remove the object from the collection. If the AllowDeleteObjects option
 242        is set then the object is also deleted.
 243
 244        @return
 245        TRUE if the object was in the collection.
 246      */
 247     virtual BOOL Remove(
 248       const PObject * obj   /// Existing object to remove from the collection.
 249     );
 250
 251     /**Remove the object at the specified ordinal index from the collection.
 252        If the AllowDeleteObjects option is set then the object is also deleted.
 253
 254        Note if the index is beyond the size of the collection then the
 255        function will assert.
 256
 257        @return
 258        pointer to the object being removed, or NULL if it was deleted.
 259      */
 260     virtual PObject * RemoveAt(
 261       PINDEX index   /// Index position in collection to place the object.
 262     );
 263
 264     /**Set the object at the specified ordinal position to the new value. This
 265        will overwrite the existing entry.
 266        This method will NOT delete the old object independently of the
 267        AllowDeleteObjects option. Use #ReplaceAt()# instead.
 268
 269        Note if the index is beyond the size of the collection then the
 270        function will assert.
 271
 272        @return
 273        TRUE if the object was successfully added.
 274      */
 275     virtual BOOL SetAt(
 276       PINDEX index,   /// Index position in collection to set.
 277       PObject * val   /// New value to place into the collection.
 278     );
 279
 280     /**Set the object at the specified ordinal position to the new value. This
 281        will overwrite the existing entry. If the AllowDeleteObjects option is
 282        set then the old object is also deleted.
 283
 284        Note if the index is beyond the size of the collection then the
 285        function will assert.
 286
 287        @return
 288        TRUE if the object was successfully replaced.
 289      */
 290     virtual BOOL ReplaceAt(
 291       PINDEX index,   /// Index position in collection to set.
 292       PObject * val   /// New value to place into the collection.
 293     );
 294
 295     /**Get the object at the specified ordinal position. If the index was
 296        greater than the size of the collection then NULL is returned.
 297
 298        The object accessed in this way is remembered by the class and further
 299        access will be fast. Access to elements one either side of that saved
 300        element, and the head and tail of the list, will always be fast.
 301
 302        @return
 303        pointer to object at the specified index.
 304      */
 305     virtual PObject * GetAt(
 306       PINDEX index  // Index position in the collection of the object.
 307     ) const;
 308
 309     /**Search the collection for the specific instance of the object. The
 310        object pointers are compared, not the values. A simple linear search
 311        from "head" of the list is performed.
 312
 313        @return
 314        ordinal index position of the object, or P_MAX_INDEX.
 315      */
 316     virtual PINDEX GetObjectsIndex(
 317       const PObject * obj  /// Object to find.
 318     ) const;
 319
 320     /**Search the collection for the specified value of the object. The object
 321        values are compared, not the pointers.  So the objects in the
 322        collection must correctly implement the #PObject::Compare()#
 323        function. A simple linear search from "head" of the list is performed.
 324
 325        @return
 326        ordinal index position of the object, or P_MAX_INDEX.
 327      */
 328     virtual PINDEX GetValuesIndex(
 329       const PObject & obj  /// Object to find value of.
 330     ) const;
 331   //@}
 332
 333
 334   protected:
 335     /**Get the object at the specified ordinal position. If the index was
 336        greater than the size of the collection then this asserts.
 337
 338        The object accessed in this way is remembered by the class and further
 339        access will be fast. Access to elements one either side of that saved
 340        element, and the head and tail of the list, will always be fast.
 341
 342        @return
 343        reference to object at the specified index.
 344      */
 345     PINLINE PObject & GetReferenceAt(
 346       PINDEX index  /// Ordinal index of the list element to set as current.
 347     ) const;
 348
 349     /**Move the internal "cursor" to the index position specified. This
 350        function will optimise the sequential move taking into account the
 351        previous current position and the position at the head and tail of the
 352        list. Whichever of these three points is closes is used as the starting
 353        point for a sequential move to the required index.
 354
 355        @return
 356        TRUE if the index could be set as the current element.
 357      */
 358     BOOL SetCurrent(
 359       PINDEX index  /// Ordinal index of the list element to set as current.
 360     ) const;
 361
 362     class Element {
 363       public:
 364         Element(PObject * theData);
 365         Element * prev;
 366         Element * next;
 367         PObject * data;
 368     };
 369
 370     class Info {
 371       public:
 372         Info() { head = tail = lastElement = NULL; }
 373         Element * head;
 374         Element * tail;
 375         Element * lastElement;
 376         PINDEX    lastIndex;
 377     } * info;
 378 };
 379
 380
 381 #ifdef PHAS_TEMPLATES
 382
 383 /**This template class maps the PAbstractList to a specific object type. The
 384    functions in this class primarily do all the appropriate casting of types.
 385
 386    Note that if templates are not used the #PDECLARE_LIST# macro will
 387    simulate the template instantiation.
 388  */
 389 template <class T> class PList : public PAbstractList
 390 {
 391   PCLASSINFO(PList, PAbstractList);
 392
 393   public:
 394   /**@name Construction */
 395   //@{
 396     /**Create a new, empty, list.
 397
 398        Note that by default, objects placed into the list will be deleted when
 399        removed or when all references to the list are destroyed.
 400      */
 401     PList()
 402       : PAbstractList() { }
 403   //@}
 404
 405   /**@name Overrides from class PObject */
 406   //@{
 407     /**Make a complete duplicate of the list. Note that all objects in the
 408        array are also cloned, so this will make a complete copy of the list.
 409      */
 410     virtual PObject * Clone() const
 411       { return PNEW PList(0, this); }
 412   //@}
 413
 414   /**@name New functions for class */
 415   //@{
 416     /**Retrieve a reference  to the object in the list. If there was not an
 417        object at that ordinal position or the index was beyond the size of the
 418        array then the function asserts.
 419
 420        The object accessed in this way is remembered by the class and further
 421        access will be fast. Access to elements one either side of that saved
 422        element, and the head and tail of the list, will always be fast.
 423
 424        @return
 425        reference to the object at #index# position.
 426      */
 427     T & operator[](PINDEX index) const
 428       { return (T &)GetReferenceAt(index); }
 429   //@}
 430
 431   protected:
 432     PList(int dummy, const PList * c)
 433       : PAbstractList(dummy, c) { }
 434 };
 435
 436
 437 /**Declare a list class.
 438    This macro is used to declare a descendent of PAbstractList class,
 439    customised for a particular object type {\bf T}. This macro closes the
 440    class declaration off so no additional members can be added.
 441
 442    If the compilation is using templates then this macro produces a typedef
 443    of the #PList# template class.
 444
 445    See the #PList# class and #PDECLARE_LIST# macro for more
 446    information.
 447  */
 448 #define PLIST(cls, T) typedef PList<T> cls
 449
 450 /**Begin declaration of list class.
 451    This macro is used to declare a descendent of PAbstractList class,
 452    customised for a particular object type {\bf T}.
 453
 454    If the compilation is using templates then this macro produces a descendent
 455    of the #PList# template class. If templates are not being used then the
 456    macro defines a set of inline functions to do all casting of types. The
 457    resultant classes have an identical set of functions in either case.
 458
 459    See the #PList# and #PAbstractList# classes for more information.
 460  */
 461 #define PDECLARE_LIST(cls, T) \
 462   PLIST(cls##_PTemplate, T); \
 463   PDECLARE_CLASS(cls, cls##_PTemplate) \
 464   protected: \
 465     cls(int dummy, const cls * c) \
 466       : cls##_PTemplate(dummy, c) { } \
 467   public: \
 468     cls() \
 469       : cls##_PTemplate() { } \
 470     virtual PObject * Clone() const \
 471       { return PNEW cls(0, this); } \
 472
 473
 474 /**This template class maps the PAbstractList to a specific object type, and
 475    adds functionality that allows the list to be used as a first in first out
 476    queue. The functions in this class primarily do all the appropriate casting
 477    of types.
 478
 479    By default, objects placed into the set will {\bf not} be deleted when
 480    removed or when all references to the set are destroyed. This is different
 481    from the default on most collection classes.
 482
 483    Note that if templates are not used the #PDECLARE_QUEUE# macro will
 484    simulate the template instantiation.
 485  */
 486 template <class T> class PQueue : public PAbstractList
 487 {
 488   PCLASSINFO(PQueue, PAbstractList);
 489
 490   public:
 491   /**@name Construction */
 492   //@{
 493     /**Create a new, empty, queue.
 494
 495        Note that by default, objects placed into the queue will {\bf not} be
 496        deleted when removed or when all references to the queue are destroyed.
 497        This is different from the default on most collection classes.
 498      */
 499     PQueue()
 500       : PAbstractList() { DisallowDeleteObjects(); }
 501   //@}
 502
 503   /**@name Overrides from class PObject */
 504   //@{
 505     /**Make a complete duplicate of the list. Note that all objects in the
 506        array are also cloned, so this will make a complete copy of the list.
 507      */
 508     virtual PObject * Clone() const
 509       { return PNEW PQueue(0, this); }
 510   //@}
 511
 512   /**@name New functions for class */
 513   //@{
 514     /**Add a new object to the queue. This places a new link at the "tail" of
 515        the list, which is the "in" side of the queue.
 516      */
 517     virtual void Enqueue(
 518       T * obj   /// Object to add to the queue.
 519     ) { PAbstractList::Append(obj); }
 520     /**Remove an object that was added to the queue.
 521
 522        @return
 523        first object added to the queue or NULL if queue empty.
 524      */
 525     virtual T * Dequeue()
 526       { if (GetSize() == 0) return NULL; else return (T *)PAbstractList::RemoveAt(0);}
 527   //@}
 528
 529   protected:
 530     PQueue(int dummy, const PQueue * c)
 531       : PAbstractList(dummy, c)
 532       { reference->deleteObjects = c->reference->deleteObjects; }
 533 };
 534
 535
 536 /**Declare a queue class.
 537    This macro is used to declare a descendent of PAbstractList class,
 538    customised for a particular object type {\bf T}, and adds functionality
 539    that allows the list to be used as a first in first out queue. This macro
 540    closes the class declaration off so no additional members can be added.
 541
 542    If the compilation is using templates then this macro produces a typedef
 543    of the #PQueue# template class.
 544
 545    See the #PList# class and #PDECLARE_QUEUE# macro for more
 546    information.
 547  */
 548 #define PQUEUE(cls, T) typedef PQueue<T> cls
 549
 550
 551 /**Begin declataion of a queue class.
 552    This macro is used to declare a descendent of PAbstractList class,
 553    customised for a particular object type {\bf T}, and adds functionality
 554    that allows the list to be used as a first in first out queue.
 555
 556    If the compilation is using templates then this macro produces a descendent
 557    of the #PQueue# template class. If templates are not being used then
 558    the macro defines a set of inline functions to do all casting of types. The
 559    resultant classes have an identical set of functions in either case.
 560
 561    See the #PQueue# and #PAbstractList# classes for more information.
 562  */
 563 #define PDECLARE_QUEUE(cls, T) \
 564   PQUEUE(cls##_PTemplate, T); \
 565   PDECLARE_CLASS(cls, cls##_PTemplate) \
 566   protected: \
 567     cls(int dummy, const cls * c) \
 568       : cls##_PTemplate(dummy, c) { } \
 569   public: \
 570     cls() \
 571       : cls##_PTemplate() { } \
 572     virtual PObject * Clone() const \
 573       { return PNEW cls(0, this); } \
 574
 575
 576 /**This template class maps the PAbstractList to a specific object type, and
 577    adds functionality that allows the list to be used as a last in first out
 578    stack. The functions in this class primarily do all the appropriate casting
 579    of types.
 580
 581    By default, objects placed into the set will {\bf not} be deleted when
 582    removed or when all references to the set are destroyed. This is different
 583    from the default on most collection classes.
 584
 585    Note that if templates are not used the #PDECLARE_STACK# macro will
 586    simulate the template instantiation.
 587  */
 588 template <class T> class PStack : public PAbstractList
 589 {
 590   PCLASSINFO(PStack, PAbstractList);
 591
 592   public:
 593   /**@name Construction */
 594   //@{
 595     /**Create a new, empty, stack.
 596
 597        Note that by default, objects placed into the stack will {\bf not} be
 598        deleted when removed or when all references to the stack are destroyed.
 599        This is different from the default on most collection classes.
 600      */
 601     PStack()
 602       : PAbstractList() { DisallowDeleteObjects(); }
 603   //@}
 604
 605   /**@name Overrides from class PObject */
 606   //@{
 607     /**Make a complete duplicate of the stack. Note that all objects in the
 608        array are also cloned, so this will make a complete copy of the stack.
 609      */
 610     virtual PObject * Clone() const
 611       { return PNEW PStack(0, this); }
 612   //@}
 613
 614   /**@name New functions for class */
 615   //@{
 616     /**Add an object to the stack. This object will be on "top" of the stack
 617        and will be the object returned by the #Pop()#
 618        function.
 619      */
 620     virtual void Push(
 621       T * obj    /// Object to add to the stack.
 622     ) { PAbstractList::InsertAt(0, obj); }
 623
 624     /**Remove the last object pushed onto the stack.
 625
 626        @return
 627        object on top of the stack.
 628      */
 629     virtual T * Pop()
 630       { return (T *)PAbstractList::RemoveAt(0); }
 631
 632     /**Get the element that is currently on top of the stack without removing
 633        it.
 634
 635        @return
 636        reference to object on top of the stack.
 637      */
 638     virtual T & Top()
 639       { PAssert(GetSize() > 0, PStackEmpty); return *(T *)GetAt(0); }
 640   //@}
 641
 642   protected:
 643     PStack(int dummy, const PStack * c)
 644       : PAbstractList(dummy, c)
 645       { reference->deleteObjects = c->reference->deleteObjects; }
 646 };
 647
 648
 649 /**Declare a stack class.
 650    This macro is used to declare a descendent of PAbstractList class,
 651    customised for a particular object type {\bf T}, and adds functionality
 652    that allows the list to be used as a last in first out stack. This macro
 653    closes the class declaration off so no additional members can be added.
 654
 655    If the compilation is using templates then this macro produces a typedef
 656    of the #PStack# template class.
 657
 658    See the #PStack# class and #PDECLARE_STACK# macro for more
 659    information.
 660  */
 661 #define PSTACK(cls, T) typedef PStack<T> cls
 662
 663
 664 /**Begin declaration of a stack class.
 665    This macro is used to declare a descendent of PAbstractList class,
 666    customised for a particular object type {\bf T}, and adds functionality
 667    that allows the list to be used as a last in first out stack.
 668
 669    If the compilation is using templates then this macro produces a descendent
 670    of the #PStack# template class. If templates are not being used then
 671    the macro defines a set of inline functions to do all casting of types. The
 672    resultant classes have an identical set of functions in either case.
 673
 674    See the #PStack# and #PAbstractList# classes for more information.
 675  */
 676 #define PDECLARE_STACK(cls, T) \
 677   PSTACK(cls##_PTemplate, T); \
 678   PDECLARE_CLASS(cls, cls##_PTemplate) \
 679   protected: \
 680     cls(int dummy, const cls * c) \
 681       : cls##_PTemplate(dummy, c) { } \
 682   public: \
 683     cls() \
 684       : cls##_PTemplate() { } \
 685     virtual PObject * Clone() const \
 686       { return PNEW cls(0, this); } \
 687
 688
 689 #else // PHAS_TEMPLATES
 690
 691
 692 #define PLIST(cls, T) \
 693   class cls : public PAbstractList { \
 694   PCLASSINFO(cls, PAbstractList); \
 695   protected: \
 696     inline cls(int dummy, const cls * c) \
 697       : PAbstractList(dummy, c) { } \
 698   public: \
 699     inline cls() \
 700       : PAbstractList() { } \
 701     inline virtual PObject * Clone() const \
 702       { return PNEW cls(0, this); } \
 703     inline T & operator[](PINDEX index) const \
 704       { return (T &)GetReferenceAt(index); } \
 705   }
 706
 707 #define PDECLARE_LIST(cls, T) \
 708   PLIST(cls##_PTemplate, T); \
 709   PDECLARE_CLASS(cls, cls##_PTemplate) \
 710   protected: \
 711     cls(int dummy, const cls * c) \
 712       : cls##_PTemplate(dummy, c) { } \
 713   public: \
 714     cls() \
 715       : cls##_PTemplate() { } \
 716     virtual PObject * Clone() const \
 717       { return PNEW cls(0, this); } \
 718
 719
 720 #define PQUEUE(cls, T) \
 721   class cls : public PAbstractList { \
 722   PCLASSINFO(cls, PAbstractList); \
 723   protected: \
 724     inline cls(int dummy, const cls * c) \
 725       : PAbstractList(dummy, c) \
 726       { reference->deleteObjects = c->reference->deleteObjects; } \
 727   public: \
 728     inline cls() \
 729       : PAbstractList() { DisallowDeleteObjects(); } \
 730     inline virtual PObject * Clone() const \
 731       { return PNEW cls(0, this); } \
 732     virtual inline void Enqueue(T * t) \
 733       { PAbstractList::Append(t); } \
 734     virtual inline T * Dequeue() \
 735       { if (GetSize() == 0) return NULL; else return (T *)PAbstractList::RemoveAt(0);} \
 736   }
 737
 738 #define PDECLARE_QUEUE(cls, T) \
 739   PQUEUE(cls##_PTemplate, T); \
 740   PDECLARE_CLASS(cls, cls##_PTemplate) \
 741   protected: \
 742     cls(int dummy, const cls * c) \
 743       : cls##_PTemplate(dummy, c) { } \
 744   public: \
 745     cls() \
 746       : cls##_PTemplate() { } \
 747     virtual PObject * Clone() const \
 748       { return PNEW cls(0, this); } \
 749
 750 #define PSTACK(cls, T) \
 751   class cls : public PAbstractList { \
 752   PCLASSINFO(cls, PAbstractList); \
 753   protected: \
 754     inline cls(int dummy, const cls * c) \
 755       : PAbstractList(dummy, c) \
 756       { reference->deleteObjects = c->reference->deleteObjects; } \
 757   public: \
 758     inline cls() \
 759       : PAbstractList() { DisallowDeleteObjects(); } \
 760     inline virtual PObject * Clone() const \
 761       { return PNEW cls(0, this); } \
 762     virtual inline void Push(T * t) \
 763       { PAbstractList::InsertAt(0, t); } \
 764     virtual inline T * Pop() \
 765       { PAssert(GetSize() > 0, PStackEmpty); return (T *)PAbstractList::RemoveAt(0); } \
 766     virtual inline T & Top() \
 767       { PAssert(GetSize() > 0, PStackEmpty); return *(T *)GetAt(0); } \
 768   }
 769
 770 #define PDECLARE_STACK(cls, T) \
 771   PSTACK(cls##_PTemplate, T); \
 772   PDECLARE_CLASS(cls, cls##_PTemplate) \
 773   protected: \
 774     cls(int dummy, const cls * c) \
 775       : cls##_PTemplate(dummy, c) { } \
 776   public: \
 777     cls() \
 778       : cls##_PTemplate() { } \
 779     virtual PObject * Clone() const \
 780       { return PNEW cls(0, this); } \
 781
 782
 783 #endif // PHAS_TEMPLATES
 784
 785
 786 ///////////////////////////////////////////////////////////////////////////////
 787 // Sorted List of PObjects
 788
 789 /**This class is a collection of objects which are descendents of the
 790    #PObject# class. It is implemeted as a Red-Black binary tree to
 791    maintain the objects in rank order. Note that this requires that the
 792    #PObject::Compare()# function be fully implemented oin objects
 793    contained in the collection.
 794
 795    The implementation of a sorted list allows fast inserting and deleting as
 796    well as random access of objects in the collection. As the objects are being
 797    kept sorted, "fast" is a relative term. All operations take o(lg n) unless
 798    a particular object is repeatedly accessed.
 799
 800    The class remembers the last accessed element. This state information is
 801    used to optimise access by the "virtual array" model of collections. If
 802    repeated access via ordinal index is made there is little overhead. All
 803    other access incurs a minimum overhead, but not insignificant.
 804
 805    The PAbstractSortedList class would very rarely be descended from directly
 806    by the user. The #PDECLARE_LIST# and #PLIST# macros would normally
 807    be used to create descendent classes. They will instantiate the template
 808    based on #PSortedList# or directly declare and define the class (using
 809    inline functions) if templates are not being used.
 810
 811    The #PSortedList# class or #PDECLARE_SORTED_LIST# macro will
 812    define the correctly typed operators for subscript access
 813    (#operator[]#).
 814  */
 815 class PAbstractSortedList : public PCollection
 816 {
 817   PCONTAINERINFO(PAbstractSortedList, PCollection);
 818
 819   public:
 820   /**@name Construction */
 821   //@{
 822     /**Create a new, empty, sorted list.
 823
 824        Note that by default, objects placed into the list will be deleted when
 825        removed or when all references to the list are destroyed.
 826      */
 827     PAbstractSortedList();
 828   //@}
 829
 830   /**@name Overrides from class PObject */
 831   //@{
 832     /**Get the relative rank of the two lists. The following algorithm is
 833        employed for the comparison:
 834 \begin{descriptions}
 835        \item[#EqualTo#] if the two lists are identical in length
 836        and each objects values, not pointer, are equal.
 837
 838        \item[#LessThan#] if the instances object value at an
 839        ordinal position is less than the corresponding objects value in the
 840        #obj# parameters list.
 841
 842        This is also returned if all objects are equal and the instances list
 843        length is less than the #obj# parameters list length.
 844
 845        \item[#GreaterThan#] if the instances object value at an
 846        ordinal position is greater than the corresponding objects value in the
 847        #obj# parameters list.
 848
 849        This is also returned if all objects are equal and the instances list
 850        length is greater than the #obj# parameters list length.
 851 \end{descriptions}
 852
 853        @return
 854        comparison of the two objects, #EqualTo# for same,
 855        #LessThan# for #obj# logically less than the
 856        object and #GreaterThan# for #obj# logically
 857        greater than the object.
 858      */
 859     virtual Comparison Compare(const PObject & obj) const;
 860   //@}
 861
 862   /**@name Overrides from class PContainer */
 863   //@{
 864     /**This function is meaningless for lists. The size of the collection is
 865        determined by the addition and removal of objects. The size cannot be
 866        set in any other way.
 867
 868        @return
 869        Always TRUE.
 870      */
 871     virtual BOOL SetSize(
 872       PINDEX newSize  // New size for the sorted list, this is ignored.
 873     );
 874   //@}
 875
 876   /**@name Overrides from class PCollection */
 877   //@{
 878     /**Add a new object to the collection. The object is always placed in the
 879        correct ordinal position in the list. It is not placed at the "end".
 880
 881        @return
 882        index of the newly added object.
 883      */
 884     virtual PINDEX Append(
 885       PObject * obj   // New object to place into the collection.
 886     );
 887
 888     /**Add a new object to the collection.
 889
 890        The object is always placed in the correct ordinal position in the list.
 891        It is not placed at the specified position. The #before#
 892        parameter is ignored.
 893
 894        @return
 895        index of the newly inserted object.
 896      */
 897     virtual PINDEX Insert(
 898       const PObject & before,   // Object value to insert before.
 899       PObject * obj             // New object to place into the collection.
 900     );
 901
 902     /**Add a new object to the collection.
 903
 904        The object is always placed in the correct ordinal position in the list.
 905        It is not placed at the specified position. The #index#
 906        parameter is ignored.
 907
 908        @return
 909        index of the newly inserted object.
 910      */
 911     virtual PINDEX InsertAt(
 912       PINDEX index,   // Index position in collection to place the object.
 913       PObject * obj   // New object to place into the collection.
 914     );
 915
 916     /**Remove the object from the collection. If the AllowDeleteObjects option
 917        is set then the object is also deleted.
 918
 919        Note that the comparison for searching for the object in collection is
 920        made by pointer, not by value. Thus the parameter must point to the
 921        same instance of the object that is in the collection.
 922
 923        @return
 924        TRUE if the object was in the collection.
 925      */
 926     virtual BOOL Remove(
 927       const PObject * obj   // Existing object to remove from the collection.
 928     );
 929
 930     /**Remove the object at the specified ordinal index from the collection.
 931        If the AllowDeleteObjects option is set then the object is also deleted.
 932
 933        Note if the index is beyond the size of the collection then the
 934        function will assert.
 935
 936        @return
 937        pointer to the object being removed, or NULL if it was deleted.
 938      */
 939     virtual PObject * RemoveAt(
 940       PINDEX index   // Index position in collection to place the object.
 941     );
 942
 943     /**Remove all of the elements in the collection. This operates by
 944        continually calling #RemoveAt()# until there are no objects left.
 945
 946        The objects are removed from the last, at index
 947        #(GetSize()-1)# toward the first at index zero.
 948      */
 949     virtual void RemoveAll();
 950
 951     /**This method simply returns FALSE as the list order is mantained by the
 952        class. Kept to mimic #PAbstractList# interface.
 953
 954        @return
 955        FALSE allways
 956      */
 957     virtual BOOL SetAt(
 958       PINDEX index,   // Index position in collection to set.
 959       PObject * val   // New value to place into the collection.
 960     );
 961
 962     /**Get the object at the specified ordinal position. If the index was
 963        greater than the size of the collection then NULL is returned.
 964
 965        @return
 966        pointer to object at the specified index.
 967      */
 968     virtual PObject * GetAt(
 969       PINDEX index  // Index position in the collection of the object.
 970     ) const;
 971
 972     /**Search the collection for the specific instance of the object. The
 973        object pointers are compared, not the values. A binary search is
 974        employed to locate the entry.
 975
 976        Note that that will require value comparisons to be made to find the
 977        equivalent entry and then a final check is made with the pointers to
 978        see if they are the same instance.
 979
 980        @return
 981        ordinal index position of the object, or P_MAX_INDEX.
 982      */
 983     virtual PINDEX GetObjectsIndex(
 984       const PObject * obj
 985     ) const;
 986
 987     /**Search the collection for the specified value of the object. The object
 988        values are compared, not the pointers.  So the objects in the
 989        collection must correctly implement the #PObject::Compare()#
 990        function. A binary search is employed to locate the entry.
 991
 992        @return
 993        ordinal index position of the object, or P_MAX_INDEX.
 994      */
 995     virtual PINDEX GetValuesIndex(
 996       const PObject & obj
 997     ) const;
 998   //@}
 999
1000
1001     friend class Element;
1002
1003   protected:
1004     struct Element {
1005       Element * parent;
1006       Element * left;
1007       Element * right;
1008       PObject * data;
1009       PINDEX subTreeSize;
1010       enum { Red, Black } colour;
1011     };
1012
1013     struct Info {
1014       Element * root;
1015       Element * lastElement;
1016       PINDEX    lastIndex;
1017       Element   nil;
1018     } * info;
1019
1020     // New functions for class
1021     void RemoveElement(Element * node);
1022     void LeftRotate(Element * node);
1023     void RightRotate(Element * node);
1024     void DeleteSubTrees(Element * node, BOOL deleteObject);
1025     Element * Successor(const Element * node) const;
1026     Element * Predecessor(const Element * node) const;
1027     Element * OrderSelect(Element * node, PINDEX index) const;
1028     PINDEX ValueSelect(const Element * node, const PObject & obj, const Element ** lastElement) const;
1029 };
1030
1031
1032 #ifdef PHAS_TEMPLATES
1033
1034 /**This template class maps the PAbstractSortedList to a specific object type.
1035    The functions in this class primarily do all the appropriate casting of
1036    types.
1037
1038    Note that if templates are not used the #PDECLARE_SORTED_LIST# macro
1039    will simulate the template instantiation.
1040  */
1041 template <class T> class PSortedList : public PAbstractSortedList
1042 {
1043   PCLASSINFO(PSortedList, PAbstractSortedList);
1044
1045   public:
1046   /**@name Construction */
1047   //@{
1048     /**Create a new, empty, sorted list.
1049
1050        Note that by default, objects placed into the list will be deleted when
1051        removed or when all references to the list are destroyed.
1052      */
1053     PSortedList()
1054       : PAbstractSortedList() { }
1055   //@}
1056
1057   /**@name Overrides from class PObject */
1058   //@{
1059     /**Make a complete duplicate of the list. Note that all objects in the
1060        array are also cloned, so this will make a complete copy of the list.
1061      */
1062     virtual PObject * Clone() const
1063       { return PNEW PSortedList(0, this); }
1064   //@}
1065
1066   /**@name New functions for class */
1067   //@{
1068     /**Retrieve a reference  to the object in the list. If there was not an
1069        object at that ordinal position or the index was beyond the size of the
1070        array then the function asserts.
1071
1072        The object accessed in this way is remembered by the class and further
1073        access will be fast.
1074
1075        @return
1076        reference to the object at #index# position.
1077      */
1078     T & operator[](PINDEX index) const
1079       { return *(T *)GetAt(index); }
1080   //@}
1081
1082   protected:
1083     PSortedList(int dummy, const PSortedList * c)
1084       : PAbstractSortedList(dummy, c) { }
1085 };
1086
1087
1088 /**Declare a sorted list class.
1089    This macro is used to declare a descendent of PAbstractSortedList class,
1090    customised for a particular object type {\bf T}. This macro closes the
1091    class declaration off so no additional members can be added.
1092
1093    If the compilation is using templates then this macro produces a typedef
1094    of the #PSortedList# template class.
1095
1096    See the #PSortedList# class and #PDECLARE_SORTED_LIST# macro for
1097    more information.
1098  */
1099 #define PSORTED_LIST(cls, T) typedef PSortedList<T> cls
1100
1101
1102 /**Begin declaration of a sorted list class.
1103    This macro is used to declare a descendent of PAbstractSortedList class,
1104    customised for a particular object type {\bf T}.
1105
1106    If the compilation is using templates then this macro produces a descendent
1107    of the #PSortedList# template class. If templates are not being used
1108    then the macro defines a set of inline functions to do all casting of types.
1109    The resultant classes have an identical set of functions in either case.
1110
1111    See the #PSortedList# and #PAbstractSortedList# classes for more
1112    information.
1113  */
1114 #define PDECLARE_SORTED_LIST(cls, T) \
1115   PSORTED_LIST(cls##_PTemplate, T); \
1116   PDECLARE_CLASS(cls, cls##_PTemplate) \
1117   protected: \
1118     cls(int dummy, const cls * c) \
1119       : cls##_PTemplate(dummy, c) { } \
1120   public: \
1121     cls() \
1122       : cls##_PTemplate() { } \
1123     virtual PObject * Clone() const \
1124       { return PNEW cls(0, this); } \
1125
1126
1127 #else // PHAS_TEMPLATES
1128
1129
1130 #define PSORTED_LIST(cls, T) \
1131   class cls : public PAbstractSortedList { \
1132   PCLASSINFO(cls, PAbstractSortedList); \
1133   protected: \
1134     inline cls(int dummy, const cls * c) \
1135       : PAbstractSortedList(dummy, c) { } \
1136   public: \
1137     inline cls() \
1138       : PAbstractSortedList() { } \
1139     inline virtual PObject * Clone() const \
1140       { return PNEW cls(0, this); } \
1141     inline T & operator[](PINDEX index) const \
1142       { return *(T *)GetAt(index); } \
1143   }
1144
1145 #define PDECLARE_SORTED_LIST(cls, T) \
1146   PSORTED_LIST(cls##_PTemplate, T); \
1147   PDECLARE_CLASS(cls, cls##_PTemplate) \
1148   protected: \
1149     cls(int dummy, const cls * c) \
1150       : cls##_PTemplate(dummy, c) { } \
1151   public: \
1152     cls() \
1153       : cls##_PTemplate() { } \
1154     virtual PObject * Clone() const \
1155       { return PNEW cls(0, this); } \
1156
1157
1158 #endif  // PHAS_TEMPLATES
1159
1160
1161 // End Of File ///////////////////////////////////////////////////////////////