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 387 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 396 of file sorted_interval_list.h.
◆ IntervalSet
| typedef std::set<ClosedInterval, IntervalComparator> IntervalSet |
Definition at line 394 of file sorted_interval_list.h.
◆ Iterator
| typedef IntervalSet::iterator Iterator |
Definition at line 395 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 480 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 488 of file sorted_interval_list.h.
◆ DebugString()
| std::string DebugString | ( | ) | const |
◆ end()
|
inline |
Definition at line 481 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 486 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 455 of file sorted_interval_list.h.
◆ swap()
|
inline |
Definition at line 489 of file sorted_interval_list.h.
The documentation for this class was generated from the following file: