# Parma_Polyhedra_Library::Grid Class Reference
[C++ Language Interface]

A grid. More...

List of all members.

## 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 , if `*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`.

## Detailed Description

A grid.

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

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

  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 , 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 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 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 :

        Grid gr(2);

  The following code builds the same grid as above, but starting from the empty grid in and inserting the appropriate generators (a point, and two lines).

        Grid gr(2, EMPTY);
        gr.add_generator(grid_point(0*x + 0*y));
        gr.add_generator(grid_line(x));
        gr.add_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 . Then we add a single equality congruence, thus obtaining the grid corresponding to the singleton set . After the last line of code, the resulting grid is

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 .

Example 7
  The following code shows the use of the function `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);

  In this example the starting grid is all the pairs of and in 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_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);

  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 to_be_removed;
        to_be_removed.insert(y);
        to_be_removed.insert(z);
        gr.remove_space_dimensions(to_be_removed);

  The starting grid is the singleton set , while the resulting grid is . 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> 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);

  In this case, the result is the grid : when removing the set of dimensions `to_be_removed2` 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`,
|  | const Degenerate_Element | kind = `UNIVERSE` |
| ) |  |  | `[explicit]`

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 | ) | `[inline, explicit]`

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 | ) | `[inline, explicit]`

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 will be recycled to build the grid.

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

Parameters:

  | cs | The system of constraints defining the grid.

Exceptions:

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

Parameters:

  | const_gs | 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 & | gs | ) | `[inline, explicit]`

Builds a grid, recycling a system of generators.

The grid inherits the space dimension of the generator system.

Parameters:

  | gs | The system of generators defining the grid. Its data-structures will be recycled to build 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.

template<typename Box>

Parma_Polyhedra_Library::Grid::Grid | ( | const Box & | box,
|  | From_Bounding_Box | dummy |
| ) |  |  |

Builds a grid out of a generic, interval-based bounding box.

Parameters:

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

Exceptions:

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

The template class Box must provide the following methods.

          dimension_type space_dimension() const

returns the dimension of the vector space enclosing the grid represented by the bounding box.

          bool is_empty() const

returns `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

Let be the interval corresponding to the `k`-th space dimension. If is not bounded from below, simply return `false`. Otherwise, set `closed`, `n` and `d` as follows: `closed` is set to `true` if the lower boundary of is closed and is set to `false` otherwise; `n` and `d` are assigned the integers and such that the canonical fraction corresponds to the greatest lower bound of . The fraction is in canonical form if and only if and have no common factors and is positive, being the unique representation for zero.

          bool get_upper_bound(dimension_type k, bool closed,
                               Coefficient& n, Coefficient& d) const

Let be the interval corresponding to the `k`-th space dimension. If is not bounded from above, simply return `false`. Otherwise, set `closed`, `n` and `d` as follows: `closed` is set to `true` if the upper boundary of is closed and is set to `false` otherwise; `n` and `d` are assigned the integers and such that the canonical fraction corresponds to the least upper bound of .

template<typename Box>

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.

Parameters:

  | box | The covering box representing the grid to be built;
  | dummy | A dummy tag to make this constructor syntactically unique.

Exceptions:

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

The template class Box must provide the following methods.

          dimension_type space_dimension() const

returns the dimension of the vector space enclosing the grid represented by the covering box.

          bool is_empty() const

returns `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

Let be the interval corresponding to the `k`-th space dimension. If is not bounded from below, simply return `false`. Otherwise, set `closed`, `n` and `d` as follows: `closed` is set to `true` if the lower boundary of is closed and is set to `false` otherwise; `n` and `d` are assigned the integers and such that the canonical fraction corresponds to the greatest lower bound of . The fraction is in canonical form if and only if and have no common factors and is positive, being the unique representation for zero.

          bool get_upper_bound(dimension_type k, bool closed,
                               Coefficient& n, Coefficient& d) const

Let be the interval corresponding to the `k`-th space dimension. If is not bounded from above, simply return `false`. Otherwise, set `closed`, `n` and `d` as follows: `closed` is set to `true` if the upper boundary of is closed and is set to `false` otherwise; `n` and `d` are assigned the integers and such that the canonical fraction corresponds to the least upper bound of .

## Member Function Documentation

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::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,
|  | 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.

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

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

template<typename Box>

void Parma_Polyhedra_Library::Grid::shrink_bounding_box | ( | Box & | box | ) | const

Uses `*this` to shrink a generic, interval-based bounding box.

Parameters:

  | box | The bounding box to be shrunk.

Exceptions:

  | std::invalid_argument | Thrown if `*this` and `box` are dimension-incompatible, or if `box` contains any topologically open bounds.

The template class Box must provide the following methods

          dimension_type space_dimension() const

returns the dimension of the vector space enclosing the grid represented by the bounding box.

          bool get_lower_bound(dimension_type k, bool closed,
                               Coefficient& n, Coefficient& d) const

Let be the interval corresponding to the `k`-th space dimension. If is not bounded from below, simply return `false`. Otherwise, set `closed`, `n` and `d` as follows: `closed` is set to `true` if the lower boundary of is closed and is set to `false` otherwise; `n` and `d` are assigned the integers and such that the canonical fraction corresponds to the greatest lower bound of . The fraction is in canonical form if and only if and have no common factors and is positive, being the unique representation for zero.

          bool get_upper_bound(dimension_type k, bool closed,
                               Coefficient& n, Coefficient& d) const

Let be the interval corresponding to the `k`-th space dimension. If is not bounded from above, simply return `false`. Otherwise, set `closed`, `n` and `d` as follows: `closed` is set to `true` if the upper boundary of is closed and is set to `false` otherwise; `n` and `d` are assigned the integers and such that the canonical fraction corresponds to the least upper bound of .

          set_empty()

Causes the box to become empty, i.e., to represent the empty set.

          raise_lower_bound(dimension_type k, bool closed,
                            Coefficient_traits::const_reference n,
                            Coefficient_traits::const_reference d)

intersects the interval corresponding to the `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)

intersects the interval corresponding to the `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)`.

template<typename Box>

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.

Parameters:

  | box | The Box into which the covering box is written.

Exceptions:

  | std::invalid_argument | Thrown if `*this` and `box` are dimension-incompatible.

The template class Box must provide the following methods

          Box(dimension_type space_dimension)

Creates a universe box of space_dimension dimensions.

          dimension_type space_dimension() const

returns the dimension of the vector space enclosing the grid represented by the covering box.

          set_empty()

Causes the box to become empty, i.e., to represent the empty set.

          raise_lower_bound(dimension_type k, bool closed,
                            Coefficient_traits::const_reference n,
                            Coefficient_traits::const_reference d)

intersects the interval corresponding to the `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)

intersects the interval corresponding to the `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.

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

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_congruence | ( | const Constraint & | c | ) |

Adds constraint `c` to `*this`.

The addition can only affect `*this` if `c` is an equality.

Exceptions:

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

Returns:
  `false` if and only if the result is empty.

Exceptions:

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

Returns:
  `false` if and only if the result is empty.

Exceptions:

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

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.

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.

Returns:
  `false` if and only if the result is empty.

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

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_congruences | ( | const Constraint_System & | cs | ) |

Adds a copy of each equality constraint in `cs` to `*this`.

Parameters:

  | cs | The congruences that will be considered for addition 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 that will be recycled, adding its congruences to the system of congruences of `*this`.

Exceptions:

  | std::invalid_argument | Thrown if `*this` and `cs` 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_recycled_congruences | ( | Constraint_System & | cs | ) |

Adds the equality constraints in `cs` to `*this`.

Parameters:

  | cs | The constraint system from which constraints will be considered for addition to the system of congruences of `*this`.

Exceptions:

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

Warning:

The only assumption that can be made about `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.

Returns:
  `false` if and only if the result is empty.

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.

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.

Returns:
  `false` if and only if the result is empty.

Parameters:

  | cs | Contains the constraints that will be added to the system of congruences of `*this`.

Exceptions:

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

Returns:
  `false` if and only if the result is empty.

Parameters:

  | cgs | The congruence system that will be recycled, adding its congruences to the system of congruences of `*this`.

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.

bool Parma_Polyhedra_Library::Grid::add_recycled_congruences_and_minimize | ( | Constraint_System & | cs | ) |

Adds the equalities in `cs` to `*this`, reducing the result.

Returns:
  `false` if and only if the result is empty.

Parameters:

  | cs | The constraint system that will be recycled, adding its equalities to the system of congruences of `*this`.

Exceptions:

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

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::add_constraint | ( | const Constraint & | c | ) |

Adds constraint `c` to `*this`.

The addition can only affect `*this` if `c` is an equality.

Exceptions:

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

Returns:
  `false` if and only if the result is empty.

Exceptions:

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

Exceptions:

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

Returns:
  `false` if and only if the result is empty.

Exceptions:

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

Exceptions:

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

Warning:
  The only assumption that can be made about `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 | ) |

Returns:
  `false` if and only if the result is empty.

Exceptions:

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

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::add_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_generators | ( | Grid_Generator_System & | gs | ) |

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

Parameters:

  | gs | The generator system that will be recycled, adding its generators 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.

Warning:
  The only assumption that can be made about `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.

Returns:
  `false` if and only if the result is empty.

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.

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.

Returns:
  `false` if and only if the result is empty.

Parameters:

  | gs | The generator system that will be recycled, adding its generators 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.

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::intersection_assign | ( | const Grid & | y | ) |

Assigns to `*this` the intersection of `*this` and `y`. The result is not guaranteed to be reduced.

Exceptions:

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

Returns:
  `false` if and only if the result is empty.

Exceptions:

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

Exceptions:

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

Returns:
  `false` if and only if the result is empty.

Exceptions:

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

Exceptions:

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

Exceptions:

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

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

Parameters:

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

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

Parameters:

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

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

Parameters:

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

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

Parameters:

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

Exceptions:

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

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

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_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 `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.

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 and adding a third space dimension, the result will be the grid

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 and adding a third space dimension, the result will be the grid

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

Removes all the specified dimensions from the vector space.

Parameters:

  | to_be_removed | 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 `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`.

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 class 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 be the represented function and be the value of `i`. If is defined in , then is assigned to `j` and `true` is returned. If is undefined in , then `false` is returned. This method is called at most times, where 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 , with , and `var` has space dimension , then the -th space dimension is expanded to `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`.

Parameters:

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

Exceptions:

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

If `*this` has space dimension , with , `var` has space dimension , `to_be_folded` is a set of variables whose maximum space dimension is also less than or equal to , and `var` is not a member of `to_be_folded`, then the space dimensions corresponding to variables in `to_be_folded` are folded into the -th space dimension.

## Friends And Related Function Documentation

bool operator== | ( | const Grid & | x,
|  | const Grid & | y |
| ) |  |  | `[friend]`

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.

bool operator!= | ( | const Grid & | x,
|  | const Grid & | y |
| ) |  |  | `[related]`

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.