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 loopup 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 */