#include <sorted_interval_list.h>

Classes
class	DomainIterator

struct	DomainIteratorBeginEnd

struct	DomainIteratorBeginEndWithOwnership

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

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

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

Constructor & Destructor Documentation

◆ Domain() [1/5]

operations_research::Domain::Domain ( )

inline

By default, Domain will be empty.

Definition at line 90 of file sorted_interval_list.h.

◆ Domain() [2/5]

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

inline

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

Definition at line 94 of file sorted_interval_list.h.

◆ Domain() [3/5]

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

inlinenoexcept

Move constructor.

Definition at line 103 of file sorted_interval_list.h.

◆ Domain() [4/5]

operations_research::Domain::Domain ( int64_t value )

explicit

Constructor for the common case of a singleton domain.

Definition at line 133 of file sorted_interval_list.cc.

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

Member Function Documentation

◆ AdditionWith()

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

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

Todo: (user): Use a better algorithm.

The sort is not needed if one of the list is of size 1.

Definition at line 439 of file sorted_interval_list.cc.

◆ AllValues()

Domain operations_research::Domain::AllValues ( )

static

Returns the full domain Int64.

Definition at line 155 of file sorted_interval_list.cc.

◆ back()

ClosedInterval operations_research::Domain::back ( ) const

inline

Definition at line 496 of file sorted_interval_list.h.

◆ begin()

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

inline

Definition at line 498 of file sorted_interval_list.h.

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

Todo: (user): Use std::upper_bound() like in ValueAtOrBefore() ?

Definition at line 263 of file sorted_interval_list.cc.

◆ Complement()

Domain operations_research::Domain::Complement ( ) const

Returns the set Int64 ∖ D.

Definition at line 352 of file sorted_interval_list.cc.

◆ Contains()

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

Returns true iff value is in Domain.

Because we only compare by start and there is no duplicate starts, this should be the next interval after the one that has a chance to contains value.

Definition at line 313 of file sorted_interval_list.cc.

◆ 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 525 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 513 of file sorted_interval_list.cc.

◆ Distance()

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

Returns the distance from the value to the domain.

Todo: (user): Deal with overflow.

Definition at line 325 of file sorted_interval_list.cc.

◆ DivisionBy()

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

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

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

Definition at line 544 of file sorted_interval_list.cc.

◆ end()

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

inline

Definition at line 501 of file sorted_interval_list.h.

◆ 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 308 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 776 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 194 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 181 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 173 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 157 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 198 of file sorted_interval_list.cc.

◆ front()

ClosedInterval operations_research::Domain::front ( ) const

inline

Definition at line 495 of file sorted_interval_list.h.

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

◆ IntersectionWith()

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

Returns the intersection of D and domain.

Empty intersection. We advance past the first interval.

Non-empty intersection: push back the intersection of these two, and advance past the first interval to finish.

We do the exact same thing as above, but swapping a and b.

Definition at line 389 of file sorted_interval_list.cc.

◆ InverseMultiplicationBy()

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

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

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

Definition at line 557 of file sorted_interval_list.cc.

◆ IsEmpty()

bool operations_research::Domain::IsEmpty ( ) const

Returns true if this is the empty set.

Definition at line 214 of file sorted_interval_list.cc.

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

◆ IsIncludedIn()

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

Returns true iff D is included in the given domain.

Find the unique interval in others that contains interval if any.

Definition at line 339 of file sorted_interval_list.cc.

◆ Max()

int64_t operations_research::Domain::Max ( ) const

Returns the max value of the domain. The domain must not be empty.

Definition at line 235 of file sorted_interval_list.cc.

◆ Min()

int64_t operations_research::Domain::Min ( ) const

Returns the min value of the domain. The domain must not be empty.

Definition at line 230 of file sorted_interval_list.cc.

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

We ignore anything that overflow.

Because abs_coeff > 1, all new values are disjoint.

This is to avoid doing ++v when v is kint64max!

Definition at line 476 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 368 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 494 of file sorted_interval_list.h.

◆ operator!=()

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

inline

Definition at line 480 of file sorted_interval_list.h.

◆ operator<()

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

Lexicographic order on the intervals() representation.

Definition at line 785 of file sorted_interval_list.cc.

◆ operator=() [1/2]

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

inline

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

Definition at line 97 of file sorted_interval_list.h.

◆ operator=() [2/2]

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

inlinenoexcept

Move operator.

Definition at line 106 of file sorted_interval_list.h.

◆ operator==()

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

inline

Definition at line 476 of file sorted_interval_list.h.

◆ operator[]()

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

inline

Definition at line 497 of file sorted_interval_list.h.

◆ 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 253 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 615 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 601 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

Returns a superset of {x ∈ Int64, ∃ y ∈ D, x = (a*y + b)*(c*y + d) }.

Definition at line 691 of file sorted_interval_list.cc.

◆ RelaxIfTooComplex()

Domain operations_research::Domain::RelaxIfTooComplex ( ) const

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

Definition at line 468 of file sorted_interval_list.cc.

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

It is a bit difficult to see, but this code is doing the same thing as for all interval in this.UnionWith(implied_domain.Complement())):

Take the two extreme points (min and max) in interval \inter implied.
Append to result [min, max] if these points exists.

We only "close" the new result interval if it cannot be extended by implied_domain.Complement(). The only extension possible look like: interval_: ...] [.... implied : ...] [... i ...]

Find the two extreme points in interval \inter implied_domain. Always stop the loop at the first interval with and end strictly greater that interval.end.

Current and interval have a non-empty intersection.

No need to update the min_point here, and the new inter_max must necessarily be > old one.

Definition at line 728 of file sorted_interval_list.cc.

◆ Size()

int64_t operations_research::Domain::Size ( ) const

Returns the number of elements in the domain. It is capped at kint64max

Because the intervals are closed on both side above, with miss 1 per interval.

Definition at line 218 of file sorted_interval_list.cc.

◆ SmallestValue()

int64_t operations_research::Domain::SmallestValue ( ) const

Returns the value closest to zero. If there is a tie, pick positive one.

Definition at line 240 of file sorted_interval_list.cc.

◆ SquareSuperset()

Domain operations_research::Domain::SquareSuperset ( ) const

Returns a superset of {x ∈ Int64, ∃ y ∈ D, x = y * y }.

Definition at line 622 of file sorted_interval_list.cc.

◆ ToString()

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

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

Definition at line 800 of file sorted_interval_list.cc.

◆ UnionWith()

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

Returns the union of D and domain.

Definition at line 428 of file sorted_interval_list.cc.

◆ ValueAtOrAfter()

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

Because we only compare by start and there is no duplicate starts, this should be the next interval after the one that has a chance to contains value.

Definition at line 295 of file sorted_interval_list.cc.

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

Because we only compare by start and there is no duplicate starts, this should be the next interval after the one that has a chance to contains value.

Definition at line 284 of file sorted_interval_list.cc.

◆ Values() [1/2]

DomainIteratorBeginEnd operations_research::Domain::Values ( ) const &

inline

Definition at line 234 of file sorted_interval_list.h.

◆ Values() [2/2]

DomainIteratorBeginEndWithOwnership operations_research::Domain::Values ( ) const &&

inline

Definition at line 235 of file sorted_interval_list.h.

Friends And Related Symbol Documentation

◆ AbslHashValue

template<typename H>

H AbslHashValue	(	H	h,
		const Domain &	domain )

friend

Definition at line 485 of file sorted_interval_list.h.

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

ortools/util/sorted_interval_list.h
ortools/util/sorted_interval_list.cc

Classes

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

Constructor & Destructor Documentation

◆ Domain() [1/5]

◆ Domain() [2/5]

◆ Domain() [3/5]

◆ Domain() [4/5]

◆ Domain() [5/5]

Member Function Documentation

◆ AdditionWith()

◆ AllValues()

◆ back()

◆ begin()

◆ ClosestValue()

◆ Complement()

◆ Contains()

◆ ContinuousMultiplicationBy() [1/2]

◆ ContinuousMultiplicationBy() [2/2]

◆ Distance()

◆ DivisionBy()

◆ end()

◆ FixedValue()

◆ FlattenedIntervals()

◆ FromFlatIntervals()

◆ FromFlatSpanOfIntervals()

◆ FromIntervals()

◆ FromValues()

◆ FromVectorIntervals()

◆ front()

◆ HasTwoValues()

◆ IntersectionWith()

◆ InverseMultiplicationBy()

◆ IsEmpty()

◆ IsFixed()

◆ IsIncludedIn()

◆ Max()

◆ Min()

◆ MultiplicationBy()

◆ Negation()

◆ NumIntervals()

◆ operator!=()

◆ operator<()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator[]()

◆ PartAroundZero()

◆ PositiveDivisionBySuperset()

◆ PositiveModuloBySuperset()

◆ QuadraticSuperset()

◆ RelaxIfTooComplex()

◆ SimplifyUsingImpliedDomain()

◆ Size()

◆ SmallestValue()

◆ SquareSuperset()

◆ ToString()

◆ UnionWith()

◆ ValueAtOrAfter()

◆ ValueAtOrBefore()

◆ Values() [1/2]

◆ Values() [2/2]

Friends And Related Symbol Documentation

◆ AbslHashValue