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