dict.h
Go to the documentation of this file.
/*
* dict.h
*
* Dictionary (hash table) Container classes.
*
* Portable Tools Library
*
* Copyright (c) 1993-1998 Equivalence Pty. Ltd.
*
* The contents of this file are subject to the Mozilla Public License
* Version 1.0 (the "License"); you may not use this file except in
* compliance with the License. You may obtain a copy of the License at
* http://www.mozilla.org/MPL/
*
* Software distributed under the License is distributed on an "AS IS"
* basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
* the License for the specific language governing rights and limitations
* under the License.
*
* The Original Code is Portable Windows Library.
*
* The Initial Developer of the Original Code is Equivalence Pty. Ltd.
*
* Portions are Copyright (C) 1993 Free Software Foundation, Inc.
* All Rights Reserved.
*
* Contributor(s): ______________________________________.
*
* $Revision: 28056 $
* $Author: rjongbloed $
* $Date: 2012-07-18 03:21:10 -0500 (Wed, 18 Jul 2012) $
*/
#ifndef PTLIB_DICT_H
#define PTLIB_DICT_H
#ifdef P_USE_PRAGMA
#pragma interface
#endif
#include <ptlib/array.h>
// PDictionary classes
class POrdinalKey : public PObject
{
PCLASSINFO(POrdinalKey, PObject);
public:
PINLINE POrdinalKey(
PINDEX newKey = 0
);
PINLINE POrdinalKey & operator=(PINDEX);
virtual PObject * Clone() const;
/* Get the relative rank of the ordinal index. This is a simpel comparison
of the objects PINDEX values.
@return
comparison of the two objects, <code>EqualTo</code> for same,
<code>LessThan</code> for \p obj logically less than the
object and <code>GreaterThan</code> for \p obj logically
greater than the object.
*/
virtual Comparison Compare(const PObject & obj) const;
virtual PINDEX HashFunction() const;
virtual void PrintOn(ostream & strm) const;
PINLINE operator PINDEX() const;
PINLINE PINDEX operator++();
PINLINE PINDEX operator++(int);
PINLINE PINDEX operator--();
PINLINE PINDEX operator--(int);
PINLINE POrdinalKey & operator+=(PINDEX);
PINLINE POrdinalKey & operator-=(PINDEX );
private:
PINDEX theKey;
};
// Member variables
struct PHashTableElement
{
PObject * key;
PObject * data;
PHashTableElement * next;
PHashTableElement * prev;
PDECLARE_POOL_ALLOCATOR();
};
PDECLARE_BASEARRAY(PHashTableInfo, PHashTableElement *)
#ifdef DOC_PLUS_PLUS
{
#endif
public:
virtual ~PHashTableInfo() { Destruct(); }
virtual void DestroyContents();
PINDEX AppendElement(PObject * key, PObject * data);
PObject * RemoveElement(const PObject & key);
PBoolean SetLastElementAt(PINDEX index, PHashTableElement * & lastElement);
PHashTableElement * GetElementAt(const PObject & key);
PINDEX GetElementsIndex(const PObject*obj,PBoolean byVal,PBoolean keys) const;
PBoolean deleteKeys;
typedef PHashTableElement Element;
friend class PHashTable;
friend class PAbstractSet;
};
class PHashTable : public PCollection
{
PCONTAINERINFO(PHashTable, PCollection);
public:
PHashTable();
virtual Comparison Compare(
const PObject & obj
) const;
virtual PBoolean SetSize(
PINDEX newSize
);
PINLINE PBoolean AbstractContains(
const PObject & key
) const;
virtual const PObject & AbstractGetKeyAt(
PINDEX index
) const;
virtual PObject & AbstractGetDataAt(
PINDEX index
) const;
// The type below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it
typedef PHashTableElement Element;
typedef PHashTableInfo Table;
PHashTableInfo * hashTable;
};
class PAbstractSet : public PHashTable
{
PCONTAINERINFO(PAbstractSet, PHashTable);
public:
PINLINE PAbstractSet();
virtual PINDEX Append(
PObject * obj
);
virtual PINDEX Insert(
const PObject & before,
PObject * obj
);
virtual PINDEX InsertAt(
PINDEX index,
PObject * obj
);
virtual PBoolean Remove(
const PObject * obj
);
virtual PObject * RemoveAt(
PINDEX index
);
virtual PObject * GetAt(
PINDEX index
) const;
virtual PBoolean SetAt(
PINDEX index,
PObject * val
);
virtual PINDEX GetObjectsIndex(
const PObject * obj
) const;
virtual PINDEX GetValuesIndex(
const PObject & obj
) const;
bool Union(
const PAbstractSet & set
);
static bool Intersection(
const PAbstractSet & set1,
const PAbstractSet & set2,
PAbstractSet * intersection = NULL
);
};
template <class T> class PSet : public PAbstractSet
{
PCLASSINFO(PSet, PAbstractSet);
public:
inline PSet(PBoolean initialDeleteObjects = false)
: PAbstractSet() { AllowDeleteObjects(initialDeleteObjects); }
virtual PObject * Clone() const
{ return PNEW PSet(0, this); }
void Include(
const T * obj // New object to include in the set.
) { Append((PObject *)obj); }
PSet & operator+=(
const T & obj // New object to include in the set.
) { Append(obj.Clone()); return *this; }
void Exclude(
const T * obj // New object to exclude in the set.
) { Remove(obj); }
PSet & operator-=(
const T & obj // New object to exclude in the set.
) { RemoveAt(GetValuesIndex(obj)); return *this; }
PBoolean Contains(
const T & key
) const { return AbstractContains(key); }
PBoolean operator[](
const T & key
) const { return AbstractContains(key); }
virtual const T & GetKeyAt(
PINDEX index
) const
{ return (const T &)AbstractGetKeyAt(index); }
protected:
PSet(int dummy, const PSet * c)
: PAbstractSet(dummy, c)
{ reference->deleteObjects = c->reference->deleteObjects; }
};
#define PSET(cls, T) typedef PSet<T> cls
#define PDECLARE_SET(cls, T, initDelObj) \
class cls : public PSet<T> { \
typedef PSet<T> BaseClass; PCLASSINFO(cls, BaseClass) \
protected: \
cls(int dummy, const cls * c) \
: BaseClass(dummy, c) { } \
public: \
cls(PBoolean initialDeleteObjects = initDelObj) \
: BaseClass(initialDeleteObjects) { } \
virtual PObject * Clone() const \
{ return PNEW cls(0, this); } \
PDECLARE_SET(POrdinalSet, POrdinalKey, true)
};
class PAbstractDictionary : public PHashTable
{
PCLASSINFO(PAbstractDictionary, PHashTable);
public:
PINLINE PAbstractDictionary();
virtual void PrintOn(
ostream &strm
) const;
virtual PINDEX Insert(
const PObject & key,
PObject * obj
);
virtual PINDEX InsertAt(
PINDEX index,
PObject * obj
);
virtual PObject * RemoveAt(
PINDEX index
);
virtual PBoolean SetAt(
PINDEX index,
PObject * val
);
virtual PObject * GetAt(
PINDEX index
) const;
virtual PINDEX GetObjectsIndex(
const PObject * obj
) const;
virtual PINDEX GetValuesIndex(
const PObject & obj
) const;
virtual PBoolean SetDataAt(
PINDEX index,
PObject * obj
);
virtual PBoolean AbstractSetAt(
const PObject & key,
PObject * obj
);
virtual PObject & GetRefAt(
const PObject & key
) const;
virtual PObject * AbstractGetAt(
const PObject & key
) const;
virtual void AbstractGetKeys(
PArrayObjects & keys
) const;
protected:
PINLINE PAbstractDictionary(int dummy, const PAbstractDictionary * c);
private:
virtual PINDEX Append(
PObject * obj
);
virtual PBoolean Remove(
const PObject * obj
);
};
template <class K, class D> class PDictionary : public PAbstractDictionary
{
PCLASSINFO(PDictionary, PAbstractDictionary);
public:
PDictionary()
: PAbstractDictionary() { }
virtual PObject * Clone() const
{ return PNEW PDictionary(0, this); }
D & operator[](
const K & key
) const
{ return (D &)GetRefAt(key); }
PBoolean Contains(
const K & key
) const { return AbstractContains(key); }
virtual D * RemoveAt(
const K & key
) {
D * obj = GetAt(key); AbstractSetAt(key, NULL);
return reference->deleteObjects ? (obj ? (D *)-1 : NULL) : obj;
}
virtual PBoolean SetAt(
const K & key, // Key for position in dictionary to add object.
D * obj // New object to put into the dictionary.
) { return AbstractSetAt(key, obj); }
virtual D * GetAt(
const K & key // Key for position in dictionary to get object.
) const { return (D *)AbstractGetAt(key); }
const K & GetKeyAt(
PINDEX index
) const
{ return (const K &)AbstractGetKeyAt(index); }
D & GetDataAt(
PINDEX index
) const
{ return (D &)AbstractGetDataAt(index); }
PArray<K> GetKeys() const
{
PArray<K> keys;
AbstractGetKeys(keys);
return keys;
}
typedef std::pair<K, D *> value_type;
protected:
PDictionary(int dummy, const PDictionary * c)
: PAbstractDictionary(dummy, c) { }
};
#define PDICTIONARY(cls, K, D) typedef PDictionary<K, D> cls
#define PDECLARE_DICTIONARY(cls, K, D) \
PDICTIONARY(cls##_PTemplate, K, D); \
PDECLARE_CLASS(cls, cls##_PTemplate) \
protected: \
cls(int dummy, const cls * c) \
: cls##_PTemplate(dummy, c) { } \
public: \
cls() \
: cls##_PTemplate() { } \
virtual PObject * Clone() const \
{ return PNEW cls(0, this); } \
template <class K> class POrdinalDictionary : public PAbstractDictionary
{
PCLASSINFO(POrdinalDictionary, PAbstractDictionary);
public:
POrdinalDictionary()
: PAbstractDictionary() { }
virtual PObject * Clone() const
{ return PNEW POrdinalDictionary(0, this); }
PINDEX operator[](
const K & key // Key to look for in the dictionary.
) const
{ return (POrdinalKey &)GetRefAt(key); }
PBoolean Contains(
const K & key
) const { return AbstractContains(key); }
virtual POrdinalKey * GetAt(
const K & key
) const { return (POrdinalKey *)AbstractGetAt(key); }
/* Get the object at the specified key position. If the key was not in the
collection then NULL is returned.
@return
pointer to object at the specified key.
*/
virtual PBoolean SetDataAt(
PINDEX index,
PINDEX ordinal
) { return PAbstractDictionary::SetDataAt(index, PNEW POrdinalKey(ordinal)); }
virtual PBoolean SetAt(
const K & key,
PINDEX ordinal
) { return AbstractSetAt(key, PNEW POrdinalKey(ordinal)); }
virtual PINDEX RemoveAt(
const K & key
) { PINDEX ord = *GetAt(key); AbstractSetAt(key, NULL); return ord; }
const K & GetKeyAt(
PINDEX index
) const
{ return (const K &)AbstractGetKeyAt(index); }
PINDEX GetDataAt(
PINDEX index
) const
{ return (POrdinalKey &)AbstractGetDataAt(index); }
protected:
POrdinalDictionary(int dummy, const POrdinalDictionary * c)
: PAbstractDictionary(dummy, c) { }
};
#define PORDINAL_DICTIONARY(cls, K) typedef POrdinalDictionary<K> cls
#define PDECLARE_ORDINAL_DICTIONARY(cls, K) \
PORDINAL_DICTIONARY(cls##_PTemplate, K); \
PDECLARE_CLASS(cls, POrdinalDictionary<K>) \
protected: \
cls(int dummy, const cls * c) \
: cls##_PTemplate(dummy, c) { } \
public: \
cls() \
: cls##_PTemplate() { } \
virtual PObject * Clone() const \
{ return PNEW cls(0, this); } \
#endif // PTLIB_DICT_H
// End Of File ///////////////////////////////////////////////////////////////
PDictionary::GetKeys
PArray< K > GetKeys() const
Get an array containing all the keys for the dictionary.
Definition: dict.h:976
PSet::Include
void Include(const T *obj)
Include the specified object into the set.
Definition: dict.h:493
PArrayObjects
An array of objects.
Definition: array.h:813
PSet::Clone
virtual PObject * Clone() const
Make a complete duplicate of the set.
Definition: dict.h:478
POrdinalDictionary::SetAt
virtual PBoolean SetAt(const K &key, PINDEX ordinal)
Add a new object to the collection.
Definition: dict.h:1129
POrdinalDictionary::RemoveAt
virtual PINDEX RemoveAt(const K &key)
Remove an object at the specified key.
Definition: dict.h:1142
PHashTableElement::data
PObject * data
Definition: dict.h:143
PSet::PSet
PSet(int dummy, const PSet *c)
Definition: dict.h:573
PCLASSINFO
#define PCLASSINFO(cls, par)
Declare all the standard PTLib class information.
Definition: object.h:1049
SetLastElementAt
PBoolean SetLastElementAt(PINDEX index, PHashTableElement *&lastElement)
POrdinalKey::Compare
virtual Comparison Compare(const PObject &obj) const
Compare the two objects and return their relative rank.
PDictionary::Contains
PBoolean Contains(const K &key) const
Determine if the value of the object is contained in the hash table.
Definition: dict.h:894
POrdinalDictionary::POrdinalDictionary
POrdinalDictionary()
Create a new, empty, dictionary.
Definition: dict.h:1052
POrdinalKey::HashFunction
virtual PINDEX HashFunction() const
This function calculates a hash table index value for the implementation of PSet and PDictionary clas...
PHashTable
friend class PHashTable
Definition: dict.h:167
POrdinalKey::POrdinalKey
PINLINE POrdinalKey(PINDEX newKey=0)
Create a new key for ordinal index values.
PDictionary
This template class maps the PAbstractDictionary to a specific key and data types.
Definition: dict.h:842
PHashTableElement::prev
PHashTableElement * prev
Definition: dict.h:145
PINLINE
#define PINLINE
Definition: object.h:127
AppendElement
PINDEX AppendElement(PObject *key, PObject *data)
PObject::Comparison
Comparison
Result of the comparison operation performed by the Compare() function.
Definition: object.h:1184
PAbstractDictionary
An abstract dictionary container.
Definition: dict.h:626
POrdinalKey::operator--
PINLINE PINDEX operator--()
Operator to pre-decrement the ordinal.
POrdinalKey::operator-=
PINLINE POrdinalKey & operator-=(PINDEX)
Operator to subtract from the ordinal.
Element
PHashTableElement Element
Definition: dict.h:166
POrdinalDictionary::GetKeyAt
const K & GetKeyAt(PINDEX index) const
Get the key in the dictionary at the ordinal index position.
Definition: dict.h:1157
PSet::operator[]
PBoolean operator[](const T &key) const
Determine if the value of the object is contained in the set.
Definition: dict.h:550
PDictionary::operator[]
D & operator[](const K &key) const
Get the object contained in the dictionary at the key position.
Definition: dict.h:881
PHashTable::Element
PHashTableElement Element
Definition: dict.h:277
PHashTableElement
Definition: dict.h:140
array.h
GetElementsIndex
PINDEX GetElementsIndex(const PObject *obj, PBoolean byVal, PBoolean keys) const
PHashTable::Table
PHashTableInfo Table
Definition: dict.h:278
PBoolean
BOOL PBoolean
Definition: object.h:102
PHashTableElement::key
PObject * key
Definition: dict.h:142
POrdinalDictionary::POrdinalDictionary
POrdinalDictionary(int dummy, const POrdinalDictionary *c)
Definition: dict.h:1180
PDictionary::GetAt
virtual D * GetAt(const K &key) const
Get the object at the specified key position.
Definition: dict.h:938
PDictionary::PDictionary
PDictionary(int dummy, const PDictionary *c)
Definition: dict.h:987
PAbstractSet
Abstract set of PObjects.
Definition: dict.h:287
PDECLARE_POOL_ALLOCATOR
#define PDECLARE_POOL_ALLOCATOR()
Definition: object.h:1025
POrdinalDictionary::Contains
PBoolean Contains(const K &key) const
Determine if the value of the object is contained in the hash table.
Definition: dict.h:1091
PAbstractDictionary::SetDataAt
virtual PBoolean SetDataAt(PINDEX index, PObject *obj)
Set the data at the specified ordinal index position in the dictionary.
POrdinalDictionary::GetAt
virtual POrdinalKey * GetAt(const K &key) const
Definition: dict.h:1095
POrdinalKey::operator++
PINLINE PINDEX operator++()
Operator to pre-increment the ordinal.
PDECLARE_BASEARRAY
#define PDECLARE_BASEARRAY(cls, T)
Begin a declaration of an array of base types.
Definition: array.h:474
PSet
This template class maps the PAbstractSet to a specific object type.
Definition: dict.h:455
PDECLARE_SET
#define PDECLARE_SET(cls, T, initDelObj)
Begin declaration of a set class.
Definition: dict.h:604
PAbstractSet
friend class PAbstractSet
Definition: dict.h:168
PHashTable
The hash table class is the basis for implementing the PSet and PDictionary classes.
Definition: dict.h:182
PDictionary::GetKeyAt
const K & GetKeyAt(PINDEX index) const
Get the key in the dictionary at the ordinal index position.
Definition: dict.h:953
PContainerReference::deleteObjects
bool deleteObjects
Definition: contain.h:72
PCONTAINERINFO
#define PCONTAINERINFO(cls, par)
Macro to declare funtions required in a container.
Definition: contain.h:343
PSet::operator+=
PSet & operator+=(const T &obj)
Include the specified objects value into the set.
Definition: dict.h:504
PDictionary::Clone
virtual PObject * Clone() const
Make a complete duplicate of the dictionary.
Definition: dict.h:865
PDictionary::value_type
std::pair< K, D * > value_type
Definition: dict.h:984
POrdinalKey::Clone
virtual PObject * Clone() const
Create a duplicate of the POrdinalKey.
PSet::Exclude
void Exclude(const T *obj)
Remove the object from the set.
Definition: dict.h:515
POrdinalDictionary::Clone
virtual PObject * Clone() const
Make a complete duplicate of the dictionary.
Definition: dict.h:1062
PSet::operator-=
PSet & operator-=(const T &obj)
Remove the objects value from the set.
Definition: dict.h:526
POrdinalDictionary::GetDataAt
PINDEX GetDataAt(PINDEX index) const
Get the data in the dictionary at the ordinal index position.
Definition: dict.h:1173
PSet::PSet
PSet(PBoolean initialDeleteObjects=false)
Create a new, empty, dictionary.
Definition: dict.h:469
deleteKeys
PBoolean deleteKeys
Definition: dict.h:164
GetElementAt
PHashTableElement * GetElementAt(const PObject &key)
POrdinalKey::operator+=
PINLINE POrdinalKey & operator+=(PINDEX)
Operator to add the ordinal.
POrdinalKey::PrintOn
virtual void PrintOn(ostream &strm) const
Output the ordinal index to the specified stream.
PDictionary::SetAt
virtual PBoolean SetAt(const K &key, D *obj)
Add a new object to the collection.
Definition: dict.h:927
PArray
This template class maps the PArrayObjects to a specific object type.
Definition: array.h:1024
POrdinalDictionary::operator[]
PINDEX operator[](const K &key) const
Get the object contained in the dictionary at the key position.
Definition: dict.h:1078
POrdinalKey::operator=
PINLINE POrdinalKey & operator=(PINDEX)
Operator to assign the ordinal.
PDictionary::GetDataAt
D & GetDataAt(PINDEX index) const
Get the data in the dictionary at the ordinal index position.
Definition: dict.h:969
POrdinalDictionary::SetDataAt
virtual PBoolean SetDataAt(PINDEX index, PINDEX ordinal)
Set the data at the specified ordinal index position in the dictionary.
Definition: dict.h:1113
PDictionary::RemoveAt
virtual D * RemoveAt(const K &key)
Remove an object at the specified key.
Definition: dict.h:909
PContainer::reference
PContainerReference * reference
Definition: contain.h:291
RemoveElement
PObject * RemoveElement(const PObject &key)
POrdinalDictionary
This template class maps the PAbstractDictionary to a specific key type and a POrdinalKey data type...
Definition: dict.h:1039
PObject
Ultimate parent class for all objects in the class library.
Definition: object.h:1118
PCollection
A collection is a container that collects together descendents of the PObject class.
Definition: contain.h:395
PSet::GetKeyAt
virtual const T & GetKeyAt(PINDEX index) const
Get the key in the set at the ordinal index position.
Definition: dict.h:565
PSet::Contains
PBoolean Contains(const T &key) const
Determine if the value of the object is contained in the set.
Definition: dict.h:538
PDictionary::PDictionary
PDictionary()
Create a new, empty, dictionary.
Definition: dict.h:855
PHashTableElement::next
PHashTableElement * next
Definition: dict.h:144
PHashTable::hashTable
PHashTableInfo * hashTable
Definition: dict.h:279
PNEW
#define PNEW
Macro for overriding system default new operator.
Definition: object.h:890
POrdinalKey
This class is used when an ordinal index value is the key for PSet and PDictionary classes...
Definition: dict.h:50