path: root/src/sortdict.h

/******************************************************************************
 *
 * 
 *
 *
 * Copyright (C) 1997-2015 by Dimitri van Heesch.
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation under the terms of the GNU General Public License is hereby 
 * granted. No representations are made about the suitability of this software 
 * for any purpose. It is provided "as is" without express or implied warranty.
 * See the GNU General Public License for more details.
 *
 * Documents produced by Doxygen are derivative works derived from the
 * input used in their production; they are not affected by this license.
 *
 */

#ifndef _SORTDICT_H
#define _SORTDICT_H

#include <qlist.h>
#include <qdict.h>
#include <qintdict.h>

#define AUTORESIZE 1

#if AUTORESIZE
const uint SDict_primes[] = 
{
  17,
  29,
  47,
  71,
  113,
  179,
  293,
  457,
  733,
  1171,
  1871,
  2999,
  4787,
  7669,
  12251,
  19603,
  31379,
  50177,
  80287,
  128449,
  205519,
  328829,
  526139,
  841801,
  1346881,
  2155007,
  3448033,
  5516827,
  8826919,
  14123059,
  23538433,
  39230771,
  65384537,
  108974231,
  181623707,
  302706181,
  504510283,
  840850487,
  0xffffffff
};
#endif

template<class T> class SDict;
template<class T> class SIntDict;

/** internal wrapper class that redirects compareValues() to the 
 *  dictionary 
 */
template<class T>
class SList : public QList<T>
{
  public:
    SList(SDict<T> *owner) : m_owner(owner) {}
    virtual ~SList() {}
    int compareValues(const T *item1,const T *item2) const
    {
      return m_owner->compareValues(item1,item2);
    }
  private:
    SDict<T> *m_owner;  
};

/** Ordered dictionary of elements of type T. 
 *  Internally uses a QList<T> and a QDict<T>.
 */
template<class T>
class SDict 
{
  private:
    SList<T> *m_list;
    QDict<T> *m_dict;
    int m_sizeIndex;
    
  public:
    /*! Create an ordered dictionary.
     *  \param size The size of the dictionary. Should be a prime number for
     *              best distribution of elements.
     *  \param caseSensitive indicated whether the keys should be sorted
     *         in a case sensitive way.
     */
    SDict(int size=17,bool caseSensitive=TRUE) : m_sizeIndex(0)
    {
      m_list = new SList<T>(this);
#if AUTORESIZE
      while ((uint)size>SDict_primes[m_sizeIndex]) m_sizeIndex++;
      m_dict = new QDict<T>(SDict_primes[m_sizeIndex],caseSensitive);
#else
      m_dict = new QDict<T>(size,caseSensitive);
#endif
    }

    /*! Destroys the dictionary */
    virtual ~SDict() 
    {
      delete m_list;
      delete m_dict;
    }

    /*! Appends an element to the dictionary. The element is owned by the
     *  dictionary.
     *  \param key The unique key to use to quickly find the item later on.
     *  \param d The compound to add.
     *  \sa find()
     */
    void append(const char *key,const T *d)
    {
      m_list->append(d);
      m_dict->insert(key,d);
#if AUTORESIZE
      if (m_dict->size()>SDict_primes[m_sizeIndex])
      {
        m_dict->resize(SDict_primes[++m_sizeIndex]);
      }
#endif
    }

    /*! Prepends an element to the dictionary. The element is owned by the
     *  dictionary.
     *  \param key The unique key to use to quickly find the item later on.
     *  \param d The compound to add.
     *  \sa find()
     */
    void prepend(const char *key,const T *d)
    {
      m_list->prepend(d);
      m_dict->insert(key,d);
#if AUTORESIZE
      if (m_dict->size()>SDict_primes[m_sizeIndex])
      {
        m_dict->resize(SDict_primes[++m_sizeIndex]);
      }
#endif
    }

    /*! Remove an item from the dictionary */
    bool remove(const char *key)
    {
      T *item = m_dict->take(key);
      return item ? m_list->remove(item) : FALSE;
    }

    /*! Take an item out of the dictionary without deleting it */
    T *take(const char *key)
    {
      T *item = m_dict->take(key);
      if (item)
      {
        int i = m_list->find(item);
        m_list->take(i);
      }
      return item;
    }

    /*! Sorts the members of the dictionary. First appending a number
     *  of members and then sorting them is faster (O(NlogN) than using 
     *  inSort() for each member (O(N^2)).
     */
    void sort()
    {
      m_list->sort();
    }
    /*! Inserts a compound into the dictionary in a sorted way.
     *  \param key The unique key to use to quickly find the item later on.
     *  \param d The compound to add.
     *  \sa find()
     */
    void inSort(const char *key,const T *d)
    {
      m_list->inSort(d);
      m_dict->insert(key,d);
#if AUTORESIZE
      if (m_dict->size()>SDict_primes[m_sizeIndex])
      {
        m_dict->resize(SDict_primes[++m_sizeIndex]);
      }
#endif
    }

    void insertAt(int i,const char *key,const T *d)
    {
      m_list->insert(i,d);
      m_dict->insert(key,d);
#if AUTORESIZE
      if (m_dict->size()>SDict_primes[m_sizeIndex])
      {
        m_dict->resize(SDict_primes[++m_sizeIndex]);
      }
#endif
    }

    /*! Indicates whether or not the dictionary owns its elements */
    void setAutoDelete(bool val)
    {
      m_list->setAutoDelete(val);
    }

    /*! Looks up a compound given its key. 
     *  \param key The key to identify this element.
     *  \return The requested compound or zero if it cannot be found.
     *  \sa append() 
     */
    T *find(const char *key)
    {
      return m_dict->find(key);
    }
    T *find(const QCString &key)
    {
      return m_dict->find(key);
    }
    int findAt(const QCString &key)
    {
      T *item = find(key);
      if (item==0) return -1;
      return m_list->find(item);
    }

    /*! Equivalent to find(). */
    T *operator[](const char *key) const
    {
      return m_dict->find(key);
    }

    /*! Returns the item at position \a i in the sorted dictionary */
    T *at(uint i)
    {
      return m_list->at(i);
    }

    /*! Function that is used to compare two items when sorting.
     *  Overload this to properly sort items.
     *  \sa inSort()
     */
    virtual int compareValues(const T *item1,const T *item2) const
    {
      return item1!=item2;
    }

    /*! Clears the dictionary. Will delete items if setAutoDelete() was
     *  set to \c TRUE.
     *  \sa setAutoDelete
     */
    void clear()
    {
      m_list->clear();
      m_dict->clear();
    }
    
    /*! Returns the number of items stored in the dictionary
     */
    int count() const
    {
      return m_list->count();
    }

    class Iterator;         // first forward declare
    friend class Iterator;  // then make it a friend
    /*! Simple iterator for SDict. It iterates in the order in which the
     *  elements are stored.
     */
    class Iterator
    {
      public:
        /*! Create an iterator given the dictionary. */
        Iterator(const SDict<T> &dict)
        {
          m_li = new QListIterator<T>(*dict.m_list);
        }

        /*! Destroys the dictionary */
        virtual ~Iterator()
        {
          delete m_li;
        }

        /*! Set the iterator to the first element in the list. 
         *  \return The first compound, or zero if the list was empty. 
         */
        T *toFirst() const
        {
          return m_li->toFirst();
        }

        /*! Set the iterator to the last element in the list. 
         *  \return The first compound, or zero if the list was empty. 
         */
        T *toLast() const
        {
          return m_li->toLast();
        }

        /*! Returns the current compound */
        T *current() const
        {
          return m_li->current();
        }
        
        /*! Moves the iterator to the next element.
         *  \return the new "current" element, or zero if the iterator was
         *          already pointing at the last element.
         */
        T *operator++()
        {
          return m_li->operator++();
        }

        /*! Moves the iterator to the previous element.
         *  \return the new "current" element, or zero if the iterator was
         *          already pointing at the first element.
         */
        T *operator--()
        {
          return m_li->operator--();
        }

      private:
        QListIterator<T> *m_li;
    };

    class IteratorDict;         // first forward declare
    friend class IteratorDict;  // then make it a friend
    /*! Simple iterator for SDict. It iterates over the dictionary elements
     *  in an unsorted way, but does provide information about the element's key.
     */
    class IteratorDict
    {
      public:
        /*! Create an iterator given the dictionary. */
        IteratorDict(const SDict<T> &dict)
        {
          m_di = new QDictIterator<T>(*dict.m_dict);
        }

        /*! Destroys the dictionary */
        virtual ~IteratorDict()
        {
          delete m_di;
        }

        /*! Set the iterator to the first element in the list. 
         *  \return The first compound, or zero if the list was empty. 
         */
        T *toFirst() const
        {
          return m_di->toFirst();
        }

        /*! Set the iterator to the last element in the list. 
         *  \return The first compound, or zero if the list was empty. 
         */
        T *toLast() const
        {
          return m_di->toLast();
        }

        /*! Returns the current compound */
        T *current() const
        {
          return m_di->current();
        }
        
        /*! Returns the current key */
        QCString currentKey() const
        {
          return m_di->currentKey();
        }
        
        /*! Moves the iterator to the next element.
         *  \return the new "current" element, or zero if the iterator was
         *          already pointing at the last element.
         */
        T *operator++()
        {
          return m_di->operator++();
        }

        /*! Moves the iterator to the previous element.
         *  \return the new "current" element, or zero if the iterator was
         *          already pointing at the first element.
         */
        T *operator--()
        {
          return m_di->operator--();
        }

      private:
        QDictIterator<T> *m_di;
    };
};

/** internal wrapper class that redirects compareValues() to the 
 *  dictionary 
 */
template<class T>
class SIntList : public QList<T>
{
  public:
    SIntList(SIntDict<T> *owner) : m_owner(owner) {}
    virtual ~SIntList() {}
  private:
    int compareValues(const T *item1,const T *item2) const
    {
      return m_owner->compareValues(item1,item2);
    }
    SIntDict<T> *m_owner;  
};

/** Ordered dictionary of elements of type T. 
 *  Internally uses a QList<T> and a QIntDict<T>.
 */
template<class T>
class SIntDict 
{
  private:
    SIntList<T> *m_list;
    QIntDict<T> *m_dict;
    int m_sizeIndex;
    
  public:
    /*! Create an ordered dictionary.
     *  \param size The size of the dictionary. Should be a prime number for
     *              best distribution of elements.
     */
    SIntDict(int size=17) : m_sizeIndex(0)
    {
      m_list = new SIntList<T>(this);
#if AUTORESIZE
      while ((uint)size>SDict_primes[m_sizeIndex]) m_sizeIndex++;
      m_dict = new QIntDict<T>(SDict_primes[m_sizeIndex]);
#else
      m_dict = new QIntDict<T>(size);
#endif
    }

    /*! Destroys the dictionary */
    virtual ~SIntDict() 
    {
      delete m_list;
      delete m_dict;
    }

    /*! Appends a compound to the dictionary. The element is owned by the
     *  dictionary.
     *  \param key The unique key to use to quickly find the item later on.
     *  \param d The compound to add.
     *  \sa find()
     */
    void append(int key,const T *d)
    {
      m_list->append(d);
      m_dict->insert(key,d);
#if AUTORESIZE
      if (m_dict->size()>SDict_primes[m_sizeIndex])
      {
        m_dict->resize(SDict_primes[++m_sizeIndex]);
      }
#endif
    }

    /*! Prepend a compound to the dictionary. The element is owned by the
     *  dictionary.
     *  \param key The unique key to use to quickly find the item later on.
     *  \param d The compound to add.
     *  \sa find()
     */
    void prepend(int key,const T *d)
    {
      m_list->prepend(d);
      m_dict->insert(key,d);
#if AUTORESIZE
      if (m_dict->size()>SDict_primes[m_sizeIndex])
      {
        m_dict->resize(SDict_primes[++m_sizeIndex]);
      }
#endif
    }

    /*! Remove an item from the dictionary */
    bool remove(int key)
    {
      T *item = m_dict->take(key);
      return item ? m_list->remove(item) : FALSE;
    }

    /*! Sorts the members of the dictionary. First appending a number
     *  of members and then sorting them is faster (O(NlogN) than using 
     *  inSort() for each member (O(N^2)).
     */
    void sort()
    {
      m_list->sort();
    }

    /*! Inserts a compound into the dictionary in a sorted way.
     *  \param key The unique key to use to quickly find the item later on.
     *  \param d The compound to add.
     *  \sa find()
     */
    void inSort(int key,const T *d)
    {
      m_list->inSort(d);
      m_dict->insert(key,d);
#if AUTORESIZE
      if (m_dict->size()>SDict_primes[m_sizeIndex])
      {
        m_dict->resize(SDict_primes[++m_sizeIndex]);
      }
#endif
    }

    /*! Indicates whether or not the dictionary owns its elements */
    void setAutoDelete(bool val)
    {
      m_list->setAutoDelete(val);
    }

    /*! Looks up a compound given its key. 
     *  \param key The key to identify this element.
     *  \return The requested compound or zero if it cannot be found.
     *  \sa append() 
     */
    T *find(int key)
    {
      return m_dict->find(key);
    }

    /*! Equivalent to find(). */
    T *operator[](int key) const
    {
      return m_dict->find(key);
    }

    /*! Returns the item at position \a i in the sorted dictionary */
    T *at(uint i)
    {
      return m_list->at(i);
    }

    /*! Function that is used to compare two items when sorting.
     *  Overload this to properly sort items.
     *  \sa inSort()
     */
    virtual int compareValues(const T *item1,const T *item2) const
    {
      return item1!=item2;
    }

    /*! Clears the dictionary. Will delete items if setAutoDelete() was
     *  set to \c TRUE.
     *  \sa setAutoDelete
     */
    void clear()
    {
      m_list->clear();
      m_dict->clear();
    }

    /*! Returns the number of items stored in the dictionary
     */
    int count() const
    {
      return m_list->count();
    }

    class Iterator;         // first forward declare
    friend class Iterator;  // then make it a friend
    /*! Simple iterator for SDict. It iterates in the order in which the
     *  elements are stored.
     */
    class Iterator
    {
      public:
        /*! Create an iterator given the dictionary. */
        Iterator(const SIntDict<T> &dict)
        {
          m_li = new QListIterator<T>(*dict.m_list);
        }
        
        /*! Destroys the dictionary */
        virtual ~Iterator()
        {
          delete m_li;
        }
        
        /*! Set the iterator to the first element in the list. 
         *  \return The first compound, or zero if the list was empty. 
         */
        T *toFirst() const
        {
          return m_li->toFirst();
        }
        
        /*! Set the iterator to the last element in the list. 
         *  \return The first compound, or zero if the list was empty. 
         */
        T *toLast() const
        {
          return m_li->toLast();
        }
        
        /*! Returns the current compound */
        T *current() const
        {
          return m_li->current();
        }

        /*! Moves the iterator to the next element.
         *  \return the new "current" element, or zero if the iterator was
         *          already pointing at the last element.
         */
        T *operator++()
        {
          return m_li->operator++();
        }
        
        /*! Moves the iterator to the previous element.
         *  \return the new "current" element, or zero if the iterator was
         *          already pointing at the first element.
         */
        T *operator--()
        {
          return m_li->operator--();
        }

      private:
        QListIterator<T> *m_li;
    };

    class IteratorDict;         // first forward declare
    friend class IteratorDict;  // then make it a friend
    /*! Simple iterator for SDict. It iterates over the dictionary elements
     *  in an unsorted way, but does provide information about the element's key.
     */
    class IteratorDict
    {
      public:
        /*! Create an iterator given the dictionary. */
        IteratorDict(const SIntDict<T> &dict)
        {
          m_di = new QIntDictIterator<T>(*dict.m_dict);
        }

        /*! Destroys the dictionary */
        virtual ~IteratorDict()
        {
          delete m_di;
        }

        /*! Set the iterator to the first element in the list. 
         *  \return The first compound, or zero if the list was empty. 
         */
        T *toFirst() const
        {
          return m_di->toFirst();
        }

        /*! Set the iterator to the last element in the list. 
         *  \return The first compound, or zero if the list was empty. 
         */
        T *toLast() const
        {
          return m_di->toLast();
        }

        /*! Returns the current compound */
        T *current() const
        {
          return m_di->current();
        }
        
        /*! Returns the current key */
        int currentKey() const
        {
          return m_di->currentKey();
        }
        
        /*! Moves the iterator to the next element.
         *  \return the new "current" element, or zero if the iterator was
         *          already pointing at the last element.
         */
        T *operator++()
        {
          return m_di->operator++();
        }

        /*! Moves the iterator to the previous element.
         *  \return the new "current" element, or zero if the iterator was
         *          already pointing at the first element.
         */
        T *operator--()
        {
          return m_di->operator--();
        }

      private:
        QDictIterator<T> *m_di;
    };

};

#endif