Lunchbox  1.15.0
Multi-threaded C++ toolbox library for all application developers creating high-performance multi-threaded programs.
intervalSet.ipp
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 
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  const_iterator( const IntervalSet& set, const edge_iterator& interval )
45  : _intervalIteratorEnd( set._intervals.end( ))
46  , _startEdge( interval )
47  {
48  if (_startEdge != _intervalIteratorEnd )
49  _value = _startEdge->first;
50  }
51 
52  const_iterator( const IntervalSet & set, const edge_iterator & interval,
53  const T& current )
54  : _value( current )
55  , _intervalIteratorEnd( set._intervals.end( ))
56  , _startEdge( interval )
57  {}
58 
59  void increment()
60  {
61  if( _startEdge == _intervalIteratorEnd )
62  return;
63 
64  edge_iterator endEdge = _startEdge;
65  ++endEdge;
66  // Next element is inside the current interval.
67  if( _value >= _startEdge->first && _value < endEdge->first )
68  ++_value;
69  else
70  {
71  ++_startEdge;
72  ++_startEdge;
73  if( _startEdge != _intervalIteratorEnd )
74  _value = _startEdge->first;
75  }
76  }
77 
78  bool equal( const const_iterator& rhs ) const
79  {
80  return (_startEdge == _intervalIteratorEnd &&
81  rhs._startEdge == _intervalIteratorEnd) ||
82  (_startEdge == rhs._startEdge && _value == rhs._value );
83  }
84 
85  T dereference() const
86  {
87  return _value;
88  }
89 
90  T _value;
91  edge_iterator _intervalIteratorEnd;
92  edge_iterator _startEdge;
93 };
94 
95 template < typename T > IntervalSet< T >::IntervalSet()
96  : _size( 0 )
97 {}
98 
99 template < typename T > void IntervalSet< T >::insert( const T& element )
100 {
101  insert( element, element );
102 }
103 
104 template < typename T > void IntervalSet< T >::erase( const T& element )
105 {
106  erase( element, element );
107 }
108 
109 template < typename T > void IntervalSet< T >::insert( const T& startElement,
110  const T& endElement )
111 {
112  LBASSERT( startElement <= endElement );
113 
114  Edge startValue( startElement, true );
115  Edge endValue( endElement, false );
116 
117  if( _intervals.empty( ))
118  {
119  _intervals.insert( startValue );
120  _intervals.insert( endValue );
121  _size = endElement - startElement + 1;
122  return;
123  }
124 
125  // Finding the first edge whose value is less or equal than startElement.
126  typename EdgeSet::iterator previous_to_start =
127  _intervals.lower_bound( startValue );
128  if( previous_to_start != _intervals.end( ))
129  {
130  if( previous_to_start == _intervals.begin( ))
131  {
132  if( startValue.first < previous_to_start->first )
133  previous_to_start = _intervals.end();
134  }
135  else
136  previous_to_start--;
137  }
138  else
139  previous_to_start = (++_intervals.rbegin()).base();
140 
141  // Adding start edge as needed.
142  typename EdgeSet::iterator position;
143  bool fallsInside;
144  size_t overlappingPortion = 0;
145  T overlappingStart = T(); // initialized to silent a warning.
146 
147  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  position = _intervals.insert( startValue );
153  fallsInside = false;
154  }
155  else if( !previous_to_start->second )
156  {
157  // Previous element is the end of one interval.
158  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  position = previous_to_start;
163  position--;
164  _intervals.erase( previous_to_start );
165  }
166  else
167  // We have to insert start.
168  position = _intervals.insert( previous_to_start, startValue );
169  fallsInside = false;
170  }
171  else
172  {
173  // Start has fallen inside another interval we don't have to insert it.
174  position = previous_to_start;
175  fallsInside = true;
176  overlappingStart = startElement;
177  }
178 
179  // Now we have to check where the end goes.
180  ++position;
181  while( position != _intervals.end() && position->first <= endElement )
182  {
183  // Calculating the length of a possible interval overlapping the
184  // interval being inserted.
185  if( fallsInside )
186  {
187  // Previous position was the start of an overlapping interval.
188  LBASSERT( !position->second );
189  overlappingPortion += position->first - overlappingStart + 1;
190  }
191  else
192  overlappingStart = position->first;
193 
194  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  _intervals.erase( position++ );
200  }
201 
202  if( position != _intervals.end() &&
203  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  _intervals.erase(position);
209  }
210  else if( !fallsInside )
211  {
212  // End edge is not inside a previously existing interval so we
213  // have to add it.
214  _intervals.insert(position, endValue);
215  }
216  else
217  overlappingPortion += endElement - overlappingStart + 1;
218 
219  _size += size_t(endElement - startElement + 1) - overlappingPortion;
220  LBASSERT( _intervals.size() % 2 == 0 );
221 }
222 
223 template < typename T > void IntervalSet< T >::erase( const T& startElement,
224  const T& endElement )
225 {
226  LBASSERT( startElement <= endElement );
227 
228  if( _intervals.empty( ))
229  return;
230 
231  // Finding the first edge whose value is less or equal than startElement.
232  typename EdgeSet::iterator nextToStart =
233  _intervals.lower_bound( std::make_pair( startElement, true ));
234  typename EdgeSet::iterator previousToStart = nextToStart;
235  if( nextToStart == _intervals.begin( ))
236  previousToStart = _intervals.end();
237  else if( nextToStart == _intervals.end( ))
238  // Nothing to remove here
239  return;
240  else
241  --previousToStart;
242 
243  typename EdgeSet::iterator position;
244  bool inside;
245  T overlappingStart = 0;
246  size_t overlapping_portion = 0;
247 
248  if( previousToStart != _intervals.end( ))
249  {
250  // startElement is greater or equal than some interval edge.
251  if( previousToStart->second )
252  {
253  // Inserting the new end of the interval starting at
254  // previous_to_start.
255  position =
256  _intervals.insert( std::make_pair( startElement - 1, false ));
257  inside = true;
258  overlappingStart = startElement;
259  }
260  else
261  {
262  position = previousToStart;
263  inside = false;
264  }
265  ++position;
266  }
267  else
268  {
269  // startElement is less than the start of any interval.
270  inside = false;
271  position = _intervals.begin();
272  overlappingStart = position->first;
273  }
274  // Position has the next edge after the last interval before the removal
275  // interval.
276 
277  while( position != _intervals.end() && position->first <= endElement )
278  {
279  if (inside)
280  overlapping_portion += position->first - overlappingStart + 1;
281  else
282  overlappingStart = position->first;
283 
284  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  _intervals.erase( position++ );
290  }
291 
292  if( inside )
293  {
294  LBASSERT( position != _intervals.end( ));
295  // End edge is not inside a previously existing interval so we
296  // have to add it.
297  _intervals.insert (std::make_pair( endElement + 1, true ));
298  overlapping_portion += endElement - overlappingStart + 1;
299  }
300 
301  _size -= overlapping_portion;
302  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 template < typename T > void IntervalSet< T >::clear()
315 {
316  _intervals.clear();
317  _size = 0;
318 }
319 
320 template < typename T > bool IntervalSet< T >::exists( const T& element ) const
321 {
322  return find( element ) != end();
323 }
324 
325 template < typename T > typename IntervalSet< T >::const_iterator
326 IntervalSet< T >::find( const T& element ) const
327 {
328  if( _intervals.empty( ))
329  return end();
330 
331  typename EdgeSet::const_iterator next =
332  _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  if( next == _intervals.end() || next == _intervals.begin( ))
337  // x cannot be inside any interval.
338  return end();
339 
340  typename EdgeSet::const_iterator previous = next;
341  --previous;
342  if( previous->second )
343  return const_iterator( *this, previous, element );
344  return end();
345 }
346 
347 template < typename T > typename IntervalSet< T >::const_iterator
349 {
350  if( _intervals.empty( ))
351  return end();
352  return const_iterator( *this, _intervals.begin( ));
353 }
354 
355 template < typename T > typename IntervalSet< T >::const_iterator
356 IntervalSet< T >::end() const
357 {
358  return const_iterator( *this, _intervals.end());
359 }
360 
361 template < typename T > size_t IntervalSet< T >::size() const
362 {
363  return _size;
364 }
365 
366 template < typename T > bool IntervalSet< T >::empty() const
367 {
368  return size() == 0;
369 }
370 
371 template < typename T > void IntervalSet< T >::swap( IntervalSet& rhs )
372 {
373  _intervals.swap( rhs._intervals );
374 }
375 
376 }
const_iterator find(const T &element) const
bool exists(const T &element) const
IntervalSet()
Construct a new interval set.
void erase(const T &element)
Remove the given element.
void swap(IntervalSet &rhs)
Swap this container with another one.
bool empty() const
void insert(const T &element)
Insert a new element.
const_iterator begin() const
Abstraction layer and common utilities for multi-threaded programming.
Definition: algorithm.h:32
const_iterator end() const
size_t size() const
void clear()
Remove all stored elements.