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;

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

template<class T>
class SDict 
{
  private:
    SList<T> *m_list;
    QDict<T> *m_dict;
    int m_sizeIndex;
    
  public:
    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
    }

    virtual ~SDict() 
    {
      delete m_list;
      delete m_dict;
    }

    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
    }

    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
    }

    bool remove(const char *key)
    {
      T *item = m_dict->take(key);
      return item ? m_list->remove(item) : FALSE;
    }

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

    void sort()
    {
      m_list->sort();
    }
    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
    }

    void setAutoDelete(bool val)
    {
      m_list->setAutoDelete(val);
    }

    T *find(const char *key)
    {
      return m_dict->find(key);
    }
    T *find(const QCString &key)
    {
      return m_dict->find(key);
    }
    T *find(const QString &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);
    }

    T *operator[](const char *key) const
    {
      return m_dict->find(key);
    }

    T *at(uint i)
    {
      return m_list->at(i);
    }

    virtual int compareValues(const T *item1,const T *item2) const
    {
      return item1!=item2;
    }

    void clear()
    {
      m_list->clear();
      m_dict->clear();
    }
    
    int count() const
    {
      return m_list->count();
    }

    class Iterator;         // first forward declare
    friend class Iterator;  // then make it a friend
    class Iterator
    {
      public:
        Iterator(const SDict<T> &dict)
        {
          m_li = new QListIterator<T>(*dict.m_list);
        }

        virtual ~Iterator()
        {
          delete m_li;
        }

        T *toFirst() const
        {
          return m_li->toFirst();
        }

        T *toLast() const
        {
          return m_li->toLast();
        }

        T *current() const
        {
          return m_li->current();
        }
        
        T *operator++()
        {
          return m_li->operator++();
        }

        T *operator--()
        {
          return m_li->operator--();
        }

      private:
        QListIterator<T> *m_li;
    };

    class IteratorDict;         // first forward declare
    friend class IteratorDict;  // then make it a friend
    class IteratorDict
    {
      public:
        IteratorDict(const SDict<T> &dict)
        {
          m_di = new QDictIterator<T>(*dict.m_dict);
        }

        virtual ~IteratorDict()
        {
          delete m_di;
        }

        T *toFirst() const
        {
          return m_di->toFirst();
        }

        T *toLast() const
        {
          return m_di->toLast();
        }

        T *current() const
        {
          return m_di->current();
        }
        
        QCString currentKey() const
        {
          return m_di->currentKey();
        }
        
        T *operator++()
        {
          return m_di->operator++();
        }

        T *operator--()
        {
          return m_di->operator--();
        }

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

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

template<class T>
class SIntDict 
{
  private:
    SIntList<T> *m_list;
    QIntDict<T> *m_dict;
    int m_sizeIndex;
    
  public:
    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
    }

    virtual ~SIntDict() 
    {
      delete m_list;
      delete m_dict;
    }

    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
    }

    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
    }

    bool remove(int key)
    {
      T *item = m_dict->take(key);
      return item ? m_list->remove(item) : FALSE;
    }

    void sort()
    {
      m_list->sort();
    }

    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
    }

    void setAutoDelete(bool val)
    {
      m_list->setAutoDelete(val);
    }

    T *find(int key)
    {
      return m_dict->find(key);
    }

    T *operator[](int key) const
    {
      return m_dict->find(key);
    }

    T *at(uint i)
    {
      return m_list->at(i);
    }

    virtual int compareValues(const T *item1,const T *item2) const
    {
      return item1!=item2;
    }

    void clear()
    {
      m_list->clear();
      m_dict->clear();
    }

    int count() const
    {
      return m_list->count();
    }

    class Iterator;         // first forward declare
    friend class Iterator;  // then make it a friend
    class Iterator
    {
      public:
        Iterator(const SIntDict<T> &dict)
        {
          m_li = new QListIterator<T>(*dict.m_list);
        }
        
        virtual ~Iterator()
        {
          delete m_li;
        }
        
        T *toFirst() const
        {
          return m_li->toFirst();
        }
        
        T *toLast() const
        {
          return m_li->toLast();
        }
        
        T *current() const
        {
          return m_li->current();
        }

        T *operator++()
        {
          return m_li->operator++();
        }
        
        T *operator--()
        {
          return m_li->operator--();
        }

      private:
        QListIterator<T> *m_li;
    };

    class IteratorDict;         // first forward declare
    friend class IteratorDict;  // then make it a friend
    class IteratorDict
    {
      public:
        IteratorDict(const SIntDict<T> &dict)
        {
          m_di = new QIntDictIterator<T>(*dict.m_dict);
        }

        virtual ~IteratorDict()
        {
          delete m_di;
        }

        T *toFirst() const
        {
          return m_di->toFirst();
        }

        T *toLast() const
        {
          return m_di->toLast();
        }

        T *current() const
        {
          return m_di->current();
        }
        
        int currentKey() const
        {
          return m_di->currentKey();
        }
        
        T *operator++()
        {
          return m_di->operator++();
        }

        T *operator--()
        {
          return m_di->operator--();
        }

      private:
        QDictIterator<T> *m_di;
    };

};

#endif