C++ Reference

C++ Reference: CP-SAT

sorted_interval_list.h
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
14#ifndef OR_TOOLS_UTIL_SORTED_INTERVAL_LIST_H_
15#define OR_TOOLS_UTIL_SORTED_INTERVAL_LIST_H_
16
17#include <iterator>
18#include <set>
19#include <string>
20#include <utility>
21#include <vector>
22
23#include "absl/container/inlined_vector.h"
24#include "absl/types/span.h"
25#include "ortools/base/integral_types.h"
26#include "ortools/base/logging.h"
27
28namespace operations_research {
29
35 ClosedInterval(int64 s, int64 e) : start(s), end(e) {
36 DLOG_IF(DFATAL, s > e) << "Invalid ClosedInterval(" << s << ", " << e
37 << ")";
38 }
39
40 std::string DebugString() const;
41 bool operator==(const ClosedInterval& other) const {
42 return start == other.start && end == other.end;
43 }
44
45 // Because we mainly manipulate vector of disjoint intervals, we only need to
46 // sort by the start. We do not care about the order in which interval with
47 // the same start appear since they will always be merged into one interval.
48 bool operator<(const ClosedInterval& other) const {
49 return start < other.start;
50 }
51
52 int64 start = 0; // Inclusive.
53 int64 end = 0; // Inclusive.
54};
55
56std::ostream& operator<<(std::ostream& out, const ClosedInterval& interval);
57std::ostream& operator<<(std::ostream& out,
58 const std::vector<ClosedInterval>& intervals);
59
69 absl::Span<const ClosedInterval> intervals);
70
81class Domain {
82 public:
84 Domain() {}
85
86#if !defined(SWIG)
88 Domain(const Domain& other) : intervals_(other.intervals_) {}
89
91 Domain& operator=(const Domain& other) {
92 intervals_ = other.intervals_;
93 return *this;
94 }
95
97 Domain(Domain&& other) : intervals_(std::move(other.intervals_)) {}
98
101 intervals_ = std::move(other.intervals_);
102 return *this;
103 }
104#endif // !defined(SWIG)
105
107 explicit Domain(int64 value);
108
113 Domain(int64 left, int64 right);
114
119
124 static Domain FromValues(std::vector<int64> values);
125
129 static Domain FromIntervals(absl::Span<const ClosedInterval> intervals);
130
135 static Domain FromFlatSpanOfIntervals(absl::Span<const int64> flat_intervals);
136
143 const std::vector<std::vector<int64> >& intervals);
144
150 static Domain FromFlatIntervals(const std::vector<int64>& flat_intervals);
151
159 std::vector<int64> FlattenedIntervals() const;
160
164 bool IsEmpty() const;
165
169 int64 Size() const;
170
175 int64 Min() const;
176
181 int64 Max() const;
182
187 bool IsFixed() const;
188
194 int64 FixedValue() const;
195
199 bool Contains(int64 value) const;
200
204 bool IsIncludedIn(const Domain& domain) const;
205
210
218
222 Domain IntersectionWith(const Domain& domain) const;
223
227 Domain UnionWith(const Domain& domain) const;
228
232 Domain AdditionWith(const Domain& domain) const;
233
245 Domain MultiplicationBy(int64 coeff, bool* exact = nullptr) const;
246
251
265
279
285 Domain DivisionBy(int64 coeff) const;
286
292 Domain InverseMultiplicationBy(const int64 coeff) const;
293
314 Domain SimplifyUsingImpliedDomain(const Domain& implied_domain) const;
315
319 std::string ToString() const;
320
324 bool operator<(const Domain& other) const;
325
326 bool operator==(const Domain& other) const {
327 return intervals_ == other.intervals_;
328 }
329
330 bool operator!=(const Domain& other) const {
331 return intervals_ != other.intervals_;
332 }
333
339 int NumIntervals() const { return intervals_.size(); }
340 ClosedInterval front() const { return intervals_.front(); }
341 ClosedInterval back() const { return intervals_.back(); }
342 ClosedInterval operator[](int i) const { return intervals_[i]; }
343 absl::InlinedVector<ClosedInterval, 1>::const_iterator begin() const {
344 return intervals_.begin();
345 }
346 absl::InlinedVector<ClosedInterval, 1>::const_iterator end() const {
347 return intervals_.end();
348 }
349
350 // Deprecated.
351 //
352 // TODO(user): remove, this makes a copy and is of a different type that our
353 // internal InlinedVector() anyway.
354 std::vector<ClosedInterval> intervals() const {
355 return {intervals_.begin(), intervals_.end()};
356 }
357
358 private:
359 // Same as Negation() but modify the current domain.
360 void NegateInPlace();
361
362 // Some functions relax the domain when its "complexity" (i.e NumIntervals())
363 // become too large.
364 static constexpr int kDomainComplexityLimit = 100;
365
366 // Invariant: will always satisfy IntervalsAreSortedAndNonAdjacent().
367 //
368 // Note that we use InlinedVector for the common case of single internal
369 // interval. This provide a good performance boost when working with a
370 // std::vector<Domain>.
371 absl::InlinedVector<ClosedInterval, 1> intervals_;
372};
373
374std::ostream& operator<<(std::ostream& out, const Domain& domain);
375
376// Returns the sum of smallest k values in the domain.
377int64 SumOfKMinValueInDomain(const Domain& domain, int k);
378
379// Returns the sum of largest k values in the domain.
380int64 SumOfKMaxValueInDomain(const Domain& domain, int k);
381
389// TODO(user): Templatize the class on the type of the bounds.
391 public:
393 bool operator()(const ClosedInterval& a, const ClosedInterval& b) const {
394 return a.start != b.start ? a.start < b.start : a.end < b.end;
395 }
396 };
397 typedef std::set<ClosedInterval, IntervalComparator> IntervalSet;
398 typedef IntervalSet::iterator Iterator;
399 typedef IntervalSet::const_iterator ConstIterator;
400
403 const std::vector<ClosedInterval>& intervals);
404
410 // TODO(user): Explain why we favored this API to the more natural
411 // input std::vector<ClosedInterval> or std::vector<std::pair<int, int>>.
412 SortedDisjointIntervalList(const std::vector<int64>& starts,
413 const std::vector<int64>& ends);
414 SortedDisjointIntervalList(const std::vector<int>& starts,
415 const std::vector<int>& ends);
416
421
431 Iterator InsertInterval(int64 start, int64 end);
432
442 Iterator GrowRightByOne(int64 value, int64* newly_covered);
443
450 void InsertIntervals(const std::vector<int64>& starts,
451 const std::vector<int64>& ends);
452 void InsertIntervals(const std::vector<int>& starts,
453 const std::vector<int>& ends);
454
458 int NumIntervals() const { return intervals_.size(); }
459
470
471 std::string DebugString() const;
472
483 ConstIterator begin() const { return intervals_.begin(); }
484 ConstIterator end() const { return intervals_.end(); }
485
489 const ClosedInterval& last() const { return *intervals_.rbegin(); }
490
491 void clear() { intervals_.clear(); }
493 intervals_.swap(other.intervals_);
494 }
495
496 private:
497 template <class T>
498 void InsertAll(const std::vector<T>& starts, const std::vector<T>& ends);
499
500 IntervalSet intervals_;
501};
502
503} // namespace operations_research
504
505#endif // OR_TOOLS_UTIL_SORTED_INTERVAL_LIST_H_
We call domain any subset of Int64 = [kint64min, kint64max].
Domain(Domain &&other)
Move constructor.
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(int64 left, int64 right)
Constructor for the common case of a single interval [left, right].
Domain MultiplicationBy(int64 coeff, bool *exact=nullptr) const
Returns {x ∈ Int64, ∃ e ∈ D, x = e * coeff}.
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}.
Domain ContinuousMultiplicationBy(const Domain &domain) const
Returns a superset of MultiplicationBy() to avoid the explosion in the representation size.
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}.
static Domain FromIntervals(absl::Span< const ClosedInterval > intervals)
Creates a domain from the union of an unsorted list of intervals.
ClosedInterval front() const
int64 Min() const
Returns the min value of the domain.
static Domain AllValues()
Returns the full domain Int64.
bool operator!=(const Domain &other) const
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.
ClosedInterval operator[](int i) const
int64 Max() const
Returns the max value of the domain.
static Domain FromValues(std::vector< int64 > values)
Creates a domain from the union of an unsorted list of integer values.
static Domain FromVectorIntervals(const std::vector< std::vector< int64 > > &intervals)
This method is available in Python, Java and .NET.
static Domain FromFlatSpanOfIntervals(absl::Span< const int64 > flat_intervals)
Same as FromIntervals() for a flattened representation (start, end, start, end, .....
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.
Domain & operator=(const Domain &other)
Copy operator (mandatory as we define the move operator).
std::vector< ClosedInterval > intervals() const
bool operator==(const Domain &other) const
Domain()
By default, Domain will be empty.
Domain(const Domain &other)
Copy constructor (mandatory as we define the move constructor).
Domain(int64 value)
Constructor for the common case of a singleton domain.
bool Contains(int64 value) const
Returns true iff value is in Domain.
static Domain FromFlatIntervals(const std::vector< int64 > &flat_intervals)
This method is available in Python, Java and .NET.
Domain RelaxIfTooComplex() const
If NumIntervals() is too large, this return a superset of the domain.
absl::InlinedVector< ClosedInterval, 1 >::const_iterator end() const
Domain & operator=(Domain &&other)
Move operator.
absl::InlinedVector< ClosedInterval, 1 >::const_iterator begin() const
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 GrowRightByOne(int64 value, int64 *newly_covered)
If value is in an interval, increase its end by one, otherwise insert the interval [value,...
Iterator FirstIntervalGreaterOrEqual(int64 value) const
Returns an iterator to either:
SortedDisjointIntervalList(const std::vector< int64 > &starts, const std::vector< int64 > &ends)
Creates a SortedDisjointIntervalList and fills it with intervals [starts[i]..ends[i]].
int NumIntervals() const
Returns the number of disjoint intervals in the list.
SortedDisjointIntervalList BuildComplementOnInterval(int64 start, int64 end)
Builds the complement of the interval list on the interval [start, end].
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
void swap(SortedDisjointIntervalList &other)
SortedDisjointIntervalList(const std::vector< int > &starts, const std::vector< int > &ends)
std::set< ClosedInterval, IntervalComparator > IntervalSet
ConstIterator begin() const
Const iterators for SortedDisjoinIntervalList.
SortedDisjointIntervalList(const std::vector< ClosedInterval > &intervals)
const ClosedInterval & last() const
Returns a const& to the last interval.
void InsertIntervals(const std::vector< int > &starts, const std::vector< int > &ends)
int64 SumOfKMinValueInDomain(const Domain &domain, int k)
std::ostream & operator<<(std::ostream &out, const ClosedInterval &interval)
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].
bool operator==(const ClosedInterval &other) const
bool operator<(const ClosedInterval &other) const
bool operator()(const ClosedInterval &a, const ClosedInterval &b) const