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 ///////////////////////////////////////////////////////////////