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
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158 #ifndef __DICT_H__
00159 #define __DICT_H__
00160
00161 #ifdef P_USE_PRAGMA
00162 #pragma interface
00163 #endif
00164
00165 #include <ptlib/array.h>
00166
00168
00169
00173 class POrdinalKey : public PObject
00174 {
00175 PCLASSINFO(POrdinalKey, PObject);
00176
00177 public:
00182 PINLINE POrdinalKey(
00183 PINDEX newKey = 0
00184 );
00185
00188 PINLINE POrdinalKey & operator=(PINDEX);
00190
00193
00194 virtual PObject * Clone() const;
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204
00205 virtual Comparison Compare(const PObject & obj) const;
00206
00213 virtual PINDEX HashFunction() const;
00214
00221 virtual void PrintOn(ostream & strm) const;
00223
00228 PINLINE operator PINDEX() const;
00229
00232 PINLINE PINDEX operator++();
00233
00236 PINLINE PINDEX operator++(int);
00237
00240 PINLINE PINDEX operator--();
00241
00244 PINLINE PINDEX operator--(int);
00245
00248 PINLINE POrdinalKey & operator+=(PINDEX);
00249
00252 PINLINE POrdinalKey & operator-=(PINDEX );
00254
00255 private:
00256 PINDEX theKey;
00257 };
00258
00259
00261
00272 class PHashTable : public PCollection
00273 {
00274 PCONTAINERINFO(PHashTable, PCollection);
00275
00276 public:
00279
00280 PHashTable();
00282
00294 virtual Comparison Compare(
00295 const PObject & obj
00296 ) const;
00298
00299
00300 protected:
00310 virtual BOOL SetSize(
00311 PINDEX newSize
00312 );
00314
00315
00326 PINLINE BOOL AbstractContains(
00327 const PObject & key
00328 ) const;
00329
00344 virtual const PObject & AbstractGetKeyAt(
00345 PINDEX index
00346 ) const;
00347
00362 virtual PObject & AbstractGetDataAt(
00363 PINDEX index
00364 ) const;
00366
00367
00368
00369 class Element {
00370 public:
00371 friend class Table;
00372 PObject * key;
00373 PObject * data;
00374 Element * next;
00375 Element * prev;
00376 };
00377
00378 PDECLARE_BASEARRAY(Table, Element *)
00379 #ifdef DOC_PLUS_PLUS
00380 {
00381 #endif
00382 public:
00383 virtual ~Table() { Destruct(); }
00384 virtual void DestroyContents();
00385
00386 PINDEX AppendElement(PObject * key, PObject * data);
00387 PObject * RemoveElement(const PObject & key);
00388 BOOL SetLastElementAt(PINDEX index);
00389 Element * GetElementAt(const PObject & key);
00390 PINDEX GetElementsIndex(const PObject*obj,BOOL byVal,BOOL keys) const;
00391
00392 PINDEX lastIndex;
00393 PINDEX lastBucket;
00394 Element * lastElement;
00395
00396 BOOL deleteKeys;
00397
00398 friend class PHashTable;
00399 friend class PAbstractSet;
00400 };
00401 friend class Table;
00402
00403
00404 Table * hashTable;
00405 };
00406
00407
00409
00412 class PAbstractSet : public PHashTable
00413 {
00414 PCONTAINERINFO(PAbstractSet, PHashTable);
00415 public:
00423 PINLINE PAbstractSet();
00425
00436 virtual PINDEX Append(
00437 PObject * obj
00438 );
00439
00452 virtual PINDEX Insert(
00453 const PObject & before,
00454 PObject * obj
00455 );
00456
00469 virtual PINDEX InsertAt(
00470 PINDEX index,
00471 PObject * obj
00472 );
00473
00484 virtual BOOL Remove(
00485 const PObject * obj
00486 );
00487
00494 virtual PObject * RemoveAt(
00495 PINDEX index
00496 );
00497
00503 virtual PObject * GetAt(
00504 PINDEX index
00505 ) const;
00506
00519 virtual BOOL SetAt(
00520 PINDEX index,
00521 PObject * val
00522 );
00523
00535 virtual PINDEX GetObjectsIndex(
00536 const PObject * obj
00537 ) const;
00538
00547 virtual PINDEX GetValuesIndex(
00548 const PObject & obj
00549 ) const;
00551 };
00552
00553
00554 #ifdef PHAS_TEMPLATES
00555
00566 template <class T> class PSet : public PAbstractSet
00567 {
00568 PCLASSINFO(PSet, PAbstractSet);
00569
00570 public:
00580 inline PSet(BOOL initialDeleteObjects = FALSE)
00581 : PAbstractSet() { AllowDeleteObjects(initialDeleteObjects); }
00583
00589 virtual PObject * Clone() const
00590 { return PNEW PSet(0, this); }
00592
00604 void Include(
00605 const T * obj
00606 ) { Append((PObject *)obj); }
00607
00615 PSet & operator+=(
00616 const T & obj
00617 ) { Append(obj.Clone()); return *this; }
00618
00626 void Exclude(
00627 const T * obj
00628 ) { Remove(obj); }
00629
00637 PSet & operator-=(
00638 const T & obj
00639 ) { RemoveAt(GetValuesIndex(obj)); return *this; }
00640
00649 BOOL Contains(
00650 const T & key
00651 ) const { return AbstractContains(key); }
00652
00661 BOOL operator[](
00662 const T & key
00663 ) const { return AbstractContains(key); }
00664
00676 virtual const T & GetKeyAt(
00677 PINDEX index
00678 ) const
00679 { return (const T &)AbstractGetKeyAt(index); }
00681
00682
00683 protected:
00684 PSet(int dummy, const PSet * c)
00685 : PAbstractSet(dummy, c)
00686 { reference->deleteObjects = c->reference->deleteObjects; }
00687 };
00688
00689
00701 #define PSET(cls, T) typedef PSet<T> cls
00702
00703
00715 #define PDECLARE_SET(cls, T, initDelObj) \
00716 PSET(cls##_PTemplate, T); \
00717 PDECLARE_CLASS(cls, cls##_PTemplate) \
00718 protected: \
00719 cls(int dummy, const cls * c) \
00720 : cls##_PTemplate(dummy, c) { } \
00721 public: \
00722 cls(BOOL initialDeleteObjects = initDelObj) \
00723 : cls##_PTemplate(initialDeleteObjects) { } \
00724 virtual PObject * Clone() const \
00725 { return PNEW cls(0, this); } \
00726
00727
00728 #else // PHAS_TEMPLATES
00729
00730
00731 #define PSET(cls, K) \
00732 class cls : public PAbstractSet { \
00733 PCLASSINFO(cls, PAbstractSet); \
00734 protected: \
00735 inline cls(int dummy, const cls * c) \
00736 : PAbstractSet(dummy, c) \
00737 { reference->deleteObjects = c->reference->deleteObjects; } \
00738 public: \
00739 inline cls(BOOL initialDeleteObjects = FALSE) \
00740 : PAbstractSet() { AllowDeleteObjects(initialDeleteObjects); } \
00741 virtual PObject * Clone() const \
00742 { return PNEW cls(0, this); } \
00743 inline void Include(const PObject * key) \
00744 { Append((PObject *)key); } \
00745 inline void Exclude(const PObject * key) \
00746 { Remove(key); } \
00747 inline BOOL operator[](const K & key) const \
00748 { return AbstractContains(key); } \
00749 inline BOOL Contains(const K & key) const \
00750 { return AbstractContains(key); } \
00751 virtual const K & GetKeyAt(PINDEX index) const \
00752 { return (const K &)AbstractGetKeyAt(index); } \
00753 }
00754
00755 #define PDECLARE_SET(cls, K, initDelObj) \
00756 PSET(cls##_PTemplate, K); \
00757 PDECLARE_CLASS(cls, cls##_PTemplate) \
00758 protected: \
00759 inline cls(int dummy, const cls * c) \
00760 : cls##_PTemplate(dummy, c) { } \
00761 public: \
00762 inline cls(BOOL initialDeleteObjects = initDelObj) \
00763 : cls##_PTemplate() { AllowDeleteObjects(initialDeleteObjects); } \
00764 virtual PObject * Clone() const \
00765 { return PNEW cls(0, this); } \
00766
00767
00768 #endif // PHAS_TEMPLATES
00769
00770
00771 PSET(POrdinalSet, POrdinalKey);
00772
00773
00775
00778 class PAbstractDictionary : public PHashTable
00779 {
00780 PCLASSINFO(PAbstractDictionary, PHashTable);
00781 public:
00789 PINLINE PAbstractDictionary();
00791
00800 virtual void PrintOn(
00801 ostream &strm
00802 ) const;
00804
00815 virtual PINDEX Insert(
00816 const PObject & key,
00817 PObject * obj
00818 );
00819
00826 virtual PINDEX InsertAt(
00827 PINDEX index,
00828 PObject * obj
00829 );
00830
00840 virtual PObject * RemoveAt(
00841 PINDEX index
00842 );
00843
00852 virtual BOOL SetAt(
00853 PINDEX index,
00854 PObject * val
00855 );
00856
00864 virtual PObject * GetAt(
00865 PINDEX index
00866 ) const;
00867
00879 virtual PINDEX GetObjectsIndex(
00880 const PObject * obj
00881 ) const;
00882
00891 virtual PINDEX GetValuesIndex(
00892 const PObject & obj
00893 ) const;
00895
00896
00907 virtual BOOL SetDataAt(
00908 PINDEX index,
00909 PObject * obj
00910 );
00911
00923 virtual BOOL AbstractSetAt(
00924 const PObject & key,
00925 PObject * obj
00926 );
00927
00937 virtual PObject & GetRefAt(
00938 const PObject & key
00939 ) const;
00940
00947 virtual PObject * AbstractGetAt(
00948 const PObject & key
00949 ) const;
00951
00952 protected:
00953 PINLINE PAbstractDictionary(int dummy, const PAbstractDictionary * c);
00954
00955 private:
00956 virtual PINDEX Append(
00957 PObject * obj
00958 );
00959
00960
00961
00962
00963
00964
00965 virtual BOOL Remove(
00966 const PObject * obj
00967 );
00968
00969
00970
00971
00972
00973
00974
00975
00976
00977
00978
00979 };
00980
00981
00982 #ifdef PHAS_TEMPLATES
00983
00991 template <class K, class D> class PDictionary : public PAbstractDictionary
00992 {
00993 PCLASSINFO(PDictionary, PAbstractDictionary);
00994
00995 public:
01004 PDictionary()
01005 : PAbstractDictionary() { }
01007
01014 virtual PObject * Clone() const
01015 { return PNEW PDictionary(0, this); }
01017
01030 D & operator[](
01031 const K & key
01032 ) const
01033 { return (D &)GetRefAt(key); }
01034
01043 BOOL Contains(
01044 const K & key
01045 ) const { return AbstractContains(key); }
01046
01058 virtual D * RemoveAt(
01059 const K & key
01060 ) {
01061 D * obj = GetAt(key); AbstractSetAt(key, NULL);
01062 return reference->deleteObjects ? (obj ? (D *)-1 : NULL) : obj;
01063 }
01064
01076 virtual BOOL SetAt(
01077 const K & key,
01078 D * obj
01079 ) { return AbstractSetAt(key, obj); }
01080
01087 virtual D * GetAt(
01088 const K & key
01089 ) const { return (D *)AbstractGetAt(key); }
01090
01102 const K & GetKeyAt(
01103 PINDEX index
01104 ) const
01105 { return (const K &)AbstractGetKeyAt(index); }
01106
01118 D & GetDataAt(
01119 PINDEX index
01120 ) const
01121 { return (D &)AbstractGetDataAt(index); }
01123
01124 protected:
01125 PDictionary(int dummy, const PDictionary * c)
01126 : PAbstractDictionary(dummy, c) { }
01127 };
01128
01129
01142 #define PDICTIONARY(cls, K, D) typedef PDictionary<K, D> cls
01143
01144
01157 #define PDECLARE_DICTIONARY(cls, K, D) \
01158 PDICTIONARY(cls##_PTemplate, K, D); \
01159 PDECLARE_CLASS(cls, cls##_PTemplate) \
01160 protected: \
01161 cls(int dummy, const cls * c) \
01162 : cls##_PTemplate(dummy, c) { } \
01163 public: \
01164 cls() \
01165 : cls##_PTemplate() { } \
01166 virtual PObject * Clone() const \
01167 { return PNEW cls(0, this); } \
01168
01169
01177 template <class K> class POrdinalDictionary : public PAbstractDictionary
01178 {
01179 PCLASSINFO(POrdinalDictionary, PAbstractDictionary);
01180
01181 public:
01190 POrdinalDictionary()
01191 : PAbstractDictionary() { }
01193
01200 virtual PObject * Clone() const
01201 { return PNEW POrdinalDictionary(0, this); }
01203
01216 PINDEX operator[](
01217 const K & key
01218 ) const
01219 { return (POrdinalKey &)GetRefAt(key); }
01220
01229 BOOL Contains(
01230 const K & key
01231 ) const { return AbstractContains(key); }
01232
01233 virtual POrdinalKey * GetAt(
01234 const K & key
01235 ) const { return (POrdinalKey *)AbstractGetAt(key); }
01236
01237
01238
01239
01240
01241
01242
01251 virtual BOOL SetDataAt(
01252 PINDEX index,
01253 PINDEX ordinal
01254 ) { return PAbstractDictionary::SetDataAt(index, PNEW POrdinalKey(ordinal)); }
01255
01267 virtual BOOL SetAt(
01268 const K & key,
01269 PINDEX ordinal
01270 ) { return AbstractSetAt(key, PNEW POrdinalKey(ordinal)); }
01271
01280 virtual PINDEX RemoveAt(
01281 const K & key
01282 ) { PINDEX ord = *GetAt(key); AbstractSetAt(key, NULL); return ord; }
01283
01295 const K & GetKeyAt(
01296 PINDEX index
01297 ) const
01298 { return (const K &)AbstractGetKeyAt(index); }
01299
01311 PINDEX GetDataAt(
01312 PINDEX index
01313 ) const
01314 { return (POrdinalKey &)AbstractGetDataAt(index); }
01316
01317 protected:
01318 POrdinalDictionary(int dummy, const POrdinalDictionary * c)
01319 : PAbstractDictionary(dummy, c) { }
01320 };
01321
01322
01335 #define PORDINAL_DICTIONARY(cls, K) typedef POrdinalDictionary<K> cls
01336
01337
01352 #define PDECLARE_ORDINAL_DICTIONARY(cls, K) \
01353 PORDINAL_DICTIONARY(cls##_PTemplate, K); \
01354 PDECLARE_CLASS(cls, POrdinalDictionary<K>) \
01355 protected: \
01356 cls(int dummy, const cls * c) \
01357 : cls##_PTemplate(dummy, c) { } \
01358 public: \
01359 cls() \
01360 : cls##_PTemplate() { } \
01361 virtual PObject * Clone() const \
01362 { return PNEW cls(0, this); } \
01363
01364
01365 #else // PHAS_TEMPLATES
01366
01367
01368 #define PDICTIONARY(cls, K, D) \
01369 class cls : public PAbstractDictionary { \
01370 PCLASSINFO(cls, PAbstractDictionary); \
01371 protected: \
01372 inline cls(int dummy, const cls * c) \
01373 : PAbstractDictionary(dummy, c) { } \
01374 public: \
01375 cls() \
01376 : PAbstractDictionary() { } \
01377 virtual PObject * Clone() const \
01378 { return PNEW cls(0, this); } \
01379 D & operator[](const K & key) const \
01380 { return (D &)GetRefAt(key); } \
01381 virtual BOOL Contains(const K & key) const \
01382 { return AbstractContains(key); } \
01383 virtual D * RemoveAt(const K & key) \
01384 { D * obj = GetAt(key); AbstractSetAt(key, NULL); return obj; } \
01385 virtual BOOL SetAt(const K & key, D * obj) \
01386 { return AbstractSetAt(key, obj); } \
01387 virtual D * GetAt(const K & key) const \
01388 { return (D *)AbstractGetAt(key); } \
01389 const K & GetKeyAt(PINDEX index) const \
01390 { return (const K &)AbstractGetKeyAt(index); } \
01391 D & GetDataAt(PINDEX index) const \
01392 { return (D &)AbstractGetDataAt(index); } \
01393 }
01394
01395 #define PDECLARE_DICTIONARY(cls, K, D) \
01396 PDICTIONARY(cls##_PTemplate, K, D); \
01397 PDECLARE_CLASS(cls, cls##_PTemplate) \
01398 protected: \
01399 cls(int dummy, const cls * c) \
01400 : cls##_PTemplate(dummy, c) { } \
01401 public: \
01402 cls() \
01403 : cls##_PTemplate() { } \
01404 virtual PObject * Clone() const \
01405 { return PNEW cls(0, this); } \
01406
01407
01408 #define PORDINAL_DICTIONARY(cls, K) \
01409 class cls : public PAbstractDictionary { \
01410 PCLASSINFO(cls, PAbstractDictionary); \
01411 protected: \
01412 inline cls(int dummy, const cls * c) \
01413 : PAbstractDictionary(dummy, c) { } \
01414 public: \
01415 inline cls() \
01416 : PAbstractDictionary() { } \
01417 virtual PObject * Clone() const \
01418 { return PNEW cls(0, this); } \
01419 inline PINDEX operator[](const K & key) const \
01420 { return (POrdinalKey &)GetRefAt(key); } \
01421 virtual BOOL Contains(const K & key) const \
01422 { return AbstractContains(key); } \
01423 virtual POrdinalKey * GetAt(const K & key) const \
01424 { return (POrdinalKey *)AbstractGetAt(key); } \
01425 virtual BOOL SetDataAt(PINDEX index, PINDEX ordinal) \
01426 { return PAbstractDictionary::SetDataAt(index, PNEW POrdinalKey(ordinal)); } \
01427 virtual BOOL SetAt(const K & key, PINDEX ordinal) \
01428 { return AbstractSetAt(key, PNEW POrdinalKey(ordinal)); } \
01429 virtual PINDEX RemoveAt(const K & key) \
01430 { PINDEX ord = *GetAt(key); AbstractSetAt(key, NULL); return ord; } \
01431 inline const K & GetKeyAt(PINDEX index) const \
01432 { return (const K &)AbstractGetKeyAt(index); } \
01433 inline PINDEX GetDataAt(PINDEX index) const \
01434 { return (POrdinalKey &)AbstractGetDataAt(index); } \
01435 }
01436
01437 #define PDECLARE_ORDINAL_DICTIONARY(cls, K) \
01438 PORDINAL_DICTIONARY(cls##_PTemplate, K); \
01439 PDECLARE_CLASS(cls, cls##_PTemplate) \
01440 protected: \
01441 cls(int dummy, const cls * c) \
01442 : cls##_PTemplate(dummy, c) { } \
01443 public: \
01444 cls() \
01445 : cls##_PTemplate() { } \
01446 virtual PObject * Clone() const \
01447 { return PNEW cls(0, this); } \
01448
01449
01450 #endif // PHAS_TEMPLATES
01451
01452 #endif // #ifndef __DICT_H__
01453
01454