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