dict.h

Go to the documentation of this file.

/*
 * dict.h
 *
 * Dictionary (hash table) Container classes.
 *
 * Portable Windows 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): ______________________________________.
 *
 * $Log: dict.h,v $
 * Revision 1.38  2007/08/01 05:20:48  rjongbloed
 * Changes to container classes to become compatible with advanced DevStudio 2005 "Visualizers".
 *
 * Revision 1.37  2006/06/30 00:56:31  csoutheren
 * Applied 1494931 - various pwlib bug fixes and enhancement
 * Thanks to Frederich Heem
 *
 * Revision 1.36  2006/06/21 03:28:41  csoutheren
 * Various cleanups thanks for Frederic Heem
 *
 * Revision 1.35  2005/11/25 03:43:47  csoutheren
 * Fixed function argument comments to be compatible with Doxygen
 *
 * Revision 1.34  2004/11/23 11:33:08  csoutheren
 * Fixed problem with RemoveAt returning invalid pointer in some cases,
 * and added extra documentation on this case.
 * Thanks to Diego Tartara for pointing out this potential problem
 *
 * Revision 1.33  2004/04/09 03:42:34  csoutheren
 * Removed all usages of "virtual inline" and "inline virtual"
 *
 * Revision 1.32  2004/04/03 23:53:09  csoutheren
 * Added various changes to improce compatibility with the Sun Forte compiler
 *   Thanks to Brian Cameron
 * Added detection of readdir_r version
 *
 * Revision 1.31  2003/09/17 01:18:02  csoutheren
 * Removed recursive include file system and removed all references
 * to deprecated coooperative threading support
 *
 * Revision 1.30  2003/03/31 01:23:56  robertj
 * Added ReadFrom functions for standard container classes such as
 *   PIntArray and PStringList etc
 *
 * Revision 1.29  2002/10/04 01:47:29  robertj
 * Added various increment and decrement operators to POrdinalKey.
 *
 * Revision 1.28  2002/09/16 01:08:59  robertj
 * Added #define so can select if #pragma interface/implementation is used on
 *   platform basis (eg MacOS) rather than compiler, thanks Robert Monaghan.
 *
 * Revision 1.27  2002/06/14 13:22:12  robertj
 * Fixed ability to remove elements from a PSet by value.
 * Added by value add and remove functions to a PSet.
 * Added a POrdinalSet class.
 * Fixed some documentation.
 *
 * Revision 1.26  2002/02/06 00:53:25  robertj
 * Fixed missing const on PSet::Contains and operator[], thanks Francisco Olarte Sanz
 *
 * Revision 1.25  1999/11/30 00:22:54  robertj
 * Updated documentation for doc++
 *
 * Revision 1.24  1999/08/22 12:13:43  robertj
 * Fixed warning when using inlines on older GNU compiler
 *
 * Revision 1.23  1999/03/09 02:59:49  robertj
 * Changed comments to doc++ compatible documentation.
 *
 * Revision 1.22  1999/02/16 08:07:11  robertj
 * MSVC 6.0 compatibility changes.
 *
 * Revision 1.21  1998/09/23 06:20:27  robertj
 * Added open source copyright license.
 *
 * Revision 1.20  1998/01/05 10:39:34  robertj
 * Fixed "typesafe" templates/macros for dictionaries, especially on GNU.
 *
 * Revision 1.19  1997/12/11 10:27:16  robertj
 * Added type correct Contains() function to dictionaries.
 *
 * Revision 1.18  1997/07/08 13:15:05  robertj
 * DLL support.
 *
 * Revision 1.17  1997/06/08 04:49:11  robertj
 * Fixed non-template class descendent order.
 *
 * Revision 1.16  1996/08/17 10:00:22  robertj
 * Changes for Windows DLL support.
 *
 * Revision 1.15  1996/03/31 08:44:10  robertj
 * Added RemoveAt() function to remove entries from dictionaries.
 *
 * Revision 1.14  1996/02/08 11:50:01  robertj
 * Moved Contains function from PSet to PHashTable so available for dictionaries.
 * Added print for dictionaries key=data\n.
 * Added GetAt(PINDEX) to template classes to make identical to macro.
 *
 * Revision 1.13  1996/02/03 11:00:28  robertj
 * Temporary removal of SetAt() and GetAt() functions in dictionary macro.
 *
 * Revision 1.12  1996/01/24 14:43:11  robertj
 * Added initialisers to string dictionaries.
 *
 * Revision 1.11  1996/01/23 13:11:12  robertj
 * Mac Metrowerks compiler support.
 *
 * Revision 1.10  1995/06/17 11:12:29  robertj
 * Documentation update.
 *
 * Revision 1.9  1995/06/04 08:45:57  robertj
 * Better C++ compatibility (with BC++)
 *
 * Revision 1.8  1995/03/14 12:41:19  robertj
 * Updated documentation to use HTML codes.
 *
 * Revision 1.7  1995/02/22  10:50:29  robertj
 * Changes required for compiling release (optimised) version.
 *
 * Revision 1.6  1995/02/11  04:10:35  robertj
 * Fixed dictionary MACRO for templates.
 *
 * Revision 1.5  1995/02/05  00:48:03  robertj
 * Fixed template version.
 *
 * Revision 1.4  1995/01/09  12:35:31  robertj
 * Removed unnecesary return value from I/O functions.
 * Changes due to Mac port.
 *
 * Revision 1.3  1994/12/21  11:52:51  robertj
 * Documentation and variable normalisation.
 *
 * Revision 1.2  1994/12/17  01:36:57  robertj
 * Fixed memory leak in PStringSet
 *
 * Revision 1.1  1994/12/12  09:59:32  robertj
 * Initial revision
 *
 */


#ifndef __DICT_H__
#define __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, #EqualTo# for same,
       #LessThan# for #obj# logically less than the
       object and #GreaterThan# for #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_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);
    BOOL SetLastElementAt(PINDEX index);
    PHashTableElement * GetElementAt(const PObject & key);
    PINDEX GetElementsIndex(const PObject*obj,BOOL byVal,BOOL keys) const;

    PINDEX lastIndex;
    PINDEX lastBucket;
    PHashTableElement * lastElement;

    BOOL 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;


  protected:
    virtual BOOL SetSize(
      PINDEX newSize  
    );


    PINLINE BOOL 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 BOOL Remove(
      const PObject * obj   
    );

    virtual PObject * RemoveAt(
      PINDEX index   
    );

    virtual PObject * GetAt(
      PINDEX index  
    ) const;

    virtual BOOL SetAt(
      PINDEX index,   
      PObject * val   
    );

    virtual PINDEX GetObjectsIndex(
      const PObject * obj   
    ) const;

    virtual PINDEX GetValuesIndex(
      const PObject & obj   
    ) const;
};


#ifdef PHAS_TEMPLATES

template <class T> class PSet : public PAbstractSet
{
  PCLASSINFO(PSet, PAbstractSet);

  public:
    inline PSet(BOOL 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; }

    BOOL Contains(
      const T & key  
    ) const { return AbstractContains(key); }

    BOOL 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) \
  PSET(cls##_PTemplate, T); \
  PDECLARE_CLASS(cls, cls##_PTemplate) \
  protected: \
    cls(int dummy, const cls * c) \
      : cls##_PTemplate(dummy, c) { } \
  public: \
    cls(BOOL initialDeleteObjects = initDelObj) \
      : cls##_PTemplate(initialDeleteObjects) { } \
    virtual PObject * Clone() const \
      { return PNEW cls(0, this); } \


#else // PHAS_TEMPLATES


#define PSET(cls, K) \
  class cls : public PAbstractSet { \
  PCLASSINFO(cls, PAbstractSet); \
  protected: \
    inline cls(int dummy, const cls * c) \
      : PAbstractSet(dummy, c) \
      { reference->deleteObjects = c->reference->deleteObjects; } \
  public: \
    inline cls(BOOL initialDeleteObjects = FALSE) \
      : PAbstractSet() { AllowDeleteObjects(initialDeleteObjects); } \
    virtual PObject * Clone() const \
      { return PNEW cls(0, this); } \
    inline void Include(const PObject * key) \
      { Append((PObject *)key); } \
    inline void Exclude(const PObject * key) \
      { Remove(key); } \
    inline BOOL operator[](const K & key) const \
        { return AbstractContains(key); } \
    inline BOOL Contains(const K & key) const \
        { return AbstractContains(key); } \
    virtual const K & GetKeyAt(PINDEX index) const \
      { return (const K &)AbstractGetKeyAt(index); } \
  }

#define PDECLARE_SET(cls, K, initDelObj) \
 PSET(cls##_PTemplate, K); \
 PDECLARE_CLASS(cls, cls##_PTemplate) \
  protected: \
    inline cls(int dummy, const cls * c) \
      : cls##_PTemplate(dummy, c) { } \
  public: \
    inline cls(BOOL initialDeleteObjects = initDelObj) \
      : cls##_PTemplate() { AllowDeleteObjects(initialDeleteObjects); } \
    virtual PObject * Clone() const \
      { return PNEW cls(0, this); } \


#endif  // PHAS_TEMPLATES


PSET(POrdinalSet, POrdinalKey);



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 BOOL 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 BOOL SetDataAt(
      PINDEX index,   
      PObject * obj   
    );

    virtual BOOL AbstractSetAt(
      const PObject & key,  
      PObject * obj         
    );

    virtual PObject & GetRefAt(
      const PObject & key   
    ) const;

    virtual PObject * AbstractGetAt(
      const PObject & key   
    ) const;

  protected:
    PINLINE PAbstractDictionary(int dummy, const PAbstractDictionary * c);

  private:
    virtual PINDEX Append(
      PObject * obj   // New object to place into the collection.
    );
    /* This function is meaningless and will assert.

       @return
       Always zero.
     */

    virtual BOOL Remove(
      const PObject * obj   // Existing object to remove from the collection.
    );
    /* Remove the object from the collection. If the AllowDeleteObjects option
       is set then the object is also deleted.

       Note that the comparison for searching for the object in collection is
       made by pointer, not by value. Thus the parameter must point to the
       same instance of the object that is in the collection.

       @return
       TRUE if the object was in the collection.
     */

};


#ifdef PHAS_TEMPLATES

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); }

    BOOL 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 BOOL 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); }

  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); }

    BOOL 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 BOOL SetDataAt(
      PINDEX index,   
      PINDEX ordinal  
      ) { return PAbstractDictionary::SetDataAt(index, PNEW POrdinalKey(ordinal)); }

    virtual BOOL 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); } \


#else // PHAS_TEMPLATES


#define PDICTIONARY(cls, K, D) \
  class cls : public PAbstractDictionary { \
  PCLASSINFO(cls, PAbstractDictionary); \
  protected: \
    inline cls(int dummy, const cls * c) \
      : PAbstractDictionary(dummy, c) { } \
  public: \
    cls() \
      : PAbstractDictionary() { } \
    virtual PObject * Clone() const \
      { return PNEW cls(0, this); } \
    D & operator[](const K & key) const \
      { return (D &)GetRefAt(key); } \
    virtual BOOL Contains(const K & key) const \
      { return AbstractContains(key); } \
    virtual D * RemoveAt(const K & key) \
      { D * obj = GetAt(key); AbstractSetAt(key, NULL); return obj; } \
    virtual BOOL SetAt(const K & key, D * obj) \
      { return AbstractSetAt(key, obj); } \
    virtual D * GetAt(const K & key) 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); } \
  }

#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); } \


#define PORDINAL_DICTIONARY(cls, K) \
  class cls : public PAbstractDictionary { \
  PCLASSINFO(cls, PAbstractDictionary); \
  protected: \
    inline cls(int dummy, const cls * c) \
      : PAbstractDictionary(dummy, c) { } \
  public: \
    inline cls() \
      : PAbstractDictionary() { } \
    virtual PObject * Clone() const \
      { return PNEW cls(0, this); } \
    inline PINDEX operator[](const K & key) const \
      { return (POrdinalKey &)GetRefAt(key); } \
    virtual BOOL Contains(const K & key) const \
      { return AbstractContains(key); } \
    virtual POrdinalKey * GetAt(const K & key) const \
      { return (POrdinalKey *)AbstractGetAt(key); } \
    virtual BOOL SetDataAt(PINDEX index, PINDEX ordinal) \
      { return PAbstractDictionary::SetDataAt(index, PNEW POrdinalKey(ordinal)); } \
    virtual BOOL 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; } \
    inline const K & GetKeyAt(PINDEX index) const \
      { return (const K &)AbstractGetKeyAt(index); } \
    inline PINDEX GetDataAt(PINDEX index) const \
      { return (POrdinalKey &)AbstractGetDataAt(index); } \
  }

#define PDECLARE_ORDINAL_DICTIONARY(cls, K) \
  PORDINAL_DICTIONARY(cls##_PTemplate, K); \
  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); } \


#endif // PHAS_TEMPLATES

#endif // #ifndef __DICT_H__

// End Of File ///////////////////////////////////////////////////////////////

---