Qt 4.8
qset.h
Go to the documentation of this file.
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 
48 
50 
51 QT_MODULE(Core)
52 
53 template <class T>
54 class QSet
55 {
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  {
100  typename Hash::iterator i;
101  friend class const_iterator;
102 
103  public:
104  typedef std::bidirectional_iterator_tag iterator_category;
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 
133  {
136  friend class iterator;
137 
138  public:
139  typedef std::bidirectional_iterator_tag iterator_category;
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(); }
173  { return q_hash.erase(reinterpret_cast<typename Hash::iterator &>(i)); }
174 
175  // more Qt
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;
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>
242 
243 template <class T>
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>
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>
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>
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>
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>
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>
320 {
321  return list.toSet();
322 }
323 
324 template <typename T>
326 {
327  return set.toList();
328 }
329 
331 
332 template <typename T>
334 {
335  typedef typename QSet<T>::iterator iterator;
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(); }
345  { c->setSharable(true); }
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 
368 
370 
371 #endif // QSET_H
QSet< T > & operator|=(const QSet< T > &other)
Definition: qset.h:202
bool operator!=(const QSet< T > &other) const
Definition: qset.h:72
int capacity() const
Definition: qset.h:79
iterator & operator=(const iterator &o)
Definition: qset.h:113
void setSharable(bool sharable)
Definition: qhash.h:305
QSet< T > & unite(const QSet< T > &other)
Definition: qset.h:244
QHash< T, QHashDummyValue > Hash
Definition: qset.h:134
bool isDetached() const
Returns true if the hash&#39;s internal data isn&#39;t shared with any other hash object; otherwise returns f...
Definition: qhash.h:304
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
QSet< T > toSet() const
Returns a QSet object with the data contained in this QList.
Definition: qset.h:309
qptrdiff difference_type
Definition: qset.h:140
#define QT_MODULE(x)
Definition: qglobal.h:2783
void clear()
Removes all items from the hash.
Definition: qhash.h:574
const_iterator & operator+=(int j)
Definition: qset.h:161
const_iterator & operator--()
Definition: qset.h:157
int remove(const Key &key)
Removes all the items that have the key from the hash.
Definition: qhash.h:784
T value_type
Definition: qset.h:191
const T & reference
Definition: qset.h:143
#define QT_BEGIN_HEADER
Definition: qglobal.h:136
const_iterator & operator++()
Definition: qset.h:155
iterator operator-(int j) const
Definition: qset.h:127
QSet< T > operator-(const QSet< T > &other)
Definition: qset.h:227
const_iterator(const iterator &o)
Definition: qset.h:148
iterator n
Definition: qset.h:337
QSet< T > & operator<<(const T &value)
Definition: qset.h:201
#define at(className, varName)
const_iterator constEnd() const
Definition: qset.h:171
QSet< T > & operator|=(const T &value)
Definition: qset.h:203
bool isEmpty() const
Definition: qset.h:77
QSet< T > * c
Definition: qset.h:336
Hash::iterator i
Definition: qset.h:100
bool operator==(const QSet< T > &other) const
Definition: qset.h:70
QSet< T > operator|(const QSet< T > &other)
Definition: qset.h:221
const T & reference
Definition: qset.h:108
QSet(const QSet< T > &other)
Definition: qset.h:60
const T * pointer
Definition: qset.h:142
void squeeze()
Reduces the size of the QHash&#39;s internal hash table to save memory.
Definition: qhash.h:301
iterator(const iterator &o)
Definition: qset.h:112
const_iterator find(const T &value) const
Definition: qset.h:183
QSet< T > & operator &=(const QSet< T > &other)
Definition: qset.h:204
void swap(QHash< Key, T > &other)
Swaps hash other with this hash.
Definition: qhash.h:290
#define Q_ASSERT(cond)
Definition: qglobal.h:1823
iterator begin()
Definition: qset.h:166
bool contains(const Key &key) const
Returns true if the hash contains an item with the key; otherwise returns false.
Definition: qhash.h:872
const T * pointer
Definition: qset.h:107
QSet< T >::iterator iterator
Definition: qset.h:335
void reserve(int size)
Ensures that the QHash&#39;s internal hash table consists of at least size buckets.
Definition: qhash.h:846
iterator insert(const Key &key, const T &value)
Inserts a new item with the key and a value of value.
Definition: qhash.h:753
int size() const
Definition: qset.h:75
value_type * pointer
Definition: qset.h:192
const_iterator & operator-=(int j)
Definition: qset.h:162
const T & operator*() const
Definition: qset.h:151
bool findNext(const T &t)
Definition: qset.h:360
QSet< T > & operator=(const QSet< T > &other)
Definition: qset.h:62
bool item_exists() const
Definition: qset.h:338
void append(const T &t)
Inserts value at the end of the list.
Definition: qlist.h:507
iterator & operator-=(int j)
Definition: qset.h:129
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
#define Q_DECLARE_SEQUENTIAL_ITERATOR(C)
Definition: qiterator.h:83
QSet< T > & intersect(const QSet< T > &other)
Definition: qset.h:256
QSet< T > & operator+=(const QSet< T > &other)
Definition: qset.h:207
friend class const_iterator
Definition: qset.h:101
const_iterator operator-(int j) const
Definition: qset.h:160
const_iterator begin() const
Definition: qset.h:167
const T & peekPrevious() const
Definition: qset.h:356
QIntegerForSizeof< void * >::Signed qptrdiff
Definition: qglobal.h:987
bool contains(const T &value) const
Definition: qset.h:91
QList< T > toList() const
Definition: qset.h:296
QSet< T > operator &(const QSet< T > &other) const
Definition: qset.h:213
const_iterator constFind(const T &value) const
Definition: qset.h:184
bool operator!=(const const_iterator &o) const
Definition: qset.h:154
QSet< T > operator &(const QSet< T > &other)
Definition: qset.h:223
iterator end()
Definition: qset.h:169
bool isEmpty() const
Returns true if the hash contains no items; otherwise returns false.
Definition: qhash.h:297
const_iterator ConstIterator
Definition: qset.h:177
const_iterator insert(const T &value)
Definition: qset.h:179
const_iterator operator++(int)
Definition: qset.h:156
#define Q_INLINE_TEMPLATE
Definition: qglobal.h:1713
qptrdiff difference_type
Definition: qset.h:105
void detach()
Definition: qset.h:83
bool operator!=(const const_iterator &o) const
Definition: qset.h:120
void clear()
Definition: qset.h:87
std::bidirectional_iterator_tag iterator_category
Definition: qset.h:104
const value_type * const_pointer
Definition: qset.h:193
int count() const
Definition: qset.h:178
iterator operator++(int)
Definition: qset.h:123
void setSharable(bool sharable)
Definition: qset.h:85
QSet< T > & subtract(const QSet< T > &other)
Definition: qset.h:270
static QList< T > fromSet(const QSet< T > &set)
Returns a QList object with the data contained in set.
Definition: qset.h:325
void qSwap(T &value1, T &value2)
Definition: qglobal.h:2181
const T & next()
Definition: qset.h:352
void toFront()
Definition: qset.h:349
QSet()
Definition: qset.h:59
const_iterator constBegin() const
Returns a const STL-style iterator pointing to the first item in the hash.
Definition: qhash.h:466
const_iterator(typename Hash::const_iterator o)
Definition: qset.h:146
QHash< T, QHashDummyValue > Hash
Definition: qset.h:99
const_iterator constEnd() const
Returns a const STL-style iterator pointing to the imaginary item after the last item in the hash...
Definition: qhash.h:469
QSet< T > operator+(const QSet< T > &other)
Definition: qset.h:225
bool findPrevious(const T &t)
Definition: qset.h:362
T key_type
Definition: qset.h:190
bool operator==(const iterator &o) const
Definition: qset.h:116
int size() const
Returns the number of items in the hash.
Definition: qhash.h:295
qptrdiff difference_type
Definition: qset.h:196
Hash q_hash
Definition: qset.h:237
bool hasNext() const
Definition: qset.h:351
iterator end()
Returns an STL-style iterator pointing to the imaginary item after the last item in the hash...
Definition: qhash.h:467
QSet< T > operator-(const QSet< T > &other) const
Definition: qset.h:217
const value_type & const_reference
Definition: qset.h:195
iterator & operator++()
Definition: qset.h:122
bool isDetached() const
Definition: qset.h:84
void swap(QSet< T > &other)
Definition: qset.h:68
const T * operator->() const
Definition: qset.h:115
void toBack()
Definition: qset.h:350
void detach()
Detaches this hash from any other hashes with which it may share data.
Definition: qhash.h:303
iterator & operator+=(int j)
Definition: qset.h:128
const T & previous()
Definition: qset.h:355
const T & peekNext() const
Definition: qset.h:353
const_iterator & operator=(const const_iterator &o)
Definition: qset.h:150
QMutableSetIterator(QSet< T > &container)
Definition: qset.h:341
bool operator!=(const iterator &o) const
Definition: qset.h:117
void squeeze()
Definition: qset.h:81
int size_type
Definition: qset.h:197
const_iterator operator+(int j) const
Definition: qset.h:159
iterator begin()
Returns an STL-style iterator pointing to the first item in the hash.
Definition: qhash.h:464
const_iterator constBegin() const
Definition: qset.h:168
QSet< T > & operator-=(const T &value)
Definition: qset.h:210
const_iterator operator--(int)
Definition: qset.h:158
bool operator==(const const_iterator &o) const
Definition: qset.h:153
QHash< T, QHashDummyValue > Hash
Definition: qset.h:56
iterator & operator--()
Definition: qset.h:124
~QMutableSetIterator()
Definition: qset.h:344
iterator Iterator
Definition: qset.h:176
QSet< T > & operator-=(const QSet< T > &other)
Definition: qset.h:209
int count(const Key &key) const
Returns the number of items associated with the key.
Definition: qhash.h:719
Hash::const_iterator i
Definition: qset.h:135
const_iterator end() const
Definition: qset.h:170
int capacity() const
Returns the number of buckets in the QHash&#39;s internal hash table.
Definition: qhash.h:299
bool operator==(const const_iterator &o) const
Definition: qset.h:118
const_iterator(const const_iterator &o)
Definition: qset.h:147
iterator find(const Key &key)
Returns an iterator pointing to the item with the key in the hash.
Definition: qhash.h:865
QList< T > values() const
Definition: qset.h:232
const T & value() const
Definition: qset.h:359
QMutableSetIterator & operator=(QSet< T > &container)
Definition: qset.h:346
static QSet< T > fromList(const QList< T > &list)
Definition: qset.h:319
bool empty() const
Definition: qset.h:199
#define Q_OUTOFLINE_TEMPLATE
Definition: qglobal.h:1710
iterator erase(iterator i)
Definition: qset.h:172
std::bidirectional_iterator_tag iterator_category
Definition: qset.h:139
const T * operator->() const
Definition: qset.h:152
#define QT_END_HEADER
Definition: qglobal.h:137
const T & operator*() const
Definition: qset.h:114
bool hasPrevious() const
Definition: qset.h:354
QSet< T > operator+(const QSet< T > &other) const
Definition: qset.h:215
iterator erase(iterator it)
Removes the (key, value) pair associated with the iterator pos from the hash, and returns an iterator...
Definition: qhash.h:827
iterator operator+(int j) const
Definition: qset.h:126
iterator(typename Hash::iterator o)
Definition: qset.h:111
friend class iterator
Definition: qhash.h:393
iterator find(const T &value)
Definition: qset.h:182
friend class const_iterator
Definition: qhash.h:461
QSet< T > & operator &=(const T &value)
Definition: qset.h:205
void reserve(int size)
Reserve space for alloc elements.
Definition: qlist.h:496
iterator operator--(int)
Definition: qset.h:125
QSet< T > & operator+=(const T &value)
Definition: qset.h:208
The QList class is a template class that provides lists.
Definition: qdatastream.h:62
QSet< T > operator|(const QSet< T > &other) const
Definition: qset.h:211
T value_type
Definition: qset.h:106
void reserve(int size)
Definition: qset.h:241
value_type & reference
Definition: qset.h:194