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