1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the documentation of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 /*!

    43     \class Q3Dict

    44     \brief The Q3Dict class is a template class that provides a

    45     dictionary based on QString keys.

    46     \compat

    47 

    48     Q3Dict is implemented as a template class. Define a template

    49     instance Q3Dict\<X\> to create a dictionary that operates on

    50     pointers to X (X *).

    51 

    52     A dictionary is a collection of key-value pairs. The key is a

    53     QString used for insertion, removal and lookup. The value is a

    54     pointer. Dictionaries provide very fast insertion and lookup.

    55 

    56     If you want to use non-Unicode, plain 8-bit \c char* keys, use the

    57     Q3AsciiDict template. A Q3Dict has the same performance as a

    58     Q3AsciiDict. If you want to have a dictionary that maps QStrings to

    59     QStrings use QMap.

    60 

    61     The size() of the dictionary is very important. In order to get

    62     good performance, you should use a suitably large prime number.

    63     Suitable means equal to or larger than the maximum expected number

    64     of dictionary items. Size is set in the constructor but may be

    65     changed with resize().

    66 

    67     Items are inserted with insert(); 0 pointers cannot be inserted.

    68     Items are removed with remove(). All the items in a dictionary can

    69     be removed with clear(). The number of items in the dictionary is

    70     returned by count(). If the dictionary contains no items isEmpty()

    71     returns TRUE. You can change an item's value with replace(). Items

    72     are looked up with operator[](), or with find() which return a

    73     pointer to the value or 0 if the given key does not exist. You can

    74     take an item out of the dictionary with take().

    75 

    76     Calling setAutoDelete(TRUE) for a dictionary tells it to delete

    77     items that are removed. The default behavior is not to delete

    78     items when they are removed.

    79    

    80     When an item is inserted, the key is converted (hashed) to an

    81     integer index into an internal hash array. This makes lookup very

    82     fast.

    83 

    84     Items with equal keys are allowed. When inserting two items with

    85     the same key, only the last inserted item will be accessible (last

    86     in, first out) until it is removed.

    87 

    88     The Q3DictIterator class can traverse the dictionary, but only in

    89     an arbitrary order. Multiple iterators may independently traverse

    90     the same dictionary.

    91 

    92     When inserting an item into a dictionary, only the pointer is

    93     copied, not the item itself, i.e. a shallow copy is made. It is

    94     possible to make the dictionary copy all of the item's data (a

    95     deep copy) when an item is inserted. insert() calls the virtual

    96     function Q3PtrCollection::newItem() for the item to be inserted.

    97     Inherit a dictionary and reimplement newItem() if you want deep

    98     copies.

    99 

   100     When removing a dictionary item, the virtual function

   101     Q3PtrCollection::deleteItem() is called. Q3Dict's default

   102     implementation is to delete the item if auto-deletion is enabled.

   103 

   104     \sa Q3DictIterator, Q3AsciiDict, Q3IntDict, Q3PtrDict

   105 */

   106 

   107 

   108 /*!

   109     \fn Q3Dict::Q3Dict( int size, bool caseSensitive )

   110 

   111     Constructs a dictionary optimized for less than \a size entries.

   112 

   113     We recommend setting \a size to a suitably large prime number

   114     (e.g. a prime that's slightly larger than the expected number of

   115     entries). This makes the hash distribution better which will lead

   116     to faster lookup.

   117 

   118     If \a caseSensitive is TRUE (the default), keys which differ only

   119     by case are considered different.

   120 */

   121 

   122 /*!

   123     \fn Q3Dict::Q3Dict( const Q3Dict<type> &dict )

   124 

   125     Constructs a copy of \a dict.

   126 

   127     Each item in \a dict is inserted into this dictionary. Only the

   128     pointers are copied (shallow copy).

   129 */

   130 

   131 /*!

   132     \fn Q3Dict::~Q3Dict()

   133 

   134     Removes all items from the dictionary and destroys it. If

   135     setAutoDelete() is TRUE, each value is deleted. All iterators that

   136     access this dictionary will be reset.

   137 

   138     \sa setAutoDelete()

   139 */

   140 

   141 /*!

   142     \fn Q3Dict<type> &Q3Dict::operator=(const Q3Dict<type> &dict)

   143 

   144     Assigns \a dict to this dictionary and returns a reference to this

   145     dictionary.

   146 

   147     This dictionary is first cleared, then each item in \a dict is

   148     inserted into this dictionary. Only the pointers are copied

   149     (shallow copy), unless newItem() has been reimplemented.

   150 */

   151 

   152 /*!

   153     \fn uint Q3Dict::count() const

   154 

   155     Returns the number of items in the dictionary.

   156 

   157     \sa isEmpty()

   158 */

   159 

   160 /*!

   161     \fn uint Q3Dict::size() const

   162 

   163     Returns the size of the internal hash array (as specified in the

   164     constructor).

   165 

   166     \sa count()

   167 */

   168 

   169 /*!

   170     \fn void Q3Dict::resize( uint newsize )

   171 

   172     Changes the size of the hash table to \a newsize. The contents of

   173     the dictionary are preserved, but all iterators on the dictionary

   174     become invalid.

   175 */

   176 

   177 /*!

   178     \fn bool Q3Dict::isEmpty() const

   179 

   180     Returns TRUE if the dictionary is empty, i.e. count() == 0;

   181     otherwise returns FALSE.

   182 

   183     \sa count()

   184 */

   185 

   186 /*!

   187     \fn void Q3Dict::insert( const QString &key, const type *item )

   188 

   189     Inserts the key \a key with value \a item into the dictionary.

   190 

   191     Multiple items can have the same key, in which case only the last

   192     item will be accessible using \l operator[]().

   193 

   194     \a item may not be 0.

   195 

   196     \sa replace()

   197 */

   198 

   199 /*!

   200     \fn void Q3Dict::replace( const QString &key, const type *item )

   201 

   202     Replaces the value of the key, \a key with \a item.

   203 

   204     If the item does not already exist, it will be inserted.

   205 

   206     \a item may not be 0.

   207 

   208     Equivalent to:

   209     \snippet doc/src/snippets/code/doc_src_q3dict.qdoc 0

   210 

   211     If there are two or more items with equal keys, then the last item

   212     that was inserted will be replaced.

   213 

   214     \sa insert()

   215 */

   216 

   217 /*!

   218     \fn bool Q3Dict::remove( const QString &key )

   219 

   220     Removes the item with \a key from the dictionary. Returns TRUE if

   221     successful, i.e. if the item is in the dictionary; otherwise

   222     returns FALSE.

   223 

   224     If there are two or more items with equal keys, then the last item

   225     that was inserted will be removed.

   226 

   227     The removed item is deleted if \link

   228     Q3PtrCollection::setAutoDelete() auto-deletion\endlink is enabled.

   229 

   230     All dictionary iterators that refer to the removed item will be

   231     set to point to the next item in the dictionary's traversal order.

   232 

   233     \sa take(), clear(), setAutoDelete()

   234 */

   235 

   236 /*!

   237     \fn type *Q3Dict::take( const QString &key )

   238 

   239     Takes the item with \a key out of the dictionary without deleting

   240     it (even if \link Q3PtrCollection::setAutoDelete()

   241     auto-deletion\endlink is enabled).

   242 

   243     If there are two or more items with equal keys, then the last item

   244     that was inserted will be taken.

   245 

   246     Returns a pointer to the item taken out, or 0 if the key does not

   247     exist in the dictionary.

   248 

   249     All dictionary iterators that refer to the taken item will be set

   250     to point to the next item in the dictionary traversal order.

   251 

   252     \sa remove(), clear(), setAutoDelete()

   253 */

   254 

   255 /*!

   256     \fn void Q3Dict::clear()

   257 

   258     Removes all items from the dictionary.

   259 

   260     The removed items are deleted if \link

   261     Q3PtrCollection::setAutoDelete() auto-deletion\endlink is enabled.

   262 

   263     All dictionary iterators that operate on the dictionary are reset.

   264 

   265     \sa remove(), take(), setAutoDelete()

   266 */

   267 

   268 /*!

   269     \fn type *Q3Dict::find( const QString &key ) const

   270 

   271     Returns the item with key \a key, or 0 if the key does not exist

   272     in the dictionary.

   273 

   274     If there are two or more items with equal keys, then the most

   275     recently inserted item will be found.

   276 

   277     Equivalent to the [] operator.

   278 

   279     \sa operator[]()

   280 */

   281 

   282 /*!

   283     \fn type *Q3Dict::operator[]( const QString &key ) const

   284 

   285     Returns the item with key \a key, or 0 if the key does not

   286     exist in the dictionary.

   287 

   288     If there are two or more items with equal keys, then the most

   289     recently inserted item will be found.

   290 

   291     Equivalent to the find() function.

   292 

   293     \sa find()

   294 */

   295 

   296 /*!

   297     \fn void Q3Dict::statistics() const

   298 

   299     Debugging-only function that prints out the dictionary

   300     distribution using qDebug().

   301 */

   302 

   303 /*!

   304     \fn QDataStream& Q3Dict::read( QDataStream &s, Q3PtrCollection::Item &item )

   305 

   306     Reads a dictionary item from the stream \a s and returns a

   307     reference to the stream.

   308 

   309     The default implementation sets \a item to 0.

   310 

   311     \sa write()

   312 */

   313 

   314 /*!

   315     \fn QDataStream& Q3Dict::write( QDataStream &s, Q3PtrCollection::Item item ) const

   316 

   317     Writes a dictionary \a item to the stream \a s and returns a

   318     reference to the stream.

   319 

   320     \sa read()

   321 */

   322 

   323 /*!

   324     \class Q3DictIterator

   325     \brief The Q3DictIterator class provides an iterator for Q3Dict collections.

   326     \compat

   327 

   328     Q3DictIterator is implemented as a template class. Define a

   329     template instance Q3DictIterator\<X\> to create a dictionary

   330     iterator that operates on Q3Dict\<X\> (dictionary of X*).

   331 

   332     The traversal order is arbitrary; when we speak of the "first",

   333     "last" and "next" item we are talking in terms of this arbitrary

   334     order.

   335 

   336     Multiple iterators may independently traverse the same dictionary.

   337     A Q3Dict knows about all the iterators that are operating on the

   338     dictionary. When an item is removed from the dictionary, Q3Dict

   339     updates all iterators that are referring to the removed item to

   340     point to the next item in the (arbitrary) traversal order.

   341 

   342     Example:

   343     \snippet doc/src/snippets/code/doc_src_q3dict.qdoc 1

   344     In the example we insert some pointers to line edits into a

   345     dictionary, then iterate over the dictionary printing the strings

   346     associated with the line edits.

   347 

   348     \sa Q3Dict

   349 */

   350 

   351 /*!

   352     \fn Q3DictIterator::Q3DictIterator( const Q3Dict<type> &dict )

   353 

   354     Constructs an iterator for \a dict. The current iterator item is

   355     set to point to the first item in the dictionary, \a dict. First

   356     in this context means first in the arbitrary traversal order.

   357 */

   358 

   359 /*!

   360     \fn Q3DictIterator::~Q3DictIterator()

   361 

   362     Destroys the iterator.

   363 */

   364 

   365 /*!

   366     \fn uint Q3DictIterator::count() const

   367 

   368     Returns the number of items in the dictionary over which the

   369     iterator is operating.

   370 

   371     \sa isEmpty()

   372 */

   373 

   374 /*!

   375     \fn bool Q3DictIterator::isEmpty() const

   376 

   377     Returns TRUE if the dictionary is empty, i.e. count() == 0;

   378     otherwise returns FALSE.

   379 

   380     \sa count()

   381 */

   382 

   383 /*!

   384     \fn type *Q3DictIterator::toFirst()

   385 

   386     Resets the iterator, making the first item the first current item.

   387     First in this context means first in the arbitrary traversal

   388     order. Returns a pointer to this item.

   389 

   390     If the dictionary is empty it sets the current item to 0 and

   391     returns 0.

   392 */

   393 

   394 /*!

   395   \fn type *Q3DictIterator::operator*()

   396   \internal

   397 */

   398 

   399 /*!

   400     \fn Q3DictIterator::operator type*() const

   401 

   402     Cast operator. Returns a pointer to the current iterator item.

   403     Same as current().

   404 */

   405 

   406 

   407 /*!

   408     \fn type *Q3DictIterator::current() const

   409 

   410     Returns a pointer to the current iterator item's value.

   411 */

   412 

   413 /*!

   414     \fn QString Q3DictIterator::currentKey() const

   415 

   416     Returns the current iterator item's key.

   417 */

   418 

   419 /*!

   420     \fn type *Q3DictIterator::operator()()

   421 

   422     Makes the next item current and returns the original current item.

   423 

   424     If the current iterator item was the last item in the dictionary

   425     or if it was 0, 0 is returned.

   426 */

   427 

   428 /*!

   429     \fn type *Q3DictIterator::operator++()

   430 

   431     Prefix ++ makes the next item current and returns the new current

   432     item.

   433 

   434     If the current iterator item was the last item in the dictionary

   435     or if it was 0, 0 is returned.

   436 */

   437 

   438 /*!

   439   \fn type *Q3DictIterator::operator+=( uint jump )

   440   \internal

   441   Sets the current item to the item \a jump positions after the current item,

   442   and returns a pointer to that item.

   443 

   444   If that item is beyond the last item or if the dictionary is empty,

   445   it sets the current item to 0 and returns 0.

   446 */