diff options
author | dimitri <dimitri@afe2bf4a-e733-0410-8a33-86f594647bc7> | 2001-11-25 18:56:18 (GMT) |
---|---|---|
committer | dimitri <dimitri@afe2bf4a-e733-0410-8a33-86f594647bc7> | 2001-11-25 18:56:18 (GMT) |
commit | cce8b9505201c95443798341d3d6176922db9253 (patch) | |
tree | 6643370adedf0cbaac88d674978bd44175ab1475 /src/sortdict.h | |
parent | c736b03f16a88b6654ff9c1ae680e46b86e50218 (diff) | |
download | Doxygen-cce8b9505201c95443798341d3d6176922db9253.zip Doxygen-cce8b9505201c95443798341d3d6176922db9253.tar.gz Doxygen-cce8b9505201c95443798341d3d6176922db9253.tar.bz2 |
Release-1.2.12-20011125
Diffstat (limited to 'src/sortdict.h')
-rw-r--r-- | src/sortdict.h | 208 |
1 files changed, 208 insertions, 0 deletions
diff --git a/src/sortdict.h b/src/sortdict.h index b716d33..7675724 100644 --- a/src/sortdict.h +++ b/src/sortdict.h @@ -22,6 +22,7 @@ #include "qtbc.h" #include <qlist.h> #include <qdict.h> +#include <qintdict.h> #define AUTORESIZE 1 @@ -63,6 +64,7 @@ const uint SDict_primes[] = #endif template<class T> class SDict; +template<class T> class SIntDict; /*! internal wrapper class that redirects compareItems() to the * dictionary @@ -270,4 +272,210 @@ class SDict }; +/*! 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) {} + ~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 + } + /*! 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 |