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 
28 namespace 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 
56 std::ostream& operator<<(std::ostream& out, const ClosedInterval& interval);
57 std::ostream& operator<<(std::ostream& out,
58  const std::vector<ClosedInterval>& intervals);
59 
69  absl::Span<const ClosedInterval> intervals);
70 
81 class 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 
100  Domain& operator=(Domain&& other) {
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 
118  static Domain AllValues();
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 
217  Domain Negation() const;
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 
264  Domain ContinuousMultiplicationBy(int64 coeff) const;
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 
374 std::ostream& operator<<(std::ostream& out, const Domain& domain);
375 
376 // Returns the sum of smallest k values in the domain.
377 int64 SumOfKMinValueInDomain(const Domain& domain, int k);
378 
379 // Returns the sum of largest k values in the domain.
380 int64 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 
469  Iterator LastIntervalLessOrEqual(int64 value) const;
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}.
Domain & operator=(Domain &&other)
Move operator.
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}.
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.
bool IsEmpty() const
Returns true if this is the empty set.
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).
std::vector< int64 > FlattenedIntervals() const
This method returns the flattened list of interval bounds of the domain.
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 begin() const
Domain & operator=(const Domain &other)
Copy operator (mandatory as we define the move operator).
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,...
const ClosedInterval & last() const
Returns a const& to the last interval.
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)
void InsertIntervals(const std::vector< int > &starts, const std::vector< int > &ends)
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:
int64 SumOfKMinValueInDomain(const Domain &domain, int k)
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