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): ______________________________________.
 */


#ifndef PTLIB_DICT_H
#define PTLIB_DICT_H

#ifdef P_USE_PRAGMA
#pragma interface
#endif

#include <ptlib/array.h>

// PDictionary classes

template <typename T>
class PKey : public PObject
{
    PCLASSINFO(PKey, PObject);
  public:
    typedef T value_type;
    typedef PKey<T> my_type;

    PINLINE PKey(
      value_type newKey = 0   
    ) : m_key(newKey) { }

    PINLINE PKey & operator=(value_type newKey)
    { this->m_key = newKey; return *this; }

    virtual PObject * Clone() const { return new PKey(this->m_key); }

    /* 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
    {
      return Compare2(this->m_key, dynamic_cast<const my_type &>(obj).m_key);
    }

    virtual PINDEX HashFunction() const
    {
#if PINDEX_SIGNED
      return std::abs((PINDEX)this->m_key)%23;
#else
      return ((PINDEX)this->m_key)%23;
#endif
    }

    virtual void PrintOn(ostream & strm) const { strm << this->m_key; }

    PINLINE operator value_type() const  { return this->m_key; }

    PINLINE value_type operator++() { return ++this->m_key; }

    PINLINE value_type operator++(int) { return this->m_key++; }

    PINLINE value_type operator--() { return --this->m_key; }

    PINLINE value_type operator--(int) { return this->m_key--; }

    PINLINE PKey & operator+=(value_type add) { this->m_key += add; return *this; }

    PINLINE PKey & operator-=(value_type minus) { this->m_key -= minus; return *this; }

  private:
    value_type m_key;
};

typedef PKey<PINDEX> POrdinalKey;



// Member variables
struct PHashTableElement
{
    PObject           * m_key;
    PObject           * m_data;
    PHashTableElement * m_next;
    PHashTableElement * m_prev;
    PINDEX              m_bucket;

    PDECLARE_POOL_ALLOCATOR(PHashTableElement);
};

P_PUSH_MSVC_WARNINGS(26495)
struct PHashTableList
{
  PHashTableList()
    : m_head(NULL)
    , m_tail(NULL)
#if PTRACING
    , m_size(0)
#endif
  { }
  PHashTableElement * m_head;
  PHashTableElement * m_tail;
#if PTRACING
  PINDEX              m_size;
#endif
};
P_POP_MSVC_WARNINGS()
__inline std::ostream & operator<<(std::ostream & strm, const PHashTableList & hash) { return strm << (void *)hash.m_head; }

class PHashTable;


class PHashTableInfo : public PBaseArray<PHashTableList>
{
    typedef PBaseArray<PHashTableList> ParentClass;
    PCLASSINFO(PCharArray, ParentClass);
  public:
    PHashTableInfo(PINDEX initialSize = 0)
      : ParentClass(initialSize), deleteKeys(true) { }
    PHashTableInfo(PHashTableList const * buffer, PINDEX length, PBoolean dynamic = true)
      : ParentClass(buffer, length, dynamic), deleteKeys(true) { }
    virtual PObject * Clone() const { return PNEW PHashTableInfo(*this, GetSize()); }
    virtual ~PHashTableInfo() { Destruct(); }
    virtual void DestroyContents();

    void AppendElement(PObject * key, PObject * data PTRACE_PARAM(, PHashTable * owner));
    PObject * RemoveElement(const PObject & key);
    PHashTableElement * GetElementAt(PINDEX index);
    PHashTableElement * GetElementAt(const PObject & key);
    PINDEX GetElementsIndex(const PObject*obj,PBoolean byVal,PBoolean keys) const;
    PHashTableElement * NextElement(PHashTableElement * element) const;
    PHashTableElement * PrevElement(PHashTableElement * element) const;

    bool deleteKeys;
    PTRACE_THROTTLE(m_throttlePoorHashFunction, 1);

  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;

    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() { this->AllowDeleteObjects(initialDeleteObjects); }

    virtual PObject * Clone() const
      { return PNEW PSet(0, this); }

    void Include(
      const T * obj   // New object to include in the set.
    ) { this->Append((PObject *)obj); }

    PSet & operator+=(
      const T & obj   // New object to include in the set.
    ) { this->Append(obj.Clone()); return *this; }

    void Exclude(
      const T * obj   // New object to exclude in the set.
    ) { this->Remove(obj); }

    PSet & operator-=(
      const T & obj   // New object to exclude in the set.
    ) { this->erase(this->find(obj)); return *this; }

    PBoolean Contains(
      const T & key  
    ) const { return this->AbstractContains(key); }

    PBoolean operator[](
      const T & key  
    ) const { return this->AbstractContains(key); }

    virtual const T & GetKeyAt(
      PINDEX index    
    ) const
      { return dynamic_cast<const T &>(this->AbstractGetKeyAt(index)); }

    class iterator;
    class const_iterator;
    class iterator_base : public std::iterator<std::forward_iterator_tag, T> {
      protected:
        iterator_base()
          : table(NULL)
          , element(NULL)
          { }
        iterator_base(PHashTableInfo * t)
          : table(t)
          , element(t->GetElementAt((PINDEX)0))
          { }
        iterator_base(PHashTableInfo * t, const T & k)
          : table(t)
          , element(t->GetElementAt(k))
          { }

        PHashTableInfo    * table;
        PHashTableElement * element;

        void Next() { this->element = PAssertNULL(this->table)->NextElement(this->element); }
        void Prev() { this->element = PAssertNULL(this->table)->PrevElement(this->element); }

        T * Ptr() const { return dynamic_cast<T *>(PAssertNULL(this->element)->m_key); }

      public:
        bool operator==(const iterator_base & it) const { return this->element == it.element; }
        bool operator!=(const iterator_base & it) const { return this->element != it.element; }
    };

    class iterator : public iterator_base  {
      protected:
        iterator(PHashTableInfo * t) : iterator_base(t) { }
        iterator(PHashTableInfo * t, const T & k) : iterator_base(t, k) { }

      public:
        iterator() { }

        iterator operator++()    {                      this->Next(); return *this; }
        iterator operator--()    {                      this->Prev(); return *this; }
        iterator operator++(int) { iterator it = *this; this->Next(); return it;    }
        iterator operator--(int) { iterator it = *this; this->Prev(); return it;    }

        T * operator->() const { return  this->Ptr(); }
        T & operator* () const { return *this->Ptr(); }

      friend class PSet<T>;
    };

    iterator begin() { return iterator(this->hashTable); }
    iterator end()   { return iterator(); }
    iterator find(const T & k) { return iterator(this->hashTable, k); }


    class const_iterator : public iterator_base {
      protected:
        const_iterator(PHashTableInfo * t) : iterator_base(t) { }
        const_iterator(PHashTableInfo * t, const T & k) : iterator_base(t, k) { }

      public:
        const_iterator() { }

        const_iterator operator++()    {                            this->Next(); return *this; }
        const_iterator operator--()    {                            this->Prev(); return *this; }
        const_iterator operator++(int) { const_iterator it = *this; this->Next(); return it;    }
        const_iterator operator--(int) { const_iterator it = *this; this->Prev(); return it;    }

        const T * operator->() const { return  this->Ptr(); }
        const T & operator* () const { return *this->Ptr(); }

      friend class PSet<T>;
    };

    const_iterator begin() const { return const_iterator(this->hashTable); }
    const_iterator end()   const { return const_iterator(); }
    const_iterator find(const T & k) const { return const_iterator(this->hashTable, k); }

    void erase(const iterator & it) { this->Remove(&*it); }
    void erase(const const_iterator & it) { this->Remove(&*it); }

  protected:
    PSet(int dummy, const PSet * c)
      : PAbstractSet(dummy, c)
      { this->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;


    P_DEPRECATED virtual PBoolean SetDataAt(
      PINDEX index,   
      PObject * obj   
    );

    virtual PObject * 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:
    typedef K key_type;
    typedef D data_type;
    typedef PDictionary<K, D> dict_type;

    PDictionary()
      : PAbstractDictionary() { }

    virtual PObject * Clone() const
      { return PNEW PDictionary(0, this); }

    const D & operator[](
      const K & key   
    ) const { return dynamic_cast<const D &>(this->GetRefAt(key)); }
    D & operator[](
      const K & key   
    ) { return dynamic_cast<D &>(this->GetRefAt(key)); }

    PBoolean Contains(
      const K & key   
    ) const { return this->AbstractContains(key); }

    virtual D * RemoveAt(
      const K & key   
    ) { return dynamic_cast<D *>(this->AbstractSetAt(key, NULL)); }

    virtual PBoolean SetAt(
      const K & key,  // Key for position in dictionary to add object.
      D * obj         // New object to put into the dictionary.
    ) { return this->AbstractSetAt(key, obj) != NULL; }

    virtual D * GetAt(
      const K & key   // Key for position in dictionary to get object.
    ) const { return dynamic_cast<D *>(this->AbstractGetAt(key)); }

    const K & GetKeyAt(
      PINDEX index  
    ) const
      { return dynamic_cast<const K &>(this->AbstractGetKeyAt(index)); }

    D & GetDataAt(
      PINDEX index  
    ) const
      { return dynamic_cast<D &>(this->AbstractGetDataAt(index)); }

    PArray<K> GetKeys() const
    {
      PArray<K> keys;
      this->AbstractGetKeys(keys);
      return keys;
    }

    class iterator;
    class const_iterator;
    class iterator_base {
      protected:
        K * m_internal_first;  // Must be first two members
        D * m_internal_second;

        PHashTableInfo    * m_table;
        PHashTableElement * m_element;

        iterator_base()
          : m_internal_first(NULL)
          , m_internal_second(NULL)
          , m_table(NULL)
          , m_element(NULL)
        {
        }

        iterator_base(const dict_type * dict)
          : m_table(dict->hashTable)
        {
          this->SetElement(this->m_table->GetElementAt((PINDEX)0));
        }
        
        iterator_base(const dict_type * dict, const K & key)
          : m_table(dict->hashTable)
        {
          this->SetElement(this->m_table->GetElementAt(key));
        }

        void SetElement(PHashTableElement * element)
        {
          this->m_element = element;
          if (element != NULL) {
            this->m_internal_first  = dynamic_cast<K *>(element->m_key);
            this->m_internal_second = dynamic_cast<D *>(element->m_data);
          }
          else {
            this->m_internal_first = NULL;
            this->m_internal_second = NULL;
          }
        }

        P_PUSH_MSVC_WARNINGS(6011)
        void Next() { this->SetElement(PAssertNULL(this->m_table)->NextElement(this->m_element)); }
        void Prev() { this->SetElement(PAssertNULL(this->m_table)->PrevElement(this->m_element)); }
        P_POP_MSVC_WARNINGS()

      public:
        bool operator==(const iterator_base & it) const { return this->m_element == it.m_element; }
        bool operator!=(const iterator_base & it) const { return this->m_element != it.m_element; }
    };

    template<class CK, class CD>
    class iterator_pair {
      public:
        CK & first;
        CD & second;

      private:
        iterator_pair() : first(reinterpret_cast<CK&>(0)), second(reinterpret_cast<CD&>(0)) { }
    };

    class iterator : public iterator_base, public std::iterator<std::forward_iterator_tag, iterator_pair<K,D> > {
      protected:
        iterator(dict_type * dict) : iterator_base(dict) { }
        iterator(dict_type * dict, const K & key) : iterator_base(dict, key) { }

      public:
        iterator() { }

        iterator operator++()    {                      this->Next(); return *this; }
        iterator operator--()    {                      this->Prev(); return *this; }
        iterator operator++(int) { iterator it = *this; this->Next(); return it;    }
        iterator operator--(int) { iterator it = *this; this->Prev(); return it;    }

        typedef iterator_pair<K,D> pair;
        const pair * operator->() const { return  reinterpret_cast<const pair *>(this); }
        const pair & operator* () const { return *reinterpret_cast<const pair *>(this); }

      friend class PDictionary<K, D>;
    };

    iterator begin() { return iterator(this); }
    iterator end()   { return iterator(); }
    iterator find(const K & key) { return iterator(this, key); }


    class const_iterator : public iterator_base, public std::iterator<std::forward_iterator_tag, iterator_pair<const K,const D> > {
      protected:
        const_iterator(const dict_type * dict) : iterator_base(dict) { }
        const_iterator(const dict_type * dict, const K & key) : iterator_base(dict, key) { }

      public:
        const_iterator() { }
        const_iterator(iterator it) : iterator_base(it) { }

        const_iterator operator++()    {                            this->Next(); return *this; }
        const_iterator operator--()    {                            this->Prev(); return *this; }
        const_iterator operator++(int) { const_iterator it = *this; this->Next(); return it;    }
        const_iterator operator--(int) { const_iterator it = *this; this->Prev(); return it;    }

        typedef iterator_pair<const K, const D> pair;
        const pair * operator->() const { return  reinterpret_cast<const pair *>(this); }
        const pair & operator* () const { return *reinterpret_cast<const pair *>(this); }

      friend class PDictionary<K, D>;
    };

    const_iterator begin() const { return const_iterator(this); }
    const_iterator end()   const { return const_iterator(); }
    const_iterator find(const K & k) const { return const_iterator(this, k); }

    void erase(const       iterator & it) { this->AbstractSetAt(*it.m_element->m_key, NULL); }
    void erase(const const_iterator & it) { this->AbstractSetAt(*it.m_element->m_key, NULL); }

  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 PDictionary<K, POrdinalKey>
{
  typedef PDictionary<K, POrdinalKey> ParentClass;
  PCLASSINFO(POrdinalDictionary, ParentClass);

  public:
    POrdinalDictionary()
      : ParentClass() { }

    virtual PObject * Clone() const
      { return PNEW POrdinalDictionary(0, this); }

    PINDEX operator[](
      const K & key   // Key to look for in the dictionary.
    ) const
      { return dynamic_cast<POrdinalKey &>(this->GetRefAt(key)); }

    virtual PBoolean SetDataAt(
      PINDEX index,   
      PINDEX ordinal  
    ) { return this->AbstractSetAt(this->AbstractGetKeyAt(index), PNEW POrdinalKey(ordinal)) != NULL; }

    virtual PBoolean SetAt(
      const K & key,  
      PINDEX ordinal  
    ) { return this->AbstractSetAt(key, PNEW POrdinalKey(ordinal)) != NULL; }

    const K & GetKeyAt(
      PINDEX index  
    ) const
      { return dynamic_cast<const K &>(this->AbstractGetKeyAt(index)); }

    PINDEX GetDataAt(
      PINDEX index  
    ) const
      { return dynamic_cast<POrdinalKey &>(this->AbstractGetDataAt(index)); }

  protected:
    POrdinalDictionary(int dummy, const POrdinalDictionary * c)
      : ParentClass(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 ///////////////////////////////////////////////////////////////