23#include "absl/container/inlined_vector.h"
24#include "absl/strings/str_format.h"
25#include "absl/types/span.h"
34 return absl::StrFormat(
"[%d,%d]",
start,
end);
38 absl::Span<const ClosedInterval> intervals) {
39 for (
int i = 1; i < intervals.size(); ++i) {
40 if (intervals[i - 1].start > intervals[i - 1].end)
return false;
42 if (intervals[i - 1].end >= intervals[i].start ||
43 intervals[i - 1].end + 1 >= intervals[i].start) {
47 return intervals.empty() ? true
48 : intervals.back().start <= intervals.back().end;
53template <
class Intervals>
54std::string IntervalsAsString(
const Intervals& intervals) {
56 for (ClosedInterval
interval : intervals) {
59 if (result.empty()) result =
"[]";
65void UnionOfSortedIntervals(absl::InlinedVector<ClosedInterval, 1>* intervals) {
66 DCHECK(std::is_sorted(intervals->begin(), intervals->end()));
68 for (
const ClosedInterval& i : *intervals) {
69 if (new_size > 0 && i.start <=
CapAdd((*intervals)[new_size - 1].end, 1)) {
70 (*intervals)[new_size - 1].end =
71 std::max(i.end, (*intervals)[new_size - 1].end);
73 (*intervals)[new_size++] = i;
76 intervals->resize(new_size);
80 intervals->shrink_to_fit();
90 const int64 adjust =
static_cast<int64>(result * positive_coeff <
value);
91 return result + adjust;
97 const int64 adjust =
static_cast<int64>(result * positive_coeff >
value);
98 return result - adjust;
106 const std::vector<ClosedInterval>& intervals) {
107 return out << IntervalsAsString(intervals);
111 return out << IntervalsAsString(domain);
123inline ClosedInterval UncheckedClosedInterval(
int64 s,
int64 e) {
132 : intervals_({UncheckedClosedInterval(left, right)}) {
133 if (left > right) intervals_.clear();
139 std::sort(values.begin(), values.end());
141 for (
const int64 v : values) {
142 if (result.intervals_.empty() || v > result.intervals_.back().end + 1) {
143 result.intervals_.push_back({v, v});
145 result.intervals_.back().end = v;
154 std::sort(result.intervals_.begin(), result.intervals_.end());
155 UnionOfSortedIntervals(&result.intervals_);
160 DCHECK(flat_intervals.size() % 2 == 0) << flat_intervals.size();
162 result.intervals_.reserve(flat_intervals.size() / 2);
163 for (
int i = 0; i < flat_intervals.size(); i += 2) {
164 result.intervals_.push_back({flat_intervals[i], flat_intervals[i + 1]});
166 std::sort(result.intervals_.begin(), result.intervals_.end());
167 UnionOfSortedIntervals(&result.intervals_);
176 const std::vector<std::vector<int64>>& intervals) {
186 std::sort(result.intervals_.begin(), result.intervals_.end());
187 UnionOfSortedIntervals(&result.intervals_);
209 return intervals_.front().start;
214 return intervals_.back().end;
219 return intervals_.front().start;
226 auto it = std::upper_bound(intervals_.begin(), intervals_.end(),
228 if (it == intervals_.begin())
return false;
230 return value <= it->end;
235 const auto& others = domain.intervals_;
238 for (; i < others.size() &&
interval.end > others[i].end; ++i) {
240 if (i == others.size())
return false;
241 if (
interval.start < others[i].start)
return false;
249 result.intervals_.reserve(intervals_.size() + 1);
252 result.intervals_.push_back({next_start,
interval.start - 1});
257 result.intervals_.push_back({next_start,
kint64max});
264 result.NegateInPlace();
268void Domain::NegateInPlace() {
269 if (intervals_.empty())
return;
270 std::reverse(intervals_.begin(), intervals_.end());
271 if (intervals_.back().end ==
kint64min) {
273 intervals_.pop_back();
275 for (ClosedInterval& ref : intervals_) {
276 std::swap(ref.start, ref.end);
285 const auto&
a = intervals_;
286 const auto&
b = domain.intervals_;
287 for (
int i = 0, j = 0; i <
a.size() && j <
b.size();) {
288 if (
a[i].start <=
b[j].start) {
289 if (
a[i].
end <
b[j].start) {
296 result.intervals_.push_back({
b[j].start,
a[i].end});
299 result.intervals_.push_back({
b[j].start,
b[j].end});
305 if (
b[j].
end <
a[i].start) {
309 result.intervals_.push_back({
a[i].start,
b[j].end});
312 result.intervals_.push_back({
a[i].start,
a[i].end});
324 const auto&
a = intervals_;
325 const auto&
b = domain.intervals_;
326 result.intervals_.resize(
a.size() +
b.size());
327 std::merge(
a.begin(),
a.end(),
b.begin(),
b.end(), result.intervals_.begin());
328 UnionOfSortedIntervals(&result.intervals_);
336 const auto&
a = intervals_;
337 const auto&
b = domain.intervals_;
338 result.intervals_.reserve(
a.size() *
b.size());
341 result.intervals_.push_back(
347 if (
a.size() > 1 &&
b.size() > 1) {
348 std::sort(result.intervals_.begin(), result.intervals_.end());
350 UnionOfSortedIntervals(&result.intervals_);
363 if (exact !=
nullptr) *exact =
true;
364 if (intervals_.empty())
return {};
365 if (coeff == 0)
return Domain(0);
367 const int64 abs_coeff = std::abs(coeff);
368 const int64 size_if_non_trivial = abs_coeff > 1 ?
Size() : 0;
369 if (size_if_non_trivial > kDomainComplexityLimit) {
370 if (exact !=
nullptr) *exact =
false;
378 result.intervals_.reserve(size_if_non_trivial);
380 for (
int64 v = i.start;; ++v) {
382 if (v >= min_value && v <= max_value) {
384 const int64 new_value = v * abs_coeff;
385 result.intervals_.push_back({new_value, new_value});
389 if (v == i.end)
break;
395 if (coeff < 0) result.NegateInPlace();
401 const int64 abs_coeff = std::abs(coeff);
406 UnionOfSortedIntervals(&result.intervals_);
407 if (coeff < 0) result.NegateInPlace();
422 result.intervals_.push_back(new_interval);
425 std::sort(result.intervals_.begin(), result.intervals_.end());
426 UnionOfSortedIntervals(&result.intervals_);
433 const int64 abs_coeff = std::abs(coeff);
436 i.
end = i.
end / abs_coeff;
438 UnionOfSortedIntervals(&result.intervals_);
439 if (coeff < 0) result.NegateInPlace();
449 const int64 abs_coeff = std::abs(coeff);
453 if (start >
end)
continue;
454 if (new_size > 0 && start == result.intervals_[new_size - 1].end + 1) {
455 result.intervals_[new_size - 1].end =
end;
457 result.intervals_[new_size++] = {start,
end};
460 result.intervals_.resize(new_size);
461 result.intervals_.shrink_to_fit();
463 if (coeff < 0) result.NegateInPlace();
473 if (implied_domain.
IsEmpty())
return result;
478 bool started =
false;
484 if (started && implied_domain.intervals_[i].start <
interval.start) {
485 result.intervals_.push_back({min_point, max_point});
492 for (; i < implied_domain.intervals_.size(); ++i) {
500 max_point = inter_max;
505 max_point = inter_max;
510 if (i == implied_domain.intervals_.size())
break;
513 result.intervals_.push_back({min_point, max_point});
520 std::vector<int64> result;
529 const auto& d1 = intervals_;
530 const auto& d2 = other.intervals_;
531 const int common_size =
std::min(d1.size(), d2.size());
532 for (
int i = 0; i < common_size; ++i) {
537 if (i1.
end < i2.
end)
return true;
538 if (i1.
end > i2.
end)
return false;
540 return d1.size() < d2.size();
546 int64 current_sum = 0.0;
547 int current_index = 0;
549 if (current_index >= k)
break;
551 if (current_index >= k)
break;
566 const std::vector<int64>& starts,
const std::vector<int64>& ends) {
571 const std::vector<int>& starts,
const std::vector<int>& ends) {
576 const std::vector<ClosedInterval>& intervals) {
585 int64 next_start = start;
589 if (next_end >
end)
break;
590 if (next_start <= next_end) {
595 if (next_start <=
end) {
598 return interval_list;
607 return intervals_.end();
610 auto result = intervals_.insert({start,
end});
611 if (!result.second)
return result.first;
622 auto it1 = result.first;
624 it1 = intervals_.begin();
626 const int64 before_start = start - 1;
627 while (it1 != intervals_.begin()) {
630 if (prev_it->end < before_start)
break;
637 auto it2 = result.first;
639 it2 = intervals_.end();
644 }
while (it2 != intervals_.end() && it2->start <= after_end);
652 if (it1 == it3)
return it3;
655 auto it = intervals_.erase(it1, it3);
675 *newly_covered =
value;
676 if (it ==
end() || it->start !=
value + 1) {
694 "that would grow already ends at "
696 *newly_covered = it_prev->end + 1;
697 if (it !=
end() && it_prev->end + 2 == it->start) {
700 intervals_.erase(it);
708void SortedDisjointIntervalList::InsertAll(
const std::vector<T>& starts,
709 const std::vector<T>& ends) {
710 CHECK_EQ(starts.size(), ends.size());
711 for (
int i = 0; i < starts.size(); ++i)
InsertInterval(starts[i], ends[i]);
715 const std::vector<int64>& starts,
const std::vector<int64>& ends) {
716 InsertAll(starts, ends);
720 const std::vector<int>& ends) {
722 InsertAll(starts, ends);
728 if (it ==
begin())
return it;
732 return it_prev->end >=
value ? it_prev : it;
#define DCHECK_LE(val1, val2)
#define CHECK_EQ(val1, val2)
#define DCHECK_GE(val1, val2)
#define CHECK_NE(val1, val2)
#define DCHECK_GT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
We call domain any subset of Int64 = [kint64min, kint64max].
static Domain AllValues()
Returns the full domain Int64.
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}.
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}.
int64 Min() const
Returns the min value of the domain.
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.
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.
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.
Domain()
By default, Domain will be empty.
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
static Domain FromFlatSpanOfIntervals(absl::Span< const int64 > flat_intervals)
Same as FromIntervals() for a flattened representation (start, end, start, end, .....
Domain SimplifyUsingImpliedDomain(const Domain &implied_domain) const
Advanced usage.
Domain DivisionBy(int64 coeff) const
Returns {x ∈ Int64, ∃ e ∈ D, x = e / coeff}.
std::string DebugString() const override
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 ...
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
std::string DebugString() const
IntervalSet::iterator Iterator
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()
static const int64 kint64max
static const int64 kint64min
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 CapAdd(int64 x, int64 y)
int64 FloorRatio(int64 value, int64 positive_coeff)
int64 SumOfKMinValueInDomain(const Domain &domain, int k)
int64 CapProd(int64 x, int64 y)
int64 CapSub(int64 x, int64 y)
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
int64 CeilRatio(int64 value, int64 positive_coeff)
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].
std::string DebugString() const