C++ Reference
C++ Reference: CP-SAT
sorted_interval_list.h
Go to the documentation of this file.
We call domain any subset of Int64 = [kint64min, kint64max].
Definition: sorted_interval_list.h:81
std::string ToString() const
Returns a compact string of a vector of intervals like "[1,4][6][10,20]".
bool IsIncludedIn(const Domain &domain) const
Returns true iff D is included in the given domain.
Domain(int64 left, int64 right)
Constructor for the common case of a single interval [left, right].
Domain MultiplicationBy(int64 coeff, bool *exact=nullptr) const
Returns {x ∈ Int64, ∃ e ∈ D, x = e * coeff}.
int NumIntervals() const
Basic read-only std::vector<> wrapping to view a Domain as a sorted list of non-adjacent intervals.
Definition: sorted_interval_list.h:339
Domain InverseMultiplicationBy(const int64 coeff) const
Returns {x ∈ Int64, ∃ e ∈ D, x * coeff = e}.
Domain ContinuousMultiplicationBy(const Domain &domain) const
Returns a superset of MultiplicationBy() to avoid the explosion in the representation size.
bool operator<(const Domain &other) const
Lexicographic order on the intervals() representation.
Domain AdditionWith(const Domain &domain) const
Returns {x ∈ Int64, ∃ a ∈ D, ∃ b ∈ domain, x = a + b}.
static Domain FromIntervals(absl::Span< const ClosedInterval > intervals)
Creates a domain from the union of an unsorted list of intervals.
ClosedInterval front() const
Definition: sorted_interval_list.h:340
bool operator!=(const Domain &other) const
Definition: sorted_interval_list.h:330
Domain UnionWith(const Domain &domain) const
Returns the union of D and domain.
Domain ContinuousMultiplicationBy(int64 coeff) const
Returns a superset of MultiplicationBy() to avoid the explosion in the representation size.
ClosedInterval operator[](int i) const
Definition: sorted_interval_list.h:342
static Domain FromValues(std::vector< int64 > values)
Creates a domain from the union of an unsorted list of integer values.
static Domain FromVectorIntervals(const std::vector< std::vector< int64 > > &intervals)
This method is available in Python, Java and .NET.
static Domain FromFlatSpanOfIntervals(absl::Span< const int64 > flat_intervals)
Same as FromIntervals() for a flattened representation (start, end, start, end, .....
bool IsFixed() const
Returns true iff the domain is reduced to a single value.
Domain IntersectionWith(const Domain &domain) const
Returns the intersection of D and domain.
std::vector< int64 > FlattenedIntervals() const
This method returns the flattened list of interval bounds of the domain.
Domain & operator=(const Domain &other)
Copy operator (mandatory as we define the move operator).
Definition: sorted_interval_list.h:91
std::vector< ClosedInterval > intervals() const
Definition: sorted_interval_list.h:354
bool operator==(const Domain &other) const
Definition: sorted_interval_list.h:326
Domain(const Domain &other)
Copy constructor (mandatory as we define the move constructor).
Definition: sorted_interval_list.h:88
Domain(int64 value)
Constructor for the common case of a singleton domain.
bool Contains(int64 value) const
Returns true iff value is in Domain.
static Domain FromFlatIntervals(const std::vector< int64 > &flat_intervals)
This method is available in Python, Java and .NET.
Domain RelaxIfTooComplex() const
If NumIntervals() is too large, this return a superset of the domain.
absl::InlinedVector< ClosedInterval, 1 >::const_iterator end() const
Definition: sorted_interval_list.h:346
absl::InlinedVector< ClosedInterval, 1 >::const_iterator begin() const
Definition: sorted_interval_list.h:343
Domain SimplifyUsingImpliedDomain(const Domain &implied_domain) const
Advanced usage.
Domain DivisionBy(int64 coeff) const
Returns {x ∈ Int64, ∃ e ∈ D, x = e / coeff}.
This class represents a sorted list of disjoint, closed intervals.
Definition: sorted_interval_list.h:390
void InsertIntervals(const std::vector< int64 > &starts, const std::vector< int64 > &ends)
Adds all intervals [starts[i]..ends[i]].
Iterator GrowRightByOne(int64 value, int64 *newly_covered)
If value is in an interval, increase its end by one, otherwise insert the interval [value,...
Iterator FirstIntervalGreaterOrEqual(int64 value) const
Returns an iterator to either:
SortedDisjointIntervalList(const std::vector< int64 > &starts, const std::vector< int64 > &ends)
Creates a SortedDisjointIntervalList and fills it with intervals [starts[i]..ends[i]].
int NumIntervals() const
Returns the number of disjoint intervals in the list.
Definition: sorted_interval_list.h:458
IntervalSet::const_iterator ConstIterator
Definition: sorted_interval_list.h:399
SortedDisjointIntervalList BuildComplementOnInterval(int64 start, int64 end)
Builds the complement of the interval list on the interval [start, end].
Iterator InsertInterval(int64 start, int64 end)
Adds the interval [start..end] to the list, and merges overlapping or immediately adjacent intervals ...
Iterator LastIntervalLessOrEqual(int64 value) const
ConstIterator end() const
Definition: sorted_interval_list.h:484
void swap(SortedDisjointIntervalList &other)
Definition: sorted_interval_list.h:492
std::string DebugString() const
IntervalSet::iterator Iterator
Definition: sorted_interval_list.h:398
SortedDisjointIntervalList(const std::vector< int > &starts, const std::vector< int > &ends)
std::set< ClosedInterval, IntervalComparator > IntervalSet
Definition: sorted_interval_list.h:397
void clear()
Definition: sorted_interval_list.h:491
ConstIterator begin() const
Const iterators for SortedDisjoinIntervalList.
Definition: sorted_interval_list.h:483
SortedDisjointIntervalList()
SortedDisjointIntervalList(const std::vector< ClosedInterval > &intervals)
const ClosedInterval & last() const
Returns a const& to the last interval.
Definition: sorted_interval_list.h:489
void InsertIntervals(const std::vector< int > &starts, const std::vector< int > &ends)
Definition: cp_model.h:52
int64 SumOfKMinValueInDomain(const Domain &domain, int k)
std::ostream & operator<<(std::ostream &out, const ClosedInterval &interval)
int64 SumOfKMaxValueInDomain(const Domain &domain, int k)
bool IntervalsAreSortedAndNonAdjacent(absl::Span< const ClosedInterval > intervals)
Returns true iff we have:
Represents a closed interval [start, end].
Definition: sorted_interval_list.h:33
bool operator==(const ClosedInterval &other) const
Definition: sorted_interval_list.h:41
std::string DebugString() const
ClosedInterval(int64 s, int64 e)
Definition: sorted_interval_list.h:35
ClosedInterval()
Definition: sorted_interval_list.h:34
bool operator<(const ClosedInterval &other) const
Definition: sorted_interval_list.h:48
Definition: sorted_interval_list.h:392
bool operator()(const ClosedInterval &a, const ClosedInterval &b) const
Definition: sorted_interval_list.h:393