PTLib  Version 2.10.4
dict.h
Go to the documentation of this file.
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 ///////////////////////////////////////////////////////////////
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines