diff options
Diffstat (limited to 'qtools/qptrdict.doc')
| -rw-r--r-- | qtools/qptrdict.doc | 486 |
1 files changed, 486 insertions, 0 deletions
diff --git a/qtools/qptrdict.doc b/qtools/qptrdict.doc new file mode 100644 index 0000000..5a652d0 --- /dev/null +++ b/qtools/qptrdict.doc @@ -0,0 +1,486 @@ +/**************************************************************************** +** $Id$ +** +** QPtrDict and QPtrDictIterator class documentation +** +** Copyright (C) 1992-2000 Trolltech AS. All rights reserved. +** +** This file is part of the Qt GUI Toolkit. +** +** This file may be distributed under the terms of the Q Public License +** as defined by Trolltech AS of Norway and appearing in the file +** LICENSE.QPL included in the packaging of this file. +** +** This file may be distributed and/or modified under the terms of the +** GNU General Public License version 2 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. +** +** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition +** licenses may use this file in accordance with the Qt Commercial License +** Agreement provided with the Software. +** +** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +** +** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for +** information about Qt Commercial License Agreements. +** See http://www.trolltech.com/qpl/ for QPL licensing information. +** See http://www.trolltech.com/gpl/ for GPL licensing information. +** +** Contact info@trolltech.com if any conditions of this licensing are +** not clear to you. +** +**********************************************************************/ + + +/***************************************************************************** + QPtrDict documentation + *****************************************************************************/ + +/*! + \class QPtrDict qptrdict.h + \brief The QPtrDict class is a template class that provides a dictionary based on \c void* keys. + + \ingroup collection + \ingroup tools + + QPtrDict is implemented as a template class. Define a + template instance QPtrDict\<X\> to create a dictionary that operates on + pointers to X, or X*. + + A dictionary is a collection that associates an item with a key. + The key is used for inserting and looking up an item. QPtrDict has + \c void* keys. + + The dictionary has very fast insertion and lookup. + + Example: + \code + #include <qptrdict.h> + #include <stdio.h> + + void main() + { + int *a = new int[12]; + int *b = new int[10]; + int *c = new int[18]; + int *d = new int[13]; + + QPtrDict<char> dict; // maps void* -> char* + + dict.insert( a, "a is int[12]" ); // describe pointers + dict.insert( b, "b is int[10]" ); + dict.insert( c, "c is int[18]" ); + + printf( "%s\n", dict[a] ); // print descriptions + printf( "%s\n", dict[b] ); + printf( "%s\n", dict[c] ); + + if ( !dict[d] ) + printf( "d not in dictionary\n" ); + } + \endcode + + Program output: + \code + a is int[12] + b is int[10] + c is int[18] + d not in dictionary + \endcode + + The dictionary in our example maps \c int* keys to \c char* items. + QPtrDict implements the \link operator[] [] operator\endlink to lookup + an item. + + QPtrDict is implemented by QGDict as a hash array with a fixed number of + entries. Each array entry points to a singly linked list of buckets, in + which the dictionary items are stored. + + When an item is inserted with a key, the key is converted (hashed) to + an integer index into the hash array using the \c mod operation. The + item is inserted before the first bucket in the list of buckets. + + Looking up an item is normally very fast. The key is again hashed to an + array index. Then QPtrDict scans the list of buckets and returns the item + found or null if the item was not found. You cannot insert null pointers + into a dictionary. + + The size of the hash array is very important. In order to get good + performance, you should use a suitably large \link primes.html prime + number\endlink. Suitable means equal to or larger than the maximum + expected number of dictionary items. + + Items with equal keys are allowed. When inserting two items with the + same key, only the last inserted item will be visible (last in, first out) + until it is removed. + + Example: + \code + #include <qptrdict.h> + #include <stdio.h> + + void main() + { + QPtrDict<char> dict; // maps char* ==> char* + + double *ptr = new double[28]; + dict.insert( ptr, "first" ); + dict.insert( ptr, "second" ); + + printf( "%s\n", dict[ptr] ); + dict.remove( ptr ); + printf( "%s\n", dict[ptr] ); + } + \endcode + + Program output: + \code + second + first + \endcode + + The QPtrDictIterator class can traverse the dictionary contents, but only + in an arbitrary order. Multiple iterators may independently traverse the + same dictionary. + + Calling setAutoDelete(TRUE) for a dictionary tells it to delete items + that are removed . The default is to not delete items when they are + removed. + + When inserting an item into a dictionary, only the pointer is copied, not + the item itself. This is called a shallow copy. It is possible to make the + dictionary copy all of the item's data (known as a deep copy) when an + item is inserted. insert() calls the virtual function + QCollection::newItem() for the item to be inserted. + Inherit a dictionary and reimplement it if you want deep copies. + + When removing a dictionary item, the virtual function + QCollection::deleteItem() is called. QPtrDict's default implementation + is to delete the item if auto-deletion is enabled. + + \sa QPtrDictIterator, QDict, QAsciiDict, QIntDict, + \link collection.html Collection Classes\endlink +*/ + + +/*! + \fn QPtrDict::QPtrDict( int size ) + Constructs a dictionary using an internal hash array with the size + \e size. + + Setting \e size to a suitably large \link primes.html prime number\endlink + (equal to or greater than the expected number of entries) makes the hash + distribution better and hence the loopup faster. +*/ + +/*! + \fn QPtrDict::QPtrDict( const QPtrDict<type> &dict ) + Constructs a copy of \e dict. + + Each item in \e dict are inserted into this dictionary. + Only the pointers are copied (shallow copy). +*/ + +/*! + \fn QPtrDict::~QPtrDict() + Removes all items from the dictionary and destroys it. + + All iterators that access this dictionary will be reset. + + \sa setAutoDelete() +*/ + +/*! + \fn QPtrDict<type> &QPtrDict::operator=(const QPtrDict<type> &dict) + Assigns \e dict to this dictionary and returns a reference to this + dictionary. + + This dictionary is first cleared, then each item in \e dict is inserted + into this dictionary. + Only the pointers are copied (shallow copy), unless newItem() has been + reimplemented(). +*/ + +/*! + \fn uint QPtrDict::count() const + Returns the number of items in the dictionary. + \sa isEmpty() +*/ + +/*! + \fn uint QPtrDict::size() const + Returns the size of the internal hash array (as specified in the + constructor). + \sa count() +*/ + +/*! + \fn void QPtrDict::resize( uint newsize ) + Changes the size of the hashtable the \a newsize. + The contents of the dictionary are preserved, + but all iterators on the dictionary become invalid. +*/ + +/*! + \fn bool QPtrDict::isEmpty() const + Returns TRUE if the dictionary is empty, i.e. count() == 0. Returns FALSE + otherwise. + \sa count() +*/ + +/*! + \fn void QPtrDict::insert( void *key, const type *item ) + Inserts the \e key with the \e item into the dictionary. + + The key does not have to be a unique dictionary key. If multiple items + are inserted with the same key, only the last item will be visible. + + Null items are not allowed. + + \sa replace() +*/ + +/*! + \fn void QPtrDict::replace( void *key, const type *item ) + Replaces an item which has a key equal to \e key with \e item. + + If the item does not already exist, it will be inserted. + + Null items are not allowed. + + Equivalent to: + \code + QPtrDict<char> dict; + ... + if ( dict.find(key) ) + dict.remove( key ); + dict.insert( key, item ); + \endcode + + If there are two or more items with equal keys, then the last inserted + of these will be replaced. + + \sa insert() +*/ + +/*! + \fn bool QPtrDict::remove( void *key ) + Removes the item associated with \e key from the dictionary. + Returns TRUE if successful, or FALSE if the key does not exist in the + dictionary. + + If there are two or more items with equal keys, then the last inserted + of these will be removed. + + The removed item is deleted if \link QCollection::setAutoDelete() + auto-deletion\endlink is enabled. + + All dictionary iterators that refer to the removed item will be set to + point to the next item in the dictionary traversing order. + + \sa take(), clear(), setAutoDelete() +*/ + +/*! + \fn type *QPtrDict::take( void *key ) + Takes the item associated with \e key out of the dictionary without + deleting it (even if \link QCollection::setAutoDelete() + auto-deletion\endlink is enabled). + + If there are two or more items with equal keys, then the last inserted + of these will be taken. + + Returns a pointer to the item taken out, or null if the key does not + exist in the dictionary. + + All dictionary iterators that refer to the taken item will be set to + point to the next item in the dictionary traversing order. + + \sa remove(), clear(), setAutoDelete() +*/ + +/*! + \fn void QPtrDict::clear() + Removes all items from the dictionary. + + The removed items are deleted if \link QCollection::setAutoDelete() + auto-deletion\endlink is enabled. + + All dictionary iterators that access this dictionary will be reset. + + \sa remove(), take(), setAutoDelete() +*/ + +/*! + \fn type *QPtrDict::find( void *key ) const + Returns the item associated with \e key, or null if the key does not + exist in the dictionary. + + This function uses an internal hashing algorithm to optimize lookup. + + If there are two or more items with equal keys, then the last inserted + of these will be found. + + Equivalent to the [] operator. + + \sa operator[]() +*/ + +/*! + \fn type *QPtrDict::operator[]( void *key ) const + Returns the item associated with \e key, or null if the key does not + exist in the dictionary. + + This function uses an internal hashing algorithm to optimize lookup. + + If there are two or more items with equal keys, then the last inserted + of these will be found. + + Equivalent to the find() function. + + \sa find() +*/ + +/*! + \fn void QPtrDict::statistics() const + Debugging-only function that prints out the dictionary distribution + using qDebug(). +*/ + + +/***************************************************************************** + QPtrDictIterator documentation + *****************************************************************************/ + +/*! + \class QPtrDictIterator qptrdict.h + \brief The QPtrDictIterator class provides an iterator for QPtrDict collections. + + \ingroup collection + \ingroup tools + + QPtrDictIterator is implemented as a template class. + Define a template instance QPtrDictIterator\<X\> to create a + dictionary iterator that operates on QPtrDict\<X\> (dictionary of X*). + + Example: + \code + #include <qptrdict.h> + #include <stdio.h> + + void main() + { + int *a = new int[12]; + int *b = new int[10]; + int *c = new int[18]; + int *d = new int[13]; + + QPtrDict<char> dict; // maps void* -> char* + + dict.insert( a, "a is int[12]" ); // describe pointers + dict.insert( b, "b is int[10]" ); + dict.insert( c, "c is int[18]" ); + + QPtrDictIterator<char> it( dict ); // iterator for dict + + while ( it.current() ) { + printf( "%x -> %s\n", it.currentKey(), it.current() ); + ++it; + } + } + \endcode + + Program output: + \code + 804a788 -> a is int[12] + 804a7f0 -> c is int[18] + 804a7c0 -> b is int[10] + \endcode + + Note that the traversal order is arbitrary, you are not guaranteed the + order above. + + Multiple iterators may independently traverse the same dictionary. + A QPtrDict knows about all iterators that are operating on the dictionary. + When an item is removed from the dictionary, QPtrDict update all + iterators that are referring the removed item to point to the next item + in the traversing order. + + \sa QPtrDict, \link collection.html Collection Classes\endlink +*/ + +/*! + \fn QPtrDictIterator::QPtrDictIterator( const QPtrDict<type> &dict ) + Constructs an iterator for \e dict. The current iterator item is + set to point on the first item in the \e dict. +*/ + +/*! + \fn QPtrDictIterator::~QPtrDictIterator() + Destroys the iterator. +*/ + +/*! + \fn uint QPtrDictIterator::count() const + Returns the number of items in the dictionary this iterator operates on. + \sa isEmpty() +*/ + +/*! + \fn bool QPtrDictIterator::isEmpty() const + Returns TRUE if the dictionary is empty, i.e. count() == 0. Returns FALSE + otherwise. + \sa count() +*/ + +/*! + \fn type *QPtrDictIterator::toFirst() + Sets the current iterator item to point to the first item in the + dictionary and returns a pointer to the item. + If the dictionary is empty it sets the current item to null and + returns null. +*/ + +/*! + \fn QPtrDictIterator::operator type *() const + Cast operator. Returns a pointer to the current iterator item. + Same as current(). +*/ + +/*! + \fn type *QPtrDictIterator::current() const + Returns a pointer to the current iterator item. +*/ + +/*! + \fn void *QPtrDictIterator::currentKey() const + Returns the key for the current iterator item. +*/ + +/*! + \fn type *QPtrDictIterator::operator()() + Makes the succeeding item current and returns the original current item. + + If the current iterator item was the last item in the dictionary or if it + was null, null is returned. +*/ + +/*! + \fn type *QPtrDictIterator::operator++() + Prefix ++ makes the succeeding item current and returns the new current + item. + + If the current iterator item was the last item in the dictionary or if it + was null, null is returned. +*/ + +/*! + \fn type *QPtrDictIterator::operator+=( uint jump ) + Sets the current item to the item \e jump positions after the current item, + and returns a pointer to that item. + + If that item is beyond the last item or if the dictionary is empty, + it sets the current item to null and returns null. +*/ |