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