PTLib  Version 2.10.10
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
lists.h
Go to the documentation of this file.
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 
43 // PList container class
44 
46 {
47  PListElement(PObject * theData);
51 
53 };
54 
55 struct PListInfo
56 {
57  PListInfo() { head = tail = NULL; }
60 
62 };
63 
84 class PAbstractList : public PCollection
85 {
86  PCONTAINERINFO(PAbstractList, PCollection);
87 
88  public:
98 
99  // Overrides from class PObject
126  virtual Comparison Compare(
127  const PObject & obj
128  ) const;
129 
139  virtual PBoolean SetSize(
140  PINDEX newSize
141  );
143 
152  virtual PINDEX Append(
153  PObject * obj
154  );
155 
168  virtual PINDEX Insert(
169  const PObject & before,
170  PObject * obj
171  );
172 
180  virtual PINDEX InsertAt(
181  PINDEX index,
182  PObject * obj
183  );
184 
191  virtual PBoolean Remove(
192  const PObject * obj
193  );
194 
204  virtual PObject * RemoveAt(
205  PINDEX index
206  );
207 
219  virtual PBoolean SetAt(
220  PINDEX index,
221  PObject * val
222  );
223 
234  virtual PBoolean ReplaceAt(
235  PINDEX index,
236  PObject * val
237  );
238 
249  virtual PObject * GetAt(
250  PINDEX index
251  ) const;
252 
260  virtual PINDEX GetObjectsIndex(
261  const PObject * obj
262  ) const;
263 
272  virtual PINDEX GetValuesIndex(
273  const PObject & obj
274  ) const;
276 
277 
278  protected:
290  PINDEX index
291  ) const;
292 
303  PINDEX index,
304  PListElement * & lastElement
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
312 };
313 
314 
321 template <class T> class PList : public PAbstractList
322 {
323  PCLASSINFO(PList, PAbstractList);
324 
325  public:
334  : PAbstractList() { }
336 
342  virtual PObject * Clone() const
343  { return PNEW PList(0, this); }
345 
348  class iterator_base : public std::iterator<std::bidirectional_iterator_tag, T> {
349  protected:
352 
353  void Next() { element = PAssertNULL(element)->next; }
354  void Prev() { element = PAssertNULL(element)->prev; }
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:
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 
375  iterator begin() { return info->head; }
376  iterator end() { return iterator(); }
377  iterator rbegin() { return info->tail; }
378  iterator rend() { return iterator(); }
379 
380 
381  class const_iterator : public iterator_base {
382  public:
384 
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 
394  const_iterator begin() const { return info->head; }
395  const_iterator end() const { return const_iterator(); }
396  const_iterator rbegin() const { return info->tail; }
397  const_iterator rend() const { return iterator(); }
398 
399  T & front() const { return *(T *)PAssertNULL(info->head)->data; }
400  T & back() const { return *(T *)PAssertNULL(info->tail)->data; }
401  void erase(const iterator & it) { Remove(&*it); }
402  void erase(const const_iterator & it) { Remove(&*it); }
403 
404  typedef T value_type;
406 
421  PINDEX index
422  ) const { return (T &)GetReferenceAt(index); }
424 
425  protected:
426  PList(int dummy, const PList * c)
427  : PAbstractList(dummy, c) { }
428 };
429 
430 
442 #define PLIST(cls, T) typedef PList<T> cls
443 
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 
480 template <class T> class PQueue : public PAbstractList
481 {
482  PCLASSINFO(PQueue, PAbstractList);
483 
484  public:
496 
502  virtual PObject * Clone() const
503  { return PNEW PQueue(0, this); }
505 
511  virtual void Enqueue(
512  T * obj
513  ) { PAbstractList::Append(obj); }
519  virtual T * Dequeue()
520  { if (GetSize() == 0) return NULL; else return (T *)PAbstractList::RemoveAt(0);}
522 
523  protected:
524  PQueue(int dummy, const PQueue * c)
525  : PAbstractList(dummy, c)
527 };
528 
529 
542 #define PQUEUE(cls, T) typedef PQueue<T> cls
543 
544 
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 
582 template <class T> class PStack : public PAbstractList
583 {
584  PCLASSINFO(PStack, PAbstractList);
585 
586  public:
598 
604  virtual PObject * Clone() const
605  { return PNEW PStack(0, this); }
607 
614  virtual void Push(
615  T * obj
616  ) { PAbstractList::InsertAt(0, obj); }
617 
623  virtual T * Pop()
624  { return (T *)PAbstractList::RemoveAt(0); }
625 
632  virtual T & Top()
633  { PAssert(GetSize() > 0, PStackEmpty); return *(T *)GetAt(0); }
635 
636  protected:
637  PStack(int dummy, const PStack * c)
638  : PAbstractList(dummy, c)
640 };
641 
642 
655 #define PSTACK(cls, T) typedef PStack<T> cls
656 
657 
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 
684 // Sorted List of PObjects
685 
687 {
692  PINDEX subTreeSize;
693  enum { Red, Black } colour;
694 
696 };
697 
699 {
700  PSortedListInfo();
701 
703  //PSortedListElement * lastElement;
704  //PINDEX lastIndex;
706 
707  PSortedListElement * Successor(const PSortedListElement * node) const;
708  PSortedListElement * Predecessor(const PSortedListElement * node) const;
709  PSortedListElement * OrderSelect(PSortedListElement * node, PINDEX index) const;
710 
712 
714 };
715 
743 {
744  PCONTAINERINFO(PAbstractSortedList, PCollection);
745 
746  public:
756 
785  virtual Comparison Compare(const PObject & obj) const;
787 
797  virtual PBoolean SetSize(
798  PINDEX newSize // New size for the sorted list, this is ignored.
799  );
801 
810  virtual PINDEX Append(
811  PObject * obj // New object to place into the collection.
812  );
813 
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 
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 
852  virtual PBoolean Remove(
853  const PObject * obj // Existing object to remove from the collection.
854  );
855 
865  virtual PObject * RemoveAt(
866  PINDEX index // Index position in collection to place the object.
867  );
868 
875  virtual void RemoveAll();
876 
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 
894  virtual PObject * GetAt(
895  PINDEX index // Index position in the collection of the object.
896  ) const;
897 
909  virtual PINDEX GetObjectsIndex(
910  const PObject * obj
911  ) const;
912  virtual PINDEX GetObjectsIndex(
913  const PObject * obj,
914  PSortedListElement * & lastElement
915  ) const;
916 
925  virtual PINDEX GetValuesIndex(
926  const PObject & obj
927  ) const;
929 
930  // The type below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it
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
944 };
945 
946 
954 template <class T> class PSortedList : public PAbstractSortedList
955 {
956  PCLASSINFO(PSortedList, PAbstractSortedList);
957 
958  public:
967  : PAbstractSortedList() { }
969 
975  virtual PObject * Clone() const
976  { return PNEW PSortedList(0, this); }
978 
992  PINDEX index
993  ) const { return *(T *)GetAt(index); }
995 
996  protected:
997  PSortedList(int dummy, const PSortedList * c)
998  : PAbstractSortedList(dummy, c) { }
999 };
1000 
1001 
1013 #define PSORTED_LIST(cls, T) typedef PSortedList<T> cls
1014 
1015 
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 ///////////////////////////////////////////////////////////////
PListInfo * info
Definition: lists.h:311
virtual PObject * Clone() const
Make a complete duplicate of the list.
Definition: lists.h:975
virtual T & Top()
Get the element that is currently on top of the stack without removing it.
Definition: lists.h:632
iterator end()
Definition: lists.h:376
virtual PObject * Clone() const
Make a complete duplicate of the list.
Definition: lists.h:502
const T * operator->() const
Definition: lists.h:390
PSortedListElement * left
Definition: lists.h:689
PSortedListElement Element
Definition: lists.h:711
T * operator->() const
Definition: lists.h:371
bool operator==(const iterator_base &it) const
Definition: lists.h:358
PQueue(int dummy, const PQueue *c)
Definition: lists.h:524
Definition: lists.h:686
PDECLARE_POOL_ALLOCATOR()
enum PSortedListElement::@6 colour
PSortedListElement * root
Definition: lists.h:702
iterator rbegin()
Definition: lists.h:377
const_iterator operator--()
Definition: lists.h:386
PBoolean SetCurrent(PINDEX index, PListElement *&lastElement) const
Move the internal "cursor" to the index position specified.
PINLINE PObject & GetReferenceAt(PINDEX index) const
Get the object at the specified ordinal position.
T * Ptr() const
Definition: lists.h:355
Definition: lists.h:45
const T & operator*() const
Definition: lists.h:391
iterator(PListElement *e=NULL)
Definition: lists.h:364
iterator rend()
Definition: lists.h:378
virtual PBoolean SetSize(PINDEX newSize)
This function is meaningless for lists.
T value_type
Definition: lists.h:404
#define PINLINE
Definition: object.h:127
iterator operator++()
Definition: lists.h:366
const_iterator operator++(int)
Definition: lists.h:387
PINDEX ValueSelect(const Element *node, const PObject &obj, const Element **lastElement) const
PSortedList()
Create a new, empty, sorted list.
Definition: lists.h:966
virtual PINDEX Insert(const PObject &before, PObject *obj)
Add a new object to the collection.
virtual PBoolean ReplaceAt(PINDEX index, PObject *val)
Set the object at the specified ordinal position to the new value.
Comparison
Result of the comparison operation performed by the Compare() function.
Definition: object.h:1184
virtual void RemoveAll()
Remove all of the elements in the collection.
virtual PINDEX GetValuesIndex(const PObject &obj) const
Search the collection for the specified value of the object.
PSortedList(int dummy, const PSortedList *c)
Definition: lists.h:997
A Pop() was made of a stack with no elements.
Definition: object.h:157
PSortedListInfo * info
Definition: lists.h:943
virtual PBoolean SetAt(PINDEX index, PObject *val)
This method simply returns false as the list order is mantained by the class.
iterator_base(PListElement *e)
Definition: lists.h:350
const_iterator(PListElement *e=NULL)
Definition: lists.h:383
virtual PObject * Clone() const
Make a complete duplicate of the stack.
Definition: lists.h:604
virtual PINDEX GetObjectsIndex(const PObject *obj) const
Search the collection for the specific instance of the object.
void Next()
Definition: lists.h:353
void erase(const iterator &it)
Definition: lists.h:401
virtual PObject * GetAt(PINDEX index) const
Get the object at the specified ordinal position.
PListElement Element
Definition: lists.h:310
virtual PINDEX Append(PObject *obj)
Append a new object to the collection.
virtual PINDEX InsertAt(PINDEX index, PObject *obj)
Insert a new object at the specified ordinal index.
virtual PBoolean SetAt(PINDEX index, PObject *val)
Set the object at the specified ordinal position to the new value.
PQueue()
Create a new, empty, queue.
Definition: lists.h:493
virtual PBoolean Remove(const PObject *obj)
Remove the object from the collection.
PList()
Create a new, empty, list.
Definition: lists.h:333
Definition: lists.h:362
PSortedListElement * OrderSelect(PSortedListElement *node, PINDEX index) const
This template class maps the PAbstractList to a specific object type.
Definition: lists.h:321
const_iterator begin() const
Definition: lists.h:394
void RightRotate(Element *node)
PListInfo()
Definition: lists.h:57
BOOL PBoolean
Definition: object.h:102
PINLINE PAbstractList()
Create a new, empty, list.
PDECLARE_POOL_ALLOCATOR()
virtual T * Dequeue()
Remove an object that was added to the queue.
Definition: lists.h:519
iterator operator--()
Definition: lists.h:367
virtual void Enqueue(T *obj)
Add a new object to the queue.
Definition: lists.h:511
virtual Comparison Compare(const PObject &obj) const
Get the relative rank of the two lists.
const_iterator operator--(int)
Definition: lists.h:388
PList(int dummy, const PList *c)
Definition: lists.h:426
virtual PINDEX Append(PObject *obj)
Add a new object to the collection.
virtual T * Pop()
Remove the last object pushed onto the stack.
Definition: lists.h:623
PSortedListElement nil
Definition: lists.h:705
virtual PObject * RemoveAt(PINDEX index)
Remove the object at the specified ordinal index from the collection.
virtual PObject * GetAt(PINDEX index) const
Get the object at the specified ordinal position.
virtual PBoolean Remove(const PObject *obj)
Remove the object from the collection.
bool operator!=(const iterator_base &it) const
Definition: lists.h:359
#define PAssertNULL(ptr)
This macro is used to assert that a pointer must be non-null.
Definition: object.h:220
virtual PINDEX GetSize() const
Get the current size of the container.
virtual PINDEX GetObjectsIndex(const PObject *obj) const
Search the collection for the specific instance of the object.
void LeftRotate(Element *node)
virtual void Push(T *obj)
Add an object to the stack.
Definition: lists.h:614
PObject * RemoveElement(PListElement *element)
Definition: lists.h:55
virtual Comparison Compare(const PObject &obj) const
Get the relative rank of the two lists.
This class is a collection of objects which are descendents of the PObject class. ...
Definition: lists.h:84
void erase(const const_iterator &it)
Definition: lists.h:402
PSortedListElement * parent
Definition: lists.h:688
PObject * data
Definition: lists.h:50
iterator begin()
Definition: lists.h:375
virtual PObject * RemoveAt(PINDEX index)
Remove the object at the specified ordinal index from the collection.
virtual PINDEX GetValuesIndex(const PObject &obj) const
Search the collection for the specified value of the object.
PObject * data
Definition: lists.h:691
PStack(int dummy, const PStack *c)
Definition: lists.h:637
This template class maps the PAbstractList to a specific object type, and adds functionality that all...
Definition: lists.h:480
void RemoveElement(Element *node)
PListElement * prev
Definition: lists.h:48
bool deleteObjects
Definition: contain.h:72
virtual PINDEX Insert(const PObject &before, PObject *obj)
Insert a new object immediately before the specified object.
T & operator[](PINDEX index) const
Retrieve a reference to the object in the list.
Definition: lists.h:420
iterator operator--(int)
Definition: lists.h:369
PAbstractSortedList()
Create a new, empty, sorted list.
virtual PINDEX InsertAt(PINDEX index, PObject *obj)
Add a new object to the collection.
T & front() const
Definition: lists.h:399
const_iterator rend() const
Definition: lists.h:397
T & operator*() const
Definition: lists.h:372
Definition: lists.h:698
PStack()
Create a new, empty, stack.
Definition: lists.h:595
iterator operator++(int)
Definition: lists.h:368
virtual PObject * Clone() const
Make a complete duplicate of the list.
Definition: lists.h:342
PListElement(PObject *theData)
This template class maps the PAbstractSortedList to a specific object type.
Definition: lists.h:954
PSortedListElement * right
Definition: lists.h:690
This template class maps the PAbstractList to a specific object type, and adds functionality that all...
Definition: lists.h:582
PListElement * tail
Definition: lists.h:59
PListElement * head
Definition: lists.h:58
#define PAssert(b, msg)
This macro is used to assert that a condition must be true.
Definition: object.h:192
T & back() const
Definition: lists.h:400
PSortedListElement Element
Definition: lists.h:931
T & operator[](PINDEX index) const
Retrieve a reference to the object in the list.
Definition: lists.h:991
PINDEX subTreeSize
Definition: lists.h:692
const_iterator operator++()
Definition: lists.h:385
This class is a collection of objects which are descendents of the PObject class. ...
Definition: lists.h:742
void DeleteSubTrees(Element *node, PBoolean deleteObject)
virtual PBoolean SetSize(PINDEX newSize)
This function is meaningless for lists.
PContainerReference * reference
Definition: contain.h:291
Definition: lists.h:348
PSortedListElement * Successor(const PSortedListElement *node) const
PListElement * next
Definition: lists.h:49
Ultimate parent class for all objects in the class library.
Definition: object.h:1118
PSortedListElement * Predecessor(const PSortedListElement *node) const
A collection is a container that collects together descendents of the PObject class.
Definition: contain.h:395
Definition: lists.h:693
PListElement * element
Definition: lists.h:351
Definition: lists.h:693
const_iterator rbegin() const
Definition: lists.h:396
void DisallowDeleteObjects()
Disallow the deletion of the objects contained in the collection.
Definition: lists.h:381
void Prev()
Definition: lists.h:354
const_iterator end() const
Definition: lists.h:395
#define PNEW
Macro for overriding system default new operator.
Definition: object.h:890