Public Member Functions | |
Grid (dimension_type num_dimensions=0, const Degenerate_Element kind=UNIVERSE) | |
Builds a grid having the specified properties. | |
Grid (const Congruence_System &cgs) | |
Builds a grid, copying a system of congruences. | |
Grid (Congruence_System &cgs) | |
Builds a grid, recycling a system of congruences. | |
Grid (const Constraint_System &cs) | |
Builds a grid, copying a system of constraints. | |
Grid (Constraint_System &cs) | |
Builds a grid, recycling a system of constraints. | |
Grid (const Grid_Generator_System &const_gs) | |
Builds a grid, copying a system of generators. | |
Grid (Grid_Generator_System &gs) | |
Builds a grid, recycling a system of generators. | |
template<typename Box> | |
Grid (const Box &box, From_Bounding_Box dummy) | |
Builds a grid out of a generic, interval-based bounding box. | |
template<typename Box> | |
Grid (const Box &box, From_Covering_Box dummy) | |
Builds a grid out of a generic, interval-based covering box. | |
Grid (const Grid &y) | |
Ordinary copy-constructor. | |
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 ![]() *this is empty; otherwise, returns the affine dimension of *this . | |
const Congruence_System & | congruences () const |
Returns the system of congruences. | |
const Congruence_System & | minimized_congruences () const |
Returns the system of congruences in reduced form. | |
const Grid_Generator_System & | generators () const |
Returns the system of generators. | |
const Grid_Generator_System & | minimized_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 . | |
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. | |
bool | is_disjoint_from (const Grid &y) const |
Returns true if and only if *this and y are disjoint. | |
bool | is_discrete () const |
Returns true if and only if *this is discrete. | |
bool | is_bounded () const |
Returns true if and only if *this is bounded. | |
bool | bounds_from_above (const Linear_Expression &expr) const |
Returns true if and only if expr is bounded in *this . | |
bool | bounds_from_below (const Linear_Expression &expr) const |
Returns true if and only if expr is bounded in *this . | |
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. | |
bool | maximize (const Linear_Expression &expr, Coefficient &sup_n, Coefficient &sup_d, bool &maximum, Grid_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. | |
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. | |
bool | minimize (const Linear_Expression &expr, Coefficient &inf_n, Coefficient &inf_d, bool &minimum, Grid_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. | |
bool | contains (const Grid &y) const |
Returns true if and only if *this contains y . | |
bool | strictly_contains (const Grid &y) const |
Returns true if and only if *this strictly contains y . | |
template<typename Box> | |
void | shrink_bounding_box (Box &box) const |
Uses *this to shrink a generic, interval-based bounding box. | |
template<typename Box> | |
void | get_covering_box (Box &box) const |
Writes the covering box for *this into box . | |
bool | OK (bool check_not_empty=false) const |
Checks if all the invariants are satisfied. | |
Space Dimension Preserving Member Functions that May Modify the Grid | |
void | add_congruence (const Congruence &cg) |
Adds a copy of congruence cg to *this . | |
void | add_congruence (const Constraint &c) |
Adds constraint c to *this . | |
bool | add_congruence_and_minimize (const Congruence &c) |
Adds a copy of congruence cg to the system of congruences of this , reducing the result. | |
bool | add_congruence_and_minimize (const Constraint &c) |
Adds a copy of constraint c to *this , reducing the result. | |
void | add_generator (const Grid_Generator &g) |
Adds a copy of generator g to the system of generators of this . | |
bool | add_generator_and_minimize (const Grid_Generator &g) |
Adds a copy of generator g to the system of generators of this , reducing the result. | |
void | add_congruences (const Congruence_System &cgs) |
Adds a copy of each congruence in cgs to *this . | |
void | add_congruences (const Constraint_System &cs) |
Adds a copy of each equality constraint in cs to *this . | |
void | add_recycled_congruences (Congruence_System &cgs) |
Adds the congruences in cgs to *this. | |
void | add_recycled_congruences (Constraint_System &cs) |
Adds the equality constraints in cs to *this . | |
bool | add_congruences_and_minimize (const Congruence_System &cgs) |
Adds a copy of the congruences in cgs to the system of congruences of *this , reducing the result. | |
bool | add_congruences_and_minimize (const Constraint_System &cs) |
Adds a copy of each equality constraint in cs to *this , reducing the result. | |
bool | add_recycled_congruences_and_minimize (Congruence_System &cgs) |
Adds the congruences in cgs to the system of congruences of this , reducing the result. | |
bool | add_recycled_congruences_and_minimize (Constraint_System &cs) |
Adds the equalities in cs to *this , reducing the result. | |
void | add_constraint (const Constraint &c) |
Adds constraint c to *this . | |
bool | add_constraint_and_minimize (const Constraint &c) |
Adds constraint c to *this , reducing the result. | |
void | add_constraints (const Constraint_System &cs) |
Adds copies of the equality constraints in cs to *this . | |
bool | add_constraints_and_minimize (const Constraint_System &cs) |
Adds copies of the equality constraints in cs to *this , reducing the result. | |
void | add_recycled_constraints (Constraint_System &cs) |
Adds the equality constraints in cs to *this . | |
bool | add_recycled_constraints_and_minimize (Constraint_System &cs) |
void | add_generators (const Grid_Generator_System &gs) |
Adds a copy of the generators in gs to the system of generators of *this . | |
void | add_recycled_generators (Grid_Generator_System &gs) |
Adds the generators in gs to the system of generators of this . | |
bool | add_generators_and_minimize (const Grid_Generator_System &gs) |
Adds a copy of the generators in gs to the system of generators of *this , reducing the result. | |
bool | add_recycled_generators_and_minimize (Grid_Generator_System &gs) |
Adds the generators in gs to the system of generators of this , reducing the result. | |
void | intersection_assign (const Grid &y) |
Assigns to *this the intersection of *this and y . The result is not guaranteed to be reduced. | |
bool | intersection_assign_and_minimize (const Grid &y) |
Assigns to *this the intersection of *this and y , reducing the result. | |
void | join_assign (const Grid &y) |
Assigns to *this the join of *this and y . | |
bool | join_assign_and_minimize (const Grid &y) |
Assigns to *this the join of *this and y , reducing the result. | |
void | upper_bound_assign (const Grid &y) |
Same as join_assign(y). | |
bool | join_assign_if_exact (const Grid &y) |
If the join of *this and y is exact it is assigned to this and true is returned, otherwise false is returned. | |
bool | upper_bound_assign_if_exact (const Grid &y) |
Same as join_assign_if_exact(y). | |
void | grid_difference_assign (const Grid &y) |
Assigns to *this the grid-difference of *this and y . | |
void | difference_assign (const Grid &y) |
Same as grid_difference_assign(y). | |
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 . | |
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 . | |
void | generalized_affine_image (Variable var, const Linear_Expression &expr, Coefficient_traits::const_reference denominator=Coefficient_one(), Coefficient_traits::const_reference modulus=Coefficient_one()) |
Assigns to *this the image of *this with respect to the generalized affine relation ![]() | |
void | generalized_affine_preimage (Variable var, const Linear_Expression &expr, Coefficient_traits::const_reference denominator=Coefficient_one(), Coefficient_traits::const_reference modulus=Coefficient_one()) |
Assigns to *this the preimage of *this with respect to the generalized affine relation ![]() | |
void | generalized_affine_image (const Linear_Expression &lhs, const Linear_Expression &rhs, Coefficient_traits::const_reference modulus=Coefficient_one()) |
Assigns to *this the image of *this with respect to the generalized affine relation ![]() | |
void | generalized_affine_preimage (const Linear_Expression &lhs, const Linear_Expression &rhs, Coefficient_traits::const_reference modulus=Coefficient_one()) |
Assigns to *this the preimage of *this with respect to the generalized affine relation ![]() | |
void | time_elapse_assign (const Grid &y) |
Assigns to *this the result of computing the time-elapse between *this and y . | |
void | topological_closure_assign () |
Assigns to *this its topological closure. | |
void | widening_assign (const Grid &y, unsigned *tp=NULL) |
Assigns to *this the result of computing the Grid widening between *this and y . | |
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 . | |
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. | |
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. | |
void | concatenate_assign (const Grid &y) |
Assigns to *this the concatenation of *this and y , taken in this order. | |
void | remove_space_dimensions (const Variables_Set &to_be_removed) |
Removes all the specified dimensions from the vector space. | |
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 . | |
template<typename Partial_Function> | |
void | map_space_dimensions (const Partial_Function &pfunc) |
Remaps the dimensions of the vector space according to a partial function. | |
void | expand_space_dimension (Variable var, dimension_type m) |
Creates m copies of the space dimension corresponding to var . | |
void | fold_space_dimensions (const Variables_Set &to_be_folded, Variable var) |
Folds the space dimensions in to_be_folded into var . | |
Miscellaneous Member Functions | |
~Grid () | |
Destructor. | |
void | swap (Grid &y) |
Swaps *this with grid y . (*this and y can be dimension-incompatible.). | |
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 . | |
Static Public Member Functions | |
static dimension_type | max_space_dimension () |
Returns the maximum space dimension all kinds of Grid can handle. | |
Friends | |
bool | operator== (const Grid &x, const Grid &y) |
Returns true if and only if x and y are the same grid. | |
Related Functions | |
(Note that these are not member functions.) | |
std::ostream & | operator<< (std::ostream &s, const Grid &gr) |
Output operator. | |
bool | operator!= (const Grid &x, const Grid &y) |
Returns true if and only if x and y are different grids. | |
void | swap (Parma_Polyhedra_Library::Grid &x, Parma_Polyhedra_Library::Grid &y) |
Specializes std::swap . |
An object of the class Grid represents a rational grid.
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 the 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. Most operators on grids are provided with two implementations: one of these, denoted <operator-name>_and_minimize
, also enforces the minimization of the representations, and returns the boolean value false
whenever the resulting grid turns out to be empty.
A key attributes of any grid is its space dimension (the dimension of the enclosing vector space):
Note that two different grids can be defined on the zero-dimension space: the empty grid and the universe grid .
x
and y
are defined (where they are used) as follows: Variable x(0); Variable y(1);
Congruence_System cgs; cgs.insert((x %= 0) / 2); cgs.insert((y %= 0) / 2); Grid gr(cgs);
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);
Congruence_System cgs; cgs.insert(x - y == 0); Grid gr(cgs);
Grid_Generator_System gs; gs.insert(grid_point(0*x + 0*y)); gs.insert(grid_line(x + y)); Grid gr(gs);
Congruence_System cgs; cgs.insert(x - y == 0); cgs.insert(x %= 0); Grid gr(cgs);
Grid_Generator_System gs; gs.insert(grid_point(0*x + 0*y)); gs.insert(parameter(x + y)); Grid gr(gs);
Grid gr(2);
add_space_dimensions_and_embed
: Grid gr(1); gr.add_congruence(x == 2); gr.add_space_dimensions_and_embed(1);
add_space_dimensions_and_project
: Grid gr(1); gr.add_congruence(x == 2); gr.add_space_dimensions_and_project(1);
add_space_dimensions_and_embed
. After the last line of code, the resulting grid is the singleton set affine_image
: Grid gr(2, EMPTY); gr.add_generator(grid_point(0*x + 0*y)); gr.add_generator(grid_point(4*x + 0*y)); gr.add_generator(grid_point(0*x + 2*y)); Linear_Expression expr = x + 3; gr.affine_image(x, expr);
x
is instead Linear_Expression expr = x + y;
Linear_Expression expr = y;
affine_preimage
: Grid gr(2, EMPTY); gr.add_generator(grid_point(0*x + 0*y)); gr.add_generator(grid_point(4*x + 0*y)); gr.add_generator(grid_point(0*x + 2*y)); Linear_Expression expr = x + 3; gr.affine_preimage(x, expr);
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 x
is Linear_Expression expr = x + y;
x
, for example, the affine expression Linear_Expression expr = y;
Variable z(2); Variable w(3);
remove_space_dimensions
: Grid_Generator_System gs; gs.insert(grid_point(3*x + y +0*z + 2*w)); Grid gr(gs); Variables_Set to_be_removed; to_be_removed.insert(y); to_be_removed.insert(z); gr.remove_space_dimensions(to_be_removed);
remove_space_dimensions
operator, unexpected results can be obtained. For instance, by using the following code we would obtain a different result: set<Variable> to_be_removed1; to_be_removed1.insert(y); gr.remove_space_dimensions(to_be_removed1); set<Variable> to_be_removed2; to_be_removed2.insert(z); gr.remove_space_dimensions(to_be_removed2);
to_be_removed2
we are actually removing variable remove_space_dimensions
is not idempotent: removing twice the same non-empty set of dimensions is never the same as removing them just once.
Parma_Polyhedra_Library::Grid::Grid | ( | dimension_type | num_dimensions = 0 , |
|
const Degenerate_Element | kind = UNIVERSE | |||
) | [explicit] |
Builds a grid having the specified properties.
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. |
std::length_error | Thrown if num_dimensions exceeds the maximum allowed space dimension. |
Parma_Polyhedra_Library::Grid::Grid | ( | const Congruence_System & | cgs | ) | [inline, explicit] |
Builds a grid, copying a system of congruences.
The grid inherits the space dimension of the congruence system.
cgs | The system of congruences defining the grid. |
std::length_error | Thrown if num_dimensions exceeds the maximum allowed space dimension. |
Parma_Polyhedra_Library::Grid::Grid | ( | Congruence_System & | cgs | ) | [inline, explicit] |
Builds a grid, recycling a system of congruences.
The grid inherits the space dimension of the congruence system.
cgs | The system of congruences defining the grid. Its data-structures will be recycled to build the grid. |
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.
cs | The system of constraints defining the grid. |
std::length_error | Thrown if num_dimensions exceeds the maximum allowed space dimension. |
Parma_Polyhedra_Library::Grid::Grid | ( | Constraint_System & | cs | ) | [explicit] |
Builds a grid, recycling a system of constraints.
The grid inherits the space dimension of the constraint system.
cs | The system of constraints defining the grid. |
std::length_error | Thrown if num_dimensions exceeds the maximum allowed space dimension. |
Parma_Polyhedra_Library::Grid::Grid | ( | const Grid_Generator_System & | const_gs | ) | [inline, explicit] |
Builds a grid, copying a system of generators.
The grid inherits the space dimension of the generator system.
const_gs | The system of generators defining the grid. |
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 & | gs | ) | [inline, explicit] |
Builds a grid, recycling a system of generators.
The grid inherits the space dimension of the generator system.
gs | The system of generators defining the grid. Its data-structures will be recycled to build the grid. |
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 | ( | const Box & | box, | |
From_Bounding_Box | dummy | |||
) |
Builds a grid out of a generic, interval-based bounding box.
box | The bounding box representing the grid to be built. The box can contain only point and universe intervals; | |
dummy | A dummy tag to make this constructor syntactically unique. |
std::length_error | Thrown if the space dimension of box exceeds the maximum allowed space dimension. | |
std::invalid_argument | Thrown if box contains at least one interval with: a topologically open bound, a single bound, or two bounds which have space between them. |
dimension_type space_dimension() const
bool is_empty() const
true
if and only if the bounding box describes the empty set. bool get_lower_bound(dimension_type k, bool closed, Coefficient& n, Coefficient& d) const
k
-th space dimension. If false
. Otherwise, set closed
, n
and d
as follows: closed
is set to true
if the lower boundary of false
otherwise; n
and d
are assigned the integers bool get_upper_bound(dimension_type k, bool closed, Coefficient& n, Coefficient& d) const
k
-th space dimension. If false
. Otherwise, set closed
, n
and d
as follows: closed
is set to true
if the upper boundary of false
otherwise; n
and d
are assigned the integers Parma_Polyhedra_Library::Grid::Grid | ( | const Box & | box, | |
From_Covering_Box | dummy | |||
) |
Builds a grid out of a generic, interval-based covering box.
The covering box is a set of upper and lower values for each dimension. When a covering box is tiled onto empty space the corners of the tiles form a rectilinear grid.
A box interval with only one bound fixes the values of all grid points in the dimension associated with the box to the value of the bound. A box interval which has upper and lower bounds of equal value allows all grid points with any value in the dimension associated with the interval. The presence of a universe interval results in the empty grid. The empty box produces the empty grid of the same dimension as the box.
box | The covering box representing the grid to be built; | |
dummy | A dummy tag to make this constructor syntactically unique. |
std::length_error | Thrown if the space dimension of box exceeds the maximum allowed space dimension. | |
std::invalid_argument | Thrown if box contains any topologically open bounds. |
dimension_type space_dimension() const
bool is_empty() const
true
if and only if the covering box describes the empty set. bool get_lower_bound(dimension_type k, bool closed, Coefficient& n, Coefficient& d) const
k
-th space dimension. If false
. Otherwise, set closed
, n
and d
as follows: closed
is set to true
if the lower boundary of false
otherwise; n
and d
are assigned the integers bool get_upper_bound(dimension_type k, bool closed, Coefficient& n, Coefficient& d) const
k
-th space dimension. If false
. Otherwise, set closed
, n
and d
as follows: closed
is set to true
if the upper boundary of false
otherwise; n
and d
are assigned the integers
bool Parma_Polyhedra_Library::Grid::is_disjoint_from | ( | const Grid & | y | ) | const |
Returns true
if and only if *this
and y
are disjoint.
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::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.
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.
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.
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. |
std::invalid_argument | Thrown if expr and *this are dimension-incompatible. |
*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, | |||
Grid_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.
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. |
std::invalid_argument | Thrown if expr and *this are dimension-incompatible. |
*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.
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. |
std::invalid_argument | Thrown if expr and *this are dimension-incompatible. |
*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, | |||
Grid_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.
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. |
std::invalid_argument | Thrown if expr and *this are dimension-incompatible. |
*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::contains | ( | const Grid & | y | ) | const |
Returns true
if and only if *this
contains y
.
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
.
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
void Parma_Polyhedra_Library::Grid::shrink_bounding_box | ( | Box & | box | ) | const |
Uses *this
to shrink a generic, interval-based bounding box.
box | The bounding box to be shrunk. |
std::invalid_argument | Thrown if *this and box are dimension-incompatible, or if box contains any topologically open bounds. |
dimension_type space_dimension() const
bool get_lower_bound(dimension_type k, bool closed, Coefficient& n, Coefficient& d) const
k
-th space dimension. If false
. Otherwise, set closed
, n
and d
as follows: closed
is set to true
if the lower boundary of false
otherwise; n
and d
are assigned the integers bool get_upper_bound(dimension_type k, bool closed, Coefficient& n, Coefficient& d) const
k
-th space dimension. If false
. Otherwise, set closed
, n
and d
as follows: closed
is set to true
if the upper boundary of false
otherwise; n
and d
are assigned the integers set_empty()
raise_lower_bound(dimension_type k, bool closed, Coefficient_traits::const_reference n, Coefficient_traits::const_reference d)
k
-th space dimension with closed
is always passed as true
. lower_upper_bound(dimension_type k, bool closed, Coefficient_traits::const_reference n, Coefficient_traits::const_reference d)
k
-th space dimension with closed
is always passed as true
.
The function raise_lower_bound(k, closed, n, d)
will be called at most once for each possible value for k
and for all such calls the fraction will be in canonical form, that is,
and
have no common factors and
is positive,
being the unique representation for zero. The same guarantee is offered for the function
lower_upper_bound(k, closed, n, d)
.
void Parma_Polyhedra_Library::Grid::get_covering_box | ( | Box & | box | ) | const |
Writes the covering box for *this
into box
.
The covering box is a set of upper and lower values for each dimension. When the covering box written into box
is tiled onto empty space the corners of the tiles form the sparsest rectilinear grid that includes *this
.
The value of the lower bound of each interval of the resulting box
are as close as possible to the origin, with positive values taking preference when the lowest positive value equals the lowest negative value.
If all the points have a single value in a particular dimension of the grid then there is only a lower bound on the interval produced in box
, and the lower bound denotes the single value for the dimension. If the coordinates of the points in a particular dimension include every value then the upper and lower bounds of the associated interval in box
are set equal. The empty grid produces the empty box
. The zero dimension universe grid produces the zero dimension universe box.
box | The Box into which the covering box is written. |
std::invalid_argument | Thrown if *this and box are dimension-incompatible. |
dimension_type space_dimension() const
set_empty()
raise_lower_bound(dimension_type k, bool closed, Coefficient_traits::const_reference n, Coefficient_traits::const_reference d)
k
-th space dimension with closed
is always passed as true
. lower_upper_bound(dimension_type k, bool closed, Coefficient_traits::const_reference n, Coefficient_traits::const_reference d)
k
-th space dimension with closed
is always passed as true
.
The function raise_lower_bound(k, closed, n, d)
will be called at most once for each possible value for k
and for all such calls the fraction will be in canonical form, that is,
and
have no common factors and
is positive,
being the unique representation for zero. The same guarantee is offered for the function
lower_upper_bound(k, closed, n, d)
.
bool Parma_Polyhedra_Library::Grid::OK | ( | bool | check_not_empty = false |
) | const |
Checks if all the invariants are satisfied.
true
if and only if *this
satisfies all the invariants and either check_not_empty
is false
or *this
is not empty.check_not_empty | true if and only if, in addition to checking the invariants, *this must be checked to be not empty. |
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 | ) |
Adds a copy of congruence cg
to *this
.
std::invalid_argument | Thrown if *this and congruence cg are dimension-incompatible. |
void Parma_Polyhedra_Library::Grid::add_congruence | ( | const Constraint & | c | ) |
Adds constraint c
to *this
.
The addition can only affect *this
if c
is an equality.
std::invalid_argument | Thrown if *this and constraint c are dimension-incompatible. |
bool Parma_Polyhedra_Library::Grid::add_congruence_and_minimize | ( | const Congruence & | c | ) |
Adds a copy of congruence cg
to the system of congruences of this
, reducing the result.
false
if and only if the result is empty.std::invalid_argument | Thrown if *this and congruence cg are dimension-incompatible. |
bool Parma_Polyhedra_Library::Grid::add_congruence_and_minimize | ( | const Constraint & | c | ) |
Adds a copy of constraint c
to *this
, reducing the result.
The addition can only affect *this
if c
is an equality.
false
if and only if the result is empty.std::invalid_argument | Thrown if *this and constraint c are dimension-incompatible. |
void Parma_Polyhedra_Library::Grid::add_generator | ( | const Grid_Generator & | g | ) |
Adds a copy of generator g
to the system of generators of this
.
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. |
bool Parma_Polyhedra_Library::Grid::add_generator_and_minimize | ( | const Grid_Generator & | g | ) |
Adds a copy of generator g
to the system of generators of this
, reducing the result.
false
if and only if the result is empty.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 | ) |
Adds a copy of each congruence in cgs
to *this
.
cgs | Contains the congruences that will be added to the system of congruences of *this . |
std::invalid_argument | Thrown if *this and cgs are dimension-incompatible. |
void Parma_Polyhedra_Library::Grid::add_congruences | ( | const Constraint_System & | cs | ) |
Adds a copy of each equality constraint in cs
to *this
.
cs | The congruences that will be considered for addition to the system of congruences of *this . |
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.
cgs | The congruence system that will be recycled, adding its congruences to the system of congruences of *this . |
std::invalid_argument | Thrown if *this and cs are dimension-incompatible. |
cgs
upon successful or exceptional return is that it can be safely destroyed. void Parma_Polyhedra_Library::Grid::add_recycled_congruences | ( | Constraint_System & | cs | ) |
Adds the equality constraints in cs
to *this
.
cs | The constraint system from which constraints will be considered for addition to the system of congruences of *this . |
std::invalid_argument | Thrown if *this and cs are dimension-incompatible. |
cs
upon successful or exceptional return is that it can be safely destroyed.
bool Parma_Polyhedra_Library::Grid::add_congruences_and_minimize | ( | const Congruence_System & | cgs | ) |
Adds a copy of the congruences in cgs
to the system of congruences of *this
, reducing the result.
false
if and only if the result is empty.cgs | Contains the congruences that will be added to the system of congruences of *this . |
std::invalid_argument | Thrown if *this and cgs are dimension-incompatible. |
bool Parma_Polyhedra_Library::Grid::add_congruences_and_minimize | ( | const Constraint_System & | cs | ) |
Adds a copy of each equality constraint in cs
to *this
, reducing the result.
false
if and only if the result is empty.cs | Contains the constraints that will be added to the system of congruences of *this . |
std::invalid_argument | Thrown if *this and cs are dimension-incompatible. |
bool Parma_Polyhedra_Library::Grid::add_recycled_congruences_and_minimize | ( | Congruence_System & | cgs | ) |
Adds the congruences in cgs
to the system of congruences of this
, reducing the result.
false
if and only if the result is empty.cgs | The congruence system that will be recycled, adding its congruences to the system of congruences of *this . |
std::invalid_argument | Thrown if *this and cgs are dimension-incompatible. |
cgs
upon successful or exceptional return is that it can be safely destroyed. bool Parma_Polyhedra_Library::Grid::add_recycled_congruences_and_minimize | ( | Constraint_System & | cs | ) |
Adds the equalities in cs
to *this
, reducing the result.
false
if and only if the result is empty.cs | The constraint system that will be recycled, adding its equalities to the system of congruences of *this . |
std::invalid_argument | Thrown if *this and cs are dimension-incompatible. |
cs
upon successful or exceptional return is that it can be safely destroyed. void Parma_Polyhedra_Library::Grid::add_constraint | ( | const Constraint & | c | ) |
Adds constraint c
to *this
.
The addition can only affect *this
if c
is an equality.
std::invalid_argument | Thrown if *this and c are dimension-incompatible. |
bool Parma_Polyhedra_Library::Grid::add_constraint_and_minimize | ( | const Constraint & | c | ) |
Adds constraint c
to *this
, reducing the result.
The addition can only affect *this
if c
is an equality.
false
if and only if the result is empty.std::invalid_argument | Thrown if *this and c are dimension-incompatible. |
void Parma_Polyhedra_Library::Grid::add_constraints | ( | const Constraint_System & | cs | ) |
Adds copies of the equality constraints in cs
to *this
.
std::invalid_argument | Thrown if *this and cs are dimension-incompatible. |
bool Parma_Polyhedra_Library::Grid::add_constraints_and_minimize | ( | const Constraint_System & | cs | ) |
Adds copies of the equality constraints in cs
to *this
, reducing the result.
false
if and only if the result is empty.std::invalid_argument | Thrown if *this and cs are dimension-incompatible. |
void Parma_Polyhedra_Library::Grid::add_recycled_constraints | ( | Constraint_System & | cs | ) |
Adds the equality constraints in cs
to *this
.
std::invalid_argument | Thrown if *this and cs are dimension-incompatible. |
cs
upon successful or exceptional return is that it can be safely destroyed. bool Parma_Polyhedra_Library::Grid::add_recycled_constraints_and_minimize | ( | Constraint_System & | cs | ) |
false
if and only if the result is empty.std::invalid_argument | Thrown if *this and cs are dimension-incompatible. |
cs
upon successful or exceptional return is that it can be safely destroyed. void Parma_Polyhedra_Library::Grid::add_generators | ( | const Grid_Generator_System & | gs | ) |
Adds a copy of the generators in gs
to the system of generators of *this
.
gs | Contains the generators that will be added to the system of generators of *this . |
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_generators | ( | Grid_Generator_System & | gs | ) |
Adds the generators in gs
to the system of generators of this
.
gs | The generator system that will be recycled, adding its generators to the system of generators of *this . |
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. |
gs
upon successful or exceptional return is that it can be safely destroyed. bool Parma_Polyhedra_Library::Grid::add_generators_and_minimize | ( | const Grid_Generator_System & | gs | ) |
Adds a copy of the generators in gs
to the system of generators of *this
, reducing the result.
false
if and only if the result is empty.gs | Contains the generators that will be added to the system of generators of *this . |
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. |
bool Parma_Polyhedra_Library::Grid::add_recycled_generators_and_minimize | ( | Grid_Generator_System & | gs | ) |
Adds the generators in gs
to the system of generators of this
, reducing the result.
false
if and only if the result is empty.gs | The generator system that will be recycled, adding its generators to the system of generators of *this . |
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. |
gs
upon successful or exceptional return is that it can be safely destroyed. void Parma_Polyhedra_Library::Grid::intersection_assign | ( | const Grid & | y | ) |
Assigns to *this
the intersection of *this
and y
. The result is not guaranteed to be reduced.
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
bool Parma_Polyhedra_Library::Grid::intersection_assign_and_minimize | ( | const Grid & | y | ) |
Assigns to *this
the intersection of *this
and y
, reducing the result.
false
if and only if the result is empty.std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
void Parma_Polyhedra_Library::Grid::join_assign | ( | const Grid & | y | ) |
Assigns to *this
the join of *this
and y
.
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
bool Parma_Polyhedra_Library::Grid::join_assign_and_minimize | ( | const Grid & | y | ) |
Assigns to *this
the join of *this
and y
, reducing the result.
false
if and only if the result is empty.std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
bool Parma_Polyhedra_Library::Grid::join_assign_if_exact | ( | const Grid & | y | ) |
If the join of *this
and y
is exact it is assigned to this
and true
is returned, otherwise false
is returned.
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
void Parma_Polyhedra_Library::Grid::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.
std::invalid_argument | Thrown if *this and y are 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
.
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). |
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
.
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). |
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, | |
const Linear_Expression & | expr, | |||
Coefficient_traits::const_reference | denominator = Coefficient_one() , |
|||
Coefficient_traits::const_reference | modulus = Coefficient_one() | |||
) |
Assigns to *this
the image of *this
with respect to the generalized affine relation .
var | The left hand side variable of the generalized affine 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 one. |
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, | |
const Linear_Expression & | expr, | |||
Coefficient_traits::const_reference | denominator = Coefficient_one() , |
|||
Coefficient_traits::const_reference | modulus = Coefficient_one() | |||
) |
Assigns to *this
the preimage of *this
with respect to the generalized affine relation .
var | The left hand side variable of the generalized affine 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 one. |
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, | |
const Linear_Expression & | rhs, | |||
Coefficient_traits::const_reference | modulus = Coefficient_one() | |||
) |
Assigns to *this
the image of *this
with respect to the generalized affine relation .
lhs | The left hand side affine expression. | |
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 one. |
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, | |
const Linear_Expression & | rhs, | |||
Coefficient_traits::const_reference | modulus = Coefficient_one() | |||
) |
Assigns to *this
the preimage of *this
with respect to the generalized affine relation .
lhs | The left hand side affine expression; | |
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 one. |
std::invalid_argument | Thrown if *this is dimension-incompatible with lhs or rhs . |
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
.
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
.
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). |
std::invalid_argument | Thrown if *this and y 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
.
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). |
std::invalid_argument | Thrown if *this , y and cs 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.
m | The number of dimensions to add. |
std::length_error | Thrown if adding m new space dimensions would cause the vector space to exceed dimension max_space_dimension() . |
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.
m | The number of space dimensions to add. |
std::length_error | Thrown if adding m new space dimensions would cause the vector space to exceed dimension max_space_dimension() . |
void Parma_Polyhedra_Library::Grid::concatenate_assign | ( | const Grid & | y | ) |
Assigns to *this
the concatenation of *this
and y
, taken in this order.
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 & | to_be_removed | ) |
Removes all the specified dimensions from the vector space.
to_be_removed | The set of Variable objects corresponding to the space dimensions to be removed. |
std::invalid_argument | Thrown if *this is dimension-incompatible with one of the Variable objects contained in to_be_removed . |
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
.
std::invalid_argument | Thrown if new_dimensions is greater than the space dimension of *this . |
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
.
pfunc | The partial function specifying the destiny of each space dimension. |
bool has_empty_codomain() const
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
max_in_codomain()
method is called at most once. bool maps(dimension_type i, dimension_type& j) const
i
. If j
and true
is returned. If false
is returned. This method is called at most
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
.
var | The variable corresponding to the space dimension to be replicated; | |
m | The number of replicas to be created. |
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() . |
*this
has space dimension var
has space dimension m
new space dimensions void Parma_Polyhedra_Library::Grid::fold_space_dimensions | ( | const Variables_Set & | to_be_folded, | |
Variable | var | |||
) |
Folds the space dimensions in to_be_folded
into var
.
to_be_folded | The set of Variable objects corresponding to the space dimensions to be folded; | |
var | The variable corresponding to the space dimension that is the destination of the folding operation. |
std::invalid_argument | Thrown if *this is dimension-incompatible with var or with one of the Variable objects contained in to_be_folded . Also thrown if var is contained in to_be_folded . |
*this
has space dimension var
has space dimension to_be_folded
is a set of variables whose maximum space dimension is also less than or equal to var
is not a member of to_be_folded
, then the space dimensions corresponding to variables in to_be_folded
are folded into the
Returns true
if and only if x
and y
are the same grid.
Note that x
and y
may be dimension-incompatible grids: in those cases, the value false
is returned.
std::ostream & operator<< | ( | std::ostream & | s, | |
const Grid & | gr | |||
) | [related] |
Output operator.
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.
Returns true
if and only if x
and y
are different grids.
Note that x
and y
may be dimension-incompatible grids: in those cases, the value true
is returned.