1 | // Copyright (C) 2016 The Qt Company Ltd. |
2 | // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only |
3 | |
4 | #ifndef QSET_H |
5 | #define QSET_H |
6 | |
7 | #include <QtCore/qhash.h> |
8 | #include <QtCore/qcontainertools_impl.h> |
9 | |
10 | #include <initializer_list> |
11 | #include <iterator> |
12 | |
13 | QT_BEGIN_NAMESPACE |
14 | |
15 | |
16 | template <class T> |
17 | class QSet |
18 | { |
19 | typedef QHash<T, QHashDummyValue> Hash; |
20 | |
21 | public: |
22 | inline QSet() noexcept {} |
23 | inline QSet(std::initializer_list<T> list) |
24 | : QSet(list.begin(), list.end()) {} |
25 | template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true> |
26 | inline QSet(InputIterator first, InputIterator last) |
27 | { |
28 | QtPrivate::reserveIfForwardIterator(this, first, last); |
29 | for (; first != last; ++first) |
30 | insert(*first); |
31 | } |
32 | |
33 | // compiler-generated copy/move ctor/assignment operators are fine! |
34 | // compiler-generated destructor is fine! |
35 | |
36 | inline void swap(QSet<T> &other) noexcept { q_hash.swap(other.q_hash); } |
37 | |
38 | #ifndef Q_QDOC |
39 | template <typename U = T> |
40 | QTypeTraits::compare_eq_result_container<QSet, U> operator==(const QSet<T> &other) const |
41 | { return q_hash == other.q_hash; } |
42 | template <typename U = T> |
43 | QTypeTraits::compare_eq_result_container<QSet, U> operator!=(const QSet<T> &other) const |
44 | { return q_hash != other.q_hash; } |
45 | #else |
46 | bool operator==(const QSet &other) const; |
47 | bool operator!=(const QSet &other) const; |
48 | #endif |
49 | |
50 | inline qsizetype size() const { return q_hash.size(); } |
51 | |
52 | inline bool isEmpty() const { return q_hash.isEmpty(); } |
53 | |
54 | inline qsizetype capacity() const { return q_hash.capacity(); } |
55 | inline void reserve(qsizetype size); |
56 | inline void squeeze() { q_hash.squeeze(); } |
57 | |
58 | inline void detach() { q_hash.detach(); } |
59 | inline bool isDetached() const { return q_hash.isDetached(); } |
60 | |
61 | inline void clear() { q_hash.clear(); } |
62 | |
63 | inline bool remove(const T &value) { return q_hash.remove(value) != 0; } |
64 | |
65 | template <typename Pred> |
66 | inline qsizetype removeIf(Pred predicate) |
67 | { |
68 | return QtPrivate::qset_erase_if(*this, predicate); |
69 | } |
70 | |
71 | inline bool contains(const T &value) const { return q_hash.contains(value); } |
72 | |
73 | bool contains(const QSet<T> &set) const; |
74 | |
75 | class const_iterator; |
76 | |
77 | class iterator |
78 | { |
79 | typedef QHash<T, QHashDummyValue> Hash; |
80 | typename Hash::iterator i; |
81 | friend class const_iterator; |
82 | friend class QSet<T>; |
83 | |
84 | public: |
85 | typedef std::forward_iterator_tag iterator_category; |
86 | typedef qptrdiff difference_type; |
87 | typedef T value_type; |
88 | typedef const T *pointer; |
89 | typedef const T &reference; |
90 | |
91 | inline iterator() {} |
92 | inline iterator(typename Hash::iterator o) : i(o) {} |
93 | inline iterator(const iterator &o) : i(o.i) {} |
94 | inline iterator &operator=(const iterator &o) { i = o.i; return *this; } |
95 | inline const T &operator*() const { return i.key(); } |
96 | inline const T *operator->() const { return &i.key(); } |
97 | inline bool operator==(const iterator &o) const { return i == o.i; } |
98 | inline bool operator!=(const iterator &o) const { return i != o.i; } |
99 | inline bool operator==(const const_iterator &o) const |
100 | { return i == o.i; } |
101 | inline bool operator!=(const const_iterator &o) const |
102 | { return i != o.i; } |
103 | inline iterator &operator++() { ++i; return *this; } |
104 | inline iterator operator++(int) { iterator r = *this; ++i; return r; } |
105 | }; |
106 | |
107 | class const_iterator |
108 | { |
109 | typedef QHash<T, QHashDummyValue> Hash; |
110 | typename Hash::const_iterator i; |
111 | friend class iterator; |
112 | friend class QSet<T>; |
113 | |
114 | public: |
115 | typedef std::forward_iterator_tag iterator_category; |
116 | typedef qptrdiff difference_type; |
117 | typedef T value_type; |
118 | typedef const T *pointer; |
119 | typedef const T &reference; |
120 | |
121 | inline const_iterator() {} |
122 | inline const_iterator(typename Hash::const_iterator o) : i(o) {} |
123 | inline const_iterator(const const_iterator &o) : i(o.i) {} |
124 | inline const_iterator(const iterator &o) |
125 | : i(o.i) {} |
126 | inline const_iterator &operator=(const const_iterator &o) { i = o.i; return *this; } |
127 | inline const T &operator*() const { return i.key(); } |
128 | inline const T *operator->() const { return &i.key(); } |
129 | inline bool operator==(const const_iterator &o) const { return i == o.i; } |
130 | inline bool operator!=(const const_iterator &o) const { return i != o.i; } |
131 | inline const_iterator &operator++() { ++i; return *this; } |
132 | inline const_iterator operator++(int) { const_iterator r = *this; ++i; return r; } |
133 | }; |
134 | |
135 | // STL style |
136 | inline iterator begin() { return q_hash.begin(); } |
137 | inline const_iterator begin() const noexcept { return q_hash.begin(); } |
138 | inline const_iterator cbegin() const noexcept { return q_hash.begin(); } |
139 | inline const_iterator constBegin() const noexcept { return q_hash.constBegin(); } |
140 | inline iterator end() { return q_hash.end(); } |
141 | inline const_iterator end() const noexcept { return q_hash.end(); } |
142 | inline const_iterator cend() const noexcept { return q_hash.end(); } |
143 | inline const_iterator constEnd() const noexcept { return q_hash.constEnd(); } |
144 | |
145 | iterator erase(const_iterator i) |
146 | { |
147 | Q_ASSERT(i != constEnd()); |
148 | return q_hash.erase(i.i); |
149 | } |
150 | |
151 | // more Qt |
152 | typedef iterator Iterator; |
153 | typedef const_iterator ConstIterator; |
154 | inline qsizetype count() const { return q_hash.size(); } |
155 | inline iterator insert(const T &value) |
156 | { return q_hash.insert(value, QHashDummyValue()); } |
157 | inline iterator insert(T &&value) |
158 | { return q_hash.emplace(std::move(value), QHashDummyValue()); } |
159 | iterator find(const T &value) { return q_hash.find(value); } |
160 | const_iterator find(const T &value) const { return q_hash.find(value); } |
161 | inline const_iterator constFind(const T &value) const { return find(value); } |
162 | QSet<T> &unite(const QSet<T> &other); |
163 | QSet<T> &intersect(const QSet<T> &other); |
164 | bool intersects(const QSet<T> &other) const; |
165 | QSet<T> &subtract(const QSet<T> &other); |
166 | |
167 | // STL compatibility |
168 | typedef T key_type; |
169 | typedef T value_type; |
170 | typedef value_type *pointer; |
171 | typedef const value_type *const_pointer; |
172 | typedef value_type &reference; |
173 | typedef const value_type &const_reference; |
174 | typedef qptrdiff difference_type; |
175 | typedef qsizetype size_type; |
176 | |
177 | inline bool empty() const { return isEmpty(); } |
178 | |
179 | iterator insert(const_iterator, const T &value) { return insert(value); } |
180 | |
181 | // comfort |
182 | inline QSet<T> &operator<<(const T &value) { insert(value); return *this; } |
183 | inline QSet<T> &operator|=(const QSet<T> &other) { unite(other); return *this; } |
184 | inline QSet<T> &operator|=(const T &value) { insert(value); return *this; } |
185 | inline QSet<T> &operator&=(const QSet<T> &other) { intersect(other); return *this; } |
186 | inline QSet<T> &operator&=(const T &value) |
187 | { QSet<T> result; if (contains(value)) result.insert(value); return (*this = result); } |
188 | inline QSet<T> &operator+=(const QSet<T> &other) { unite(other); return *this; } |
189 | inline QSet<T> &operator+=(const T &value) { insert(value); return *this; } |
190 | inline QSet<T> &operator-=(const QSet<T> &other) { subtract(other); return *this; } |
191 | inline QSet<T> &operator-=(const T &value) { remove(value); return *this; } |
192 | inline QSet<T> operator|(const QSet<T> &other) const |
193 | { QSet<T> result = *this; result |= other; return result; } |
194 | inline QSet<T> operator&(const QSet<T> &other) const |
195 | { QSet<T> result = *this; result &= other; return result; } |
196 | inline QSet<T> operator+(const QSet<T> &other) const |
197 | { QSet<T> result = *this; result += other; return result; } |
198 | inline QSet<T> operator-(const QSet<T> &other) const |
199 | { QSet<T> result = *this; result -= other; return result; } |
200 | |
201 | QList<T> values() const; |
202 | |
203 | private: |
204 | Hash q_hash; |
205 | }; |
206 | |
207 | template <typename InputIterator, |
208 | typename ValueType = typename std::iterator_traits<InputIterator>::value_type, |
209 | QtPrivate::IfIsInputIterator<InputIterator> = true> |
210 | QSet(InputIterator, InputIterator) -> QSet<ValueType>; |
211 | |
212 | template <typename T> |
213 | size_t qHash(const QSet<T> &key, size_t seed = 0) |
214 | noexcept(noexcept(qHashRangeCommutative(key.begin(), key.end(), seed))) |
215 | { |
216 | return qHashRangeCommutative(key.begin(), key.end(), seed); |
217 | } |
218 | |
219 | // inline function implementations |
220 | |
221 | template <class T> |
222 | Q_INLINE_TEMPLATE void QSet<T>::reserve(qsizetype asize) { q_hash.reserve(asize); } |
223 | |
224 | template <class T> |
225 | Q_INLINE_TEMPLATE QSet<T> &QSet<T>::unite(const QSet<T> &other) |
226 | { |
227 | if (!q_hash.isSharedWith(other.q_hash)) { |
228 | for (const T &e : other) |
229 | insert(e); |
230 | } |
231 | return *this; |
232 | } |
233 | |
234 | template <class T> |
235 | Q_INLINE_TEMPLATE QSet<T> &QSet<T>::intersect(const QSet<T> &other) |
236 | { |
237 | QSet<T> copy1; |
238 | QSet<T> copy2; |
239 | if (size() <= other.size()) { |
240 | copy1 = *this; |
241 | copy2 = other; |
242 | } else { |
243 | copy1 = other; |
244 | copy2 = *this; |
245 | *this = copy1; |
246 | } |
247 | for (const auto &e : std::as_const(copy1)) { |
248 | if (!copy2.contains(e)) |
249 | remove(value: e); |
250 | } |
251 | return *this; |
252 | } |
253 | |
254 | template <class T> |
255 | Q_INLINE_TEMPLATE bool QSet<T>::intersects(const QSet<T> &other) const |
256 | { |
257 | const bool otherIsBigger = other.size() > size(); |
258 | const QSet &smallestSet = otherIsBigger ? *this : other; |
259 | const QSet &biggestSet = otherIsBigger ? other : *this; |
260 | typename QSet::const_iterator i = smallestSet.cbegin(); |
261 | typename QSet::const_iterator e = smallestSet.cend(); |
262 | |
263 | while (i != e) { |
264 | if (biggestSet.contains(*i)) |
265 | return true; |
266 | ++i; |
267 | } |
268 | |
269 | return false; |
270 | } |
271 | |
272 | template <class T> |
273 | Q_INLINE_TEMPLATE QSet<T> &QSet<T>::subtract(const QSet<T> &other) |
274 | { |
275 | if (q_hash.isSharedWith(other.q_hash)) { |
276 | clear(); |
277 | } else { |
278 | for (const auto &e : other) |
279 | remove(value: e); |
280 | } |
281 | return *this; |
282 | } |
283 | |
284 | template <class T> |
285 | Q_INLINE_TEMPLATE bool QSet<T>::contains(const QSet<T> &other) const |
286 | { |
287 | typename QSet<T>::const_iterator i = other.constBegin(); |
288 | while (i != other.constEnd()) { |
289 | if (!contains(*i)) |
290 | return false; |
291 | ++i; |
292 | } |
293 | return true; |
294 | } |
295 | |
296 | template <typename T> |
297 | Q_OUTOFLINE_TEMPLATE QList<T> QSet<T>::values() const |
298 | { |
299 | QList<T> result; |
300 | result.reserve(size()); |
301 | typename QSet<T>::const_iterator i = constBegin(); |
302 | while (i != constEnd()) { |
303 | result.append(*i); |
304 | ++i; |
305 | } |
306 | return result; |
307 | } |
308 | |
309 | Q_DECLARE_SEQUENTIAL_ITERATOR(Set) |
310 | |
311 | #if !defined(QT_NO_JAVA_STYLE_ITERATORS) |
312 | template <typename T> |
313 | class QMutableSetIterator |
314 | { |
315 | typedef typename QSet<T>::iterator iterator; |
316 | QSet<T> *c; |
317 | iterator i, n; |
318 | inline bool item_exists() const { return c->constEnd() != n; } |
319 | |
320 | public: |
321 | inline QMutableSetIterator(QSet<T> &container) |
322 | : c(&container) |
323 | { i = c->begin(); n = c->end(); } |
324 | inline QMutableSetIterator &operator=(QSet<T> &container) |
325 | { c = &container; i = c->begin(); n = c->end(); return *this; } |
326 | inline void toFront() { i = c->begin(); n = c->end(); } |
327 | inline void toBack() { i = c->end(); n = i; } |
328 | inline bool hasNext() const { return c->constEnd() != i; } |
329 | inline const T &next() { n = i++; return *n; } |
330 | inline const T &peekNext() const { return *i; } |
331 | inline void remove() |
332 | { if (c->constEnd() != n) { i = c->erase(n); n = c->end(); } } |
333 | inline const T &value() const { Q_ASSERT(item_exists()); return *n; } |
334 | inline bool findNext(const T &t) |
335 | { while (c->constEnd() != (n = i)) if (*i++ == t) return true; return false; } |
336 | }; |
337 | #endif // QT_NO_JAVA_STYLE_ITERATORS |
338 | |
339 | template <typename T, typename Predicate> |
340 | qsizetype erase_if(QSet<T> &set, Predicate pred) |
341 | { |
342 | return QtPrivate::qset_erase_if(set, pred); |
343 | } |
344 | |
345 | QT_END_NAMESPACE |
346 | |
347 | #endif // QSET_H |
348 | |