diff -r 000000000000 -r 42188c7ea2d9 Orb/Doxygen/src/sortdict.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Orb/Doxygen/src/sortdict.h	Thu Jan 21 17:29:01 2010 +0000
@@ -0,0 +1,647 @@
+/******************************************************************************
+ *
+ * 
+ *
+ *
+ * Copyright (C) 1997-2008 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 "qtbc.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 compareItems() to the 
+ *  dictionary 
+ */
+template<class T>
+class SList : public QList<T>
+{
+  public:
+    SList(SDict<T> *owner) : m_owner(owner) {}
+    virtual ~SList() {}
+    int compareItems(GCI item1,GCI item2)
+    {
+      return m_owner->compareItems(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,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 quicky 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 quicky 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 quicky 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
+    }
+
+    /*! 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);
+    }
+    T *find(const QString &key)
+    {
+      return m_dict->find(key);
+    }
+
+    /*! Equavalent 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 compareItems(GCI item1,GCI item2)
+    {
+      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 in 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 compareItems() to the 
+ *  dictionary 
+ */
+template<class T>
+class SIntList : public QList<T>
+{
+  public:
+    SIntList(SIntDict<T> *owner) : m_owner(owner) {}
+    virtual ~SIntList() {}
+    int compareItems(GCI item1,GCI item2)
+    {
+      return m_owner->compareItems(item1,item2);
+    }
+  private:
+    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) : 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 quicky 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 quicky 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 quicky 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);
+    }
+
+    /*! Equavalent 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 compareItems(GCI item1,GCI item2)
+    {
+      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()
+    {
+      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;
+    };
+
+};
+
+#endif