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