1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies). |
4 | ** Contact: http://www.qt-project.org/legal |
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 Digia. For licensing terms and |
14 | ** conditions see http://qt.digia.com/licensing. For further information |
15 | ** use the contact form at http://qt.digia.com/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 2.1 as published by the Free Software |
20 | ** Foundation and appearing in the file LICENSE.LGPL included in the |
21 | ** packaging of this file. Please review the following information to |
22 | ** ensure the GNU Lesser General Public License version 2.1 requirements |
23 | ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. |
24 | ** |
25 | ** In addition, as a special exception, Digia gives you certain additional |
26 | ** rights. These rights are described in the Digia Qt LGPL Exception |
27 | ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. |
28 | ** |
29 | ** GNU General Public License Usage |
30 | ** Alternatively, this file may be used under the terms of the GNU |
31 | ** General Public License version 3.0 as published by the Free Software |
32 | ** Foundation and appearing in the file LICENSE.GPL included in the |
33 | ** packaging of this file. Please review the following information to |
34 | ** ensure the GNU General Public License version 3.0 requirements will be |
35 | ** met: http://www.gnu.org/copyleft/gpl.html. |
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 | #ifdef Q_COMPILER_RVALUE_REFS |
65 | inline QSet<T> &operator=(QSet<T> &&other) |
66 | { qSwap(q_hash, other.q_hash); return *this; } |
67 | #endif |
68 | inline void swap(QSet<T> &other) { q_hash.swap(other.q_hash); } |
69 | |
70 | inline bool operator==(const QSet<T> &other) const |
71 | { return q_hash == other.q_hash; } |
72 | inline bool operator!=(const QSet<T> &other) const |
73 | { return q_hash != other.q_hash; } |
74 | |
75 | inline int size() const { return q_hash.size(); } |
76 | |
77 | inline bool isEmpty() const { return q_hash.isEmpty(); } |
78 | |
79 | inline int capacity() const { return q_hash.capacity(); } |
80 | inline void reserve(int size); |
81 | inline void squeeze() { q_hash.squeeze(); } |
82 | |
83 | inline void detach() { q_hash.detach(); } |
84 | inline bool isDetached() const { return q_hash.isDetached(); } |
85 | inline void setSharable(bool sharable) { q_hash.setSharable(sharable); } |
86 | |
87 | inline void clear() { q_hash.clear(); } |
88 | |
89 | inline bool remove(const T &value) { return q_hash.remove(value) != 0; } |
90 | |
91 | inline bool contains(const T &value) const { return q_hash.contains(value); } |
92 | |
93 | bool contains(const QSet<T> &set) const; |
94 | |
95 | class const_iterator; |
96 | |
97 | class iterator |
98 | { |
99 | typedef QHash<T, QHashDummyValue> Hash; |
100 | typename Hash::iterator i; |
101 | friend class const_iterator; |
102 | |
103 | public: |
104 | typedef std::bidirectional_iterator_tag iterator_category; |
105 | typedef qptrdiff difference_type; |
106 | typedef T value_type; |
107 | typedef const T *pointer; |
108 | typedef const T &reference; |
109 | |
110 | inline iterator() {} |
111 | inline iterator(typename Hash::iterator o) : i(o) {} |
112 | inline iterator(const iterator &o) : i(o.i) {} |
113 | inline iterator &operator=(const iterator &o) { i = o.i; return *this; } |
114 | inline const T &operator*() const { return i.key(); } |
115 | inline const T *operator->() const { return &i.key(); } |
116 | inline bool operator==(const iterator &o) const { return i == o.i; } |
117 | inline bool operator!=(const iterator &o) const { return i != o.i; } |
118 | inline bool operator==(const const_iterator &o) const |
119 | { return i == o.i; } |
120 | inline bool operator!=(const const_iterator &o) const |
121 | { return i != o.i; } |
122 | inline iterator &operator++() { ++i; return *this; } |
123 | inline iterator operator++(int) { iterator r = *this; ++i; return r; } |
124 | inline iterator &operator--() { --i; return *this; } |
125 | inline iterator operator--(int) { iterator r = *this; --i; return r; } |
126 | inline iterator operator+(int j) const { return i + j; } |
127 | inline iterator operator-(int j) const { return i - j; } |
128 | inline iterator &operator+=(int j) { i += j; return *this; } |
129 | inline iterator &operator-=(int j) { i -= j; return *this; } |
130 | }; |
131 | |
132 | class const_iterator |
133 | { |
134 | typedef QHash<T, QHashDummyValue> Hash; |
135 | typename Hash::const_iterator i; |
136 | friend class iterator; |
137 | |
138 | public: |
139 | typedef std::bidirectional_iterator_tag iterator_category; |
140 | typedef qptrdiff difference_type; |
141 | typedef T value_type; |
142 | typedef const T *pointer; |
143 | typedef const T &reference; |
144 | |
145 | inline const_iterator() {} |
146 | inline const_iterator(typename Hash::const_iterator o) : i(o) {} |
147 | inline const_iterator(const const_iterator &o) : i(o.i) {} |
148 | inline const_iterator(const iterator &o) |
149 | : i(o.i) {} |
150 | inline const_iterator &operator=(const const_iterator &o) { i = o.i; return *this; } |
151 | inline const T &operator*() const { return i.key(); } |
152 | inline const T *operator->() const { return &i.key(); } |
153 | inline bool operator==(const const_iterator &o) const { return i == o.i; } |
154 | inline bool operator!=(const const_iterator &o) const { return i != o.i; } |
155 | inline const_iterator &operator++() { ++i; return *this; } |
156 | inline const_iterator operator++(int) { const_iterator r = *this; ++i; return r; } |
157 | inline const_iterator &operator--() { --i; return *this; } |
158 | inline const_iterator operator--(int) { const_iterator r = *this; --i; return r; } |
159 | inline const_iterator operator+(int j) const { return i + j; } |
160 | inline const_iterator operator-(int j) const { return i - j; } |
161 | inline const_iterator &operator+=(int j) { i += j; return *this; } |
162 | inline const_iterator &operator-=(int j) { i -= j; return *this; } |
163 | }; |
164 | |
165 | // STL style |
166 | inline iterator begin() { return q_hash.begin(); } |
167 | inline const_iterator begin() const { return q_hash.begin(); } |
168 | inline const_iterator constBegin() const { return q_hash.constBegin(); } |
169 | inline iterator end() { return q_hash.end(); } |
170 | inline const_iterator end() const { return q_hash.end(); } |
171 | inline const_iterator constEnd() const { return q_hash.constEnd(); } |
172 | iterator erase(iterator i) |
173 | { return q_hash.erase(reinterpret_cast<typename Hash::iterator &>(i)); } |
174 | |
175 | // more Qt |
176 | typedef iterator Iterator; |
177 | typedef const_iterator ConstIterator; |
178 | inline int count() const { return q_hash.count(); } |
179 | inline const_iterator insert(const T &value) // ### Qt 5: should return an 'iterator' |
180 | { return static_cast<typename Hash::const_iterator>(q_hash.insert(value, |
181 | 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 | QSet<T> &subtract(const QSet<T> &other); |
188 | |
189 | // STL compatibility |
190 | typedef T key_type; |
191 | typedef T value_type; |
192 | typedef value_type *pointer; |
193 | typedef const value_type *const_pointer; |
194 | typedef value_type &reference; |
195 | typedef const value_type &const_reference; |
196 | typedef qptrdiff difference_type; |
197 | typedef int size_type; |
198 | |
199 | inline bool empty() const { return isEmpty(); } |
200 | // comfort |
201 | inline QSet<T> &operator<<(const T &value) { insert(value); return *this; } |
202 | inline QSet<T> &operator|=(const QSet<T> &other) { unite(other); return *this; } |
203 | inline QSet<T> &operator|=(const T &value) { insert(value); return *this; } |
204 | inline QSet<T> &operator&=(const QSet<T> &other) { intersect(other); return *this; } |
205 | inline QSet<T> &operator&=(const T &value) |
206 | { QSet<T> result; if (contains(value)) result.insert(value); return (*this = result); } |
207 | inline QSet<T> &operator+=(const QSet<T> &other) { unite(other); return *this; } |
208 | inline QSet<T> &operator+=(const T &value) { insert(value); return *this; } |
209 | inline QSet<T> &operator-=(const QSet<T> &other) { subtract(other); return *this; } |
210 | inline QSet<T> &operator-=(const T &value) { remove(value); return *this; } |
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 | inline QSet<T> operator+(const QSet<T> &other) const |
216 | { QSet<T> result = *this; result += other; return result; } |
217 | inline QSet<T> operator-(const QSet<T> &other) const |
218 | { QSet<T> result = *this; result -= other; return result; } |
219 | #if QT_VERSION < 0x050000 |
220 | // ### Qt 5: remove |
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 | inline QSet<T> operator+(const QSet<T> &other) |
226 | { QSet<T> result = *this; result += other; return result; } |
227 | inline QSet<T> operator-(const QSet<T> &other) |
228 | { QSet<T> result = *this; result -= other; return result; } |
229 | #endif |
230 | |
231 | QList<T> toList() const; |
232 | inline QList<T> values() const { return toList(); } |
233 | |
234 | static QSet<T> fromList(const QList<T> &list); |
235 | |
236 | private: |
237 | Hash q_hash; |
238 | }; |
239 | |
240 | template <class T> |
241 | Q_INLINE_TEMPLATE void QSet<T>::reserve(int asize) { q_hash.reserve(asize); } |
242 | |
243 | template <class T> |
244 | Q_INLINE_TEMPLATE QSet<T> &QSet<T>::unite(const QSet<T> &other) |
245 | { |
246 | QSet<T> copy(other); |
247 | typename QSet<T>::const_iterator i = copy.constEnd(); |
248 | while (i != copy.constBegin()) { |
249 | --i; |
250 | insert(*i); |
251 | } |
252 | return *this; |
253 | } |
254 | |
255 | template <class T> |
256 | Q_INLINE_TEMPLATE QSet<T> &QSet<T>::intersect(const QSet<T> &other) |
257 | { |
258 | QSet<T> copy1(*this); |
259 | QSet<T> copy2(other); |
260 | typename QSet<T>::const_iterator i = copy1.constEnd(); |
261 | while (i != copy1.constBegin()) { |
262 | --i; |
263 | if (!copy2.contains(*i)) |
264 | remove(*i); |
265 | } |
266 | return *this; |
267 | } |
268 | |
269 | template <class T> |
270 | Q_INLINE_TEMPLATE QSet<T> &QSet<T>::subtract(const QSet<T> &other) |
271 | { |
272 | QSet<T> copy1(*this); |
273 | QSet<T> copy2(other); |
274 | typename QSet<T>::const_iterator i = copy1.constEnd(); |
275 | while (i != copy1.constBegin()) { |
276 | --i; |
277 | if (copy2.contains(*i)) |
278 | remove(*i); |
279 | } |
280 | return *this; |
281 | } |
282 | |
283 | template <class T> |
284 | Q_INLINE_TEMPLATE bool QSet<T>::contains(const QSet<T> &other) const |
285 | { |
286 | typename QSet<T>::const_iterator i = other.constBegin(); |
287 | while (i != other.constEnd()) { |
288 | if (!contains(*i)) |
289 | return false; |
290 | ++i; |
291 | } |
292 | return true; |
293 | } |
294 | |
295 | template <typename T> |
296 | Q_OUTOFLINE_TEMPLATE QList<T> QSet<T>::toList() const |
297 | { |
298 | QList<T> result; |
299 | result.reserve(size()); |
300 | typename QSet<T>::const_iterator i = constBegin(); |
301 | while (i != constEnd()) { |
302 | result.append(*i); |
303 | ++i; |
304 | } |
305 | return result; |
306 | } |
307 | |
308 | template <typename T> |
309 | Q_OUTOFLINE_TEMPLATE QSet<T> QList<T>::toSet() const |
310 | { |
311 | QSet<T> result; |
312 | result.reserve(size()); |
313 | for (int i = 0; i < size(); ++i) |
314 | result.insert(at(i)); |
315 | return result; |
316 | } |
317 | |
318 | template <typename T> |
319 | QSet<T> QSet<T>::fromList(const QList<T> &list) |
320 | { |
321 | return list.toSet(); |
322 | } |
323 | |
324 | template <typename T> |
325 | QList<T> QList<T>::fromSet(const QSet<T> &set) |
326 | { |
327 | return set.toList(); |
328 | } |
329 | |
330 | Q_DECLARE_SEQUENTIAL_ITERATOR(Set) |
331 | |
332 | template <typename T> |
333 | class QMutableSetIterator |
334 | { |
335 | typedef typename QSet<T>::iterator iterator; |
336 | QSet<T> *c; |
337 | iterator i, n; |
338 | inline bool item_exists() const { return c->constEnd() != n; } |
339 | |
340 | public: |
341 | inline QMutableSetIterator(QSet<T> &container) |
342 | : c(&container) |
343 | { c->setSharable(false); i = c->begin(); n = c->end(); } |
344 | inline ~QMutableSetIterator() |
345 | { c->setSharable(true); } |
346 | inline QMutableSetIterator &operator=(QSet<T> &container) |
347 | { c->setSharable(true); c = &container; c->setSharable(false); |
348 | i = c->begin(); n = c->end(); return *this; } |
349 | inline void toFront() { i = c->begin(); n = c->end(); } |
350 | inline void toBack() { i = c->end(); n = i; } |
351 | inline bool hasNext() const { return c->constEnd() != i; } |
352 | inline const T &next() { n = i++; return *n; } |
353 | inline const T &peekNext() const { return *i; } |
354 | inline bool hasPrevious() const { return c->constBegin() != i; } |
355 | inline const T &previous() { n = --i; return *n; } |
356 | inline const T &peekPrevious() const { iterator p = i; return *--p; } |
357 | inline void remove() |
358 | { if (c->constEnd() != n) { i = c->erase(n); n = c->end(); } } |
359 | inline const T &value() const { Q_ASSERT(item_exists()); return *n; } |
360 | inline bool findNext(const T &t) |
361 | { while (c->constEnd() != (n = i)) if (*i++ == t) return true; return false; } |
362 | inline bool findPrevious(const T &t) |
363 | { while (c->constBegin() != i) if (*(n = --i) == t) return true; |
364 | n = c->end(); return false; } |
365 | }; |
366 | |
367 | QT_END_NAMESPACE |
368 | |
369 | QT_END_HEADER |
370 | |
371 | #endif // QSET_H |
372 | |