|
Packit |
1c1d7e |
/******************************************************************************
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
* Copyright (C) 1997-2015 by Dimitri van Heesch.
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
* Permission to use, copy, modify, and distribute this software and its
|
|
Packit |
1c1d7e |
* documentation under the terms of the GNU General Public License is hereby
|
|
Packit |
1c1d7e |
* granted. No representations are made about the suitability of this software
|
|
Packit |
1c1d7e |
* for any purpose. It is provided "as is" without express or implied warranty.
|
|
Packit |
1c1d7e |
* See the GNU General Public License for more details.
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
* Documents produced by Doxygen are derivative works derived from the
|
|
Packit |
1c1d7e |
* input used in their production; they are not affected by this license.
|
|
Packit |
1c1d7e |
*
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#ifndef _SORTDICT_H
|
|
Packit |
1c1d7e |
#define _SORTDICT_H
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#include <qlist.h>
|
|
Packit |
1c1d7e |
#include <qdict.h>
|
|
Packit |
1c1d7e |
#include <qintdict.h>
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#define AUTORESIZE 1
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#if AUTORESIZE
|
|
Packit |
1c1d7e |
const uint SDict_primes[] =
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
17,
|
|
Packit |
1c1d7e |
29,
|
|
Packit |
1c1d7e |
47,
|
|
Packit |
1c1d7e |
71,
|
|
Packit |
1c1d7e |
113,
|
|
Packit |
1c1d7e |
179,
|
|
Packit |
1c1d7e |
293,
|
|
Packit |
1c1d7e |
457,
|
|
Packit |
1c1d7e |
733,
|
|
Packit |
1c1d7e |
1171,
|
|
Packit |
1c1d7e |
1871,
|
|
Packit |
1c1d7e |
2999,
|
|
Packit |
1c1d7e |
4787,
|
|
Packit |
1c1d7e |
7669,
|
|
Packit |
1c1d7e |
12251,
|
|
Packit |
1c1d7e |
19603,
|
|
Packit |
1c1d7e |
31379,
|
|
Packit |
1c1d7e |
50177,
|
|
Packit |
1c1d7e |
80287,
|
|
Packit |
1c1d7e |
128449,
|
|
Packit |
1c1d7e |
205519,
|
|
Packit |
1c1d7e |
328829,
|
|
Packit |
1c1d7e |
526139,
|
|
Packit |
1c1d7e |
841801,
|
|
Packit |
1c1d7e |
1346881,
|
|
Packit |
1c1d7e |
2155007,
|
|
Packit |
1c1d7e |
3448033,
|
|
Packit |
1c1d7e |
5516827,
|
|
Packit |
1c1d7e |
8826919,
|
|
Packit |
1c1d7e |
14123059,
|
|
Packit |
1c1d7e |
23538433,
|
|
Packit |
1c1d7e |
39230771,
|
|
Packit |
1c1d7e |
65384537,
|
|
Packit |
1c1d7e |
108974231,
|
|
Packit |
1c1d7e |
181623707,
|
|
Packit |
1c1d7e |
302706181,
|
|
Packit |
1c1d7e |
504510283,
|
|
Packit |
1c1d7e |
840850487,
|
|
Packit |
1c1d7e |
0xffffffff
|
|
Packit |
1c1d7e |
};
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
template<class T> class SDict;
|
|
Packit |
1c1d7e |
template<class T> class SIntDict;
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/** internal wrapper class that redirects compareValues() to the
|
|
Packit |
1c1d7e |
* dictionary
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
template<class T>
|
|
Packit |
1c1d7e |
class SList : public QList<T>
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
public:
|
|
Packit |
1c1d7e |
SList(SDict<T> *owner) : m_owner(owner) {}
|
|
Packit |
1c1d7e |
virtual ~SList() {}
|
|
Packit |
1c1d7e |
int compareValues(const T *item1,const T *item2) const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_owner->compareValues(item1,item2);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
private:
|
|
Packit |
1c1d7e |
SDict<T> *m_owner;
|
|
Packit |
1c1d7e |
};
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/** Ordered dictionary of elements of type T.
|
|
Packit |
1c1d7e |
* Internally uses a QList<T> and a QDict<T>.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
template<class T>
|
|
Packit |
1c1d7e |
class SDict
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
private:
|
|
Packit |
1c1d7e |
SList<T> *m_list;
|
|
Packit |
1c1d7e |
QDict<T> *m_dict;
|
|
Packit |
1c1d7e |
int m_sizeIndex;
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
public:
|
|
Packit |
1c1d7e |
/*! Create an ordered dictionary.
|
|
Packit |
1c1d7e |
* \param size The size of the dictionary. Should be a prime number for
|
|
Packit |
1c1d7e |
* best distribution of elements.
|
|
Packit |
1c1d7e |
* \param caseSensitive indicated whether the keys should be sorted
|
|
Packit |
1c1d7e |
* in a case sensitive way.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
SDict(int size=17,bool caseSensitive=TRUE) : m_sizeIndex(0)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_list = new SList<T>(this);
|
|
Packit |
1c1d7e |
#if AUTORESIZE
|
|
Packit |
1c1d7e |
while ((uint)size>SDict_primes[m_sizeIndex]) m_sizeIndex++;
|
|
Packit |
1c1d7e |
m_dict = new QDict<T>(SDict_primes[m_sizeIndex],caseSensitive);
|
|
Packit |
1c1d7e |
#else
|
|
Packit |
1c1d7e |
m_dict = new QDict<T>(size,caseSensitive);
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Destroys the dictionary */
|
|
Packit |
1c1d7e |
virtual ~SDict()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
delete m_list;
|
|
Packit |
1c1d7e |
delete m_dict;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Appends an element to the dictionary. The element is owned by the
|
|
Packit |
1c1d7e |
* dictionary.
|
|
Packit |
1c1d7e |
* \param key The unique key to use to quicky find the item later on.
|
|
Packit |
1c1d7e |
* \param d The compound to add.
|
|
Packit |
1c1d7e |
* \sa find()
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
void append(const char *key,const T *d)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_list->append(d);
|
|
Packit |
1c1d7e |
m_dict->insert(key,d);
|
|
Packit |
1c1d7e |
#if AUTORESIZE
|
|
Packit |
1c1d7e |
if (m_dict->size()>SDict_primes[m_sizeIndex])
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_dict->resize(SDict_primes[++m_sizeIndex]);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Prepends an element to the dictionary. The element is owned by the
|
|
Packit |
1c1d7e |
* dictionary.
|
|
Packit |
1c1d7e |
* \param key The unique key to use to quicky find the item later on.
|
|
Packit |
1c1d7e |
* \param d The compound to add.
|
|
Packit |
1c1d7e |
* \sa find()
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
void prepend(const char *key,const T *d)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_list->prepend(d);
|
|
Packit |
1c1d7e |
m_dict->insert(key,d);
|
|
Packit |
1c1d7e |
#if AUTORESIZE
|
|
Packit |
1c1d7e |
if (m_dict->size()>SDict_primes[m_sizeIndex])
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_dict->resize(SDict_primes[++m_sizeIndex]);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Remove an item from the dictionary */
|
|
Packit |
1c1d7e |
bool remove(const char *key)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
T *item = m_dict->take(key);
|
|
Packit |
1c1d7e |
return item ? m_list->remove(item) : FALSE;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Take an item out of the dictionary without deleting it */
|
|
Packit |
1c1d7e |
T *take(const char *key)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
T *item = m_dict->take(key);
|
|
Packit |
1c1d7e |
if (item)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
int i = m_list->find(item);
|
|
Packit |
1c1d7e |
m_list->take(i);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
return item;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Sorts the members of the dictionary. First appending a number
|
|
Packit |
1c1d7e |
* of members and then sorting them is faster (O(NlogN) than using
|
|
Packit |
1c1d7e |
* inSort() for each member (O(N^2)).
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
void sort()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_list->sort();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
/*! Inserts a compound into the dictionary in a sorted way.
|
|
Packit |
1c1d7e |
* \param key The unique key to use to quicky find the item later on.
|
|
Packit |
1c1d7e |
* \param d The compound to add.
|
|
Packit |
1c1d7e |
* \sa find()
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
void inSort(const char *key,const T *d)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_list->inSort(d);
|
|
Packit |
1c1d7e |
m_dict->insert(key,d);
|
|
Packit |
1c1d7e |
#if AUTORESIZE
|
|
Packit |
1c1d7e |
if (m_dict->size()>SDict_primes[m_sizeIndex])
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_dict->resize(SDict_primes[++m_sizeIndex]);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
void insertAt(int i,const char *key,const T *d)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_list->insert(i,d);
|
|
Packit |
1c1d7e |
m_dict->insert(key,d);
|
|
Packit |
1c1d7e |
#if AUTORESIZE
|
|
Packit |
1c1d7e |
if (m_dict->size()>SDict_primes[m_sizeIndex])
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_dict->resize(SDict_primes[++m_sizeIndex]);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Indicates whether or not the dictionary owns its elements */
|
|
Packit |
1c1d7e |
void setAutoDelete(bool val)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_list->setAutoDelete(val);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Looks up a compound given its key.
|
|
Packit |
1c1d7e |
* \param key The key to identify this element.
|
|
Packit |
1c1d7e |
* \return The requested compound or zero if it cannot be found.
|
|
Packit |
1c1d7e |
* \sa append()
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *find(const char *key)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_dict->find(key);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
T *find(const QCString &key)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_dict->find(key);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
T *find(const QString &key)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_dict->find(key);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
int findAt(const QCString &key)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
T *item = find(key);
|
|
Packit |
1c1d7e |
if (item==0) return -1;
|
|
Packit |
1c1d7e |
return m_list->find(item);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Equavalent to find(). */
|
|
Packit |
1c1d7e |
T *operator[](const char *key) const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_dict->find(key);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Returns the item at position \a i in the sorted dictionary */
|
|
Packit |
1c1d7e |
T *at(uint i)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_list->at(i);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Function that is used to compare two items when sorting.
|
|
Packit |
1c1d7e |
* Overload this to properly sort items.
|
|
Packit |
1c1d7e |
* \sa inSort()
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
virtual int compareValues(const T *item1,const T *item2) const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return item1!=item2;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Clears the dictionary. Will delete items if setAutoDelete() was
|
|
Packit |
1c1d7e |
* set to \c TRUE.
|
|
Packit |
1c1d7e |
* \sa setAutoDelete
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
void clear()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_list->clear();
|
|
Packit |
1c1d7e |
m_dict->clear();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Returns the number of items stored in the dictionary
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
int count() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_list->count();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
class Iterator; // first forward declare
|
|
Packit |
1c1d7e |
friend class Iterator; // then make it a friend
|
|
Packit |
1c1d7e |
/*! Simple iterator for SDict. It iterates in the order in which the
|
|
Packit |
1c1d7e |
* elements are stored.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
class Iterator
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
public:
|
|
Packit |
1c1d7e |
/*! Create an iterator given the dictionary. */
|
|
Packit |
1c1d7e |
Iterator(const SDict<T> &dict)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_li = new QListIterator<T>(*dict.m_list);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Destroys the dictionary */
|
|
Packit |
1c1d7e |
virtual ~Iterator()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
delete m_li;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Set the iterator to the first element in the list.
|
|
Packit |
1c1d7e |
* \return The first compound, or zero if the list was empty.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *toFirst() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_li->toFirst();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Set the iterator to the last element in the list.
|
|
Packit |
1c1d7e |
* \return The first compound, or zero if the list was empty.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *toLast() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_li->toLast();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Returns the current compound */
|
|
Packit |
1c1d7e |
T *current() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_li->current();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Moves the iterator to the next element.
|
|
Packit |
1c1d7e |
* \return the new "current" element, or zero if the iterator was
|
|
Packit |
1c1d7e |
* already pointing at the last element.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *operator++()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_li->operator++();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Moves the iterator to the previous element.
|
|
Packit |
1c1d7e |
* \return the new "current" element, or zero if the iterator was
|
|
Packit |
1c1d7e |
* already pointing at the first element.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *operator--()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_li->operator--();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
private:
|
|
Packit |
1c1d7e |
QListIterator<T> *m_li;
|
|
Packit |
1c1d7e |
};
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
class IteratorDict; // first forward declare
|
|
Packit |
1c1d7e |
friend class IteratorDict; // then make it a friend
|
|
Packit |
1c1d7e |
/*! Simple iterator for SDict. It iterates over the dictionary elements
|
|
Packit |
1c1d7e |
* in an unsorted way, but does provide information about the element's key.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
class IteratorDict
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
public:
|
|
Packit |
1c1d7e |
/*! Create an iterator given the dictionary. */
|
|
Packit |
1c1d7e |
IteratorDict(const SDict<T> &dict)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_di = new QDictIterator<T>(*dict.m_dict);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Destroys the dictionary */
|
|
Packit |
1c1d7e |
virtual ~IteratorDict()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
delete m_di;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Set the iterator to the first element in the list.
|
|
Packit |
1c1d7e |
* \return The first compound, or zero if the list was empty.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *toFirst() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_di->toFirst();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Set the iterator to the last element in the list.
|
|
Packit |
1c1d7e |
* \return The first compound, or zero if the list was empty.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *toLast() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_di->toLast();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Returns the current compound */
|
|
Packit |
1c1d7e |
T *current() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_di->current();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Returns the current key */
|
|
Packit |
1c1d7e |
QCString currentKey() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_di->currentKey();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Moves the iterator to the next element.
|
|
Packit |
1c1d7e |
* \return the new "current" element, or zero if the iterator was
|
|
Packit |
1c1d7e |
* already pointing at the last element.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *operator++()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_di->operator++();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Moves the iterator to the previous element.
|
|
Packit |
1c1d7e |
* \return the new "current" element, or zero if the iterator was
|
|
Packit |
1c1d7e |
* already pointing at the first element.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *operator--()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_di->operator--();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
private:
|
|
Packit |
1c1d7e |
QDictIterator<T> *m_di;
|
|
Packit |
1c1d7e |
};
|
|
Packit |
1c1d7e |
};
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/** internal wrapper class that redirects compareValues() to the
|
|
Packit |
1c1d7e |
* dictionary
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
template<class T>
|
|
Packit |
1c1d7e |
class SIntList : public QList<T>
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
public:
|
|
Packit |
1c1d7e |
SIntList(SIntDict<T> *owner) : m_owner(owner) {}
|
|
Packit |
1c1d7e |
virtual ~SIntList() {}
|
|
Packit |
1c1d7e |
private:
|
|
Packit |
1c1d7e |
int compareValues(const T *item1,const T *item2) const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_owner->compareValues(item1,item2);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
SIntDict<T> *m_owner;
|
|
Packit |
1c1d7e |
};
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/** Ordered dictionary of elements of type T.
|
|
Packit |
1c1d7e |
* Internally uses a QList<T> and a QIntDict<T>.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
template<class T>
|
|
Packit |
1c1d7e |
class SIntDict
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
private:
|
|
Packit |
1c1d7e |
SIntList<T> *m_list;
|
|
Packit |
1c1d7e |
QIntDict<T> *m_dict;
|
|
Packit |
1c1d7e |
int m_sizeIndex;
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
public:
|
|
Packit |
1c1d7e |
/*! Create an ordered dictionary.
|
|
Packit |
1c1d7e |
* \param size The size of the dictionary. Should be a prime number for
|
|
Packit |
1c1d7e |
* best distribution of elements.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
SIntDict(int size=17) : m_sizeIndex(0)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_list = new SIntList<T>(this);
|
|
Packit |
1c1d7e |
#if AUTORESIZE
|
|
Packit |
1c1d7e |
while ((uint)size>SDict_primes[m_sizeIndex]) m_sizeIndex++;
|
|
Packit |
1c1d7e |
m_dict = new QIntDict<T>(SDict_primes[m_sizeIndex]);
|
|
Packit |
1c1d7e |
#else
|
|
Packit |
1c1d7e |
m_dict = new QIntDict<T>(size);
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Destroys the dictionary */
|
|
Packit |
1c1d7e |
virtual ~SIntDict()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
delete m_list;
|
|
Packit |
1c1d7e |
delete m_dict;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Appends a compound to the dictionary. The element is owned by the
|
|
Packit |
1c1d7e |
* dictionary.
|
|
Packit |
1c1d7e |
* \param key The unique key to use to quicky find the item later on.
|
|
Packit |
1c1d7e |
* \param d The compound to add.
|
|
Packit |
1c1d7e |
* \sa find()
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
void append(int key,const T *d)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_list->append(d);
|
|
Packit |
1c1d7e |
m_dict->insert(key,d);
|
|
Packit |
1c1d7e |
#if AUTORESIZE
|
|
Packit |
1c1d7e |
if (m_dict->size()>SDict_primes[m_sizeIndex])
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_dict->resize(SDict_primes[++m_sizeIndex]);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Prepend a compound to the dictionary. The element is owned by the
|
|
Packit |
1c1d7e |
* dictionary.
|
|
Packit |
1c1d7e |
* \param key The unique key to use to quicky find the item later on.
|
|
Packit |
1c1d7e |
* \param d The compound to add.
|
|
Packit |
1c1d7e |
* \sa find()
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
void prepend(int key,const T *d)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_list->prepend(d);
|
|
Packit |
1c1d7e |
m_dict->insert(key,d);
|
|
Packit |
1c1d7e |
#if AUTORESIZE
|
|
Packit |
1c1d7e |
if (m_dict->size()>SDict_primes[m_sizeIndex])
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_dict->resize(SDict_primes[++m_sizeIndex]);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Remove an item from the dictionary */
|
|
Packit |
1c1d7e |
bool remove(int key)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
T *item = m_dict->take(key);
|
|
Packit |
1c1d7e |
return item ? m_list->remove(item) : FALSE;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Sorts the members of the dictionary. First appending a number
|
|
Packit |
1c1d7e |
* of members and then sorting them is faster (O(NlogN) than using
|
|
Packit |
1c1d7e |
* inSort() for each member (O(N^2)).
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
void sort()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_list->sort();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Inserts a compound into the dictionary in a sorted way.
|
|
Packit |
1c1d7e |
* \param key The unique key to use to quicky find the item later on.
|
|
Packit |
1c1d7e |
* \param d The compound to add.
|
|
Packit |
1c1d7e |
* \sa find()
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
void inSort(int key,const T *d)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_list->inSort(d);
|
|
Packit |
1c1d7e |
m_dict->insert(key,d);
|
|
Packit |
1c1d7e |
#if AUTORESIZE
|
|
Packit |
1c1d7e |
if (m_dict->size()>SDict_primes[m_sizeIndex])
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_dict->resize(SDict_primes[++m_sizeIndex]);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Indicates whether or not the dictionary owns its elements */
|
|
Packit |
1c1d7e |
void setAutoDelete(bool val)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_list->setAutoDelete(val);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Looks up a compound given its key.
|
|
Packit |
1c1d7e |
* \param key The key to identify this element.
|
|
Packit |
1c1d7e |
* \return The requested compound or zero if it cannot be found.
|
|
Packit |
1c1d7e |
* \sa append()
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *find(int key)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_dict->find(key);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Equavalent to find(). */
|
|
Packit |
1c1d7e |
T *operator[](int key) const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_dict->find(key);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Returns the item at position \a i in the sorted dictionary */
|
|
Packit |
1c1d7e |
T *at(uint i)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_list->at(i);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Function that is used to compare two items when sorting.
|
|
Packit |
1c1d7e |
* Overload this to properly sort items.
|
|
Packit |
1c1d7e |
* \sa inSort()
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
virtual int compareValues(const T *item1,const T *item2) const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return item1!=item2;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Clears the dictionary. Will delete items if setAutoDelete() was
|
|
Packit |
1c1d7e |
* set to \c TRUE.
|
|
Packit |
1c1d7e |
* \sa setAutoDelete
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
void clear()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_list->clear();
|
|
Packit |
1c1d7e |
m_dict->clear();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Returns the number of items stored in the dictionary
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
int count() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_list->count();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
class Iterator; // first forward declare
|
|
Packit |
1c1d7e |
friend class Iterator; // then make it a friend
|
|
Packit |
1c1d7e |
/*! Simple iterator for SDict. It iterates in the order in which the
|
|
Packit |
1c1d7e |
* elements are stored.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
class Iterator
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
public:
|
|
Packit |
1c1d7e |
/*! Create an iterator given the dictionary. */
|
|
Packit |
1c1d7e |
Iterator(const SIntDict<T> &dict)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_li = new QListIterator<T>(*dict.m_list);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Destroys the dictionary */
|
|
Packit |
1c1d7e |
virtual ~Iterator()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
delete m_li;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Set the iterator to the first element in the list.
|
|
Packit |
1c1d7e |
* \return The first compound, or zero if the list was empty.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *toFirst() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_li->toFirst();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Set the iterator to the last element in the list.
|
|
Packit |
1c1d7e |
* \return The first compound, or zero if the list was empty.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *toLast() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_li->toLast();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Returns the current compound */
|
|
Packit |
1c1d7e |
T *current() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_li->current();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Moves the iterator to the next element.
|
|
Packit |
1c1d7e |
* \return the new "current" element, or zero if the iterator was
|
|
Packit |
1c1d7e |
* already pointing at the last element.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *operator++()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_li->operator++();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Moves the iterator to the previous element.
|
|
Packit |
1c1d7e |
* \return the new "current" element, or zero if the iterator was
|
|
Packit |
1c1d7e |
* already pointing at the first element.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *operator--()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_li->operator--();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
private:
|
|
Packit |
1c1d7e |
QListIterator<T> *m_li;
|
|
Packit |
1c1d7e |
};
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
class IteratorDict; // first forward declare
|
|
Packit |
1c1d7e |
friend class IteratorDict; // then make it a friend
|
|
Packit |
1c1d7e |
/*! Simple iterator for SDict. It iterates over the dictionary elements
|
|
Packit |
1c1d7e |
* in an unsorted way, but does provide information about the element's key.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
class IteratorDict
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
public:
|
|
Packit |
1c1d7e |
/*! Create an iterator given the dictionary. */
|
|
Packit |
1c1d7e |
IteratorDict(const SIntDict<T> &dict)
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
m_di = new QIntDictIterator<T>(*dict.m_dict);
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Destroys the dictionary */
|
|
Packit |
1c1d7e |
virtual ~IteratorDict()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
delete m_di;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Set the iterator to the first element in the list.
|
|
Packit |
1c1d7e |
* \return The first compound, or zero if the list was empty.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *toFirst() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_di->toFirst();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Set the iterator to the last element in the list.
|
|
Packit |
1c1d7e |
* \return The first compound, or zero if the list was empty.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *toLast() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_di->toLast();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Returns the current compound */
|
|
Packit |
1c1d7e |
T *current() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_di->current();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Returns the current key */
|
|
Packit |
1c1d7e |
int currentKey() const
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_di->currentKey();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Moves the iterator to the next element.
|
|
Packit |
1c1d7e |
* \return the new "current" element, or zero if the iterator was
|
|
Packit |
1c1d7e |
* already pointing at the last element.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *operator++()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_di->operator++();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*! Moves the iterator to the previous element.
|
|
Packit |
1c1d7e |
* \return the new "current" element, or zero if the iterator was
|
|
Packit |
1c1d7e |
* already pointing at the first element.
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
T *operator--()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return m_di->operator--();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
private:
|
|
Packit |
1c1d7e |
QDictIterator<T> *m_di;
|
|
Packit |
1c1d7e |
};
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
};
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#endif
|