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 | |
43 | class KItemSet |
44 | { |
45 | public: |
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 | |
265 | private: |
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 | |
290 | inline KItemSet::KItemSet() : |
291 | m_itemRanges() |
292 | { |
293 | } |
294 | |
295 | inline KItemSet::KItemSet(const KItemSet& other) : |
296 | m_itemRanges(other.m_itemRanges) |
297 | { |
298 | } |
299 | |
300 | inline 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 | |
309 | inline bool KItemSet::isEmpty() const |
310 | { |
311 | return m_itemRanges.isEmpty(); |
312 | } |
313 | |
314 | inline void KItemSet::clear() |
315 | { |
316 | m_itemRanges.clear(); |
317 | } |
318 | |
319 | inline bool KItemSet::operator==(const KItemSet& other) const |
320 | { |
321 | return m_itemRanges == other.m_itemRanges; |
322 | } |
323 | |
324 | inline bool KItemSet::operator!=(const KItemSet& other) const |
325 | { |
326 | return m_itemRanges != other.m_itemRanges; |
327 | } |
328 | |
329 | inline bool KItemSet::contains(int i) const |
330 | { |
331 | const KItemRangeList::const_iterator it = constRangeForItem(i); |
332 | return it != m_itemRanges.end(); |
333 | } |
334 | |
335 | inline 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 | |
345 | inline 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 | |
355 | inline 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 | |
366 | inline KItemSet::iterator KItemSet::begin() |
367 | { |
368 | return iterator(m_itemRanges.begin(), 0); |
369 | } |
370 | |
371 | inline KItemSet::const_iterator KItemSet::begin() const |
372 | { |
373 | return const_iterator(m_itemRanges.begin(), 0); |
374 | } |
375 | |
376 | inline KItemSet::const_iterator KItemSet::constBegin() const |
377 | { |
378 | return const_iterator(m_itemRanges.constBegin(), 0); |
379 | } |
380 | |
381 | inline KItemSet::iterator KItemSet::end() |
382 | { |
383 | return iterator(m_itemRanges.end(), 0); |
384 | } |
385 | |
386 | inline KItemSet::const_iterator KItemSet::end() const |
387 | { |
388 | return const_iterator(m_itemRanges.end(), 0); |
389 | } |
390 | |
391 | inline KItemSet::const_iterator KItemSet::constEnd() const |
392 | { |
393 | return const_iterator(m_itemRanges.constEnd(), 0); |
394 | } |
395 | |
396 | inline int KItemSet::first() const |
397 | { |
398 | return m_itemRanges.first().index; |
399 | } |
400 | |
401 | inline int KItemSet::last() const |
402 | { |
403 | const KItemRange& lastRange = m_itemRanges.last(); |
404 | return lastRange.index + lastRange.count - 1; |
405 | } |
406 | |
407 | inline KItemSet& KItemSet::operator<<(int i) |
408 | { |
409 | insert(i); |
410 | return *this; |
411 | } |
412 | |
413 | #endif |
414 | |