1/***************************************************************************
2 * Copyright (C) 2013 by Frank Reininghaus <frank78ac@googlemail.com> *
3 * *
4 * This program is free software; you can redistribute it and/or modify *
5 * it under the terms of the GNU General Public License as published by *
6 * the Free Software Foundation; either version 2 of the License, or *
7 * (at your option) any later version. *
8 * *
9 * This program is distributed in the hope that it will be useful, *
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
12 * GNU General Public License for more details. *
13 * *
14 * You should have received a copy of the GNU General Public License *
15 * along with this program; if not, write to the *
16 * Free Software Foundation, Inc., *
17 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA *
18 ***************************************************************************/
19
20#ifndef KITEMSET_H
21#define KITEMSET_H
22
23#include <kitemviews/kitemrange.h>
24
25/**
26 * @brief Stores a set of integer numbers in a space-efficient way.
27 *
28 * This class is similar to QSet<int>, but it has the following advantages:
29 *
30 * 1. It uses less memory than a QSet<int> if many consecutive numbers are
31 * stored. This is achieved by not storing each number separately, but
32 * "ranges" of numbers.
33 *
34 * Example: The set {1, 2, 3, 4, 5} is represented by a single range which
35 * starts at 1 and has the length 5.
36 *
37 * 2. When iterating through a KItemSet using KItemSet::iterator or
38 * KItemSet::const_iterator, the numbers are traversed in ascending order.
39 *
40 * The complexity of most operations depends on the number of ranges.
41 */
42
43class KItemSet
44{
45public:
46 KItemSet();
47 KItemSet(const KItemSet& other);
48
49 /**
50 * Returns the number of items in the set.
51 * Complexity: O(log(number of ranges)).
52 */
53 int count() const;
54
55 bool isEmpty() const;
56 void clear();
57
58 bool operator==(const KItemSet& other) const;
59 bool operator!=(const KItemSet& other) const;
60
61 class iterator
62 {
63 iterator(const KItemRangeList::iterator& rangeIt, int offset) :
64 m_rangeIt(rangeIt),
65 m_offset(offset)
66 {
67 }
68
69 public:
70 iterator(const iterator& other) :
71 m_rangeIt(other.m_rangeIt),
72 m_offset(other.m_offset)
73 {
74 }
75
76 iterator& operator=(const iterator& other)
77 {
78 m_rangeIt = other.m_rangeIt;
79 m_offset = other.m_offset;
80 return *this;
81 }
82
83 int operator*() const
84 {
85 return m_rangeIt->index + m_offset;
86 }
87
88 inline bool operator==(const iterator& other) const
89 {
90 return m_rangeIt == other.m_rangeIt && m_offset == other.m_offset;
91 }
92
93 inline bool operator!=(const iterator& other) const
94 {
95 return !(*this == other);
96 }
97
98 inline iterator& operator++()
99 {
100 ++m_offset;
101
102 if (m_offset == m_rangeIt->count) {
103 ++m_rangeIt;
104 m_offset = 0;
105 }
106
107 return *this;
108 }
109
110 inline iterator operator++(int)
111 {
112 iterator r = *this;
113 ++(*this);
114 return r;
115 }
116
117 inline iterator& operator--()
118 {
119 if (m_offset == 0) {
120 --m_rangeIt;
121 m_offset = m_rangeIt->count - 1;
122 } else {
123 --m_offset;
124 }
125
126 return *this;
127 }
128
129 inline iterator operator--(int)
130 {
131 iterator r = *this;
132 --(*this);
133 return r;
134 }
135
136 private:
137 KItemRangeList::iterator m_rangeIt;
138 int m_offset;
139
140 friend class const_iterator;
141 friend class KItemSet;
142 };
143
144
145 class const_iterator
146 {
147 const_iterator(KItemRangeList::const_iterator rangeIt, int offset) :
148 m_rangeIt(rangeIt),
149 m_offset(offset)
150 {
151 }
152
153 public:
154 const_iterator(const const_iterator& other) :
155 m_rangeIt(other.m_rangeIt),
156 m_offset(other.m_offset)
157 {
158 }
159
160 const_iterator(const iterator& other) :
161 m_rangeIt(other.m_rangeIt),
162 m_offset(other.m_offset)
163 {
164 }
165
166 const_iterator& operator=(const const_iterator& other)
167 {
168 m_rangeIt = other.m_rangeIt;
169 m_offset = other.m_offset;
170 return *this;
171 }
172
173 int operator*() const
174 {
175 return m_rangeIt->index + m_offset;
176 }
177
178 inline bool operator==(const const_iterator& other) const
179 {
180 return m_rangeIt == other.m_rangeIt && m_offset == other.m_offset;
181 }
182
183 inline bool operator!=(const const_iterator& other) const
184 {
185 return !(*this == other);
186 }
187
188 inline const_iterator& operator++()
189 {
190 ++m_offset;
191
192 if (m_offset == m_rangeIt->count) {
193 ++m_rangeIt;
194 m_offset = 0;
195 }
196
197 return *this;
198 }
199
200 inline const_iterator operator++(int)
201 {
202 const_iterator r = *this;
203 ++(*this);
204 return r;
205 }
206
207 inline const_iterator& operator--()
208 {
209 if (m_offset == 0) {
210 --m_rangeIt;
211 m_offset = m_rangeIt->count - 1;
212 } else {
213 --m_offset;
214 }
215
216 return *this;
217 }
218
219 inline const_iterator operator--(int)
220 {
221 const_iterator r = *this;
222 --(*this);
223 return r;
224 }
225
226 private:
227 KItemRangeList::const_iterator m_rangeIt;
228 int m_offset;
229
230 friend class KItemSet;
231 };
232
233 iterator begin();
234 const_iterator begin() const;
235 const_iterator constBegin() const;
236 iterator end();
237 const_iterator end() const;
238 const_iterator constEnd() const;
239
240 int first() const;
241 int last() const;
242
243 bool contains(int i) const;
244 iterator insert(int i);
245 iterator find(int i);
246 const_iterator constFind(int i) const;
247 bool remove(int i);
248 iterator erase(iterator it);
249
250 /**
251 * Returns a new set which contains all items that are contained in this
252 * KItemSet, in \a other, or in both.
253 */
254 KItemSet operator+(const KItemSet& other) const;
255
256 /**
257 * Returns a new set which contains all items that are contained either in
258 * this KItemSet, or in \a other, but not in both (the symmetric difference
259 * of both KItemSets).
260 */
261 KItemSet operator^(const KItemSet& other) const;
262
263 KItemSet& operator<<(int i);
264
265private:
266 /**
267 * Returns true if the KItemSet is valid, and false otherwise.
268 * A valid KItemSet must store the item ranges in ascending order, and
269 * the ranges must not overlap.
270 */
271 bool isValid() const;
272
273 /**
274 * This function returns an iterator that points to the KItemRange which
275 * contains i, or m_itemRanges.end() if no such range exists.
276 */
277 KItemRangeList::iterator rangeForItem(int i);
278
279 /**
280 * This function returns an iterator that points to the KItemRange which
281 * contains i, or m_itemRanges.constEnd() if no such range exists.
282 */
283 KItemRangeList::const_iterator constRangeForItem(int i) const;
284
285 KItemRangeList m_itemRanges;
286
287 friend class KItemSetTest;
288};
289
290inline KItemSet::KItemSet() :
291 m_itemRanges()
292{
293}
294
295inline KItemSet::KItemSet(const KItemSet& other) :
296 m_itemRanges(other.m_itemRanges)
297{
298}
299
300inline int KItemSet::count() const
301{
302 int result = 0;
303 foreach (const KItemRange& range, m_itemRanges) {
304 result += range.count;
305 }
306 return result;
307}
308
309inline bool KItemSet::isEmpty() const
310{
311 return m_itemRanges.isEmpty();
312}
313
314inline void KItemSet::clear()
315{
316 m_itemRanges.clear();
317}
318
319inline bool KItemSet::operator==(const KItemSet& other) const
320{
321 return m_itemRanges == other.m_itemRanges;
322}
323
324inline bool KItemSet::operator!=(const KItemSet& other) const
325{
326 return m_itemRanges != other.m_itemRanges;
327}
328
329inline bool KItemSet::contains(int i) const
330{
331 const KItemRangeList::const_iterator it = constRangeForItem(i);
332 return it != m_itemRanges.end();
333}
334
335inline KItemSet::iterator KItemSet::find(int i)
336{
337 const KItemRangeList::iterator it = rangeForItem(i);
338 if (it != m_itemRanges.end()) {
339 return iterator(it, i - it->index);
340 } else {
341 return end();
342 }
343}
344
345inline KItemSet::const_iterator KItemSet::constFind(int i) const
346{
347 const KItemRangeList::const_iterator it = constRangeForItem(i);
348 if (it != m_itemRanges.constEnd()) {
349 return const_iterator(it, i - it->index);
350 } else {
351 return constEnd();
352 }
353}
354
355inline bool KItemSet::remove(int i)
356{
357 iterator it = find(i);
358 if (it != end()) {
359 erase(it);
360 return true;
361 } else {
362 return false;
363 }
364}
365
366inline KItemSet::iterator KItemSet::begin()
367{
368 return iterator(m_itemRanges.begin(), 0);
369}
370
371inline KItemSet::const_iterator KItemSet::begin() const
372{
373 return const_iterator(m_itemRanges.begin(), 0);
374}
375
376inline KItemSet::const_iterator KItemSet::constBegin() const
377{
378 return const_iterator(m_itemRanges.constBegin(), 0);
379}
380
381inline KItemSet::iterator KItemSet::end()
382{
383 return iterator(m_itemRanges.end(), 0);
384}
385
386inline KItemSet::const_iterator KItemSet::end() const
387{
388 return const_iterator(m_itemRanges.end(), 0);
389}
390
391inline KItemSet::const_iterator KItemSet::constEnd() const
392{
393 return const_iterator(m_itemRanges.constEnd(), 0);
394}
395
396inline int KItemSet::first() const
397{
398 return m_itemRanges.first().index;
399}
400
401inline int KItemSet::last() const
402{
403 const KItemRange& lastRange = m_itemRanges.last();
404 return lastRange.index + lastRange.count - 1;
405}
406
407inline KItemSet& KItemSet::operator<<(int i)
408{
409 insert(i);
410 return *this;
411}
412
413#endif
414