DGtal  1.5.beta
IntegralIntervals.h
1
17 #pragma once
27 #if defined(IntegralIntervals_RECURSES)
28 #error Recursive header files inclusion detected in IntegralIntervals.h
29 #else // defined(IntegralIntervals_RECURSES)
31 #define IntegralIntervals_RECURSES
32
33 #if !defined IntegralIntervals_h
35 #define IntegralIntervals_h
36
37 #include <vector>
38 #include <set>
39 #include "DGtal/base/Common.h"
40 #include "DGtal/kernel/CBoundedNumber.h"
41
42 namespace DGtal
43 {
44
46  // template class IntegralIntervals
61  template < typename TInteger >
63  {
64  public:
66
67  typedef TInteger Integer;
69  using Interval = std::pair<Integer,Integer>;
70  using Container = std::vector< Interval >;
71  using Size = std::size_t;
72  using CIterator = typename Container::iterator;
73  using IntegerRange = std::vector< Integer >;
74
76  IntegralIntervals() = default;
77
80  IntegralIntervals( const Self & other ) = default;
81
84  IntegralIntervals( Self&& other ) = default;
85
89  Self& operator=( const Self & other ) = default;
90
94  Self& operator=( Self&& other ) = default;
95
99  template <typename InputIterator>
100  IntegralIntervals( InputIterator it, InputIterator itE )
101  {
102  if ( it == itE ) return;
103  Integer first = *it;
104  Integer last = *it;
105  for ( ++it; it != itE; ++it )
106  {
107  Integer x = *it;
108  if ( first <= x && x <= last ) continue;
109  if ( x == last+1 ) { last = x; continue; }
110  if ( x == first-1 ) { first = x; continue; }
111  insert( first, last );
112  first = x;
113  last = x;
114  }
115  insert( first, last );
116  }
117
119  void clear() { myData.clear(); }
120
122  Container& data() { return myData; }
124  const Container& data() const { return myData; }
125
127  bool empty() const { return myData.empty(); }
128
130  Size size() const
131  {
132  Size nb = 0;
133  for ( const auto& I : myData ) nb += 1 + I.second - I.first;
134  return nb;
135  }
136
138  Size capacity() const
139  {
140  return myData.capacity();
141  }
142
144  bool isConvex() const
145  {
146  return myData.size() <= 1;
147  }
148
150  std::set<Integer> integerSet() const
151  {
152  std::set<Integer> S;
153  for ( const auto& I : myData )
154  for ( Integer x = I.first; x <= I.second; x++ )
155  S.insert( x );
156  return S;
157  }
159  std::vector<Integer> integerVector() const
160  {
161  std::vector<Integer> S;
162  for ( const auto& I : myData )
163  for ( Integer x = I.first; x <= I.second; x++ )
164  S.push_back( x );
165  return S;
166  }
167
170  Size count( Integer x ) const
171  {
172  if ( empty() ) return 0;
173  Size i = 0;
174  Size j = myData.size() - 1;
175  while ( i <= j )
176  {
177  const Size m = (i+j)/2;
178  const Interval& I = myData[ m ]; // I = [a,...,b]
179  if ( x < I.first ) // x < a
180  {
181  if ( m == 0 ) return 0;
182  j = m - 1;
183  }
184  else if ( I.second < x ) // b < x
185  i = m + 1;
186  else // a <= x <= b
187  return 1;
188  }
189  return 0;
190  }
191
194  void insert( Integer i )
195  {
196  insert( Interval( i, i ) );
197  }
198
201  void insert( Integer f, Integer l )
202  {
203  insert( Interval( f, l ) );
204  }
205
208  void insert( const Interval& I )
209  {
210  // Search position of first element.
211  auto it = lowerBound( I.first );
212  if ( it == myData.end() ) // if you reach the end, just add the interval
213  {
214  myData.push_back( I );
215  if ( myData.size() >= 2 ) extend( myData.end() - 2 );
216  }
217  else if ( I.first < it->first )
218  {
219  // See if interval must merge with previous
220  if ( it != myData.begin() )
221  {
222  auto it_prev = it; --it_prev;
223  if ( I.first <= it_prev->second + 1 )
224  {
225  it_prev->second = I.second;
226  extend( it_prev );
227  return;
228  }
229  }
230  Size idx = it - myData.begin();
231  // std::cout << "(Inserting " << idx << ")" << std::endl;;
232  myData.insert( it, I );
233  extend( myData.begin() + idx );
234  }
235  else // it->first <= I.first <= it->second
236  {
237  it->second = std::max( it->second, I.second );
238  extend( it );
239  }
240  }
241
244  void erase( Integer i )
245  {
246  erase( Interval( i, i ) );
247  }
250  void erase( Integer f, Integer l )
251  {
252  erase( Interval( f, l ) );
253  }
254
257  void erase( const Interval& I )
258  {
259  for ( std::size_t i = 0; i < myData.size(); )
260  {
261  Interval& J = myData[ i ];
262  // I=[a,b], J=[a',b'], a <= b, a' <= b'
263  if ( I.second < J.first )
264  { break; } // b < a' : no further intersection
265  if ( J.second < I.first )
266  { ++i; continue; } // b' < a : no further intersection
267  // a' <= b and a <= b'
268  // a ---------- b
269  // a' ............... a'
270  // b' ................. b'
271  //
272  // a' ..................... b' => a'..a-1 b+1..b'
273  Interval K1( J.first, I.first - 1 );
274  Interval K2( I.second + 1, J.second );
275  bool K1_exist = K1.second >= K1.first;
276  bool K2_exist = K2.second >= K2.first;
277  if ( K1_exist && K2_exist )
278  {
279  myData[ i ] = K2;
280  myData.insert( myData.begin() + i, K1 );
281  break; // no further intersection possible
282  }
283  else if ( K1_exist )
284  {
285  myData[ i ] = K1; i++;
286  }
287  else if ( K2_exist )
288  {
289  myData[ i ] = K2; break;
290  }
291  else
292  {
293  myData.erase( myData.begin() + i );
294  }
295  }
296  }
297
301  Self& add( const Self& other )
302  {
303  for ( const auto& I : other.myData )
304  insert( I );
305  return *this;
306  }
307
311  Self& subtract( const Self& other )
312  {
313  for ( const auto& I : other.myData )
314  erase( I );
315  return *this;
316  }
317
321  Self set_union( const Self& other ) const
322  {
323  Self U = *this;
324  U.add( other );
325  return U;
326  }
327
331  Self set_difference( const Self& other ) const
332  {
333  Self U = *this;
334  U.subtract( other );
335  return U;
336  }
337
341  Self set_intersection( const Self& other ) const
342  {
343  Self A_plus_B = set_union( other );
344  Self A_delta_B = set_symmetric_difference( other );
345  return A_plus_B.subtract( A_delta_B );
346  }
347
351  Self set_symmetric_difference( const Self& other ) const
352  {
353  Self A_minus_B = *this;
354  A_minus_B.subtract( other );
355  Self B_minus_A = other;
356  B_minus_A.subtract( *this );
357  return A_minus_B.add( B_minus_A );
358  }
359
367  {
368  Self R( *this );
369  for ( auto& I : R.myData )
370  {
371  I.first = 2*I.first-1;
372  I.second = 2*I.second+1;
373  }
374  return R;
375  }
376
382  {
383  Self R( *this );
384  for ( size_t i = 0; i < R.myData.size(); )
385  {
386  auto& I = R.myData[ i ];
387  if ( ( I.first & 0x1 ) == 0 ) I.first -= 1;
388  if ( ( I.second & 0x1 ) == 0 ) I.second += 1;
389  // We have to be careful since extending this interval may
390  // have reached the next interval.
391  // We have to merge them in this case.
392  i += 1;
393  if ( i < R.myData.size() )
394  {
395  auto& Inext = R.myData[ i ];
396  if ( Inext.first <= I.second+1 )
397  {
398  I.second = Inext.second;
399  R.myData.erase( R.myData.begin() + i );
400  i -= 1;
401  }
402  }
403  }
404  return R;
405  }
406
410  {
411  IntegerRange C;
412  for ( auto I : myData )
413  {
414  if ( ( I.first & 0x1 ) != 0 ) I.first -= 1;
415  if ( ( I.second & 0x1 ) != 0 ) I.second += 1;
416  for ( auto x = I.first; x <= I.second; x += 2 )
417  C.push_back( x >> 1 ); // here x / 2 == x >> 1 since x is even
418  }
419  auto last = std::unique( C.begin(), C.end() );
420  C.erase( last, C.end() );
421  return C;
422  }
423
426  bool includes( const Self& other ) const
427  {
428  auto it = myData.cbegin();
429  for ( const auto& I : other.myData )
430  {
431  // Find possible interval
432  while ( it != myData.cend() && it->second < I.second ) ++it;
433  if ( it == myData.cend() ) return false;
434  if ( I.first < it->first ) return false;
435  }
436  return true;
437  }
438
441  bool equals( const Self& other ) const
442  {
443  if ( myData.size() != other.myData.size() ) return false;
444  auto it = myData.cbegin();
445  for ( const auto& I : other.myData )
446  {
447  if ( it->first != I.first || it->second != I.second ) return false;
448  ++it;
449  }
450  return true;
451  }
452
453  // ----------------------- Interface --------------------------------------
454 public:
455
460  void selfDisplay ( std::ostream & out ) const
461  {
462  out << "[";
463  for ( const auto& I : myData )
464  out << " (" << I.first << "," << I.second << ")";
465  out << " ]";
466  }
467
469  bool isValid() const
470  {
471  for ( const auto& I : myData )
472  if ( I.first > I.second ) return false;
473  for ( Size i = 1; i < myData.size(); i++ )
474  {
475  if ( myData[i-1].second >= myData[i].first - 1 )
476  return false;
477  }
478  return true;
479  }
480
481  // ------------------- protected services -------------------------------
482  protected:
483
487  void extend( CIterator it )
488  {
489  // std::cout << "Extending" << std::endl;
490  CIterator it_next = it; ++it_next;
491  while ( it_next != myData.end() )
492  {
493  if ( it->second >= ( it_next->first - 1 ) )
494  {
495  it->second = std::max( it->second, it_next->second );
496  ++it_next;
497  }
498  else break;
499  }
500  ++it;
501  // std::cout << "Erase from " << ( it - myData.begin() )
502  // << " to " << ( it_next - myData.begin() ) << std::endl;
503  myData.erase( it, it_next );
504  }
505
512  {
513  // std::cout << "(lowerbound for " << x << ")" << std::endl;
514  if ( empty() ) return myData.end();
515  Size i = 0;
516  Size j = myData.size() - 1;
517  while ( i <= j )
518  {
519  const Size m = (i+j)/2;
520  const Interval& I = myData[ m ]; // I = [a,...,b]
521  if ( x < I.first ) // x < a
522  {
523  if ( m == 0 ) break;
524  j = m - 1;
525  }
526  else if ( I.second < x ) // b < x
527  i = m + 1;
528  else // a <= x <= b
529  return myData.begin() + m;
530  }
531  // std::cout << "(not found, return " << i << ")" << std::endl;
532  return myData.begin() + i;
533  }
534
535  // ------------------- protected data -------------------------------
536  protected:
537
540  };
541
548  template <typename TInteger>
549  std::ostream&
550  operator<< ( std::ostream & out, const IntegralIntervals<TInteger> & object )
551  {
552  object.selfDisplay( out );
553  return out;
554  }
555
556 } // namespace DGtal
557
558
560 // Includes inline functions.
561
562 // //
564
565 #endif // !defined IntegralIntervals_h
566
567 #undef IntegralIntervals_RECURSES
568 #endif // else defined(IntegralIntervals_RECURSES)
BOOST_CONCEPT_ASSERT((concepts::CBoundedNumber< TInteger >))
IntegerRange extremaOfCells() const
Self set_intersection(const Self &other) const
Self & operator=(Self &&other)=default
void erase(Integer f, Integer l)
void insert(const Interval &I)
void extend(CIterator it)
bool includes(const Self &other) const
std::set< Integer > integerSet() const
CIterator lowerBound(Integer x)
std::pair< Integer, Integer > Interval
IntegralIntervals()=default
Default Constructor.
Self set_symmetric_difference(const Self &other) const
Self & operator=(const Self &other)=default
std::vector< Integer > integerVector() const
void erase(const Interval &I)
Self & add(const Self &other)
IntegralIntervals(const Self &other)=default
void clear()
Clears the data structure.
bool equals(const Self &other) const
typename Container::iterator CIterator
std::vector< Interval > Container
void selfDisplay(std::ostream &out) const
IntegralIntervals(Self &&other)=default
Container myData
The sorted sequence of integral intervals.
const Container & data() const
Self & subtract(const Self &other)
void insert(Integer f, Integer l)
Size count(Integer x) const
IntegralIntervals(InputIterator it, InputIterator itE)
Self set_union(const Self &other) const
std::vector< Integer > IntegerRange
Self set_difference(const Self &other) const
DGtal is the top-level namespace which contains all DGtal functions and types.
std::ostream & operator<<(std::ostream &out, const ATu0v1< TKSpace, TLinearAlgebra > &object)
Aim: The concept CBoundedNumber specifies what are the bounded numbers. Models of this concept should...
int max(int a, int b)