PTLib  Version 2.10.11
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 {
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:
289  PINLINE PObject & GetReferenceAt(
290  PINDEX index
291  ) const;
292 
302  PBoolean SetCurrent(
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 {
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:
350  iterator_base(PListElement * e) : element(e) { }
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 
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 
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 {
483 
484  public:
494  : PAbstractList() { DisallowDeleteObjects(); }
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)
526  { reference->deleteObjects = c->reference->deleteObjects; }
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 {
585 
586  public:
596  : PAbstractList() { DisallowDeleteObjects(); }
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)
639  { reference->deleteObjects = c->reference->deleteObjects; }
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 {
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 {
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
PSortedListElement * root
Definition: lists.h:702
iterator rbegin()
Definition: lists.h:377
#define PCLASSINFO(cls, par)
Declare all the standard PTLib class information.
Definition: object.h:1049
const_iterator operator--()
Definition: lists.h:386
T * Ptr() const
Definition: lists.h:355
Definition: lists.h:45
iterator(PListElement *e=NULL)
Definition: lists.h:364
iterator rend()
Definition: lists.h:378
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
PSortedList()
Create a new, empty, sorted list.
Definition: lists.h:966
Comparison
Result of the comparison operation performed by the Compare() function.
Definition: object.h:1184
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
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
void Next()
Definition: lists.h:353
void erase(const iterator &it)
Definition: lists.h:401
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.
PQueue()
Create a new, empty, queue.
Definition: lists.h:493
PList()
Create a new, empty, list.
Definition: lists.h:333
Definition: lists.h:362
This template class maps the PAbstractList to a specific object type.
Definition: lists.h:321
const_iterator begin() const
Definition: lists.h:394
PListInfo()
Definition: lists.h:57
BOOL PBoolean
Definition: object.h:102
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
const_iterator operator--(int)
Definition: lists.h:388
PList(int dummy, const PList *c)
Definition: lists.h:426
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.
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 void Push(T *obj)
Add an object to the stack.
Definition: lists.h:614
Definition: lists.h:55
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
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
PListElement * prev
Definition: lists.h:48
bool deleteObjects
Definition: contain.h:72
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
#define PCONTAINERINFO(cls, par)
Macro to declare funtions required in a container.
Definition: contain.h:343
T & front() const
Definition: lists.h:399
const_iterator rend() const
Definition: lists.h:397
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
PContainerReference * reference
Definition: contain.h:291
Definition: lists.h:348
PListElement * next
Definition: lists.h:49
PObject * RemoveElement(const PObject &key)
Ultimate parent class for all objects in the class library.
Definition: object.h:1118
A collection is a container that collects together descendents of the PObject class.
Definition: contain.h:395
PListElement * element
Definition: lists.h:351
Definition: lists.h:693
const_iterator rbegin() const
Definition: lists.h:396
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