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: 24846 $
 * $Author: rjongbloed $
 * $Date: 2010-10-30 00:09:31 -0500 (Sat, 30 Oct 2010) $
 */


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


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



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

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

    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 ///////////////////////////////////////////////////////////////

---