Back to home page

EIC code displayed by LXR
 
 

    

Warning, file /include/QtCore/qset.h was not indexed or was modified since last indexation (in which case cross-reference links may be missing, inaccurate or erroneous).

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

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!