00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136 #ifdef P_USE_PRAGMA
00137 #pragma interface
00138 #endif
00139
00140
00142
00143
00164 class PAbstractList : public PCollection
00165 {
00166 PCONTAINERINFO(PAbstractList, PCollection);
00167
00168 public:
00176 PINLINE PAbstractList();
00178
00179
00207 virtual Comparison Compare(const PObject & obj) const;
00208
00218 virtual BOOL SetSize(
00219 PINDEX newSize
00220 );
00222
00231 virtual PINDEX Append(
00232 PObject * obj
00233 );
00234
00247 virtual PINDEX Insert(
00248 const PObject & before,
00249 PObject * obj
00250 );
00251
00259 virtual PINDEX InsertAt(
00260 PINDEX index,
00261 PObject * obj
00262 );
00263
00270 virtual BOOL Remove(
00271 const PObject * obj
00272 );
00273
00283 virtual PObject * RemoveAt(
00284 PINDEX index
00285 );
00286
00298 virtual BOOL SetAt(
00299 PINDEX index,
00300 PObject * val
00301 );
00302
00313 virtual BOOL ReplaceAt(
00314 PINDEX index,
00315 PObject * val
00316 );
00317
00328 virtual PObject * GetAt(
00329 PINDEX index
00330 ) const;
00331
00339 virtual PINDEX GetObjectsIndex(
00340 const PObject * obj
00341 ) const;
00342
00351 virtual PINDEX GetValuesIndex(
00352 const PObject & obj
00353 ) const;
00355
00356
00357 protected:
00368 PINLINE PObject & GetReferenceAt(
00369 PINDEX index
00370 ) const;
00371
00381 BOOL SetCurrent(
00382 PINDEX index
00383 ) const;
00384
00385 class Element {
00386 public:
00387 friend class Info;
00388 Element(PObject * theData);
00389 Element * prev;
00390 Element * next;
00391 PObject * data;
00392 };
00393
00394 class Info {
00395 public:
00396 Info() { head = tail = lastElement = NULL; }
00397 Element * head;
00398 Element * tail;
00399 Element * lastElement;
00400 PINDEX lastIndex;
00401 } * info;
00402 };
00403
00404
00405 #ifdef PHAS_TEMPLATES
00406
00413 template <class T> class PList : public PAbstractList
00414 {
00415 PCLASSINFO(PList, PAbstractList);
00416
00417 public:
00425 PList()
00426 : PAbstractList() { }
00428
00434 virtual PObject * Clone() const
00435 { return PNEW PList(0, this); }
00437
00451 T & operator[](PINDEX index) const
00452 { return (T &)GetReferenceAt(index); }
00454
00455 protected:
00456 PList(int dummy, const PList * c)
00457 : PAbstractList(dummy, c) { }
00458 };
00459
00460
00472 #define PLIST(cls, T) typedef PList<T> cls
00473
00485 #define PDECLARE_LIST(cls, T) \
00486 PLIST(cls##_PTemplate, T); \
00487 PDECLARE_CLASS(cls, PList<T>) \
00488 protected: \
00489 cls(int dummy, const cls * c) \
00490 : PList<T>(dummy, c) { } \
00491 public: \
00492 cls() \
00493 : PList<T>() { } \
00494 virtual PObject * Clone() const \
00495 { return PNEW cls(0, this); } \
00496
00497
00510 template <class T> class PQueue : public PAbstractList
00511 {
00512 PCLASSINFO(PQueue, PAbstractList);
00513
00514 public:
00523 PQueue()
00524 : PAbstractList() { DisallowDeleteObjects(); }
00526
00532 virtual PObject * Clone() const
00533 { return PNEW PQueue(0, this); }
00535
00541 virtual void Enqueue(
00542 T * obj
00543 ) { PAbstractList::Append(obj); }
00549 virtual T * Dequeue()
00550 { if (GetSize() == 0) return NULL; else return (T *)PAbstractList::RemoveAt(0);}
00552
00553 protected:
00554 PQueue(int dummy, const PQueue * c)
00555 : PAbstractList(dummy, c)
00556 { reference->deleteObjects = c->reference->deleteObjects; }
00557 };
00558
00559
00572 #define PQUEUE(cls, T) typedef PQueue<T> cls
00573
00574
00587 #define PDECLARE_QUEUE(cls, T) \
00588 PQUEUE(cls##_PTemplate, T); \
00589 PDECLARE_CLASS(cls, cls##_PTemplate) \
00590 protected: \
00591 cls(int dummy, const cls * c) \
00592 : cls##_PTemplate(dummy, c) { } \
00593 public: \
00594 cls() \
00595 : cls##_PTemplate() { } \
00596 virtual PObject * Clone() const \
00597 { return PNEW cls(0, this); } \
00598
00599
00612 template <class T> class PStack : public PAbstractList
00613 {
00614 PCLASSINFO(PStack, PAbstractList);
00615
00616 public:
00625 PStack()
00626 : PAbstractList() { DisallowDeleteObjects(); }
00628
00634 virtual PObject * Clone() const
00635 { return PNEW PStack(0, this); }
00637
00644 virtual void Push(
00645 T * obj
00646 ) { PAbstractList::InsertAt(0, obj); }
00647
00653 virtual T * Pop()
00654 { return (T *)PAbstractList::RemoveAt(0); }
00655
00662 virtual T & Top()
00663 { PAssert(GetSize() > 0, PStackEmpty); return *(T *)GetAt(0); }
00665
00666 protected:
00667 PStack(int dummy, const PStack * c)
00668 : PAbstractList(dummy, c)
00669 { reference->deleteObjects = c->reference->deleteObjects; }
00670 };
00671
00672
00685 #define PSTACK(cls, T) typedef PStack<T> cls
00686
00687
00700 #define PDECLARE_STACK(cls, T) \
00701 PSTACK(cls##_PTemplate, T); \
00702 PDECLARE_CLASS(cls, cls##_PTemplate) \
00703 protected: \
00704 cls(int dummy, const cls * c) \
00705 : cls##_PTemplate(dummy, c) { } \
00706 public: \
00707 cls() \
00708 : cls##_PTemplate() { } \
00709 virtual PObject * Clone() const \
00710 { return PNEW cls(0, this); } \
00711
00712
00713 #else // PHAS_TEMPLATES
00714
00715
00716 #define PLIST(cls, T) \
00717 class cls : public PAbstractList { \
00718 PCLASSINFO(cls, PAbstractList); \
00719 protected: \
00720 inline cls(int dummy, const cls * c) \
00721 : PAbstractList(dummy, c) { } \
00722 public: \
00723 inline cls() \
00724 : PAbstractList() { } \
00725 virtual PObject * Clone() const \
00726 { return PNEW cls(0, this); } \
00727 inline T & operator[](PINDEX index) const \
00728 { return (T &)GetReferenceAt(index); } \
00729 }
00730
00731 #define PDECLARE_LIST(cls, T) \
00732 PLIST(cls##_PTemplate, T); \
00733 PDECLARE_CLASS(cls, cls##_PTemplate) \
00734 protected: \
00735 cls(int dummy, const cls * c) \
00736 : cls##_PTemplate(dummy, c) { } \
00737 public: \
00738 cls() \
00739 : cls##_PTemplate() { } \
00740 virtual PObject * Clone() const \
00741 { return PNEW cls(0, this); } \
00742
00743
00744 #define PQUEUE(cls, T) \
00745 class cls : public PAbstractList { \
00746 PCLASSINFO(cls, PAbstractList); \
00747 protected: \
00748 inline cls(int dummy, const cls * c) \
00749 : PAbstractList(dummy, c) \
00750 { reference->deleteObjects = c->reference->deleteObjects; } \
00751 public: \
00752 inline cls() \
00753 : PAbstractList() { DisallowDeleteObjects(); } \
00754 virtual PObject * Clone() const \
00755 { return PNEW cls(0, this); } \
00756 virtual void Enqueue(T * t) \
00757 { PAbstractList::Append(t); } \
00758 virtual T * Dequeue() \
00759 { if (GetSize() == 0) return NULL; else return (T *)PAbstractList::RemoveAt(0);} \
00760 }
00761
00762 #define PDECLARE_QUEUE(cls, T) \
00763 PQUEUE(cls##_PTemplate, T); \
00764 PDECLARE_CLASS(cls, cls##_PTemplate) \
00765 protected: \
00766 cls(int dummy, const cls * c) \
00767 : cls##_PTemplate(dummy, c) { } \
00768 public: \
00769 cls() \
00770 : cls##_PTemplate() { } \
00771 virtual PObject * Clone() const \
00772 { return PNEW cls(0, this); } \
00773
00774 #define PSTACK(cls, T) \
00775 class cls : public PAbstractList { \
00776 PCLASSINFO(cls, PAbstractList); \
00777 protected: \
00778 inline cls(int dummy, const cls * c) \
00779 : PAbstractList(dummy, c) \
00780 { reference->deleteObjects = c->reference->deleteObjects; } \
00781 public: \
00782 inline cls() \
00783 : PAbstractList() { DisallowDeleteObjects(); } \
00784 virtual PObject * Clone() const \
00785 { return PNEW cls(0, this); } \
00786 virtual void Push(T * t) \
00787 { PAbstractList::InsertAt(0, t); } \
00788 virtual T * Pop() \
00789 { PAssert(GetSize() > 0, PStackEmpty); return (T *)PAbstractList::RemoveAt(0); } \
00790 virtual T & Top() \
00791 { PAssert(GetSize() > 0, PStackEmpty); return *(T *)GetAt(0); } \
00792 }
00793
00794 #define PDECLARE_STACK(cls, T) \
00795 PSTACK(cls##_PTemplate, T); \
00796 PDECLARE_CLASS(cls, cls##_PTemplate) \
00797 protected: \
00798 cls(int dummy, const cls * c) \
00799 : cls##_PTemplate(dummy, c) { } \
00800 public: \
00801 cls() \
00802 : cls##_PTemplate() { } \
00803 virtual PObject * Clone() const \
00804 { return PNEW cls(0, this); } \
00805
00806
00807 #endif // PHAS_TEMPLATES
00808
00809
00811
00812
00839 class PAbstractSortedList : public PCollection
00840 {
00841 PCONTAINERINFO(PAbstractSortedList, PCollection);
00842
00843 public:
00851 PAbstractSortedList();
00853
00883 virtual Comparison Compare(const PObject & obj) const;
00885
00895 virtual BOOL SetSize(
00896 PINDEX newSize
00897 );
00899
00908 virtual PINDEX Append(
00909 PObject * obj
00910 );
00911
00921 virtual PINDEX Insert(
00922 const PObject & before,
00923 PObject * obj
00924 );
00925
00935 virtual PINDEX InsertAt(
00936 PINDEX index,
00937 PObject * obj
00938 );
00939
00950 virtual BOOL Remove(
00951 const PObject * obj
00952 );
00953
00963 virtual PObject * RemoveAt(
00964 PINDEX index
00965 );
00966
00973 virtual void RemoveAll();
00974
00981 virtual BOOL SetAt(
00982 PINDEX index,
00983 PObject * val
00984 );
00985
00992 virtual PObject * GetAt(
00993 PINDEX index
00994 ) const;
00995
01007 virtual PINDEX GetObjectsIndex(
01008 const PObject * obj
01009 ) const;
01010
01019 virtual PINDEX GetValuesIndex(
01020 const PObject & obj
01021 ) const;
01023
01024 struct Element {
01025 friend class Info;
01026 Element * parent;
01027 Element * left;
01028 Element * right;
01029 PObject * data;
01030 PINDEX subTreeSize;
01031 enum { Red, Black } colour;
01032 };
01033
01034 protected:
01035 struct Info {
01036 Info();
01037
01038 Element * root;
01039 Element * lastElement;
01040 PINDEX lastIndex;
01041 Element nil;
01042
01043 Element * Successor(const Element * node) const;
01044 Element * Predecessor(const Element * node) const;
01045 Element * OrderSelect(Element * node, PINDEX index) const;
01046 } * info;
01047
01048
01049 void RemoveElement(Element * node);
01050 void LeftRotate(Element * node);
01051 void RightRotate(Element * node);
01052 void DeleteSubTrees(Element * node, BOOL deleteObject);
01053 PINDEX ValueSelect(const Element * node, const PObject & obj, const Element ** lastElement) const;
01054 };
01055
01056
01057 #ifdef PHAS_TEMPLATES
01058
01066 template <class T> class PSortedList : public PAbstractSortedList
01067 {
01068 PCLASSINFO(PSortedList, PAbstractSortedList);
01069
01070 public:
01078 PSortedList()
01079 : PAbstractSortedList() { }
01081
01087 virtual PObject * Clone() const
01088 { return PNEW PSortedList(0, this); }
01090
01103 T & operator[](PINDEX index) const
01104 { return *(T *)GetAt(index); }
01106
01107 protected:
01108 PSortedList(int dummy, const PSortedList * c)
01109 : PAbstractSortedList(dummy, c) { }
01110 };
01111
01112
01124 #define PSORTED_LIST(cls, T) typedef PSortedList<T> cls
01125
01126
01139 #define PDECLARE_SORTED_LIST(cls, T) \
01140 PSORTED_LIST(cls##_PTemplate, T); \
01141 PDECLARE_CLASS(cls, PSortedList<T>) \
01142 protected: \
01143 cls(int dummy, const cls * c) \
01144 : PSortedList<T>(dummy, c) { } \
01145 public: \
01146 cls() \
01147 : PSortedList<T>() { } \
01148 virtual PObject * Clone() const \
01149 { return PNEW cls(0, this); } \
01150
01151
01152 #else // PHAS_TEMPLATES
01153
01154
01155 #define PSORTED_LIST(cls, T) \
01156 class cls : public PAbstractSortedList { \
01157 PCLASSINFO(cls, PAbstractSortedList); \
01158 protected: \
01159 inline cls(int dummy, const cls * c) \
01160 : PAbstractSortedList(dummy, c) { } \
01161 public: \
01162 inline cls() \
01163 : PAbstractSortedList() { } \
01164 virtual PObject * Clone() const \
01165 { return PNEW cls(0, this); } \
01166 inline T & operator[](PINDEX index) const \
01167 { return *(T *)GetAt(index); } \
01168 }
01169
01170 #define PDECLARE_SORTED_LIST(cls, T) \
01171 PSORTED_LIST(cls##_PTemplate, T); \
01172 PDECLARE_CLASS(cls, cls##_PTemplate) \
01173 protected: \
01174 cls(int dummy, const cls * c) \
01175 : cls##_PTemplate(dummy, c) { } \
01176 public: \
01177 cls() \
01178 : cls##_PTemplate() { } \
01179 virtual PObject * Clone() const \
01180 { return PNEW cls(0, this); } \
01181
01182
01183 #endif // PHAS_TEMPLATES
01184
01185
01186