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

**

** 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 QSet

    \brief The QSet class is a template class that provides a hash-table-based set.

    \ingroup tools

    \ingroup shared

    \reentrant

    QSet<T> is one of Qt's generic \l{container classes}. It stores

    values in an unspecified order and provides very fast lookup of

    the values. Internally, QSet<T> is implemented as a QHash.

    Here's an example QSet with QString values:

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

    To insert a value into the set, use insert():

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

    Another way to insert items into the set is to use operator<<():

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

    To test whether an item belongs to the set or not, use contains():

    \snippet doc/src/snippets/code/doc_src_qset.qdoc 3

    If you want to navigate through all the values stored in a QSet,

    you can use an iterator. QSet supports both \l{Java-style

    iterators} (QSetIterator and QMutableSetIterator) and \l{STL-style

    iterators} (QSet::iterator and QSet::const_iterator). Here's how

    to iterate over a QSet<QWidget *> using a Java-style iterator:

    \snippet doc/src/snippets/code/doc_src_qset.qdoc 4

    Here's the same code, but using an STL-style iterator:

    \snippet doc/src/snippets/code/doc_src_qset.qdoc 5

    QSet is unordered, so an iterator's sequence cannot be assumed to

    be predictable. If ordering by key is required, use a QMap.

    To navigate through a QSet, you can also use \l{foreach}:

    \snippet doc/src/snippets/code/doc_src_qset.qdoc 6

    Items can be removed from the set using remove(). There is also a

    clear() function that removes all items.

    QSet's value data type must be an \l{assignable data type}. You

    cannot, for example, store a QWidget as a value; instead, store a

    QWidget *. In addition, the type must provide \c operator==(), and

    there must also be a global qHash() function that returns a hash

    value for an argument of the key's type. See the QHash

    documentation for a list of types supported by qHash().

    Internally, QSet uses a hash table to perform lookups. The hash

    table automatically grows and shrinks to provide fast lookups

    without wasting memory. You can still control the size of the hash

    table by calling reserve(), if you already know approximately how

    many elements the QSet will contain, but this isn't necessary to

    obtain good performance. You can also call capacity() to retrieve

    the hash table's size.

    \sa QSetIterator, QMutableSetIterator, QHash, QMap

*/

/*!

    \fn QSet::QSet()

    Constructs an empty set.

    \sa clear()

*/

/*!

    \fn QSet::QSet(const QSet<T> &other)

    Constructs a copy of \a other.

    This operation occurs in \l{constant time}, because QSet is

    \l{implicitly shared}. This makes returning a QSet from a

    function very fast. If a shared instance is modified, it will be

    copied (copy-on-write), and this takes \l{linear time}.

    \sa operator=()

*/

/*!

    \fn QSet<T> &QSet::operator=(const QSet<T> &other)

    Assigns the \a other set to this set and returns a reference to

    this set.  

*/

/*!

    \fn bool QSet::operator==(const QSet<T> &other) const

    Returns true if the \a other set is equal to this set; otherwise

    returns false.

    Two sets are considered equal if they contain the same elements.

    This function requires the value type to implement \c operator==().

    \sa operator!=()

*/

/*!

    \fn bool QSet::operator!=(const QSet<T> &other) const

    Returns true if the \a other set is not equal to this set; otherwise

    returns false.

    Two sets are considered equal if they contain the same elements.

    This function requires the value type to implement \c operator==().

    \sa operator==()

*/

/*!

    \fn int QSet::size() const

    Returns the number of items in the set.

    \sa isEmpty(), count()

*/

/*!

    \fn bool QSet::isEmpty() const

    Returns true if the set contains no elements; otherwise returns

    false.

    \sa size()

*/

/*!

    \fn int QSet::capacity() const

    Returns the number of buckets in the set's internal hash

    table.

    The sole purpose of this function is to provide a means of fine

    tuning QSet's memory usage. In general, you will rarely ever need

    to call this function. If you want to know how many items are in

    the set, call size().

    \sa reserve(), squeeze()

*/

/*! \fn void QSet::reserve(int size)

    Ensures that the set's internal hash table consists of at

    least \a size buckets.

    This function is useful for code that needs to build a huge set

    and wants to avoid repeated reallocation. For example:

    \snippet doc/src/snippets/code/doc_src_qset.qdoc 7

    Ideally, \a size should be slightly more than the maximum number

    of elements expected in the set. \a size doesn't have to be prime,

    because QSet will use a prime number internally anyway. If \a size

    is an underestimate, the worst that will happen is that the QSet

    will be a bit slower.

    In general, you will rarely ever need to call this function.

    QSet's internal hash table automatically shrinks or grows to

    provide good performance without wasting too much memory.

    \sa squeeze(), capacity()

*/

/*!

    \fn void QSet::squeeze()

    Reduces the size of the set's internal hash table to save

    memory.

    The sole purpose of this function is to provide a means of fine

    tuning QSet's memory usage. In general, you will rarely ever

    need to call this function.

    \sa reserve(), capacity()

*/

/*!

    \fn void QSet::detach()

    \internal

    Detaches this set from any other sets with which it may share

    data.

    \sa isDetached()

*/

/*! \fn bool QSet::isDetached() const

    \internal

    Returns true if the set's internal data isn't shared with any

    other set object; otherwise returns false.

    \sa detach()

*/

/*!

    \fn void QSet::setSharable(bool sharable)

    \internal

*/

/*!

    \fn void QSet::clear()

    Removes all elements from the set.

    \sa remove()

*/

/*!

    \fn bool QSet::remove(const T &value)

    Removes any occurrence of item \a value from the set. Returns

    true if an item was actually removed; otherwise returns false.

    \sa contains(), insert()

*/

/*!

    \fn QSet::iterator QSet::erase(iterator pos)

    \since 4.2

    Removes the item at the iterator position \a pos from the set, and

    returns an iterator positioned at the next item in the set.

    Unlike remove(), this function never causes QSet to rehash its

    internal data structure. This means that it can safely be called

    while iterating, and won't affect the order of items in the set.

    \sa remove(), find()

*/

/*! \fn QSet::const_iterator QSet::find(const T &value) const

    \since 4.2

    Returns a const iterator positioned at the item \a value in the

    set. If the set contains no item \a value, the function returns

    constEnd().

    \sa constFind(), contains()

*/

/*! \fn QSet::iterator QSet::find(const T &value)

    \since 4.2

    \overload

    Returns a non-const iterator positioned at the item \a value in

    the set. If the set contains no item \a value, the function

    returns end(). 

*/

/*! \fn QSet::const_iterator QSet::constFind(const T &value) const

    \since 4.2

    Returns a const iterator positioned at the item \a value in the

    set. If the set contains no item \a value, the function returns

    constEnd().

    \sa find(), contains()

*/

/*!

    \fn bool QSet::contains(const T &value) const

    Returns true if the set contains item \a value; otherwise returns

    false.

    \sa insert(), remove(), find()

*/

/*!

    \fn bool QSet::contains(const QSet<T> &other) const

    \since 4.6

    Returns true if the set contains all items from the \a other set;

    otherwise returns false.

    \sa insert(), remove(), find()

*/

/*! \fn QSet::const_iterator QSet::begin() const

    Returns a const \l{STL-style iterator} positioned at the first

    item in the set.

    \sa constBegin(), end()

*/

/*! \fn QSet::iterator QSet::begin()

    \since 4.2

    \overload

    Returns a non-const \l{STL-style iterator} positioned at the first

    item in the set.  

*/

/*! \fn QSet::const_iterator QSet::constBegin() const

    Returns a const \l{STL-style iterator} positioned at the first

    item in the set.

    \sa begin(), constEnd()

*/

/*! \fn QSet::const_iterator QSet::end() const

    Returns a const \l{STL-style iterator} positioned at the imaginary

    item after the last item in the set.

    \sa constEnd(), begin()

*/

/*! \fn QSet::iterator QSet::end()

    \since 4.2

    \overload

    Returns a non-const \l{STL-style iterator} pointing to the

    imaginary item after the last item in the set.

*/

/*! \fn QSet::const_iterator QSet::constEnd() const

    Returns a const \l{STL-style iterator} pointing to the imaginary

    item after the last item in the set.

    \sa constBegin(), end()

*/

/*!

    \typedef QSet::Iterator

    \since 4.2

    Qt-style synonym for QSet::iterator.

*/

/*!

    \typedef QSet::ConstIterator

    Qt-style synonym for QSet::const_iterator.

*/

/*!

    \typedef QSet::const_pointer

    Typedef for const T *. Provided for STL compatibility.

*/

/*!

    \typedef QSet::const_reference

    Typedef for const T &. Provided for STL compatibility.

*/

/*!

    \typedef QSet::difference_type

    Typedef for const ptrdiff_t. Provided for STL compatibility.

*/

/*!

    \typedef QSet::key_type

    Typedef for T. Provided for STL compatibility.

*/

/*!

    \typedef QSet::pointer

    Typedef for T *. Provided for STL compatibility.

*/

/*!

    \typedef QSet::reference

    Typedef for T &. Provided for STL compatibility.

*/

/*!

    \typedef QSet::size_type

    Typedef for int. Provided for STL compatibility.

*/

/*!

    \typedef QSet::value_type

    Typedef for T. Provided for STL compatibility.

*/

/*!

    \fn QSet::const_iterator QSet::insert(const T &value)

    Inserts item \a value into the set, if \a value isn't already

    in the set, and returns an iterator pointing at the inserted

    item.

    \sa operator<<(), remove(), contains()

*/

/*!

    \fn QSet<T> &QSet::unite(const QSet<T> &other)

    Each item in the \a other set that isn't already in this set is

    inserted into this set. A reference to this set is returned.

    \sa operator|=(), intersect(), subtract()

*/

/*!

    \fn QSet<T> &QSet::intersect(const QSet<T> &other)

    Removes all items from this set that are not contained in the

    \a other set. A reference to this set is returned.

    \sa operator&=(), unite(), subtract()

*/

/*!

    \fn QSet<T> &QSet::subtract(const QSet<T> &other)

    Removes all items from  this set that are contained in the 

    \a other set. Returns a reference to this set.

    \sa operator-=(), unite(), intersect()

*/

/*!

    \fn bool QSet::empty() const

    Returns true if the set is empty. This function is provided

    for STL compatibility. It is equivalent to isEmpty().  

*/

/*!

    \fn bool QSet::count() const

    Same as size().

*/

/*!

    \fn QSet<T> &QSet::operator<<(const T &value)

    \fn QSet<T> &QSet::operator+=(const T &value)

    \fn QSet<T> &QSet::operator|=(const T &value)

    Inserts a new item \a value and returns a reference to the set.

    If \a value already exists in the set, the set is left unchanged.

    \sa insert()

*/

/*!

    \fn QSet<T> &QSet::operator-=(const T &value)

    Removes the occurrence of item \a value from the set, if 

    it is found, and returns a reference to the set. If the

    \a value is not contained the set, nothing is removed.

    \sa remove()

*/

/*!

    \fn QSet<T> &QSet::operator|=(const QSet<T> &other)

    \fn QSet<T> &QSet::operator+=(const QSet<T> &other)

    Same as unite(\a other).

    \sa operator|(), operator&=(), operator-=()

*/

/*!

    \fn QSet<T> &QSet::operator&=(const QSet<T> &other)

    Same as intersect(\a other).

    \sa operator&(), operator|=(), operator-=()

*/

/*!

    \fn QSet<T> &QSet::operator&=(const T &value)

    \overload

    Same as intersect(\e{other}), if we consider \e{other} to be a set

    that contains the singleton \a value.  

*/