PTLib  Version 2.10.10
dict.h
Go to the documentation of this file.
1 /*
2  * dict.h
3  *
4  * Dictionary (hash table) Container classes.
5  *
6  * Portable Tools Library
7  *
8  * Copyright (c) 1993-1998 Equivalence Pty. Ltd.
9  *
10  * The contents of this file are subject to the Mozilla Public License
11  * Version 1.0 (the "License"); you may not use this file except in
12  * compliance with the License. You may obtain a copy of the License at
13  * http://www.mozilla.org/MPL/
14  *
15  * Software distributed under the License is distributed on an "AS IS"
16  * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
17  * the License for the specific language governing rights and limitations
18  * under the License.
19  *
20  * The Original Code is Portable Windows Library.
21  *
22  * The Initial Developer of the Original Code is Equivalence Pty. Ltd.
23  *
24  * Portions are Copyright (C) 1993 Free Software Foundation, Inc.
25  * All Rights Reserved.
26  *
27  * Contributor(s): ______________________________________.
28  *
29  * $Revision: 28056 $
30  * $Author: rjongbloed $
31  * $Date: 2012-07-18 03:21:10 -0500 (Wed, 18 Jul 2012) $
32  */
33 
34 
35 #ifndef PTLIB_DICT_H
36 #define PTLIB_DICT_H
37 
38 #ifdef P_USE_PRAGMA
39 #pragma interface
40 #endif
41 
42 #include <ptlib/array.h>
43 
45 // PDictionary classes
46 
50 class POrdinalKey : public PObject
51 {
52  PCLASSINFO(POrdinalKey, PObject);
53 
54  public:
60  PINDEX newKey = 0
61  );
62 
65  PINLINE POrdinalKey & operator=(PINDEX);
67 
70  virtual PObject * Clone() const;
72 
73  /* Get the relative rank of the ordinal index. This is a simpel comparison
74  of the objects PINDEX values.
75 
76  @return
77  comparison of the two objects, <code>EqualTo</code> for same,
78  <code>LessThan</code> for \p obj logically less than the
79  object and <code>GreaterThan</code> for \p obj logically
80  greater than the object.
81  */
82  virtual Comparison Compare(const PObject & obj) const;
83 
90  virtual PINDEX HashFunction() const;
91 
98  virtual void PrintOn(ostream & strm) const;
100 
105  PINLINE operator PINDEX() const;
106 
109  PINLINE PINDEX operator++();
110 
113  PINLINE PINDEX operator++(int);
114 
117  PINLINE PINDEX operator--();
118 
121  PINLINE PINDEX operator--(int);
122 
125  PINLINE POrdinalKey & operator+=(PINDEX);
126 
129  PINLINE POrdinalKey & operator-=(PINDEX );
131 
132  private:
133  PINDEX theKey;
134 };
135 
136 
138 
139 // Member variables
141 {
146 
148 };
149 
150 PDECLARE_BASEARRAY(PHashTableInfo, PHashTableElement *)
151 #ifdef DOC_PLUS_PLUS
152 {
153 #endif
154  public:
155  virtual ~PHashTableInfo() { Destruct(); }
156  virtual void DestroyContents();
157 
158  PINDEX AppendElement(PObject * key, PObject * data);
159  PObject * RemoveElement(const PObject & key);
160  PBoolean SetLastElementAt(PINDEX index, PHashTableElement * & lastElement);
161  PHashTableElement * GetElementAt(const PObject & key);
162  PINDEX GetElementsIndex(const PObject*obj,PBoolean byVal,PBoolean keys) const;
163 
165 
167  friend class PHashTable;
168  friend class PAbstractSet;
169 };
170 
171 
182 class PHashTable : public PCollection
183 {
184  PCONTAINERINFO(PHashTable, PCollection);
185 
186  public:
189  PHashTable();
192 
204  virtual Comparison Compare(
205  const PObject & obj
206  ) const;
208 
209 
219  virtual PBoolean SetSize(
220  PINDEX newSize
221  );
223 
224 
236  const PObject & key
237  ) const;
238 
253  virtual const PObject & AbstractGetKeyAt(
254  PINDEX index
255  ) const;
256 
271  virtual PObject & AbstractGetDataAt(
272  PINDEX index
273  ) const;
275 
276  // The type below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it
278  typedef PHashTableInfo Table;
279  PHashTableInfo * hashTable;
280 };
281 
282 
284 
287 class PAbstractSet : public PHashTable
288 {
289  PCONTAINERINFO(PAbstractSet, PHashTable);
290  public:
300 
311  virtual PINDEX Append(
312  PObject * obj
313  );
314 
327  virtual PINDEX Insert(
328  const PObject & before,
329  PObject * obj
330  );
331 
344  virtual PINDEX InsertAt(
345  PINDEX index,
346  PObject * obj
347  );
348 
359  virtual PBoolean Remove(
360  const PObject * obj
361  );
362 
369  virtual PObject * RemoveAt(
370  PINDEX index
371  );
372 
378  virtual PObject * GetAt(
379  PINDEX index
380  ) const;
381 
394  virtual PBoolean SetAt(
395  PINDEX index,
396  PObject * val
397  );
398 
410  virtual PINDEX GetObjectsIndex(
411  const PObject * obj
412  ) const;
413 
422  virtual PINDEX GetValuesIndex(
423  const PObject & obj
424  ) const;
425 
429  bool Union(
430  const PAbstractSet & set
431  );
432 
436  static bool Intersection(
437  const PAbstractSet & set1,
438  const PAbstractSet & set2,
439  PAbstractSet * intersection = NULL
440  );
442 };
443 
444 
455 template <class T> class PSet : public PAbstractSet
456 {
457  PCLASSINFO(PSet, PAbstractSet);
458 
459  public:
469  inline PSet(PBoolean initialDeleteObjects = false)
470  : PAbstractSet() { AllowDeleteObjects(initialDeleteObjects); }
472 
478  virtual PObject * Clone() const
479  { return PNEW PSet(0, this); }
481 
493  void Include(
494  const T * obj // New object to include in the set.
495  ) { Append((PObject *)obj); }
496 
505  const T & obj // New object to include in the set.
506  ) { Append(obj.Clone()); return *this; }
507 
515  void Exclude(
516  const T * obj // New object to exclude in the set.
517  ) { Remove(obj); }
518 
527  const T & obj // New object to exclude in the set.
528  ) { RemoveAt(GetValuesIndex(obj)); return *this; }
529 
539  const T & key
540  ) const { return AbstractContains(key); }
541 
551  const T & key
552  ) const { return AbstractContains(key); }
553 
565  virtual const T & GetKeyAt(
566  PINDEX index
567  ) const
568  { return (const T &)AbstractGetKeyAt(index); }
570 
571 
572  protected:
573  PSet(int dummy, const PSet * c)
574  : PAbstractSet(dummy, c)
576 };
577 
578 
590 #define PSET(cls, T) typedef PSet<T> cls
591 
592 
604 #define PDECLARE_SET(cls, T, initDelObj) \
605  class cls : public PSet<T> { \
606  typedef PSet<T> BaseClass; PCLASSINFO(cls, BaseClass) \
607  protected: \
608  cls(int dummy, const cls * c) \
609  : BaseClass(dummy, c) { } \
610  public: \
611  cls(PBoolean initialDeleteObjects = initDelObj) \
612  : BaseClass(initialDeleteObjects) { } \
613  virtual PObject * Clone() const \
614  { return PNEW cls(0, this); } \
615 
616 
617 
618 PDECLARE_SET(POrdinalSet, POrdinalKey, true)
619 };
620 
621 
623 
627 {
628  PCLASSINFO(PAbstractDictionary, PHashTable);
629  public:
639 
648  virtual void PrintOn(
649  ostream &strm
650  ) const;
652 
663  virtual PINDEX Insert(
664  const PObject & key,
665  PObject * obj
666  );
667 
674  virtual PINDEX InsertAt(
675  PINDEX index,
676  PObject * obj
677  );
678 
688  virtual PObject * RemoveAt(
689  PINDEX index
690  );
691 
700  virtual PBoolean SetAt(
701  PINDEX index,
702  PObject * val
703  );
704 
711  virtual PObject * GetAt(
712  PINDEX index
713  ) const;
714 
726  virtual PINDEX GetObjectsIndex(
727  const PObject * obj
728  ) const;
729 
738  virtual PINDEX GetValuesIndex(
739  const PObject & obj
740  ) const;
742 
743 
754  virtual PBoolean SetDataAt(
755  PINDEX index,
756  PObject * obj
757  );
758 
770  virtual PBoolean AbstractSetAt(
771  const PObject & key,
772  PObject * obj
773  );
774 
784  virtual PObject & GetRefAt(
785  const PObject & key
786  ) const;
787 
794  virtual PObject * AbstractGetAt(
795  const PObject & key
796  ) const;
797 
800  virtual void AbstractGetKeys(
801  PArrayObjects & keys
802  ) const;
804 
805  protected:
806  PINLINE PAbstractDictionary(int dummy, const PAbstractDictionary * c);
807 
808  private:
814  virtual PINDEX Append(
815  PObject * obj
816  );
817 
828  virtual PBoolean Remove(
829  const PObject * obj
830  );
831 
832 };
833 
834 
842 template <class K, class D> class PDictionary : public PAbstractDictionary
843 {
844  PCLASSINFO(PDictionary, PAbstractDictionary);
845 
846  public:
856  : PAbstractDictionary() { }
858 
865  virtual PObject * Clone() const
866  { return PNEW PDictionary(0, this); }
868 
882  const K & key
883  ) const
884  { return (D &)GetRefAt(key); }
885 
895  const K & key
896  ) const { return AbstractContains(key); }
897 
909  virtual D * RemoveAt(
910  const K & key
911  ) {
912  D * obj = GetAt(key); AbstractSetAt(key, NULL);
913  return reference->deleteObjects ? (obj ? (D *)-1 : NULL) : obj;
914  }
915 
927  virtual PBoolean SetAt(
928  const K & key, // Key for position in dictionary to add object.
929  D * obj // New object to put into the dictionary.
930  ) { return AbstractSetAt(key, obj); }
931 
938  virtual D * GetAt(
939  const K & key // Key for position in dictionary to get object.
940  ) const { return (D *)AbstractGetAt(key); }
941 
953  const K & GetKeyAt(
954  PINDEX index
955  ) const
956  { return (const K &)AbstractGetKeyAt(index); }
957 
970  PINDEX index
971  ) const
972  { return (D &)AbstractGetDataAt(index); }
973 
977  {
978  PArray<K> keys;
979  AbstractGetKeys(keys);
980  return keys;
981  }
983 
984  typedef std::pair<K, D *> value_type;
985 
986  protected:
987  PDictionary(int dummy, const PDictionary * c)
988  : PAbstractDictionary(dummy, c) { }
989 };
990 
991 
1004 #define PDICTIONARY(cls, K, D) typedef PDictionary<K, D> cls
1005 
1006 
1019 #define PDECLARE_DICTIONARY(cls, K, D) \
1020  PDICTIONARY(cls##_PTemplate, K, D); \
1021  PDECLARE_CLASS(cls, cls##_PTemplate) \
1022  protected: \
1023  cls(int dummy, const cls * c) \
1024  : cls##_PTemplate(dummy, c) { } \
1025  public: \
1026  cls() \
1027  : cls##_PTemplate() { } \
1028  virtual PObject * Clone() const \
1029  { return PNEW cls(0, this); } \
1030 
1031 
1039 template <class K> class POrdinalDictionary : public PAbstractDictionary
1040 {
1042 
1043  public:
1053  : PAbstractDictionary() { }
1055 
1062  virtual PObject * Clone() const
1063  { return PNEW POrdinalDictionary(0, this); }
1065 
1078  PINDEX operator[](
1079  const K & key // Key to look for in the dictionary.
1080  ) const
1081  { return (POrdinalKey &)GetRefAt(key); }
1082 
1092  const K & key
1093  ) const { return AbstractContains(key); }
1094 
1095  virtual POrdinalKey * GetAt(
1096  const K & key
1097  ) const { return (POrdinalKey *)AbstractGetAt(key); }
1098  /* Get the object at the specified key position. If the key was not in the
1099  collection then NULL is returned.
1100 
1101  @return
1102  pointer to object at the specified key.
1103  */
1104 
1114  PINDEX index,
1115  PINDEX ordinal
1116  ) { return PAbstractDictionary::SetDataAt(index, PNEW POrdinalKey(ordinal)); }
1117 
1129  virtual PBoolean SetAt(
1130  const K & key,
1131  PINDEX ordinal
1132  ) { return AbstractSetAt(key, PNEW POrdinalKey(ordinal)); }
1133 
1142  virtual PINDEX RemoveAt(
1143  const K & key
1144  ) { PINDEX ord = *GetAt(key); AbstractSetAt(key, NULL); return ord; }
1145 
1157  const K & GetKeyAt(
1158  PINDEX index
1159  ) const
1160  { return (const K &)AbstractGetKeyAt(index); }
1161 
1173  PINDEX GetDataAt(
1174  PINDEX index
1175  ) const
1176  { return (POrdinalKey &)AbstractGetDataAt(index); }
1178 
1179  protected:
1181  : PAbstractDictionary(dummy, c) { }
1182 };
1183 
1184 
1197 #define PORDINAL_DICTIONARY(cls, K) typedef POrdinalDictionary<K> cls
1198 
1199 
1214 #define PDECLARE_ORDINAL_DICTIONARY(cls, K) \
1215  PORDINAL_DICTIONARY(cls##_PTemplate, K); \
1216  PDECLARE_CLASS(cls, POrdinalDictionary<K>) \
1217  protected: \
1218  cls(int dummy, const cls * c) \
1219  : cls##_PTemplate(dummy, c) { } \
1220  public: \
1221  cls() \
1222  : cls##_PTemplate() { } \
1223  virtual PObject * Clone() const \
1224  { return PNEW cls(0, this); } \
1225 
1226 
1227 #endif // PTLIB_DICT_H
1228 
1229 // End Of File ///////////////////////////////////////////////////////////////
PINLINE PBoolean AbstractContains(const PObject &key) const
Determine if the value of the object is contained in the hash table.
virtual const T & GetKeyAt(PINDEX index) const
Get the key in the set at the ordinal index position.
Definition: dict.h:565
virtual POrdinalKey * GetAt(const K &key) const
Definition: dict.h:1095
virtual PINDEX GetObjectsIndex(const PObject *obj) const
Search the collection for the specific instance of the object.
void Include(const T *obj)
Include the specified object into the set.
Definition: dict.h:493
PHashTable()
Create a new, empty, hash table.
virtual PBoolean SetAt(PINDEX index, PObject *val)
Set the object at the specified index to the new value.
bool Union(const PAbstractSet &set)
Calculate union of sets.
const K & GetKeyAt(PINDEX index) const
Get the key in the dictionary at the ordinal index position.
Definition: dict.h:1157
PINDEX GetElementsIndex(const PObject *obj, PBoolean byVal, PBoolean keys) const
virtual void PrintOn(ostream &strm) const
Output the contents of the object to the stream.
An array of objects.
Definition: array.h:813
D & operator[](const K &key) const
Get the object contained in the dictionary at the key position.
Definition: dict.h:881
virtual PINDEX InsertAt(PINDEX index, PObject *obj)
Add a new object to the collection.
virtual PBoolean SetAt(const K &key, PINDEX ordinal)
Add a new object to the collection.
Definition: dict.h:1129
virtual PINDEX RemoveAt(const K &key)
Remove an object at the specified key.
Definition: dict.h:1142
PObject * data
Definition: dict.h:143
PSet(int dummy, const PSet *c)
Definition: dict.h:573
PBoolean SetLastElementAt(PINDEX index, PHashTableElement *&lastElement)
virtual Comparison Compare(const PObject &obj) const
Compare the two objects and return their relative rank.
virtual PBoolean SetAt(PINDEX index, PObject *val)
Add a new object to the collection.
PBoolean Contains(const K &key) const
Determine if the value of the object is contained in the hash table.
Definition: dict.h:1091
PINLINE void AllowDeleteObjects(PBoolean yes=true)
Allow or disallow the deletion of the objects contained in the collection.
virtual PINDEX GetValuesIndex(const PObject &obj) const
Search the collection for the specified value of the object.
POrdinalDictionary()
Create a new, empty, dictionary.
Definition: dict.h:1052
virtual PObject * Clone() const
Make a complete duplicate of the dictionary.
Definition: dict.h:1062
PINLINE POrdinalKey(PINDEX newKey=0)
Create a new key for ordinal index values.
This template class maps the PAbstractDictionary to a specific key and data types.
Definition: dict.h:842
virtual PINDEX HashFunction() const
This function calculates a hash table index value for the implementation of PSet and PDictionary clas...
PHashTableElement * prev
Definition: dict.h:145
#define PINLINE
Definition: object.h:127
PINDEX AppendElement(PObject *key, PObject *data)
Comparison
Result of the comparison operation performed by the Compare() function.
Definition: object.h:1184
virtual PINDEX GetObjectsIndex(const PObject *obj) const
Search the collection for the specific instance of the object.
virtual PINDEX Append(PObject *obj)
Add a new object to the collection.
PINLINE PAbstractDictionary()
Create a new, empty, dictionary.
An abstract dictionary container.
Definition: dict.h:626
PINLINE PINDEX operator--()
Operator to pre-decrement the ordinal.
PINLINE POrdinalKey & operator-=(PINDEX)
Operator to subtract from the ordinal.
PHashTableElement Element
Definition: dict.h:166
virtual PObject * GetAt(PINDEX index) const
This function is the same as PHashTable::AbstractGetKeyAt().
PINDEX operator[](const K &key) const
Get the object contained in the dictionary at the key position.
Definition: dict.h:1078
virtual void AbstractGetKeys(PArrayObjects &keys) const
Get an array containing all the keys for the dictionary.
virtual PINDEX GetValuesIndex(const PObject &obj) const
Search the collection for the specified value of the object.
PHashTableElement Element
Definition: dict.h:277
virtual Comparison Compare(const PObject &obj) const
Get the relative rank of the two hash tables.
Definition: dict.h:140
PHashTableInfo Table
Definition: dict.h:278
PBoolean Contains(const T &key) const
Determine if the value of the object is contained in the set.
Definition: dict.h:538
BOOL PBoolean
Definition: object.h:102
virtual PBoolean AbstractSetAt(const PObject &key, PObject *obj)
Add a new object to the collection.
PObject * key
Definition: dict.h:142
virtual PBoolean SetSize(PINDEX newSize)
This function is meaningless for hash table.
POrdinalDictionary(int dummy, const POrdinalDictionary *c)
Definition: dict.h:1180
PBoolean operator[](const T &key) const
Determine if the value of the object is contained in the set.
Definition: dict.h:550
virtual PObject * Clone() const
Make a complete duplicate of the set.
Definition: dict.h:478
PDictionary(int dummy, const PDictionary *c)
Definition: dict.h:987
virtual void PrintOn(ostream &strm) const
Output the ordinal index to the specified stream.
Abstract set of PObjects.
Definition: dict.h:287
virtual PObject * AbstractGetAt(const PObject &key) const
Get the object at the specified key position.
virtual PBoolean SetDataAt(PINDEX index, PObject *obj)
Set the data at the specified ordinal index position in the dictionary.
D & GetDataAt(PINDEX index) const
Get the data in the dictionary at the ordinal index position.
Definition: dict.h:969
PINLINE PINDEX operator++()
Operator to pre-increment the ordinal.
PBoolean Contains(const K &key) const
Determine if the value of the object is contained in the hash table.
Definition: dict.h:894
#define PDECLARE_BASEARRAY(cls, T)
Begin a declaration of an array of base types.
Definition: array.h:474
This template class maps the PAbstractSet to a specific object type.
Definition: dict.h:455
#define PDECLARE_SET(cls, T, initDelObj)
Begin declaration of a set class.
Definition: dict.h:604
virtual D * GetAt(const K &key) const
Get the object at the specified key position.
Definition: dict.h:938
virtual PINDEX Insert(const PObject &before, PObject *obj)
Add a new object to the collection.
The hash table class is the basis for implementing the PSet and PDictionary classes.
Definition: dict.h:182
bool deleteObjects
Definition: contain.h:72
PSet & operator+=(const T &obj)
Include the specified objects value into the set.
Definition: dict.h:504
virtual PINDEX Insert(const PObject &key, PObject *obj)
Insert a new object into the dictionary.
virtual PObject * RemoveAt(PINDEX index)
Remove an object at the specified index.
static bool Intersection(const PAbstractSet &set1, const PAbstractSet &set2, PAbstractSet *intersection=NULL)
Calculate intersection of sets.
virtual PINDEX InsertAt(PINDEX index, PObject *obj)
Insert a new object at the specified index.
std::pair< K, D * > value_type
Definition: dict.h:984
virtual PObject * GetAt(PINDEX index) const
Get the object at the specified index position.
void Exclude(const T *obj)
Remove the object from the set.
Definition: dict.h:515
PSet & operator-=(const T &obj)
Remove the objects value from the set.
Definition: dict.h:526
virtual PObject * Clone() const
Create a duplicate of the POrdinalKey.
PSet(PBoolean initialDeleteObjects=false)
Create a new, empty, dictionary.
Definition: dict.h:469
PBoolean deleteKeys
Definition: dict.h:164
virtual PObject & GetRefAt(const PObject &key) const
Get the object at the specified key position.
PHashTableElement * GetElementAt(const PObject &key)
virtual const PObject & AbstractGetKeyAt(PINDEX index) const
Get the key in the hash table at the ordinal index position.
PINLINE POrdinalKey & operator+=(PINDEX)
Operator to add the ordinal.
virtual PBoolean SetAt(const K &key, D *obj)
Add a new object to the collection.
Definition: dict.h:927
This template class maps the PArrayObjects to a specific object type.
Definition: array.h:1024
const K & GetKeyAt(PINDEX index) const
Get the key in the dictionary at the ordinal index position.
Definition: dict.h:953
PINLINE POrdinalKey & operator=(PINDEX)
Operator to assign the ordinal.
virtual PObject * RemoveAt(PINDEX index)
Remove an object at the specified index.
virtual PBoolean SetDataAt(PINDEX index, PINDEX ordinal)
Set the data at the specified ordinal index position in the dictionary.
Definition: dict.h:1113
virtual D * RemoveAt(const K &key)
Remove an object at the specified key.
Definition: dict.h:909
virtual PBoolean Remove(const PObject *obj)
Remove the object from the collection.
PINLINE PAbstractSet()
Create a new, empty, set.
PINDEX GetDataAt(PINDEX index) const
Get the data in the dictionary at the ordinal index position.
Definition: dict.h:1173
PContainerReference * reference
Definition: contain.h:291
virtual PObject & AbstractGetDataAt(PINDEX index) const
Get the data in the hash table at the ordinal index position.
PObject * RemoveElement(const PObject &key)
This template class maps the PAbstractDictionary to a specific key type and a POrdinalKey data type...
Definition: dict.h:1039
Ultimate parent class for all objects in the class library.
Definition: object.h:1118
A collection is a container that collects together descendents of the PObject class.
Definition: contain.h:395
virtual PObject * Clone() const
Make a complete duplicate of the dictionary.
Definition: dict.h:865
PDictionary()
Create a new, empty, dictionary.
Definition: dict.h:855
PHashTableElement * next
Definition: dict.h:144
PArray< K > GetKeys() const
Get an array containing all the keys for the dictionary.
Definition: dict.h:976
PHashTableInfo * hashTable
Definition: dict.h:279
#define PNEW
Macro for overriding system default new operator.
Definition: object.h:890
This class is used when an ordinal index value is the key for PSet and PDictionary classes...
Definition: dict.h:50