![]() |
OR-Tools
8.2
|
We call domain any subset of Int64 = [kint64min, kint64max].
This class can be used to represent such set efficiently as a sorted and non-adjacent list of intervals. This is efficient as long as the size of such list stays reasonable.
In the comments below, the domain of *this will always be written 'D'. Note that all the functions are safe with respect to integer overflow.
Definition at line 81 of file sorted_interval_list.h.
Public Member Functions | |
Domain () | |
By default, Domain will be empty. More... | |
Domain (const Domain &other) | |
Copy constructor (mandatory as we define the move constructor). More... | |
Domain & | operator= (const Domain &other) |
Copy operator (mandatory as we define the move operator). More... | |
Domain (Domain &&other) | |
Move constructor. More... | |
Domain & | operator= (Domain &&other) |
Move operator. More... | |
Domain (int64 value) | |
Constructor for the common case of a singleton domain. More... | |
Domain (int64 left, int64 right) | |
Constructor for the common case of a single interval [left, right]. More... | |
std::vector< int64 > | FlattenedIntervals () const |
This method returns the flattened list of interval bounds of the domain. More... | |
bool | IsEmpty () const |
Returns true if this is the empty set. More... | |
int64 | Size () const |
Returns the number of elements in the domain. More... | |
int64 | Min () const |
Returns the min value of the domain. More... | |
int64 | Max () const |
Returns the max value of the domain. More... | |
bool | IsFixed () const |
Returns true iff the domain is reduced to a single value. More... | |
int64 | FixedValue () const |
Returns the value of a fixed domain. More... | |
bool | Contains (int64 value) const |
Returns true iff value is in Domain. More... | |
bool | IsIncludedIn (const Domain &domain) const |
Returns true iff D is included in the given domain. More... | |
Domain | Complement () const |
Returns the set Int64 ∖ D. More... | |
Domain | Negation () const |
Returns {x ∈ Int64, ∃ e ∈ D, x = -e}. More... | |
Domain | IntersectionWith (const Domain &domain) const |
Returns the intersection of D and domain. More... | |
Domain | UnionWith (const Domain &domain) const |
Returns the union of D and domain. More... | |
Domain | AdditionWith (const Domain &domain) const |
Returns {x ∈ Int64, ∃ a ∈ D, ∃ b ∈ domain, x = a + b}. More... | |
Domain | MultiplicationBy (int64 coeff, bool *exact=nullptr) const |
Returns {x ∈ Int64, ∃ e ∈ D, x = e * coeff}. More... | |
Domain | RelaxIfTooComplex () const |
If NumIntervals() is too large, this return a superset of the domain. More... | |
Domain | ContinuousMultiplicationBy (int64 coeff) const |
Returns a superset of MultiplicationBy() to avoid the explosion in the representation size. More... | |
Domain | ContinuousMultiplicationBy (const Domain &domain) const |
Returns a superset of MultiplicationBy() to avoid the explosion in the representation size. More... | |
Domain | DivisionBy (int64 coeff) const |
Returns {x ∈ Int64, ∃ e ∈ D, x = e / coeff}. More... | |
Domain | InverseMultiplicationBy (const int64 coeff) const |
Returns {x ∈ Int64, ∃ e ∈ D, x * coeff = e}. More... | |
Domain | SimplifyUsingImpliedDomain (const Domain &implied_domain) const |
Advanced usage. More... | |
std::string | ToString () const |
Returns a compact string of a vector of intervals like "[1,4][6][10,20]". More... | |
bool | operator< (const Domain &other) const |
Lexicographic order on the intervals() representation. More... | |
bool | operator== (const Domain &other) const |
bool | operator!= (const Domain &other) const |
int | NumIntervals () const |
Basic read-only std::vector<> wrapping to view a Domain as a sorted list of non-adjacent intervals. More... | |
ClosedInterval | front () const |
ClosedInterval | back () const |
ClosedInterval | operator[] (int i) const |
absl::InlinedVector< ClosedInterval, 1 >::const_iterator | begin () const |
absl::InlinedVector< ClosedInterval, 1 >::const_iterator | end () const |
std::vector< ClosedInterval > | intervals () const |
Static Public Member Functions | |
static Domain | AllValues () |
Returns the full domain Int64. More... | |
static Domain | FromValues (std::vector< int64 > values) |
Creates a domain from the union of an unsorted list of integer values. More... | |
static Domain | FromIntervals (absl::Span< const ClosedInterval > intervals) |
Creates a domain from the union of an unsorted list of intervals. More... | |
static Domain | FromFlatSpanOfIntervals (absl::Span< const int64 > flat_intervals) |
Same as FromIntervals() for a flattened representation (start, end, start, end, ...). More... | |
static Domain | FromVectorIntervals (const std::vector< std::vector< int64 > > &intervals) |
This method is available in Python, Java and .NET. More... | |
static Domain | FromFlatIntervals (const std::vector< int64 > &flat_intervals) |
This method is available in Python, Java and .NET. More... | |
|
inline |
By default, Domain will be empty.
Definition at line 84 of file sorted_interval_list.h.
Copy constructor (mandatory as we define the move constructor).
Definition at line 88 of file sorted_interval_list.h.
Move constructor.
Definition at line 97 of file sorted_interval_list.h.
Constructor for the common case of a singleton domain.
Definition at line 114 of file sorted_interval_list.cc.
Constructor for the common case of a single interval [left, right].
If left > right, this will result in the empty domain.
Definition at line 131 of file sorted_interval_list.cc.
Returns {x ∈ Int64, ∃ a ∈ D, ∃ b ∈ domain, x = a + b}.
Definition at line 333 of file sorted_interval_list.cc.
|
static |
Returns the full domain Int64.
Definition at line 136 of file sorted_interval_list.cc.
|
inline |
Definition at line 341 of file sorted_interval_list.h.
|
inline |
Definition at line 343 of file sorted_interval_list.h.
Domain Complement | ( | ) | const |
Returns the set Int64 ∖ D.
Definition at line 246 of file sorted_interval_list.cc.
bool Contains | ( | int64 | value | ) | const |
Returns true iff value is in Domain.
Definition at line 222 of file sorted_interval_list.cc.
Returns a superset of MultiplicationBy() to avoid the explosion in the representation size.
This behaves as if we replace the set D of non-adjacent integer intervals by the set of floating-point elements in the same intervals.
For instance, [1, 100] * 2 will be transformed in [2, 200] and not in [2][4][6]...[200] like in MultiplicationBy(). Note that this would be similar to a InverseDivisionBy(), but not quite the same because if we look for {x ∈ Int64, ∃ e ∈ D, x / coeff = e}, then we will get [2, 201] in the case above.
Definition at line 411 of file sorted_interval_list.cc.
Returns a superset of MultiplicationBy() to avoid the explosion in the representation size.
This behaves as if we replace the set D of non-adjacent integer intervals by the set of floating-point elements in the same intervals.
For instance, [1, 100] * 2 will be transformed in [2, 200] and not in [2][4][6]...[200] like in MultiplicationBy(). Note that this would be similar to a InverseDivisionBy(), but not quite the same because if we look for {x ∈ Int64, ∃ e ∈ D, x / coeff = e}, then we will get [2, 201] in the case above.
Definition at line 399 of file sorted_interval_list.cc.
Returns {x ∈ Int64, ∃ e ∈ D, x = e / coeff}.
For instance Domain(1, 7).DivisionBy(2) == Domain(0, 3).
Definition at line 430 of file sorted_interval_list.cc.
|
inline |
Definition at line 346 of file sorted_interval_list.h.
int64 FixedValue | ( | ) | const |
Returns the value of a fixed domain.
IsFixed() must be true. This is the same as Min() or Max() but allows for amore readable code and also crash in debug mode if called on a non fixed domain.
Definition at line 217 of file sorted_interval_list.cc.
std::vector< int64 > FlattenedIntervals | ( | ) | const |
This method returns the flattened list of interval bounds of the domain.
Thus the domain {0, 1, 2, 5, 8, 9, 10} will return 0, 2, 5, 5, 8, 10.
Definition at line 519 of file sorted_interval_list.cc.
This method is available in Python, Java and .NET.
It allows building a Domain object from a flattened list of intervals (long[] in Java and .NET, [0, 2, 5, 5, 8, 10] in python).
Definition at line 171 of file sorted_interval_list.cc.
Same as FromIntervals() for a flattened representation (start, end, start, end, ...).
Definition at line 159 of file sorted_interval_list.cc.
|
static |
Creates a domain from the union of an unsorted list of intervals.
Definition at line 151 of file sorted_interval_list.cc.
Creates a domain from the union of an unsorted list of integer values.
Input values may be repeated, with no consequence on the output
Definition at line 138 of file sorted_interval_list.cc.
This method is available in Python, Java and .NET.
It allows building a Domain object from a list of intervals (long[][] in Java and .NET, [[0, 2], [5, 5], [8, 10]] in python).
Definition at line 175 of file sorted_interval_list.cc.
|
inline |
Definition at line 340 of file sorted_interval_list.h.
Returns the intersection of D and domain.
Definition at line 283 of file sorted_interval_list.cc.
|
inline |
Definition at line 354 of file sorted_interval_list.h.
Returns {x ∈ Int64, ∃ e ∈ D, x * coeff = e}.
For instance Domain(1, 7).InverseMultiplicationBy(2) == Domain(1, 3).
Definition at line 443 of file sorted_interval_list.cc.
bool IsEmpty | ( | ) | const |
Returns true if this is the empty set.
Definition at line 191 of file sorted_interval_list.cc.
bool IsFixed | ( | ) | const |
Returns true iff the domain is reduced to a single value.
The domain must not be empty.
Definition at line 193 of file sorted_interval_list.cc.
bool IsIncludedIn | ( | const Domain & | domain | ) | const |
Returns true iff D is included in the given domain.
Definition at line 233 of file sorted_interval_list.cc.
int64 Max | ( | ) | const |
Returns the max value of the domain.
The domain must not be empty.
Definition at line 212 of file sorted_interval_list.cc.
int64 Min | ( | ) | const |
Returns the min value of the domain.
The domain must not be empty.
Definition at line 207 of file sorted_interval_list.cc.
Returns {x ∈ Int64, ∃ e ∈ D, x = e * coeff}.
Note that because the resulting domain will only contains multiple of coeff, the size of intervals.size() can become really large. If it is larger than a fixed constant, exact will be set to false and the result will be set to ContinuousMultiplicationBy(coeff).
Note that if you multiply by a negative coeff, kint64min will be dropped from the result even if it was here due to how this is implemented.
Definition at line 362 of file sorted_interval_list.cc.
Domain Negation | ( | ) | const |
Returns {x ∈ Int64, ∃ e ∈ D, x = -e}.
Note in particular that if the negation of Int64 is not Int64 but Int64 \ {kint64min} !!
Definition at line 262 of file sorted_interval_list.cc.
|
inline |
Basic read-only std::vector<> wrapping to view a Domain as a sorted list of non-adjacent intervals.
Note that we don't expose size() which might be confused with the number of values in the domain.
Definition at line 339 of file sorted_interval_list.h.
|
inline |
Definition at line 330 of file sorted_interval_list.h.
bool operator< | ( | const Domain & | other | ) | const |
Lexicographic order on the intervals() representation.
Definition at line 528 of file sorted_interval_list.cc.
Copy operator (mandatory as we define the move operator).
Definition at line 91 of file sorted_interval_list.h.
Move operator.
Definition at line 100 of file sorted_interval_list.h.
|
inline |
Definition at line 326 of file sorted_interval_list.h.
|
inline |
Definition at line 342 of file sorted_interval_list.h.
Domain RelaxIfTooComplex | ( | ) | const |
If NumIntervals() is too large, this return a superset of the domain.
Definition at line 354 of file sorted_interval_list.cc.
Advanced usage.
Given some implied information on this domain that is assumed to be always true (i.e. only values in the intersection with implied domain matter), this function will simplify the current domain without changing the set of "possible values".
More precisely, this will:
Note that domain.SimplifyUsingImpliedDomain(domain) will just return [domain.Min(), domain.Max()]. This is meant to be applied to the right-hand side of a constraint to make its propagation more efficient.
Definition at line 471 of file sorted_interval_list.cc.
int64 Size | ( | ) | const |
Returns the number of elements in the domain.
It is capped at kint64max
Definition at line 195 of file sorted_interval_list.cc.
std::string ToString | ( | ) | const |
Returns a compact string of a vector of intervals like "[1,4][6][10,20]".
Definition at line 543 of file sorted_interval_list.cc.
Returns the union of D and domain.
Definition at line 322 of file sorted_interval_list.cc.