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): ______________________________________.
 *
 * $Revision: 19008 $
 * $Author: rjongbloed $
 * $Date: 2007-11-29 09:17:41 +0000 (Thu, 29 Nov 2007) $
 */


#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);
    PBoolean SetLastElementAt(PINDEX index);
    PHashTableElement * GetElementAt(const PObject & key);
    PINDEX GetElementsIndex(const PObject*obj,PBoolean byVal,PBoolean keys) const;

    PINDEX lastIndex;
    PINDEX lastBucket;
    PHashTableElement * lastElement;

    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;


  protected:
    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;
};


#ifdef PHAS_TEMPLATES

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

  public:
    inline PSet(PBoolean initialDeleteObjects = PFalse)
      : 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) \
  PSET(cls##_PTemplate, T); \
  PDECLARE_CLASS(cls, cls##_PTemplate) \
  protected: \
    cls(int dummy, const cls * c) \
      : cls##_PTemplate(dummy, c) { } \
  public: \
    cls(PBoolean 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(PBoolean initialDeleteObjects = PFalse) \
      : 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 PBoolean operator[](const K & key) const \
        { return AbstractContains(key); } \
    inline PBoolean 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(PBoolean 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 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;

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

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

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


#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 PBoolean Contains(const K & key) const \
      { return AbstractContains(key); } \
    virtual D * RemoveAt(const K & key) \
      { D * obj = GetAt(key); AbstractSetAt(key, NULL); return obj; } \
    virtual PBoolean 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 PBoolean Contains(const K & key) const \
      { return AbstractContains(key); } \
    virtual POrdinalKey * GetAt(const K & key) const \
      { return (POrdinalKey *)AbstractGetAt(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; } \
    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 ///////////////////////////////////////////////////////////////

---