14#ifndef OR_TOOLS_UTIL_SORTED_INTERVAL_LIST_H_
15#define OR_TOOLS_UTIL_SORTED_INTERVAL_LIST_H_
23#include "absl/container/inlined_vector.h"
24#include "absl/types/span.h"
36 DLOG_IF(DFATAL, s > e) <<
"Invalid ClosedInterval(" << s <<
", " << e
58 const std::vector<ClosedInterval>& intervals);
69 absl::Span<const ClosedInterval> intervals);
92 intervals_ = other.intervals_;
101 intervals_ = std::move(other.intervals_);
143 const std::vector<std::vector<int64> >&
intervals);
327 return intervals_ == other.intervals_;
331 return intervals_ != other.intervals_;
343 absl::InlinedVector<ClosedInterval, 1>::const_iterator
begin()
const {
344 return intervals_.begin();
346 absl::InlinedVector<ClosedInterval, 1>::const_iterator
end()
const {
347 return intervals_.end();
355 return {intervals_.begin(), intervals_.end()};
360 void NegateInPlace();
364 static constexpr int kDomainComplexityLimit = 100;
371 absl::InlinedVector<ClosedInterval, 1> intervals_;
374std::ostream&
operator<<(std::ostream& out,
const Domain& domain);
394 return a.start !=
b.start ?
a.start <
b.start :
a.end <
b.end;
403 const std::vector<ClosedInterval>& intervals);
413 const std::vector<int64>& ends);
415 const std::vector<int>& ends);
451 const std::vector<int64>& ends);
453 const std::vector<int>& ends);
491 void clear() { intervals_.clear(); }
493 intervals_.swap(other.intervals_);
498 void InsertAll(
const std::vector<T>& starts,
const std::vector<T>& ends);
#define DLOG_IF(severity, condition)
We call domain any subset of Int64 = [kint64min, kint64max].
static Domain AllValues()
Returns the full domain Int64.
Domain(Domain &&other)
Move constructor.
static Domain FromFlatIntervals(const std::vector< int64 > &flat_intervals)
This method is available in Python, Java and .NET.
std::string ToString() const
Returns a compact string of a vector of intervals like "[1,4][6][10,20]".
int64 FixedValue() const
Returns the value of a fixed domain.
Domain Negation() const
Returns {x ∈ Int64, ∃ e ∈ D, x = -e}.
Domain Complement() const
Returns the set Int64 ∖ D.
bool IsIncludedIn(const Domain &domain) const
Returns true iff D is included in the given domain.
Domain MultiplicationBy(int64 coeff, bool *exact=nullptr) const
Returns {x ∈ Int64, ∃ e ∈ D, x = e * coeff}.
static Domain FromValues(std::vector< int64 > values)
Creates a domain from the union of an unsorted list of integer values.
int64 Size() const
Returns the number of elements in the domain.
int NumIntervals() const
Basic read-only std::vector<> wrapping to view a Domain as a sorted list of non-adjacent intervals.
Domain InverseMultiplicationBy(const int64 coeff) const
Returns {x ∈ Int64, ∃ e ∈ D, x * coeff = e}.
ClosedInterval back() const
static Domain FromVectorIntervals(const std::vector< std::vector< int64 > > &intervals)
This method is available in Python, Java and .NET.
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}.
ClosedInterval front() const
int64 Min() const
Returns the min value of the domain.
bool operator!=(const Domain &other) const
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
int64 Max() const
Returns the max value of the domain.
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.
bool IsEmpty() const
Returns true if this is the empty set.
Domain & operator=(const Domain &other)
Copy operator (mandatory as we define the move operator).
std::vector< ClosedInterval > intervals() const
static Domain FromIntervals(absl::Span< const ClosedInterval > intervals)
Creates a domain from the union of an unsorted list of intervals.
bool operator==(const Domain &other) const
Domain()
By default, Domain will be empty.
Domain(const Domain &other)
Copy constructor (mandatory as we define the move constructor).
bool Contains(int64 value) const
Returns true iff value is in Domain.
Domain RelaxIfTooComplex() const
If NumIntervals() is too large, this return a superset of the domain.
absl::InlinedVector< ClosedInterval, 1 >::const_iterator end() const
Domain & operator=(Domain &&other)
Move operator.
static Domain FromFlatSpanOfIntervals(absl::Span< const int64 > flat_intervals)
Same as FromIntervals() for a flattened representation (start, end, start, end, .....
absl::InlinedVector< ClosedInterval, 1 >::const_iterator begin() const
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.
void InsertIntervals(const std::vector< int64 > &starts, const std::vector< int64 > &ends)
Adds all intervals [starts[i]..ends[i]].
Iterator InsertInterval(int64 start, int64 end)
Adds the interval [start..end] to the list, and merges overlapping or immediately adjacent intervals ...
int NumIntervals() const
Returns the number of disjoint intervals in the list.
IntervalSet::const_iterator ConstIterator
Iterator LastIntervalLessOrEqual(int64 value) const
SortedDisjointIntervalList BuildComplementOnInterval(int64 start, int64 end)
Builds the complement of the interval list on the interval [start, end].
ConstIterator end() const
void swap(SortedDisjointIntervalList &other)
std::string DebugString() const
IntervalSet::iterator Iterator
std::set< ClosedInterval, IntervalComparator > IntervalSet
Iterator FirstIntervalGreaterOrEqual(int64 value) const
Returns an iterator to either:
Iterator GrowRightByOne(int64 value, int64 *newly_covered)
If value is in an interval, increase its end by one, otherwise insert the interval [value,...
ConstIterator begin() const
Const iterators for SortedDisjoinIntervalList.
SortedDisjointIntervalList()
const ClosedInterval & last() const
Returns a const& to the last interval.
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 SumOfKMinValueInDomain(const Domain &domain, int k)
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
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].
bool operator==(const ClosedInterval &other) const
std::string DebugString() const
ClosedInterval(int64 s, int64 e)
bool operator<(const ClosedInterval &other) const
bool operator()(const ClosedInterval &a, const ClosedInterval &b) const