File failed to load: https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.3/config/TeX-MML-AM_CHTML/MathJax.js
DGtal 2.0.0
DGtal::IntegralIntervals< TInteger > Class Template Reference

Aim: More...

#include <DGtal/kernel/IntegralIntervals.h>

Inheritance diagram for DGtal::IntegralIntervals< TInteger >:
[legend]

Public Types

typedef TInteger Integer
using Self = IntegralIntervals< Integer >
using Interval = std::pair<Integer,Integer>
using Container = std::vector< Interval >
using Size = std::size_t
using CIterator = typename Container::iterator
using IntegerRange = std::vector< Integer >

Public Member Functions

 BOOST_CONCEPT_ASSERT ((concepts::CBoundedNumber< TInteger >))
 IntegralIntervals ()=default
 Default Constructor.
 IntegralIntervals (const Self &other)=default
 IntegralIntervals (Self &&other)=default
Selfoperator= (const Self &other)=default
Selfoperator= (Self &&other)=default
template<typename InputIterator>
 IntegralIntervals (InputIterator it, InputIterator itE)
void clear ()
 Clears the data structure.
Containerdata ()
const Containerdata () const
bool empty () const
Size size () const
Size capacity () const
bool isConvex () const
std::set< IntegerintegerSet () const
std::vector< IntegerintegerVector () const
Size count (Integer x) const
void insert (Integer i)
void insert (Integer f, Integer l)
void insert (const Interval &I)
void erase (Integer i)
void erase (Integer f, Integer l)
void erase (const Interval &I)
Selfadd (const Self &other)
Selfsubtract (const Self &other)
Self set_union (const Self &other) const
Self set_difference (const Self &other) const
Self set_intersection (const Self &other) const
Self set_symmetric_difference (const Self &other) const
Self starOfPoints () const
Self starOfCells () const
IntegerRange extremaOfCells () const
bool includes (const Self &other) const
bool equals (const Self &other) const
void selfDisplay (std::ostream &out) const
bool isValid () const

Protected Member Functions

void extend (CIterator it)
CIterator lowerBound (Integer x)

Protected Attributes

Container myData
 The sorted sequence of integral intervals.

Detailed Description

template<typename TInteger>
class DGtal::IntegralIntervals< TInteger >

Aim:

Description of template class 'IntegralIntervals'

A class that represents a set of integers using intervals. For instance the set X={-3,-2,0,1,2,4,7,8} is represented as the sorted vector ((-3,-2),(0,2),(4,4),(7,8)).

Inserting -1 into X induced the sorted vector ((-3,2),(4,4),(7,8)).

Template Parameters
TIntegerany model of concepts::CBoundedNumber, for instance int, long, etc
Note
Useful to represent points of (especially convex) lattice polytopes or points of digital sets.

Definition at line 62 of file IntegralIntervals.h.

Member Typedef Documentation

◆ CIterator

template<typename TInteger>
using DGtal::IntegralIntervals< TInteger >::CIterator = typename Container::iterator

Definition at line 72 of file IntegralIntervals.h.

◆ Container

template<typename TInteger>
using DGtal::IntegralIntervals< TInteger >::Container = std::vector< Interval >

Definition at line 70 of file IntegralIntervals.h.

◆ Integer

template<typename TInteger>
typedef TInteger DGtal::IntegralIntervals< TInteger >::Integer

Definition at line 67 of file IntegralIntervals.h.

◆ IntegerRange

template<typename TInteger>
using DGtal::IntegralIntervals< TInteger >::IntegerRange = std::vector< Integer >

Definition at line 73 of file IntegralIntervals.h.

◆ Interval

template<typename TInteger>
using DGtal::IntegralIntervals< TInteger >::Interval = std::pair<Integer,Integer>

Definition at line 69 of file IntegralIntervals.h.

◆ Self

template<typename TInteger>
using DGtal::IntegralIntervals< TInteger >::Self = IntegralIntervals< Integer >

Definition at line 68 of file IntegralIntervals.h.

◆ Size

template<typename TInteger>
using DGtal::IntegralIntervals< TInteger >::Size = std::size_t

Definition at line 71 of file IntegralIntervals.h.

Constructor & Destructor Documentation

◆ IntegralIntervals() [1/4]

template<typename TInteger>
DGtal::IntegralIntervals< TInteger >::IntegralIntervals ( )
default

Default Constructor.

◆ IntegralIntervals() [2/4]

template<typename TInteger>
DGtal::IntegralIntervals< TInteger >::IntegralIntervals ( const Self & other)
default

Copy constructor

Parameters
otherany other object.

◆ IntegralIntervals() [3/4]

template<typename TInteger>
DGtal::IntegralIntervals< TInteger >::IntegralIntervals ( Self && other)
default

Move constructor

Parameters
otherany other object.

◆ IntegralIntervals() [4/4]

template<typename TInteger>
template<typename InputIterator>
DGtal::IntegralIntervals< TInteger >::IntegralIntervals ( InputIterator it,
InputIterator itE )
inline

Constructor from range

Template Parameters
InputIteratorthe type of forward iterator on a range of integer values.
Parameters
it,itEthe range of integer values.

Definition at line 100 of file IntegralIntervals.h.

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 }

Member Function Documentation

◆ add()

template<typename TInteger>
Self & DGtal::IntegralIntervals< TInteger >::add ( const Self & other)
inline

Performs the union of set other with this object.

Parameters
otherany intervals
Returns
a reference to this object

Definition at line 301 of file IntegralIntervals.h.

302 {
303 for ( const auto& I : other.myData )
304 insert( I );
305 return *this;
306 }
Container myData
The sorted sequence of integral intervals.

Referenced by DGtal::IntegralIntervals< Integer >::set_symmetric_difference(), and DGtal::IntegralIntervals< Integer >::set_union().

◆ BOOST_CONCEPT_ASSERT()

template<typename TInteger>
DGtal::IntegralIntervals< TInteger >::BOOST_CONCEPT_ASSERT ( (concepts::CBoundedNumber< TInteger >) )

◆ capacity()

template<typename TInteger>
Size DGtal::IntegralIntervals< TInteger >::capacity ( ) const
inline
Returns
the current allocated space in the object container.

Definition at line 138 of file IntegralIntervals.h.

139 {
140 return myData.capacity();
141 }

◆ clear()

template<typename TInteger>
void DGtal::IntegralIntervals< TInteger >::clear ( )
inline

Clears the data structure.

Definition at line 119 of file IntegralIntervals.h.

119{ myData.clear(); }

◆ count()

template<typename TInteger>
Size DGtal::IntegralIntervals< TInteger >::count ( Integer x) const
inline
Parameters
xany integer
Returns
the number of times the element x is in the set (either 0 or 1).

Definition at line 170 of file IntegralIntervals.h.

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 }
std::pair< Integer, Integer > Interval

◆ data() [1/2]

template<typename TInteger>
Container & DGtal::IntegralIntervals< TInteger >::data ( )
inline
Returns
a reference to the current data

Definition at line 122 of file IntegralIntervals.h.

122{ return myData; }

Referenced by DGtal::LatticeSetByIntervals< Space >::skeletonOfCells().

◆ data() [2/2]

template<typename TInteger>
const Container & DGtal::IntegralIntervals< TInteger >::data ( ) const
inline
Returns
a const reference to the current data

Definition at line 124 of file IntegralIntervals.h.

124{ return myData; }

◆ empty()

template<typename TInteger>
bool DGtal::IntegralIntervals< TInteger >::empty ( ) const
inline
Returns
'true' if the set contains no element

Definition at line 127 of file IntegralIntervals.h.

127{ return myData.empty(); }

Referenced by DGtal::IntegralIntervals< Integer >::count(), and DGtal::IntegralIntervals< Integer >::lowerBound().

◆ equals()

template<typename TInteger>
bool DGtal::IntegralIntervals< TInteger >::equals ( const Self & other) const
inline
Parameters
otherany other integral set represented by intervals
Returns
'true' iff this integer set equals the integer set other.

Definition at line 441 of file IntegralIntervals.h.

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 }

◆ erase() [1/3]

template<typename TInteger>
void DGtal::IntegralIntervals< TInteger >::erase ( const Interval & I)
inline

Erases the interval of integers from the sequence

Parameters
Iany valid interval (I.first <= I.second)

Definition at line 257 of file IntegralIntervals.h.

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 }

◆ erase() [2/3]

template<typename TInteger>
void DGtal::IntegralIntervals< TInteger >::erase ( Integer f,
Integer l )
inline

Erases the interval of integers from the sequence

Parameters
f,lany valid interval (f <= l)

Definition at line 250 of file IntegralIntervals.h.

251 {
252 erase( Interval( f, l ) );
253 }

◆ erase() [3/3]

template<typename TInteger>
void DGtal::IntegralIntervals< TInteger >::erase ( Integer i)
inline

Erases the integer i from the sequence

Parameters
iany integer

Definition at line 244 of file IntegralIntervals.h.

245 {
246 erase( Interval( i, i ) );
247 }

Referenced by DGtal::IntegralIntervals< Integer >::erase(), DGtal::IntegralIntervals< Integer >::erase(), and DGtal::IntegralIntervals< Integer >::subtract().

◆ extend()

template<typename TInteger>
void DGtal::IntegralIntervals< TInteger >::extend ( CIterator it)
inlineprotected

At the given iterator position the current interval may overlap with the following ones. Merge them.

Parameters
itany position

Definition at line 487 of file IntegralIntervals.h.

488 {
489 // std::cout << "Extending" << std::endl;
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 }
typename Container::iterator CIterator

Referenced by DGtal::IntegralIntervals< Integer >::insert().

◆ extremaOfCells()

template<typename TInteger>
IntegerRange DGtal::IntegralIntervals< TInteger >::extremaOfCells ( ) const
inline
Returns
the range of points that contains the vertices of all the cells stored in this set. It is thus a range of integers.

Definition at line 409 of file IntegralIntervals.h.

410 {
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 }
std::vector< Integer > IntegerRange

◆ includes()

template<typename TInteger>
bool DGtal::IntegralIntervals< TInteger >::includes ( const Self & other) const
inline
Parameters
otherany other integral set represented by intervals
Returns
'true' iff this integer set includes the integer set other.

Definition at line 426 of file IntegralIntervals.h.

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 }

◆ insert() [1/3]

template<typename TInteger>
void DGtal::IntegralIntervals< TInteger >::insert ( const Interval & I)
inline

Inserts the interval of integers into the sequence

Parameters
Iany valid interval (I.first <= I.second)

Definition at line 208 of file IntegralIntervals.h.

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 }
CIterator lowerBound(Integer x)

◆ insert() [2/3]

template<typename TInteger>
void DGtal::IntegralIntervals< TInteger >::insert ( Integer f,
Integer l )
inline

Inserts the interval of integers into the sequence

Parameters
f,lany valid interval (f <= l)

Definition at line 201 of file IntegralIntervals.h.

202 {
203 insert( Interval( f, l ) );
204 }

◆ insert() [3/3]

template<typename TInteger>
void DGtal::IntegralIntervals< TInteger >::insert ( Integer i)
inline

◆ integerSet()

template<typename TInteger>
std::set< Integer > DGtal::IntegralIntervals< TInteger >::integerSet ( ) const
inline
Returns
the set of integers

Definition at line 150 of file IntegralIntervals.h.

151 {
153 for ( const auto& I : myData )
154 for ( Integer x = I.first; x <= I.second; x++ )
155 S.insert( x );
156 return S;
157 }

◆ integerVector()

template<typename TInteger>
std::vector< Integer > DGtal::IntegralIntervals< TInteger >::integerVector ( ) const
inline
Returns
the set of integers as a vector

Definition at line 159 of file IntegralIntervals.h.

160 {
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 }

◆ isConvex()

template<typename TInteger>
bool DGtal::IntegralIntervals< TInteger >::isConvex ( ) const
inline
Returns
'true' if the set of integers is convex, i.e. empty or one interval.

Definition at line 144 of file IntegralIntervals.h.

145 {
146 return myData.size() <= 1;
147 }

◆ isValid()

template<typename TInteger>
bool DGtal::IntegralIntervals< TInteger >::isValid ( ) const
inline
Returns
'true' iff the intervals are consistent and sorted.

Definition at line 469 of file IntegralIntervals.h.

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 }

◆ lowerBound()

template<typename TInteger>
CIterator DGtal::IntegralIntervals< TInteger >::lowerBound ( Integer x)
inlineprotected
Parameters
xany integer
Returns
the iterator on the interval which is not before x, i.e. the interval containing x or, if it does not exist, the interval after.

Definition at line 511 of file IntegralIntervals.h.

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 }

Referenced by DGtal::IntegralIntervals< Integer >::insert().

◆ operator=() [1/2]

template<typename TInteger>
Self & DGtal::IntegralIntervals< TInteger >::operator= ( const Self & other)
default

Assignment

Parameters
otherany other object.
Returns
a reference to this object.

◆ operator=() [2/2]

template<typename TInteger>
Self & DGtal::IntegralIntervals< TInteger >::operator= ( Self && other)
default

Move assignment

Parameters
otherany other object.
Returns
a reference to this object.

◆ selfDisplay()

template<typename TInteger>
void DGtal::IntegralIntervals< TInteger >::selfDisplay ( std::ostream & out) const
inline

Writes/Displays the object on an output stream.

Parameters
outthe output stream where the object is written.

Definition at line 460 of file IntegralIntervals.h.

461 {
462 out << "[";
463 for ( const auto& I : myData )
464 out << " (" << I.first << "," << I.second << ")";
465 out << " ]";
466 }

◆ set_difference()

template<typename TInteger>
Self DGtal::IntegralIntervals< TInteger >::set_difference ( const Self & other) const
inline

Performs the set difference between this and other.

Parameters
otherany other integral set represented by intervals
Returns
the set difference between this and other.

Definition at line 331 of file IntegralIntervals.h.

332 {
333 Self U = *this;
334 U.subtract( other );
335 return U;
336 }
IntegralIntervals< Integer > Self
Self & subtract(const Self &other)

◆ set_intersection()

template<typename TInteger>
Self DGtal::IntegralIntervals< TInteger >::set_intersection ( const Self & other) const
inline

Performs the set intersection between this and other.

Parameters
otherany other integral set represented by intervals
Returns
the set difference between this and other.

Definition at line 341 of file IntegralIntervals.h.

342 {
345 return A_plus_B.subtract( A_delta_B );
346 }
Self set_symmetric_difference(const Self &other) const
Self set_union(const Self &other) const

◆ set_symmetric_difference()

template<typename TInteger>
Self DGtal::IntegralIntervals< TInteger >::set_symmetric_difference ( const Self & other) const
inline

Performs the set symmetric difference between this and other.

Parameters
otherany other integral set represented by intervals
Returns
the set symmetric difference between this and other.

Definition at line 351 of file IntegralIntervals.h.

352 {
353 Self A_minus_B = *this;
356 B_minus_A.subtract( *this );
357 return A_minus_B.add( B_minus_A );
358 }
Self & add(const Self &other)

Referenced by DGtal::IntegralIntervals< Integer >::set_intersection().

◆ set_union()

template<typename TInteger>
Self DGtal::IntegralIntervals< TInteger >::set_union ( const Self & other) const
inline

Performs the set union between this and other.

Parameters
otherany other integral set represented by intervals
Returns
the set union between this and other.

Definition at line 321 of file IntegralIntervals.h.

322 {
323 Self U = *this;
324 U.add( other );
325 return U;
326 }

Referenced by DGtal::IntegralIntervals< Integer >::set_intersection().

◆ size()

template<typename TInteger>
Size DGtal::IntegralIntervals< TInteger >::size ( ) const
inline
Returns
the number of integers of the set.

Definition at line 130 of file IntegralIntervals.h.

131 {
132 Size nb = 0;
133 for ( const auto& I : myData ) nb += 1 + I.second - I.first;
134 return nb;
135 }

◆ starOfCells()

template<typename TInteger>
Self DGtal::IntegralIntervals< TInteger >::starOfCells ( ) const
inline

Consider the set of integers as cells represented by their Khalimsky coordinates, and build their star.

Returns
the star of these cells.

Definition at line 381 of file IntegralIntervals.h.

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 }

◆ starOfPoints()

template<typename TInteger>
Self DGtal::IntegralIntervals< TInteger >::starOfPoints ( ) const
inline

Consider the set of integers as points, transform them into pointels inn Khalimsky coordinates and build their star. All integers are multiplied by two. All doubled integers are completed with their immediately inferior and superior value.

Returns
the star of these points.

Definition at line 366 of file IntegralIntervals.h.

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 }

◆ subtract()

template<typename TInteger>
Self & DGtal::IntegralIntervals< TInteger >::subtract ( const Self & other)
inline

Subtract set other from this object.

Parameters
otherany intervals
Returns
a reference to this object

Definition at line 311 of file IntegralIntervals.h.

312 {
313 for ( const auto& I : other.myData )
314 erase( I );
315 return *this;
316 }

Referenced by DGtal::IntegralIntervals< Integer >::set_difference(), DGtal::IntegralIntervals< Integer >::set_intersection(), and DGtal::IntegralIntervals< Integer >::set_symmetric_difference().

Field Documentation

◆ myData

template<typename TInteger>
Container DGtal::IntegralIntervals< TInteger >::myData
protected

The documentation for this class was generated from the following file: