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"
27 #include "ortools/base/logging.h"
29 
30 namespace operations_research {
31 
32 std::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 
51 namespace {
52 
53 template <class Intervals>
54 std::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.
65 void 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.
87 int64 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 
94 int64 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 
101 std::ostream& operator<<(std::ostream& out, const ClosedInterval& interval) {
102  return out << interval.DebugString();
103 }
104 
105 std::ostream& operator<<(std::ostream& out,
106  const std::vector<ClosedInterval>& intervals) {
107  return out << IntervalsAsString(intervals);
108 }
109 
110 std::ostream& operator<<(std::ostream& out, const Domain& domain) {
111  return out << IntervalsAsString(domain);
112 }
113 
114 Domain::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.
122 namespace {
123 inline 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 
138 Domain 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 
151 Domain 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 
159 Domain 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 
171 Domain 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 
191 bool Domain::IsEmpty() const { return intervals_.empty(); }
192 
193 bool Domain::IsFixed() const { return Min() == Max(); }
194 
196  int64 size = 0;
197  for (const ClosedInterval interval : intervals_) {
199  size, operations_research::CapSub(interval.end, interval.start));
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 
233 bool 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 
268 void 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 
283 Domain Domain::IntersectionWith(const Domain& domain) const {
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 
322 Domain 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.
333 Domain 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 
362 Domain 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.
471 Domain Domain::SimplifyUsingImpliedDomain(const Domain& implied_domain) const {
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 
519 std::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 
528 bool 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 
543 std::string Domain::ToString() const { return IntervalsAsString(intervals_); }
544 
545 int64 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 
559 int64 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 
707 template <class T>
708 void 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 
719 void 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.
absl::InlinedVector< ClosedInterval, 1 >::const_iterator end() const
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.
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 CapSub(int64 x, int64 y)
int64 SumOfKMinValueInDomain(const Domain &domain, int k)
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
int64 FloorRatio(int64 value, int64 positive_coeff)
int64 CapAdd(int64 x, int64 y)
int64 CapProd(int64 x, int64 y)
int64 SumOfKMaxValueInDomain(const Domain &domain, int k)
int64 CeilRatio(int64 value, int64 positive_coeff)
bool IntervalsAreSortedAndNonAdjacent(absl::Span< const ClosedInterval > intervals)
Returns true iff we have:
IntervalVar * interval
Definition: resource.cc:98
Represents a closed interval [start, end].