PTLib  Version 2.10.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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: 25554 $
30  * $Author: rjongbloed $
31  * $Date: 2011-04-13 03:34:50 -0500 (Wed, 13 Apr 2011) $
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 
71  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 
164  PBoolean deleteKeys;
165 
166  typedef PHashTableElement Element;
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 
190  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;
426 };
427 
428 
439 template <class T> class PSet : public PAbstractSet
440 {
441  PCLASSINFO(PSet, PAbstractSet);
442 
443  public:
453  inline PSet(PBoolean initialDeleteObjects = false)
454  : PAbstractSet() { AllowDeleteObjects(initialDeleteObjects); }
456 
462  virtual PObject * Clone() const
463  { return PNEW PSet(0, this); }
465 
477  void Include(
478  const T * obj // New object to include in the set.
479  ) { Append((PObject *)obj); }
480 
489  const T & obj // New object to include in the set.
490  ) { Append(obj.Clone()); return *this; }
491 
499  void Exclude(
500  const T * obj // New object to exclude in the set.
501  ) { Remove(obj); }
502 
511  const T & obj // New object to exclude in the set.
512  ) { RemoveAt(GetValuesIndex(obj)); return *this; }
513 
523  const T & key
524  ) const { return AbstractContains(key); }
525 
535  const T & key
536  ) const { return AbstractContains(key); }
537 
549  virtual const T & GetKeyAt(
550  PINDEX index
551  ) const
552  { return (const T &)AbstractGetKeyAt(index); }
554 
555 
556  protected:
557  PSet(int dummy, const PSet * c)
558  : PAbstractSet(dummy, c)
560 };
561 
562 
574 #define PSET(cls, T) typedef PSet<T> cls
575 
576 
588 #define PDECLARE_SET(cls, T, initDelObj) \
589  PSET(cls##_PTemplate, T); \
590  PDECLARE_CLASS(cls, cls##_PTemplate) \
591  protected: \
592  cls(int dummy, const cls * c) \
593  : cls##_PTemplate(dummy, c) { } \
594  public: \
595  cls(PBoolean initialDeleteObjects = initDelObj) \
596  : cls##_PTemplate(initialDeleteObjects) { } \
597  virtual PObject * Clone() const \
598  { return PNEW cls(0, this); } \
599 
600 
601 
602 PSET(POrdinalSet, POrdinalKey);
603 
604 
606 
610 {
611  PCLASSINFO(PAbstractDictionary, PHashTable);
612  public:
622 
631  virtual void PrintOn(
632  ostream &strm
633  ) const;
635 
646  virtual PINDEX Insert(
647  const PObject & key,
648  PObject * obj
649  );
650 
657  virtual PINDEX InsertAt(
658  PINDEX index,
659  PObject * obj
660  );
661 
671  virtual PObject * RemoveAt(
672  PINDEX index
673  );
674 
683  virtual PBoolean SetAt(
684  PINDEX index,
685  PObject * val
686  );
687 
694  virtual PObject * GetAt(
695  PINDEX index
696  ) const;
697 
709  virtual PINDEX GetObjectsIndex(
710  const PObject * obj
711  ) const;
712 
721  virtual PINDEX GetValuesIndex(
722  const PObject & obj
723  ) const;
725 
726 
737  virtual PBoolean SetDataAt(
738  PINDEX index,
739  PObject * obj
740  );
741 
753  virtual PBoolean AbstractSetAt(
754  const PObject & key,
755  PObject * obj
756  );
757 
767  virtual PObject & GetRefAt(
768  const PObject & key
769  ) const;
770 
777  virtual PObject * AbstractGetAt(
778  const PObject & key
779  ) const;
780 
783  virtual void AbstractGetKeys(
784  PArrayObjects & keys
785  ) const;
787 
788  protected:
789  PINLINE PAbstractDictionary(int dummy, const PAbstractDictionary * c);
790 
791  private:
797  virtual PINDEX Append(
798  PObject * obj
799  );
800 
811  virtual PBoolean Remove(
812  const PObject * obj
813  );
814 
815 };
816 
817 
825 template <class K, class D> class PDictionary : public PAbstractDictionary
826 {
827  PCLASSINFO(PDictionary, PAbstractDictionary);
828 
829  public:
839  : PAbstractDictionary() { }
841 
848  virtual PObject * Clone() const
849  { return PNEW PDictionary(0, this); }
851 
865  const K & key
866  ) const
867  { return (D &)GetRefAt(key); }
868 
878  const K & key
879  ) const { return AbstractContains(key); }
880 
892  virtual D * RemoveAt(
893  const K & key
894  ) {
895  D * obj = GetAt(key); AbstractSetAt(key, NULL);
896  return reference->deleteObjects ? (obj ? (D *)-1 : NULL) : obj;
897  }
898 
910  virtual PBoolean SetAt(
911  const K & key, // Key for position in dictionary to add object.
912  D * obj // New object to put into the dictionary.
913  ) { return AbstractSetAt(key, obj); }
914 
921  virtual D * GetAt(
922  const K & key // Key for position in dictionary to get object.
923  ) const { return (D *)AbstractGetAt(key); }
924 
936  const K & GetKeyAt(
937  PINDEX index
938  ) const
939  { return (const K &)AbstractGetKeyAt(index); }
940 
953  PINDEX index
954  ) const
955  { return (D &)AbstractGetDataAt(index); }
956 
960  {
961  PArray<K> keys;
962  AbstractGetKeys(keys);
963  return keys;
964  }
966 
967  typedef std::pair<K, D *> value_type;
968 
969  protected:
970  PDictionary(int dummy, const PDictionary * c)
971  : PAbstractDictionary(dummy, c) { }
972 };
973 
974 
987 #define PDICTIONARY(cls, K, D) typedef PDictionary<K, D> cls
988 
989 
1002 #define PDECLARE_DICTIONARY(cls, K, D) \
1003  PDICTIONARY(cls##_PTemplate, K, D); \
1004  PDECLARE_CLASS(cls, cls##_PTemplate) \
1005  protected: \
1006  cls(int dummy, const cls * c) \
1007  : cls##_PTemplate(dummy, c) { } \
1008  public: \
1009  cls() \
1010  : cls##_PTemplate() { } \
1011  virtual PObject * Clone() const \
1012  { return PNEW cls(0, this); } \
1013 
1014 
1022 template <class K> class POrdinalDictionary : public PAbstractDictionary
1023 {
1025 
1026  public:
1036  : PAbstractDictionary() { }
1038 
1045  virtual PObject * Clone() const
1046  { return PNEW POrdinalDictionary(0, this); }
1048 
1061  PINDEX operator[](
1062  const K & key // Key to look for in the dictionary.
1063  ) const
1064  { return (POrdinalKey &)GetRefAt(key); }
1065 
1075  const K & key
1076  ) const { return AbstractContains(key); }
1077 
1078  virtual POrdinalKey * GetAt(
1079  const K & key
1080  ) const { return (POrdinalKey *)AbstractGetAt(key); }
1081  /* Get the object at the specified key position. If the key was not in the
1082  collection then NULL is returned.
1083 
1084  @return
1085  pointer to object at the specified key.
1086  */
1087 
1097  PINDEX index,
1098  PINDEX ordinal
1099  ) { return PAbstractDictionary::SetDataAt(index, PNEW POrdinalKey(ordinal)); }
1100 
1112  virtual PBoolean SetAt(
1113  const K & key,
1114  PINDEX ordinal
1115  ) { return AbstractSetAt(key, PNEW POrdinalKey(ordinal)); }
1116 
1125  virtual PINDEX RemoveAt(
1126  const K & key
1127  ) { PINDEX ord = *GetAt(key); AbstractSetAt(key, NULL); return ord; }
1128 
1140  const K & GetKeyAt(
1141  PINDEX index
1142  ) const
1143  { return (const K &)AbstractGetKeyAt(index); }
1144 
1156  PINDEX GetDataAt(
1157  PINDEX index
1158  ) const
1159  { return (POrdinalKey &)AbstractGetDataAt(index); }
1161 
1162  protected:
1164  : PAbstractDictionary(dummy, c) { }
1165 };
1166 
1167 
1180 #define PORDINAL_DICTIONARY(cls, K) typedef POrdinalDictionary<K> cls
1181 
1182 
1197 #define PDECLARE_ORDINAL_DICTIONARY(cls, K) \
1198  PORDINAL_DICTIONARY(cls##_PTemplate, K); \
1199  PDECLARE_CLASS(cls, POrdinalDictionary<K>) \
1200  protected: \
1201  cls(int dummy, const cls * c) \
1202  : cls##_PTemplate(dummy, c) { } \
1203  public: \
1204  cls() \
1205  : cls##_PTemplate() { } \
1206  virtual PObject * Clone() const \
1207  { return PNEW cls(0, this); } \
1208 
1209 
1210 #endif // PTLIB_DICT_H
1211 
1212 // End Of File ///////////////////////////////////////////////////////////////