Line data Source code
1 :
2 : /* Copyright (c) 2008-2016, Juan Hernando <jhernando@fi.upm.es>
3 : * Daniel Nachbaur <danielnachbaur@epfl.ch>
4 : *
5 : * This library is free software; you can redistribute it and/or modify it under
6 : * the terms of the GNU Lesser General Public License version 2.1 as published
7 : * by the Free Software Foundation.
8 : *
9 : * This library is distributed in the hope that it will be useful, but WITHOUT
10 : * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11 : * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
12 : * details.
13 : *
14 : * You should have received a copy of the GNU Lesser General Public License
15 : * along with this library; if not, write to the Free Software Foundation, Inc.,
16 : * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
17 : */
18 :
19 : #include <lunchbox/debug.h>
20 :
21 : #include <boost/iterator/iterator_facade.hpp>
22 :
23 : /** @cond IGNORE */
24 : namespace lunchbox
25 : {
26 : template <typename T>
27 : class IntervalSet<T>::const_iterator
28 : : public boost::iterator_facade<typename IntervalSet<T>::const_iterator, T,
29 : std::forward_iterator_tag, T>
30 : {
31 : public:
32 : // Default constructor to an end() iterator.
33 : const_iterator() {}
34 : private:
35 : friend class boost::iterator_core_access;
36 : friend class IntervalSet;
37 :
38 : typedef typename IntervalSet<T>::EdgeSet::const_iterator edge_iterator;
39 :
40 15 : const_iterator(const IntervalSet& set, const edge_iterator& interval)
41 : : _intervalIteratorEnd(set._intervals.end())
42 15 : , _startEdge(interval)
43 : {
44 15 : if (_startEdge != _intervalIteratorEnd)
45 2 : _value = _startEdge->first;
46 15 : }
47 :
48 4 : const_iterator(const IntervalSet& set, const edge_iterator& interval,
49 : const T& current)
50 : : _value(current)
51 : , _intervalIteratorEnd(set._intervals.end())
52 4 : , _startEdge(interval)
53 : {
54 4 : }
55 :
56 9 : void increment()
57 : {
58 9 : if (_startEdge == _intervalIteratorEnd)
59 0 : return;
60 :
61 9 : edge_iterator endEdge = _startEdge;
62 9 : ++endEdge;
63 : // Next element is inside the current interval.
64 9 : if (_value >= _startEdge->first && _value < endEdge->first)
65 7 : ++_value;
66 : else
67 : {
68 2 : ++_startEdge;
69 2 : ++_startEdge;
70 2 : if (_startEdge != _intervalIteratorEnd)
71 1 : _value = _startEdge->first;
72 : }
73 : }
74 :
75 11 : bool equal(const const_iterator& rhs) const
76 : {
77 14 : return (_startEdge == _intervalIteratorEnd &&
78 22 : rhs._startEdge == _intervalIteratorEnd) ||
79 19 : (_startEdge == rhs._startEdge && _value == rhs._value);
80 : }
81 :
82 11 : T dereference() const { return _value; }
83 : T _value;
84 : edge_iterator _intervalIteratorEnd;
85 : edge_iterator _startEdge;
86 : };
87 :
88 : template <typename T>
89 1 : IntervalSet<T>::IntervalSet()
90 1 : : _size(0)
91 : {
92 1 : }
93 :
94 : template <typename T>
95 1 : void IntervalSet<T>::insert(const T& element)
96 : {
97 1 : insert(element, element);
98 1 : }
99 :
100 : template <typename T>
101 1 : void IntervalSet<T>::erase(const T& element)
102 : {
103 1 : erase(element, element);
104 1 : }
105 :
106 : template <typename T>
107 6 : void IntervalSet<T>::insert(const T& startElement, const T& endElement)
108 : {
109 6 : LBASSERT(startElement <= endElement);
110 :
111 6 : Edge startValue(startElement, true);
112 6 : Edge endValue(endElement, false);
113 :
114 6 : if (_intervals.empty())
115 : {
116 2 : _intervals.insert(startValue);
117 2 : _intervals.insert(endValue);
118 2 : _size = endElement - startElement + 1;
119 2 : return;
120 : }
121 :
122 : // Finding the first edge whose value is less or equal than startElement.
123 : typename EdgeSet::iterator previous_to_start =
124 4 : _intervals.lower_bound(startValue);
125 4 : if (previous_to_start != _intervals.end())
126 : {
127 3 : if (previous_to_start == _intervals.begin())
128 : {
129 2 : if (startValue.first < previous_to_start->first)
130 1 : previous_to_start = _intervals.end();
131 : }
132 : else
133 1 : previous_to_start--;
134 : }
135 : else
136 1 : previous_to_start = (++_intervals.rbegin()).base();
137 :
138 : // Adding start edge as needed.
139 4 : typename EdgeSet::iterator position;
140 : bool fallsInside;
141 4 : size_t overlappingPortion = 0;
142 4 : T overlappingStart = T(); // initialized to silent a warning.
143 :
144 4 : if (previous_to_start == _intervals.end())
145 : {
146 : // Previous element doesn't exist and there is neither any of
147 : // equal value.
148 : // We have to insert start.
149 1 : position = _intervals.insert(startValue);
150 1 : fallsInside = false;
151 : }
152 3 : else if (!previous_to_start->second)
153 : {
154 : // Previous element is the end of one interval.
155 1 : if (previous_to_start->first + 1 == startElement)
156 : {
157 : // The end of previous interval end is one unit less than the start
158 : // of this interval. Removing the edge to fuse both.
159 0 : position = previous_to_start;
160 0 : position--;
161 0 : _intervals.erase(previous_to_start);
162 : }
163 : else
164 : // We have to insert start.
165 1 : position = _intervals.insert(previous_to_start, startValue);
166 1 : fallsInside = false;
167 : }
168 : else
169 : {
170 : // Start has fallen inside another interval we don't have to insert it.
171 2 : position = previous_to_start;
172 2 : fallsInside = true;
173 2 : overlappingStart = startElement;
174 : }
175 :
176 : // Now we have to check where the end goes.
177 4 : ++position;
178 10 : while (position != _intervals.end() && position->first <= endElement)
179 : {
180 : // Calculating the length of a possible interval overlapping the
181 : // interval being inserted.
182 3 : if (fallsInside)
183 : {
184 : // Previous position was the start of an overlapping interval.
185 2 : LBASSERT(!position->second);
186 2 : overlappingPortion += position->first - overlappingStart + 1;
187 : }
188 : else
189 1 : overlappingStart = position->first;
190 :
191 3 : fallsInside = position->second;
192 :
193 : // Note that the post-increment is evaluated before the function call
194 : // So position is actually pointing to the next one before the previous
195 : // element is erased.
196 3 : _intervals.erase(position++);
197 : }
198 :
199 4 : if (position != _intervals.end() && position->second &&
200 0 : position->first == endElement + 1)
201 : {
202 : // The end of the interval connects with the start of the next one.
203 : // We remove the start of the following one and don't insert this
204 : // edge.
205 0 : _intervals.erase(position);
206 : }
207 4 : else if (!fallsInside)
208 : {
209 : // End edge is not inside a previously existing interval so we
210 : // have to add it.
211 3 : _intervals.insert(position, endValue);
212 : }
213 : else
214 1 : overlappingPortion += endElement - overlappingStart + 1;
215 :
216 4 : _size += size_t(endElement - startElement + 1) - overlappingPortion;
217 4 : LBASSERT(_intervals.size() % 2 == 0);
218 : }
219 :
220 : template <typename T>
221 4 : void IntervalSet<T>::erase(const T& startElement, const T& endElement)
222 : {
223 4 : LBASSERT(startElement <= endElement);
224 :
225 4 : if (_intervals.empty())
226 1 : return;
227 :
228 : // Finding the first edge whose value is less or equal than startElement.
229 : typename EdgeSet::iterator nextToStart =
230 4 : _intervals.lower_bound(std::make_pair(startElement, true));
231 4 : typename EdgeSet::iterator previousToStart = nextToStart;
232 4 : if (nextToStart == _intervals.begin())
233 0 : previousToStart = _intervals.end();
234 4 : else if (nextToStart == _intervals.end())
235 : // Nothing to remove here
236 1 : return;
237 : else
238 3 : --previousToStart;
239 :
240 3 : typename EdgeSet::iterator position;
241 : bool inside;
242 3 : T overlappingStart = 0;
243 3 : size_t overlapping_portion = 0;
244 :
245 3 : if (previousToStart != _intervals.end())
246 : {
247 : // startElement is greater or equal than some interval edge.
248 3 : if (previousToStart->second)
249 : {
250 : // Inserting the new end of the interval starting at
251 : // previous_to_start.
252 3 : position =
253 6 : _intervals.insert(std::make_pair(startElement - 1, false));
254 3 : inside = true;
255 3 : overlappingStart = startElement;
256 : }
257 : else
258 : {
259 0 : position = previousToStart;
260 0 : inside = false;
261 : }
262 3 : ++position;
263 : }
264 : else
265 : {
266 : // startElement is less than the start of any interval.
267 0 : inside = false;
268 0 : position = _intervals.begin();
269 0 : overlappingStart = position->first;
270 : }
271 : // Position has the next edge after the last interval before the removal
272 : // interval.
273 :
274 7 : while (position != _intervals.end() && position->first <= endElement)
275 : {
276 2 : if (inside)
277 2 : overlapping_portion += position->first - overlappingStart + 1;
278 : else
279 0 : overlappingStart = position->first;
280 :
281 2 : inside = position->second;
282 :
283 : // Note that the post-increment is evaluated before the function call
284 : // So position is actually pointing to the next one before the previous
285 : // element is erased.
286 2 : _intervals.erase(position++);
287 : }
288 :
289 3 : if (inside)
290 : {
291 1 : LBASSERT(position != _intervals.end());
292 : // End edge is not inside a previously existing interval so we
293 : // have to add it.
294 1 : _intervals.insert(std::make_pair(endElement + 1, true));
295 1 : overlapping_portion += endElement - overlappingStart + 1;
296 : }
297 :
298 3 : _size -= overlapping_portion;
299 3 : LBASSERT(_intervals.size() % 2 == 0);
300 : }
301 :
302 : template <typename T>
303 : void IntervalSet<T>::insert(const IntervalSet& rhs)
304 : {
305 : for (typename EdgeSet::const_iterator i = rhs._intervals.begin();
306 : i != rhs._intervals.end(); ++i)
307 : {
308 : insert(i->first, i->second);
309 : }
310 : }
311 :
312 : template <typename T>
313 1 : void IntervalSet<T>::clear()
314 : {
315 1 : _intervals.clear();
316 1 : _size = 0;
317 1 : }
318 :
319 : template <typename T>
320 3 : bool IntervalSet<T>::exists(const T& element) const
321 : {
322 3 : return find(element) != end();
323 : }
324 :
325 : template <typename T>
326 6 : typename IntervalSet<T>::const_iterator IntervalSet<T>::find(
327 : const T& element) const
328 : {
329 6 : if (_intervals.empty())
330 0 : return end();
331 :
332 : typename EdgeSet::const_iterator next =
333 6 : _intervals.lower_bound(std::make_pair(element, false));
334 : // Note that if x equals the start edge of any interval then
335 : // next will be the end edge due to the use of (x, false) in the
336 : // search.
337 6 : if (next == _intervals.end() || next == _intervals.begin())
338 : // x cannot be inside any interval.
339 2 : return end();
340 :
341 4 : typename EdgeSet::const_iterator previous = next;
342 4 : --previous;
343 4 : if (previous->second)
344 4 : return const_iterator(*this, previous, element);
345 0 : return end();
346 : }
347 :
348 : template <typename T>
349 2 : typename IntervalSet<T>::const_iterator IntervalSet<T>::begin() const
350 : {
351 2 : if (_intervals.empty())
352 0 : return end();
353 2 : return const_iterator(*this, _intervals.begin());
354 : }
355 :
356 : template <typename T>
357 13 : typename IntervalSet<T>::const_iterator IntervalSet<T>::end() const
358 : {
359 13 : return const_iterator(*this, _intervals.end());
360 : }
361 :
362 : template <typename T>
363 12 : size_t IntervalSet<T>::size() const
364 : {
365 12 : return _size;
366 : }
367 :
368 : template <typename T>
369 2 : bool IntervalSet<T>::empty() const
370 : {
371 2 : return size() == 0;
372 : }
373 :
374 : template <typename T>
375 : void IntervalSet<T>::swap(IntervalSet& rhs)
376 : {
377 : _intervals.swap(rhs._intervals);
378 : }
379 : }
380 : /** @endcond */
|
