C++ Reference

C++ Reference: CP-SAT

Detailed Description

This class represents a sorted list of disjoint, closed intervals.

When an interval is inserted, all intervals that overlap it or are adjacent to it are merged into one. I.e. [0,14] and [15,30] will be merged to [0,30].

Iterators returned by this class are invalidated by non-const operations.

Definition at line 390 of file sorted_interval_list.h.

Classes

struct  IntervalComparator
 

Public Types

typedef std::set< ClosedInterval, IntervalComparatorIntervalSet
 
typedef IntervalSet::iterator Iterator
 
typedef IntervalSet::const_iterator ConstIterator
 

Public Member Functions

 SortedDisjointIntervalList ()
 
 SortedDisjointIntervalList (const std::vector< ClosedInterval > &intervals)
 
 SortedDisjointIntervalList (const std::vector< int64 > &starts, const std::vector< int64 > &ends)
 Creates a SortedDisjointIntervalList and fills it with intervals [starts[i]..ends[i]]. More...
 
 SortedDisjointIntervalList (const std::vector< int > &starts, const std::vector< int > &ends)
 
SortedDisjointIntervalList BuildComplementOnInterval (int64 start, int64 end)
 Builds the complement of the interval list on the interval [start, end]. More...
 
Iterator InsertInterval (int64 start, int64 end)
 Adds the interval [start..end] to the list, and merges overlapping or immediately adjacent intervals ([2, 5] and [6, 7] are adjacent, but [2, 5] and [7, 8] are not). More...
 
Iterator GrowRightByOne (int64 value, int64 *newly_covered)
 If value is in an interval, increase its end by one, otherwise insert the interval [value, value]. More...
 
void InsertIntervals (const std::vector< int64 > &starts, const std::vector< int64 > &ends)
 Adds all intervals [starts[i]..ends[i]]. More...
 
void InsertIntervals (const std::vector< int > &starts, const std::vector< int > &ends)
 
int NumIntervals () const
 Returns the number of disjoint intervals in the list. More...
 
Iterator FirstIntervalGreaterOrEqual (int64 value) const
 Returns an iterator to either: More...
 
Iterator LastIntervalLessOrEqual (int64 value) const
 
std::string DebugString () const
 
ConstIterator begin () const
 Const iterators for SortedDisjoinIntervalList. More...
 
ConstIterator end () const
 
const ClosedIntervallast () const
 Returns a const& to the last interval. More...
 
void clear ()
 
void swap (SortedDisjointIntervalList &other)
 

Member Typedef Documentation

◆ ConstIterator

typedef IntervalSet::const_iterator ConstIterator

Definition at line 399 of file sorted_interval_list.h.

◆ IntervalSet

Definition at line 397 of file sorted_interval_list.h.

◆ Iterator

typedef IntervalSet::iterator Iterator

Definition at line 398 of file sorted_interval_list.h.

Constructor & Destructor Documentation

◆ SortedDisjointIntervalList() [1/4]

◆ SortedDisjointIntervalList() [2/4]

SortedDisjointIntervalList ( const std::vector< ClosedInterval > &  intervals)
explicit

◆ SortedDisjointIntervalList() [3/4]

SortedDisjointIntervalList ( const std::vector< int64 > &  starts,
const std::vector< int64 > &  ends 
)

Creates a SortedDisjointIntervalList and fills it with intervals [starts[i]..ends[i]].

All intervals must be consistent (starts[i] <= ends[i]). There are two version, one for int64 and one for int.

◆ SortedDisjointIntervalList() [4/4]

SortedDisjointIntervalList ( const std::vector< int > &  starts,
const std::vector< int > &  ends 
)

Member Function Documentation

◆ begin()

ConstIterator begin ( ) const
inline

Const iterators for SortedDisjoinIntervalList.

One example usage is to use range loops in C++: SortedDisjointIntervalList list; ... for (const ClosedInterval& interval : list) { ... }

Definition at line 483 of file sorted_interval_list.h.

◆ BuildComplementOnInterval()

SortedDisjointIntervalList BuildComplementOnInterval ( int64  start,
int64  end 
)

Builds the complement of the interval list on the interval [start, end].

◆ clear()

void clear ( )
inline

Definition at line 491 of file sorted_interval_list.h.

◆ DebugString()

std::string DebugString ( ) const

◆ end()

ConstIterator end ( ) const
inline

Definition at line 484 of file sorted_interval_list.h.

◆ FirstIntervalGreaterOrEqual()

Iterator FirstIntervalGreaterOrEqual ( int64  value) const

Returns an iterator to either:

  • the first interval containing or above the given value, or
  • the last interval containing or below the given value. Returns end() if no interval fulfills that condition.

If the value is within an interval, both functions will return it.

◆ GrowRightByOne()

Iterator GrowRightByOne ( int64  value,
int64 *  newly_covered 
)

If value is in an interval, increase its end by one, otherwise insert the interval [value, value].

In both cases, this returns an iterator to the new/modified interval (possibly merged with others) and fills newly_covered with the new value that was just added in the union of all the intervals.

If this causes an interval ending at kint64max to grow, it will die with a CHECK fail.

◆ InsertInterval()

Iterator InsertInterval ( int64  start,
int64  end 
)

Adds the interval [start..end] to the list, and merges overlapping or immediately adjacent intervals ([2, 5] and [6, 7] are adjacent, but [2, 5] and [7, 8] are not).

Returns an iterator to the inserted interval (possibly merged with others).

If start > end, it does LOG(DFATAL) and returns end() (no interval added).

◆ InsertIntervals() [1/2]

void InsertIntervals ( const std::vector< int > &  starts,
const std::vector< int > &  ends 
)

◆ InsertIntervals() [2/2]

void InsertIntervals ( const std::vector< int64 > &  starts,
const std::vector< int64 > &  ends 
)

Adds all intervals [starts[i]..ends[i]].

Same behavior as InsertInterval() upon invalid intervals. There's a version with int64 and int32.

◆ last()

const ClosedInterval& last ( ) const
inline

Returns a const& to the last interval.

The list must not be empty.

Definition at line 489 of file sorted_interval_list.h.

◆ LastIntervalLessOrEqual()

Iterator LastIntervalLessOrEqual ( int64  value) const

◆ NumIntervals()

int NumIntervals ( ) const
inline

Returns the number of disjoint intervals in the list.

Definition at line 458 of file sorted_interval_list.h.

◆ swap()

void swap ( SortedDisjointIntervalList other)
inline

Definition at line 492 of file sorted_interval_list.h.


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