Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
sorted_interval_list.h
Go to the documentation of this file.
1// Copyright 2010-2025 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
14#ifndef OR_TOOLS_UTIL_SORTED_INTERVAL_LIST_H_
15#define OR_TOOLS_UTIL_SORTED_INTERVAL_LIST_H_
16
17#include <cstddef>
18#include <cstdint>
19#include <iterator>
20#include <ostream>
21#include <set>
22#include <string>
23#include <utility>
24#include <vector>
25
26#include "absl/container/inlined_vector.h"
27#include "absl/types/span.h"
29
30namespace operations_research {
31
36#if !defined(SWIG)
52 class Iterator;
53#endif // !defined(SWIG)
54
56 explicit ClosedInterval(int64_t v) : start(v), end(v) {}
57 ClosedInterval(int64_t s, int64_t e) : start(s), end(e) {
58 DLOG_IF(DFATAL, s > e) << "Invalid ClosedInterval(" << s << ", " << e
59 << ")";
60 }
61
62 std::string DebugString() const;
63 constexpr bool operator==(const ClosedInterval& other) const {
64 return start == other.start && end == other.end;
65 }
66
67 // Because we mainly manipulate vector of disjoint intervals, we only need to
68 // sort by the start. We do not care about the order in which interval with
69 // the same start appear since they will always be merged into one interval.
70 constexpr bool operator<(const ClosedInterval& other) const {
71 return start < other.start;
72 }
73
74 template <typename H>
75 friend H AbslHashValue(H h, const ClosedInterval& interval) {
76 return H::combine(std::move(h), interval.start, interval.end);
77 }
78
79 int64_t start = 0; // Inclusive.
80 int64_t end = 0; // Inclusive.
81};
82
83#if !defined(SWIG)
86#endif // !defined(SWIG)
87
88std::ostream& operator<<(std::ostream& out, const ClosedInterval& interval);
89std::ostream& operator<<(std::ostream& out,
90 const std::vector<ClosedInterval>& intervals);
91
101 absl::Span<const ClosedInterval> intervals);
102
113class Domain {
114 public:
117
118#if !defined(SWIG)
120 Domain(const Domain& other) : intervals_(other.intervals_) {}
121
123 Domain& operator=(const Domain& other) {
124 intervals_ = other.intervals_;
125 return *this;
126 }
127
129 Domain(Domain&& other) noexcept : intervals_(std::move(other.intervals_)) {}
130
132 Domain& operator=(Domain&& other) noexcept {
133 intervals_ = std::move(other.intervals_);
134 return *this;
135 }
136#endif // !defined(SWIG)
137
139 explicit Domain(int64_t value);
140
145 Domain(int64_t left, int64_t right);
146
150 static Domain AllValues();
151
156 static Domain FromValues(std::vector<int64_t> values);
157
164 static Domain FromIntervals(absl::Span<const ClosedInterval> intervals);
165
174 absl::Span<const int64_t> flat_intervals);
175
188 const std::vector<std::vector<int64_t> >& intervals);
189
198 static Domain FromFlatIntervals(const std::vector<int64_t>& flat_intervals);
199
207 std::vector<int64_t> FlattenedIntervals() const;
208
209#if !defined(SWIG)
218 public:
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()) {}
224
225 int64_t operator*() const { return value_; }
226
227 void operator++() {
228 if (value_ == it_->end) {
229 ++it_;
230 if (it_ != end_) value_ = it_->start;
231 } else {
232 ++value_;
233 }
234 }
235
237 absl::InlinedVector<ClosedInterval, 1>::const_iterator end) const {
238 return it_ != end;
239 }
240
241 private:
242 int64_t value_;
243 absl::InlinedVector<ClosedInterval, 1>::const_iterator it_;
244 absl::InlinedVector<ClosedInterval, 1>::const_iterator end_;
245 };
248 absl::InlinedVector<ClosedInterval, 1>::const_iterator end() const {
249 return intervals.end();
250 }
251 const absl::InlinedVector<ClosedInterval, 1>& intervals;
252 };
255 absl::InlinedVector<ClosedInterval, 1>::const_iterator end() const {
256 return intervals.end();
257 }
258 absl::InlinedVector<ClosedInterval, 1> intervals;
259 };
260 DomainIteratorBeginEnd Values() const& { return {this->intervals_}; }
262 return {std::move(this->intervals_)};
263 }
264#endif // !defined(SWIG)
265
269 bool IsEmpty() const;
270
274 int64_t Size() const;
275
280 bool HasTwoValues() 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;
286 }
287 return false;
288 }
289
294 int64_t Min() const;
295
300 int64_t Max() const;
301
305 int64_t SmallestValue() const;
306
311 int64_t ClosestValue(int64_t wanted) const;
312
317 int64_t ValueAtOrBefore(int64_t input) const;
318 int64_t ValueAtOrAfter(int64_t input) const;
319
324 Domain PartAroundZero() const;
325
330 bool IsFixed() const;
331
337 int64_t FixedValue() const;
338
342 bool Contains(int64_t value) const;
343
347 int64_t Distance(int64_t value) const;
348
352 bool IsIncludedIn(const Domain& domain) const;
353
357 Domain Complement() const;
358
365 Domain Negation() const;
366
370 Domain IntersectionWith(const Domain& domain) const;
371
375 Domain UnionWith(const Domain& domain) const;
376
380 Domain AdditionWith(const Domain& domain) const;
381
393 Domain MultiplicationBy(int64_t coeff, bool* exact = nullptr) const;
394
399
412 Domain ContinuousMultiplicationBy(int64_t coeff) const;
413
426 Domain ContinuousMultiplicationBy(const Domain& domain) const;
427
433 Domain DivisionBy(int64_t coeff) const;
434
440 Domain InverseMultiplicationBy(int64_t coeff) const;
441
450 Domain PositiveModuloBySuperset(const Domain& modulo) const;
451
458 Domain PositiveDivisionBySuperset(const Domain& divisor) const;
459
463 Domain SquareSuperset() const;
464
468 Domain QuadraticSuperset(int64_t a, int64_t b, int64_t c, int64_t d) const;
469
490 Domain SimplifyUsingImpliedDomain(const Domain& implied_domain) const;
491
495 std::string ToString() const;
496
500 bool operator<(const Domain& other) const;
501
502 bool operator==(const Domain& other) const {
503 return intervals_ == other.intervals_;
504 }
505
506 bool operator!=(const Domain& other) const {
507 return intervals_ != other.intervals_;
508 }
509
510 template <typename H>
511 friend H AbslHashValue(H h, const Domain& domain) {
512 return H::combine(std::move(h), domain.intervals_);
513 }
514
520 int NumIntervals() const { return intervals_.size(); }
521 ClosedInterval front() const { return intervals_.front(); }
522 ClosedInterval back() const { return intervals_.back(); }
523 ClosedInterval operator[](int i) const { return intervals_[i]; }
524 absl::InlinedVector<ClosedInterval, 1>::const_iterator begin() const {
525 return intervals_.begin();
526 }
527 absl::InlinedVector<ClosedInterval, 1>::const_iterator end() const {
528 return intervals_.end();
529 }
530
531 private:
532 // Same as Negation() but modify the current domain.
533 void NegateInPlace();
534
535 // Some functions relax the domain when its "complexity" (i.e NumIntervals())
536 // become too large.
537 static constexpr int kDomainComplexityLimit = 100;
538
539 // Invariant: will always satisfy IntervalsAreSortedAndNonAdjacent().
540 //
541 // Note that we use InlinedVector for the common case of single internal
542 // interval. This provide a good performance boost when working with a
543 // std::vector<Domain>.
544 absl::InlinedVector<ClosedInterval, 1> intervals_;
545};
546
547std::ostream& operator<<(std::ostream& out, const Domain& domain);
548
549// Returns the sum of smallest k values in the domain.
550int64_t SumOfKMinValueInDomain(const Domain& domain, int k);
551
552// Returns the sum of largest k values in the domain.
553int64_t SumOfKMaxValueInDomain(const Domain& domain, int k);
554
562// TODO(user): Templatize the class on the type of the bounds.
564 public:
566 bool operator()(const ClosedInterval& a, const ClosedInterval& b) const {
567 return a.start != b.start ? a.start < b.start : a.end < b.end;
568 }
569 };
570 typedef std::set<ClosedInterval, IntervalComparator> IntervalSet;
571 typedef IntervalSet::iterator Iterator;
572 typedef IntervalSet::const_iterator ConstIterator;
573
576 const std::vector<ClosedInterval>& intervals);
577
583 // TODO(user): Explain why we favored this API to the more natural
584 // input std::vector<ClosedInterval> or std::vector<std::pair<int, int>>.
585 SortedDisjointIntervalList(const std::vector<int64_t>& starts,
586 const std::vector<int64_t>& ends);
587 SortedDisjointIntervalList(const std::vector<int>& starts,
588 const std::vector<int>& ends);
589
594 int64_t end);
595
605 Iterator InsertInterval(int64_t start, int64_t end);
606
616 Iterator GrowRightByOne(int64_t value, int64_t* newly_covered);
617
624 void InsertIntervals(const std::vector<int64_t>& starts,
625 const std::vector<int64_t>& ends);
626 void InsertIntervals(const std::vector<int>& starts,
627 const std::vector<int>& ends);
628
632 int NumIntervals() const { return intervals_.size(); }
633
642 Iterator FirstIntervalGreaterOrEqual(int64_t value) const;
643 Iterator LastIntervalLessOrEqual(int64_t value) const;
644
645 std::string DebugString() const;
646
657 ConstIterator begin() const { return intervals_.begin(); }
658 ConstIterator end() const { return intervals_.end(); }
659
663 const ClosedInterval& last() const { return *intervals_.rbegin(); }
664
665 void clear() { intervals_.clear(); }
667 intervals_.swap(other.intervals_);
668 }
669
670 private:
671 template <class T>
672 void InsertAll(const std::vector<T>& starts, const std::vector<T>& ends);
673
674 IntervalSet intervals_;
675};
676
677// Implementation details.
678
679#if !defined(SWIG)
681 public:
682 using value_type = int64_t;
683 using difference_type = std::ptrdiff_t;
684
685 Iterator(const Iterator&) = default;
686
687 int64_t operator*() const { return static_cast<int64_t>(current_); }
688
690 ++current_;
691 return *this;
692 }
693 void operator++(int) { ++current_; }
694
695 bool operator==(Iterator other) const { return current_ == other.current_; }
696 bool operator!=(Iterator other) const { return current_ != other.current_; }
697
698 Iterator& operator=(const Iterator&) = default;
699
700 static Iterator Begin(ClosedInterval interval) {
701 AssertNotFullInt64Range(interval);
702 return Iterator(static_cast<uint64_t>(interval.start));
703 }
704 static Iterator End(ClosedInterval interval) {
705 AssertNotFullInt64Range(interval);
706 return Iterator(static_cast<uint64_t>(interval.end) + 1);
707 }
708
709 private:
710 explicit Iterator(uint64_t current) : current_(current) {}
711
712 // Triggers a DCHECK-failure when `interval` represents the full int64_t
713 // range.
714 static void AssertNotFullInt64Range(ClosedInterval interval) {
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.";
718 }
719
720 // Implementation note: In C++, integer overflow is well-defined only for
721 // unsigned integers. To avoid any compilation issues or UBSan failures, the
722 // iterator uses uint64_t internally and relies on the fact that since C++20
723 // unsigned->signed conversion is well-defined for all values using modulo
724 // arithmetic.
725 uint64_t current_;
726};
727#if __cplusplus >= 202002L
728static_assert(std::input_iterator<ClosedInterval::Iterator>);
729#endif
730// begin()/end() are required for iteration over ClosedInterval in a range for
731// loop.
736 return ClosedInterval::Iterator::End(interval);
737}
738#endif // !defined(SWIG)
739
740} // namespace operations_research
741
742#endif // OR_TOOLS_UTIL_SORTED_INTERVAL_LIST_H_
static Iterator Begin(ClosedInterval interval)
static Iterator End(ClosedInterval interval)
Iterator & operator=(const Iterator &)=default
DomainIterator(const absl::InlinedVector< ClosedInterval, 1 > &intervals)
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 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)
Domain()
By default, Domain will be empty.
Domain DivisionBy(int64_t coeff) const
int64_t Distance(int64_t value) const
Domain & operator=(const Domain &other)
Copy operator (mandatory as we define the move operator).
static Domain FromFlatSpanOfIntervals(absl::Span< const int64_t > flat_intervals)
absl::InlinedVector< ClosedInterval, 1 >::const_iterator end() const
Domain PositiveDivisionBySuperset(const Domain &divisor) const
absl::InlinedVector< ClosedInterval, 1 >::const_iterator begin() const
Domain UnionWith(const Domain &domain) const
bool operator==(const Domain &other) const
Domain & operator=(Domain &&other) noexcept
Move operator.
ClosedInterval operator[](int i) const
Domain InverseMultiplicationBy(int64_t coeff) const
int64_t ValueAtOrBefore(int64_t input) const
bool operator!=(const Domain &other) const
int64_t ClosestValue(int64_t wanted) const
void InsertIntervals(const std::vector< int64_t > &starts, const std::vector< int64_t > &ends)
Iterator InsertInterval(int64_t start, int64_t end)
SortedDisjointIntervalList BuildComplementOnInterval(int64_t start, int64_t end)
void swap(SortedDisjointIntervalList &other)
std::set< ClosedInterval, IntervalComparator > IntervalSet
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)
Definition model.h:51
constexpr bool operator==(const ClosedInterval &other) const
constexpr bool operator<(const ClosedInterval &other) const
friend H AbslHashValue(H h, const ClosedInterval &interval)
absl::InlinedVector< ClosedInterval, 1 >::const_iterator end() const
absl::InlinedVector< ClosedInterval, 1 >::const_iterator end() const
const absl::InlinedVector< ClosedInterval, 1 > & intervals
bool operator()(const ClosedInterval &a, const ClosedInterval &b) const