qtools/qintdict.doc

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