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, IntervalComparator > | IntervalSet |
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 ClosedInterval & | last () 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
typedef std::set<ClosedInterval, IntervalComparator> 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]
|
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()
|
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()
|
inline |
Definition at line 491 of file sorted_interval_list.h.
◆ DebugString()
std::string DebugString | ( | ) | const |
◆ end()
|
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()
|
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()
|
inline |
Returns the number of disjoint intervals in the list.
Definition at line 458 of file sorted_interval_list.h.
◆ swap()
|
inline |
Definition at line 492 of file sorted_interval_list.h.
The documentation for this class was generated from the following file: