PTLib
Version 2.10.4
|
00001 /* 00002 * dict.h 00003 * 00004 * Dictionary (hash table) Container classes. 00005 * 00006 * Portable Tools 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: 25554 $ 00030 * $Author: rjongbloed $ 00031 * $Date: 2011-04-13 03:34:50 -0500 (Wed, 13 Apr 2011) $ 00032 */ 00033 00034 00035 #ifndef PTLIB_DICT_H 00036 #define PTLIB_DICT_H 00037 00038 #ifdef P_USE_PRAGMA 00039 #pragma interface 00040 #endif 00041 00042 #include <ptlib/array.h> 00043 00045 // PDictionary classes 00046 00050 class POrdinalKey : public PObject 00051 { 00052 PCLASSINFO(POrdinalKey, PObject); 00053 00054 public: 00059 PINLINE POrdinalKey( 00060 PINDEX newKey = 0 00061 ); 00062 00065 PINLINE POrdinalKey & operator=(PINDEX); 00067 00070 00071 virtual PObject * Clone() const; 00072 00073 /* Get the relative rank of the ordinal index. This is a simpel comparison 00074 of the objects PINDEX values. 00075 00076 @return 00077 comparison of the two objects, <code>EqualTo</code> for same, 00078 <code>LessThan</code> for \p obj logically less than the 00079 object and <code>GreaterThan</code> for \p obj logically 00080 greater than the object. 00081 */ 00082 virtual Comparison Compare(const PObject & obj) const; 00083 00090 virtual PINDEX HashFunction() const; 00091 00098 virtual void PrintOn(ostream & strm) const; 00100 00105 PINLINE operator PINDEX() const; 00106 00109 PINLINE PINDEX operator++(); 00110 00113 PINLINE PINDEX operator++(int); 00114 00117 PINLINE PINDEX operator--(); 00118 00121 PINLINE PINDEX operator--(int); 00122 00125 PINLINE POrdinalKey & operator+=(PINDEX); 00126 00129 PINLINE POrdinalKey & operator-=(PINDEX ); 00131 00132 private: 00133 PINDEX theKey; 00134 }; 00135 00136 00138 00139 // Member variables 00140 struct PHashTableElement 00141 { 00142 PObject * key; 00143 PObject * data; 00144 PHashTableElement * next; 00145 PHashTableElement * prev; 00146 00147 PDECLARE_POOL_ALLOCATOR(); 00148 }; 00149 00150 PDECLARE_BASEARRAY(PHashTableInfo, PHashTableElement *) 00151 #ifdef DOC_PLUS_PLUS 00152 { 00153 #endif 00154 public: 00155 virtual ~PHashTableInfo() { Destruct(); } 00156 virtual void DestroyContents(); 00157 00158 PINDEX AppendElement(PObject * key, PObject * data); 00159 PObject * RemoveElement(const PObject & key); 00160 PBoolean SetLastElementAt(PINDEX index, PHashTableElement * & lastElement); 00161 PHashTableElement * GetElementAt(const PObject & key); 00162 PINDEX GetElementsIndex(const PObject*obj,PBoolean byVal,PBoolean keys) const; 00163 00164 PBoolean deleteKeys; 00165 00166 typedef PHashTableElement Element; 00167 friend class PHashTable; 00168 friend class PAbstractSet; 00169 }; 00170 00171 00182 class PHashTable : public PCollection 00183 { 00184 PCONTAINERINFO(PHashTable, PCollection); 00185 00186 public: 00189 00190 PHashTable(); 00192 00204 virtual Comparison Compare( 00205 const PObject & obj 00206 ) const; 00208 00209 00219 virtual PBoolean SetSize( 00220 PINDEX newSize 00221 ); 00223 00224 00235 PINLINE PBoolean AbstractContains( 00236 const PObject & key 00237 ) const; 00238 00253 virtual const PObject & AbstractGetKeyAt( 00254 PINDEX index 00255 ) const; 00256 00271 virtual PObject & AbstractGetDataAt( 00272 PINDEX index 00273 ) const; 00275 00276 // The type below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it 00277 typedef PHashTableElement Element; 00278 typedef PHashTableInfo Table; 00279 PHashTableInfo * hashTable; 00280 }; 00281 00282 00284 00287 class PAbstractSet : public PHashTable 00288 { 00289 PCONTAINERINFO(PAbstractSet, PHashTable); 00290 public: 00298 PINLINE PAbstractSet(); 00300 00311 virtual PINDEX Append( 00312 PObject * obj 00313 ); 00314 00327 virtual PINDEX Insert( 00328 const PObject & before, 00329 PObject * obj 00330 ); 00331 00344 virtual PINDEX InsertAt( 00345 PINDEX index, 00346 PObject * obj 00347 ); 00348 00359 virtual PBoolean Remove( 00360 const PObject * obj 00361 ); 00362 00369 virtual PObject * RemoveAt( 00370 PINDEX index 00371 ); 00372 00378 virtual PObject * GetAt( 00379 PINDEX index 00380 ) const; 00381 00394 virtual PBoolean SetAt( 00395 PINDEX index, 00396 PObject * val 00397 ); 00398 00410 virtual PINDEX GetObjectsIndex( 00411 const PObject * obj 00412 ) const; 00413 00422 virtual PINDEX GetValuesIndex( 00423 const PObject & obj 00424 ) const; 00426 }; 00427 00428 00439 template <class T> class PSet : public PAbstractSet 00440 { 00441 PCLASSINFO(PSet, PAbstractSet); 00442 00443 public: 00453 inline PSet(PBoolean initialDeleteObjects = false) 00454 : PAbstractSet() { AllowDeleteObjects(initialDeleteObjects); } 00456 00462 virtual PObject * Clone() const 00463 { return PNEW PSet(0, this); } 00465 00477 void Include( 00478 const T * obj // New object to include in the set. 00479 ) { Append((PObject *)obj); } 00480 00488 PSet & operator+=( 00489 const T & obj // New object to include in the set. 00490 ) { Append(obj.Clone()); return *this; } 00491 00499 void Exclude( 00500 const T * obj // New object to exclude in the set. 00501 ) { Remove(obj); } 00502 00510 PSet & operator-=( 00511 const T & obj // New object to exclude in the set. 00512 ) { RemoveAt(GetValuesIndex(obj)); return *this; } 00513 00522 PBoolean Contains( 00523 const T & key 00524 ) const { return AbstractContains(key); } 00525 00534 PBoolean operator[]( 00535 const T & key 00536 ) const { return AbstractContains(key); } 00537 00549 virtual const T & GetKeyAt( 00550 PINDEX index 00551 ) const 00552 { return (const T &)AbstractGetKeyAt(index); } 00554 00555 00556 protected: 00557 PSet(int dummy, const PSet * c) 00558 : PAbstractSet(dummy, c) 00559 { reference->deleteObjects = c->reference->deleteObjects; } 00560 }; 00561 00562 00574 #define PSET(cls, T) typedef PSet<T> cls 00575 00576 00588 #define PDECLARE_SET(cls, T, initDelObj) \ 00589 PSET(cls##_PTemplate, T); \ 00590 PDECLARE_CLASS(cls, cls##_PTemplate) \ 00591 protected: \ 00592 cls(int dummy, const cls * c) \ 00593 : cls##_PTemplate(dummy, c) { } \ 00594 public: \ 00595 cls(PBoolean initialDeleteObjects = initDelObj) \ 00596 : cls##_PTemplate(initialDeleteObjects) { } \ 00597 virtual PObject * Clone() const \ 00598 { return PNEW cls(0, this); } \ 00599 00600 00601 00602 PSET(POrdinalSet, POrdinalKey); 00603 00604 00606 00609 class PAbstractDictionary : public PHashTable 00610 { 00611 PCLASSINFO(PAbstractDictionary, PHashTable); 00612 public: 00620 PINLINE PAbstractDictionary(); 00622 00631 virtual void PrintOn( 00632 ostream &strm 00633 ) const; 00635 00646 virtual PINDEX Insert( 00647 const PObject & key, 00648 PObject * obj 00649 ); 00650 00657 virtual PINDEX InsertAt( 00658 PINDEX index, 00659 PObject * obj 00660 ); 00661 00671 virtual PObject * RemoveAt( 00672 PINDEX index 00673 ); 00674 00683 virtual PBoolean SetAt( 00684 PINDEX index, 00685 PObject * val 00686 ); 00687 00694 virtual PObject * GetAt( 00695 PINDEX index 00696 ) const; 00697 00709 virtual PINDEX GetObjectsIndex( 00710 const PObject * obj 00711 ) const; 00712 00721 virtual PINDEX GetValuesIndex( 00722 const PObject & obj 00723 ) const; 00725 00726 00737 virtual PBoolean SetDataAt( 00738 PINDEX index, 00739 PObject * obj 00740 ); 00741 00753 virtual PBoolean AbstractSetAt( 00754 const PObject & key, 00755 PObject * obj 00756 ); 00757 00767 virtual PObject & GetRefAt( 00768 const PObject & key 00769 ) const; 00770 00777 virtual PObject * AbstractGetAt( 00778 const PObject & key 00779 ) const; 00780 00783 virtual void AbstractGetKeys( 00784 PArrayObjects & keys 00785 ) const; 00787 00788 protected: 00789 PINLINE PAbstractDictionary(int dummy, const PAbstractDictionary * c); 00790 00791 private: 00797 virtual PINDEX Append( 00798 PObject * obj 00799 ); 00800 00811 virtual PBoolean Remove( 00812 const PObject * obj 00813 ); 00814 00815 }; 00816 00817 00825 template <class K, class D> class PDictionary : public PAbstractDictionary 00826 { 00827 PCLASSINFO(PDictionary, PAbstractDictionary); 00828 00829 public: 00838 PDictionary() 00839 : PAbstractDictionary() { } 00841 00848 virtual PObject * Clone() const 00849 { return PNEW PDictionary(0, this); } 00851 00864 D & operator[]( 00865 const K & key 00866 ) const 00867 { return (D &)GetRefAt(key); } 00868 00877 PBoolean Contains( 00878 const K & key 00879 ) const { return AbstractContains(key); } 00880 00892 virtual D * RemoveAt( 00893 const K & key 00894 ) { 00895 D * obj = GetAt(key); AbstractSetAt(key, NULL); 00896 return reference->deleteObjects ? (obj ? (D *)-1 : NULL) : obj; 00897 } 00898 00910 virtual PBoolean SetAt( 00911 const K & key, // Key for position in dictionary to add object. 00912 D * obj // New object to put into the dictionary. 00913 ) { return AbstractSetAt(key, obj); } 00914 00921 virtual D * GetAt( 00922 const K & key // Key for position in dictionary to get object. 00923 ) const { return (D *)AbstractGetAt(key); } 00924 00936 const K & GetKeyAt( 00937 PINDEX index 00938 ) const 00939 { return (const K &)AbstractGetKeyAt(index); } 00940 00952 D & GetDataAt( 00953 PINDEX index 00954 ) const 00955 { return (D &)AbstractGetDataAt(index); } 00956 00959 PArray<K> GetKeys() const 00960 { 00961 PArray<K> keys; 00962 AbstractGetKeys(keys); 00963 return keys; 00964 } 00966 00967 typedef std::pair<K, D *> value_type; 00968 00969 protected: 00970 PDictionary(int dummy, const PDictionary * c) 00971 : PAbstractDictionary(dummy, c) { } 00972 }; 00973 00974 00987 #define PDICTIONARY(cls, K, D) typedef PDictionary<K, D> cls 00988 00989 01002 #define PDECLARE_DICTIONARY(cls, K, D) \ 01003 PDICTIONARY(cls##_PTemplate, K, D); \ 01004 PDECLARE_CLASS(cls, cls##_PTemplate) \ 01005 protected: \ 01006 cls(int dummy, const cls * c) \ 01007 : cls##_PTemplate(dummy, c) { } \ 01008 public: \ 01009 cls() \ 01010 : cls##_PTemplate() { } \ 01011 virtual PObject * Clone() const \ 01012 { return PNEW cls(0, this); } \ 01013 01014 01022 template <class K> class POrdinalDictionary : public PAbstractDictionary 01023 { 01024 PCLASSINFO(POrdinalDictionary, PAbstractDictionary); 01025 01026 public: 01035 POrdinalDictionary() 01036 : PAbstractDictionary() { } 01038 01045 virtual PObject * Clone() const 01046 { return PNEW POrdinalDictionary(0, this); } 01048 01061 PINDEX operator[]( 01062 const K & key // Key to look for in the dictionary. 01063 ) const 01064 { return (POrdinalKey &)GetRefAt(key); } 01065 01074 PBoolean Contains( 01075 const K & key 01076 ) const { return AbstractContains(key); } 01077 01078 virtual POrdinalKey * GetAt( 01079 const K & key 01080 ) const { return (POrdinalKey *)AbstractGetAt(key); } 01081 /* Get the object at the specified key position. If the key was not in the 01082 collection then NULL is returned. 01083 01084 @return 01085 pointer to object at the specified key. 01086 */ 01087 01096 virtual PBoolean SetDataAt( 01097 PINDEX index, 01098 PINDEX ordinal 01099 ) { return PAbstractDictionary::SetDataAt(index, PNEW POrdinalKey(ordinal)); } 01100 01112 virtual PBoolean SetAt( 01113 const K & key, 01114 PINDEX ordinal 01115 ) { return AbstractSetAt(key, PNEW POrdinalKey(ordinal)); } 01116 01125 virtual PINDEX RemoveAt( 01126 const K & key 01127 ) { PINDEX ord = *GetAt(key); AbstractSetAt(key, NULL); return ord; } 01128 01140 const K & GetKeyAt( 01141 PINDEX index 01142 ) const 01143 { return (const K &)AbstractGetKeyAt(index); } 01144 01156 PINDEX GetDataAt( 01157 PINDEX index 01158 ) const 01159 { return (POrdinalKey &)AbstractGetDataAt(index); } 01161 01162 protected: 01163 POrdinalDictionary(int dummy, const POrdinalDictionary * c) 01164 : PAbstractDictionary(dummy, c) { } 01165 }; 01166 01167 01180 #define PORDINAL_DICTIONARY(cls, K) typedef POrdinalDictionary<K> cls 01181 01182 01197 #define PDECLARE_ORDINAL_DICTIONARY(cls, K) \ 01198 PORDINAL_DICTIONARY(cls##_PTemplate, K); \ 01199 PDECLARE_CLASS(cls, POrdinalDictionary<K>) \ 01200 protected: \ 01201 cls(int dummy, const cls * c) \ 01202 : cls##_PTemplate(dummy, c) { } \ 01203 public: \ 01204 cls() \ 01205 : cls##_PTemplate() { } \ 01206 virtual PObject * Clone() const \ 01207 { return PNEW cls(0, this); } \ 01208 01209 01210 #endif // PTLIB_DICT_H 01211 01212 // End Of File ///////////////////////////////////////////////////////////////