MCL/sftools/depl/doctools: comparison Orb/Doxygen/src/sortdict.h

equal deleted inserted replaced

-:932c358ece3e
+:d8fccb2cd802
+/******************************************************************************
+*
+*
+*
+*
+* 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

changeset 3	d8fccb2cd802
parent 0	42188c7ea2d9
child 4	468f4c8d3d5b