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)
87  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 
242  Domain MultiplicationBy(int64 coeff, bool* exact = nullptr) const;
243 
248 
261  Domain ContinuousMultiplicationBy(int64 coeff) const;
262 
276 
282  Domain DivisionBy(int64 coeff) const;
283 
289  Domain InverseMultiplicationBy(const int64 coeff) const;
290 
311  Domain SimplifyUsingImpliedDomain(const Domain& implied_domain) const;
312 
316  std::string ToString() const;
317 
321  bool operator<(const Domain& other) const;
322 
323  bool operator==(const Domain& other) const {
324  return intervals_ == other.intervals_;
325  }
326 
327  bool operator!=(const Domain& other) const {
328  return intervals_ != other.intervals_;
329  }
330 
336  int NumIntervals() const { return intervals_.size(); }
337  ClosedInterval front() const { return intervals_.front(); }
338  ClosedInterval back() const { return intervals_.back(); }
339  ClosedInterval operator[](int i) const { return intervals_[i]; }
340  absl::InlinedVector<ClosedInterval, 1>::const_iterator begin() const {
341  return intervals_.begin();
342  }
343  absl::InlinedVector<ClosedInterval, 1>::const_iterator end() const {
344  return intervals_.end();
345  }
346 
347  // Deprecated.
348  //
349  // TODO(user): remove, this makes a copy and is of a different type that our
350  // internal InlinedVector() anyway.
351  std::vector<ClosedInterval> intervals() const {
352  return {intervals_.begin(), intervals_.end()};
353  }
354 
355  private:
356  // Same as Negation() but modify the current domain.
357  void NegateInPlace();
358 
359  // Some functions relax the domain when its "complexity" (i.e NumIntervals())
360  // become too large.
361  static constexpr int kDomainComplexityLimit = 100;
362 
363  // Invariant: will always satisfy IntervalsAreSortedAndNonAdjacent().
364  //
365  // Note that we use InlinedVector for the common case of single internal
366  // interval. This provide a good performance boost when working with a
367  // std::vector<Domain>.
368  absl::InlinedVector<ClosedInterval, 1> intervals_;
369 };
370 
371 std::ostream& operator<<(std::ostream& out, const Domain& domain);
372 
373 // Returns the sum of smallest k values in the domain.
374 int64 SumOfKMinValueInDomain(const Domain& domain, int k);
375 
376 // Returns the sum of largest k values in the domain.
377 int64 SumOfKMaxValueInDomain(const Domain& domain, int k);
378 
386 // TODO(user): Templatize the class on the type of the bounds.
388  public:
390  bool operator()(const ClosedInterval& a, const ClosedInterval& b) const {
391  return a.start != b.start ? a.start < b.start : a.end < b.end;
392  }
393  };
394  typedef std::set<ClosedInterval, IntervalComparator> IntervalSet;
395  typedef IntervalSet::iterator Iterator;
396  typedef IntervalSet::const_iterator ConstIterator;
397 
400  const std::vector<ClosedInterval>& intervals);
401 
407  // TODO(user): Explain why we favored this API to the more natural
408  // input std::vector<ClosedInterval> or std::vector<std::pair<int, int>>.
409  SortedDisjointIntervalList(const std::vector<int64>& starts,
410  const std::vector<int64>& ends);
411  SortedDisjointIntervalList(const std::vector<int>& starts,
412  const std::vector<int>& ends);
413 
418 
428  Iterator InsertInterval(int64 start, int64 end);
429 
439  Iterator GrowRightByOne(int64 value, int64* newly_covered);
440 
447  void InsertIntervals(const std::vector<int64>& starts,
448  const std::vector<int64>& ends);
449  void InsertIntervals(const std::vector<int>& starts,
450  const std::vector<int>& ends);
451 
455  int NumIntervals() const { return intervals_.size(); }
456 
466  Iterator LastIntervalLessOrEqual(int64 value) const;
467 
468  std::string DebugString() const;
469 
480  ConstIterator begin() const { return intervals_.begin(); }
481  ConstIterator end() const { return intervals_.end(); }
482 
486  const ClosedInterval& last() const { return *intervals_.rbegin(); }
487 
488  void clear() { intervals_.clear(); }
490  intervals_.swap(other.intervals_);
491  }
492 
493  private:
494  template <class T>
495  void InsertAll(const std::vector<T>& starts, const std::vector<T>& ends);
496 
497  IntervalSet intervals_;
498 };
499 
500 } // namespace operations_research
501 
502 #endif // OR_TOOLS_UTIL_SORTED_INTERVAL_LIST_H_
Domain & operator=(Domain &&other)
Move operator.
Domain(int64 left, int64 right)
Constructor for the common case of a single interval [left, right].
ClosedInterval back() const
bool IntervalsAreSortedAndNonAdjacent(absl::Span< const ClosedInterval > intervals)
Returns true iff we have:
Domain(Domain &&other)
Move constructor.
Domain MultiplicationBy(int64 coeff, bool *exact=nullptr) const
Returns {x ∈ Int64, ∃ e ∈ D, x = e * coeff}.
int NumIntervals() const
Basic read-only std::vector<> wrapping to view a Domain as a sorted list of non-adjacent intervals.
bool operator==(const Domain &other) const
static Domain FromValues(std::vector< int64 > values)
Creates a domain from the union of an unsorted list of integer values.
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 Size() const
Returns the number of elements in the domain.
SortedDisjointIntervalList(const std::vector< int64 > &starts, const std::vector< int64 > &ends)
Creates a SortedDisjointIntervalList and fills it with intervals [starts[i]..ends[i]].
Iterator LastIntervalLessOrEqual(int64 value) const
Domain UnionWith(const Domain &domain) const
Returns the union of D and domain.
Domain DivisionBy(int64 coeff) const
Returns {x ∈ Int64, ∃ e ∈ D, x = e / coeff}.
bool IsFixed() const
Returns true iff the domain is reduced to a single value.
IntervalSet::const_iterator ConstIterator
absl::InlinedVector< ClosedInterval, 1 >::const_iterator end() const
Domain ContinuousMultiplicationBy(const Domain &domain) const
Returns a superset of MultiplicationBy() to avoid the explosion in the representation size.
Definition: cp_model.h:52
bool operator!=(const Domain &other) const
int64 SumOfKMaxValueInDomain(const Domain &domain, int k)
Domain ContinuousMultiplicationBy(int64 coeff) const
Returns a superset of MultiplicationBy() to avoid the explosion in the representation size.
Represents a closed interval [start, end].
Iterator InsertInterval(int64 start, int64 end)
Adds the interval [start..end] to the list, and merges overlapping or immediately adjacent intervals ...
Domain AdditionWith(const Domain &domain) const
Returns {x ∈ Int64, ∃ a ∈ D, ∃ b ∈ domain, x = a + b}.
Iterator GrowRightByOne(int64 value, int64 *newly_covered)
If value is in an interval, increase its end by one, otherwise insert the interval [value,...
std::ostream & operator<<(std::ostream &out, const ClosedInterval &interval)
static Domain FromVectorIntervals(const std::vector< std::vector< int64 > > &intervals)
This method is available in Python, Java and .NET.
SortedDisjointIntervalList(const std::vector< ClosedInterval > &intervals)
We call domain any subset of Int64 = [kint64min, kint64max].
static Domain FromFlatSpanOfIntervals(absl::Span< const int64 > flat_intervals)
Same as FromIntervals() for a flattened representation (start, end, start, end, .....
This class represents a sorted list of disjoint, closed intervals.
Domain IntersectionWith(const Domain &domain) const
Returns the intersection of D and domain.
static Domain FromIntervals(absl::Span< const ClosedInterval > intervals)
Creates a domain from the union of an unsorted list of intervals.
void swap(SortedDisjointIntervalList &other)
bool IsEmpty() const
Returns true if this is the empty set.
std::string DebugString() const
void InsertIntervals(const std::vector< int64 > &starts, const std::vector< int64 > &ends)
Adds all intervals [starts[i]..ends[i]].
absl::InlinedVector< ClosedInterval, 1 >::const_iterator begin() const
int64 end
ClosedInterval(int64 s, int64 e)
std::vector< int64 > FlattenedIntervals() const
This method returns the flattened list of interval bounds of the domain.
Domain RelaxIfTooComplex() const
If NumIntervals() is too large, this return a superset of the domain.
int NumIntervals() const
Returns the number of disjoint intervals in the list.
SortedDisjointIntervalList()
Domain SimplifyUsingImpliedDomain(const Domain &implied_domain) const
Advanced usage.
int64 FixedValue() const
Returns the value of a fixed domain.
Domain(int64 value)
Constructor for the common case of a singleton domain.
static Domain AllValues()
Returns the full domain Int64.
ConstIterator end() const
ClosedInterval()
int64 start
bool operator==(const ClosedInterval &other) const
void InsertIntervals(const std::vector< int > &starts, const std::vector< int > &ends)
IntervalSet::iterator Iterator
Domain()
By default, Domain will be empty.
Domain InverseMultiplicationBy(const int64 coeff) const
Returns {x ∈ Int64, ∃ e ∈ D, x * coeff = e}.
int64 SumOfKMinValueInDomain(const Domain &domain, int k)
std::string DebugString() const
ConstIterator begin() const
Const iterators for SortedDisjoinIntervalList.
SortedDisjointIntervalList(const std::vector< int > &starts, const std::vector< int > &ends)
Domain Negation() const
Returns {x ∈ Int64, ∃ e ∈ D, x = -e}.
Domain Complement() const
Returns the set Int64 ∖ D.
std::set< ClosedInterval, IntervalComparator > IntervalSet
bool operator()(const ClosedInterval &a, const ClosedInterval &b) const
const ClosedInterval & last() const
Returns a const& to the last interval.
std::vector< ClosedInterval > intervals() const
ClosedInterval operator[](int i) const
int64 Max() const
Returns the max value of the domain.
int64 Min() const
Returns the min value of the domain.
void clear()
ClosedInterval front() const
bool operator<(const Domain &other) const
Lexicographic order on the intervals() representation.
bool IsIncludedIn(const Domain &domain) const
Returns true iff D is included in the given domain.
SortedDisjointIntervalList BuildComplementOnInterval(int64 start, int64 end)
Builds the complement of the interval list on the interval [start, end].
bool operator<(const ClosedInterval &other) const
Iterator FirstIntervalGreaterOrEqual(int64 value) const
Returns an iterator to either:
Domain & operator=(const Domain &other)
Copy operator (mandatory as we define the move operator).
bool Contains(int64 value) const
Returns true iff value is in Domain.