OR-Tools  8.2
sorted_interval_list.cc
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
15
16#include <algorithm>
17#include <cmath>
18#include <map>
19#include <string>
20#include <utility>
21#include <vector>
22
23#include "absl/container/inlined_vector.h"
24#include "absl/strings/str_format.h"
25#include "absl/types/span.h"
29
30namespace operations_research {
31
32std::string ClosedInterval::DebugString() const {
33 if (start == end) return absl::StrFormat("[%d]", start);
34 return absl::StrFormat("[%d,%d]", start, end);
35}
36
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;
41 // First test make sure that intervals[i - 1].end + 1 will not overflow.
42 if (intervals[i - 1].end >= intervals[i].start ||
43 intervals[i - 1].end + 1 >= intervals[i].start) {
44 return false;
45 }
46 }
47 return intervals.empty() ? true
48 : intervals.back().start <= intervals.back().end;
49}
50
51namespace {
52
53template <class Intervals>
54std::string IntervalsAsString(const Intervals& intervals) {
55 std::string result;
56 for (ClosedInterval interval : intervals) {
57 result += interval.DebugString();
58 }
59 if (result.empty()) result = "[]";
60 return result;
61}
62
63// Transforms a sorted list of intervals in a sorted DISJOINT list for which
64// IntervalsAreSortedAndNonAdjacent() would return true.
65void UnionOfSortedIntervals(absl::InlinedVector<ClosedInterval, 1>* intervals) {
66 DCHECK(std::is_sorted(intervals->begin(), intervals->end()));
67 int new_size = 0;
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);
72 } else {
73 (*intervals)[new_size++] = i;
74 }
75 }
76 intervals->resize(new_size);
77
78 // This is important for InlinedVector in the case the result is a single
79 // intervals.
80 intervals->shrink_to_fit();
82}
83
84} // namespace
85
86// TODO(user): Use MathUtil::CeilOfRatio / FloorOfRatio instead.
87int64 CeilRatio(int64 value, int64 positive_coeff) {
88 DCHECK_GT(positive_coeff, 0);
89 const int64 result = value / positive_coeff;
90 const int64 adjust = static_cast<int64>(result * positive_coeff < value);
91 return result + adjust;
92}
93
94int64 FloorRatio(int64 value, int64 positive_coeff) {
95 DCHECK_GT(positive_coeff, 0);
96 const int64 result = value / positive_coeff;
97 const int64 adjust = static_cast<int64>(result * positive_coeff > value);
98 return result - adjust;
99}
100
101std::ostream& operator<<(std::ostream& out, const ClosedInterval& interval) {
102 return out << interval.DebugString();
103}
104
105std::ostream& operator<<(std::ostream& out,
106 const std::vector<ClosedInterval>& intervals) {
107 return out << IntervalsAsString(intervals);
108}
109
110std::ostream& operator<<(std::ostream& out, const Domain& domain) {
111 return out << IntervalsAsString(domain);
112}
113
114Domain::Domain(int64 value) : intervals_({{value, value}}) {}
115
116// HACK(user): We spare significant time if we use an initializer here, because
117// InlineVector<1> is able to recognize the fast path or "exactly one element".
118// I was unable to obtain the same performance with any other recipe, I always
119// had at least 1 more cycle. See BM_SingleIntervalDomainConstructor.
120// Since the constructor takes very few cycles (most likely less than 10),
121// that's quite significant.
122namespace {
123inline ClosedInterval UncheckedClosedInterval(int64 s, int64 e) {
124 ClosedInterval i;
125 i.start = s;
126 i.end = e;
127 return i;
128}
129} // namespace
130
132 : intervals_({UncheckedClosedInterval(left, right)}) {
133 if (left > right) intervals_.clear();
134}
135
137
138Domain Domain::FromValues(std::vector<int64> values) {
139 std::sort(values.begin(), values.end());
140 Domain result;
141 for (const int64 v : values) {
142 if (result.intervals_.empty() || v > result.intervals_.back().end + 1) {
143 result.intervals_.push_back({v, v});
144 } else {
145 result.intervals_.back().end = v;
146 }
147 }
148 return result;
149}
150
151Domain Domain::FromIntervals(absl::Span<const ClosedInterval> intervals) {
152 Domain result;
153 result.intervals_.assign(intervals.begin(), intervals.end());
154 std::sort(result.intervals_.begin(), result.intervals_.end());
155 UnionOfSortedIntervals(&result.intervals_);
156 return result;
157}
158
159Domain Domain::FromFlatSpanOfIntervals(absl::Span<const int64> flat_intervals) {
160 DCHECK(flat_intervals.size() % 2 == 0) << flat_intervals.size();
161 Domain result;
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]});
165 }
166 std::sort(result.intervals_.begin(), result.intervals_.end());
167 UnionOfSortedIntervals(&result.intervals_);
168 return result;
169}
170
171Domain Domain::FromFlatIntervals(const std::vector<int64>& flat_intervals) {
172 return FromFlatSpanOfIntervals(absl::MakeSpan(flat_intervals));
173}
174
176 const std::vector<std::vector<int64>>& intervals) {
177 Domain result;
178 for (const std::vector<int64>& interval : intervals) {
179 if (interval.size() == 1) {
180 result.intervals_.push_back({interval[0], interval[0]});
181 } else {
182 DCHECK_EQ(interval.size(), 2);
183 result.intervals_.push_back({interval[0], interval[1]});
184 }
185 }
186 std::sort(result.intervals_.begin(), result.intervals_.end());
187 UnionOfSortedIntervals(&result.intervals_);
188 return result;
189}
190
191bool Domain::IsEmpty() const { return intervals_.empty(); }
192
193bool Domain::IsFixed() const { return Min() == Max(); }
194
196 int64 size = 0;
197 for (const ClosedInterval interval : intervals_) {
200 }
201 // Because the intervals are closed on both side above, with miss 1 per
202 // interval.
203 size = operations_research::CapAdd(size, intervals_.size());
204 return size;
205}
206
208 DCHECK(!IsEmpty());
209 return intervals_.front().start;
210}
211
213 DCHECK(!IsEmpty());
214 return intervals_.back().end;
215}
216
218 DCHECK(IsFixed());
219 return intervals_.front().start;
220}
221
223 // Because we only compare by start and there is no duplicate starts, this
224 // should be the next interval after the one that has a chance to contains
225 // value.
226 auto it = std::upper_bound(intervals_.begin(), intervals_.end(),
228 if (it == intervals_.begin()) return false;
229 --it;
230 return value <= it->end;
231}
232
233bool Domain::IsIncludedIn(const Domain& domain) const {
234 int i = 0;
235 const auto& others = domain.intervals_;
236 for (const ClosedInterval interval : intervals_) {
237 // Find the unique interval in others that contains interval if any.
238 for (; i < others.size() && interval.end > others[i].end; ++i) {
239 }
240 if (i == others.size()) return false;
241 if (interval.start < others[i].start) return false;
242 }
243 return true;
244}
245
247 Domain result;
248 int64 next_start = kint64min;
249 result.intervals_.reserve(intervals_.size() + 1);
250 for (const ClosedInterval& interval : intervals_) {
251 if (interval.start != kint64min) {
252 result.intervals_.push_back({next_start, interval.start - 1});
253 }
254 if (interval.end == kint64max) return result;
255 next_start = interval.end + 1;
256 }
257 result.intervals_.push_back({next_start, kint64max});
258 DCHECK(IntervalsAreSortedAndNonAdjacent(result.intervals_));
259 return result;
260}
261
263 Domain result = *this;
264 result.NegateInPlace();
265 return result;
266}
267
268void Domain::NegateInPlace() {
269 if (intervals_.empty()) return;
270 std::reverse(intervals_.begin(), intervals_.end());
271 if (intervals_.back().end == kint64min) {
272 // corner-case
273 intervals_.pop_back();
274 }
275 for (ClosedInterval& ref : intervals_) {
276 std::swap(ref.start, ref.end);
277 ref.start = ref.start == kint64min ? kint64max : -ref.start;
278 ref.end = ref.end == kint64min ? kint64max : -ref.end;
279 }
281}
282
284 Domain result;
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) {
290 // Empty intersection. We advance past the first interval.
291 ++i;
292 } else { // a[i].end >= b[j].start
293 // Non-empty intersection: push back the intersection of these two, and
294 // advance past the first interval to finish.
295 if (a[i].end <= b[j].end) {
296 result.intervals_.push_back({b[j].start, a[i].end});
297 ++i;
298 } else { // a[i].end > b[j].end.
299 result.intervals_.push_back({b[j].start, b[j].end});
300 ++j;
301 }
302 }
303 } else { // a[i].start > b[i].start.
304 // We do the exact same thing as above, but swapping a and b.
305 if (b[j].end < a[i].start) {
306 ++j;
307 } else { // b[j].end >= a[i].start
308 if (b[j].end <= a[i].end) {
309 result.intervals_.push_back({a[i].start, b[j].end});
310 ++j;
311 } else { // a[i].end > b[j].end.
312 result.intervals_.push_back({a[i].start, a[i].end});
313 ++i;
314 }
315 }
316 }
317 }
318 DCHECK(IntervalsAreSortedAndNonAdjacent(result.intervals_));
319 return result;
320}
321
322Domain Domain::UnionWith(const Domain& domain) const {
323 Domain result;
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_);
329 return result;
330}
331
332// TODO(user): Use a better algorithm.
333Domain Domain::AdditionWith(const Domain& domain) const {
334 Domain result;
335
336 const auto& a = intervals_;
337 const auto& b = domain.intervals_;
338 result.intervals_.reserve(a.size() * b.size());
339 for (const ClosedInterval& i : a) {
340 for (const ClosedInterval& j : b) {
341 result.intervals_.push_back(
342 {CapAdd(i.start, j.start), CapAdd(i.end, j.end)});
343 }
344 }
345
346 // The sort is not needed if one of the list is of size 1.
347 if (a.size() > 1 && b.size() > 1) {
348 std::sort(result.intervals_.begin(), result.intervals_.end());
349 }
350 UnionOfSortedIntervals(&result.intervals_);
351 return result;
352}
353
355 if (NumIntervals() > kDomainComplexityLimit) {
356 return Domain(Min(), Max());
357 } else {
358 return *this;
359 }
360}
361
362Domain Domain::MultiplicationBy(int64 coeff, bool* exact) const {
363 if (exact != nullptr) *exact = true;
364 if (intervals_.empty()) return {};
365 if (coeff == 0) return Domain(0);
366
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;
371 return ContinuousMultiplicationBy(coeff);
372 }
373
374 Domain result;
375 if (abs_coeff > 1) {
376 const int64 max_value = kint64max / abs_coeff;
377 const int64 min_value = kint64min / abs_coeff;
378 result.intervals_.reserve(size_if_non_trivial);
379 for (const ClosedInterval& i : intervals_) {
380 for (int64 v = i.start;; ++v) {
381 // We ignore anything that overflow.
382 if (v >= min_value && v <= max_value) {
383 // Because abs_coeff > 1, all new values are disjoint.
384 const int64 new_value = v * abs_coeff;
385 result.intervals_.push_back({new_value, new_value});
386 }
387
388 // This is to avoid doing ++v when v is kint64max!
389 if (v == i.end) break;
390 }
391 }
392 } else {
393 result = *this;
394 }
395 if (coeff < 0) result.NegateInPlace();
396 return result;
397}
398
400 Domain result = *this;
401 const int64 abs_coeff = std::abs(coeff);
402 for (ClosedInterval& i : result.intervals_) {
403 i.start = CapProd(i.start, abs_coeff);
404 i.end = CapProd(i.end, abs_coeff);
405 }
406 UnionOfSortedIntervals(&result.intervals_);
407 if (coeff < 0) result.NegateInPlace();
408 return result;
409}
410
412 Domain result;
413 for (const ClosedInterval& i : this->intervals_) {
414 for (const ClosedInterval& j : domain.intervals_) {
415 ClosedInterval new_interval;
416 const int64 a = CapProd(i.start, j.start);
417 const int64 b = CapProd(i.end, j.end);
418 const int64 c = CapProd(i.start, j.end);
419 const int64 d = CapProd(i.end, j.start);
420 new_interval.start = std::min({a, b, c, d});
421 new_interval.end = std::max({a, b, c, d});
422 result.intervals_.push_back(new_interval);
423 }
424 }
425 std::sort(result.intervals_.begin(), result.intervals_.end());
426 UnionOfSortedIntervals(&result.intervals_);
427 return result;
428}
429
431 CHECK_NE(coeff, 0);
432 Domain result = *this;
433 const int64 abs_coeff = std::abs(coeff);
434 for (ClosedInterval& i : result.intervals_) {
435 i.start = i.start / abs_coeff;
436 i.end = i.end / abs_coeff;
437 }
438 UnionOfSortedIntervals(&result.intervals_);
439 if (coeff < 0) result.NegateInPlace();
440 return result;
441}
442
444 if (coeff == 0) {
445 return Contains(0) ? Domain::AllValues() : Domain();
446 }
447 Domain result = *this;
448 int new_size = 0;
449 const int64 abs_coeff = std::abs(coeff);
450 for (const ClosedInterval& i : result.intervals_) {
451 const int64 start = CeilRatio(i.start, abs_coeff);
452 const int64 end = FloorRatio(i.end, 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;
456 } else {
457 result.intervals_[new_size++] = {start, end};
458 }
459 }
460 result.intervals_.resize(new_size);
461 result.intervals_.shrink_to_fit();
462 DCHECK(IntervalsAreSortedAndNonAdjacent(result.intervals_));
463 if (coeff < 0) result.NegateInPlace();
464 return result;
465}
466
467// It is a bit difficult to see, but this code is doing the same thing as
468// for all interval in this.UnionWith(implied_domain.Complement())):
469// - Take the two extreme points (min and max) in interval \inter implied.
470// - Append to result [min, max] if these points exists.
472 Domain result;
473 if (implied_domain.IsEmpty()) return result;
474
475 int i = 0;
476 int64 min_point;
477 int64 max_point;
478 bool started = false;
479 for (const ClosedInterval interval : intervals_) {
480 // We only "close" the new result interval if it cannot be extended by
481 // implied_domain.Complement(). The only extension possible look like:
482 // interval_: ...] [....
483 // implied : ...] [... i ...]
484 if (started && implied_domain.intervals_[i].start < interval.start) {
485 result.intervals_.push_back({min_point, max_point});
486 started = false;
487 }
488
489 // Find the two extreme points in interval \inter implied_domain.
490 // Always stop the loop at the first interval with and end strictly greater
491 // that interval.end.
492 for (; i < implied_domain.intervals_.size(); ++i) {
493 const ClosedInterval current = implied_domain.intervals_[i];
494 if (current.end >= interval.start && current.start <= interval.end) {
495 // Current and interval have a non-empty intersection.
496 const int64 inter_max = std::min(interval.end, current.end);
497 if (!started) {
498 started = true;
499 min_point = std::max(interval.start, current.start);
500 max_point = inter_max;
501 } else {
502 // No need to update the min_point here, and the new inter_max must
503 // necessarily be > old one.
504 DCHECK_GE(inter_max, max_point);
505 max_point = inter_max;
506 }
507 }
508 if (current.end > interval.end) break;
509 }
510 if (i == implied_domain.intervals_.size()) break;
511 }
512 if (started) {
513 result.intervals_.push_back({min_point, max_point});
514 }
515 DCHECK(IntervalsAreSortedAndNonAdjacent(result.intervals_));
516 return result;
517}
518
519std::vector<int64> Domain::FlattenedIntervals() const {
520 std::vector<int64> result;
521 for (const ClosedInterval& interval : intervals_) {
522 result.push_back(interval.start);
523 result.push_back(interval.end);
524 }
525 return result;
526}
527
528bool Domain::operator<(const Domain& other) const {
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) {
533 const ClosedInterval& i1 = d1[i];
534 const ClosedInterval& i2 = d2[i];
535 if (i1.start < i2.start) return true;
536 if (i1.start > i2.start) return false;
537 if (i1.end < i2.end) return true;
538 if (i1.end > i2.end) return false;
539 }
540 return d1.size() < d2.size();
541}
542
543std::string Domain::ToString() const { return IntervalsAsString(intervals_); }
544
545int64 SumOfKMinValueInDomain(const Domain& domain, int k) {
546 int64 current_sum = 0.0;
547 int current_index = 0;
548 for (const ClosedInterval interval : domain) {
549 if (current_index >= k) break;
550 for (int v(interval.start); v <= interval.end; ++v) {
551 if (current_index >= k) break;
552 current_index++;
553 current_sum += v;
554 }
555 }
556 return current_sum;
557}
558
559int64 SumOfKMaxValueInDomain(const Domain& domain, int k) {
560 return -SumOfKMinValueInDomain(domain.Negation(), k);
561}
562
564
566 const std::vector<int64>& starts, const std::vector<int64>& ends) {
567 InsertIntervals(starts, ends);
568}
569
571 const std::vector<int>& starts, const std::vector<int>& ends) {
572 InsertIntervals(starts, ends);
573}
574
576 const std::vector<ClosedInterval>& intervals) {
577 for (ClosedInterval interval : intervals) {
578 InsertInterval(interval.start, interval.end);
579 }
580}
581
584 SortedDisjointIntervalList interval_list;
585 int64 next_start = start;
586 for (auto it = FirstIntervalGreaterOrEqual(start); it != this->end(); ++it) {
587 const ClosedInterval& interval = *it;
588 const int64 next_end = CapSub(interval.start, 1);
589 if (next_end > end) break;
590 if (next_start <= next_end) {
591 interval_list.InsertInterval(next_start, next_end);
592 }
593 next_start = CapAdd(interval.end, 1);
594 }
595 if (next_start <= end) {
596 interval_list.InsertInterval(next_start, end);
597 }
598 return interval_list;
599}
600
602 int64 start, int64 end) {
603 // start > end could mean an empty interval, but we prefer to LOG(DFATAL)
604 // anyway. Really, the user should never give us that.
605 if (start > end) {
606 LOG(DFATAL) << "Invalid interval: " << ClosedInterval({start, end});
607 return intervals_.end();
608 }
609
610 auto result = intervals_.insert({start, end});
611 if (!result.second) return result.first; // Duplicate: exit immediately.
612
613 // TODO(user): tune the algorithm below if it proves to be a bottleneck.
614 // For example, one could try to avoid an insertion if it's not needed
615 // (when the interval merges with a single existing interval or is fully
616 // contained by one).
617
618 // Iterate over the previous iterators whose end is after (or almost at) our
619 // start. After this, "it1" will point to the first interval that needs to be
620 // merged with the current interval (possibly pointing to the current interval
621 // itself, if no "earlier" interval should be merged).
622 auto it1 = result.first;
623 if (start == kint64min) { // Catch underflows
624 it1 = intervals_.begin();
625 } else {
626 const int64 before_start = start - 1;
627 while (it1 != intervals_.begin()) {
628 auto prev_it = it1;
629 --prev_it;
630 if (prev_it->end < before_start) break;
631 it1 = prev_it;
632 }
633 }
634
635 // Ditto, on the other side: "it2" will point to the interval *after* the last
636 // one that should be merged with the current interval.
637 auto it2 = result.first;
638 if (end == kint64max) {
639 it2 = intervals_.end();
640 } else {
641 const int64 after_end = end + 1;
642 do {
643 ++it2;
644 } while (it2 != intervals_.end() && it2->start <= after_end);
645 }
646
647 // [it1..it2) is the range (inclusive on it1, exclusive on it2) of intervals
648 // that should be merged together. We'll set it3 = it2-1 and erase [it1..it3)
649 // and set *it3 to the merged interval.
650 auto it3 = it2;
651 it3--;
652 if (it1 == it3) return it3; // Nothing was merged.
653 const int64 new_start = std::min(it1->start, start);
654 const int64 new_end = std::max(it3->end, end);
655 auto it = intervals_.erase(it1, it3);
656 // HACK(user): set iterators point to *const* values. Which is expected,
657 // because if one alters a set element's value, then it collapses the set
658 // property! But in this very special case, we know that we can just overwrite
659 // it->start, so we do it.
660 const_cast<ClosedInterval*>(&(*it))->start = new_start;
661 const_cast<ClosedInterval*>(&(*it))->end = new_end;
662 return it;
663}
664
666 int64 value, int64* newly_covered) {
667 auto it = intervals_.upper_bound({value, kint64max});
668 auto it_prev = it;
669
670 // No interval containing or adjacent to "value" on the left (i.e. below).
671 if (it != begin()) {
672 --it_prev;
673 }
674 if (it == begin() || ((value != kint64min) && it_prev->end < value - 1)) {
675 *newly_covered = value;
676 if (it == end() || it->start != value + 1) {
677 // No interval adjacent to "value" on the right: insert a singleton.
678 return intervals_.insert(it, {value, value});
679 } else {
680 // There is an interval adjacent to "value" on the right. Extend it by
681 // one. Note that we already know that there won't be a merge with another
682 // interval on the left, since there were no interval adjacent to "value"
683 // on the left.
684 DCHECK_EQ(it->start, value + 1);
685 const_cast<ClosedInterval*>(&(*it))->start = value;
686 return it;
687 }
688 }
689
690 // At this point, "it_prev" points to an interval containing or adjacent to
691 // "value" on the left: grow it by one, and if it now touches the next
692 // interval, merge with it.
693 CHECK_NE(kint64max, it_prev->end) << "Cannot grow right by one: the interval "
694 "that would grow already ends at "
695 "kint64max";
696 *newly_covered = it_prev->end + 1;
697 if (it != end() && it_prev->end + 2 == it->start) {
698 // We need to merge it_prev with 'it'.
699 const_cast<ClosedInterval*>(&(*it_prev))->end = it->end;
700 intervals_.erase(it);
701 } else {
702 const_cast<ClosedInterval*>(&(*it_prev))->end = it_prev->end + 1;
703 }
704 return it_prev;
705}
706
707template <class T>
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]);
712}
713
715 const std::vector<int64>& starts, const std::vector<int64>& ends) {
716 InsertAll(starts, ends);
717}
718
719void SortedDisjointIntervalList::InsertIntervals(const std::vector<int>& starts,
720 const std::vector<int>& ends) {
721 // TODO(user): treat kint32min and kint32max as their kint64 variants.
722 InsertAll(starts, ends);
723}
724
727 const auto it = intervals_.upper_bound({value, kint64max});
728 if (it == begin()) return it;
729 auto it_prev = it;
730 it_prev--;
731 DCHECK_LE(it_prev->start, value);
732 return it_prev->end >= value ? it_prev : it;
733}
734
737 const auto it = intervals_.upper_bound({value, kint64max});
738 if (it == begin()) return end();
739 auto it_prev = it;
740 it_prev--;
741 return it_prev;
742}
743
745 std::string str;
746 for (const ClosedInterval& interval : intervals_) {
747 str += interval.DebugString();
748 }
749 return str;
750}
751
752} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define CHECK_NE(val1, val2)
Definition: base/logging.h:698
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
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}.
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 ...
SortedDisjointIntervalList BuildComplementOnInterval(int64 start, int64 end)
Builds the complement of the interval list on the interval [start, end].
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.
int64 value
static const int64 kint64max
int64_t int64
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:
IntervalVar * interval
Definition: resource.cc:98
Represents a closed interval [start, end].