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 QtCore module 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 #ifndef QSET_H

    43 #define QSET_H

    44 

    45 #include <QtCore/qhash.h>

    46 

    47 QT_BEGIN_HEADER

    48 

    49 QT_BEGIN_NAMESPACE

    50 

    51 QT_MODULE(Core)

    52 

    53 template <class T>

    54 class QSet

    55 {

    56     typedef QHash<T, QHashDummyValue> Hash;

    57 

    58 public:

    59     inline QSet() {}

    60     inline QSet(const QSet<T> &other) : q_hash(other.q_hash) {}

    61 

    62     inline QSet<T> &operator=(const QSet<T> &other)

    63         { q_hash = other.q_hash; return *this; }

    64 

    65     inline bool operator==(const QSet<T> &other) const

    66         { return q_hash == other.q_hash; }

    67     inline bool operator!=(const QSet<T> &other) const

    68         { return q_hash != other.q_hash; }

    69 

    70     inline int size() const { return q_hash.size(); }

    71 

    72     inline bool isEmpty() const { return q_hash.isEmpty(); }

    73 

    74     inline int capacity() const { return q_hash.capacity(); }

    75     inline void reserve(int size);

    76     inline void squeeze() { q_hash.squeeze(); }

    77 

    78     inline void detach() { q_hash.detach(); }

    79     inline bool isDetached() const { return q_hash.isDetached(); }

    80     inline void setSharable(bool sharable) { q_hash.setSharable(sharable); }

    81 

    82     inline void clear() { q_hash.clear(); }

    83 

    84     inline bool remove(const T &value) { return q_hash.remove(value) != 0; }

    85 

    86     inline bool contains(const T &value) const { return q_hash.contains(value); }

    87 

    88     bool contains(const QSet<T> &set) const;

    89 

    90     class const_iterator;

    91 

    92     class iterator

    93     {

    94         typedef QHash<T, QHashDummyValue> Hash;

    95         typename Hash::iterator i;

    96         friend class const_iterator;

    97 

    98     public:

    99         typedef std::bidirectional_iterator_tag iterator_category;

   100         typedef ptrdiff_t difference_type;

   101         typedef T value_type;

   102         typedef const T *pointer;

   103         typedef const T &reference;

   104 

   105         inline iterator() {}

   106         inline iterator(typename Hash::iterator o) : i(o) {}

   107         inline iterator(const iterator &o) : i(o.i) {}

   108         inline iterator &operator=(const iterator &o) { i = o.i; return *this; }

   109         inline const T &operator*() const { return i.key(); }

   110         inline const T *operator->() const { return &i.key(); }

   111         inline bool operator==(const iterator &o) const { return i == o.i; }

   112         inline bool operator!=(const iterator &o) const { return i != o.i; }

   113         inline bool operator==(const const_iterator &o) const

   114             { return i == o.i; }

   115         inline bool operator!=(const const_iterator &o) const

   116             { return i != o.i; }

   117         inline iterator &operator++() { ++i; return *this; }

   118         inline iterator operator++(int) { iterator r = *this; ++i; return r; }

   119         inline iterator &operator--() { --i; return *this; }

   120         inline iterator operator--(int) { iterator r = *this; --i; return r; }

   121         inline iterator operator+(int j) const { return i + j; }

   122         inline iterator operator-(int j) const { return i - j; }

   123         inline iterator &operator+=(int j) { i += j; return *this; }

   124         inline iterator &operator-=(int j) { i -= j; return *this; }

   125     };

   126 

   127     class const_iterator

   128     {

   129         typedef QHash<T, QHashDummyValue> Hash;

   130         typename Hash::const_iterator i;

   131         friend class iterator;

   132 

   133     public:

   134         typedef std::bidirectional_iterator_tag iterator_category;

   135         typedef ptrdiff_t difference_type;

   136         typedef T value_type;

   137         typedef const T *pointer;

   138         typedef const T &reference;

   139 

   140         inline const_iterator() {}

   141         inline const_iterator(typename Hash::const_iterator o) : i(o) {}

   142         inline const_iterator(const const_iterator &o) : i(o.i) {}

   143         inline const_iterator(const iterator &o)

   144             : i(o.i) {}

   145         inline const_iterator &operator=(const const_iterator &o) { i = o.i; return *this; }

   146         inline const T &operator*() const { return i.key(); }

   147         inline const T *operator->() const { return &i.key(); }

   148         inline bool operator==(const const_iterator &o) const { return i == o.i; }

   149         inline bool operator!=(const const_iterator &o) const { return i != o.i; }

   150         inline const_iterator &operator++() { ++i; return *this; }

   151         inline const_iterator operator++(int) { const_iterator r = *this; ++i; return r; }

   152         inline const_iterator &operator--() { --i; return *this; }

   153         inline const_iterator operator--(int) { const_iterator r = *this; --i; return r; }

   154         inline const_iterator operator+(int j) const { return i + j; }

   155         inline const_iterator operator-(int j) const { return i - j; }

   156         inline const_iterator &operator+=(int j) { i += j; return *this; }

   157         inline const_iterator &operator-=(int j) { i -= j; return *this; }

   158     };

   159 

   160     // STL style

   161     inline iterator begin() { return q_hash.begin(); }

   162     inline const_iterator begin() const { return q_hash.begin(); }

   163     inline const_iterator constBegin() const { return q_hash.constBegin(); }

   164     inline iterator end() { return q_hash.end(); }

   165     inline const_iterator end() const { return q_hash.end(); }

   166     inline const_iterator constEnd() const { return q_hash.constEnd(); }

   167     iterator erase(iterator i)

   168         { return q_hash.erase(reinterpret_cast<typename Hash::iterator &>(i)); }

   169 

   170     // more Qt

   171     typedef iterator Iterator;

   172     typedef const_iterator ConstIterator;

   173     inline int count() const { return q_hash.count(); }

   174     inline const_iterator insert(const T &value) // ### Qt 5: should return an 'iterator'

   175         { return static_cast<typename Hash::const_iterator>(q_hash.insert(value,

   176                                                                           QHashDummyValue())); }

   177     iterator find(const T &value) { return q_hash.find(value); }

   178     const_iterator find(const T &value) const { return q_hash.find(value); }

   179     inline const_iterator constFind(const T &value) const { return find(value); }

   180     QSet<T> &unite(const QSet<T> &other);

   181     QSet<T> &intersect(const QSet<T> &other);

   182     QSet<T> &subtract(const QSet<T> &other);

   183 

   184     // STL compatibility

   185     typedef T key_type;

   186     typedef T value_type;

   187     typedef value_type *pointer;

   188     typedef const value_type *const_pointer;

   189     typedef value_type &reference;

   190     typedef const value_type &const_reference;

   191     typedef ptrdiff_t difference_type;

   192     typedef int size_type;

   193 

   194     inline bool empty() const { return isEmpty(); }

   195 

   196     // comfort

   197     inline QSet<T> &operator<<(const T &value) { insert(value); return *this; }

   198     inline QSet<T> &operator|=(const QSet<T> &other) { unite(other); return *this; }

   199     inline QSet<T> &operator|=(const T &value) { insert(value); return *this; }

   200     inline QSet<T> &operator&=(const QSet<T> &other) { intersect(other); return *this; }

   201     inline QSet<T> &operator&=(const T &value)

   202         { QSet<T> result; if (contains(value)) result.insert(value); return (*this = result); }

   203     inline QSet<T> &operator+=(const QSet<T> &other) { unite(other); return *this; }

   204     inline QSet<T> &operator+=(const T &value) { insert(value); return *this; }

   205     inline QSet<T> &operator-=(const QSet<T> &other) { subtract(other); return *this; }

   206     inline QSet<T> &operator-=(const T &value) { remove(value); return *this; }

   207     inline QSet<T> operator|(const QSet<T> &other) const

   208         { QSet<T> result = *this; result |= other; return result; }

   209     inline QSet<T> operator&(const QSet<T> &other) const

   210         { QSet<T> result = *this; result &= other; return result; }

   211     inline QSet<T> operator+(const QSet<T> &other) const

   212         { QSet<T> result = *this; result += other; return result; }

   213     inline QSet<T> operator-(const QSet<T> &other) const

   214         { QSet<T> result = *this; result -= other; return result; }

   215 #if QT_VERSION < 0x050000

   216     // ### Qt 5: remove

   217     inline QSet<T> operator|(const QSet<T> &other)

   218         { QSet<T> result = *this; result |= other; return result; }

   219     inline QSet<T> operator&(const QSet<T> &other)

   220         { QSet<T> result = *this; result &= other; return result; }

   221     inline QSet<T> operator+(const QSet<T> &other)

   222         { QSet<T> result = *this; result += other; return result; }

   223     inline QSet<T> operator-(const QSet<T> &other)

   224         { QSet<T> result = *this; result -= other; return result; }

   225 #endif

   226 

   227     QList<T> toList() const;

   228     inline QList<T> values() const { return toList(); }

   229 

   230     static QSet<T> fromList(const QList<T> &list);

   231 

   232 private:

   233     Hash q_hash;

   234 };

   235 

   236 template <class T>

   237 Q_INLINE_TEMPLATE void QSet<T>::reserve(int asize) { q_hash.reserve(asize); }

   238 

   239 template <class T>

   240 Q_INLINE_TEMPLATE QSet<T> &QSet<T>::unite(const QSet<T> &other)

   241 {

   242     QSet<T> copy(other);

   243     typename QSet<T>::const_iterator i = copy.constEnd();

   244     while (i != copy.constBegin()) {

   245         --i;

   246         insert(*i);

   247     }

   248     return *this;

   249 }

   250 

   251 template <class T>

   252 Q_INLINE_TEMPLATE QSet<T> &QSet<T>::intersect(const QSet<T> &other)

   253 {

   254     QSet<T> copy1(*this);

   255     QSet<T> copy2(other);

   256     typename QSet<T>::const_iterator i = copy1.constEnd();

   257     while (i != copy1.constBegin()) {

   258         --i;

   259         if (!copy2.contains(*i))

   260             remove(*i);

   261     }

   262     return *this;

   263 }

   264 

   265 template <class T>

   266 Q_INLINE_TEMPLATE QSet<T> &QSet<T>::subtract(const QSet<T> &other)

   267 {

   268     QSet<T> copy1(*this);

   269     QSet<T> copy2(other);

   270     typename QSet<T>::const_iterator i = copy1.constEnd();

   271     while (i != copy1.constBegin()) {

   272         --i;

   273         if (copy2.contains(*i))

   274             remove(*i);

   275     }

   276     return *this;

   277 }

   278 

   279 template <class T>

   280 Q_INLINE_TEMPLATE bool QSet<T>::contains(const QSet<T> &other) const

   281 {

   282     typename QSet<T>::const_iterator i = other.constBegin();

   283     while (i != other.constEnd()) {

   284         if (!contains(*i))

   285             return false;

   286         ++i;

   287     }

   288     return true;

   289 }

   290 

   291 template <typename T>

   292 Q_OUTOFLINE_TEMPLATE QList<T> QSet<T>::toList() const

   293 {

   294     QList<T> result;

   295     typename QSet<T>::const_iterator i = constBegin();

   296     while (i != constEnd()) {

   297         result.append(*i);

   298         ++i;

   299     }

   300     return result;

   301 }

   302 

   303 template <typename T>

   304 Q_OUTOFLINE_TEMPLATE QSet<T> QList<T>::toSet() const

   305 {

   306     QSet<T> result;

   307     result.reserve(size());

   308     for (int i = 0; i < size(); ++i)

   309         result.insert(at(i));

   310     return result;

   311 }

   312 

   313 template <typename T>

   314 QSet<T> QSet<T>::fromList(const QList<T> &list)

   315 {

   316     return list.toSet();

   317 }

   318 

   319 template <typename T>

   320 QList<T> QList<T>::fromSet(const QSet<T> &set)

   321 {

   322     return set.toList();

   323 }

   324 

   325 Q_DECLARE_SEQUENTIAL_ITERATOR(Set)

   326 

   327 template <typename T>

   328 class QMutableSetIterator

   329 {

   330     typedef typename QSet<T>::iterator iterator;

   331     QSet<T> *c;

   332     iterator i, n;

   333     inline bool item_exists() const { return n != c->constEnd(); }

   334 

   335 public:

   336     inline QMutableSetIterator(QSet<T> &container)

   337         : c(&container)

   338     { c->setSharable(false); i = c->begin(); n = c->end(); }

   339     inline ~QMutableSetIterator()

   340     { c->setSharable(true); }

   341     inline QMutableSetIterator &operator=(QSet<T> &container)

   342     { c->setSharable(true); c = &container; c->setSharable(false);

   343       i = c->begin(); n = c->end(); return *this; }

   344     inline void toFront() { i = c->begin(); n = c->end(); }

   345     inline void toBack() { i = c->end(); n = i; }

   346     inline bool hasNext() const { return c->constEnd() != i; }

   347     inline const T &next() { n = i++; return *n; }

   348     inline const T &peekNext() const { return *i; }

   349     inline bool hasPrevious() const { return c->constBegin() != i; }

   350     inline const T &previous() { n = --i; return *n; }

   351     inline const T &peekPrevious() const { iterator p = i; return *--p; }

   352     inline void remove()

   353     { if (c->constEnd() != n) { i = c->erase(n); n = c->end(); } }

   354     inline const T &value() const { Q_ASSERT(item_exists()); return *n; }

   355     inline bool findNext(const T &t)

   356     { while (c->constEnd() != (n = i)) if (*i++ == t) return true; return false; }

   357     inline bool findPrevious(const T &t)

   358     { while (c->constBegin() != i) if (*(n = --i) == t) return true;

   359       n = c->end(); return false;  }

   360 };

   361 

   362 QT_END_NAMESPACE

   363 

   364 QT_END_HEADER

   365 

   366 #endif // QSET_H