PTLib
Version 2.10.4
|
00001 /* 00002 * lists.h 00003 * 00004 * List Container Classes 00005 * 00006 * Portable Windows Library 00007 * 00008 * Copyright (c) 1993-1998 Equivalence Pty. Ltd. 00009 * 00010 * The contents of this file are subject to the Mozilla Public License 00011 * Version 1.0 (the "License"); you may not use this file except in 00012 * compliance with the License. You may obtain a copy of the License at 00013 * http://www.mozilla.org/MPL/ 00014 * 00015 * Software distributed under the License is distributed on an "AS IS" 00016 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 00017 * the License for the specific language governing rights and limitations 00018 * under the License. 00019 * 00020 * The Original Code is Portable Windows Library. 00021 * 00022 * The Initial Developer of the Original Code is Equivalence Pty. Ltd. 00023 * 00024 * Portions are Copyright (C) 1993 Free Software Foundation, Inc. 00025 * All Rights Reserved. 00026 * 00027 * Contributor(s): ______________________________________. 00028 * 00029 * $Revision: 24177 $ 00030 * $Author: rjongbloed $ 00031 * $Date: 2010-04-05 06:52:04 -0500 (Mon, 05 Apr 2010) $ 00032 */ 00033 00034 #ifndef PTLIB_LISTS_H 00035 #define PTLIB_LISTS_H 00036 00037 #ifdef P_USE_PRAGMA 00038 #pragma interface 00039 #endif 00040 00041 00043 // PList container class 00044 00045 struct PListElement 00046 { 00047 PListElement(PObject * theData); 00048 PListElement * prev; 00049 PListElement * next; 00050 PObject * data; 00051 00052 PDECLARE_POOL_ALLOCATOR(); 00053 }; 00054 00055 struct PListInfo 00056 { 00057 PListInfo() { head = tail = NULL; } 00058 PListElement * head; 00059 PListElement * tail; 00060 00061 PDECLARE_POOL_ALLOCATOR(); 00062 }; 00063 00084 class PAbstractList : public PCollection 00085 { 00086 PCONTAINERINFO(PAbstractList, PCollection); 00087 00088 public: 00096 PINLINE PAbstractList(); 00098 00099 // Overrides from class PObject 00126 virtual Comparison Compare( 00127 const PObject & obj 00128 ) const; 00129 00139 virtual PBoolean SetSize( 00140 PINDEX newSize 00141 ); 00143 00152 virtual PINDEX Append( 00153 PObject * obj 00154 ); 00155 00168 virtual PINDEX Insert( 00169 const PObject & before, 00170 PObject * obj 00171 ); 00172 00180 virtual PINDEX InsertAt( 00181 PINDEX index, 00182 PObject * obj 00183 ); 00184 00191 virtual PBoolean Remove( 00192 const PObject * obj 00193 ); 00194 00204 virtual PObject * RemoveAt( 00205 PINDEX index 00206 ); 00207 00219 virtual PBoolean SetAt( 00220 PINDEX index, 00221 PObject * val 00222 ); 00223 00234 virtual PBoolean ReplaceAt( 00235 PINDEX index, 00236 PObject * val 00237 ); 00238 00249 virtual PObject * GetAt( 00250 PINDEX index 00251 ) const; 00252 00260 virtual PINDEX GetObjectsIndex( 00261 const PObject * obj 00262 ) const; 00263 00272 virtual PINDEX GetValuesIndex( 00273 const PObject & obj 00274 ) const; 00276 00277 00278 protected: 00289 PINLINE PObject & GetReferenceAt( 00290 PINDEX index 00291 ) const; 00292 00302 PBoolean SetCurrent( 00303 PINDEX index, 00304 PListElement * & lastElement 00305 ) const; 00306 00307 PObject * RemoveElement(PListElement * element); 00308 00309 // The types below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it 00310 typedef PListElement Element; 00311 PListInfo * info; 00312 }; 00313 00314 00321 template <class T> class PList : public PAbstractList 00322 { 00323 PCLASSINFO(PList, PAbstractList); 00324 00325 public: 00333 PList() 00334 : PAbstractList() { } 00336 00342 virtual PObject * Clone() const 00343 { return PNEW PList(0, this); } 00345 00348 class iterator_base : public std::iterator<std::bidirectional_iterator_tag, T> { 00349 protected: 00350 iterator_base(PListElement * e) : element(e) { } 00351 PListElement * element; 00352 00353 void Next() { element = PAssertNULL(element)->next; } 00354 void Prev() { element = PAssertNULL(element)->prev; } 00355 T * Ptr() const { return (T *)PAssertNULL(element)->data; } 00356 00357 public: 00358 bool operator==(const iterator_base & it) const { return element == it.element; } 00359 bool operator!=(const iterator_base & it) const { return element != it.element; } 00360 }; 00361 00362 class iterator : public iterator_base { 00363 public: 00364 iterator(PListElement * e = NULL) : iterator_base(e) { } 00365 00366 iterator operator++() { iterator_base::Next(); return *this; } 00367 iterator operator--() { iterator_base::Prev(); return *this; } 00368 iterator operator++(int) { iterator it = *this; iterator_base::Next(); return it; } 00369 iterator operator--(int) { iterator it = *this; iterator_base::Prev(); return it; } 00370 00371 T * operator->() const { return iterator_base::Ptr(); } 00372 T & operator* () const { return *iterator_base::Ptr(); } 00373 }; 00374 00375 iterator begin() { return info->head; } 00376 iterator end() { return iterator(); } 00377 iterator rbegin() { return info->tail; } 00378 iterator rend() { return iterator(); } 00379 00380 00381 class const_iterator : public iterator_base { 00382 public: 00383 const_iterator(PListElement * e = NULL) : iterator_base(e) { } 00384 00385 const_iterator operator++() { iterator_base::Next(); return *this; } 00386 const_iterator operator--() { iterator_base::Prev(); return *this; } 00387 const_iterator operator++(int) { const_iterator it = *this; iterator_base::Next(); return it; } 00388 const_iterator operator--(int) { const_iterator it = *this; iterator_base::Prev(); return it; } 00389 00390 const T * operator->() const { return iterator_base::Ptr(); } 00391 const T & operator* () const { return *iterator_base::Ptr(); } 00392 }; 00393 00394 const_iterator begin() const { return info->head; } 00395 const_iterator end() const { return const_iterator(); } 00396 const_iterator rbegin() const { return info->tail; } 00397 const_iterator rend() const { return iterator(); } 00398 00399 T & front() const { return *(T *)PAssertNULL(info->head)->data; } 00400 T & back() const { return *(T *)PAssertNULL(info->tail)->data; } 00401 void erase(const iterator & it) { Remove(&*it); } 00402 void erase(const const_iterator & it) { Remove(&*it); } 00403 00404 typedef T value_type; 00406 00420 T & operator[]( 00421 PINDEX index 00422 ) const { return (T &)GetReferenceAt(index); } 00424 00425 protected: 00426 PList(int dummy, const PList * c) 00427 : PAbstractList(dummy, c) { } 00428 }; 00429 00430 00442 #define PLIST(cls, T) typedef PList<T> cls 00443 00455 #define PDECLARE_LIST(cls, T) \ 00456 PLIST(cls##_PTemplate, T); \ 00457 PDECLARE_CLASS(cls, PList<T>) \ 00458 protected: \ 00459 cls(int dummy, const cls * c) \ 00460 : PList<T>(dummy, c) { } \ 00461 public: \ 00462 cls() \ 00463 : PList<T>() { } \ 00464 virtual PObject * Clone() const \ 00465 { return PNEW cls(0, this); } \ 00466 00467 00480 template <class T> class PQueue : public PAbstractList 00481 { 00482 PCLASSINFO(PQueue, PAbstractList); 00483 00484 public: 00493 PQueue() 00494 : PAbstractList() { DisallowDeleteObjects(); } 00496 00502 virtual PObject * Clone() const 00503 { return PNEW PQueue(0, this); } 00505 00511 virtual void Enqueue( 00512 T * obj 00513 ) { PAbstractList::Append(obj); } 00519 virtual T * Dequeue() 00520 { if (GetSize() == 0) return NULL; else return (T *)PAbstractList::RemoveAt(0);} 00522 00523 protected: 00524 PQueue(int dummy, const PQueue * c) 00525 : PAbstractList(dummy, c) 00526 { reference->deleteObjects = c->reference->deleteObjects; } 00527 }; 00528 00529 00542 #define PQUEUE(cls, T) typedef PQueue<T> cls 00543 00544 00557 #define PDECLARE_QUEUE(cls, T) \ 00558 PQUEUE(cls##_PTemplate, T); \ 00559 PDECLARE_CLASS(cls, cls##_PTemplate) \ 00560 protected: \ 00561 cls(int dummy, const cls * c) \ 00562 : cls##_PTemplate(dummy, c) { } \ 00563 public: \ 00564 cls() \ 00565 : cls##_PTemplate() { } \ 00566 virtual PObject * Clone() const \ 00567 { return PNEW cls(0, this); } \ 00568 00569 00582 template <class T> class PStack : public PAbstractList 00583 { 00584 PCLASSINFO(PStack, PAbstractList); 00585 00586 public: 00595 PStack() 00596 : PAbstractList() { DisallowDeleteObjects(); } 00598 00604 virtual PObject * Clone() const 00605 { return PNEW PStack(0, this); } 00607 00614 virtual void Push( 00615 T * obj 00616 ) { PAbstractList::InsertAt(0, obj); } 00617 00623 virtual T * Pop() 00624 { return (T *)PAbstractList::RemoveAt(0); } 00625 00632 virtual T & Top() 00633 { PAssert(GetSize() > 0, PStackEmpty); return *(T *)GetAt(0); } 00635 00636 protected: 00637 PStack(int dummy, const PStack * c) 00638 : PAbstractList(dummy, c) 00639 { reference->deleteObjects = c->reference->deleteObjects; } 00640 }; 00641 00642 00655 #define PSTACK(cls, T) typedef PStack<T> cls 00656 00657 00670 #define PDECLARE_STACK(cls, T) \ 00671 PSTACK(cls##_PTemplate, T); \ 00672 PDECLARE_CLASS(cls, cls##_PTemplate) \ 00673 protected: \ 00674 cls(int dummy, const cls * c) \ 00675 : cls##_PTemplate(dummy, c) { } \ 00676 public: \ 00677 cls() \ 00678 : cls##_PTemplate() { } \ 00679 virtual PObject * Clone() const \ 00680 { return PNEW cls(0, this); } \ 00681 00682 00684 // Sorted List of PObjects 00685 00686 struct PSortedListElement 00687 { 00688 PSortedListElement * parent; 00689 PSortedListElement * left; 00690 PSortedListElement * right; 00691 PObject * data; 00692 PINDEX subTreeSize; 00693 enum { Red, Black } colour; 00694 00695 PDECLARE_POOL_ALLOCATOR(); 00696 }; 00697 00698 struct PSortedListInfo 00699 { 00700 PSortedListInfo(); 00701 00702 PSortedListElement * root; 00703 //PSortedListElement * lastElement; 00704 //PINDEX lastIndex; 00705 PSortedListElement nil; 00706 00707 PSortedListElement * Successor(const PSortedListElement * node) const; 00708 PSortedListElement * Predecessor(const PSortedListElement * node) const; 00709 PSortedListElement * OrderSelect(PSortedListElement * node, PINDEX index) const; 00710 00711 typedef PSortedListElement Element; 00712 00713 PDECLARE_POOL_ALLOCATOR(); 00714 }; 00715 00742 class PAbstractSortedList : public PCollection 00743 { 00744 PCONTAINERINFO(PAbstractSortedList, PCollection); 00745 00746 public: 00754 PAbstractSortedList(); 00756 00785 virtual Comparison Compare(const PObject & obj) const; 00787 00797 virtual PBoolean SetSize( 00798 PINDEX newSize // New size for the sorted list, this is ignored. 00799 ); 00801 00810 virtual PINDEX Append( 00811 PObject * obj // New object to place into the collection. 00812 ); 00813 00823 virtual PINDEX Insert( 00824 const PObject & before, // Object value to insert before. 00825 PObject * obj // New object to place into the collection. 00826 ); 00827 00837 virtual PINDEX InsertAt( 00838 PINDEX index, // Index position in collection to place the object. 00839 PObject * obj // New object to place into the collection. 00840 ); 00841 00852 virtual PBoolean Remove( 00853 const PObject * obj // Existing object to remove from the collection. 00854 ); 00855 00865 virtual PObject * RemoveAt( 00866 PINDEX index // Index position in collection to place the object. 00867 ); 00868 00875 virtual void RemoveAll(); 00876 00883 virtual PBoolean SetAt( 00884 PINDEX index, // Index position in collection to set. 00885 PObject * val // New value to place into the collection. 00886 ); 00887 00894 virtual PObject * GetAt( 00895 PINDEX index // Index position in the collection of the object. 00896 ) const; 00897 00909 virtual PINDEX GetObjectsIndex( 00910 const PObject * obj 00911 ) const; 00912 virtual PINDEX GetObjectsIndex( 00913 const PObject * obj, 00914 PSortedListElement * & lastElement 00915 ) const; 00916 00925 virtual PINDEX GetValuesIndex( 00926 const PObject & obj 00927 ) const; 00929 00930 // The type below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it 00931 typedef PSortedListElement Element; 00932 00933 protected: 00934 00935 // New functions for class 00936 void RemoveElement(Element * node); 00937 void LeftRotate(Element * node); 00938 void RightRotate(Element * node); 00939 void DeleteSubTrees(Element * node, PBoolean deleteObject); 00940 PINDEX ValueSelect(const Element * node, const PObject & obj, const Element ** lastElement) const; 00941 00942 // The type below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it 00943 PSortedListInfo * info; 00944 }; 00945 00946 00954 template <class T> class PSortedList : public PAbstractSortedList 00955 { 00956 PCLASSINFO(PSortedList, PAbstractSortedList); 00957 00958 public: 00966 PSortedList() 00967 : PAbstractSortedList() { } 00969 00975 virtual PObject * Clone() const 00976 { return PNEW PSortedList(0, this); } 00978 00991 T & operator[]( 00992 PINDEX index 00993 ) const { return *(T *)GetAt(index); } 00995 00996 protected: 00997 PSortedList(int dummy, const PSortedList * c) 00998 : PAbstractSortedList(dummy, c) { } 00999 }; 01000 01001 01013 #define PSORTED_LIST(cls, T) typedef PSortedList<T> cls 01014 01015 01028 #define PDECLARE_SORTED_LIST(cls, T) \ 01029 PSORTED_LIST(cls##_PTemplate, T); \ 01030 PDECLARE_CLASS(cls, PSortedList<T>) \ 01031 protected: \ 01032 cls(int dummy, const cls * c) \ 01033 : PSortedList<T>(dummy, c) { } \ 01034 public: \ 01035 cls() \ 01036 : PSortedList<T>() { } \ 01037 virtual PObject * Clone() const \ 01038 { return PNEW cls(0, this); } \ 01039 01040 01041 #endif // PTLIB_LISTS_H 01042 01043 01044 // End Of File ///////////////////////////////////////////////////////////////