include/QtCore/qset.h

0001 // Copyright (C) 2016 The Qt Company Ltd.
0002 // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
0003
0004 #ifndef QSET_H
0005 #define QSET_H
0006
0007 #include <QtCore/qhash.h>
0008 #include <QtCore/qcontainertools_impl.h>
0009 #include <QtCore/qttypetraits.h>
0010
0011 #include <initializer_list>
0012 #include <iterator>
0013
0014 QT_BEGIN_NAMESPACE
0015
0016
0017 template <class T>
0018 class QSet
0019 {
0020     typedef QHash<T, QHashDummyValue> Hash;
0021
0022 public:
0023     inline QSet() noexcept {}
0024     inline QSet(std::initializer_list<T> list)
0025         : QSet(list.begin(), list.end()) {}
0026     template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true>
0027     inline QSet(InputIterator first, InputIterator last)
0028     {
0029         QtPrivate::reserveIfForwardIterator(this, first, last);
0030         for (; first != last; ++first)
0031             insert(*first);
0032     }
0033
0034     // compiler-generated copy/move ctor/assignment operators are fine!
0035     // compiler-generated destructor is fine!
0036
0037     inline void swap(QSet<T> &other) noexcept { q_hash.swap(other.q_hash); }
0038
0039 #ifndef Q_QDOC
0040 private:
0041     template <typename U = T, QTypeTraits::compare_eq_result_container<QSet, U> = true>
0042     friend bool comparesEqual(const QSet &lhs, const QSet &rhs) noexcept
0043     {
0044         return lhs.q_hash == rhs.q_hash;
0045     }
0046     QT_DECLARE_EQUALITY_OPERATORS_HELPER(QSet, QSet, /* non-constexpr */, noexcept,
0047             template <typename U = T, QTypeTraits::compare_eq_result_container<QSet, U> = true>)
0048 public:
0049 #else
0050     friend bool operator==(const QSet &lhs, const QSet &rhs) noexcept;
0051     friend bool operator!=(const QSet &lhs, const QSet &rhs) noexcept;
0052 #endif
0053
0054     inline qsizetype size() const { return q_hash.size(); }
0055
0056     inline bool isEmpty() const { return q_hash.isEmpty(); }
0057
0058     inline qsizetype capacity() const { return q_hash.capacity(); }
0059     inline void reserve(qsizetype size);
0060     inline void squeeze() { q_hash.squeeze(); }
0061
0062     inline void detach() { q_hash.detach(); }
0063     inline bool isDetached() const { return q_hash.isDetached(); }
0064
0065     inline void clear() { q_hash.clear(); }
0066
0067     bool remove(const T &value) { return q_hash.remove(value); }
0068
0069     template <typename Pred>
0070     inline qsizetype removeIf(Pred predicate)
0071     {
0072         return QtPrivate::qset_erase_if(*this, predicate);
0073     }
0074
0075     inline bool contains(const T &value) const { return q_hash.contains(value); }
0076
0077     bool contains(const QSet<T> &set) const;
0078
0079     class const_iterator;
0080
0081     class iterator
0082     {
0083         typedef QHash<T, QHashDummyValue> Hash;
0084         typename Hash::iterator i;
0085         friend class const_iterator;
0086         friend class QSet<T>;
0087
0088     public:
0089         typedef std::forward_iterator_tag iterator_category;
0090         typedef qptrdiff difference_type;
0091         typedef T value_type;
0092         typedef const T *pointer;
0093         typedef const T &reference;
0094
0095         inline iterator() {}
0096         inline iterator(typename Hash::iterator o) : i(o) {}
0097         inline iterator(const iterator &o) : i(o.i) {}
0098         inline iterator &operator=(const iterator &o) { i = o.i; return *this; }
0099         inline const T &operator*() const { return i.key(); }
0100         inline const T *operator->() const { return &i.key(); }
0101         inline bool operator==(const iterator &o) const { return i == o.i; }
0102         inline bool operator!=(const iterator &o) const { return i != o.i; }
0103         inline bool operator==(const const_iterator &o) const
0104             { return i == o.i; }
0105         inline bool operator!=(const const_iterator &o) const
0106             { return i != o.i; }
0107         inline iterator &operator++() { ++i; return *this; }
0108         inline iterator operator++(int) { iterator r = *this; ++i; return r; }
0109     };
0110
0111     class const_iterator
0112     {
0113         typedef QHash<T, QHashDummyValue> Hash;
0114         typename Hash::const_iterator i;
0115         friend class iterator;
0116         friend class QSet<T>;
0117
0118     public:
0119         typedef std::forward_iterator_tag iterator_category;
0120         typedef qptrdiff difference_type;
0121         typedef T value_type;
0122         typedef const T *pointer;
0123         typedef const T &reference;
0124
0125         inline const_iterator() {}
0126         inline const_iterator(typename Hash::const_iterator o) : i(o) {}
0127         inline const_iterator(const const_iterator &o) : i(o.i) {}
0128         inline const_iterator(const iterator &o)
0129             : i(o.i) {}
0130         inline const_iterator &operator=(const const_iterator &o) { i = o.i; return *this; }
0131         inline const T &operator*() const { return i.key(); }
0132         inline const T *operator->() const { return &i.key(); }
0133         inline bool operator==(const const_iterator &o) const { return i == o.i; }
0134         inline bool operator!=(const const_iterator &o) const { return i != o.i; }
0135         inline const_iterator &operator++() { ++i; return *this; }
0136         inline const_iterator operator++(int) { const_iterator r = *this; ++i; return r; }
0137     };
0138
0139     // STL style
0140     inline iterator begin() { return q_hash.begin(); }
0141     inline const_iterator begin() const noexcept { return q_hash.begin(); }
0142     inline const_iterator cbegin() const noexcept { return q_hash.begin(); }
0143     inline const_iterator constBegin() const noexcept { return q_hash.constBegin(); }
0144     inline iterator end() { return q_hash.end(); }
0145     inline const_iterator end() const noexcept { return q_hash.end(); }
0146     inline const_iterator cend() const noexcept { return q_hash.end(); }
0147     inline const_iterator constEnd() const noexcept { return q_hash.constEnd(); }
0148
0149     iterator erase(const_iterator i)
0150     {
0151         Q_ASSERT(i != constEnd());
0152         return q_hash.erase(i.i);
0153     }
0154
0155     // more Qt
0156     typedef iterator Iterator;
0157     typedef const_iterator ConstIterator;
0158     inline qsizetype count() const { return q_hash.size(); }
0159     inline iterator insert(const T &value)
0160         { return q_hash.insert(value, QHashDummyValue()); }
0161     inline iterator insert(T &&value)
0162         { return q_hash.emplace(std::move(value), QHashDummyValue()); }
0163     iterator find(const T &value) { return q_hash.find(value); }
0164     const_iterator find(const T &value) const { return q_hash.find(value); }
0165     inline const_iterator constFind(const T &value) const { return find(value); }
0166     QSet<T> &unite(const QSet<T> &other);
0167     QSet<T> &intersect(const QSet<T> &other);
0168     bool intersects(const QSet<T> &other) const;
0169     QSet<T> &subtract(const QSet<T> &other);
0170
0171     // STL compatibility
0172     typedef T key_type;
0173     typedef T value_type;
0174     typedef value_type *pointer;
0175     typedef const value_type *const_pointer;
0176     typedef value_type &reference;
0177     typedef const value_type &const_reference;
0178     typedef qptrdiff difference_type;
0179     typedef qsizetype size_type;
0180
0181     inline bool empty() const { return isEmpty(); }
0182
0183     iterator insert(const_iterator, const T &value) { return insert(value); }
0184
0185     // comfort
0186     inline QSet<T> &operator<<(const T &value) { insert(value); return *this; }
0187     inline QSet<T> &operator|=(const QSet<T> &other) { unite(other); return *this; }
0188     inline QSet<T> &operator|=(const T &value) { insert(value); return *this; }
0189     inline QSet<T> &operator&=(const QSet<T> &other) { intersect(other); return *this; }
0190     inline QSet<T> &operator&=(const T &value)
0191         { QSet<T> result; if (contains(value)) result.insert(value); return (*this = result); }
0192     inline QSet<T> &operator+=(const QSet<T> &other) { unite(other); return *this; }
0193     inline QSet<T> &operator+=(const T &value) { insert(value); return *this; }
0194     inline QSet<T> &operator-=(const QSet<T> &other) { subtract(other); return *this; }
0195     inline QSet<T> &operator-=(const T &value) { remove(value); return *this; }
0196
0197     friend QSet operator|(const QSet &lhs, const QSet &rhs) { return QSet(lhs) |= rhs; }
0198     friend QSet operator|(QSet &&lhs, const QSet &rhs) { lhs |= rhs; return std::move(lhs); }
0199
0200     friend QSet operator&(const QSet &lhs, const QSet &rhs) { return QSet(lhs) &= rhs; }
0201     friend QSet operator&(QSet &&lhs, const QSet &rhs) { lhs &= rhs; return std::move(lhs); }
0202
0203     friend QSet operator+(const QSet &lhs, const QSet &rhs) { return QSet(lhs) += rhs; }
0204     friend QSet operator+(QSet &&lhs, const QSet &rhs) { lhs += rhs; return std::move(lhs); }
0205
0206     friend QSet operator-(const QSet &lhs, const QSet &rhs) { return QSet(lhs) -= rhs; }
0207     friend QSet operator-(QSet &&lhs, const QSet &rhs) { lhs -= rhs; return std::move(lhs); }
0208
0209     QList<T> values() const;
0210
0211 private:
0212     static inline QSet intersected_helper(const QSet &lhs, const QSet &rhs);
0213
0214     Hash q_hash;
0215 };
0216
0217 template <typename InputIterator,
0218           typename ValueType = typename std::iterator_traits<InputIterator>::value_type,
0219           QtPrivate::IfIsInputIterator<InputIterator> = true>
0220 QSet(InputIterator, InputIterator) -> QSet<ValueType>;
0221
0222 template <typename T>
0223 size_t qHash(const QSet<T> &key, size_t seed = 0)
0224 noexcept(noexcept(qHashRangeCommutative(key.begin(), key.end(), seed)))
0225 {
0226     return qHashRangeCommutative(key.begin(), key.end(), seed);
0227 }
0228
0229 // inline function implementations
0230
0231 template <class T>
0232 Q_INLINE_TEMPLATE void QSet<T>::reserve(qsizetype asize) { q_hash.reserve(asize); }
0233
0234 template <class T>
0235 Q_INLINE_TEMPLATE QSet<T> &QSet<T>::unite(const QSet<T> &other)
0236 {
0237     if (!q_hash.isSharedWith(other.q_hash)) {
0238         for (const T &e : other)
0239             insert(e);
0240     }
0241     return *this;
0242 }
0243
0244 template <class T>
0245 Q_INLINE_TEMPLATE QSet<T> &QSet<T>::intersect(const QSet<T> &other)
0246 {
0247     if (q_hash.isSharedWith(other.q_hash)) {
0248         // nothing to do
0249     } else if (isEmpty() || other.isEmpty()) {
0250         // any set intersected with the empty set is the empty set
0251         clear();
0252     } else if (q_hash.isDetached()) {
0253         // do it in-place:
0254         removeIf([&other] (const T &e) { return !other.contains(e); });
0255     } else {
0256         // don't detach *this just to remove some items; create a new set
0257         *this = intersected_helper(*this, other);
0258     }
0259     return *this;
0260 }
0261
0262 template <class T>
0263 // static
0264 auto QSet<T>::intersected_helper(const QSet &lhs, const QSet &rhs) -> QSet
0265 {
0266     QSet r;
0267
0268     const auto l_size = lhs.size();
0269     const auto r_size = rhs.size();
0270     r.reserve((std::min)(l_size, r_size));
0271
0272     // Iterate the smaller of the two sets, but always take from lhs, for
0273     // consistency with insert():
0274
0275     if (l_size <= r_size) {
0276         // lhs is not larger
0277         for (const auto &e : lhs) {
0278             if (rhs.contains(e))
0279                 r.insert(e);
0280         }
0281     } else {
0282         // rhs is smaller
0283         for (const auto &e : rhs) {
0284             if (const auto it = lhs.find(e); it != lhs.end())
0285                 r.insert(*it);
0286         }
0287     }
0288
0289     return r;
0290 }
0291
0292 template <class T>
0293 Q_INLINE_TEMPLATE bool QSet<T>::intersects(const QSet<T> &other) const
0294 {
0295     const bool otherIsBigger = other.size() > size();
0296     const QSet &smallestSet = otherIsBigger ? *this : other;
0297     const QSet &biggestSet = otherIsBigger ? other : *this;
0298     typename QSet::const_iterator i = smallestSet.cbegin();
0299     typename QSet::const_iterator e = smallestSet.cend();
0300
0301     while (i != e) {
0302         if (biggestSet.contains(*i))
0303             return true;
0304         ++i;
0305     }
0306
0307     return false;
0308 }
0309
0310 template <class T>
0311 Q_INLINE_TEMPLATE QSet<T> &QSet<T>::subtract(const QSet<T> &other)
0312 {
0313     if (q_hash.isSharedWith(other.q_hash)) {
0314         clear();
0315     } else {
0316         for (const auto &e : other)
0317             remove(e);
0318     }
0319     return *this;
0320 }
0321
0322 template <class T>
0323 Q_INLINE_TEMPLATE bool QSet<T>::contains(const QSet<T> &other) const
0324 {
0325     typename QSet<T>::const_iterator i = other.constBegin();
0326     while (i != other.constEnd()) {
0327         if (!contains(*i))
0328             return false;
0329         ++i;
0330     }
0331     return true;
0332 }
0333
0334 template <typename T>
0335 Q_OUTOFLINE_TEMPLATE QList<T> QSet<T>::values() const
0336 {
0337     QList<T> result;
0338     result.reserve(size());
0339     typename QSet<T>::const_iterator i = constBegin();
0340     while (i != constEnd()) {
0341         result.append(*i);
0342         ++i;
0343     }
0344     return result;
0345 }
0346
0347 Q_DECLARE_SEQUENTIAL_ITERATOR(Set)
0348
0349 #if !defined(QT_NO_JAVA_STYLE_ITERATORS)
0350 template <typename T>
0351 class QMutableSetIterator
0352 {
0353     typedef typename QSet<T>::iterator iterator;
0354     QSet<T> *c;
0355     iterator i, n;
0356     inline bool item_exists() const { return c->constEnd() != n; }
0357
0358 public:
0359     inline QMutableSetIterator(QSet<T> &container)
0360         : c(&container)
0361     { i = c->begin(); n = c->end(); }
0362     inline QMutableSetIterator &operator=(QSet<T> &container)
0363     { c = &container; i = c->begin(); n = c->end(); return *this; }
0364     inline void toFront() { i = c->begin(); n = c->end(); }
0365     inline void toBack() { i = c->end(); n = i; }
0366     inline bool hasNext() const { return c->constEnd() != i; }
0367     inline const T &next() { n = i++; return *n; }
0368     inline const T &peekNext() const { return *i; }
0369     inline void remove()
0370     { if (c->constEnd() != n) { i = c->erase(n); n = c->end(); } }
0371     inline const T &value() const { Q_ASSERT(item_exists()); return *n; }
0372     inline bool findNext(const T &t)
0373     { while (c->constEnd() != (n = i)) if (*i++ == t) return true; return false; }
0374 };
0375 #endif // QT_NO_JAVA_STYLE_ITERATORS
0376
0377 template <typename T, typename Predicate>
0378 qsizetype erase_if(QSet<T> &set, Predicate pred)
0379 {
0380     return QtPrivate::qset_erase_if(set, pred);
0381 }
0382
0383 QT_END_NAMESPACE
0384
0385 #endif // QSET_H