qtools/qdict.doc

   1 /****************************************************************************
   2 **
   3 **
   4 ** QDict and QDictIterator class documentation
   5 **
   6 ** Copyright (C) 1992-2000 Trolltech AS.  All rights reserved.
   7 **
   8 ** This file is part of the Qt GUI Toolkit.
   9 **
  10 ** This file may be distributed under the terms of the Q Public License
  11 ** as defined by Trolltech AS of Norway and appearing in the file
  12 ** LICENSE.QPL included in the packaging of this file.
  13 **
  14 ** This file may be distributed and/or modified under the terms of the
  15 ** GNU General Public License version 2 as published by the Free Software
  16 ** Foundation and appearing in the file LICENSE.GPL included in the
  17 ** packaging of this file.
  18 **
  19 ** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
  20 ** licenses may use this file in accordance with the Qt Commercial License
  21 ** Agreement provided with the Software.
  22 **
  23 ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  24 ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  25 **
  26 ** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
  27 **   information about Qt Commercial License Agreements.
  28 ** See http://www.trolltech.com/qpl/ for QPL licensing information.
  29 ** See http://www.trolltech.com/gpl/ for GPL licensing information.
  30 **
  31 ** Contact info@trolltech.com if any conditions of this licensing are
  32 ** not clear to you.
  33 **
  34 **********************************************************************/
  35
  36
  37 /*****************************************************************************
  38   QDict documentation
  39  *****************************************************************************/
  40
  41 /*!
  42   \class QDict qdict.h
  43   \brief The QDict class is a template class that provides a dictionary based on \c QString keys.
  44
  45   \ingroup collection
  46   \ingroup tools
  47
  48   QDict is implemented as a template class. Define a template instance
  49   QDict\<X\> to create a dictionary that operates on pointers to X, or X*.
  50
  51   A dictionary is a collection that associates an item with a key.
  52   The key is used for inserting and looking up an item. QDict has
  53   \l QString keys, which are Unicode strings.  If you want to use
  54   non-Unicode, plain 8-bit \c char* keys, use the QAsciiDict template.
  55   A QDict has the same performace as a QAsciiDict.
  56
  57   The dictionary has very fast insertion and lookup.
  58
  59   Example:
  60   \code
  61     #include <qdict.h>
  62     #include <stdio.h>
  63
  64     void main()
  65     {
  66       // Creates a dictionary that maps QString ==> char* (case insensitive)
  67         QDict<char> dict( 17, FALSE );
  68
  69         dict.insert( "France", "Paris" );
  70         dict.insert( "Russia", "Moscow" );
  71         dict.insert( "Norway", "Oslo" );
  72
  73         printf( "%s\n", dict["Norway"] );
  74         printf( "%s\n", dict["FRANCE"] );
  75         printf( "%s\n", dict["russia"] );
  76
  77         if ( !dict["Italy"] )
  78             printf( "Italy not defined\n" );
  79     }
  80   \endcode
  81
  82   Program output:
  83   \code
  84         Oslo
  85         Paris
  86         Moscow
  87         Italy not defined
  88   \endcode
  89
  90   The dictionary in our example maps \c QString keys to \c char* items.
  91   Note that the mapping is case insensitive (specified in the
  92   \link QDict::QDict() constructor\endlink).
  93   QDict implements the \link operator[] [] operator\endlink to lookup an item.
  94
  95   QDict is implemented by QGDict as a hash array with a fixed number of
  96   entries. Each array entry points to a singly linked list of buckets, in
  97   which the dictionary items are stored.
  98
  99   When an item is inserted with a key, the key is converted (hashed) to
 100   an integer index into the hash array. The item is inserted before the
 101   first bucket in the list of buckets.
 102
 103   Looking up an item is normally very fast. The key is again hashed to an
 104   array index. Then QDict scans the list of buckets and returns the item
 105   found or null if the item was not found.  You cannot insert null pointers
 106   into a dictionary.
 107
 108   The size of the hash array is very important. In order to get good
 109   performance, you should use a suitably large \link primes.html prime
 110   number\endlink.  Suitable means equal to or larger than the maximum
 111   expected number of dictionary items.
 112
 113   Items with equal keys are allowed.  When inserting two items with the
 114   same key, only the last inserted item will be visible (last in, first out)
 115   until it is removed.
 116
 117   Example:
 118   \code
 119     #include <qdict.h>
 120     #include <stdio.h>
 121
 122     void main()
 123     {
 124       // Creates a dictionary that maps QString ==> char* (case sensitive)
 125         QDict<char> dict;
 126
 127         dict.insert( "Germany", "Berlin" );
 128         dict.insert( "Germany", "Bonn" );
 129
 130         printf( "%s\n", dict["Germany"] );
 131         dict.remove( "Germany" );       // Oct 3rd 1990
 132         printf( "%s\n", dict["Germany"] );
 133     }
 134   \endcode
 135
 136   Program output:
 137   \code
 138         Bonn
 139         Berlin
 140   \endcode
 141
 142   The QDictIterator class can traverse the dictionary contents, but only
 143   in an arbitrary order.  Multiple iterators may independently traverse the
 144   same dictionary.
 145
 146   Calling setAutoDelete(TRUE) for a dictionary tells it to delete items
 147   that are removed .  The default is to not delete items when they are
 148   removed.
 149
 150   When inserting an item into a dictionary, only the pointer is copied, not
 151   the item itself. This is called a shallow copy. It is possible to make the
 152   dictionary copy all of the item's data (known as a deep copy) when an
 153   item is inserted.  insert() calls the virtual function
 154   QCollection::newItem() for the item to be inserted.
 155   Inherit a dictionary and reimplement it if you want deep copies.
 156
 157   When removing a dictionary item, the virtual function
 158   QCollection::deleteItem() is called.  QDict's default implementation
 159   is to delete the item if auto-deletion is enabled.
 160
 161   \sa QDictIterator, QAsciiDict, QIntDict, QPtrDict,
 162       \link collection.html Collection Classes\endlink
 163 */
 164
 165
 166 /*!
 167   \fn QDict::QDict( int size, bool caseSensitive )
 168   Constructs a dictionary with the following properties:
 169   \arg \e size is the size of the internal hash array.
 170   \arg \e caseSensitive specifies whether to use case sensitive lookup or not.
 171
 172   Setting \e size to a suitably large \link primes.html prime
 173   number\endlink (equal to or greater than the expected number of entries)
 174   makes the hash distribution better and hence the loopup faster.
 175
 176   Setting \e caseSensitive to TRUE will treat "abc" and "Abc" as different
 177   keys.  Setting it to FALSE will make the dictionary ignore case.
 178   Case insensitive comparison includes the whole Unicode alphabeth.
 179 */
 180
 181 /*!
 182   \fn QDict::QDict( const QDict<type> &dict )
 183   Constructs a copy of \e dict.
 184
 185   Each item in \e dict are inserted into this dictionary.
 186   Only the pointers are copied (shallow copy).
 187 */
 188
 189 /*!
 190   \fn QDict::~QDict()
 191   Removes all items from the dictionary and destroys it.
 192   All iterators that access this dictionary will be reset.
 193
 194   \sa setAutoDelete()
 195 */
 196
 197 /*!
 198   \fn QDict<type> &QDict::operator=(const QDict<type> &dict)
 199   Assigns \e dict to this dictionary and returns a reference to this
 200   dictionary.
 201
 202   This dictionary is first cleared, then each item in \e dict is inserted
 203   into this dictionary.
 204   Only the pointers are copied (shallow copy), unless newItem() has been
 205   reimplemented().
 206 */
 207
 208 /*!
 209   \fn uint QDict::count() const
 210   Returns the number of items in the dictionary.
 211   \sa isEmpty()
 212 */
 213
 214 /*!
 215   \fn uint QDict::size() const
 216   Returns the size of the internal hash array (as specified in the
 217   constructor).
 218   \sa count()
 219 */
 220
 221 /*!
 222   \fn void QDict::resize( uint newsize )
 223   Changes the size of the hashtable the \a newsize.
 224   The contents of the dictionary are preserved,
 225   but all iterators on the dictionary become invalid.
 226 */
 227
 228 /*!
 229   \fn bool QDict::isEmpty() const
 230   Returns TRUE if the dictionary is empty, i.e. count() == 0. Returns FALSE
 231   otherwise.
 232   \sa count()
 233 */
 234
 235 /*!
 236   \fn void QDict::insert( const QString &key, const type *item )
 237
 238   Inserts the \e key with the \e item into the dictionary.
 239
 240   The key does not have to be a unique dictionary key.  If multiple items
 241   are inserted with the same key, only the last item will be visible.
 242
 243   Null items are not allowed.
 244
 245   \sa replace()
 246 */
 247
 248 /*!
 249   \fn void QDict::replace( const QString &key, const type *item )
 250
 251   Replaces an item which has a key equal to \e key with \e item.
 252
 253   If the item does not already exist, it will be inserted.
 254
 255   Null items are not allowed.
 256
 257   Equivalent to:
 258   \code
 259     QDict<char> dict;
 260         ...
 261     if ( dict.find(key) )
 262         dict.remove( key );
 263     dict.insert( key, item );
 264   \endcode
 265
 266   If there are two or more items with equal keys, then the last inserted
 267   of these will be replaced.
 268
 269   \sa insert()
 270 */
 271
 272 /*!
 273   \fn bool QDict::remove( const QString &key )
 274
 275   Removes the item associated with \e key from the dictionary.
 276   Returns TRUE if successful, or FALSE if the key does not exist in the
 277   dictionary.
 278
 279   If there are two or more items with equal keys, then the last inserted
 280   of these will be removed.
 281
 282   The removed item is deleted if \link QCollection::setAutoDelete()
 283   auto-deletion\endlink is enabled.
 284
 285   All dictionary iterators that refer to the removed item will be set to
 286   point to the next item in the dictionary traversing order.
 287
 288   \sa take(), clear(), setAutoDelete()
 289 */
 290
 291 /*!
 292   \fn type *QDict::take( const QString &key )
 293
 294   Takes the item associated with \e key out of the dictionary without
 295   deleting it (even if \link QCollection::setAutoDelete()
 296   auto-deletion\endlink is enabled).
 297
 298   If there are two or more items with equal keys, then the last inserted
 299   of these will be taken.
 300
 301   Returns a pointer to the item taken out, or null if the key does not
 302   exist in the dictionary.
 303
 304   All dictionary iterators that refer to the taken item will be set to
 305   point to the next item in the dictionary traversal order.
 306
 307   \sa remove(), clear(), setAutoDelete()
 308 */
 309
 310 /*!
 311   \fn void QDict::clear()
 312
 313   Removes all items from the dictionary.
 314
 315   The removed items are deleted if \link QCollection::setAutoDelete()
 316   auto-deletion\endlink is enabled.
 317
 318   All dictionary iterators that operate on dictionary are reset.
 319
 320   \sa remove(), take(), setAutoDelete()
 321 */
 322
 323 /*!
 324   \fn type *QDict::find( const QString &key ) const
 325
 326   Returns the item associated with \e key, or null if the key does not
 327   exist in the dictionary.
 328
 329   This function uses an internal hashing algorithm to optimize lookup.
 330
 331   If there are two or more items with equal keys, then the last inserted
 332   of these will be found.
 333
 334   Equivalent to the [] operator.
 335
 336   \sa operator[]()
 337 */
 338
 339 /*!
 340   \fn type *QDict::operator[]( const QString &key ) const
 341
 342   Returns the item associated with \e key, or null if the key does not
 343   exist in the dictionary.
 344
 345   This function uses an internal hashing algorithm to optimize lookup.
 346
 347   If there are two or more items with equal keys, then the last inserted
 348   of these will be found.
 349
 350   Equivalent to the find() function.
 351
 352   \sa find()
 353 */
 354
 355 /*!
 356   \fn void QDict::statistics() const
 357   Debugging-only function that prints out the dictionary distribution
 358   using qDebug().
 359 */
 360
 361
 362 /*****************************************************************************
 363   QDictIterator documentation
 364  *****************************************************************************/
 365
 366 /*!
 367   \class QDictIterator qdict.h
 368   \brief The QDictIterator class provides an iterator for QDict collections.
 369
 370   \ingroup collection
 371   \ingroup tools
 372
 373   QDictIterator is implemented as a template class.
 374   Define a template instance QDictIterator\<X\> to create a
 375   dictionary iterator that operates on QDict\<X\> (dictionary of X*).
 376
 377   Example:
 378   \code
 379     #include <qdict.h>
 380     #include <stdio.h>
 381
 382     void main()
 383     {
 384       // Creates a dictionary that maps QString ==> char* (case insensitive)
 385         QDict<char> dict( 17, FALSE );
 386
 387         dict.insert( "France", "Paris" );
 388         dict.insert( "Russia", "Moscow" );
 389         dict.insert( "Norway", "Oslo" );
 390
 391         QDictIterator<char> it( dict ); // iterator for dict
 392
 393         while ( it.current() ) {
 394             printf( "%s -> %s\n", it.currentKey().latin1(), it.current() );
 395             ++it;
 396         }
 397     }
 398   \endcode
 399
 400   Program output:
 401   \code
 402         Russia -> Moscow
 403         Norway -> Oslo
 404         France -> Paris
 405   \endcode
 406
 407   Note that the traversal order is arbitrary, you are not guaranteed the
 408   order above.
 409
 410   Multiple iterators may independently traverse the same dictionary.
 411   A QDict knows about all iterators that are operating on the dictionary.
 412   When an item is removed from the dictionary, QDict update all iterators
 413   that are referring the removed item to point to the next item in the
 414   traversing order.
 415
 416   \sa QDict, \link collection.html Collection Classes\endlink
 417 */
 418
 419 /*!
 420   \fn QDictIterator::QDictIterator( const QDict<type> &dict )
 421   Constructs an iterator for \e dict.  The current iterator item is
 422   set to point on the first item in the \e dict.
 423 */
 424
 425 /*!
 426   \fn QDictIterator::~QDictIterator()
 427   Destroys the iterator.
 428 */
 429
 430 /*!
 431   \fn uint QDictIterator::count() const
 432   Returns the number of items in the dictionary this iterator operates on.
 433   \sa isEmpty()
 434 */
 435
 436 /*!
 437   \fn bool QDictIterator::isEmpty() const
 438   Returns TRUE if the dictionary is empty, i.e. count() == 0, otherwise FALSE.
 439   \sa count()
 440 */
 441
 442 /*!
 443   \fn type *QDictIterator::toFirst()
 444   Sets the current iterator item to point to the first item in the
 445   dictionary and returns a pointer to the item.
 446   If the dictionary is  empty it sets the current item to null and
 447   returns null.
 448 */
 449
 450 /*!
 451   \fn QDictIterator::operator type *() const
 452   Cast operator. Returns a pointer to the current iterator item.
 453   Same as current().
 454 */
 455
 456 /*!
 457   \fn type *QDictIterator::current() const
 458   Returns a pointer to the current iterator item.
 459 */
 460
 461 /*!
 462   \fn QString QDictIterator::currentKey() const
 463   Returns a pointer to the key for the current iterator item.
 464 */
 465
 466 /*!
 467   \fn type *QDictIterator::operator()()
 468   Makes the succeeding item current and returns the original current item.
 469
 470   If the current iterator item was the last item in the dictionary or if it
 471   was null, null is returned.
 472 */
 473
 474 /*!
 475   \fn type *QDictIterator::operator++()
 476   Prefix ++ makes the succeeding item current and returns the new current
 477   item.
 478
 479   If the current iterator item was the last item in the dictionary or if it
 480   was null, null is returned.
 481 */
 482
 483 /*!
 484   \fn type *QDictIterator::operator+=( uint jump )
 485   Sets the current item to the item \e jump positions after the current item,
 486   and returns a pointer to that item.
 487
 488   If that item is beyond the last item or if the dictionary is  empty,
 489   it sets the current item to null and  returns null.
 490 */
 491
 492