Long live Qt 4.5!

1 files changed, 648 insertions, 0 deletions

diff --git a/doc/src/qalgorithms.qdoc b/doc/src/qalgorithms.qdoc
new file mode 100644
index 0000000..459fb81
--- /dev/null
+++ b/doc/src/qalgorithms.qdoc
@@ -0,0 +1,648 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the documentation of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain
+** additional rights. These rights are described in the Nokia Qt LGPL
+** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@nokia.com.
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+/*!
+    \headerfile <QtAlgorithms>
+    \title Generic Algorithms
+    \ingroup architecture
+
+    \brief The <QtAlgorithms> header provides generic template-based algorithms.
+
+    Qt provides a number of global template functions in \c
+    <QtAlgorithms> that work on containers and perform well-know
+    algorithms. You can use these algorithms with any \l {container
+    class} that provides STL-style iterators, including Qt's QList,
+    QLinkedList, QVector, QMap, and QHash classes.
+
+    These functions have taken their inspiration from similar
+    functions available in the STL \c <algorithm> header. Most of them
+    have a direct STL equivalent; for example, qCopyBackward() is the
+    same as STL's copy_backward() algorithm.
+
+    If STL is available on all your target platforms, you can use the
+    STL algorithms instead of their Qt counterparts. One reason why
+    you might want to use the the STL algorithms is that STL provides
+    dozens and dozens of algorithms, whereas Qt only provides the most
+    important ones, making no attempt to duplicate functionality that
+    is already provided by the C++ standard.
+
+    Most algorithms take \l {STL-style iterators} as parameters. The
+    algorithms are generic in the sense that they aren't bound to a
+    specific iterator class; you can use them with any iterators that
+    meet a certain set of requirements.
+
+    Let's take the qFill() algorithm as an example. Unlike QVector,
+    QList has no fill() function that can be used to fill a list with
+    a particular value. If you need that functionality, you can use
+    qFill():
+
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 0
+
+    qFill() takes a begin iterator, an end iterator, and a value.
+    In the example above, we pass \c list.begin() and \c list.end()
+    as the begin and end iterators, but this doesn't have to be
+    the case:
+
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 1
+
+    Different algorithms can have different requirements for the
+    iterators they accept. For example, qFill() accepts two 
+    \l {forward iterators}. The iterator types required are specified
+    for each algorithm. If an iterator of the wrong type is passed (for
+    example, if QList::ConstIterator is passed as an \l {output
+    iterator}), you will always get a compiler error, although not
+    necessarily a very informative one.
+
+    Some algorithms have special requirements on the value type
+    stored in the containers. For example, qEqual() requires that the
+    value type supports operator==(), which it uses to compare items.
+    Similarly, qDeleteAll() requires that the value type is a
+    non-const pointer type (for example, QWidget *). The value type
+    requirements are specified for each algorithm, and the compiler
+    will produce an error if a requirement isn't met.
+
+    \target binaryFind example
+
+    The generic algorithms can be used on other container classes
+    than those provided by Qt and STL. The syntax of STL-style
+    iterators is modeled after C++ pointers, so it's possible to use
+    plain arrays as containers and plain pointers as iterators. A
+    common idiom is to use qBinaryFind() together with two static
+    arrays: one that contains a list of keys, and another that
+    contains a list of associated values. For example, the following
+    code will look up an HTML entity (e.g., \c &amp;) in the \c
+    name_table array and return the corresponding Unicode value from
+    the \c value_table if the entity is recognized:
+
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 2
+
+    This kind of code is for advanced users only; for most
+    applications, a QMap- or QHash-based approach would work just as
+    well:
+
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 3
+
+    \section1 Types of Iterators
+
+    The algorithms have certain requirements on the iterator types
+    they accept, and these are specified individually for each
+    function. The compiler will produce an error if a requirement
+    isn't met.
+
+    \section2 Input Iterators
+
+    An \e{input iterator} is an iterator that can be used for reading
+    data sequentially from a container. It must provide the following
+    operators: \c{==} and \c{!=} for comparing two iterators, unary
+    \c{*} for retrieving the value stored in the item, and prefix
+    \c{++} for advancing to the next item.
+
+    The Qt containers' iterator types (const and non-const) are all
+    input iterators.
+
+    \section2 Output Iterators
+
+    An \e{output iterator} is an iterator that can be used for
+    writing data sequentially to a container or to some output
+    stream. It must provide the following operators: unary \c{*} for
+    writing a value (i.e., \c{*it = val}) and prefix \c{++} for
+    advancing to the next item.
+
+    The Qt containers' non-const iterator types are all output
+    iterators.
+
+    \section2 Forward Iterators
+
+    A \e{forward iterator} is an iterator that meets the requirements
+    of both input iterators and output iterators.
+
+    The Qt containers' non-const iterator types are all forward
+    iterators.
+
+    \section2 Bidirectional Iterators
+
+    A \e{bidirectional iterator} is an iterator that meets the
+    requirements of forward iterators but that in addition supports
+    prefix \c{--} for iterating backward.
+
+    The Qt containers' non-const iterator types are all bidirectional
+    iterators.
+
+    \section2 Random Access Iterators
+
+    The last category, \e{random access iterators}, is the most
+    powerful type of iterator. It supports all the requirements of a
+    bidirectional iterator, and supports the following operations:
+
+    \table
+    \row \i \c{i += n} \i advances iterator \c i by \c n positions
+    \row \i \c{i -= n} \i moves iterator \c i back by \c n positions
+    \row \i \c{i + n} or \c{n + i} \i returns the iterator for the item \c
+       n positions ahead of iterator \c i
+    \row \i \c{i - n} \i returns the iterator for the item \c n positions behind of iterator \c i
+    \row \i \c{i - j} \i returns the number of items between iterators \c i and \c j
+    \row \i \c{i[n]} \i same as \c{*(i + n)}
+    \row \i \c{i < j} \i returns true if iterator \c j comes after iterator \c i
+    \endtable
+
+    QList and QVector's non-const iterator types are random access iterators.
+
+    \sa {container classes}, <QtGlobal>
+*/
+
+/*! \fn OutputIterator qCopy(InputIterator begin1, InputIterator end1, OutputIterator begin2)
+    \relates <QtAlgorithms>
+
+    Copies the items from range [\a begin1, \a end1) to range [\a
+    begin2, ...), in the order in which they appear.
+
+    The item at position \a begin1 is assigned to that at position \a
+    begin2; the item at position \a begin1 + 1 is assigned to that at
+    position \a begin2 + 1; and so on.
+
+    Example:
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 4
+
+    \sa qCopyBackward(), {input iterators}, {output iterators}
+*/
+
+/*! \fn BiIterator2 qCopyBackward(BiIterator1 begin1, BiIterator1 end1, BiIterator2 end2)
+    \relates <QtAlgorithms>
+
+    Copies the items from range [\a begin1, \a end1) to range [...,
+    \a end2).
+
+    The item at position \a end1 - 1 is assigned to that at position
+    \a end2 - 1; the item at position \a end1 - 2 is assigned to that
+    at position \a end2 - 2; and so on.
+
+    Example:
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 5
+
+    \sa qCopy(), {bidirectional iterators}
+*/
+
+/*! \fn bool qEqual(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
+    \relates <QtAlgorithms>
+
+    Compares the items in the range [\a begin1, \a end1) with the
+    items in the range [\a begin2, ...). Returns true if all the
+    items compare equal; otherwise returns false.
+
+    Example:
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 6
+
+    This function requires the item type (in the example above,
+    QString) to implement \c operator==().
+
+    \sa {input iterators}
+*/
+
+/*! \fn void qFill(ForwardIterator begin, ForwardIterator end, const T &value)
+    \relates <QtAlgorithms>
+
+    Fills the range [\a begin, \a end) with \a value.
+
+    Example:
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 7
+
+    \sa qCopy(), {forward iterators}
+*/
+
+/*! \fn void qFill(Container &container, const T &value)
+    \relates <QtAlgorithms>
+
+    \overload
+
+    This is the same as qFill(\a{container}.begin(), \a{container}.end(), \a value);
+*/
+
+/*! \fn InputIterator qFind(InputIterator begin, InputIterator end, const T &value)
+    \relates <QtAlgorithms>
+
+    Returns an iterator to the first occurrence of \a value in a
+    container in the range [\a begin, \a end). Returns \a end if \a
+    value isn't found.
+
+    Example:
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 8
+
+    This function requires the item type (in the example above,
+    QString) to implement \c operator==().
+
+    If the items in the range are in ascending order, you can get
+    faster results by using qLowerBound() or qBinaryFind() instead of
+    qFind().
+
+    \sa qBinaryFind(), {input iterators}
+*/
+
+/*! \fn void qFind(const Container &container, const T &value)
+    \relates <QtAlgorithms>
+
+    \overload
+
+    This is the same as qFind(\a{container}.begin(), \a{container}.end(), value);
+*/
+
+/*! \fn void qCount(InputIterator begin, InputIterator end, const T &value, Size &n)
+    \relates <QtAlgorithms>
+
+    Returns the number of occurrences of \a value in the range [\a begin, \a end),
+    which is returned in \a n. \a n is never initialized, the count is added to \a n.
+    It is the caller's responsibility to initialize \a n.
+
+    Example:
+
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 9
+
+    This function requires the item type (in the example above,
+    \c int) to implement \c operator==().
+
+    \sa {input iterators}
+*/
+
+/*! \fn void qCount(const Container &container, const T &value, Size &n)
+\relates <QtAlgorithms>
+
+\overload
+
+Instead of operating on iterators, as in the other overload, this function
+operates on the specified \a container to obtain the number of instances
+of \a value in the variable passed as a reference in argument \a n.
+*/
+
+/*! \fn void qSwap(T &var1, T &var2)
+    \relates <QtAlgorithms>
+
+    Exchanges the values of variables \a var1 and \a var2.
+
+    Example:
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 10
+*/
+
+/*! \fn void qSort(RandomAccessIterator begin, RandomAccessIterator end)
+    \relates <QtAlgorithms>
+
+    Sorts the items in range [\a begin, \a end) in ascending order
+    using the quicksort algorithm.
+
+    Example:
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 11
+
+    The sort algorithm is efficient on large data sets. It operates
+    in \l {linear-logarithmic time}, O(\e{n} log \e{n}).
+
+    This function requires the item type (in the example above,
+    \c{int}) to implement \c operator<().
+
+    If neither of the two items is "less than" the other, the items are
+    taken to be equal. It is then undefined which one of the two
+    items will appear before the other after the sort.
+
+    \sa qStableSort(), {random access iterators}
+*/
+
+/*! \fn void qSort(RandomAccessIterator begin, RandomAccessIterator end, LessThan lessThan)
+    \relates <QtAlgorithms>
+
+    \overload
+
+    Uses the \a lessThan function instead of \c operator<() to
+    compare the items.
+
+    For example, here's how to sort the strings in a QStringList
+    in case-insensitive alphabetical order:
+
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 12
+
+    To sort values in reverse order, pass
+    \l{qGreater()}{qGreater<T>()} as the \a lessThan parameter. For
+    example:
+
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 13
+
+    If neither of the two items is "less than" the other, the items are
+    taken to be equal. It is then undefined which one of the two
+    items will appear before the other after the sort.
+
+    An alternative to using qSort() is to put the items to sort in a
+    QMap, using the sort key as the QMap key. This is often more
+    convenient than defining a \a lessThan function. For example, the
+    following code shows how to sort a list of strings case
+    insensitively using QMap:
+
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 14
+
+    \sa QMap
+*/
+
+/*! \fn void qSort(Container &container)
+    \relates <QtAlgorithms>
+
+    \overload
+
+    This is the same as qSort(\a{container}.begin(), \a{container}.end());
+*/
+
+/*! 
+    \fn void qStableSort(RandomAccessIterator begin, RandomAccessIterator end)
+    \relates <QtAlgorithms>
+
+    Sorts the items in range [\a begin, \a end) in ascending order
+    using a stable sorting algorithm.
+
+    If neither of the two items is "less than" the other, the items are
+    taken to be equal. The item that appeared before the other in the
+    original container will still appear first after the sort. This
+    property is often useful when sorting user-visible data.
+
+    Example:
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 15
+
+    The sort algorithm is efficient on large data sets. It operates
+    in \l {linear-logarithmic time}, O(\e{n} log \e{n}).
+
+    This function requires the item type (in the example above,
+    \c{int}) to implement \c operator<().
+
+    \sa qSort(), {random access iterators}
+*/
+
+/*! 
+    \fn void qStableSort(RandomAccessIterator begin, RandomAccessIterator end, LessThan lessThan)
+    \relates <QtAlgorithms>
+
+    \overload
+
+    Uses the \a lessThan function instead of \c operator<() to
+    compare the items.
+
+    For example, here's how to sort the strings in a QStringList
+    in case-insensitive alphabetical order:
+
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 16
+    
+    Note that earlier versions of Qt allowed using a lessThan function that took its
+    arguments by non-const reference. From 4.3 and on this is no longer possible,
+    the arguments has to be passed by const reference or value.
+
+    To sort values in reverse order, pass
+    \l{qGreater()}{qGreater<T>()} as the \a lessThan parameter. For
+    example:
+
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 17
+
+    If neither of the two items is "less than" the other, the items are
+    taken to be equal. The item that appeared before the other in the
+    original container will still appear first after the sort. This
+    property is often useful when sorting user-visible data.
+*/
+
+/*! 
+    \fn void qStableSort(Container &container)
+    \relates <QtAlgorithms>
+
+    \overload
+
+    This is the same as qStableSort(\a{container}.begin(), \a{container}.end());
+*/
+
+/*! \fn RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
+    \relates <QtAlgorithms>
+
+    Performs a binary search of the range [\a begin, \a end) and
+    returns the position of the first ocurrence of \a value. If no
+    such item is found, returns the position where it should be
+    inserted.
+
+    The items in the range [\a begin, \e end) must be sorted in
+    ascending order; see qSort().
+
+    Example:
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 18
+
+    This function requires the item type (in the example above,
+    \c{int}) to implement \c operator<().
+
+    qLowerBound() can be used in conjunction with qUpperBound() to
+    iterate over all occurrences of the same value:
+
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 19
+
+    \sa qUpperBound(), qBinaryFind()
+*/
+
+/*!
+    \fn RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
+    \relates <QtAlgorithms>
+
+    \overload
+
+    Uses the \a lessThan function instead of \c operator<() to
+    compare the items.
+
+    Note that the items in the range must be sorted according to the order
+    specified by the \a lessThan object.
+*/
+
+/*! 
+    \fn void qLowerBound(const Container &container, const T &value)
+    \relates <QtAlgorithms>
+
+    \overload
+
+    This is the same as qLowerBound(\a{container}.begin(), \a{container}.end(), value);
+*/
+
+/*! \fn RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
+    \relates <QtAlgorithms>
+
+    Performs a binary search of the range [\a begin, \a end) and
+    returns the position of the one-past-the-last occurrence of \a
+    value. If no such item is found, returns the position where the
+    item should be inserted.
+
+    The items in the range [\a begin, \e end) must be sorted in
+    ascending order; see qSort().
+
+    Example:
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 20
+
+    This function requires the item type (in the example above,
+    \c{int}) to implement \c operator<().
+
+    qUpperBound() can be used in conjunction with qLowerBound() to
+    iterate over all occurrences of the same value:
+
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 21
+
+    \sa qLowerBound(), qBinaryFind()
+*/
+
+/*!
+    \fn RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
+    \relates <QtAlgorithms>
+
+    \overload
+
+    Uses the \a lessThan function instead of \c operator<() to
+    compare the items.
+
+    Note that the items in the range must be sorted according to the order
+    specified by the \a lessThan object.
+*/
+
+/*! 
+    \fn void qUpperBound(const Container &container, const T &value)
+    \relates <QtAlgorithms>
+
+    \overload
+
+    This is the same as qUpperBound(\a{container}.begin(), \a{container}.end(), value);
+*/
+
+
+/*! \fn RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
+    \relates <QtAlgorithms>
+
+    Performs a binary search of the range [\a begin, \a end) and
+    returns the position of an occurrence of \a value. If there are
+    no occurrences of \a value, returns \a end.
+
+    The items in the range [\a begin, \a end) must be sorted in
+    ascending order; see qSort().
+
+    If there are many occurrences of the same value, any one of them
+    could be returned. Use qLowerBound() or qUpperBound() if you need
+    finer control.
+
+    Example:
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 22
+
+    This function requires the item type (in the example above,
+    QString) to implement \c operator<().
+
+    See the \l{<QtAlgorithms>#binaryFind example}{detailed
+    description} for an example usage.
+
+    \sa qLowerBound(), qUpperBound(), {random access iterators}
+*/
+
+/*! \fn RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
+    \relates <QtAlgorithms>
+
+    \overload
+
+    Uses the \a lessThan function instead of \c operator<() to
+    compare the items.
+
+    Note that the items in the range must be sorted according to the order
+    specified by the \a lessThan object.
+*/
+
+/*! 
+    \fn void qBinaryFind(const Container &container, const T &value)
+    \relates <QtAlgorithms>
+
+    \overload
+
+    This is the same as qBinaryFind(\a{container}.begin(), \a{container}.end(), value);
+*/
+
+
+/*! 
+    \fn void qDeleteAll(ForwardIterator begin, ForwardIterator end)
+    \relates <QtAlgorithms>
+
+    Deletes all the items in the range [\a begin, \a end) using the
+    C++ \c delete operator. The item type must be a pointer type (for
+    example, \c{QWidget *}).
+
+    Example:
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 23
+
+    Notice that qDeleteAll() doesn't remove the items from the
+    container; it merely calls \c delete on them. In the example
+    above, we call clear() on the container to remove the items.
+
+    This function can also be used to delete items stored in
+    associative containers, such as QMap and QHash. Only the objects
+    stored in each container will be deleted by this function; objects
+    used as keys will not be deleted.
+
+    \sa {forward iterators}
+*/
+
+/*! 
+    \fn void qDeleteAll(const Container &c)
+    \relates <QtAlgorithms>
+
+    \overload
+
+    This is the same as qDeleteAll(\a{c}.begin(), \a{c}.end()).
+*/
+
+/*! \fn LessThan qLess()
+    \relates <QtAlgorithms>
+
+    Returns a functional object, or functor, that can be passed to qSort()
+    or qStableSort().
+
+    Example:
+
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 24
+
+    \sa {qGreater()}{qGreater<T>()}
+*/
+
+/*! \fn LessThan qGreater()
+    \relates <QtAlgorithms>
+
+    Returns a functional object, or functor, that can be passed to qSort()
+    or qStableSort().
+
+    Example:
+
+    \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 25
+
+    \sa {qLess()}{qLess<T>()}
+*/