/****************************************************************************

**

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

** All rights reserved.

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

**

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

**

** $QT_BEGIN_LICENSE:FDL$

** Commercial Usage

** Licensees holding valid Qt Commercial licenses may use this file in

** accordance with the Qt Commercial License Agreement provided with the

** Software or, alternatively, in accordance with the terms contained in a

** written agreement between you and Nokia.

**

** GNU Free Documentation License

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

** Documentation License version 1.3 as published by the Free Software

** Foundation and appearing in the file included in the packaging of this

** file.

**

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

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

** $QT_END_LICENSE$

**

****************************************************************************/

/*!

    \class Q3PtrList

    \brief The Q3PtrList class is a template class that provides a list.

    \compat

    Q3ValueList is an STL-compatible alternative to this class.

    Define a template instance Q3PtrList\<X\> to create a list that

    operates on pointers to X (X*).

    The list class is indexable and has a \link at() current

    index\endlink and a \link current() current item\endlink. The

    first item corresponds to index position 0. The current index is

    -1 if the current item is 0.

    Items are inserted with prepend(), insert() or append(). Items are

    removed with remove(), removeRef(), removeFirst() and

    removeLast(). You can search for an item using find(), findNext(),

    findRef() or findNextRef(). The list can be sorted with sort().

    You can count the number of occurrences of an item with contains()

    or containsRef(). You can get a pointer to the current item with

    current(), to an item at a particular index position in the list

    with at() or to the first or last item with getFirst() and

    getLast(). You can also iterate over the list with first(),

    last(), next() and prev() (which all update current()). The list's

    deletion property is set with setAutoDelete().

    \target example

    Example:

    \snippet doc/src/snippets/code/doc_src_q3ptrlist.qdoc 0

    The output is

    \snippet doc/src/snippets/code/doc_src_q3ptrlist.qdoc 1

    Q3PtrList has several member functions for traversing the list, but

    using a Q3PtrListIterator can be more practical. Multiple list

    iterators may traverse the same list, independently of each other

    and of the current list item.

    In the example above we make the call setAutoDelete(true).

    Enabling auto-deletion tells the list to delete items that are

    removed. The default is to not delete items when they are removed

    but this would cause a memory leak in the example because there

    are no other references to the list items.

    When inserting an item into a list only the pointer is copied, not

    the item itself, i.e. a shallow copy. It is possible to make the

    list copy all of the item's data (deep copy) when an item is

    inserted. insert(), inSort() and append() call the virtual

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

    Inherit a list and reimplement newItem() to have deep copies.

    When removing an item from a list, the virtual function

    Q3PtrCollection::deleteItem() is called. Q3PtrList's default

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

    The virtual function compareItems() can be reimplemented to

    compare two list items. This function is called from all list

    functions that need to compare list items, for instance

    remove(const type*). If you only want to deal with pointers, there

    are functions that compare pointers instead, for instance

    removeRef(const type*). These functions are somewhat faster than

    those that call compareItems().

    List items are stored as \c void* in an internal Q3LNode, which

    also holds pointers to the next and previous list items. The

    functions currentNode(), removeNode(), and takeNode() operate

    directly on the Q3LNode, but they should be used with care. The

    data component of the node is available through Q3LNode::getData().

    The Q3StrList class is a list of \c char*.

    It reimplements newItem(), deleteItem() and compareItems(). (But

    see QStringList for a list of Unicode QStrings.)

    \sa Q3PtrListIterator

*/

/*!

    \fn Q3PtrList::Q3PtrList()

    Constructs an empty list.

*/

/*!

    \fn Q3PtrList::Q3PtrList( const Q3PtrList<type> &list )

    Constructs a copy of \a list.

    Each item in \a list is \link append() appended\endlink to this

    list. Only the pointers are copied (shallow copy).

*/

/*!

    \fn Q3PtrList::~Q3PtrList()

    Removes all items from the list and destroys the list.

    All list iterators that access this list will be reset.

    \sa setAutoDelete()

*/

/*!

    \fn Q3PtrList<type> &Q3PtrList::operator=(const Q3PtrList<type> &list)

    Assigns \a list to this list and returns a reference to this list.

    This list is first cleared and then each item in \a list is \link

    append() appended\endlink to this list. Only the pointers are

    copied (shallow copy) unless newItem() has been reimplemented.

*/

/*!

    \fn bool Q3PtrList::operator==(const Q3PtrList<type> &list ) const

    Compares this list with \a list. Returns TRUE if the lists contain

    the same data; otherwise returns FALSE.

*/

/*!

    \fn uint Q3PtrList::count() const

    Returns the number of items in the list.

    \sa isEmpty()

*/

/*!

    \fn bool Q3PtrList::operator!=(const Q3PtrList<type> &list ) const

    Compares this list with \a list. Returns TRUE if the lists contain

    different data; otherwise returns FALSE.

*/

/*!

    \fn void Q3PtrList::sort()

    Sorts the list by the result of the virtual compareItems()

    function.

    The heap sort algorithm is used for sorting. It sorts n items with

    O(n*log n) comparisons. This is the asymptotic optimal solution of

    the sorting problem.

    If the items in your list support operator<() and operator==(),

    you might be better off with Q3SortedList because it implements the

    compareItems() function for you using these two operators.

    \sa inSort()

*/

/*!

    \fn bool Q3PtrList::isEmpty() const

    Returns TRUE if the list is empty; otherwise returns FALSE.

    \sa count()

*/

/*!

    \fn bool Q3PtrList::insert( uint index, const type *item )

    Inserts the \a item at position \a index in the list.

    Returns TRUE if successful, i.e. if \a index is in range;

    otherwise returns FALSE. The valid range is 0 to count()

    (inclusively). The item is appended if \a index == count().

    The inserted item becomes the current list item.

    \a item must not be 0.

    \sa append(), current(), replace()

*/

/*!

    \fn bool Q3PtrList::replace( uint index, const type *item )

    Replaces the item at position \a index with the new \a item. 

    Returns TRUE if successful, i.e. \a index is in the range 0 to

    count()-1.

    \sa append(), current(), insert()

*/

/*!

    \fn void Q3PtrList::inSort( const type *item )

    Inserts the \a item at its sorted position in the list.

    The sort order depends on the virtual compareItems() function. All

    items must be inserted with inSort() to maintain the sorting

    order.

    The inserted item becomes the current list item.

    \a item must not be 0.

    \warning Using inSort() is slow. An alternative, especially if you

    have lots of items, is to simply append() or insert() them and

    then use sort(). inSort() takes up to O(n) compares. That means

    inserting n items in your list will need O(n^2) compares whereas

    sort() only needs O(n*log n) for the same task. So use inSort()

    only if you already have a presorted list and want to insert just

    a few additional items.

    \sa insert(), compareItems(), current(), sort()

*/

/*!

    \fn void Q3PtrList::append( const type *item )

    Inserts the \a item at the end of the list.

    The inserted item becomes the current list item. This is

    equivalent to \c{insert( count(), item )}.

    \a item must not be 0.

    \sa insert(), current(), prepend()

*/

/*!

    \fn void Q3PtrList::prepend( const type *item )

    Inserts the \a item at the start of the list.

    The inserted item becomes the current list item. This is

    equivalent to \c{insert( 0, item )}.

    \a item must not be 0.

    \sa append(), insert(), current()

*/

/*!

    \fn bool Q3PtrList::remove( uint index )

    Removes the item at position \a index in the list.

    Returns TRUE if successful, i.e. if \a index is in range;

    otherwise returns FALSE. The valid range is \c{0..(count() - 1)}

    inclusive.

    The removed item is deleted if \link setAutoDelete()

    auto-deletion\endlink is enabled.

    The item after the removed item becomes the new current list item

    if the removed item is not the last item in the list. If the last

    item is removed, the new last item becomes the current item.

    All list iterators that refer to the removed item will be set to

    point to the new current item.

    \sa take(), clear(), setAutoDelete(), current() removeRef()

*/

/*!

    \fn bool Q3PtrList::remove()

    \overload

    Removes the current list item.

    Returns TRUE if successful, i.e. if the current item isn't 0;

    otherwise returns FALSE.

    The removed item is deleted if \link setAutoDelete()

    auto-deletion\endlink is enabled.

    The item after the removed item becomes the new current list item

    if the removed item is not the last item in the list. If the last

    item is removed, the new last item becomes the current item. The

    current item is set to 0 if the list becomes empty.

    All list iterators that refer to the removed item will be set to

    point to the new current item.

    \sa take(), clear(), setAutoDelete(), current() removeRef()

*/

/*!

    \fn bool Q3PtrList::remove( const type *item )

    \overload

    Removes the first occurrence of \a item from the list.

    Returns TRUE if successful, i.e. if \a item is in the list;

    otherwise returns FALSE.

    The removed item is deleted if \link setAutoDelete()

    auto-deletion\endlink is enabled.

    The compareItems() function is called when searching for the item

    in the list. If compareItems() is not reimplemented, it is more

    efficient to call removeRef().

    If \a item is NULL then the current item is removed from the list.

    The item after the removed item becomes the new current list item

    if the removed item is not the last item in the list. If the last

    item is removed, the new last item becomes the current item. The

    current item is set to 0 if the list becomes empty.

    All list iterators that refer to the removed item will be set to

    point to the new current item.

    \sa removeRef(), take(), clear(), setAutoDelete(), compareItems(),

    current()

*/

/*!

    \fn bool Q3PtrList::removeRef( const type *item )

    Removes the first occurrence of \a item from the list.

    Returns TRUE if successful, i.e. if \a item is in the list;

    otherwise returns FALSE.

    The removed item is deleted if \link setAutoDelete()

    auto-deletion\endlink is enabled.

    Equivalent to:

    \snippet doc/src/snippets/code/doc_src_q3ptrlist.qdoc 2

    The item after the removed item becomes the new current list item

    if the removed item is not the last item in the list. If the last

    item is removed, the new last item becomes the current item. The

    current item is set to 0 if the list becomes empty.

    All list iterators that refer to the removed item will be set to

    point to the new current item.

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

*/

/*!

    \fn void Q3PtrList::removeNode( Q3LNode *node )

    Removes the \a node from the list.

    This node must exist in the list, otherwise the program may crash.

    The removed item is deleted if \link setAutoDelete()

    auto-deletion\endlink is enabled.

    The first item in the list will become the new current list item.

    The current item is set to 0 if the list becomes empty.

    All list iterators that refer to the removed item will be set to

    point to the item succeeding this item or to the preceding item if

    the removed item was the last item.

    \warning Do not call this function unless you are an expert.

    \sa takeNode(), currentNode() remove() removeRef()

*/

/*!

    \fn bool Q3PtrList::removeFirst()

    Removes the first item from the list. Returns TRUE if successful,

    i.e. if the list isn't empty; otherwise returns FALSE.

    The removed item is deleted if \link setAutoDelete()

    auto-deletion\endlink is enabled.

    The first item in the list becomes the new current list item. The

    current item is set to 0 if the list becomes empty.

    All list iterators that refer to the removed item will be set to

    point to the new current item.

    \sa removeLast(), setAutoDelete(), current() remove()

*/

/*!

    \fn bool Q3PtrList::removeLast()

    Removes the last item from the list. Returns TRUE if successful,

    i.e. if the list isn't empty; otherwise returns FALSE.

    The removed item is deleted if \link setAutoDelete()

    auto-deletion\endlink is enabled.

    The last item in the list becomes the new current list item. The

    current item is set to 0 if the list becomes empty.

    All list iterators that refer to the removed item will be set to

    point to the new current item.

    \sa removeFirst(), setAutoDelete(), current()

*/

/*!

    \fn type *Q3PtrList::take( uint index )

    Takes the item at position \a index out of the list without

    deleting it (even if \link setAutoDelete() auto-deletion\endlink

    is enabled).

    Returns a pointer to the item taken out of the list, or 0 if the

    index is out of range. The valid range is \c{0..(count() - 1)}

    inclusive.

    The item after the removed item becomes the new current list item

    if the removed item is not the last item in the list. If the last

    item is removed, the new last item becomes the current item. The

    current item is set to 0 if the list becomes empty.

    All list iterators that refer to the taken item will be set to

    point to the new current item.

    \sa remove(), clear(), current()

*/

/*!

    \fn type *Q3PtrList::take()

    \overload

    Takes the current item out of the list without deleting it (even

    if \link setAutoDelete() auto-deletion\endlink is enabled).

    Returns a pointer to the item taken out of the list, or 0 if

    the current item is 0.

    The item after the removed item becomes the new current list item

    if the removed item is not the last item in the list. If the last

    item is removed, the new last item becomes the current item. The

    current item is set to 0 if the list becomes empty.

    All list iterators that refer to the taken item will be set to

    point to the new current item.

    \sa remove(), clear(), current()

*/

/*!

    \fn type *Q3PtrList::takeNode( Q3LNode *node )

    Takes the \a node out of the list without deleting its item (even

    if \link setAutoDelete() auto-deletion\endlink is enabled).

    Returns a pointer to the item taken out of the list.

    This node must exist in the list, otherwise the program may crash.

    The first item in the list becomes the new current list item.

    All list iterators that refer to the taken item will be set to

    point to the item succeeding this item or to the preceding item if

    the taken item was the last item.

    \warning Do not call this function unless you are an expert.

    \sa removeNode(), currentNode()

*/

/*!

    \fn void Q3PtrList::clear()

    Removes all items from the list.

    The removed items are deleted if \link setAutoDelete()

    auto-deletion\endlink is enabled.

    All list iterators that access this list will be reset.

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

*/

/*!

    \fn int Q3PtrList::find( const type *item )

    Finds the first occurrence of \a item in the list.

    If the item is found, the list sets the current item to point to

    the found item and returns the index of this item. If the item is

    not found, the list sets the current item to 0, the current

    index to -1, and returns -1.

    The compareItems() function is called when searching for the item

    in the list. If compareItems() is not reimplemented, it is more

    efficient to call findRef().

    \sa findNext(), findRef(), compareItems(), current()

*/

/*!

    \fn int Q3PtrList::findNext( const type *item )

    Finds the next occurrence of \a item in the list, starting from

    the current list item.

    If the item is found, the list sets the current item to point to

    the found item and returns the index of this item. If the item is