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
44 ///////////////////////////////////////////////////////////////////////////////
45 // PDictionary classes
46
47 /**This class is used when an ordinal index value is the key for <code>PSet</code>
48 and <code>PDictionary</code> classes.
49 */
50 class POrdinalKey : public PObject
51 {
52 PCLASSINFO(POrdinalKey, PObject);
53
54 public:
55 /**@name Construction */
56 //@{
57 /** Create a new key for ordinal index values.
58 */
59 PINLINE POrdinalKey(
60 PINDEX newKey = 0 ///< Ordinal index value to use as a key.
61 );
62
63 /**Operator to assign the ordinal.
64 */
65 PINLINE POrdinalKey & operator=(PINDEX);
66 //@}
67
68 /**@name Overrides from class PObject */
69 //@{
70 /// Create a duplicate of the POrdinalKey.
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
84 /**This function calculates a hash table index value for the implementation
85 of <code>PSet</code> and <code>PDictionary</code> classes.
86
87 @return
88 hash table bucket number.
89 */
90 virtual PINDEX HashFunction() const;
91
92 /**Output the ordinal index to the specified stream. This is identical to
93 outputting the PINDEX, i.e. integer, value.
94
95 @return
96 stream that the index was output to.
97 */
98 virtual void PrintOn(ostream & strm) const;
99 //@}
100
101 /**@name New functions for class */
102 //@{
103 /** Operator so that a POrdinalKey can be used as a PINDEX value.
104 */
105 PINLINE operator PINDEX() const;
106
107 /**Operator to pre-increment the ordinal.
108 */
109 PINLINE PINDEX operator++();
110
111 /**Operator to post-increment the ordinal.
112 */
113 PINLINE PINDEX operator++(int);
114
115 /**Operator to pre-decrement the ordinal.
116 */
117 PINLINE PINDEX operator--();
118
119 /**Operator to post-decrement the ordinal.
120 */
121 PINLINE PINDEX operator--(int);
122
123 /**Operator to add the ordinal.
124 */
125 PINLINE POrdinalKey & operator+=(PINDEX);
126
127 /**Operator to subtract from the ordinal.
128 */
129 PINLINE POrdinalKey & operator-=(PINDEX );
130 //@}
131
132 private:
133 PINDEX theKey;
134 };
135
136
137 //////////////////////////////////////////////////////////////////////////////
138
139 // Member variables
140 struct PHashTableElement
141 {
142 PObject * key;
143 PObject * data;
144 PHashTableElement * next;
145 PHashTableElement * prev;
146
147 PDECLARE_POOL_ALLOCATOR();
148 };
149
PDECLARE_BASEARRAY(PHashTableInfo,PHashTableElement *)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
172 /**The hash table class is the basis for implementing the <code>PSet</code> and
173 <code>PDictionary</code> classes.
174
175 The hash table allows for very fast searches for an object based on a "hash
176 function". This function yields an index into an array which is directly
177 looked up to locate the object. When two key values have the same hash
178 function value, then a linear search of a linked list is made to locate
179 the object. Thus the efficiency of the hash table is highly dependent on the
180 quality of the hash function for the data being used as keys.
181 */
182 class PHashTable : public PCollection
183 {
184 PCONTAINERINFO(PHashTable, PCollection);
185
186 public:
187 /**@name Construction */
188 //@{
189 /// Create a new, empty, hash table.
190 PHashTable();
191 //@}
192
193 /**@name Overrides from class PObject */
194 //@{
195 /**Get the relative rank of the two hash tables. Actally ranking hash
196 tables is really meaningless, so only equality is returned by the
197 comparison. Equality is only achieved if the two instances reference the
198 same hash table.
199
200 @return
201 comparison of the two objects, <code>EqualTo</code> if the same
202 reference and <code>GreaterThan</code> if not.
203 */
204 virtual Comparison Compare(
205 const PObject & obj ///< Other PHashTable to compare against.
206 ) const;
207 //@}
208
209
210 /**@name Overrides from class PContainer */
211 //@{
212 /**This function is meaningless for hash table. The size of the collection
213 is determined by the addition and removal of objects. The size cannot be
214 set in any other way.
215
216 @return
217 Always true.
218 */
219 virtual PBoolean SetSize(
220 PINDEX newSize ///< New size for the hash table, this is ignored.
221 );
222 //@}
223
224
225 /**@name New functions for class */
226 //@{
227 /**Determine if the value of the object is contained in the hash table. The
228 object values are compared, not the pointers. So the objects in the
229 collection must correctly implement the <code>PObject::Compare()</code>
230 function. The hash table is used to locate the entry.
231
232 @return
233 true if the object value is in the set.
234 */
235 PINLINE PBoolean AbstractContains(
236 const PObject & key ///< Key to look for in the set.
237 ) const;
238
239 /**Get the key in the hash table at the ordinal index position.
240
241 The ordinal position in the hash table is determined by the hash values
242 of the keys and the order of insertion.
243
244 The last key/data pair is remembered by the class so that subseqent
245 access is very fast.
246
247 This function is primarily used by the descendent template classes, or
248 macro, with the appropriate type conversion.
249
250 @return
251 reference to key at the index position.
252 */
253 virtual const PObject & AbstractGetKeyAt(
254 PINDEX index ///< Ordinal position in the hash table.
255 ) const;
256
257 /**Get the data in the hash table at the ordinal index position.
258
259 The ordinal position in the hash table is determined by the hash values
260 of the keys and the order of insertion.
261
262 The last key/data pair is remembered by the class so that subseqent
263 access is very fast.
264
265 This function is primarily used by the descendent template classes, or
266 macro, with the appropriate type conversion.
267
268 @return
269 reference to key at the index position.
270 */
271 virtual PObject & AbstractGetDataAt(
272 PINDEX index ///< Ordinal position in the hash table.
273 ) const;
274 //@}
275
276 // The type below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it
277 typedef PHashTableElement Element;
278 typedef PHashTableInfo Table;
279 PHashTableInfo * hashTable;
280 };
281
282
283 //////////////////////////////////////////////////////////////////////////////
284
285 /** Abstract set of PObjects.
286 */
287 class PAbstractSet : public PHashTable
288 {
289 PCONTAINERINFO(PAbstractSet, PHashTable);
290 public:
291 /**@name Construction */
292 //@{
293 /**Create a new, empty, set.
294
295 Note that by default, objects placed into the list will be deleted when
296 removed or when all references to the list are destroyed.
297 */
298 PINLINE PAbstractSet();
299 //@}
300
301 /**@name Overrides from class PCollection */
302 //@{
303 /**Add a new object to the collection. If the objects value is already in
304 the set then the object is \b not included. If the
305 <code>AllowDeleteObjects</code> option is set then the \p obj parameter
306 is also deleted.
307
308 @return
309 hash function value of the newly added object.
310 */
311 virtual PINDEX Append(
312 PObject * obj ///< New object to place into the collection.
313 );
314
315 /**Add a new object to the collection. If the objects value is already in
316 the set then the object is \b not included. If the
317 <code>AllowDeleteObjects</code> option is set then the \p obj parameter is
318 also deleted.
319
320 The object is always placed in the an ordinal position dependent on its
321 hash function. It is not placed at the specified position. The
322 \p before parameter is ignored.
323
324 @return
325 hash function value of the newly added object.
326 */
327 virtual PINDEX Insert(
328 const PObject & before, ///< Object value to insert before.
329 PObject * obj ///< New object to place into the collection.
330 );
331
332 /**Add a new object to the collection. If the objects value is already in
333 the set then the object is \b not included. If the
334 <code>AllowDeleteObjects</code> option is set then the \p obj parameter is
335 also deleted.
336
337 The object is always placed in the an ordinal position dependent on its
338 hash function. It is not placed at the specified position. The
339 \p index parameter is ignored.
340
341 @return
342 hash function value of the newly added object.
343 */
344 virtual PINDEX InsertAt(
345 PINDEX index, ///< Index position in collection to place the object.
346 PObject * obj ///< New object to place into the collection.
347 );
348
349 /**Remove the object from the collection. If the <code>AllowDeleteObjects</code> option
350 is set then the object is also deleted.
351
352 Note that the comparison for searching for the object in collection is
353 made by pointer, not by value. Thus the parameter must point to the
354 same instance of the object that is in the collection.
355
356 @return
357 true if the object was in the collection.
358 */
359 virtual PBoolean Remove(
360 const PObject * obj ///< Existing object to remove from the collection.
361 );
362
363 /**Remove an object at the specified index. If the <code>AllowDeleteObjects</code>
364 option is set then the object is also deleted.
365
366 @return
367 pointer to the object being removed, or NULL if it was deleted.
368 */
369 virtual PObject * RemoveAt(
370 PINDEX index ///< Index position in collection to place the object.
371 );
372
373 /**This function is the same as PHashTable::AbstractGetKeyAt().
374
375 @return
376 Always NULL.
377 */
378 virtual PObject * GetAt(
379 PINDEX index ///< Index position in the collection of the object.
380 ) const;
381
382 /**Add a new object to the collection. If the objects value is already in
383 the set then the object is \b not included. If the
384 AllowDeleteObjects option is set then the \p obj parameter is
385 also deleted.
386
387 The object is always placed in the an ordinal position dependent on its
388 hash function. It is not placed at the specified position. The
389 \p index parameter is ignored.
390
391 @return
392 true if the object was successfully added.
393 */
394 virtual PBoolean SetAt(
395 PINDEX index, ///< Index position in collection to set.
396 PObject * val ///< New value to place into the collection.
397 );
398
399 /**Search the collection for the specific instance of the object. The
400 object pointers are compared, not the values. The hash table is used
401 to locate the entry.
402
403 Note that that will require value comparisons to be made to find the
404 equivalent entry and then a final check is made with the pointers to
405 see if they are the same instance.
406
407 @return
408 ordinal index position of the object, or P_MAX_INDEX .
409 */
410 virtual PINDEX GetObjectsIndex(
411 const PObject * obj ///< Object to find.
412 ) const;
413
414 /**Search the collection for the specified value of the object. The object
415 values are compared, not the pointers. So the objects in the
416 collection must correctly implement the <code>PObject::Compare()</code>
417 function. The hash table is used to locate the entry.
418
419 @return
420 ordinal index position of the object, or P_MAX_INDEX.
421 */
422 virtual PINDEX GetValuesIndex(
423 const PObject & obj ///< Object to find equal value.
424 ) const;
425
426 /**Calculate union of sets.
427 Returns true if any new elements were added.
428 */
429 bool Union(
430 const PAbstractSet & set
431 );
432
433 /**Calculate intersection of sets.
434 Returns true if there is an intersection.
435 */
436 static bool Intersection(
437 const PAbstractSet & set1,
438 const PAbstractSet & set2,
439 PAbstractSet * intersection = NULL
440 );
441 //@}
442 };
443
444
445 /**This template class maps the <code>PAbstractSet</code> to a specific object type. The
446 functions in this class primarily do all the appropriate casting of types.
447
448 By default, objects placed into the set will \b not be deleted when
449 removed or when all references to the set are destroyed. This is different
450 from the default on most collection classes.
451
452 Note that if templates are not used the <code>PDECLARE_SET</code> macro will
453 simulate the template instantiation.
454 */
455 template <class T> class PSet : public PAbstractSet
456 {
457 PCLASSINFO(PSet, PAbstractSet);
458
459 public:
460 /**@name Construction */
461 //@{
462 /**Create a new, empty, dictionary. The parameter indicates whether to
463 delete objects that are removed from the set.
464
465 Note that by default, objects placed into the set will \b not be
466 deleted when removed or when all references to the set are destroyed.
467 This is different from the default on most collection classes.
468 */
469 inline PSet(PBoolean initialDeleteObjects = false)
PAbstractSet()470 : PAbstractSet() { AllowDeleteObjects(initialDeleteObjects); }
471 //@}
472
473 /**@name Overrides from class PObject */
474 //@{
475 /**Make a complete duplicate of the set. Note that all objects in the
476 array are also cloned, so this will make a complete copy of the set.
477 */
Clone()478 virtual PObject * Clone() const
479 { return PNEW PSet(0, this); }
480 //@}
481
482 /**@name New functions for class */
483 //@{
484 /**Include the specified object into the set. If the objects value is
485 already in the set then the object is \b not included. If the
486 <code>AllowDeleteObjects</code> option is set then the \p obj parameter is
487 also deleted.
488
489 The object values are compared, not the pointers. So the objects in
490 the collection must correctly implement the <code>PObject::Compare()</code>
491 function. The hash table is used to locate the entry.
492 */
Include(const T * obj)493 void Include(
494 const T * obj // New object to include in the set.
495 ) { Append((PObject *)obj); }
496
497 /**Include the specified objects value into the set. If the objects value
498 is already in the set then the object is \b not included.
499
500 The object values are compared, not the pointers. So the objects in
501 the collection must correctly implement the <code>PObject::Compare()</code>
502 function. The hash table is used to locate the entry.
503 */
504 PSet & operator+=(
505 const T & obj // New object to include in the set.
506 ) { Append(obj.Clone()); return *this; }
507
508 /**Remove the object from the set. If the <code>AllowDeleteObjects</code> option is set
509 then the object is also deleted.
510
511 The object values are compared, not the pointers. So the objects in
512 the collection must correctly implement the <code>PObject::Compare()</code>
513 function. The hash table is used to locate the entry.
514 */
Exclude(const T * obj)515 void Exclude(
516 const T * obj // New object to exclude in the set.
517 ) { Remove(obj); }
518
519 /**Remove the objects value from the set. If the <code>AllowDeleteObjects</code>
520 option is set then the object is also deleted.
521
522 The object values are compared, not the pointers. So the objects in
523 the collection must correctly implement the <code>PObject::Compare()</code>
524 function. The hash table is used to locate the entry.
525 */
526 PSet & operator-=(
527 const T & obj // New object to exclude in the set.
528 ) { RemoveAt(GetValuesIndex(obj)); return *this; }
529
530 /**Determine if the value of the object is contained in the set. The
531 object values are compared, not the pointers. So the objects in the
532 collection must correctly implement the <code>PObject::Compare()</code>
533 function. The hash table is used to locate the entry.
534
535 @return
536 true if the object value is in the set.
537 */
Contains(const T & key)538 PBoolean Contains(
539 const T & key ///< Key to look for in the set.
540 ) const { return AbstractContains(key); }
541
542 /**Determine if the value of the object is contained in the set. The
543 object values are compared, not the pointers. So the objects in the
544 collection must correctly implement the <code>PObject::Compare()</code>
545 function. The hash table is used to locate the entry.
546
547 @return
548 true if the object value is in the set.
549 */
550 PBoolean operator[](
551 const T & key ///< Key to look for in the set.
552 ) const { return AbstractContains(key); }
553
554 /**Get the key in the set at the ordinal index position.
555
556 The ordinal position in the set is determined by the hash values of the
557 keys and the order of insertion.
558
559 The last key/data pair is remembered by the class so that subseqent
560 access is very fast.
561
562 @return
563 reference to key at the index position.
564 */
GetKeyAt(PINDEX index)565 virtual const T & GetKeyAt(
566 PINDEX index ///< Index of value to get.
567 ) const
568 { return (const T &)AbstractGetKeyAt(index); }
569 //@}
570
571
572 protected:
PSet(int dummy,const PSet * c)573 PSet(int dummy, const PSet * c)
574 : PAbstractSet(dummy, c)
575 { reference->deleteObjects = c->reference->deleteObjects; }
576 };
577
578
579 /**Declare set class.
580 This macro is used to declare a descendent of <code>PAbstractSet</code> class,
581 customised for a particular object type \b T. This macro closes the
582 class declaration off so no additional members can be added.
583
584 If the compilation is using templates then this macro produces a typedef
585 of the <code>PSet</code> template class.
586
587 See the <code>PSet</code> class and <code>PDECLARE_SET</code> macro for more
588 information.
589 */
590 #define PSET(cls, T) typedef PSet<T> cls
591
592
593 /**Begin declaration of a set class.
594 This macro is used to declare a descendent of <code>PAbstractSet</code> class,
595 customised for a particular object type \b T.
596
597 If the compilation is using templates then this macro produces a descendent
598 of the <code>PSet</code> template class. If templates are not being used then the
599 macro defines a set of inline functions to do all casting of types. The
600 resultant classes have an identical set of functions in either case.
601
602 See the <code>PSet</code> and <code>PAbstractSet</code> classes for more information.
603 */
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
622 //////////////////////////////////////////////////////////////////////////////
623
624 /**An abstract dictionary container.
625 */
626 class PAbstractDictionary : public PHashTable
627 {
628 PCLASSINFO(PAbstractDictionary, PHashTable);
629 public:
630 /**@name Construction */
631 //@{
632 /**Create a new, empty, dictionary.
633
634 Note that by default, objects placed into the dictionary will be deleted
635 when removed or when all references to the dictionary are destroyed.
636 */
637 PINLINE PAbstractDictionary();
638 //@}
639
640 /**@name Overrides from class PObject */
641 //@{
642 /**Output the contents of the object to the stream. The exact output is
643 dependent on the exact semantics of the descendent class. This is
644 primarily used by the standard <code>operator<<</code> function.
645
646 The default behaviour is to print the class name.
647 */
648 virtual void PrintOn(
649 ostream &strm ///< Stream to print the object into.
650 ) const;
651 //@}
652
653 /**@name Overrides from class PCollection */
654 //@{
655 /**Insert a new object into the dictionary. The semantics of this function
656 is different from that of the <code>PCollection</code> class. This function is
657 exactly equivalent to the <code>SetAt()</code> function that sets a data value at
658 the key value location.
659
660 @return
661 Always zero.
662 */
663 virtual PINDEX Insert(
664 const PObject & key, ///< Object value to use as the key.
665 PObject * obj ///< New object to place into the collection.
666 );
667
668 /**Insert a new object at the specified index. This function only applies
669 to derived classes whose key is PINDEX based.
670
671 @return
672 \p index parameter.
673 */
674 virtual PINDEX InsertAt(
675 PINDEX index, ///< Index position in collection to place the object.
676 PObject * obj ///< New object to place into the collection.
677 );
678
679 /**Remove an object at the specified index. This function only applies
680 to derived classes whose key is PINDEX based. The returned pointer is
681 then removed using the <code>SetAt()</code> function to set that key value to NULL.
682 If the <code>AllowDeleteObjects</code> option is set then the object is also
683 deleted.
684
685 @return
686 pointer to the object being removed, or NULL if it was deleted.
687 */
688 virtual PObject * RemoveAt(
689 PINDEX index ///< Index position in collection to place the object.
690 );
691
692 /**Set the object at the specified index to the new value. This function
693 only applies to derived classes whose key is PINDEX based. This will
694 overwrite the existing entry. If the AllowDeleteObjects() option is set
695 then the old object is also deleted.
696
697 @return
698 true if the object was successfully added.
699 */
700 virtual PBoolean SetAt(
701 PINDEX index, ///< Index position in collection to set.
702 PObject * val ///< New value to place into the collection.
703 );
704
705 /**Get the object at the specified index position. If the index was not in
706 the collection then NULL is returned.
707
708 @return
709 pointer to object at the specified index.
710 */
711 virtual PObject * GetAt(
712 PINDEX index ///< Index position in the collection of the object.
713 ) const;
714
715 /**Search the collection for the specific instance of the object. The
716 object pointers are compared, not the values. The hash table is used
717 to locate the entry.
718
719 Note that that will require value comparisons to be made to find the
720 equivalent entry and then a final check is made with the pointers to
721 see if they are the same instance.
722
723 @return
724 ordinal index position of the object, or P_MAX_INDEX.
725 */
726 virtual PINDEX GetObjectsIndex(
727 const PObject * obj ///< Object to find.
728 ) const;
729
730 /**Search the collection for the specified value of the object. The object
731 values are compared, not the pointers. So the objects in the
732 collection must correctly implement the <code>PObject::Compare()</code>
733 function. The hash table is used to locate the entry.
734
735 @return
736 ordinal index position of the object, or P_MAX_INDEX.
737 */
738 virtual PINDEX GetValuesIndex(
739 const PObject & obj ///< Object to find value of.
740 ) const;
741 //@}
742
743
744 /**@name New functions for class */
745 //@{
746 /**Set the data at the specified ordinal index position in the dictionary.
747
748 The ordinal position in the dictionary is determined by the hash values
749 of the keys and the order of insertion.
750
751 @return
752 true if the new object could be placed into the dictionary.
753 */
754 virtual PBoolean SetDataAt(
755 PINDEX index, ///< Ordinal index in the dictionary.
756 PObject * obj ///< New object to put into the dictionary.
757 );
758
759 /**Add a new object to the collection. If the objects value is already in
760 the dictionary then the object is overrides the previous value. If the
761 AllowDeleteObjects option is set then the old object is also deleted.
762
763 The object is placed in the an ordinal position dependent on the keys
764 hash function. Subsequent searches use the hash function to speed access
765 to the data item.
766
767 @return
768 true if the object was successfully added.
769 */
770 virtual PBoolean AbstractSetAt(
771 const PObject & key, ///< Key for position in dictionary to add object.
772 PObject * obj ///< New object to put into the dictionary.
773 );
774
775 /**Get the object at the specified key position. If the key was not in the
776 collection then this function asserts.
777
778 This function is primarily for use by the operator[] function in the
779 descendent template classes.
780
781 @return
782 reference to object at the specified key.
783 */
784 virtual PObject & GetRefAt(
785 const PObject & key ///< Key for position in dictionary to get object.
786 ) const;
787
788 /**Get the object at the specified key position. If the key was not in the
789 collection then NULL is returned.
790
791 @return
792 pointer to object at the specified key.
793 */
794 virtual PObject * AbstractGetAt(
795 const PObject & key ///< Key for position in dictionary to get object.
796 ) const;
797
798 /**Get an array containing all the keys for the dictionary.
799 */
800 virtual void AbstractGetKeys(
801 PArrayObjects & keys
802 ) const;
803 //@}
804
805 protected:
806 PINLINE PAbstractDictionary(int dummy, const PAbstractDictionary * c);
807
808 private:
809 /**This function is meaningless and will assert.
810
811 @return
812 Always zero.
813 */
814 virtual PINDEX Append(
815 PObject * obj ///< New object to place into the collection.
816 );
817
818 /**Remove the object from the collection. If the <code>AllowDeleteObjects</code> option
819 is set then the object is also deleted.
820
821 Note that the comparison for searching for the object in collection is
822 made by pointer, not by value. Thus the parameter must point to the
823 same instance of the object that is in the collection.
824
825 @return
826 true if the object was in the collection.
827 */
828 virtual PBoolean Remove(
829 const PObject * obj ///< Existing object to remove from the collection.
830 );
831
832 };
833
834
835 /**This template class maps the <code>PAbstractDictionary</code> to a specific key and data
836 types. The functions in this class primarily do all the appropriate casting
837 of types.
838
839 Note that if templates are not used the <code>PDECLARE_DICTIONARY</code> macro
840 will simulate the template instantiation.
841 */
842 template <class K, class D> class PDictionary : public PAbstractDictionary
843 {
844 PCLASSINFO(PDictionary, PAbstractDictionary);
845
846 public:
847 /**@name Construction */
848 //@{
849 /**Create a new, empty, dictionary.
850
851 Note that by default, objects placed into the dictionary will be
852 deleted when removed or when all references to the dictionary are
853 destroyed.
854 */
855 PDictionary()
856 : PAbstractDictionary() { }
857 //@}
858
859 /**@name Overrides from class PObject */
860 //@{
861 /**Make a complete duplicate of the dictionary. Note that all objects in
862 the array are also cloned, so this will make a complete copy of the
863 dictionary.
864 */
865 virtual PObject * Clone() const
866 { return PNEW PDictionary(0, this); }
867 //@}
868
869 /**@name New functions for class */
870 //@{
871 /**Get the object contained in the dictionary at the \p key
872 position. The hash table is used to locate the data quickly via the
873 hash function provided by the \p key.
874
875 The last key/data pair is remembered by the class so that subseqent
876 access is very fast.
877
878 @return
879 reference to the object indexed by the key.
880 */
881 D & operator[](
882 const K & key ///< Key to look for in the dictionary.
883 ) const
884 { return (D &)GetRefAt(key); }
885
886 /**Determine if the value of the object is contained in the hash table. The
887 object values are compared, not the pointers. So the objects in the
888 collection must correctly implement the <code>PObject::Compare()</code>
889 function. The hash table is used to locate the entry.
890
891 @return
892 true if the object value is in the dictionary.
893 */
894 PBoolean Contains(
895 const K & key ///< Key to look for in the dictionary.
896 ) const { return AbstractContains(key); }
897
898 /**Remove an object at the specified \p key. The returned pointer is then
899 removed using the <code>SetAt()</code> function to set that key value to
900 NULL. If the <code>AllowDeleteObjects</code> option is set then the
901 object is also deleted.
902
903 @return
904 pointer to the object being removed, or NULL if the key was not
905 present in the dictionary. If the dictionary is set to delete objects
906 upon removal, the value -1 is returned if the key existed prior to removal
907 rather than returning an illegal pointer
908 */
909 virtual D * RemoveAt(
910 const K & key ///< Key for position in dictionary to get object.
911 ) {
912 D * obj = GetAt(key); AbstractSetAt(key, NULL);
913 return reference->deleteObjects ? (obj ? (D *)-1 : NULL) : obj;
914 }
915
916 /**Add a new object to the collection. If the objects value is already in
917 the dictionary then the object is overrides the previous value. If the
918 <code>AllowDeleteObjects</code> option is set then the old object is also deleted.
919
920 The object is placed in the an ordinal position dependent on the keys
921 hash function. Subsequent searches use the hash function to speed access
922 to the data item.
923
924 @return
925 true if the object was successfully added.
926 */
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
932 /**Get the object at the specified key position. If the key was not in the
933 collection then NULL is returned.
934
935 @return
936 pointer to object at the specified key.
937 */
938 virtual D * GetAt(
939 const K & key // Key for position in dictionary to get object.
940 ) const { return (D *)AbstractGetAt(key); }
941
942 /**Get the key in the dictionary at the ordinal index position.
943
944 The ordinal position in the dictionary is determined by the hash values
945 of the keys and the order of insertion.
946
947 The last key/data pair is remembered by the class so that subseqent
948 access is very fast.
949
950 @return
951 reference to key at the index position.
952 */
953 const K & GetKeyAt(
954 PINDEX index ///< Ordinal position in dictionary for key.
955 ) const
956 { return (const K &)AbstractGetKeyAt(index); }
957
958 /**Get the data in the dictionary at the ordinal index position.
959
960 The ordinal position in the dictionary is determined by the hash values
961 of the keys and the order of insertion.
962
963 The last key/data pair is remembered by the class so that subseqent
964 access is very fast.
965
966 @return
967 reference to data at the index position.
968 */
969 D & GetDataAt(
970 PINDEX index ///< Ordinal position in dictionary for data.
971 ) const
972 { return (D &)AbstractGetDataAt(index); }
973
974 /**Get an array containing all the keys for the dictionary.
975 */
976 PArray<K> GetKeys() const
977 {
978 PArray<K> keys;
979 AbstractGetKeys(keys);
980 return keys;
981 }
982 //@}
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
992 /**Declare a dictionary class.
993 This macro is used to declare a descendent of PAbstractDictionary class,
994 customised for a particular key type \b K and data object type \b D.
995 This macro closes the class declaration off so no additional members can
996 be added.
997
998 If the compilation is using templates then this macro produces a typedef
999 of the <code>PDictionary</code> template class.
1000
1001 See the <code>PDictionary</code> class and <code>PDECLARE_DICTIONARY</code> macro for
1002 more information.
1003 */
1004 #define PDICTIONARY(cls, K, D) typedef PDictionary<K, D> cls
1005
1006
1007 /**Begin declaration of dictionary class.
1008 This macro is used to declare a descendent of PAbstractDictionary class,
1009 customised for a particular key type \b K and data object type \b D.
1010
1011 If the compilation is using templates then this macro produces a descendent
1012 of the <code>PDictionary</code> template class. If templates are not being used
1013 then the macro defines a set of inline functions to do all casting of types.
1014 The resultant classes have an identical set of functions in either case.
1015
1016 See the <code>PDictionary</code> and <code>PAbstractDictionary</code> classes for more
1017 information.
1018 */
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
1032 /**This template class maps the <code>PAbstractDictionary</code> to a specific key
1033 type and a <code>POrdinalKey</code> data type. The functions in this class
1034 primarily do all the appropriate casting of types.
1035
1036 Note that if templates are not used the <code>PDECLARE_ORDINAL_DICTIONARY</code>
1037 macro will simulate the template instantiation.
1038 */
1039 template <class K> class POrdinalDictionary : public PAbstractDictionary
1040 {
1041 PCLASSINFO(POrdinalDictionary, PAbstractDictionary);
1042
1043 public:
1044 /**@name Construction */
1045 //@{
1046 /**Create a new, empty, dictionary.
1047
1048 Note that by default, objects placed into the dictionary will be
1049 deleted when removed or when all references to the dictionary are
1050 destroyed.
1051 */
1052 POrdinalDictionary()
1053 : PAbstractDictionary() { }
1054 //@}
1055
1056 /**@name Overrides from class PObject */
1057 //@{
1058 /**Make a complete duplicate of the dictionary. Note that all objects in
1059 the array are also cloned, so this will make a complete copy of the
1060 dictionary.
1061 */
1062 virtual PObject * Clone() const
1063 { return PNEW POrdinalDictionary(0, this); }
1064 //@}
1065
1066 /**@name New functions for class */
1067 //@{
1068 /**Get the object contained in the dictionary at the \p key
1069 position. The hash table is used to locate the data quickly via the
1070 hash function provided by the key.
1071
1072 The last key/data pair is remembered by the class so that subseqent
1073 access is very fast.
1074
1075 @return
1076 reference to the object indexed by the key.
1077 */
1078 PINDEX operator[](
1079 const K & key // Key to look for in the dictionary.
1080 ) const
1081 { return (POrdinalKey &)GetRefAt(key); }
1082
1083 /**Determine if the value of the object is contained in the hash table. The
1084 object values are compared, not the pointers. So the objects in the
1085 collection must correctly implement the <code>PObject::Compare()</code>
1086 function. The hash table is used to locate the entry.
1087
1088 @return
1089 true if the object value is in the dictionary.
1090 */
1091 PBoolean Contains(
1092 const K & key ///< Key to look for in the dictionary.
1093 ) const { return AbstractContains(key); }
1094
1095 virtual POrdinalKey * GetAt(
1096 const K & key ///< Key for position in dictionary to get object.
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
1105 /**Set the data at the specified ordinal index position in the dictionary.
1106
1107 The ordinal position in the dictionary is determined by the hash values
1108 of the keys and the order of insertion.
1109
1110 @return
1111 true if the new object could be placed into the dictionary.
1112 */
1113 virtual PBoolean SetDataAt(
1114 PINDEX index, ///< Ordinal index in the dictionary.
1115 PINDEX ordinal ///< New ordinal value to put into the dictionary.
1116 ) { return PAbstractDictionary::SetDataAt(index, PNEW POrdinalKey(ordinal)); }
1117
1118 /**Add a new object to the collection. If the objects value is already in
1119 the dictionary then the object is overrides the previous value. If the
1120 <code>AllowDeleteObjects</code> option is set then the old object is also deleted.
1121
1122 The object is placed in the an ordinal position dependent on the keys
1123 hash function. Subsequent searches use the hash function to speed access
1124 to the data item.
1125
1126 @return
1127 true if the object was successfully added.
1128 */
1129 virtual PBoolean SetAt(
1130 const K & key, ///< Key for position in dictionary to add object.
1131 PINDEX ordinal ///< New ordinal value to put into the dictionary.
1132 ) { return AbstractSetAt(key, PNEW POrdinalKey(ordinal)); }
1133
1134 /**Remove an object at the specified key. The returned pointer is then
1135 removed using the <code>SetAt()</code> function to set that key value to
1136 NULL. If the <code>AllowDeleteObjects</code> option is set then the
1137 object is also deleted.
1138
1139 @return
1140 pointer to the object being removed, or NULL if it was deleted.
1141 */
1142 virtual PINDEX RemoveAt(
1143 const K & key ///< Key for position in dictionary to get object.
1144 ) { PINDEX ord = *GetAt(key); AbstractSetAt(key, NULL); return ord; }
1145
1146 /**Get the key in the dictionary at the ordinal index position.
1147
1148 The ordinal position in the dictionary is determined by the hash values
1149 of the keys and the order of insertion.
1150
1151 The last key/data pair is remembered by the class so that subseqent
1152 access is very fast.
1153
1154 @return
1155 reference to key at the index position.
1156 */
1157 const K & GetKeyAt(
1158 PINDEX index ///< Ordinal position in dictionary for key.
1159 ) const
1160 { return (const K &)AbstractGetKeyAt(index); }
1161
1162 /**Get the data in the dictionary at the ordinal index position.
1163
1164 The ordinal position in the dictionary is determined by the hash values
1165 of the keys and the order of insertion.
1166
1167 The last key/data pair is remembered by the class so that subseqent
1168 access is very fast.
1169
1170 @return
1171 reference to data at the index position.
1172 */
1173 PINDEX GetDataAt(
1174 PINDEX index ///< Ordinal position in dictionary for data.
1175 ) const
1176 { return (POrdinalKey &)AbstractGetDataAt(index); }
1177 //@}
1178
1179 protected:
1180 POrdinalDictionary(int dummy, const POrdinalDictionary * c)
1181 : PAbstractDictionary(dummy, c) { }
1182 };
1183
1184
1185 /**Declare an ordinal dictionary class.
1186 This macro is used to declare a descendent of PAbstractDictionary class,
1187 customised for a particular key type \b K and data object type of
1188 <code>POrdinalKey</code>. This macro closes the class declaration off so no
1189 additional members can be added.
1190
1191 If the compilation is using templates then this macro produces a typedef
1192 of the <code>POrdinalDictionary</code> template class.
1193
1194 See the <code>POrdinalDictionary</code> class and
1195 <code>PDECLARE_ORDINAL_DICTIONARY</code> macro for more information.
1196 */
1197 #define PORDINAL_DICTIONARY(cls, K) typedef POrdinalDictionary<K> cls
1198
1199
1200 /**Begin declaration of an ordinal dictionary class.
1201 This macro is used to declare a descendent of PAbstractList class,
1202 customised for a particular key type \b K and data object type of
1203 <code>POrdinalKey</code>.
1204
1205 If the compilation is using templates then this macro produces a descendent
1206 of the <code>POrdinalDictionary</code> template class. If templates are not being
1207 used then the macro defines a set of inline functions to do all casting of
1208 types. The resultant classes have an identical set of functions in either
1209 case.
1210
1211 See the <code>POrdinalDictionary</code> and <code>PAbstractDictionary</code> classes
1212 for more information.
1213 */
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 ///////////////////////////////////////////////////////////////
1230