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
#ifdef P_USE_PRAGMA
00128
#pragma interface
00129
#endif
00130
00131
00133
00134
00155 class PAbstractList :
public PCollection
00156 {
00157
PCONTAINERINFO(
PAbstractList,
PCollection);
00158
00159
public:
00167
PINLINE PAbstractList();
00169
00170
00198
virtual Comparison
Compare(
const PObject & obj)
const;
00199
00209
virtual BOOL
SetSize(
00210 PINDEX newSize
00211 );
00213
00222
virtual PINDEX
Append(
00223
PObject * obj
00224 );
00225
00238
virtual PINDEX
Insert(
00239
const PObject & before,
00240
PObject * obj
00241 );
00242
00250
virtual PINDEX
InsertAt(
00251 PINDEX index,
00252
PObject * obj
00253 );
00254
00261
virtual BOOL
Remove(
00262
const PObject * obj
00263 );
00264
00274
virtual PObject *
RemoveAt(
00275 PINDEX index
00276 );
00277
00289
virtual BOOL
SetAt(
00290 PINDEX index,
00291
PObject * val
00292 );
00293
00304
virtual BOOL
ReplaceAt(
00305 PINDEX index,
00306
PObject * val
00307 );
00308
00319
virtual PObject *
GetAt(
00320 PINDEX index
00321 )
const;
00322
00330
virtual PINDEX
GetObjectsIndex(
00331
const PObject * obj
00332 )
const;
00333
00342
virtual PINDEX
GetValuesIndex(
00343
const PObject & obj
00344 )
const;
00346
00347
00348
protected:
00359
PINLINE PObject &
GetReferenceAt(
00360 PINDEX index
00361 )
const;
00362
00372 BOOL
SetCurrent(
00373 PINDEX index
00374 )
const;
00375
00376 class Element {
00377
public:
00378
friend class Info;
00379
Element(
PObject * theData);
00380 Element *
prev;
00381 Element *
next;
00382 PObject *
data;
00383 };
00384
00385 class Info {
00386
public:
00387 Info() {
head =
tail =
lastElement = NULL; }
00388 Element *
head;
00389 Element *
tail;
00390 Element *
lastElement;
00391 PINDEX
lastIndex;
00392 } *
info;
00393 };
00394
00395
00396
#ifdef PHAS_TEMPLATES
00397
00404
template <
class T>
class PList :
public PAbstractList
00405 {
00406
PCLASSINFO(PList,
PAbstractList);
00407
00408
public:
00416 PList()
00417 :
PAbstractList() { }
00419
00425
virtual PObject *
Clone()
const
00426
{
return PNEW PList(0,
this); }
00428
00442 T & operator[](PINDEX index)
const
00443
{
return (T &)GetReferenceAt(index); }
00445
00446
protected:
00447 PList(
int dummy,
const PList * c)
00448 :
PAbstractList(dummy, c) { }
00449 };
00450
00451
00463
#define PLIST(cls, T) typedef PList<T> cls
00464
00476
#define PDECLARE_LIST(cls, T) \
00477
PLIST(cls##_PTemplate, T); \
00478
PDECLARE_CLASS(cls, PList<T>) \
00479
protected: \
00480
cls(int dummy, const cls * c) \
00481
: PList<T>(dummy, c) { } \
00482
public: \
00483
cls() \
00484
: PList<T>() { } \
00485
virtual PObject * Clone() const \
00486
{ return PNEW cls(0, this); } \
00487
00488
00501
template <
class T>
class PQueue :
public PAbstractList
00502 {
00503
PCLASSINFO(PQueue,
PAbstractList);
00504
00505
public:
00514 PQueue()
00515 :
PAbstractList() {
DisallowDeleteObjects(); }
00517
00523
virtual PObject *
Clone()
const
00524
{
return PNEW PQueue(0,
this); }
00526
00532
virtual void Enqueue(
00533 T * obj
00534 ) {
PAbstractList::Append(obj); }
00540
virtual T * Dequeue()
00541 {
if (
GetSize() == 0)
return NULL;
else return (T *)
PAbstractList::RemoveAt(0);}
00543
00544
protected:
00545 PQueue(
int dummy,
const PQueue * c)
00546 :
PAbstractList(dummy, c)
00547 { reference->deleteObjects = c->reference->deleteObjects; }
00548 };
00549
00550
00563
#define PQUEUE(cls, T) typedef PQueue<T> cls
00564
00565
00578
#define PDECLARE_QUEUE(cls, T) \
00579
PQUEUE(cls##_PTemplate, T); \
00580
PDECLARE_CLASS(cls, cls##_PTemplate) \
00581
protected: \
00582
cls(int dummy, const cls * c) \
00583
: cls##_PTemplate(dummy, c) { } \
00584
public: \
00585
cls() \
00586
: cls##_PTemplate() { } \
00587
virtual PObject * Clone() const \
00588
{ return PNEW cls(0, this); } \
00589
00590
00603
template <
class T>
class PStack :
public PAbstractList
00604 {
00605
PCLASSINFO(PStack,
PAbstractList);
00606
00607
public:
00616 PStack()
00617 :
PAbstractList() {
DisallowDeleteObjects(); }
00619
00625
virtual PObject *
Clone()
const
00626
{
return PNEW PStack(0,
this); }
00628
00635
virtual void Push(
00636 T * obj
00637 ) {
PAbstractList::InsertAt(0, obj); }
00638
00644
virtual T * Pop()
00645 {
return (T *)
PAbstractList::RemoveAt(0); }
00646
00653
virtual T & Top()
00654 {
PAssert(
GetSize() > 0, PStackEmpty);
return *(T *)GetAt(0); }
00656
00657
protected:
00658 PStack(
int dummy,
const PStack * c)
00659 :
PAbstractList(dummy, c)
00660 { reference->deleteObjects = c->reference->deleteObjects; }
00661 };
00662
00663
00676
#define PSTACK(cls, T) typedef PStack<T> cls
00677
00678
00691
#define PDECLARE_STACK(cls, T) \
00692
PSTACK(cls##_PTemplate, T); \
00693
PDECLARE_CLASS(cls, cls##_PTemplate) \
00694
protected: \
00695
cls(int dummy, const cls * c) \
00696
: cls##_PTemplate(dummy, c) { } \
00697
public: \
00698
cls() \
00699
: cls##_PTemplate() { } \
00700
virtual PObject * Clone() const \
00701
{ return PNEW cls(0, this); } \
00702
00703
00704
#else // PHAS_TEMPLATES
00705
00706
00707 #define PLIST(cls, T) \
00708
class cls : public PAbstractList { \
00709
PCLASSINFO(cls, PAbstractList); \
00710
protected: \
00711
inline cls(int dummy, const cls * c) \
00712
: PAbstractList(dummy, c) { } \
00713
public: \
00714
inline cls() \
00715
: PAbstractList() { } \
00716
virtual PObject * Clone() const \
00717
{ return PNEW cls(0, this); } \
00718
inline T & operator[](PINDEX index) const \
00719
{ return (T &)GetReferenceAt(index); } \
00720
}
00721
00722 #define PDECLARE_LIST(cls, T) \
00723
PLIST(cls##_PTemplate, T); \
00724
PDECLARE_CLASS(cls, cls##_PTemplate) \
00725
protected: \
00726
cls(int dummy, const cls * c) \
00727
: cls##_PTemplate(dummy, c) { } \
00728
public: \
00729
cls() \
00730
: cls##_PTemplate() { } \
00731
virtual PObject * Clone() const \
00732
{ return PNEW cls(0, this); } \
00733
00734
00735 #define PQUEUE(cls, T) \
00736
class cls : public PAbstractList { \
00737
PCLASSINFO(cls, PAbstractList); \
00738
protected: \
00739
inline cls(int dummy, const cls * c) \
00740
: PAbstractList(dummy, c) \
00741
{ reference->deleteObjects = c->reference->deleteObjects; } \
00742
public: \
00743
inline cls() \
00744
: PAbstractList() { DisallowDeleteObjects(); } \
00745
virtual PObject * Clone() const \
00746
{ return PNEW cls(0, this); } \
00747
virtual void Enqueue(T * t) \
00748
{ PAbstractList::Append(t); } \
00749
virtual T * Dequeue() \
00750
{ if (GetSize() == 0) return NULL; else return (T *)PAbstractList::RemoveAt(0);} \
00751
}
00752
00753 #define PDECLARE_QUEUE(cls, T) \
00754
PQUEUE(cls##_PTemplate, T); \
00755
PDECLARE_CLASS(cls, cls##_PTemplate) \
00756
protected: \
00757
cls(int dummy, const cls * c) \
00758
: cls##_PTemplate(dummy, c) { } \
00759
public: \
00760
cls() \
00761
: cls##_PTemplate() { } \
00762
virtual PObject * Clone() const \
00763
{ return PNEW cls(0, this); } \
00764
00765 #define PSTACK(cls, T) \
00766
class cls : public PAbstractList { \
00767
PCLASSINFO(cls, PAbstractList); \
00768
protected: \
00769
inline cls(int dummy, const cls * c) \
00770
: PAbstractList(dummy, c) \
00771
{ reference->deleteObjects = c->reference->deleteObjects; } \
00772
public: \
00773
inline cls() \
00774
: PAbstractList() { DisallowDeleteObjects(); } \
00775
virtual PObject * Clone() const \
00776
{ return PNEW cls(0, this); } \
00777
virtual void Push(T * t) \
00778
{ PAbstractList::InsertAt(0, t); } \
00779
virtual T * Pop() \
00780
{ PAssert(GetSize() > 0, PStackEmpty); return (T *)PAbstractList::RemoveAt(0); } \
00781
virtual T & Top() \
00782
{ PAssert(GetSize() > 0, PStackEmpty); return *(T *)GetAt(0); } \
00783
}
00784
00785 #define PDECLARE_STACK(cls, T) \
00786
PSTACK(cls##_PTemplate, T); \
00787
PDECLARE_CLASS(cls, cls##_PTemplate) \
00788
protected: \
00789
cls(int dummy, const cls * c) \
00790
: cls##_PTemplate(dummy, c) { } \
00791
public: \
00792
cls() \
00793
: cls##_PTemplate() { } \
00794
virtual PObject * Clone() const \
00795
{ return PNEW cls(0, this); } \
00796
00797
00798
#endif // PHAS_TEMPLATES
00799
00800
00802
00803
00830 class PAbstractSortedList :
public PCollection
00831 {
00832
PCONTAINERINFO(
PAbstractSortedList,
PCollection);
00833
00834
public:
00842
PAbstractSortedList();
00844
00874
virtual Comparison
Compare(
const PObject & obj)
const;
00876
00886
virtual BOOL
SetSize(
00887 PINDEX newSize
00888 );
00890
00899
virtual PINDEX
Append(
00900
PObject * obj
00901 );
00902
00912
virtual PINDEX
Insert(
00913
const PObject & before,
00914
PObject * obj
00915 );
00916
00926
virtual PINDEX
InsertAt(
00927 PINDEX index,
00928
PObject * obj
00929 );
00930
00941
virtual BOOL
Remove(
00942
const PObject * obj
00943 );
00944
00954
virtual PObject *
RemoveAt(
00955 PINDEX index
00956 );
00957
00964
virtual void RemoveAll();
00965
00972
virtual BOOL
SetAt(
00973 PINDEX index,
00974
PObject * val
00975 );
00976
00983
virtual PObject *
GetAt(
00984 PINDEX index
00985 )
const;
00986
00998
virtual PINDEX
GetObjectsIndex(
00999
const PObject * obj
01000 )
const;
01001
01010
virtual PINDEX
GetValuesIndex(
01011
const PObject & obj
01012 )
const;
01014
01015
protected:
01016 struct Element {
01017
friend class Info;
01018 Element *
parent;
01019 Element *
left;
01020 Element *
right;
01021 PObject *
data;
01022 PINDEX
subTreeSize;
01023
enum {
Red,
Black } colour;
01024 };
01025
01026 struct Info {
01027 Element *
root;
01028 Element *
lastElement;
01029 PINDEX
lastIndex;
01030 Element nil;
01031 } *
info;
01032
01033
01034
void RemoveElement(
Element * node);
01035
void LeftRotate(
Element * node);
01036
void RightRotate(
Element * node);
01037
void DeleteSubTrees(
Element * node, BOOL deleteObject);
01038
Element *
Successor(
const Element * node)
const;
01039
Element *
Predecessor(
const Element * node)
const;
01040
Element *
OrderSelect(
Element * node, PINDEX index)
const;
01041 PINDEX
ValueSelect(
const Element * node,
const PObject & obj,
const Element ** lastElement)
const;
01042 };
01043
01044
01045
#ifdef PHAS_TEMPLATES
01046
01054
template <
class T>
class PSortedList :
public PAbstractSortedList
01055 {
01056
PCLASSINFO(PSortedList,
PAbstractSortedList);
01057
01058
public:
01066 PSortedList()
01067 :
PAbstractSortedList() { }
01069
01075
virtual PObject *
Clone()
const
01076
{
return PNEW PSortedList(0,
this); }
01078
01091 T & operator[](PINDEX index)
const
01092
{
return *(T *)GetAt(index); }
01094
01095
protected:
01096 PSortedList(
int dummy,
const PSortedList * c)
01097 :
PAbstractSortedList(dummy, c) { }
01098 };
01099
01100
01112
#define PSORTED_LIST(cls, T) typedef PSortedList<T> cls
01113
01114
01127
#define PDECLARE_SORTED_LIST(cls, T) \
01128
PSORTED_LIST(cls##_PTemplate, T); \
01129
PDECLARE_CLASS(cls, PSortedList<T>) \
01130
protected: \
01131
cls(int dummy, const cls * c) \
01132
: PSortedList<T>(dummy, c) { } \
01133
public: \
01134
cls() \
01135
: PSortedList<T>() { } \
01136
virtual PObject * Clone() const \
01137
{ return PNEW cls(0, this); } \
01138
01139
01140
#else // PHAS_TEMPLATES
01141
01142
01143 #define PSORTED_LIST(cls, T) \
01144
class cls : public PAbstractSortedList { \
01145
PCLASSINFO(cls, PAbstractSortedList); \
01146
protected: \
01147
inline cls(int dummy, const cls * c) \
01148
: PAbstractSortedList(dummy, c) { } \
01149
public: \
01150
inline cls() \
01151
: PAbstractSortedList() { } \
01152
virtual PObject * Clone() const \
01153
{ return PNEW cls(0, this); } \
01154
inline T & operator[](PINDEX index) const \
01155
{ return *(T *)GetAt(index); } \
01156
}
01157
01158 #define PDECLARE_SORTED_LIST(cls, T) \
01159
PSORTED_LIST(cls##_PTemplate, T); \
01160
PDECLARE_CLASS(cls, cls##_PTemplate) \
01161
protected: \
01162
cls(int dummy, const cls * c) \
01163
: cls##_PTemplate(dummy, c) { } \
01164
public: \
01165
cls() \
01166
: cls##_PTemplate() { } \
01167
virtual PObject * Clone() const \
01168
{ return PNEW cls(0, this); } \
01169
01170
01171
#endif // PHAS_TEMPLATES
01172
01173
01174