14#ifndef OR_TOOLS_UTIL_SORTED_INTERVAL_LIST_H_
15#define OR_TOOLS_UTIL_SORTED_INTERVAL_LIST_H_
26#include "absl/container/inlined_vector.h"
27#include "absl/types/span.h"
58 DLOG_IF(DFATAL, s > e) <<
"Invalid ClosedInterval(" << s <<
", " << e
76 return H::combine(std::move(h), interval.
start, interval.
end);
90 const std::vector<ClosedInterval>& intervals);
101 absl::Span<const ClosedInterval> intervals);
124 intervals_ = other.intervals_;
129 Domain(
Domain&& other) noexcept : intervals_(std::move(other.intervals_)) {}
133 intervals_ = std::move(other.intervals_);
139 explicit Domain(int64_t value);
145 Domain(int64_t left, int64_t right);
174 absl::Span<const int64_t> flat_intervals);
188 const std::vector<std::vector<int64_t> >& intervals);
220 const absl::InlinedVector<ClosedInterval, 1>& intervals)
221 : value_(intervals.empty() ? int64_t{0} : intervals.
front().start),
222 it_(intervals.
begin()),
223 end_(intervals.
end()) {}
228 if (value_ == it_->end) {
230 if (it_ != end_) value_ = it_->start;
237 absl::InlinedVector<ClosedInterval, 1>::const_iterator
end)
const {
243 absl::InlinedVector<ClosedInterval, 1>::const_iterator it_;
244 absl::InlinedVector<ClosedInterval, 1>::const_iterator end_;
248 absl::InlinedVector<ClosedInterval, 1>::const_iterator
end()
const {
251 const absl::InlinedVector<ClosedInterval, 1>&
intervals;
255 absl::InlinedVector<ClosedInterval, 1>::const_iterator
end()
const {
262 return {std::move(this->intervals_)};
274 int64_t
Size()
const;
281 if (intervals_.size() == 1) {
282 return intervals_[0].end == intervals_[0].start + 1;
283 }
else if (intervals_.size() == 2) {
284 return intervals_[0].end == intervals_[0].start &&
285 intervals_[1].end == intervals_[1].start;
347 int64_t
Distance(int64_t value)
const;
503 return intervals_ == other.intervals_;
507 return intervals_ != other.intervals_;
510 template <
typename H>
512 return H::combine(std::move(h), domain.intervals_);
524 absl::InlinedVector<ClosedInterval, 1>::const_iterator
begin()
const {
525 return intervals_.begin();
527 absl::InlinedVector<ClosedInterval, 1>::const_iterator
end()
const {
528 return intervals_.end();
533 void NegateInPlace();
537 static constexpr int kDomainComplexityLimit = 100;
544 absl::InlinedVector<ClosedInterval, 1> intervals_;
567 return a.
start != b.start ? a.
start < b.start : a.
end < b.end;
576 const std::vector<ClosedInterval>& intervals);
586 const std::vector<int64_t>& ends);
588 const std::vector<int>& ends);
625 const std::vector<int64_t>& ends);
627 const std::vector<int>& ends);
665 void clear() { intervals_.clear(); }
667 intervals_.swap(other.intervals_);
672 void InsertAll(
const std::vector<T>& starts,
const std::vector<T>& ends);
687 int64_t
operator*()
const {
return static_cast<int64_t
>(current_); }
701 AssertNotFullInt64Range(interval);
705 AssertNotFullInt64Range(interval);
706 return Iterator(
static_cast<uint64_t
>(interval.
end) + 1);
710 explicit Iterator(uint64_t current) : current_(current) {}
715 DCHECK_NE(
static_cast<uint64_t
>(interval.
start),
716 static_cast<uint64_t
>(interval.
end) + 1)
717 <<
"Iteration over the full int64_t range is not supported.";
727#if __cplusplus >= 202002L
728static_assert(std::input_iterator<ClosedInterval::Iterator>);
bool operator!=(Iterator other) const
static Iterator Begin(ClosedInterval interval)
bool operator==(Iterator other) const
std::ptrdiff_t difference_type
Iterator(const Iterator &)=default
static Iterator End(ClosedInterval interval)
int64_t operator*() const
Iterator & operator=(const Iterator &)=default
DomainIterator(const absl::InlinedVector< ClosedInterval, 1 > &intervals)
int64_t operator*() const
bool operator!=(absl::InlinedVector< ClosedInterval, 1 >::const_iterator end) const
Domain SimplifyUsingImpliedDomain(const Domain &implied_domain) const
static Domain FromVectorIntervals(const std::vector< std::vector< int64_t > > &intervals)
DomainIteratorBeginEndWithOwnership Values() const &&
Domain(Domain &&other) noexcept
Move constructor.
Domain MultiplicationBy(int64_t coeff, bool *exact=nullptr) const
static Domain FromValues(std::vector< int64_t > values)
bool operator<(const Domain &other) const
friend H AbslHashValue(H h, const Domain &domain)
int64_t ValueAtOrAfter(int64_t input) const
Domain(const Domain &other)
Copy constructor (mandatory as we define the move constructor).
std::vector< int64_t > FlattenedIntervals() const
Domain SquareSuperset() const
Domain IntersectionWith(const Domain &domain) const
Domain QuadraticSuperset(int64_t a, int64_t b, int64_t c, int64_t d) const
static Domain FromIntervals(absl::Span< const ClosedInterval > intervals)
Domain ContinuousMultiplicationBy(int64_t coeff) const
bool Contains(int64_t value) const
DomainIteratorBeginEnd Values() const &
Domain PositiveModuloBySuperset(const Domain &modulo) const
Domain AdditionWith(const Domain &domain) const
bool IsIncludedIn(const Domain &domain) const
static Domain FromFlatIntervals(const std::vector< int64_t > &flat_intervals)
int64_t SmallestValue() const
Domain()
By default, Domain will be empty.
int64_t FixedValue() const
Domain DivisionBy(int64_t coeff) const
int64_t Distance(int64_t value) const
std::string ToString() const
Domain & operator=(const Domain &other)
Copy operator (mandatory as we define the move operator).
static Domain AllValues()
static Domain FromFlatSpanOfIntervals(absl::Span< const int64_t > flat_intervals)
absl::InlinedVector< ClosedInterval, 1 >::const_iterator end() const
Domain PositiveDivisionBySuperset(const Domain &divisor) const
Domain RelaxIfTooComplex() const
absl::InlinedVector< ClosedInterval, 1 >::const_iterator begin() const
Domain UnionWith(const Domain &domain) const
ClosedInterval back() const
Domain Complement() const
bool operator==(const Domain &other) const
Domain & operator=(Domain &&other) noexcept
Move operator.
ClosedInterval operator[](int i) const
Domain PartAroundZero() const
ClosedInterval front() const
Domain InverseMultiplicationBy(int64_t coeff) const
int64_t ValueAtOrBefore(int64_t input) const
bool operator!=(const Domain &other) const
bool HasTwoValues() const
int64_t ClosestValue(int64_t wanted) const
void InsertIntervals(const std::vector< int64_t > &starts, const std::vector< int64_t > &ends)
SortedDisjointIntervalList()
Iterator LastIntervalLessOrEqual(int64_t value) const
std::string DebugString() const
Iterator InsertInterval(int64_t start, int64_t end)
const ClosedInterval & last() const
ConstIterator begin() const
SortedDisjointIntervalList BuildComplementOnInterval(int64_t start, int64_t end)
IntervalSet::const_iterator ConstIterator
void swap(SortedDisjointIntervalList &other)
std::set< ClosedInterval, IntervalComparator > IntervalSet
IntervalSet::iterator Iterator
Iterator FirstIntervalGreaterOrEqual(int64_t value) const
ConstIterator end() const
Iterator GrowRightByOne(int64_t value, int64_t *newly_covered)
In SWIG mode, we don't want anything besides these top-level includes.
ClosedInterval::Iterator end(ClosedInterval interval)
int64_t SumOfKMinValueInDomain(const Domain &domain, int k)
Returns the sum of smallest k values in the domain.
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
bool IntervalsAreSortedAndNonAdjacent(absl::Span< const ClosedInterval > intervals)
ClosedInterval::Iterator begin(ClosedInterval interval)
int64_t SumOfKMaxValueInDomain(const Domain &domain, int k)
Returns the sum of largest k values in the domain.
static int input(yyscan_t yyscanner)
constexpr bool operator==(const ClosedInterval &other) const
std::string DebugString() const
constexpr bool operator<(const ClosedInterval &other) const
ClosedInterval(int64_t v)
friend H AbslHashValue(H h, const ClosedInterval &interval)
ClosedInterval(int64_t s, int64_t e)
absl::InlinedVector< ClosedInterval, 1 >::const_iterator end() const
absl::InlinedVector< ClosedInterval, 1 > intervals
DomainIterator begin() const
absl::InlinedVector< ClosedInterval, 1 >::const_iterator end() const
DomainIterator begin() const
const absl::InlinedVector< ClosedInterval, 1 > & intervals
bool operator()(const ClosedInterval &a, const ClosedInterval &b) const