Home Original page

Google OR-Tools: operations_research::Domain Class Reference

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 113 of file sorted_interval_list.h.

#include <sorted_interval_list.h>

Public Member Functions

 Domain ()
 By default, Domain will be empty.
 Domain (const Domain &other)
 Copy constructor (mandatory as we define the move constructor).
Domain & operator= (const Domain &other)
 Copy operator (mandatory as we define the move operator).
 Domain (Domain &&other) noexcept
 Move constructor.
Domain & operator= (Domain &&other) noexcept
 Move operator.
 Domain (int64_t value)
 Constructor for the common case of a singleton domain.
 Domain (int64_t left, int64_t right)
std::vector< int64_t > FlattenedIntervals () const
DomainIteratorBeginEnd Values () const &
DomainIteratorBeginEndWithOwnership Values () const &&
bool IsEmpty () const
int64_t Size () const
bool HasTwoValues () const
int64_t Min () const
int64_t Max () const
int64_t SmallestValue () const
int64_t ClosestValue (int64_t wanted) const
int64_t ValueAtOrBefore (int64_t input) const
int64_t ValueAtOrAfter (int64_t input) const
Domain PartAroundZero () const
bool IsFixed () const
int64_t FixedValue () const
bool Contains (int64_t value) const
int64_t Distance (int64_t value) const
bool IsIncludedIn (const Domain &domain) const
bool OverlapsWith (const Domain &domain) const
Domain Complement () const
Domain Negation () const
Domain IntersectionWith (const Domain &domain) const
Domain UnionWith (const Domain &domain) const
Domain AdditionWith (const Domain &domain) const
Domain MultiplicationBy (int64_t coeff, bool *exact=nullptr) const
Domain RelaxIfTooComplex () const
Domain ContinuousMultiplicationBy (int64_t coeff) const
Domain ContinuousMultiplicationBy (const Domain &domain) const
Domain DivisionBy (int64_t coeff) const
Domain InverseMultiplicationBy (int64_t coeff) const
Domain PositiveModuloBySuperset (const Domain &modulo) const
Domain PositiveDivisionBySuperset (const Domain &divisor) const
Domain SquareSuperset () const
Domain QuadraticSuperset (int64_t a, int64_t b, int64_t c, int64_t d) const
Domain SimplifyUsingImpliedDomain (const Domain &implied_domain) const
std::string ToString () const
bool operator< (const Domain &other) const
bool operator== (const Domain &other) const
bool operator!= (const Domain &other) const
int NumIntervals () const
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

Static Public Member Functions

static Domain AllValues ()
static Domain LowerOrEqual (int64_t value)
static Domain GreaterOrEqual (int64_t value)
static Domain FromValues (std::vector< int64_t > values)
static Domain FromIntervals (absl::Span< const ClosedInterval > intervals)
static Domain FromFlatSpanOfIntervals (absl::Span< const int64_t > flat_intervals)
static Domain FromVectorIntervals (const std::vector< std::vector< int64_t > > &intervals)
static Domain FromFlatIntervals (const std::vector< int64_t > &flat_intervals)

Friends

template<typename H>
H AbslHashValue (H h, const Domain &domain)

◆ Domain() [1/5]

operations_research::Domain::Domain ( )
inline

◆ Domain() [2/5]

operations_research::Domain::Domain ( const Domain & other)
inline

◆ Domain() [3/5]

operations_research::Domain::Domain ( Domain && other)
inlinenoexcept

◆ Domain() [4/5]

operations_research::Domain::Domain ( int64_t value)
explicit

◆ Domain() [5/5]

operations_research::Domain::Domain ( int64_t left,
int64_t right )

Constructor for the common case of a single interval [left, right]. If left > right, this will result in the empty domain.

Definition at line 150 of file sorted_interval_list.cc.

◆ AdditionWith()

Domain operations_research::Domain::AdditionWith ( const Domain & domain) const

◆ AllValues()

Domain operations_research::Domain::AllValues ( )
static

◆ back()

◆ begin()

absl::InlinedVector< ClosedInterval, 1 >::const_iterator operations_research::Domain::begin ( ) const
inline

◆ ClosestValue()

int64_t operations_research::Domain::ClosestValue ( int64_t wanted) const

Returns the value closest to the given point. If there is a tie, pick larger one.

Definition at line 269 of file sorted_interval_list.cc.

◆ Complement()

Domain operations_research::Domain::Complement ( ) const

◆ Contains()

bool operations_research::Domain::Contains ( int64_t value) const

◆ ContinuousMultiplicationBy() [1/2]

Domain operations_research::Domain::ContinuousMultiplicationBy ( const Domain & domain) const

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 554 of file sorted_interval_list.cc.

◆ ContinuousMultiplicationBy() [2/2]

Domain operations_research::Domain::ContinuousMultiplicationBy ( int64_t coeff) const

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 542 of file sorted_interval_list.cc.

◆ Distance()

int64_t operations_research::Domain::Distance ( int64_t value) const

◆ DivisionBy()

Domain operations_research::Domain::DivisionBy ( int64_t coeff) const

◆ end()

absl::InlinedVector< ClosedInterval, 1 >::const_iterator operations_research::Domain::end ( ) const
inline

◆ FixedValue()

int64_t operations_research::Domain::FixedValue ( ) const

Returns the value of a fixed domain. IsFixed() must be true. This is the same as Min() or Max() but allows for a more readable code and also crash in debug mode if called on a non fixed domain.

Definition at line 314 of file sorted_interval_list.cc.

◆ FlattenedIntervals()

std::vector< int64_t > operations_research::Domain::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] (as a C++ std::vector<int64_t>, as a java or C# long[], as a python list of integers).

Definition at line 805 of file sorted_interval_list.cc.

◆ FromFlatIntervals()

Domain operations_research::Domain::FromFlatIntervals ( const std::vector< int64_t > & flat_intervals)
static

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).

Note that invalid intervals (start > end) will log a DFATAL error and will be ignored.

Definition at line 200 of file sorted_interval_list.cc.

◆ FromFlatSpanOfIntervals()

Domain operations_research::Domain::FromFlatSpanOfIntervals ( absl::Span< const int64_t > flat_intervals)
static

Same as FromIntervals() for a flattened representation (start, end, start, end, ...).

Note that invalid intervals (start > end) will log a DFATAL error and will be ignored.

Definition at line 187 of file sorted_interval_list.cc.

◆ FromIntervals()

Domain operations_research::Domain::FromIntervals ( absl::Span< const ClosedInterval > intervals)
static

Creates a domain from the union of an unsorted list of intervals.

Note that invalid intervals (start > end) will log a DFATAL error and will be ignored.

Definition at line 179 of file sorted_interval_list.cc.

◆ FromValues()

Domain operations_research::Domain::FromValues ( std::vector< int64_t > values)
static

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 163 of file sorted_interval_list.cc.

◆ FromVectorIntervals()

Domain operations_research::Domain::FromVectorIntervals ( const std::vector< std::vector< int64_t > > & intervals)
static

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], [8, 10]] in python).

Note that the intervals can be defined with a single value (i.e. [5]), or two increasing values (i.e. [8, 10]).

Invalid intervals (start > end) will log a DFATAL error and will be ignored.

Definition at line 204 of file sorted_interval_list.cc.

◆ front()

◆ GreaterOrEqual()

Domain operations_research::Domain::GreaterOrEqual ( int64_t value)
static

◆ HasTwoValues()

bool operations_research::Domain::HasTwoValues ( ) const
inline

Returns true if the domain has just two values. This often mean a non-fixed Boolean variable.

Definition at line 286 of file sorted_interval_list.h.

◆ IntersectionWith()

Domain operations_research::Domain::IntersectionWith ( const Domain & domain) const

◆ InverseMultiplicationBy()

Domain operations_research::Domain::InverseMultiplicationBy ( int64_t coeff) const

◆ IsEmpty()

bool operations_research::Domain::IsEmpty ( ) const

◆ IsFixed()

bool operations_research::Domain::IsFixed ( ) const

Returns true iff the domain is reduced to a single value. The domain must not be empty.

Definition at line 222 of file sorted_interval_list.cc.

◆ IsIncludedIn()

bool operations_research::Domain::IsIncludedIn ( const Domain & domain) const

◆ LowerOrEqual()

Domain operations_research::Domain::LowerOrEqual ( int64_t value)
static

◆ Max()

int64_t operations_research::Domain::Max ( ) const

◆ Min()

int64_t operations_research::Domain::Min ( ) const

◆ MultiplicationBy()

Domain operations_research::Domain::MultiplicationBy ( int64_t coeff,
bool * exact = nullptr ) const

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 505 of file sorted_interval_list.cc.

◆ Negation()

Domain operations_research::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 397 of file sorted_interval_list.cc.

◆ NumIntervals()

int operations_research::Domain::NumIntervals ( ) const
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 532 of file sorted_interval_list.h.

◆ operator!=()

bool operations_research::Domain::operator!= ( const Domain & other) const
inline

◆ operator<()

bool operations_research::Domain::operator< ( const Domain & other) const

◆ operator=() [1/2]

Domain & operations_research::Domain::operator= ( const Domain & other)
inline

◆ operator=() [2/2]

Domain & operations_research::Domain::operator= ( Domain && other)
inlinenoexcept

◆ operator==()

bool operations_research::Domain::operator== ( const Domain & other) const
inline

◆ operator[]()

ClosedInterval operations_research::Domain::operator[] ( int i) const
inline

◆ OverlapsWith()

bool operations_research::Domain::OverlapsWith ( const Domain & domain) const

Returns true iff D overlaps with the given domain, that is, the intersection of the two domains is not empty.

Definition at line 358 of file sorted_interval_list.cc.

◆ PartAroundZero()

Domain operations_research::Domain::PartAroundZero ( ) const

If the domain contains zero, this return the simple interval around it. Otherwise, this returns an empty domain.

Definition at line 259 of file sorted_interval_list.cc.

◆ PositiveDivisionBySuperset()

Domain operations_research::Domain::PositiveDivisionBySuperset ( const Domain & divisor) const

Returns a superset of {x ∈ Int64, ∃ e ∈ D, ∃ d ∈ divisor, x = e / d }.

We check that divisor is strictly positive. For now we just intersect with the min/max possible value.

Definition at line 644 of file sorted_interval_list.cc.

◆ PositiveModuloBySuperset()

Domain operations_research::Domain::PositiveModuloBySuperset ( const Domain & modulo) const

Returns a superset of {x ∈ Int64, ∃ e ∈ D, ∃ m ∈ modulo, x = e % m }.

We check that modulo is strictly positive. The sign of the modulo depends on the sign of e. We compute the exact min/max if the modulo is fixed, otherwise we will just return a superset.

Definition at line 630 of file sorted_interval_list.cc.

◆ QuadraticSuperset()

Domain operations_research::Domain::QuadraticSuperset ( int64_t a,
int64_t b,
int64_t c,
int64_t d ) const

◆ RelaxIfTooComplex()

Domain operations_research::Domain::RelaxIfTooComplex ( ) const

◆ SimplifyUsingImpliedDomain()

Domain operations_research::Domain::SimplifyUsingImpliedDomain ( const Domain & implied_domain) const

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:

  • Take the intersection with implied_domain.
  • Minimize the number of intervals. For example, if the domain is [1,2][4] and implied is [1][4], then the domain can be relaxed to [1, 4] to simplify its complexity without changing the set of admissible value assuming only implied values can be seen.
  • Restrict as much as possible the bounds of the remaining intervals. For example, if the input is [1,2] and implied is [0,4], then the domain will not be changed.

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 757 of file sorted_interval_list.cc.

◆ Size()

int64_t operations_research::Domain::Size ( ) const

◆ SmallestValue()

int64_t operations_research::Domain::SmallestValue ( ) const

◆ SquareSuperset()

Domain operations_research::Domain::SquareSuperset ( ) const

◆ ToString()

std::string operations_research::Domain::ToString ( ) const

◆ UnionWith()

Domain operations_research::Domain::UnionWith ( const Domain & domain) const

◆ ValueAtOrAfter()

int64_t operations_research::Domain::ValueAtOrAfter ( int64_t input) const

◆ ValueAtOrBefore()

int64_t operations_research::Domain::ValueAtOrBefore ( int64_t input) const

Returns the closest value in the domain that is <= (resp. >=) to the input. Do not change the input if there is no such value.

Definition at line 290 of file sorted_interval_list.cc.

◆ Values() [1/2]

◆ Values() [2/2]

◆ AbslHashValue

template<typename H>

H AbslHashValue ( H h,
const Domain & domain )
friend

The documentation for this class was generated from the following files: