src/sortdict.h

   1 /******************************************************************************
   2  *
   3  * $Id: sortdict.h,v 1.3 2001/03/19 19:27:41 root Exp $
   4  *
   5  *
   6  * Copyright (C) 1997-2012 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
  30 const 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
  74 template<class T> class SDict;
  75 template<class T> class SIntDict;
  76
  77 /** internal wrapper class that redirects compareItems() to the
  78  *  dictionary
  79  */
  80 template<class T>
  81 class 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  */
  97 template<class T>
  98 class 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     void insertAt(int i,const char *key,const T *d)
 211     {
 212       m_list->insert(i,d);
 213       m_dict->insert(key,d);
 214 #if AUTORESIZE
 215       if (m_dict->size()>SDict_primes[m_sizeIndex])
 216       {
 217         m_dict->resize(SDict_primes[++m_sizeIndex]);
 218       }
 219 #endif
 220     }
 221
 222     /*! Indicates whether or not the dictionary owns its elements */
 223     void setAutoDelete(bool val)
 224     {
 225       m_list->setAutoDelete(val);
 226     }
 227
 228     /*! Looks up a compound given its key.
 229      *  \param key The key to identify this element.
 230      *  \return The requested compound or zero if it cannot be found.
 231      *  \sa append()
 232      */
 233     T *find(const char *key)
 234     {
 235       return m_dict->find(key);
 236     }
 237     T *find(const QCString &key)
 238     {
 239       return m_dict->find(key);
 240     }
 241     T *find(const QString &key)
 242     {
 243       return m_dict->find(key);
 244     }
 245     int findAt(const QCString &key)
 246     {
 247       T *item = find(key);
 248       if (item==0) return -1;
 249       return m_list->find(item);
 250     }
 251
 252     /*! Equavalent to find(). */
 253     T *operator[](const char *key) const
 254     {
 255       return m_dict->find(key);
 256     }
 257
 258     /*! Returns the item at position \a i in the sorted dictionary */
 259     T *at(uint i)
 260     {
 261       return m_list->at(i);
 262     }
 263
 264     /*! Function that is used to compare two items when sorting.
 265      *  Overload this to properly sort items.
 266      *  \sa inSort()
 267      */
 268     virtual int compareItems(GCI item1,GCI item2)
 269     {
 270       return item1!=item2;
 271     }
 272
 273     /*! Clears the dictionary. Will delete items if setAutoDelete() was
 274      *  set to \c TRUE.
 275      *  \sa setAutoDelete
 276      */
 277     void clear()
 278     {
 279       m_list->clear();
 280       m_dict->clear();
 281     }
 282
 283     /*! Returns the number of items stored in the dictionary
 284      */
 285     int count() const
 286     {
 287       return m_list->count();
 288     }
 289
 290     class Iterator;         // first forward declare
 291     friend class Iterator;  // then make it a friend
 292     /*! Simple iterator for SDict. It iterates in the order in which the
 293      *  elements are stored.
 294      */
 295     class Iterator
 296     {
 297       public:
 298         /*! Create an iterator given the dictionary. */
 299         Iterator(const SDict<T> &dict)
 300         {
 301           m_li = new QListIterator<T>(*dict.m_list);
 302         }
 303
 304         /*! Destroys the dictionary */
 305         virtual ~Iterator()
 306         {
 307           delete m_li;
 308         }
 309
 310         /*! Set the iterator to the first element in the list.
 311          *  \return The first compound, or zero if the list was empty.
 312          */
 313         T *toFirst() const
 314         {
 315           return m_li->toFirst();
 316         }
 317
 318         /*! Set the iterator to the last element in the list.
 319          *  \return The first compound, or zero if the list was empty.
 320          */
 321         T *toLast() const
 322         {
 323           return m_li->toLast();
 324         }
 325
 326         /*! Returns the current compound */
 327         T *current() const
 328         {
 329           return m_li->current();
 330         }
 331
 332         /*! Moves the iterator to the next element.
 333          *  \return the new "current" element, or zero if the iterator was
 334          *          already pointing at the last element.
 335          */
 336         T *operator++()
 337         {
 338           return m_li->operator++();
 339         }
 340
 341         /*! Moves the iterator to the previous element.
 342          *  \return the new "current" element, or zero if the iterator was
 343          *          already pointing at the first element.
 344          */
 345         T *operator--()
 346         {
 347           return m_li->operator--();
 348         }
 349
 350       private:
 351         QListIterator<T> *m_li;
 352     };
 353
 354     class IteratorDict;         // first forward declare
 355     friend class IteratorDict;  // then make it a friend
 356     /*! Simple iterator for SDict. It iterates over the dictionary elements
 357      *  in an unsorted way, but does provide information about the element's key.
 358      */
 359     class IteratorDict
 360     {
 361       public:
 362         /*! Create an iterator given the dictionary. */
 363         IteratorDict(const SDict<T> &dict)
 364         {
 365           m_di = new QDictIterator<T>(*dict.m_dict);
 366         }
 367
 368         /*! Destroys the dictionary */
 369         virtual ~IteratorDict()
 370         {
 371           delete m_di;
 372         }
 373
 374         /*! Set the iterator to the first element in the list.
 375          *  \return The first compound, or zero if the list was empty.
 376          */
 377         T *toFirst() const
 378         {
 379           return m_di->toFirst();
 380         }
 381
 382         /*! Set the iterator to the last element in the list.
 383          *  \return The first compound, or zero if the list was empty.
 384          */
 385         T *toLast() const
 386         {
 387           return m_di->toLast();
 388         }
 389
 390         /*! Returns the current compound */
 391         T *current() const
 392         {
 393           return m_di->current();
 394         }
 395
 396         /*! Returns the current key */
 397         QCString currentKey() const
 398         {
 399           return m_di->currentKey();
 400         }
 401
 402         /*! Moves the iterator to the next element.
 403          *  \return the new "current" element, or zero if the iterator was
 404          *          already pointing at the last element.
 405          */
 406         T *operator++()
 407         {
 408           return m_di->operator++();
 409         }
 410
 411         /*! Moves the iterator to the previous element.
 412          *  \return the new "current" element, or zero if the iterator was
 413          *          already pointing at the first element.
 414          */
 415         T *operator--()
 416         {
 417           return m_di->operator--();
 418         }
 419
 420       private:
 421         QDictIterator<T> *m_di;
 422     };
 423 };
 424
 425 /** internal wrapper class that redirects compareItems() to the
 426  *  dictionary
 427  */
 428 template<class T>
 429 class SIntList : public QList<T>
 430 {
 431   public:
 432     SIntList(SIntDict<T> *owner) : m_owner(owner) {}
 433     virtual ~SIntList() {}
 434     int compareItems(GCI item1,GCI item2)
 435     {
 436       return m_owner->compareItems(item1,item2);
 437     }
 438   private:
 439     SIntDict<T> *m_owner;
 440 };
 441
 442 /** Ordered dictionary of elements of type T.
 443  *  Internally uses a QList<T> and a QIntDict<T>.
 444  */
 445 template<class T>
 446 class SIntDict
 447 {
 448   private:
 449     SIntList<T> *m_list;
 450     QIntDict<T> *m_dict;
 451     int m_sizeIndex;
 452
 453   public:
 454     /*! Create an ordered dictionary.
 455      *  \param size The size of the dictionary. Should be a prime number for
 456      *              best distribution of elements.
 457      */
 458     SIntDict(int size) : m_sizeIndex(0)
 459     {
 460       m_list = new SIntList<T>(this);
 461 #if AUTORESIZE
 462       while ((uint)size>SDict_primes[m_sizeIndex]) m_sizeIndex++;
 463       m_dict = new QIntDict<T>(SDict_primes[m_sizeIndex]);
 464 #else
 465       m_dict = new QIntDict<T>(size);
 466 #endif
 467     }
 468
 469     /*! Destroys the dictionary */
 470     virtual ~SIntDict()
 471     {
 472       delete m_list;
 473       delete m_dict;
 474     }
 475
 476     /*! Appends 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 append(int key,const T *d)
 483     {
 484       m_list->append(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     /*! Prepend a compound to the dictionary. The element is owned by the
 495      *  dictionary.
 496      *  \param key The unique key to use to quicky find the item later on.
 497      *  \param d The compound to add.
 498      *  \sa find()
 499      */
 500     void prepend(int key,const T *d)
 501     {
 502       m_list->prepend(d);
 503       m_dict->insert(key,d);
 504 #if AUTORESIZE
 505       if (m_dict->size()>SDict_primes[m_sizeIndex])
 506       {
 507         m_dict->resize(SDict_primes[++m_sizeIndex]);
 508       }
 509 #endif
 510     }
 511
 512     /*! Remove an item from the dictionary */
 513     bool remove(int key)
 514     {
 515       T *item = m_dict->take(key);
 516       return item ? m_list->remove(item) : FALSE;
 517     }
 518
 519     /*! Sorts the members of the dictionary. First appending a number
 520      *  of members and then sorting them is faster (O(NlogN) than using
 521      *  inSort() for each member (O(N^2)).
 522      */
 523     void sort()
 524     {
 525       m_list->sort();
 526     }
 527
 528     /*! Inserts a compound into the dictionary in a sorted way.
 529      *  \param key The unique key to use to quicky find the item later on.
 530      *  \param d The compound to add.
 531      *  \sa find()
 532      */
 533     void inSort(int key,const T *d)
 534     {
 535       m_list->inSort(d);
 536       m_dict->insert(key,d);
 537 #if AUTORESIZE
 538       if (m_dict->size()>SDict_primes[m_sizeIndex])
 539       {
 540         m_dict->resize(SDict_primes[++m_sizeIndex]);
 541       }
 542 #endif
 543     }
 544
 545     /*! Indicates whether or not the dictionary owns its elements */
 546     void setAutoDelete(bool val)
 547     {
 548       m_list->setAutoDelete(val);
 549     }
 550
 551     /*! Looks up a compound given its key.
 552      *  \param key The key to identify this element.
 553      *  \return The requested compound or zero if it cannot be found.
 554      *  \sa append()
 555      */
 556     T *find(int key)
 557     {
 558       return m_dict->find(key);
 559     }
 560
 561     /*! Equavalent to find(). */
 562     T *operator[](int key) const
 563     {
 564       return m_dict->find(key);
 565     }
 566
 567     /*! Returns the item at position \a i in the sorted dictionary */
 568     T *at(uint i)
 569     {
 570       return m_list->at(i);
 571     }
 572
 573     /*! Function that is used to compare two items when sorting.
 574      *  Overload this to properly sort items.
 575      *  \sa inSort()
 576      */
 577     virtual int compareItems(GCI item1,GCI item2)
 578     {
 579       return item1!=item2;
 580     }
 581
 582     /*! Clears the dictionary. Will delete items if setAutoDelete() was
 583      *  set to \c TRUE.
 584      *  \sa setAutoDelete
 585      */
 586     void clear()
 587     {
 588       m_list->clear();
 589       m_dict->clear();
 590     }
 591
 592     /*! Returns the number of items stored in the dictionary
 593      */
 594     int count()
 595     {
 596       return m_list->count();
 597     }
 598
 599     class Iterator;         // first forward declare
 600     friend class Iterator;  // then make it a friend
 601     /*! Simple iterator for SDict. It iterates in the order in which the
 602      *  elements are stored.
 603      */
 604     class Iterator
 605     {
 606       public:
 607         /*! Create an iterator given the dictionary. */
 608         Iterator(const SIntDict<T> &dict)
 609         {
 610           m_li = new QListIterator<T>(*dict.m_list);
 611         }
 612
 613         /*! Destroys the dictionary */
 614         virtual ~Iterator()
 615         {
 616           delete m_li;
 617         }
 618
 619         /*! Set the iterator to the first element in the list.
 620          *  \return The first compound, or zero if the list was empty.
 621          */
 622         T *toFirst() const
 623         {
 624           return m_li->toFirst();
 625         }
 626
 627         /*! Set the iterator to the last element in the list.
 628          *  \return The first compound, or zero if the list was empty.
 629          */
 630         T *toLast() const
 631         {
 632           return m_li->toLast();
 633         }
 634
 635         /*! Returns the current compound */
 636         T *current() const
 637         {
 638           return m_li->current();
 639         }
 640
 641         /*! Moves the iterator to the next element.
 642          *  \return the new "current" element, or zero if the iterator was
 643          *          already pointing at the last element.
 644          */
 645         T *operator++()
 646         {
 647           return m_li->operator++();
 648         }
 649
 650         /*! Moves the iterator to the previous element.
 651          *  \return the new "current" element, or zero if the iterator was
 652          *          already pointing at the first element.
 653          */
 654         T *operator--()
 655         {
 656           return m_li->operator--();
 657         }
 658
 659       private:
 660         QListIterator<T> *m_li;
 661     };
 662
 663 };
 664
 665 #endif