DGtal 1.3.0
Searching...
No Matches
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
42namespace 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
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;
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 );
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 ( auto 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 --------------------------------------
454public:
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
void erase(Integer f, Integer l)
void insert(const Interval &I)
void extend(CIterator it)
std::set< Integer > integerSet() const
std::vector< Integer > integerVector() const
bool includes(const Self &other) const
CIterator lowerBound(Integer x)
Self & operator=(const Self &other)=default
std::pair< Integer, Integer > Interval
IntegralIntervals()=default
Default Constructor.
Self set_symmetric_difference(const Self &other) const
void erase(const Interval &I)
Self & subtract(const Self &other)
IntegralIntervals(const Self &other)=default
void clear()
Clears the data structure.
Self & operator=(Self &&other)=default
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
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 ClosedIntegerHalfPlane< TSpace > &object)
Aim: The concept CBoundedNumber specifies what are the bounded numbers. Models of this concept should...