A grid. More...

#include <ppl.hh>

Public Types
typedef Coefficient	coefficient_type
	The numeric type of coefficients.

Public Member Functions
	Grid (dimension_type num_dimensions=0, Degenerate_Element kind=UNIVERSE)
	Builds a grid having the specified properties. More...

	Grid (const Congruence_System &cgs)
	Builds a grid, copying a system of congruences. More...

	Grid (Congruence_System &cgs, Recycle_Input dummy)
	Builds a grid, recycling a system of congruences. More...

	Grid (const Constraint_System &cs)
	Builds a grid, copying a system of constraints. More...

	Grid (Constraint_System &cs, Recycle_Input dummy)
	Builds a grid, recycling a system of constraints. More...

	Grid (const Grid_Generator_System &ggs)
	Builds a grid, copying a system of grid generators. More...

	Grid (Grid_Generator_System &ggs, Recycle_Input dummy)
	Builds a grid, recycling a system of grid generators. More...

template<typename Interval >
	Grid (const Box< Interval > &box, Complexity_Class complexity=ANY_COMPLEXITY)
	Builds a grid out of a box. More...

template<typename U >
	Grid (const BD_Shape< U > &bd, Complexity_Class complexity=ANY_COMPLEXITY)
	Builds a grid out of a bounded-difference shape. More...

template<typename U >
	Grid (const Octagonal_Shape< U > &os, Complexity_Class complexity=ANY_COMPLEXITY)
	Builds a grid out of an octagonal shape. More...

	Grid (const Polyhedron &ph, Complexity_Class complexity=ANY_COMPLEXITY)
	Builds a grid from a polyhedron using algorithms whose complexity does not exceed the one specified by `complexity`. If `complexity` is `ANY_COMPLEXITY`, then the grid built is the smallest one containing `ph`. More...

	Grid (const Grid &y, Complexity_Class complexity=ANY_COMPLEXITY)
	Ordinary copy constructor. More...

Grid &	operator= (const Grid &y)
	The assignment operator. (`*this` and `y` can be dimension-incompatible.)

Member Functions that Do Not Modify the Grid
dimension_type	space_dimension () const
	Returns the dimension of the vector space enclosing `*this`.

dimension_type	affine_dimension () const
	Returns , if `this` is empty; otherwise, returns the affine dimension of `this`.

Constraint_System	constraints () const
	Returns a system of equality constraints satisfied by `this` with the same affine dimension as `this`.

Constraint_System	minimized_constraints () const
	Returns a minimal system of equality constraints satisfied by `this` with the same affine dimension as `this`.

const Congruence_System &	congruences () const
	Returns the system of congruences.

const Congruence_System &	minimized_congruences () const
	Returns the system of congruences in minimal form.

const Grid_Generator_System &	grid_generators () const
	Returns the system of generators.

const Grid_Generator_System &	minimized_grid_generators () const
	Returns the minimized system of generators.

Poly_Con_Relation	relation_with (const Congruence &cg) const
	Returns the relations holding between `*this` and `cg`.

Poly_Gen_Relation	relation_with (const Grid_Generator &g) const
	Returns the relations holding between `*this` and `g`.

Poly_Gen_Relation	relation_with (const Generator &g) const
	Returns the relations holding between `*this` and `g`.

Poly_Con_Relation	relation_with (const Constraint &c) const
	Returns the relations holding between `*this` and `c`.

bool	is_empty () const
	Returns `true` if and only if `*this` is an empty grid.

bool	is_universe () const
	Returns `true` if and only if `*this` is a universe grid.

bool	is_topologically_closed () const
	Returns `true` if and only if `*this` is a topologically closed subset of the vector space. More...

bool	is_disjoint_from (const Grid &y) const
	Returns `true` if and only if `*this` and `y` are disjoint. More...

bool	is_discrete () const
	Returns `true` if and only if `*this` is discrete. More...

bool	is_bounded () const
	Returns `true` if and only if `*this` is bounded.

bool	contains_integer_point () const
	Returns `true` if and only if `*this` contains at least one integer point.

bool	constrains (Variable var) const
	Returns `true` if and only if `var` is constrained in `*this`. More...

bool	bounds_from_above (const Linear_Expression &expr) const
	Returns `true` if and only if `expr` is bounded in `*this`. More...

bool	bounds_from_below (const Linear_Expression &expr) const
	Returns `true` if and only if `expr` is bounded in `*this`. More...

bool	maximize (const Linear_Expression &expr, Coefficient &sup_n, Coefficient &sup_d, bool &maximum) const
	Returns `true` if and only if `this` is not empty and `expr` is bounded from above in `this`, in which case the supremum value is computed. More...

bool	maximize (const Linear_Expression &expr, Coefficient &sup_n, Coefficient &sup_d, bool &maximum, Generator &point) const
	Returns `true` if and only if `this` is not empty and `expr` is bounded from above in `this`, in which case the supremum value and a point where `expr` reaches it are computed. More...

bool	minimize (const Linear_Expression &expr, Coefficient &inf_n, Coefficient &inf_d, bool &minimum) const
	Returns `true` if and only if `this` is not empty and `expr` is bounded from below in `this`, in which case the infimum value is computed. More...

bool	minimize (const Linear_Expression &expr, Coefficient &inf_n, Coefficient &inf_d, bool &minimum, Generator &point) const
	Returns `true` if and only if `this` is not empty and `expr` is bounded from below in `this`, in which case the infimum value and a point where `expr` reaches it are computed. More...

bool	frequency (const Linear_Expression &expr, Coefficient &freq_n, Coefficient &freq_d, Coefficient &val_n, Coefficient &val_d) const
	Returns `true` if and only if `this` is not empty and frequency for `this` with respect to `expr` is defined, in which case the frequency and the value for `expr` that is closest to zero are computed. More...

bool	contains (const Grid &y) const
	Returns `true` if and only if `*this` contains `y`. More...

bool	strictly_contains (const Grid &y) const
	Returns `true` if and only if `*this` strictly contains `y`. More...

bool	OK (bool check_not_empty=false) const
	Checks if all the invariants are satisfied. More...

Space Dimension Preserving Member Functions that May Modify the Grid
void	add_congruence (const Congruence &cg)
	Adds a copy of congruence `cg` to `*this`. More...

void	add_grid_generator (const Grid_Generator &g)
	Adds a copy of grid generator `g` to the system of generators of `*this`. More...

void	add_congruences (const Congruence_System &cgs)
	Adds a copy of each congruence in `cgs` to `*this`. More...

void	add_recycled_congruences (Congruence_System &cgs)
	Adds the congruences in `cgs` to *this. More...

void	add_constraint (const Constraint &c)
	Adds to `*this` a congruence equivalent to constraint `c`. More...

void	add_constraints (const Constraint_System &cs)
	Adds to `*this` congruences equivalent to the constraints in `cs`. More...

void	add_recycled_constraints (Constraint_System &cs)
	Adds to `*this` congruences equivalent to the constraints in `cs`. More...

void	refine_with_congruence (const Congruence &cg)
	Uses a copy of the congruence `cg` to refine `*this`. More...

void	refine_with_congruences (const Congruence_System &cgs)
	Uses a copy of the congruences in `cgs` to refine `*this`. More...

void	refine_with_constraint (const Constraint &c)
	Uses a copy of the constraint `c` to refine `*this`. More...

void	refine_with_constraints (const Constraint_System &cs)
	Uses a copy of the constraints in `cs` to refine `*this`. More...

void	add_grid_generators (const Grid_Generator_System &gs)
	Adds a copy of the generators in `gs` to the system of generators of `*this`. More...

void	add_recycled_grid_generators (Grid_Generator_System &gs)
	Adds the generators in `gs` to the system of generators of `this`. More...

void	unconstrain (Variable var)
	Computes the cylindrification of `this` with respect to space dimension `var`, assigning the result to `this`. More...

void	unconstrain (const Variables_Set &vars)
	Computes the cylindrification of `this` with respect to the set of space dimensions `vars`, assigning the result to `this`. More...

void	intersection_assign (const Grid &y)
	Assigns to `this` the intersection of `this` and `y`. More...

void	upper_bound_assign (const Grid &y)
	Assigns to `this` the least upper bound of `this` and `y`. More...

bool	upper_bound_assign_if_exact (const Grid &y)
	If the upper bound of `*this` and `y` is exact it is assigned to `this` and `true` is returned, otherwise `false` is returned. More...

void	difference_assign (const Grid &y)
	Assigns to `this` the grid-difference of `this` and `y`. More...

bool	simplify_using_context_assign (const Grid &y)
	Assigns to `this` a meet-preserving simplification of `this` with respect to `y`. If `false` is returned, then the intersection is empty. More...

void	affine_image (Variable var, const Linear_Expression &expr, Coefficient_traits::const_reference denominator=Coefficient_one())
	Assigns to `*this` the affine image of `this` under the function mapping variable `var` to the affine expression specified by `expr` and `denominator`. More...

void	affine_preimage (Variable var, const Linear_Expression &expr, Coefficient_traits::const_reference denominator=Coefficient_one())
	Assigns to `this` the affine preimage of `this` under the function mapping variable `var` to the affine expression specified by `expr` and `denominator`. More...

void	generalized_affine_image (Variable var, Relation_Symbol relsym, const Linear_Expression &expr, Coefficient_traits::const_reference denominator=Coefficient_one(), Coefficient_traits::const_reference modulus=Coefficient_zero())
	Assigns to `this` the image of `this` with respect to the generalized affine relation $\mathrm{var}' = \frac{\mathrm{expr}}{\mathrm{denominator}} \pmod{\mathrm{modulus}}$ . More...

void	generalized_affine_preimage (Variable var, Relation_Symbol relsym, const Linear_Expression &expr, Coefficient_traits::const_reference denominator=Coefficient_one(), Coefficient_traits::const_reference modulus=Coefficient_zero())
	Assigns to `this` the preimage of `this` with respect to the generalized affine relation $\mathrm{var}' = \frac{\mathrm{expr}}{\mathrm{denominator}} \pmod{\mathrm{modulus}}$ . More...

void	generalized_affine_image (const Linear_Expression &lhs, Relation_Symbol relsym, const Linear_Expression &rhs, Coefficient_traits::const_reference modulus=Coefficient_zero())
	Assigns to `this` the image of `this` with respect to the generalized affine relation $\mathrm{lhs}' = \mathrm{rhs} \pmod{\mathrm{modulus}}$ . More...

void	generalized_affine_preimage (const Linear_Expression &lhs, Relation_Symbol relsym, const Linear_Expression &rhs, Coefficient_traits::const_reference modulus=Coefficient_zero())
	Assigns to `this` the preimage of `this` with respect to the generalized affine relation $\mathrm{lhs}' = \mathrm{rhs} \pmod{\mathrm{modulus}}$ . More...

void	bounded_affine_image (Variable var, const Linear_Expression &lb_expr, const Linear_Expression &ub_expr, Coefficient_traits::const_reference denominator=Coefficient_one())
	Assigns to `this` the image of `this` with respect to the bounded affine relation $\frac{\mathrm{lb\_expr}}{\mathrm{denominator}} \leq \mathrm{var}' \leq \frac{\mathrm{ub\_expr}}{\mathrm{denominator}}$ . More...

void	bounded_affine_preimage (Variable var, const Linear_Expression &lb_expr, const Linear_Expression &ub_expr, Coefficient_traits::const_reference denominator=Coefficient_one())
	Assigns to `this` the preimage of `this` with respect to the bounded affine relation $\frac{\mathrm{lb\_expr}}{\mathrm{denominator}} \leq \mathrm{var}' \leq \frac{\mathrm{ub\_expr}}{\mathrm{denominator}}$ . More...

void	time_elapse_assign (const Grid &y)
	Assigns to `this` the result of computing the time-elapse between `this` and `y`. More...

void	wrap_assign (const Variables_Set &vars, Bounded_Integer_Type_Width w, Bounded_Integer_Type_Representation r, Bounded_Integer_Type_Overflow o, const Constraint_System *cs_p=0, unsigned complexity_threshold=16, bool wrap_individually=true)
	Wraps the specified dimensions of the vector space. More...

void	drop_some_non_integer_points (Complexity_Class complexity=ANY_COMPLEXITY)
	Possibly tightens `*this` by dropping all points with non-integer coordinates. More...

void	drop_some_non_integer_points (const Variables_Set &vars, Complexity_Class complexity=ANY_COMPLEXITY)
	Possibly tightens `*this` by dropping all points with non-integer coordinates for the space dimensions corresponding to `vars`. More...

void	topological_closure_assign ()
	Assigns to `*this` its topological closure.

void	congruence_widening_assign (const Grid &y, unsigned *tp=NULL)
	Assigns to `this` the result of computing the Grid widening between `this` and `y` using congruence systems. More...

void	generator_widening_assign (const Grid &y, unsigned *tp=NULL)
	Assigns to `this` the result of computing the Grid widening between `this` and `y` using generator systems. More...

void	widening_assign (const Grid &y, unsigned *tp=NULL)
	Assigns to `this` the result of computing the Grid widening between `this` and `y`. More...

void	limited_congruence_extrapolation_assign (const Grid &y, const Congruence_System &cgs, unsigned *tp=NULL)
	Improves the result of the congruence variant of Grid widening computation by also enforcing those congruences in `cgs` that are satisfied by all the points of `*this`. More...

void	limited_generator_extrapolation_assign (const Grid &y, const Congruence_System &cgs, unsigned *tp=NULL)
	Improves the result of the generator variant of the Grid widening computation by also enforcing those congruences in `cgs` that are satisfied by all the points of `*this`. More...

void	limited_extrapolation_assign (const Grid &y, const Congruence_System &cgs, unsigned *tp=NULL)
	Improves the result of the Grid widening computation by also enforcing those congruences in `cgs` that are satisfied by all the points of `*this`. More...

Member Functions that May Modify the Dimension of the Vector Space
void	add_space_dimensions_and_embed (dimension_type m)
	Adds `m` new space dimensions and embeds the old grid in the new vector space. More...

void	add_space_dimensions_and_project (dimension_type m)
	Adds `m` new space dimensions to the grid and does not embed it in the new vector space. More...

void	concatenate_assign (const Grid &y)
	Assigns to `this` the concatenation of `this` and `y`, taken in this order. More...

void	remove_space_dimensions (const Variables_Set &vars)
	Removes all the specified dimensions from the vector space. More...

void	remove_higher_space_dimensions (dimension_type new_dimension)
	Removes the higher dimensions of the vector space so that the resulting space will have dimension `new_dimension`.. More...

template<typename Partial_Function >
void	map_space_dimensions (const Partial_Function &pfunc)
	Remaps the dimensions of the vector space according to a partial function. More...

void	expand_space_dimension (Variable var, dimension_type m)
	Creates `m` copies of the space dimension corresponding to `var`. More...

void	fold_space_dimensions (const Variables_Set &vars, Variable dest)
	Folds the space dimensions in `vars` into `dest`. More...

Miscellaneous Member Functions
	~Grid ()
	Destructor.

void	m_swap (Grid &y)
	Swaps `this` with grid `y`. (`this` and `y` can be dimension-incompatible.)

void	ascii_dump () const
	Writes to `std::cerr` an ASCII representation of `*this`.

void	ascii_dump (std::ostream &s) const
	Writes to `s` an ASCII representation of `*this`.

void	print () const
	Prints `*this` to `std::cerr` using `operator<<`.

bool	ascii_load (std::istream &s)
	Loads from `s` an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets `*this` accordingly. Returns `true` if successful, `false` otherwise.

memory_size_type	total_memory_in_bytes () const
	Returns the total size in bytes of the memory occupied by `*this`.

memory_size_type	external_memory_in_bytes () const
	Returns the size in bytes of the memory managed by `*this`.

int32_t	hash_code () const
	Returns a 32-bit hash code for `*this`. More...

Static Public Member Functions
static dimension_type	max_space_dimension ()
	Returns the maximum space dimension all kinds of Grid can handle.

static bool	can_recycle_congruence_systems ()
	Returns true indicating that this domain has methods that can recycle congruences.

static bool	can_recycle_constraint_systems ()
	Returns true indicating that this domain has methods that can recycle constraints.

Related Functions
(Note that these are not member functions.)
std::ostream &	operator<< (std::ostream &s, const Grid &gr)
	Output operator. More...

void	swap (Grid &x, Grid &y)
	Swaps `x` with `y`. More...

bool	operator== (const Grid &x, const Grid &y)
	Returns `true` if and only if `x` and `y` are the same grid. More...

bool	operator!= (const Grid &x, const Grid &y)
	Returns `true` if and only if `x` and `y` are different grids. More...

bool	operator!= (const Grid &x, const Grid &y)

void	swap (Grid &x, Grid &y)

Detailed Description

A grid.

An object of the class Grid represents a rational grid.

The domain of grids optimally supports:

all (proper and non-proper) congruences;
tautological and inconsistent constraints;
linear equality constraints (i.e., non-proper congruences).

Depending on the method, using a constraint that is not optimally supported by the domain will either raise an exception or result in a (possibly non-optimal) upward approximation.

The domain of grids support a concept of double description similar to the one developed for polyhedra: hence, a grid can be specified as either a finite system of congruences or a finite system of generators (see Section Rational Grids) and it is always possible to obtain either representation. That is, if we know the system of congruences, we can obtain from this a system of generators that define the same grid and vice versa. These systems can contain redundant members, or they can be in the minimal form.

A key attribute of any grid is its space dimension (the dimension $n \in \Nset$ of the enclosing vector space):

all grids, the empty ones included, are endowed with a space dimension;
most operations working on a grid and another object (another grid, a congruence, a generator, a set of variables, etc.) will throw an exception if the grid and the object are not dimension-compatible (see Section Space Dimensions and Dimension-compatibility for Grids);
the only ways in which the space dimension of a grid can be changed are with explicit calls to operators provided for that purpose, and with standard copy, assignment and swap operators.

Note that two different grids can be defined on the zero-dimension space: the empty grid and the universe grid $R^0$ .

: In all the examples it is assumed that variables x and y are defined (where they are used) as follows:
Variable x(0);

Variable y(1);

Example 1: The following code builds a grid corresponding to the even integer pairs in $\Rset^2$ , given as a system of congruences:
Congruence_System cgs;

cgs.insert((x %= 0) / 2);

cgs.insert((y %= 0) / 2);

Grid gr(cgs);

The following code builds the same grid as above, but starting from a system of generators specifying three of the points:
Grid_Generator_System gs;

gs.insert(grid_point(0*x + 0*y));

gs.insert(grid_point(0*x + 2*y));

gs.insert(grid_point(2*x + 0*y));

Grid gr(gs);

Example 2: The following code builds a grid corresponding to a line in $\Rset^2$ by adding a single congruence to the universe grid:
Congruence_System cgs;

cgs.insert(x - y == 0);

Grid gr(cgs);

The following code builds the same grid as above, but starting from a system of generators specifying a point and a line:
Grid_Generator_System gs;

gs.insert(grid_point(0*x + 0*y));

gs.insert(grid_line(x + y));

Grid gr(gs);

Example 3: The following code builds a grid corresponding to the integral points on the line in $\Rset^2$ constructed by adding an equality and congruence to the universe grid:
Congruence_System cgs;

cgs.insert(x - y == 0);

cgs.insert(x %= 0);

Grid gr(cgs);

The following code builds the same grid as above, but starting from a system of generators specifying a point and a parameter:
Grid_Generator_System gs;

gs.insert(grid_point(0*x + 0*y));

gs.insert(parameter(x + y));

Grid gr(gs);

Example 4: The following code builds the grid corresponding to a plane by creating the universe grid in $\Rset^2$ :
Grid gr(2);

The following code builds the same grid as above, but starting from the empty grid in $\Rset^2$ and inserting the appropriate generators (a point, and two lines).
Grid gr(2, EMPTY);

gr.add_grid_generator(grid_point(0*x + 0*y));

gr.add_grid_generator(grid_line(x));

gr.add_grid_generator(grid_line(y));

Note that a generator system must contain a point when describing a grid. To ensure that this is always the case it is required that the first generator inserted in an empty grid is a point (otherwise, an exception is thrown).

Example 5: The following code shows the use of the function add_space_dimensions_and_embed:
Grid gr(1);

gr.add_congruence(x == 2);

gr.add_space_dimensions_and_embed(1);

We build the universe grid in the 1-dimension space $\Rset$ . Then we add a single equality congruence, thus obtaining the grid corresponding to the singleton set $\{ 2 \} \sseq \Rset$ . After the last line of code, the resulting grid is
$\bigl\{\, (2, y)^\transpose \in \Rset^2 \bigm| y \in \Rset \,\bigr\}.$

Example 6: The following code shows the use of the function add_space_dimensions_and_project:
Grid gr(1);

gr.add_congruence(x == 2);

gr.add_space_dimensions_and_project(1);

The first two lines of code are the same as in Example 4 for add_space_dimensions_and_embed. After the last line of code, the resulting grid is the singleton set $\bigl\{ (2, 0)^\transpose \bigr\} \sseq \Rset^2$ .

Example 7: The following code shows the use of the function affine_image:
Grid gr(2, EMPTY);

gr.add_grid_generator(grid_point(0*x + 0*y));

gr.add_grid_generator(grid_point(4*x + 0*y));

gr.add_grid_generator(grid_point(0*x + 2*y));

Linear_Expression expr = x + 3;

gr.affine_image(x, expr);

In this example the starting grid is all the pairs of and in $\Rset^2$ where is an integer multiple of 4 and is an integer multiple of 2. The considered variable is and the affine expression is . The resulting grid is the given grid translated 3 integers to the right (all the pairs where is -1 plus an integer multiple of 4 and is an integer multiple of 2). Moreover, if the affine transformation for the same variable x is instead :
Linear_Expression expr = x + y;

the resulting grid is every second integral point along the line, with this line of points repeated at every fourth integral value along the axis. Instead, if we do not use an invertible transformation for the same variable; for example, the affine expression :
Linear_Expression expr = y;

the resulting grid is every second point along the line.

Example 8: The following code shows the use of the function affine_preimage:
Grid gr(2, EMPTY);

gr.add_grid_generator(grid_point(0*x + 0*y));

gr.add_grid_generator(grid_point(4*x + 0*y));

gr.add_grid_generator(grid_point(0*x + 2*y));

Linear_Expression expr = x + 3;

gr.affine_preimage(x, expr);

In this example the starting grid, var and the affine expression and the denominator are the same as in Example 6, while the resulting grid is similar but translated 3 integers to the left (all the pairs where is -3 plus an integer multiple of 4 and is an integer multiple of 2).. Moreover, if the affine transformation for x is
Linear_Expression expr = x + y;

the resulting grid is a similar grid to the result in Example 6, only the grid is slanted along . Instead, if we do not use an invertible transformation for the same variable x, for example, the affine expression :
Linear_Expression expr = y;

the resulting grid is every fourth line parallel to the axis.

Example 9: For this example we also use the variables:
Variable z(2);

Variable w(3);

The following code shows the use of the function remove_space_dimensions:
Grid_Generator_System gs;

gs.insert(grid_point(3*x + y +0*z + 2*w));

Grid gr(gs);

Variables_Set vars;

vars.insert(y);

vars.insert(z);

gr.remove_space_dimensions(vars);

The starting grid is the singleton set $\bigl\{ (3, 1, 0, 2)^\transpose \bigr\} \sseq \Rset^4$ , while the resulting grid is $\bigl\{ (3, 2)^\transpose \bigr\} \sseq \Rset^2$ . Be careful when removing space dimensions incrementally: since dimensions are automatically renamed after each application of the remove_space_dimensions operator, unexpected results can be obtained. For instance, by using the following code we would obtain a different result:
set<Variable> vars1;

vars1.insert(y);

gr.remove_space_dimensions(vars1);

set<Variable> vars2;

vars2.insert(z);

gr.remove_space_dimensions(vars2);

In this case, the result is the grid $\bigl\{(3, 0)^\transpose \bigr\} \sseq \Rset^2$ : when removing the set of dimensions vars2 we are actually removing variable of the original grid. For the same reason, the operator remove_space_dimensions is not idempotent: removing twice the same non-empty set of dimensions is never the same as removing them just once.

Constructor & Destructor Documentation

Parma_Polyhedra_Library::Grid::Grid	(	dimension_type	num_dimensions = `0`,
		Degenerate_Element	kind = `UNIVERSE`
	)

inlineexplicit

Builds a grid having the specified properties.

Parameters

num_dimensions	The number of dimensions of the vector space enclosing the grid;
kind	Specifies whether the universe or the empty grid has to be built.

Exceptions

std::length_error Thrown if num_dimensions exceeds the maximum allowed space dimension.

Parma_Polyhedra_Library::Grid::Grid ( const Congruence_System & cgs )

inlineexplicit

Builds a grid, copying a system of congruences.

The grid inherits the space dimension of the congruence system.

Parameters

cgs	The system of congruences defining the grid.

Exceptions

std::length_error Thrown if num_dimensions exceeds the maximum allowed space dimension.

Parma_Polyhedra_Library::Grid::Grid	(	Congruence_System &	cgs,
		Recycle_Input	dummy
	)

inline

Builds a grid, recycling a system of congruences.

The grid inherits the space dimension of the congruence system.

Parameters

cgs	The system of congruences defining the grid. Its data-structures may be recycled to build the grid.
dummy	A dummy tag to syntactically differentiate this one from the other constructors.

Exceptions

std::length_error Thrown if num_dimensions exceeds the maximum allowed space dimension.

Parma_Polyhedra_Library::Grid::Grid ( const Constraint_System & cs )

explicit

Builds a grid, copying a system of constraints.

The grid inherits the space dimension of the constraint system.

Parameters

cs	The system of constraints defining the grid.

Exceptions

std::invalid_argument	Thrown if the constraint system `cs` contains inequality constraints.
std::length_error	Thrown if `num_dimensions` exceeds the maximum allowed space dimension.

Parma_Polyhedra_Library::Grid::Grid	(	Constraint_System &	cs,
		Recycle_Input	dummy
	)

Builds a grid, recycling a system of constraints.

The grid inherits the space dimension of the constraint system.

Parameters

cs	The system of constraints defining the grid. Its data-structures may be recycled to build the grid.
dummy	A dummy tag to syntactically differentiate this one from the other constructors.

Exceptions

std::invalid_argument	Thrown if the constraint system `cs` contains inequality constraints.
std::length_error	Thrown if `num_dimensions` exceeds the maximum allowed space dimension.

Parma_Polyhedra_Library::Grid::Grid ( const Grid_Generator_System & ggs )

inlineexplicit

Builds a grid, copying a system of grid generators.

The grid inherits the space dimension of the generator system.

Parameters

ggs	The system of generators defining the grid.

Exceptions

std::invalid_argument	Thrown if the system of generators is not empty but has no points.
std::length_error	Thrown if `num_dimensions` exceeds the maximum allowed space dimension.

Parma_Polyhedra_Library::Grid::Grid	(	Grid_Generator_System &	ggs,
		Recycle_Input	dummy
	)

inline

Builds a grid, recycling a system of grid generators.

The grid inherits the space dimension of the generator system.

Parameters

ggs	The system of generators defining the grid. Its data-structures may be recycled to build the grid.
dummy	A dummy tag to syntactically differentiate this one from the other constructors.

Exceptions

std::invalid_argument	Thrown if the system of generators is not empty but has no points.
std::length_error	Thrown if `num_dimensions` exceeds the maximum allowed space dimension.

template<typename Interval >

Parma_Polyhedra_Library::Grid::Grid	(	const Box< Interval > &	box,
		Complexity_Class	complexity = `ANY_COMPLEXITY`
	)

explicit

Builds a grid out of a box.

The grid inherits the space dimension of the box. The built grid is the most precise grid that includes the box.

Parameters

box	The box representing the grid to be built.
complexity	This argument is ignored as the algorithm used has polynomial complexity.

Exceptions

std::length_error Thrown if the space dimension of box exceeds the maximum allowed space dimension.

template<typename U >

Parma_Polyhedra_Library::Grid::Grid	(	const BD_Shape< U > &	bd,
		Complexity_Class	complexity = `ANY_COMPLEXITY`
	)

inlineexplicit

Builds a grid out of a bounded-difference shape.

The grid inherits the space dimension of the BDS. The built grid is the most precise grid that includes the BDS.

Parameters

bd	The BDS representing the grid to be built.
complexity	This argument is ignored as the algorithm used has polynomial complexity.

Exceptions

std::length_error Thrown if the space dimension of bd exceeds the maximum allowed space dimension.

template<typename U >

Parma_Polyhedra_Library::Grid::Grid	(	const Octagonal_Shape< U > &	os,
		Complexity_Class	complexity = `ANY_COMPLEXITY`
	)

inlineexplicit

Builds a grid out of an octagonal shape.

The grid inherits the space dimension of the octagonal shape. The built grid is the most precise grid that includes the octagonal shape.

Parameters

os	The octagonal shape representing the grid to be built.
complexity	This argument is ignored as the algorithm used has polynomial complexity.

Exceptions

std::length_error Thrown if the space dimension of os exceeds the maximum allowed space dimension.

Parma_Polyhedra_Library::Grid::Grid	(	const Polyhedron &	ph,
		Complexity_Class	complexity = `ANY_COMPLEXITY`
	)

explicit

Builds a grid from a polyhedron using algorithms whose complexity does not exceed the one specified by complexity. If complexity is ANY_COMPLEXITY, then the grid built is the smallest one containing ph.

The grid inherits the space dimension of polyhedron.

Parameters

ph	The polyhedron.
complexity	The complexity class.

Exceptions

std::length_error Thrown if num_dimensions exceeds the maximum allowed space dimension.

Parma_Polyhedra_Library::Grid::Grid	(	const Grid &	y,
		Complexity_Class	complexity = `ANY_COMPLEXITY`
	)

Ordinary copy constructor.

The complexity argument is ignored.

Member Function Documentation

bool Parma_Polyhedra_Library::Grid::is_topologically_closed ( ) const

Returns true if and only if *this is a topologically closed subset of the vector space.

A grid is always topologically closed.

bool Parma_Polyhedra_Library::Grid::is_disjoint_from ( const Grid & y ) const

Returns true if and only if *this and y are disjoint.

Exceptions

std::invalid_argument Thrown if x and y are dimension-incompatible.

bool Parma_Polyhedra_Library::Grid::is_discrete ( ) const

Returns true if and only if *this is discrete.

A grid is discrete if it can be defined by a generator system which contains only points and parameters. This includes the empty grid and any grid in dimension zero.

bool Parma_Polyhedra_Library::Grid::constrains ( Variable var ) const

Returns true if and only if var is constrained in *this.

Exceptions

std::invalid_argument Thrown if var is not a space dimension of *this.

bool Parma_Polyhedra_Library::Grid::bounds_from_above ( const Linear_Expression & expr ) const

inline

Returns true if and only if expr is bounded in *this.

This method is the same as bounds_from_below.

Exceptions

std::invalid_argument Thrown if expr and *this are dimension-incompatible.

bool Parma_Polyhedra_Library::Grid::bounds_from_below ( const Linear_Expression & expr ) const

inline

Returns true if and only if expr is bounded in *this.

This method is the same as bounds_from_above.

Exceptions

std::invalid_argument Thrown if expr and *this are dimension-incompatible.

bool Parma_Polyhedra_Library::Grid::maximize	(	const Linear_Expression &	expr,
		Coefficient &	sup_n,
		Coefficient &	sup_d,
		bool &	maximum
	)		const

inline

Returns true if and only if *this is not empty and expr is bounded from above in *this, in which case the supremum value is computed.

Parameters

expr	The linear expression to be maximized subject to `*this`;
sup_n	The numerator of the supremum value;
sup_d	The denominator of the supremum value;
maximum	`true` if the supremum value can be reached in `this`. Always `true` when `this` bounds `expr`. Present for interface compatibility with class Polyhedron, where closure points can result in a value of false.

Exceptions

std::invalid_argument Thrown if expr and *this are dimension-incompatible.

If *this is empty or expr is not bounded by *this, false is returned and sup_n, sup_d and maximum are left untouched.

bool Parma_Polyhedra_Library::Grid::maximize	(	const Linear_Expression &	expr,
		Coefficient &	sup_n,
		Coefficient &	sup_d,
		bool &	maximum,
		Generator &	point
	)		const

inline

Returns true if and only if *this is not empty and expr is bounded from above in *this, in which case the supremum value and a point where expr reaches it are computed.

Parameters

expr	The linear expression to be maximized subject to `*this`;
sup_n	The numerator of the supremum value;
sup_d	The denominator of the supremum value;
maximum	`true` if the supremum value can be reached in `this`. Always `true` when `this` bounds `expr`. Present for interface compatibility with class Polyhedron, where closure points can result in a value of false;
point	When maximization succeeds, will be assigned a point where `expr` reaches its supremum value.

Exceptions

std::invalid_argument Thrown if expr and *this are dimension-incompatible.

If *this is empty or expr is not bounded by *this, false is returned and sup_n, sup_d, maximum and point are left untouched.

bool Parma_Polyhedra_Library::Grid::minimize	(	const Linear_Expression &	expr,
		Coefficient &	inf_n,
		Coefficient &	inf_d,
		bool &	minimum
	)		const

inline

Returns true if and only if *this is not empty and expr is bounded from below in *this, in which case the infimum value is computed.

Parameters

expr	The linear expression to be minimized subject to `*this`;
inf_n	The numerator of the infimum value;
inf_d	The denominator of the infimum value;
minimum	`true` if the is the infimum value can be reached in `this`. Always `true` when `this` bounds `expr`. Present for interface compatibility with class Polyhedron, where closure points can result in a value of false.

Exceptions

std::invalid_argument Thrown if expr and *this are dimension-incompatible.

If *this is empty or expr is not bounded from below, false is returned and inf_n, inf_d and minimum are left untouched.

bool Parma_Polyhedra_Library::Grid::minimize	(	const Linear_Expression &	expr,
		Coefficient &	inf_n,
		Coefficient &	inf_d,
		bool &	minimum,
		Generator &	point
	)		const

inline

Returns true if and only if *this is not empty and expr is bounded from below in *this, in which case the infimum value and a point where expr reaches it are computed.

Parameters

expr	The linear expression to be minimized subject to `*this`;
inf_n	The numerator of the infimum value;
inf_d	The denominator of the infimum value;
minimum	`true` if the is the infimum value can be reached in `this`. Always `true` when `this` bounds `expr`. Present for interface compatibility with class Polyhedron, where closure points can result in a value of false;
point	When minimization succeeds, will be assigned a point where `expr` reaches its infimum value.

Exceptions

std::invalid_argument Thrown if expr and *this are dimension-incompatible.

If *this is empty or expr is not bounded from below, false is returned and inf_n, inf_d, minimum and point are left untouched.

bool Parma_Polyhedra_Library::Grid::frequency	(	const Linear_Expression &	expr,
		Coefficient &	freq_n,
		Coefficient &	freq_d,
		Coefficient &	val_n,
		Coefficient &	val_d
	)		const

Returns true if and only if *this is not empty and frequency for *this with respect to expr is defined, in which case the frequency and the value for expr that is closest to zero are computed.

Parameters

expr	The linear expression for which the frequency is needed;
freq_n	The numerator of the maximum frequency of `expr`;
freq_d	The denominator of the maximum frequency of `expr`;
val_n	The numerator of them value of `expr` at a point in the grid that is closest to zero;
val_d	The denominator of a value of `expr` at a point in the grid that is closest to zero;

Exceptions

std::invalid_argument Thrown if expr and *this are dimension-incompatible.

If *this is empty or frequency is undefined with respect to expr, then false is returned and freq_n, freq_d, val_n and val_d are left untouched.

bool Parma_Polyhedra_Library::Grid::contains ( const Grid & y ) const

Returns true if and only if *this contains y.

Exceptions

std::invalid_argument Thrown if *this and y are dimension-incompatible.

bool Parma_Polyhedra_Library::Grid::strictly_contains ( const Grid & y ) const

inline

Returns true if and only if *this strictly contains y.

Exceptions

std::invalid_argument Thrown if *this and y are dimension-incompatible.

bool Parma_Polyhedra_Library::Grid::OK ( bool check_not_empty = false ) const

Checks if all the invariants are satisfied.

Returns: true if and only if *this satisfies all the invariants and either check_not_empty is false or *this is not empty.

Parameters

check_not_empty true if and only if, in addition to checking the invariants, *this must be checked to be not empty.

The check is performed so as to intrude as little as possible. If the library has been compiled with run-time assertions enabled, error messages are written on std::cerr in case invariants are violated. This is useful for the purpose of debugging the library.

void Parma_Polyhedra_Library::Grid::add_congruence ( const Congruence & cg )

inline

Adds a copy of congruence cg to *this.

Exceptions

std::invalid_argument Thrown if *this and congruence cg are dimension-incompatible.

void Parma_Polyhedra_Library::Grid::add_grid_generator ( const Grid_Generator & g )

Adds a copy of grid generator g to the system of generators of *this.

Exceptions

std::invalid_argument Thrown if *this and generator g are dimension-incompatible, or if *this is an empty grid and g is not a point.

void Parma_Polyhedra_Library::Grid::add_congruences ( const Congruence_System & cgs )

inline

Adds a copy of each congruence in cgs to *this.

Parameters

cgs	Contains the congruences that will be added to the system of congruences of `*this`.

Exceptions

std::invalid_argument Thrown if *this and cgs are dimension-incompatible.

void Parma_Polyhedra_Library::Grid::add_recycled_congruences ( Congruence_System & cgs )

Adds the congruences in cgs to *this.

Parameters

cgs	The congruence system to be added to `*this`. The congruences in `cgs` may be recycled.

Exceptions

std::invalid_argument Thrown if *this and cgs are dimension-incompatible.

Warning: The only assumption that can be made about cgs upon successful or exceptional return is that it can be safely destroyed.

void Parma_Polyhedra_Library::Grid::add_constraint ( const Constraint & c )

inline

Adds to *this a congruence equivalent to constraint c.

Parameters

c	The constraint to be added.

Exceptions

std::invalid_argument Thrown if *this and c are dimension-incompatible or if constraint c is not optimally supported by the grid domain.

void Parma_Polyhedra_Library::Grid::add_constraints ( const Constraint_System & cs )

Adds to *this congruences equivalent to the constraints in cs.

Parameters

cs	The constraints to be added.

Exceptions

std::invalid_argument Thrown if *this and cs are dimension-incompatible or if cs contains a constraint which is not optimally supported by the grid domain.

void Parma_Polyhedra_Library::Grid::add_recycled_constraints ( Constraint_System & cs )

inline

Adds to *this congruences equivalent to the constraints in cs.

Parameters

cs	The constraints to be added. They may be recycled.

Exceptions

std::invalid_argument Thrown if *this and cs are dimension-incompatible or if cs contains a constraint which is not optimally supported by the grid domain.

Warning: The only assumption that can be made about cs upon successful or exceptional return is that it can be safely destroyed.

void Parma_Polyhedra_Library::Grid::refine_with_congruence ( const Congruence & cg )

inline

Uses a copy of the congruence cg to refine *this.

Parameters

cg	The congruence used.

Exceptions

std::invalid_argument Thrown if *this and congruence cg are dimension-incompatible.

void Parma_Polyhedra_Library::Grid::refine_with_congruences ( const Congruence_System & cgs )

inline

Uses a copy of the congruences in cgs to refine *this.

Parameters

cgs	The congruences used.

Exceptions

std::invalid_argument Thrown if *this and cgs are dimension-incompatible.

void Parma_Polyhedra_Library::Grid::refine_with_constraint ( const Constraint & c )

Uses a copy of the constraint c to refine *this.

Parameters

c	The constraint used. If it is not an equality, it will be ignored

Exceptions

std::invalid_argument Thrown if *this and c are dimension-incompatible.

void Parma_Polyhedra_Library::Grid::refine_with_constraints ( const Constraint_System & cs )

Uses a copy of the constraints in cs to refine *this.

Parameters

cs	The constraints used. Constraints that are not equalities are ignored.

Exceptions

std::invalid_argument Thrown if *this and cs are dimension-incompatible.

void Parma_Polyhedra_Library::Grid::add_grid_generators ( const Grid_Generator_System & gs )

Adds a copy of the generators in gs to the system of generators of *this.

Parameters

gs	Contains the generators that will be added to the system of generators of `*this`.

Exceptions

std::invalid_argument Thrown if *this and gs are dimension-incompatible, or if *this is empty and the system of generators gs is not empty, but has no points.

void Parma_Polyhedra_Library::Grid::add_recycled_grid_generators ( Grid_Generator_System & gs )

Adds the generators in gs to the system of generators of this.

Parameters

gs	The generator system to be added to `*this`. The generators in `gs` may be recycled.

Exceptions

std::invalid_argument Thrown if *this and gs are dimension-incompatible.

Warning: The only assumption that can be made about gs upon successful or exceptional return is that it can be safely destroyed.

void Parma_Polyhedra_Library::Grid::unconstrain ( Variable var )

Computes the cylindrification of *this with respect to space dimension var, assigning the result to *this.

Parameters

var	The space dimension that will be unconstrained.

Exceptions

std::invalid_argument Thrown if var is not a space dimension of *this.

void Parma_Polyhedra_Library::Grid::unconstrain ( const Variables_Set & vars )

Computes the cylindrification of *this with respect to the set of space dimensions vars, assigning the result to *this.

Parameters

vars	The set of space dimension that will be unconstrained.

Exceptions

std::invalid_argument Thrown if *this is dimension-incompatible with one of the Variable objects contained in vars.

void Parma_Polyhedra_Library::Grid::intersection_assign ( const Grid & y )

Assigns to *this the intersection of *this and y.

Exceptions

std::invalid_argument Thrown if *this and y are dimension-incompatible.

void Parma_Polyhedra_Library::Grid::upper_bound_assign ( const Grid & y )

Assigns to *this the least upper bound of *this and y.

Exceptions

std::invalid_argument Thrown if *this and y are dimension-incompatible.

bool Parma_Polyhedra_Library::Grid::upper_bound_assign_if_exact ( const Grid & y )

If the upper bound of *this and y is exact it is assigned to this and true is returned, otherwise false is returned.

Exceptions

std::invalid_argument Thrown if *this and y are dimension-incompatible.

void Parma_Polyhedra_Library::Grid::difference_assign ( const Grid & y )

Assigns to *this the grid-difference of *this and y.

The grid difference between grids x and y is the smallest grid containing all the points from x and y that are only in x.

Exceptions

std::invalid_argument Thrown if *this and y are dimension-incompatible.

bool Parma_Polyhedra_Library::Grid::simplify_using_context_assign ( const Grid & y )

Assigns to *this a meet-preserving simplification of *this with respect to y. If false is returned, then the intersection is empty.

Exceptions

std::invalid_argument Thrown if *this and y are topology-incompatible or dimension-incompatible.

void Parma_Polyhedra_Library::Grid::affine_image	(	Variable	var,
		const Linear_Expression &	expr,
		Coefficient_traits::const_reference	denominator = `Coefficient_one()`
	)

Assigns to *this the affine image of this under the function mapping variable var to the affine expression specified by expr and denominator.

Parameters

var	The variable to which the affine expression is assigned;
expr	The numerator of the affine expression;
denominator	The denominator of the affine expression (optional argument with default value 1).

Exceptions

std::invalid_argument Thrown if denominator is zero or if expr and *this are dimension-incompatible or if var is not a space dimension of *this.

void Parma_Polyhedra_Library::Grid::affine_preimage	(	Variable	var,
		const Linear_Expression &	expr,
		Coefficient_traits::const_reference	denominator = `Coefficient_one()`
	)

Assigns to *this the affine preimage of *this under the function mapping variable var to the affine expression specified by expr and denominator.

Parameters

var	The variable to which the affine expression is substituted;
expr	The numerator of the affine expression;
denominator	The denominator of the affine expression (optional argument with default value 1).

Exceptions

std::invalid_argument Thrown if denominator is zero or if expr and *this are dimension-incompatible or if var is not a space dimension of *this.

void Parma_Polyhedra_Library::Grid::generalized_affine_image	(	Variable	var,
		Relation_Symbol	relsym,
		const Linear_Expression &	expr,
		Coefficient_traits::const_reference	denominator = `Coefficient_one()`,
		Coefficient_traits::const_reference	modulus = `Coefficient_zero()`
	)

Assigns to *this the image of *this with respect to the generalized affine relation $\mathrm{var}' = \frac{\mathrm{expr}}{\mathrm{denominator}} \pmod{\mathrm{modulus}}$ .

Parameters

var	The left hand side variable of the generalized affine relation;
relsym	The relation symbol where EQUAL is the symbol for a congruence relation;
expr	The numerator of the right hand side affine expression;
denominator	The denominator of the right hand side affine expression. Optional argument with an automatic value of one;
modulus	The modulus of the congruence lhs %= rhs. A modulus of zero indicates lhs == rhs. Optional argument with an automatic value of zero.

Exceptions

std::invalid_argument Thrown if denominator is zero or if expr and *this are dimension-incompatible or if var is not a space dimension of this.

void Parma_Polyhedra_Library::Grid::generalized_affine_preimage	(	Variable	var,
		Relation_Symbol	relsym,
		const Linear_Expression &	expr,
		Coefficient_traits::const_reference	denominator = `Coefficient_one()`,
		Coefficient_traits::const_reference	modulus = `Coefficient_zero()`
	)

Assigns to *this the preimage of *this with respect to the generalized affine relation $\mathrm{var}' = \frac{\mathrm{expr}}{\mathrm{denominator}} \pmod{\mathrm{modulus}}$ .

Parameters

var	The left hand side variable of the generalized affine relation;
relsym	The relation symbol where EQUAL is the symbol for a congruence relation;
expr	The numerator of the right hand side affine expression;
denominator	The denominator of the right hand side affine expression. Optional argument with an automatic value of one;
modulus	The modulus of the congruence lhs %= rhs. A modulus of zero indicates lhs == rhs. Optional argument with an automatic value of zero.

Exceptions

std::invalid_argument Thrown if denominator is zero or if expr and *this are dimension-incompatible or if var is not a space dimension of this.

void Parma_Polyhedra_Library::Grid::generalized_affine_image	(	const Linear_Expression &	lhs,
		Relation_Symbol	relsym,
		const Linear_Expression &	rhs,
		Coefficient_traits::const_reference	modulus = `Coefficient_zero()`
	)

Assigns to *this the image of *this with respect to the generalized affine relation $\mathrm{lhs}' = \mathrm{rhs} \pmod{\mathrm{modulus}}$ .

Parameters

lhs	The left hand side affine expression.
relsym	The relation symbol where EQUAL is the symbol for a congruence relation;
rhs	The right hand side affine expression.
modulus	The modulus of the congruence lhs %= rhs. A modulus of zero indicates lhs == rhs. Optional argument with an automatic value of zero.

Exceptions

std::invalid_argument Thrown if *this is dimension-incompatible with lhs or rhs.

void Parma_Polyhedra_Library::Grid::generalized_affine_preimage	(	const Linear_Expression &	lhs,
		Relation_Symbol	relsym,
		const Linear_Expression &	rhs,
		Coefficient_traits::const_reference	modulus = `Coefficient_zero()`
	)

Assigns to *this the preimage of *this with respect to the generalized affine relation $\mathrm{lhs}' = \mathrm{rhs} \pmod{\mathrm{modulus}}$ .

Parameters

lhs	The left hand side affine expression;
relsym	The relation symbol where EQUAL is the symbol for a congruence relation;
rhs	The right hand side affine expression;
modulus	The modulus of the congruence lhs %= rhs. A modulus of zero indicates lhs == rhs. Optional argument with an automatic value of zero.

Exceptions

std::invalid_argument Thrown if *this is dimension-incompatible with lhs or rhs.

void Parma_Polyhedra_Library::Grid::bounded_affine_image	(	Variable	var,
		const Linear_Expression &	lb_expr,
		const Linear_Expression &	ub_expr,
		Coefficient_traits::const_reference	denominator = `Coefficient_one()`
	)

Assigns to *this the image of *this with respect to the bounded affine relation $\frac{\mathrm{lb\_expr}}{\mathrm{denominator}} \leq \mathrm{var}' \leq \frac{\mathrm{ub\_expr}}{\mathrm{denominator}}$ .

Parameters

var	The variable updated by the affine relation;
lb_expr	The numerator of the lower bounding affine expression;
ub_expr	The numerator of the upper bounding affine expression;
denominator	The (common) denominator for the lower and upper bounding affine expressions (optional argument with default value 1).

Exceptions

std::invalid_argument Thrown if denominator is zero or if lb_expr (resp., ub_expr) and *this are dimension-incompatible or if var is not a space dimension of *this.

void Parma_Polyhedra_Library::Grid::bounded_affine_preimage	(	Variable	var,
		const Linear_Expression &	lb_expr,
		const Linear_Expression &	ub_expr,
		Coefficient_traits::const_reference	denominator = `Coefficient_one()`
	)

Assigns to *this the preimage of *this with respect to the bounded affine relation $\frac{\mathrm{lb\_expr}}{\mathrm{denominator}} \leq \mathrm{var}' \leq \frac{\mathrm{ub\_expr}}{\mathrm{denominator}}$ .

Parameters

var	The variable updated by the affine relation;
lb_expr	The numerator of the lower bounding affine expression;
ub_expr	The numerator of the upper bounding affine expression;
denominator	The (common) denominator for the lower and upper bounding affine expressions (optional argument with default value 1).

Exceptions

std::invalid_argument Thrown if denominator is zero or if lb_expr (resp., ub_expr) and *this are dimension-incompatible or if var is not a space dimension of *this.

void Parma_Polyhedra_Library::Grid::time_elapse_assign ( const Grid & y )

Assigns to *this the result of computing the time-elapse between *this and y.

Exceptions

std::invalid_argument Thrown if *this and y are dimension-incompatible.

void Parma_Polyhedra_Library::Grid::wrap_assign	(	const Variables_Set &	vars,
		Bounded_Integer_Type_Width	w,
		Bounded_Integer_Type_Representation	r,
		Bounded_Integer_Type_Overflow	o,
		const Constraint_System *	cs_p = `0`,
		unsigned	complexity_threshold = `16`,
		bool	wrap_individually = `true`
	)

Wraps the specified dimensions of the vector space.

Parameters

vars	The set of Variable objects corresponding to the space dimensions to be wrapped.
w	The width of the bounded integer type corresponding to all the dimensions to be wrapped.
r	The representation of the bounded integer type corresponding to all the dimensions to be wrapped.
o	The overflow behavior of the bounded integer type corresponding to all the dimensions to be wrapped.
cs_p	Possibly null pointer to a constraint system. This argument is for compatibility with wrap_assign() for the other domains and only checked for dimension-compatibility.
complexity_threshold	A precision parameter of the wrapping operator. This argument is for compatibility with wrap_assign() for the other domains and is ignored.
wrap_individually	`true` if the dimensions should be wrapped individually. As wrapping dimensions collectively does not improve the precision, this argument is ignored.

Exceptions

std::invalid_argument Thrown if *this is dimension-incompatible with one of the Variable objects contained in vars or with *cs_p.

Warning: It is assumed that variables in Vars represent integers. Thus, where the extra cost is negligible, the integrality of these variables is enforced; possibly causing a non-integral grid to become empty.

void Parma_Polyhedra_Library::Grid::drop_some_non_integer_points ( Complexity_Class complexity = ANY_COMPLEXITY )

Possibly tightens *this by dropping all points with non-integer coordinates.

Parameters

complexity This argument is ignored as the algorithm used has polynomial complexity.

void Parma_Polyhedra_Library::Grid::drop_some_non_integer_points	(	const Variables_Set &	vars,
		Complexity_Class	complexity = `ANY_COMPLEXITY`
	)

Possibly tightens *this by dropping all points with non-integer coordinates for the space dimensions corresponding to vars.

Parameters

vars	Points with non-integer coordinates for these variables/space-dimensions can be discarded.
complexity	This argument is ignored as the algorithm used has polynomial complexity.

void Parma_Polyhedra_Library::Grid::congruence_widening_assign	(	const Grid &	y,
		unsigned *	tp = `NULL`
	)

Assigns to *this the result of computing the Grid widening between *this and y using congruence systems.

Parameters

y	A grid that must be contained in `*this`;
tp	An optional pointer to an unsigned variable storing the number of available tokens (to be used when applying the widening with tokens delay technique).

Exceptions

std::invalid_argument Thrown if *this and y are dimension-incompatible.

void Parma_Polyhedra_Library::Grid::generator_widening_assign	(	const Grid &	y,
		unsigned *	tp = `NULL`
	)

Assigns to *this the result of computing the Grid widening between *this and y using generator systems.

Parameters

y	A grid that must be contained in `*this`;
tp	An optional pointer to an unsigned variable storing the number of available tokens (to be used when applying the widening with tokens delay technique).

Exceptions

std::invalid_argument Thrown if *this and y are dimension-incompatible.

void Parma_Polyhedra_Library::Grid::widening_assign	(	const Grid &	y,
		unsigned *	tp = `NULL`
	)

Assigns to *this the result of computing the Grid widening between *this and y.

This widening uses either the congruence or generator systems depending on which of the systems describing x and y are up to date and minimized.

Parameters

y	A grid that must be contained in `*this`;
tp	An optional pointer to an unsigned variable storing the number of available tokens (to be used when applying the widening with tokens delay technique).

Exceptions

std::invalid_argument Thrown if *this and y are dimension-incompatible.

void Parma_Polyhedra_Library::Grid::limited_congruence_extrapolation_assign	(	const Grid &	y,
		const Congruence_System &	cgs,
		unsigned *	tp = `NULL`
	)

Improves the result of the congruence variant of Grid widening computation by also enforcing those congruences in cgs that are satisfied by all the points of *this.

Parameters

y	A grid that must be contained in `*this`;
cgs	The system of congruences used to improve the widened grid;
tp	An optional pointer to an unsigned variable storing the number of available tokens (to be used when applying the widening with tokens delay technique).

Exceptions

std::invalid_argument Thrown if *this, y and cgs are dimension-incompatible.

void Parma_Polyhedra_Library::Grid::limited_generator_extrapolation_assign	(	const Grid &	y,
		const Congruence_System &	cgs,
		unsigned *	tp = `NULL`
	)

Improves the result of the generator variant of the Grid widening computation by also enforcing those congruences in cgs that are satisfied by all the points of *this.

Parameters

y	A grid that must be contained in `*this`;
cgs	The system of congruences used to improve the widened grid;
tp	An optional pointer to an unsigned variable storing the number of available tokens (to be used when applying the widening with tokens delay technique).

Exceptions

std::invalid_argument Thrown if *this, y and cgs are dimension-incompatible.

void Parma_Polyhedra_Library::Grid::limited_extrapolation_assign	(	const Grid &	y,
		const Congruence_System &	cgs,
		unsigned *	tp = `NULL`
	)

Improves the result of the Grid widening computation by also enforcing those congruences in cgs that are satisfied by all the points of *this.

Parameters

y	A grid that must be contained in `*this`;
cgs	The system of congruences used to improve the widened grid;
tp	An optional pointer to an unsigned variable storing the number of available tokens (to be used when applying the widening with tokens delay technique).

Exceptions

std::invalid_argument Thrown if *this, y and cgs are dimension-incompatible.

void Parma_Polyhedra_Library::Grid::add_space_dimensions_and_embed ( dimension_type m )

Adds m new space dimensions and embeds the old grid in the new vector space.

Parameters

m	The number of dimensions to add.

Exceptions

std::length_error Thrown if adding m new space dimensions would cause the vector space to exceed dimension max_space_dimension().

The new space dimensions will be those having the highest indexes in the new grid, which is characterized by a system of congruences in which the variables which are the new dimensions can have any value. For instance, when starting from the grid $\cL \sseq \Rset^2$ and adding a third space dimension, the result will be the grid

$\bigl\{\, (x, y, z)^\transpose \in \Rset^3 \bigm| (x, y)^\transpose \in \cL \,\bigr\}.$

void Parma_Polyhedra_Library::Grid::add_space_dimensions_and_project ( dimension_type m )

Adds m new space dimensions to the grid and does not embed it in the new vector space.

Parameters

m	The number of space dimensions to add.

Exceptions

std::length_error Thrown if adding m new space dimensions would cause the vector space to exceed dimension max_space_dimension().

The new space dimensions will be those having the highest indexes in the new grid, which is characterized by a system of congruences in which the variables running through the new dimensions are all constrained to be equal to 0. For instance, when starting from the grid $\cL \sseq \Rset^2$ and adding a third space dimension, the result will be the grid

$\bigl\{\, (x, y, 0)^\transpose \in \Rset^3 \bigm| (x, y)^\transpose \in \cL \,\bigr\}.$

void Parma_Polyhedra_Library::Grid::concatenate_assign ( const Grid & y )

Assigns to *this the concatenation of *this and y, taken in this order.

Exceptions

std::length_error Thrown if the concatenation would cause the vector space to exceed dimension max_space_dimension().

void Parma_Polyhedra_Library::Grid::remove_space_dimensions ( const Variables_Set & vars )

Removes all the specified dimensions from the vector space.

Parameters

vars	The set of Variable objects corresponding to the space dimensions to be removed.

Exceptions

std::invalid_argument Thrown if *this is dimension-incompatible with one of the Variable objects contained in vars.

void Parma_Polyhedra_Library::Grid::remove_higher_space_dimensions ( dimension_type new_dimension )

Removes the higher dimensions of the vector space so that the resulting space will have dimension new_dimension..

Exceptions

std::invalid_argument Thrown if new_dimensions is greater than the space dimension of *this.

template<typename Partial_Function >

void Parma_Polyhedra_Library::Grid::map_space_dimensions ( const Partial_Function & pfunc )

Remaps the dimensions of the vector space according to a partial function.

If pfunc maps only some of the dimensions of *this then the rest will be projected away.

If the highest dimension mapped to by pfunc is higher than the highest dimension in *this then the number of dimensions in this will be increased to the highest dimension mapped to by pfunc.

Parameters

pfunc The partial function specifying the destiny of each space dimension.

The template type parameter Partial_Function must provide the following methods.

bool has_empty_codomain() const

returns true if and only if the represented partial function has an empty codomain (i.e., it is always undefined). The has_empty_codomain() method will always be called before the methods below. However, if has_empty_codomain() returns true, none of the functions below will be called.

dimension_type max_in_codomain() const

returns the maximum value that belongs to the codomain of the partial function. The max_in_codomain() method is called at most once.

bool maps(dimension_type i, dimension_type& j) const

Let $f$ be the represented function and $k$ be the value of i. If $f$ is defined in $k$ , then $f(k)$ is assigned to j and true is returned. If $f$ is undefined in $k$ , then false is returned. This method is called at most $n$ times, where $n$ is the dimension of the vector space enclosing the grid.

The result is undefined if pfunc does not encode a partial function with the properties described in the specification of the mapping operator.

void Parma_Polyhedra_Library::Grid::expand_space_dimension	(	Variable	var,
		dimension_type	m
	)

Creates m copies of the space dimension corresponding to var.

Parameters

var	The variable corresponding to the space dimension to be replicated;
m	The number of replicas to be created.

Exceptions

std::invalid_argument	Thrown if `var` does not correspond to a dimension of the vector space.
std::length_error	Thrown if adding `m` new space dimensions would cause the vector space to exceed dimension `max_space_dimension()`.

If *this has space dimension $n$ , with $n > 0$ , and var has space dimension $k \leq n$ , then the $k$ -th space dimension is expanded to m new space dimensions $n$ , $n+1$ , $\dots$ , $n+m-1$ .

void Parma_Polyhedra_Library::Grid::fold_space_dimensions	(	const Variables_Set &	vars,
		Variable	dest
	)

Folds the space dimensions in vars into dest.

Parameters

vars	The set of Variable objects corresponding to the space dimensions to be folded;
dest	The variable corresponding to the space dimension that is the destination of the folding operation.

Exceptions

std::invalid_argument Thrown if *this is dimension-incompatible with dest or with one of the Variable objects contained in vars. Also thrown if dest is contained in vars.

If *this has space dimension $n$ , with $n > 0$ , dest has space dimension $k \leq n$ , vars is a set of variables whose maximum space dimension is also less than or equal to $n$ , and dest is not a member of vars, then the space dimensions corresponding to variables in vars are folded into the $k$ -th space dimension.

int32_t Parma_Polyhedra_Library::Grid::hash_code ( ) const

inline

Returns a 32-bit hash code for *this.

If x and y are such that x == y, then x.hash_code() == y.hash_code().

Friends And Related Function Documentation

std::ostream & operator<<	(	std::ostream &	s,
		const Grid &	gr
	)

Writes a textual representation of gr on s: false is written if gr is an empty grid; true is written if gr is a universe grid; a minimized system of congruences defining gr is written otherwise, all congruences in one row separated by ", "s.

void swap	(	Grid &	x,
		Grid &	y
	)

bool operator==	(	const Grid &	x,
		const Grid &	y
	)

Note that x and y may be dimension-incompatible grids: in those cases, the value false is returned.

bool operator!=	(	const Grid &	x,
		const Grid &	y
	)

Note that x and y may be dimension-incompatible grids: in those cases, the value true is returned.

bool operator!=	(	const Grid &	x,
		const Grid &	y
	)

void swap	(	Grid &	x,
		Grid &	y
	)

ppl.hh

Public Types

Public Member Functions

Static Public Member Functions

Related Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation