C++ Reference

C++ Reference: CP-SAT

Detailed Description

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...
 
Domainoperator= (const Domain &other)
 Copy operator (mandatory as we define the move operator). More...
 
 Domain (Domain &&other)
 Move constructor. More...
 
Domainoperator= (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< ClosedIntervalintervals () 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...
 

Constructor & Destructor Documentation

◆ Domain() [1/5]

Domain ( )
inline

By default, Domain will be empty.

Definition at line 84 of file sorted_interval_list.h.

◆ Domain() [2/5]

Domain ( const Domain other)
inline

Copy constructor (mandatory as we define the move constructor).

Definition at line 88 of file sorted_interval_list.h.

◆ Domain() [3/5]

Domain ( Domain &&  other)
inline

Move constructor.

Definition at line 97 of file sorted_interval_list.h.

◆ Domain() [4/5]

Domain ( int64  value)
explicit

Constructor for the common case of a singleton domain.

◆ Domain() [5/5]

Domain ( int64  left,
int64  right 
)

Constructor for the common case of a single interval [left, right].

If left > right, this will result in the empty domain.

Member Function Documentation

◆ AdditionWith()

Domain AdditionWith ( const Domain domain) const

Returns {x ∈ Int64, ∃ a ∈ D, ∃ b ∈ domain, x = a + b}.

◆ AllValues()

static Domain AllValues ( )
static

Returns the full domain Int64.

◆ back()

ClosedInterval back ( ) const
inline

Definition at line 341 of file sorted_interval_list.h.

◆ begin()

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

Definition at line 343 of file sorted_interval_list.h.

◆ Complement()

Domain Complement ( ) const

Returns the set Int64 ∖ D.

◆ Contains()

bool Contains ( int64  value) const

Returns true iff value is in Domain.

◆ ContinuousMultiplicationBy() [1/2]

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.

◆ ContinuousMultiplicationBy() [2/2]

Domain ContinuousMultiplicationBy ( int64  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.

◆ DivisionBy()

Domain DivisionBy ( int64  coeff) const

Returns {x ∈ Int64, ∃ e ∈ D, x = e / coeff}.

For instance Domain(1, 7).DivisionBy(2) == Domain(0, 3).

◆ end()

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

Definition at line 346 of file sorted_interval_list.h.

◆ FixedValue()

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.

◆ FlattenedIntervals()

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

◆ FromFlatIntervals()

static Domain FromFlatIntervals ( const std::vector< int64 > &  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).

◆ FromFlatSpanOfIntervals()

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

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

◆ FromIntervals()

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

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

◆ FromValues()

static Domain FromValues ( std::vector< int64 >  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

◆ FromVectorIntervals()

static Domain FromVectorIntervals ( const std::vector< std::vector< int64 > > &  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, 5], [8, 10]] in python).

◆ front()

ClosedInterval front ( ) const
inline

Definition at line 340 of file sorted_interval_list.h.

◆ IntersectionWith()

Domain IntersectionWith ( const Domain domain) const

Returns the intersection of D and domain.

◆ intervals()

std::vector< ClosedInterval > intervals ( ) const
inline

Definition at line 354 of file sorted_interval_list.h.

◆ InverseMultiplicationBy()

Domain InverseMultiplicationBy ( const int64  coeff) const

Returns {x ∈ Int64, ∃ e ∈ D, x * coeff = e}.

For instance Domain(1, 7).InverseMultiplicationBy(2) == Domain(1, 3).

◆ IsEmpty()

bool IsEmpty ( ) const

Returns true if this is the empty set.

◆ IsFixed()

bool IsFixed ( ) const

Returns true iff the domain is reduced to a single value.

The domain must not be empty.

◆ IsIncludedIn()

bool IsIncludedIn ( const Domain domain) const

Returns true iff D is included in the given domain.

◆ Max()

int64 Max ( ) const

Returns the max value of the domain.

The domain must not be empty.

◆ Min()

int64 Min ( ) const

Returns the min value of the domain.

The domain must not be empty.

◆ MultiplicationBy()

Domain MultiplicationBy ( int64  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.

◆ Negation()

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} !!

◆ NumIntervals()

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

◆ operator!=()

bool operator!= ( const Domain other) const
inline

Definition at line 330 of file sorted_interval_list.h.

◆ operator<()

bool operator< ( const Domain other) const

Lexicographic order on the intervals() representation.

◆ operator=() [1/2]

Domain & operator= ( const Domain other)
inline

Copy operator (mandatory as we define the move operator).

Definition at line 91 of file sorted_interval_list.h.

◆ operator=() [2/2]

Domain & operator= ( Domain &&  other)
inline

Move operator.

Definition at line 100 of file sorted_interval_list.h.

◆ operator==()

bool operator== ( const Domain other) const
inline

Definition at line 326 of file sorted_interval_list.h.

◆ operator[]()

ClosedInterval operator[] ( int  i) const
inline

Definition at line 342 of file sorted_interval_list.h.

◆ RelaxIfTooComplex()

Domain RelaxIfTooComplex ( ) const

If NumIntervals() is too large, this return a superset of the domain.

◆ SimplifyUsingImpliedDomain()

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.

◆ Size()

int64 Size ( ) const

Returns the number of elements in the domain.

It is capped at kint64max

◆ ToString()

std::string ToString ( ) const

Returns a compact string of a vector of intervals like "[1,4][6][10,20]".

◆ UnionWith()

Domain UnionWith ( const Domain domain) const

Returns the union of D and domain.


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