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 * $Revision: 24177 $ 30 * $Author: rjongbloed $ 31 * $Date: 2010-04-05 06:52:04 -0500 (Mon, 05 Apr 2010) $ 32 */ 33 34 #ifndef PTLIB_LISTS_H 35 #define PTLIB_LISTS_H 36 37 #ifdef P_USE_PRAGMA 38 #pragma interface 39 #endif 40 41 42 /////////////////////////////////////////////////////////////////////////////// 43 // PList container class 44 45 struct PListElement 46 { 47 PListElement(PObject * theData); 48 PListElement * prev; 49 PListElement * next; 50 PObject * data; 51 52 PDECLARE_POOL_ALLOCATOR(); 53 }; 54 55 struct PListInfo 56 { PListInfoPListInfo57 PListInfo() { head = tail = NULL; } 58 PListElement * head; 59 PListElement * tail; 60 61 PDECLARE_POOL_ALLOCATOR(); 62 }; 63 64 /**This class is a collection of objects which are descendents of the 65 <code>PObject</code> class. It is implemeted as a doubly linked list. 66 67 The implementation of a list allows very fast inserting and deleting of 68 objects in the collection, but has severe penalties for random access. All 69 object access should be done sequentially to avoid these speed penalties. 70 71 The class remembers the last accessed element. This state information is 72 used to optimise access by the "virtual array" model of collections. If 73 access via ordinal index is made sequentially there is little overhead. 74 75 The PAbstractList class would very rarely be descended from directly by 76 the user. The <code>PDECLARE_LIST</code> and <code>PLIST</code> macros would normally 77 be used to create descendent classes. They will instantiate the template 78 based on <code>PList</code> or directly declare and define the class (using 79 inline functions) if templates are not being used. 80 81 The <code>PList</code> class or <code>PDECLARE_LIST</code> macro will define the 82 correctly typed operators for subscript access (operator[]). 83 */ 84 class PAbstractList : public PCollection 85 { 86 PCONTAINERINFO(PAbstractList, PCollection); 87 88 public: 89 /**@name Construction */ 90 //@{ 91 /**Create a new, empty, list. 92 93 Note that by default, objects placed into the list will be deleted when 94 removed or when all references to the list are destroyed. 95 */ 96 PINLINE PAbstractList(); 97 //@} 98 99 // Overrides from class PObject 100 /**Get the relative rank of the two lists. The following algorithm is 101 employed for the comparison: 102 103 \arg \c EqualTo if the two lists are identical in length 104 and each objects values, not pointer, are equal. 105 106 \arg \c LessThan if the instances object value at an 107 ordinal position is less than the corresponding objects value in the 108 <code>obj</code> parameters list. 109 110 This is also returned if all objects are equal and the instances list 111 length is less than the <code>obj</code> parameters list length. 112 113 \arg \c GreaterThan if the instances object value at an 114 ordinal position is greater than the corresponding objects value in the 115 <code>obj</code> parameters list. 116 117 This is also returned if all objects are equal and the instances list 118 length is greater than the <code>obj</code> parameters list length. 119 120 @return 121 comparison of the two objects, <code>EqualTo</code> for same, 122 <code>LessThan</code> for <code>obj</code> logically less than the 123 object and <code>GreaterThan</code> for <code>obj</code> logically 124 greater than the object. 125 */ 126 virtual Comparison Compare( 127 const PObject & obj ///< Object being compared to 128 ) const; 129 130 /**@name Overrides from class PContainer */ 131 //@{ 132 /**This function is meaningless for lists. The size of the collection is 133 determined by the addition and removal of objects. The size cannot be 134 set in any other way. 135 136 @return 137 Always true. 138 */ 139 virtual PBoolean SetSize( 140 PINDEX newSize ///< New size for the list, this is ignored. 141 ); 142 //@} 143 144 /**@name Overrides from class PCollection */ 145 //@{ 146 /**Append a new object to the collection. This places a new link at the 147 "tail" of the list. 148 149 @return 150 index of the newly added object. 151 */ 152 virtual PINDEX Append( 153 PObject * obj ///< New object to place into the collection. 154 ); 155 156 /**Insert a new object immediately before the specified object. If the 157 object to insert before is not in the collection then the equivalent of 158 the <code>Append()</code> function is performed. 159 160 Note that the object values are compared for the search of the 161 <code>before</code> parameter, not the pointers. So the objects in the 162 collection must correctly implement the <code>PObject::Compare()</code> 163 function. 164 165 @return 166 index of the newly inserted object. 167 */ 168 virtual PINDEX Insert( 169 const PObject & before, ///< Object value to insert before. 170 PObject * obj ///< New object to place into the collection. 171 ); 172 173 /**Insert a new object at the specified ordinal index. If the index is 174 greater than the number of objects in the collection then the 175 equivalent of the <code>Append()</code> function is performed. 176 177 @return 178 index of the newly inserted object. 179 */ 180 virtual PINDEX InsertAt( 181 PINDEX index, ///< Index position in collection to place the object. 182 PObject * obj ///< New object to place into the collection. 183 ); 184 185 /**Remove the object from the collection. If the AllowDeleteObjects option 186 is set then the object is also deleted. 187 188 @return 189 true if the object was in the collection. 190 */ 191 virtual PBoolean Remove( 192 const PObject * obj ///< Existing object to remove from the collection. 193 ); 194 195 /**Remove the object at the specified ordinal index from the collection. 196 If the AllowDeleteObjects option is set then the object is also deleted. 197 198 Note if the index is beyond the size of the collection then the 199 function will assert. 200 201 @return 202 pointer to the object being removed, or NULL if it was deleted. 203 */ 204 virtual PObject * RemoveAt( 205 PINDEX index ///< Index position in collection to place the object. 206 ); 207 208 /**Set the object at the specified ordinal position to the new value. This 209 will overwrite the existing entry. 210 This method will NOT delete the old object independently of the 211 AllowDeleteObjects option. Use <code>ReplaceAt()</code> instead. 212 213 Note if the index is beyond the size of the collection then the 214 function will assert. 215 216 @return 217 true if the object was successfully added. 218 */ 219 virtual PBoolean SetAt( 220 PINDEX index, ///< Index position in collection to set. 221 PObject * val ///< New value to place into the collection. 222 ); 223 224 /**Set the object at the specified ordinal position to the new value. This 225 will overwrite the existing entry. If the AllowDeleteObjects option is 226 set then the old object is also deleted. 227 228 Note if the index is beyond the size of the collection then the 229 function will assert. 230 231 @return 232 true if the object was successfully replaced. 233 */ 234 virtual PBoolean ReplaceAt( 235 PINDEX index, ///< Index position in collection to set. 236 PObject * val ///< New value to place into the collection. 237 ); 238 239 /**Get the object at the specified ordinal position. If the index was 240 greater than the size of the collection then NULL is returned. 241 242 The object accessed in this way is remembered by the class and further 243 access will be fast. Access to elements one either side of that saved 244 element, and the head and tail of the list, will always be fast. 245 246 @return 247 pointer to object at the specified index. 248 */ 249 virtual PObject * GetAt( 250 PINDEX index ///< Index position in the collection of the object. 251 ) const; 252 253 /**Search the collection for the specific instance of the object. The 254 object pointers are compared, not the values. A simple linear search 255 from "head" of the list is performed. 256 257 @return 258 ordinal index position of the object, or P_MAX_INDEX. 259 */ 260 virtual PINDEX GetObjectsIndex( 261 const PObject * obj ///< Object to find. 262 ) const; 263 264 /**Search the collection for the specified value of the object. The object 265 values are compared, not the pointers. So the objects in the 266 collection must correctly implement the <code>PObject::Compare()</code> 267 function. A simple linear search from "head" of the list is performed. 268 269 @return 270 ordinal index position of the object, or P_MAX_INDEX. 271 */ 272 virtual PINDEX GetValuesIndex( 273 const PObject & obj ///< Object to find value of. 274 ) const; 275 //@} 276 277 278 protected: 279 /**Get the object at the specified ordinal position. If the index was 280 greater than the size of the collection then this asserts. 281 282 The object accessed in this way is remembered by the class and further 283 access will be fast. Access to elements one either side of that saved 284 element, and the head and tail of the list, will always be fast. 285 286 @return 287 reference to object at the specified index. 288 */ 289 PINLINE PObject & GetReferenceAt( 290 PINDEX index ///< Ordinal index of the list element to set as current. 291 ) const; 292 293 /**Move the internal "cursor" to the index position specified. This 294 function will optimise the sequential move taking into account the 295 previous current position and the position at the head and tail of the 296 list. Whichever of these three points is closes is used as the starting 297 point for a sequential move to the required index. 298 299 @return 300 true if the index could be set as the current element. 301 */ 302 PBoolean SetCurrent( 303 PINDEX index, ///< Ordinal index of the list element to set as current. 304 PListElement * & lastElement ///< pointer to final element 305 ) const; 306 307 PObject * RemoveElement(PListElement * element); 308 309 // The types below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it 310 typedef PListElement Element; 311 PListInfo * info; 312 }; 313 314 315 /**This template class maps the PAbstractList to a specific object type. The 316 functions in this class primarily do all the appropriate casting of types. 317 318 Note that if templates are not used the <code>PDECLARE_LIST</code> macro will 319 simulate the template instantiation. 320 */ 321 template <class T> class PList : public PAbstractList 322 { 323 PCLASSINFO(PList, PAbstractList); 324 325 public: 326 /**@name Construction */ 327 //@{ 328 /**Create a new, empty, list. 329 330 Note that by default, objects placed into the list will be deleted when 331 removed or when all references to the list are destroyed. 332 */ PList()333 PList() 334 : PAbstractList() { } 335 //@} 336 337 /**@name Overrides from class PObject */ 338 //@{ 339 /**Make a complete duplicate of the list. Note that all objects in the 340 array are also cloned, so this will make a complete copy of the list. 341 */ Clone()342 virtual PObject * Clone() const 343 { return PNEW PList(0, this); } 344 //@} 345 346 /**@name Iterators */ 347 //@{ 348 class iterator_base : public std::iterator<std::bidirectional_iterator_tag, T> { 349 protected: iterator_base(PListElement * e)350 iterator_base(PListElement * e) : element(e) { } 351 PListElement * element; 352 Next()353 void Next() { element = PAssertNULL(element)->next; } Prev()354 void Prev() { element = PAssertNULL(element)->prev; } Ptr()355 T * Ptr() const { return (T *)PAssertNULL(element)->data; } 356 357 public: 358 bool operator==(const iterator_base & it) const { return element == it.element; } 359 bool operator!=(const iterator_base & it) const { return element != it.element; } 360 }; 361 362 class iterator : public iterator_base { 363 public: iterator_base(e)364 iterator(PListElement * e = NULL) : iterator_base(e) { } 365 366 iterator operator++() { iterator_base::Next(); return *this; } 367 iterator operator--() { iterator_base::Prev(); return *this; } 368 iterator operator++(int) { iterator it = *this; iterator_base::Next(); return it; } 369 iterator operator--(int) { iterator it = *this; iterator_base::Prev(); return it; } 370 371 T * operator->() const { return iterator_base::Ptr(); } 372 T & operator* () const { return *iterator_base::Ptr(); } 373 }; 374 begin()375 iterator begin() { return info->head; } end()376 iterator end() { return iterator(); } rbegin()377 iterator rbegin() { return info->tail; } rend()378 iterator rend() { return iterator(); } 379 380 381 class const_iterator : public iterator_base { 382 public: iterator_base(e)383 const_iterator(PListElement * e = NULL) : iterator_base(e) { } 384 385 const_iterator operator++() { iterator_base::Next(); return *this; } 386 const_iterator operator--() { iterator_base::Prev(); return *this; } 387 const_iterator operator++(int) { const_iterator it = *this; iterator_base::Next(); return it; } 388 const_iterator operator--(int) { const_iterator it = *this; iterator_base::Prev(); return it; } 389 390 const T * operator->() const { return iterator_base::Ptr(); } 391 const T & operator* () const { return *iterator_base::Ptr(); } 392 }; 393 begin()394 const_iterator begin() const { return info->head; } end()395 const_iterator end() const { return const_iterator(); } rbegin()396 const_iterator rbegin() const { return info->tail; } rend()397 const_iterator rend() const { return iterator(); } 398 front()399 T & front() const { return *(T *)PAssertNULL(info->head)->data; } back()400 T & back() const { return *(T *)PAssertNULL(info->tail)->data; } erase(const iterator & it)401 void erase(const iterator & it) { Remove(&*it); } erase(const const_iterator & it)402 void erase(const const_iterator & it) { Remove(&*it); } 403 404 typedef T value_type; 405 //@} 406 407 /**@name New functions for class */ 408 //@{ 409 /**Retrieve a reference to the object in the list. If there was not an 410 object at that ordinal position or the index was beyond the size of the 411 array then the function asserts. 412 413 The object accessed in this way is remembered by the class and further 414 access will be fast. Access to elements one either side of that saved 415 element, and the head and tail of the list, will always be fast. 416 417 @return 418 reference to the object at <code>index</code> position. 419 */ 420 T & operator[]( 421 PINDEX index ///< Index for entry 422 ) const { return (T &)GetReferenceAt(index); } 423 //@} 424 425 protected: PList(int dummy,const PList * c)426 PList(int dummy, const PList * c) 427 : PAbstractList(dummy, c) { } 428 }; 429 430 431 /**Declare a list class. 432 This macro is used to declare a descendent of PAbstractList class, 433 customised for a particular object type <b>T</b>. This macro closes the 434 class declaration off so no additional members can be added. 435 436 If the compilation is using templates then this macro produces a typedef 437 of the <code>PList</code> template class. 438 439 See the <code>PList</code> class and <code>PDECLARE_LIST</code> macro for more 440 information. 441 */ 442 #define PLIST(cls, T) typedef PList<T> cls 443 444 /**Begin declaration of list class. 445 This macro is used to declare a descendent of PAbstractList class, 446 customised for a particular object type <b>T</b>. 447 448 If the compilation is using templates then this macro produces a descendent 449 of the <code>PList</code> template class. If templates are not being used then the 450 macro defines a set of inline functions to do all casting of types. The 451 resultant classes have an identical set of functions in either case. 452 453 See the <code>PList</code> and <code>PAbstractList</code> classes for more information. 454 */ 455 #define PDECLARE_LIST(cls, T) \ 456 PLIST(cls##_PTemplate, T); \ 457 PDECLARE_CLASS(cls, PList<T>) \ 458 protected: \ 459 cls(int dummy, const cls * c) \ 460 : PList<T>(dummy, c) { } \ 461 public: \ 462 cls() \ 463 : PList<T>() { } \ 464 virtual PObject * Clone() const \ 465 { return PNEW cls(0, this); } \ 466 467 468 /**This template class maps the PAbstractList to a specific object type, and 469 adds functionality that allows the list to be used as a first in first out 470 queue. The functions in this class primarily do all the appropriate casting 471 of types. 472 473 By default, objects placed into the set will <b>T</b> be deleted when 474 removed or when all references to the set are destroyed. This is different 475 from the default on most collection classes. 476 477 Note that if templates are not used the <code>PDECLARE_QUEUE</code> macro will 478 simulate the template instantiation. 479 */ 480 template <class T> class PQueue : public PAbstractList 481 { 482 PCLASSINFO(PQueue, PAbstractList); 483 484 public: 485 /**@name Construction */ 486 //@{ 487 /**Create a new, empty, queue. 488 489 Note that by default, objects placed into the queue will <b>not</b> be 490 deleted when removed or when all references to the queue are destroyed. 491 This is different from the default on most collection classes. 492 */ PQueue()493 PQueue() 494 : PAbstractList() { DisallowDeleteObjects(); } 495 //@} 496 497 /**@name Overrides from class PObject */ 498 //@{ 499 /**Make a complete duplicate of the list. Note that all objects in the 500 array are also cloned, so this will make a complete copy of the list. 501 */ Clone()502 virtual PObject * Clone() const 503 { return PNEW PQueue(0, this); } 504 //@} 505 506 /**@name New functions for class */ 507 //@{ 508 /**Add a new object to the queue. This places a new link at the "tail" of 509 the list, which is the "in" side of the queue. 510 */ Enqueue(T * obj)511 virtual void Enqueue( 512 T * obj ///< Object to add to the queue. 513 ) { PAbstractList::Append(obj); } 514 /**Remove an object that was added to the queue. 515 516 @return 517 first object added to the queue or NULL if queue empty. 518 */ Dequeue()519 virtual T * Dequeue() 520 { if (GetSize() == 0) return NULL; else return (T *)PAbstractList::RemoveAt(0);} 521 //@} 522 523 protected: PQueue(int dummy,const PQueue * c)524 PQueue(int dummy, const PQueue * c) 525 : PAbstractList(dummy, c) 526 { reference->deleteObjects = c->reference->deleteObjects; } 527 }; 528 529 530 /**Declare a queue class. 531 This macro is used to declare a descendent of PAbstractList class, 532 customised for a particular object type <b>T</b>, and adds functionality 533 that allows the list to be used as a first in first out queue. This macro 534 closes the class declaration off so no additional members can be added. 535 536 If the compilation is using templates then this macro produces a typedef 537 of the <code>PQueue</code> template class. 538 539 See the <code>PList</code> class and <code>PDECLARE_QUEUE</code> macro for more 540 information. 541 */ 542 #define PQUEUE(cls, T) typedef PQueue<T> cls 543 544 545 /**Begin declataion of a queue class. 546 This macro is used to declare a descendent of PAbstractList class, 547 customised for a particular object type <b>T</b>, and adds functionality 548 that allows the list to be used as a first in first out queue. 549 550 If the compilation is using templates then this macro produces a descendent 551 of the <code>PQueue</code> template class. If templates are not being used then 552 the macro defines a set of inline functions to do all casting of types. The 553 resultant classes have an identical set of functions in either case. 554 555 See the <code>PQueue</code> and <code>PAbstractList</code> classes for more information. 556 */ 557 #define PDECLARE_QUEUE(cls, T) \ 558 PQUEUE(cls##_PTemplate, T); \ 559 PDECLARE_CLASS(cls, cls##_PTemplate) \ 560 protected: \ 561 cls(int dummy, const cls * c) \ 562 : cls##_PTemplate(dummy, c) { } \ 563 public: \ 564 cls() \ 565 : cls##_PTemplate() { } \ 566 virtual PObject * Clone() const \ 567 { return PNEW cls(0, this); } \ 568 569 570 /**This template class maps the PAbstractList to a specific object type, and 571 adds functionality that allows the list to be used as a last in first out 572 stack. The functions in this class primarily do all the appropriate casting 573 of types. 574 575 By default, objects placed into the set will <b>not</b> be deleted when 576 removed or when all references to the set are destroyed. This is different 577 from the default on most collection classes. 578 579 Note that if templates are not used the <code>PDECLARE_STACK</code> macro will 580 simulate the template instantiation. 581 */ 582 template <class T> class PStack : public PAbstractList 583 { 584 PCLASSINFO(PStack, PAbstractList); 585 586 public: 587 /**@name Construction */ 588 //@{ 589 /**Create a new, empty, stack. 590 591 Note that by default, objects placed into the stack will <b>not</b> be 592 deleted when removed or when all references to the stack are destroyed. 593 This is different from the default on most collection classes. 594 */ PStack()595 PStack() 596 : PAbstractList() { DisallowDeleteObjects(); } 597 //@} 598 599 /**@name Overrides from class PObject */ 600 //@{ 601 /**Make a complete duplicate of the stack. Note that all objects in the 602 array are also cloned, so this will make a complete copy of the stack. 603 */ Clone()604 virtual PObject * Clone() const 605 { return PNEW PStack(0, this); } 606 //@} 607 608 /**@name New functions for class */ 609 //@{ 610 /**Add an object to the stack. This object will be on "top" of the stack 611 and will be the object returned by the <code>Pop()</code> 612 function. 613 */ Push(T * obj)614 virtual void Push( 615 T * obj ///< Object to add to the stack. 616 ) { PAbstractList::InsertAt(0, obj); } 617 618 /**Remove the last object pushed onto the stack. 619 620 @return 621 object on top of the stack. 622 */ Pop()623 virtual T * Pop() 624 { return (T *)PAbstractList::RemoveAt(0); } 625 626 /**Get the element that is currently on top of the stack without removing 627 it. 628 629 @return 630 reference to object on top of the stack. 631 */ Top()632 virtual T & Top() 633 { PAssert(GetSize() > 0, PStackEmpty); return *(T *)GetAt(0); } 634 //@} 635 636 protected: PStack(int dummy,const PStack * c)637 PStack(int dummy, const PStack * c) 638 : PAbstractList(dummy, c) 639 { reference->deleteObjects = c->reference->deleteObjects; } 640 }; 641 642 643 /**Declare a stack class. 644 This macro is used to declare a descendent of PAbstractList class, 645 customised for a particular object type <b>T</b>, and adds functionality 646 that allows the list to be used as a last in first out stack. This macro 647 closes the class declaration off so no additional members can be added. 648 649 If the compilation is using templates then this macro produces a typedef 650 of the <code>PStack</code> template class. 651 652 See the <code>PStack</code> class and <code>PDECLARE_STACK</code> macro for more 653 information. 654 */ 655 #define PSTACK(cls, T) typedef PStack<T> cls 656 657 658 /**Begin declaration of a stack class. 659 This macro is used to declare a descendent of PAbstractList class, 660 customised for a particular object type <b>T</b>, and adds functionality 661 that allows the list to be used as a last in first out stack. 662 663 If the compilation is using templates then this macro produces a descendent 664 of the <code>PStack</code> template class. If templates are not being used then 665 the macro defines a set of inline functions to do all casting of types. The 666 resultant classes have an identical set of functions in either case. 667 668 See the <code>PStack</code> and <code>PAbstractList</code> classes for more information. 669 */ 670 #define PDECLARE_STACK(cls, T) \ 671 PSTACK(cls##_PTemplate, T); \ 672 PDECLARE_CLASS(cls, cls##_PTemplate) \ 673 protected: \ 674 cls(int dummy, const cls * c) \ 675 : cls##_PTemplate(dummy, c) { } \ 676 public: \ 677 cls() \ 678 : cls##_PTemplate() { } \ 679 virtual PObject * Clone() const \ 680 { return PNEW cls(0, this); } \ 681 682 683 /////////////////////////////////////////////////////////////////////////////// 684 // Sorted List of PObjects 685 686 struct PSortedListElement 687 { 688 PSortedListElement * parent; 689 PSortedListElement * left; 690 PSortedListElement * right; 691 PObject * data; 692 PINDEX subTreeSize; 693 enum { Red, Black } colour; 694 695 PDECLARE_POOL_ALLOCATOR(); 696 }; 697 698 struct PSortedListInfo 699 { 700 PSortedListInfo(); 701 702 PSortedListElement * root; 703 //PSortedListElement * lastElement; 704 //PINDEX lastIndex; 705 PSortedListElement nil; 706 707 PSortedListElement * Successor(const PSortedListElement * node) const; 708 PSortedListElement * Predecessor(const PSortedListElement * node) const; 709 PSortedListElement * OrderSelect(PSortedListElement * node, PINDEX index) const; 710 711 typedef PSortedListElement Element; 712 713 PDECLARE_POOL_ALLOCATOR(); 714 }; 715 716 /**This class is a collection of objects which are descendents of the 717 <code>PObject</code> class. It is implemeted as a Red-Black binary tree to 718 maintain the objects in rank order. Note that this requires that the 719 <code>PObject::Compare()</code> function be fully implemented oin objects 720 contained in the collection. 721 722 The implementation of a sorted list allows fast inserting and deleting as 723 well as random access of objects in the collection. As the objects are being 724 kept sorted, "fast" is a relative term. All operations take o(lg n) unless 725 a particular object is repeatedly accessed. 726 727 The class remembers the last accessed element. This state information is 728 used to optimise access by the "virtual array" model of collections. If 729 repeated access via ordinal index is made there is little overhead. All 730 other access incurs a minimum overhead, but not insignificant. 731 732 The PAbstractSortedList class would very rarely be descended from directly 733 by the user. The <code>PDECLARE_LIST</code> and <code>PLIST</code> macros would normally 734 be used to create descendent classes. They will instantiate the template 735 based on <code>PSortedList</code> or directly declare and define the class (using 736 inline functions) if templates are not being used. 737 738 The <code>PSortedList</code> class or <code>PDECLARE_SORTED_LIST</code> macro will 739 define the correctly typed operators for subscript access 740 (operator[]). 741 */ 742 class PAbstractSortedList : public PCollection 743 { 744 PCONTAINERINFO(PAbstractSortedList, PCollection); 745 746 public: 747 /**@name Construction */ 748 //@{ 749 /**Create a new, empty, sorted list. 750 751 Note that by default, objects placed into the list will be deleted when 752 removed or when all references to the list are destroyed. 753 */ 754 PAbstractSortedList(); 755 //@} 756 757 /**@name Overrides from class PObject */ 758 //@{ 759 /**Get the relative rank of the two lists. The following algorithm is 760 employed for the comparison: 761 762 \arg \c EqualTo if the two lists are identical in length 763 and each objects values, not pointer, are equal. 764 765 \arg \c LessThan if the instances object value at an 766 ordinal position is less than the corresponding objects value in the 767 <code>obj</code> parameters list. 768 769 This is also returned if all objects are equal and the instances list 770 length is less than the <code>obj</code> parameters list length. 771 772 \arg \c GreaterThan if the instances object value at an 773 ordinal position is greater than the corresponding objects value in the 774 <code>obj</code> parameters list. 775 776 This is also returned if all objects are equal and the instances list 777 length is greater than the <code>obj</code> parameters list length. 778 779 @return 780 comparison of the two objects, <code>EqualTo</code> for same, 781 <code>LessThan</code> for <code>obj</code> logically less than the 782 object and <code>GreaterThan</code> for <code>obj</code> logically 783 greater than the object. 784 */ 785 virtual Comparison Compare(const PObject & obj) const; 786 //@} 787 788 /**@name Overrides from class PContainer */ 789 //@{ 790 /**This function is meaningless for lists. The size of the collection is 791 determined by the addition and removal of objects. The size cannot be 792 set in any other way. 793 794 @return 795 Always true. 796 */ 797 virtual PBoolean SetSize( 798 PINDEX newSize // New size for the sorted list, this is ignored. 799 ); 800 //@} 801 802 /**@name Overrides from class PCollection */ 803 //@{ 804 /**Add a new object to the collection. The object is always placed in the 805 correct ordinal position in the list. It is not placed at the "end". 806 807 @return 808 index of the newly added object. 809 */ 810 virtual PINDEX Append( 811 PObject * obj // New object to place into the collection. 812 ); 813 814 /**Add a new object to the collection. 815 816 The object is always placed in the correct ordinal position in the list. 817 It is not placed at the specified position. The <code>before</code> 818 parameter is ignored. 819 820 @return 821 index of the newly inserted object. 822 */ 823 virtual PINDEX Insert( 824 const PObject & before, // Object value to insert before. 825 PObject * obj // New object to place into the collection. 826 ); 827 828 /**Add a new object to the collection. 829 830 The object is always placed in the correct ordinal position in the list. 831 It is not placed at the specified position. The <code>index</code> 832 parameter is ignored. 833 834 @return 835 index of the newly inserted object. 836 */ 837 virtual PINDEX InsertAt( 838 PINDEX index, // Index position in collection to place the object. 839 PObject * obj // New object to place into the collection. 840 ); 841 842 /**Remove the object from the collection. If the AllowDeleteObjects option 843 is set then the object is also deleted. 844 845 Note that the comparison for searching for the object in collection is 846 made by pointer, not by value. Thus the parameter must point to the 847 same instance of the object that is in the collection. 848 849 @return 850 true if the object was in the collection. 851 */ 852 virtual PBoolean Remove( 853 const PObject * obj // Existing object to remove from the collection. 854 ); 855 856 /**Remove the object at the specified ordinal index from the collection. 857 If the AllowDeleteObjects option is set then the object is also deleted. 858 859 Note if the index is beyond the size of the collection then the 860 function will assert. 861 862 @return 863 pointer to the object being removed, or NULL if it was deleted. 864 */ 865 virtual PObject * RemoveAt( 866 PINDEX index // Index position in collection to place the object. 867 ); 868 869 /**Remove all of the elements in the collection. This operates by 870 continually calling <code>RemoveAt()</code> until there are no objects left. 871 872 The objects are removed from the last, at index 873 <code>(GetSize()-1)</code> toward the first at index zero. 874 */ 875 virtual void RemoveAll(); 876 877 /**This method simply returns false as the list order is mantained by the 878 class. Kept to mimic <code>PAbstractList</code> interface. 879 880 @return 881 false allways 882 */ 883 virtual PBoolean SetAt( 884 PINDEX index, // Index position in collection to set. 885 PObject * val // New value to place into the collection. 886 ); 887 888 /**Get the object at the specified ordinal position. If the index was 889 greater than the size of the collection then NULL is returned. 890 891 @return 892 pointer to object at the specified index. 893 */ 894 virtual PObject * GetAt( 895 PINDEX index // Index position in the collection of the object. 896 ) const; 897 898 /**Search the collection for the specific instance of the object. The 899 object pointers are compared, not the values. A binary search is 900 employed to locate the entry. 901 902 Note that that will require value comparisons to be made to find the 903 equivalent entry and then a final check is made with the pointers to 904 see if they are the same instance. 905 906 @return 907 ordinal index position of the object, or P_MAX_INDEX. 908 */ 909 virtual PINDEX GetObjectsIndex( 910 const PObject * obj 911 ) const; 912 virtual PINDEX GetObjectsIndex( 913 const PObject * obj, 914 PSortedListElement * & lastElement 915 ) const; 916 917 /**Search the collection for the specified value of the object. The object 918 values are compared, not the pointers. So the objects in the 919 collection must correctly implement the <code>PObject::Compare()</code> 920 function. A binary search is employed to locate the entry. 921 922 @return 923 ordinal index position of the object, or P_MAX_INDEX. 924 */ 925 virtual PINDEX GetValuesIndex( 926 const PObject & obj 927 ) const; 928 //@} 929 930 // The type below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it 931 typedef PSortedListElement Element; 932 933 protected: 934 935 // New functions for class 936 void RemoveElement(Element * node); 937 void LeftRotate(Element * node); 938 void RightRotate(Element * node); 939 void DeleteSubTrees(Element * node, PBoolean deleteObject); 940 PINDEX ValueSelect(const Element * node, const PObject & obj, const Element ** lastElement) const; 941 942 // The type below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it 943 PSortedListInfo * info; 944 }; 945 946 947 /**This template class maps the PAbstractSortedList to a specific object type. 948 The functions in this class primarily do all the appropriate casting of 949 types. 950 951 Note that if templates are not used the <code>PDECLARE_SORTED_LIST</code> macro 952 will simulate the template instantiation. 953 */ 954 template <class T> class PSortedList : public PAbstractSortedList 955 { 956 PCLASSINFO(PSortedList, PAbstractSortedList); 957 958 public: 959 /**@name Construction */ 960 //@{ 961 /**Create a new, empty, sorted list. 962 963 Note that by default, objects placed into the list will be deleted when 964 removed or when all references to the list are destroyed. 965 */ PSortedList()966 PSortedList() 967 : PAbstractSortedList() { } 968 //@} 969 970 /**@name Overrides from class PObject */ 971 //@{ 972 /**Make a complete duplicate of the list. Note that all objects in the 973 array are also cloned, so this will make a complete copy of the list. 974 */ Clone()975 virtual PObject * Clone() const 976 { return PNEW PSortedList(0, this); } 977 //@} 978 979 /**@name New functions for class */ 980 //@{ 981 /**Retrieve a reference to the object in the list. If there was not an 982 object at that ordinal position or the index was beyond the size of the 983 array then the function asserts. 984 985 The object accessed in this way is remembered by the class and further 986 access will be fast. 987 988 @return 989 reference to the object at <code>index</code> position. 990 */ 991 T & operator[]( 992 PINDEX index ///< Index for entry 993 ) const { return *(T *)GetAt(index); } 994 //@} 995 996 protected: PSortedList(int dummy,const PSortedList * c)997 PSortedList(int dummy, const PSortedList * c) 998 : PAbstractSortedList(dummy, c) { } 999 }; 1000 1001 1002 /**Declare a sorted list class. 1003 This macro is used to declare a descendent of PAbstractSortedList class, 1004 customised for a particular object type <b>T</b>. This macro closes the 1005 class declaration off so no additional members can be added. 1006 1007 If the compilation is using templates then this macro produces a typedef 1008 of the <code>PSortedList</code> template class. 1009 1010 See the <code>PSortedList</code> class and <code>PDECLARE_SORTED_LIST</code> macro for 1011 more information. 1012 */ 1013 #define PSORTED_LIST(cls, T) typedef PSortedList<T> cls 1014 1015 1016 /**Begin declaration of a sorted list class. 1017 This macro is used to declare a descendent of PAbstractSortedList class, 1018 customised for a particular object type <b>T</b>. 1019 1020 If the compilation is using templates then this macro produces a descendent 1021 of the <code>PSortedList</code> template class. If templates are not being used 1022 then the macro defines a set of inline functions to do all casting of types. 1023 The resultant classes have an identical set of functions in either case. 1024 1025 See the <code>PSortedList</code> and <code>PAbstractSortedList</code> classes for more 1026 information. 1027 */ 1028 #define PDECLARE_SORTED_LIST(cls, T) \ 1029 PSORTED_LIST(cls##_PTemplate, T); \ 1030 PDECLARE_CLASS(cls, PSortedList<T>) \ 1031 protected: \ 1032 cls(int dummy, const cls * c) \ 1033 : PSortedList<T>(dummy, c) { } \ 1034 public: \ 1035 cls() \ 1036 : PSortedList<T>() { } \ 1037 virtual PObject * Clone() const \ 1038 { return PNEW cls(0, this); } \ 1039 1040 1041 #endif // PTLIB_LISTS_H 1042 1043 1044 // End Of File /////////////////////////////////////////////////////////////// 1045