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