OR-Tools  8.2
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"
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 
209  Domain Complement() const;
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 
250  Domain RelaxIfTooComplex() const;
251 
265 
278  Domain ContinuousMultiplicationBy(const Domain& domain) const;
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 
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_
#define DLOG_IF(severity, condition)
Definition: base/logging.h:877
We call domain any subset of Int64 = [kint64min, kint64max].
static Domain AllValues()
Returns the full domain Int64.
Domain(Domain &&other)
Move constructor.
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.
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}.
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}.
ClosedInterval front() const
int64 Min() const
Returns the min value of the domain.
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.
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.
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).
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.
absl::InlinedVector< ClosedInterval, 1 >::const_iterator begin() const
Domain & operator=(const Domain &other)
Copy operator (mandatory as we define the move operator).
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 ...
const ClosedInterval & last() const
Returns a const& to the last interval.
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].
void swap(SortedDisjointIntervalList &other)
std::set< ClosedInterval, IntervalComparator > IntervalSet
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
int64_t int64
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 SumOfKMinValueInDomain(const Domain &domain, int k)
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
int64 SumOfKMaxValueInDomain(const Domain &domain, int k)
bool IntervalsAreSortedAndNonAdjacent(absl::Span< const ClosedInterval > intervals)
Returns true iff we have:
IntervalVar * interval
Definition: resource.cc:98
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