qtools/qptrdict.doc

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