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

Classes
class	DomainIterator
	Allows to iterate over all values of a domain in order with for (const int64_t v : domain.Values()) { ... More...

struct	DomainIteratorBeginEnd

struct	DomainIteratorBeginEndWithOwnership

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_t value)
	Constructor for the common case of a singleton domain. More...

	Domain (int64_t left, int64_t right)
	Constructor for the common case of a single interval [left, right]. More...

std::vector< int64_t >	FlattenedIntervals () const
	This method returns the flattened list of interval bounds of the domain. More...

DomainIteratorBeginEnd	Values () const &

DomainIteratorBeginEndWithOwnership	Values () const &&

bool	IsEmpty () const
	Returns true if this is the empty set. More...

int64_t	Size () const
	Returns the number of elements in the domain. More...

int64_t	Min () const
	Returns the min value of the domain. More...

int64_t	Max () const
	Returns the max value of the domain. More...

int64_t	SmallestValue () const
	Returns the value closest to zero. More...

int64_t	ValueAtOrBefore (int64_t input) const
	Returns the closest value in the domain that is <= (resp. More...

int64_t	ValueAtOrAfter (int64_t input) const

bool	IsFixed () const
	Returns true iff the domain is reduced to a single value. More...

int64_t	FixedValue () const
	Returns the value of a fixed domain. More...

bool	Contains (int64_t 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_t 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_t 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_t coeff) const
	Returns {x ∈ Int64, ∃ e ∈ D, x = e / coeff}. More...

Domain	InverseMultiplicationBy (const int64_t coeff) const
	Returns {x ∈ Int64, ∃ e ∈ D, x * coeff = e}. More...

Domain	PositiveModuloBySuperset (const Domain &modulo) const
	Returns a superset of {x ∈ Int64, ∃ e ∈ D, ∃ m ∈ modulo, x = e % m }. More...

Domain	PositiveDivisionBySuperset (const Domain &divisor) const
	Returns a superset of {x ∈ Int64, ∃ e ∈ D, ∃ d ∈ divisor, x = e / d }. More...

Domain	SquareSuperset () const
	Returns a superset of {x ∈ Int64, ∃ y ∈ D, x = y * y }. 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_t > 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_t > flat_intervals)
	Same as FromIntervals() for a flattened representation (start, end, start, end, ...). More...

static Domain	FromVectorIntervals (const std::vector< std::vector< int64_t > > &intervals)
	This method is available in Python, Java and .NET. More...

static Domain	FromFlatIntervals (const std::vector< int64_t > &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 85 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 89 of file sorted_interval_list.h.

◆ Domain() [3/5]

Domain ( Domain && other )

inline

Move constructor.

Definition at line 98 of file sorted_interval_list.h.

◆ Domain() [4/5]

Domain ( int64_t value )

explicit

Constructor for the common case of a singleton domain.

Definition at line 121 of file sorted_interval_list.cc.

◆ Domain() [5/5]

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

Member Function Documentation

◆ AdditionWith()

Domain AdditionWith ( const Domain & domain ) const

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

Definition at line 378 of file sorted_interval_list.cc.

◆ AllValues()

Domain AllValues ( )

static

Returns the full domain Int64.

Definition at line 143 of file sorted_interval_list.cc.

◆ back()

ClosedInterval back ( ) const

inline

Definition at line 435 of file sorted_interval_list.h.

◆ begin()

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

inline

Definition at line 437 of file sorted_interval_list.h.

◆ Complement()

Domain Complement ( ) const

Returns the set Int64 ∖ D.

Definition at line 291 of file sorted_interval_list.cc.

◆ Contains()

bool Contains ( int64_t value ) const

Returns true iff value is in Domain.

Definition at line 267 of file sorted_interval_list.cc.

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

Definition at line 456 of file sorted_interval_list.cc.

◆ ContinuousMultiplicationBy() [2/2]

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

◆ DivisionBy()

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

◆ end()

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

inline

Definition at line 440 of file sorted_interval_list.h.

◆ FixedValue()

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

◆ FlattenedIntervals()

std::vector< int64_t > 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 631 of file sorted_interval_list.cc.

◆ FromFlatIntervals()

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

Definition at line 179 of file sorted_interval_list.cc.

◆ FromFlatSpanOfIntervals()

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

static

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

Definition at line 166 of file sorted_interval_list.cc.

◆ FromIntervals()

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

static

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

Definition at line 158 of file sorted_interval_list.cc.

◆ FromValues()

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

◆ FromVectorIntervals()

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

Definition at line 183 of file sorted_interval_list.cc.

◆ front()

ClosedInterval front ( ) const

inline

Definition at line 434 of file sorted_interval_list.h.

◆ IntersectionWith()

Domain IntersectionWith ( const Domain & domain ) const

Returns the intersection of D and domain.

Definition at line 328 of file sorted_interval_list.cc.

◆ intervals()

std::vector<ClosedInterval> intervals ( ) const

inline

Definition at line 448 of file sorted_interval_list.h.

◆ InverseMultiplicationBy()

Domain InverseMultiplicationBy ( const 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 488 of file sorted_interval_list.cc.

◆ IsEmpty()

bool IsEmpty ( ) const

Returns true if this is the empty set.

Definition at line 199 of file sorted_interval_list.cc.

◆ IsFixed()

bool IsFixed ( ) const

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

The domain must not be empty.

Definition at line 201 of file sorted_interval_list.cc.

◆ IsIncludedIn()

bool IsIncludedIn ( const Domain & domain ) const

Returns true iff D is included in the given domain.

Definition at line 278 of file sorted_interval_list.cc.

◆ Max()

int64_t Max ( ) const

Returns the max value of the domain.

The domain must not be empty.

Definition at line 220 of file sorted_interval_list.cc.

◆ Min()

int64_t Min ( ) const

Returns the min value of the domain.

The domain must not be empty.

Definition at line 215 of file sorted_interval_list.cc.

◆ MultiplicationBy()

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

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

Definition at line 307 of file sorted_interval_list.cc.

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

◆ operator!=()

bool operator!= ( const Domain & other ) const

inline

Definition at line 424 of file sorted_interval_list.h.

◆ operator<()

bool operator< ( const Domain & other ) const

Lexicographic order on the intervals() representation.

Definition at line 640 of file sorted_interval_list.cc.

◆ operator=() [1/2]

Domain& operator= ( const Domain & other )

inline

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

Definition at line 92 of file sorted_interval_list.h.

◆ operator=() [2/2]

Domain& operator= ( Domain && other )

inline

Move operator.

Definition at line 101 of file sorted_interval_list.h.

◆ operator==()

bool operator== ( const Domain & other ) const

inline

Definition at line 420 of file sorted_interval_list.h.

◆ operator[]()

ClosedInterval operator[] ( int i ) const

inline

Definition at line 436 of file sorted_interval_list.h.

◆ PositiveDivisionBySuperset()

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

◆ PositiveModuloBySuperset()

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

◆ RelaxIfTooComplex()

Domain RelaxIfTooComplex ( ) const

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

Definition at line 399 of file sorted_interval_list.cc.

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

Definition at line 583 of file sorted_interval_list.cc.

◆ Size()

int64_t Size ( ) const

Returns the number of elements in the domain.

It is capped at kint64max

Definition at line 203 of file sorted_interval_list.cc.

◆ SmallestValue()

int64_t SmallestValue ( ) const

Returns the value closest to zero.

If there is a tie, pick positive one.

Definition at line 225 of file sorted_interval_list.cc.

◆ SquareSuperset()

Domain SquareSuperset ( ) const

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

Definition at line 553 of file sorted_interval_list.cc.

◆ ToString()

std::string ToString ( ) const

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

Definition at line 655 of file sorted_interval_list.cc.

◆ UnionWith()

Domain UnionWith ( const Domain & domain ) const

Returns the union of D and domain.

Definition at line 367 of file sorted_interval_list.cc.

◆ ValueAtOrAfter()

int64_t ValueAtOrAfter ( int64_t input ) const

Definition at line 249 of file sorted_interval_list.cc.

◆ ValueAtOrBefore()

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

◆ Values() [1/2]

DomainIteratorBeginEnd Values ( ) const &

inline

Definition at line 214 of file sorted_interval_list.h.

◆ Values() [2/2]

DomainIteratorBeginEndWithOwnership Values ( ) const &&

inline

Definition at line 215 of file sorted_interval_list.h.

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

Detailed Description

Classes

Public Member Functions

Static Public Member Functions

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

◆ Complement()

◆ Contains()

◆ ContinuousMultiplicationBy() [1/2]

◆ ContinuousMultiplicationBy() [2/2]

◆ DivisionBy()

◆ end()

◆ FixedValue()

◆ FlattenedIntervals()

◆ FromFlatIntervals()

◆ FromFlatSpanOfIntervals()

◆ FromIntervals()

◆ FromValues()

◆ FromVectorIntervals()

◆ front()

◆ IntersectionWith()

◆ intervals()

◆ InverseMultiplicationBy()

◆ IsEmpty()

◆ IsFixed()

◆ IsIncludedIn()

◆ Max()

◆ Min()

◆ MultiplicationBy()

◆ Negation()

◆ NumIntervals()

◆ operator!=()

◆ operator<()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator[]()

◆ PositiveDivisionBySuperset()

◆ PositiveModuloBySuperset()

◆ RelaxIfTooComplex()

◆ SimplifyUsingImpliedDomain()

◆ Size()

◆ SmallestValue()

◆ SquareSuperset()

◆ ToString()

◆ UnionWith()

◆ ValueAtOrAfter()

◆ ValueAtOrBefore()

◆ Values() [1/2]

◆ Values() [2/2]