Chameleon

Chameleon Svn Source Tree

Root/branches/xZenu/src/util/doxygen/src/sortdict.h

Source at commit 1322 created 9 years 5 months ago.
By meklort, Add doxygen to utils folder
1/******************************************************************************
2 *
3 * $Id: sortdict.h,v 1.3 2001/03/19 19:27:41 root Exp $
4 *
5 *
6 * Copyright (C) 1997-2011 by Dimitri van Heesch.
7 *
8 * Permission to use, copy, modify, and distribute this software and its
9 * documentation under the terms of the GNU General Public License is hereby
10 * granted. No representations are made about the suitability of this software
11 * for any purpose. It is provided "as is" without express or implied warranty.
12 * See the GNU General Public License for more details.
13 *
14 * Documents produced by Doxygen are derivative works derived from the
15 * input used in their production; they are not affected by this license.
16 *
17 */
18
19#ifndef _SORTDICT_H
20#define _SORTDICT_H
21
22#include "qtbc.h"
23#include <qlist.h>
24#include <qdict.h>
25#include <qintdict.h>
26
27#define AUTORESIZE 1
28
29#if AUTORESIZE
30const uint SDict_primes[] =
31{
32 17,
33 29,
34 47,
35 71,
36 113,
37 179,
38 293,
39 457,
40 733,
41 1171,
42 1871,
43 2999,
44 4787,
45 7669,
46 12251,
47 19603,
48 31379,
49 50177,
50 80287,
51 128449,
52 205519,
53 328829,
54 526139,
55 841801,
56 1346881,
57 2155007,
58 3448033,
59 5516827,
60 8826919,
61 14123059,
62 23538433,
63 39230771,
64 65384537,
65 108974231,
66 181623707,
67 302706181,
68 504510283,
69 840850487,
70 0xffffffff
71};
72#endif
73
74template<class T> class SDict;
75template<class T> class SIntDict;
76
77/*! internal wrapper class that redirects compareItems() to the
78 * dictionary
79 */
80template<class T>
81class SList : public QList<T>
82{
83 public:
84 SList(SDict<T> *owner) : m_owner(owner) {}
85 virtual ~SList() {}
86 int compareItems(GCI item1,GCI item2)
87 {
88 return m_owner->compareItems(item1,item2);
89 }
90 private:
91 SDict<T> *m_owner;
92};
93
94/*! Ordered dictionary of elements of type T.
95 * Internally uses a QList<T> and a QDict<T>.
96 */
97template<class T>
98class SDict
99{
100 private:
101 SList<T> *m_list;
102 QDict<T> *m_dict;
103 int m_sizeIndex;
104
105 public:
106 /*! Create an ordered dictionary.
107 * \param size The size of the dictionary. Should be a prime number for
108 * best distribution of elements.
109 * \param caseSensitive indicated whether the keys should be sorted
110 * in a case sensitive way.
111 */
112 SDict(int size,bool caseSensitive=TRUE) : m_sizeIndex(0)
113 {
114 m_list = new SList<T>(this);
115#if AUTORESIZE
116 while ((uint)size>SDict_primes[m_sizeIndex]) m_sizeIndex++;
117 m_dict = new QDict<T>(SDict_primes[m_sizeIndex],caseSensitive);
118#else
119 m_dict = new QDict<T>(size,caseSensitive);
120#endif
121 }
122
123 /*! Destroys the dictionary */
124 virtual ~SDict()
125 {
126 delete m_list;
127 delete m_dict;
128 }
129
130 /*! Appends an element to the dictionary. The element is owned by the
131 * dictionary.
132 * \param key The unique key to use to quicky find the item later on.
133 * \param d The compound to add.
134 * \sa find()
135 */
136 void append(const char *key,const T *d)
137 {
138 m_list->append(d);
139 m_dict->insert(key,d);
140#if AUTORESIZE
141 if (m_dict->size()>SDict_primes[m_sizeIndex])
142 {
143 m_dict->resize(SDict_primes[++m_sizeIndex]);
144 }
145#endif
146 }
147
148 /*! Prepends an element to the dictionary. The element is owned by the
149 * dictionary.
150 * \param key The unique key to use to quicky find the item later on.
151 * \param d The compound to add.
152 * \sa find()
153 */
154 void prepend(const char *key,const T *d)
155 {
156 m_list->prepend(d);
157 m_dict->insert(key,d);
158#if AUTORESIZE
159 if (m_dict->size()>SDict_primes[m_sizeIndex])
160 {
161 m_dict->resize(SDict_primes[++m_sizeIndex]);
162 }
163#endif
164 }
165
166 /*! Remove an item from the dictionary */
167 bool remove(const char *key)
168 {
169 T *item = m_dict->take(key);
170 return item ? m_list->remove(item) : FALSE;
171 }
172
173 /*! Take an item out of the dictionary without deleting it */
174 T *take(const char *key)
175 {
176 T *item = m_dict->take(key);
177 if (item)
178 {
179 int i = m_list->find(item);
180 m_list->take(i);
181 }
182 return item;
183 }
184
185 /*! Sorts the members of the dictionary. First appending a number
186 * of members and then sorting them is faster (O(NlogN) than using
187 * inSort() for each member (O(N^2)).
188 */
189 void sort()
190 {
191 m_list->sort();
192 }
193 /*! Inserts a compound into the dictionary in a sorted way.
194 * \param key The unique key to use to quicky find the item later on.
195 * \param d The compound to add.
196 * \sa find()
197 */
198 void inSort(const char *key,const T *d)
199 {
200 m_list->inSort(d);
201 m_dict->insert(key,d);
202#if AUTORESIZE
203 if (m_dict->size()>SDict_primes[m_sizeIndex])
204 {
205 m_dict->resize(SDict_primes[++m_sizeIndex]);
206 }
207#endif
208 }
209
210 /*! Indicates whether or not the dictionary owns its elements */
211 void setAutoDelete(bool val)
212 {
213 m_list->setAutoDelete(val);
214 }
215
216 /*! Looks up a compound given its key.
217 * \param key The key to identify this element.
218 * \return The requested compound or zero if it cannot be found.
219 * \sa append()
220 */
221 T *find(const char *key)
222 {
223 return m_dict->find(key);
224 }
225 T *find(const QCString &key)
226 {
227 return m_dict->find(key);
228 }
229 T *find(const QString &key)
230 {
231 return m_dict->find(key);
232 }
233
234 /*! Equavalent to find(). */
235 T *operator[](const char *key) const
236 {
237 return m_dict->find(key);
238 }
239
240 /*! Returns the item at position \a i in the sorted dictionary */
241 T *at(uint i)
242 {
243 return m_list->at(i);
244 }
245
246 /*! Function that is used to compare two items when sorting.
247 * Overload this to properly sort items.
248 * \sa inSort()
249 */
250 virtual int compareItems(GCI item1,GCI item2)
251 {
252 return item1!=item2;
253 }
254
255 /*! Clears the dictionary. Will delete items if setAutoDelete() was
256 * set to \c TRUE.
257 * \sa setAutoDelete
258 */
259 void clear()
260 {
261 m_list->clear();
262 m_dict->clear();
263 }
264
265 /*! Returns the number of items stored in the dictionary
266 */
267 int count() const
268 {
269 return m_list->count();
270 }
271
272 class Iterator; // first forward declare
273 friend class Iterator; // then make it a friend
274 /*! Simple iterator for SDict. It iterates in the order in which the
275 * elements are stored.
276 */
277 class Iterator
278 {
279 public:
280 /*! Create an iterator given the dictionary. */
281 Iterator(const SDict<T> &dict)
282 {
283 m_li = new QListIterator<T>(*dict.m_list);
284 }
285
286 /*! Destroys the dictionary */
287 virtual ~Iterator()
288 {
289 delete m_li;
290 }
291
292 /*! Set the iterator to the first element in the list.
293 * \return The first compound, or zero if the list was empty.
294 */
295 T *toFirst() const
296 {
297 return m_li->toFirst();
298 }
299
300 /*! Set the iterator to the last element in the list.
301 * \return The first compound, or zero if the list was empty.
302 */
303 T *toLast() const
304 {
305 return m_li->toLast();
306 }
307
308 /*! Returns the current compound */
309 T *current() const
310 {
311 return m_li->current();
312 }
313
314 /*! Moves the iterator to the next element.
315 * \return the new "current" element, or zero if the iterator was
316 * already pointing at the last element.
317 */
318 T *operator++()
319 {
320 return m_li->operator++();
321 }
322
323 /*! Moves the iterator to the previous element.
324 * \return the new "current" element, or zero if the iterator was
325 * already pointing at the first element.
326 */
327 T *operator--()
328 {
329 return m_li->operator--();
330 }
331
332 private:
333 QListIterator<T> *m_li;
334 };
335
336 class IteratorDict; // first forward declare
337 friend class IteratorDict; // then make it a friend
338 /*! Simple iterator for SDict. It iterates in over the dictionary elements
339 * in an unsorted way, but does provide information about the element's key.
340 */
341 class IteratorDict
342 {
343 public:
344 /*! Create an iterator given the dictionary. */
345 IteratorDict(const SDict<T> &dict)
346 {
347 m_di = new QDictIterator<T>(*dict.m_dict);
348 }
349
350 /*! Destroys the dictionary */
351 virtual ~IteratorDict()
352 {
353 delete m_di;
354 }
355
356 /*! Set the iterator to the first element in the list.
357 * \return The first compound, or zero if the list was empty.
358 */
359 T *toFirst() const
360 {
361 return m_di->toFirst();
362 }
363
364 /*! Set the iterator to the last element in the list.
365 * \return The first compound, or zero if the list was empty.
366 */
367 T *toLast() const
368 {
369 return m_di->toLast();
370 }
371
372 /*! Returns the current compound */
373 T *current() const
374 {
375 return m_di->current();
376 }
377
378 /*! Returns the current key */
379 QCString currentKey() const
380 {
381 return m_di->currentKey();
382 }
383
384 /*! Moves the iterator to the next element.
385 * \return the new "current" element, or zero if the iterator was
386 * already pointing at the last element.
387 */
388 T *operator++()
389 {
390 return m_di->operator++();
391 }
392
393 /*! Moves the iterator to the previous element.
394 * \return the new "current" element, or zero if the iterator was
395 * already pointing at the first element.
396 */
397 T *operator--()
398 {
399 return m_di->operator--();
400 }
401
402 private:
403 QDictIterator<T> *m_di;
404 };
405};
406
407/*! internal wrapper class that redirects compareItems() to the
408 * dictionary
409 */
410template<class T>
411class SIntList : public QList<T>
412{
413 public:
414 SIntList(SIntDict<T> *owner) : m_owner(owner) {}
415 virtual ~SIntList() {}
416 int compareItems(GCI item1,GCI item2)
417 {
418 return m_owner->compareItems(item1,item2);
419 }
420 private:
421 SIntDict<T> *m_owner;
422};
423
424/*! Ordered dictionary of elements of type T.
425 * Internally uses a QList<T> and a QIntDict<T>.
426 */
427template<class T>
428class SIntDict
429{
430 private:
431 SIntList<T> *m_list;
432 QIntDict<T> *m_dict;
433 int m_sizeIndex;
434
435 public:
436 /*! Create an ordered dictionary.
437 * \param size The size of the dictionary. Should be a prime number for
438 * best distribution of elements.
439 */
440 SIntDict(int size) : m_sizeIndex(0)
441 {
442 m_list = new SIntList<T>(this);
443#if AUTORESIZE
444 while ((uint)size>SDict_primes[m_sizeIndex]) m_sizeIndex++;
445 m_dict = new QIntDict<T>(SDict_primes[m_sizeIndex]);
446#else
447 m_dict = new QIntDict<T>(size);
448#endif
449 }
450
451 /*! Destroys the dictionary */
452 virtual ~SIntDict()
453 {
454 delete m_list;
455 delete m_dict;
456 }
457
458 /*! Appends a compound to the dictionary. The element is owned by the
459 * dictionary.
460 * \param key The unique key to use to quicky find the item later on.
461 * \param d The compound to add.
462 * \sa find()
463 */
464 void append(int key,const T *d)
465 {
466 m_list->append(d);
467 m_dict->insert(key,d);
468#if AUTORESIZE
469 if (m_dict->size()>SDict_primes[m_sizeIndex])
470 {
471 m_dict->resize(SDict_primes[++m_sizeIndex]);
472 }
473#endif
474 }
475
476 /*! Prepend a compound to the dictionary. The element is owned by the
477 * dictionary.
478 * \param key The unique key to use to quicky find the item later on.
479 * \param d The compound to add.
480 * \sa find()
481 */
482 void prepend(int key,const T *d)
483 {
484 m_list->prepend(d);
485 m_dict->insert(key,d);
486#if AUTORESIZE
487 if (m_dict->size()>SDict_primes[m_sizeIndex])
488 {
489 m_dict->resize(SDict_primes[++m_sizeIndex]);
490 }
491#endif
492 }
493
494 /*! Remove an item from the dictionary */
495 bool remove(int key)
496 {
497 T *item = m_dict->take(key);
498 return item ? m_list->remove(item) : FALSE;
499 }
500
501 /*! Sorts the members of the dictionary. First appending a number
502 * of members and then sorting them is faster (O(NlogN) than using
503 * inSort() for each member (O(N^2)).
504 */
505 void sort()
506 {
507 m_list->sort();
508 }
509
510 /*! Inserts a compound into the dictionary in a sorted way.
511 * \param key The unique key to use to quicky find the item later on.
512 * \param d The compound to add.
513 * \sa find()
514 */
515 void inSort(int key,const T *d)
516 {
517 m_list->inSort(d);
518 m_dict->insert(key,d);
519#if AUTORESIZE
520 if (m_dict->size()>SDict_primes[m_sizeIndex])
521 {
522 m_dict->resize(SDict_primes[++m_sizeIndex]);
523 }
524#endif
525 }
526
527 /*! Indicates whether or not the dictionary owns its elements */
528 void setAutoDelete(bool val)
529 {
530 m_list->setAutoDelete(val);
531 }
532
533 /*! Looks up a compound given its key.
534 * \param key The key to identify this element.
535 * \return The requested compound or zero if it cannot be found.
536 * \sa append()
537 */
538 T *find(int key)
539 {
540 return m_dict->find(key);
541 }
542
543 /*! Equavalent to find(). */
544 T *operator[](int key) const
545 {
546 return m_dict->find(key);
547 }
548
549 /*! Returns the item at position \a i in the sorted dictionary */
550 T *at(uint i)
551 {
552 return m_list->at(i);
553 }
554
555 /*! Function that is used to compare two items when sorting.
556 * Overload this to properly sort items.
557 * \sa inSort()
558 */
559 virtual int compareItems(GCI item1,GCI item2)
560 {
561 return item1!=item2;
562 }
563
564 /*! Clears the dictionary. Will delete items if setAutoDelete() was
565 * set to \c TRUE.
566 * \sa setAutoDelete
567 */
568 void clear()
569 {
570 m_list->clear();
571 m_dict->clear();
572 }
573
574 /*! Returns the number of items stored in the dictionary
575 */
576 int count()
577 {
578 return m_list->count();
579 }
580
581 class Iterator; // first forward declare
582 friend class Iterator; // then make it a friend
583 /*! Simple iterator for SDict. It iterates in the order in which the
584 * elements are stored.
585 */
586 class Iterator
587 {
588 public:
589 /*! Create an iterator given the dictionary. */
590 Iterator(const SIntDict<T> &dict)
591 {
592 m_li = new QListIterator<T>(*dict.m_list);
593 }
594
595 /*! Destroys the dictionary */
596 virtual ~Iterator()
597 {
598 delete m_li;
599 }
600
601 /*! Set the iterator to the first element in the list.
602 * \return The first compound, or zero if the list was empty.
603 */
604 T *toFirst() const
605 {
606 return m_li->toFirst();
607 }
608
609 /*! Set the iterator to the last element in the list.
610 * \return The first compound, or zero if the list was empty.
611 */
612 T *toLast() const
613 {
614 return m_li->toLast();
615 }
616
617 /*! Returns the current compound */
618 T *current() const
619 {
620 return m_li->current();
621 }
622
623 /*! Moves the iterator to the next element.
624 * \return the new "current" element, or zero if the iterator was
625 * already pointing at the last element.
626 */
627 T *operator++()
628 {
629 return m_li->operator++();
630 }
631
632 /*! Moves the iterator to the previous element.
633 * \return the new "current" element, or zero if the iterator was
634 * already pointing at the first element.
635 */
636 T *operator--()
637 {
638 return m_li->operator--();
639 }
640
641 private:
642 QListIterator<T> *m_li;
643 };
644
645};
646
647#endif
648

Archive Download this file

Revision: 1322