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.
Gridoperator= (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 $0$, if *this is empty; otherwise, returns the affine dimension of *this.
const Congruence_Systemcongruences () const
 Returns the system of congruences.
const Congruence_Systemminimized_congruences () const
 Returns the system of congruences in reduced form.
const Grid_Generator_Systemgenerators () const
 Returns the system of generators.
const Grid_Generator_Systemminimized_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 $\mathrm{var}' = \frac{\mathrm{expr}}{\mathrm{denominator}} \pmod{\mathrm{modulus}}$.
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 $\mathrm{var}' = \frac{\mathrm{expr}}{\mathrm{denominator}} \pmod{\mathrm{modulus}}$.
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 $\mathrm{lhs}' = \mathrm{rhs} \pmod{\mathrm{modulus}}$.
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 $\mathrm{lhs}' = \mathrm{rhs} \pmod{\mathrm{modulus}}$.
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 $n \in \Nset$ 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 $R^0$.

In all the examples it is assumed that variables x and y are defined (where they are used) as follows:
  Variable x(0);
  Variable y(1);
Example 1
The following code builds a grid corresponding to the even integer pairs in $\Rset^2$, given as a system of congruences:
  Congruence_System cgs;
  cgs.insert((x %= 0) / 2);
  cgs.insert((y %= 0) / 2);
  Grid gr(cgs);
The following code builds the same grid as above, but starting from a system of generators specifying three of the points:
  Grid_Generator_System gs;
  gs.insert(grid_point(0*x + 0*y));
  gs.insert(grid_point(0*x + 2*y));
  gs.insert(grid_point(2*x + 0*y));
  Grid gr(gs);
Example 2
The following code builds a grid corresponding to a line in $\Rset^2$ by adding a single congruence to the universe grid:
  Congruence_System cgs;
  cgs.insert(x - y == 0);
  Grid gr(cgs);
The following code builds the same grid as above, but starting from a system of generators specifying a point and a line:
  Grid_Generator_System gs;
  gs.insert(grid_point(0*x + 0*y));
  gs.insert(grid_line(x + y));
  Grid gr(gs);
Example 3
The following code builds a grid corresponding to the integral points on the line $x = y$ in $\Rset^2$ constructed by adding an equality and congruence to the universe grid:
  Congruence_System cgs;
  cgs.insert(x - y == 0);
  cgs.insert(x %= 0);
  Grid gr(cgs);
The following code builds the same grid as above, but starting from a system of generators specifying a point and a parameter:
  Grid_Generator_System gs;
  gs.insert(grid_point(0*x + 0*y));
  gs.insert(parameter(x + y));
  Grid gr(gs);
Example 4
The following code builds the grid corresponding to a plane by creating the universe grid in $\Rset^2$:
  Grid gr(2);
The following code builds the same grid as above, but starting from the empty grid in $\Rset^2$ and inserting the appropriate generators (a point, and two lines).
  Grid gr(2, EMPTY);
  gr.add_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 $\Rset$. Then we add a single equality congruence, thus obtaining the grid corresponding to the singleton set $\{ 2 \} \sseq \Rset$. After the last line of code, the resulting grid is

\[ \bigl\{\, (2, y)^\transpose \in \Rset^2 \bigm| y \in \Rset \,\bigr\}. \]

Example 6
The following code shows the use of the function add_space_dimensions_and_project:
  Grid gr(1);
  gr.add_congruence(x == 2);
  gr.add_space_dimensions_and_project(1);
The first two lines of code are the same as in Example 4 for add_space_dimensions_and_embed. After the last line of code, the resulting grid is the singleton set $\bigl\{ (2, 0)^\transpose \bigr\} \sseq \Rset^2$.
Example 7
The following code shows the use of the function affine_image:
  Grid gr(2, EMPTY);
  gr.add_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 $x$ and $y$ in $\Rset^2$ where $x$ is an integer multiple of 4 and $y$ is an integer multiple of 2. The considered variable is $x$ and the affine expression is $x+3$. The resulting grid is the given grid translated 3 integers to the right (all the pairs $(x, y)$ where $x$ is -1 plus an integer multiple of 4 and $y$ is an integer multiple of 2). Moreover, if the affine transformation for the same variable x is instead $x+y$:
  Linear_Expression expr = x + y;
the resulting grid is every second integral point along the $x=y$ line, with this line of points repeated at every fourth integral value along the $x$ axis. Instead, if we do not use an invertible transformation for the same variable; for example, the affine expression $y$:
  Linear_Expression expr = y;
the resulting grid is every second point along the $x=y$ 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 $(x, y)$ where $x$ is -3 plus an integer multiple of 4 and $y$ is an integer multiple of 2).. Moreover, if the affine transformation for x is $x+y$
  Linear_Expression expr = x + y;
the resulting grid is a similar grid to the result in Example 6, only the grid is slanted along $x=-y$. Instead, if we do not use an invertible transformation for the same variable x, for example, the affine expression $y$:
  Linear_Expression expr = y;
the resulting grid is every fourth line parallel to the $x$ 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 $\bigl\{ (3, 1, 0, 2)^\transpose \bigr\} \sseq \Rset^4$, while the resulting grid is $\bigl\{ (3, 2)^\transpose \bigr\} \sseq \Rset^2$. Be careful when removing space dimensions incrementally: since dimensions are automatically renamed after each application of the remove_space_dimensions operator, unexpected results can be obtained. For instance, by using the following code we would obtain a different result:
  set<Variable> 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 $\bigl\{(3, 0)^\transpose \bigr\} \sseq \Rset^2$: when removing the set of dimensions to_be_removed2 we are actually removing variable $w$ 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. 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 $I$ be the interval corresponding to the k-th space dimension. If $I$ 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 $I$ is closed and is set to false otherwise; n and d are assigned the integers $n$ and $d$ such that the canonical fraction $n/d$ corresponds to the greatest lower bound of $I$. The fraction $n/d$ is in canonical form if and only if $n$ and $d$ have no common factors and $d$ is positive, $0/1$ being the unique representation for zero.
      bool get_upper_bound(dimension_type k, bool closed,
                           Coefficient& n, Coefficient& d) const
Let $I$ be the interval corresponding to the k-th space dimension. If $I$ 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 $I$ is closed and is set to false otherwise; n and d are assigned the integers $n$ and $d$ such that the canonical fraction $n/d$ corresponds to the least upper bound of $I$.

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. 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 $I$ be the interval corresponding to the k-th space dimension. If $I$ 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 $I$ is closed and is set to false otherwise; n and d are assigned the integers $n$ and $d$ such that the canonical fraction $n/d$ corresponds to the greatest lower bound of $I$. The fraction $n/d$ is in canonical form if and only if $n$ and $d$ have no common factors and $d$ is positive, $0/1$ being the unique representation for zero.
      bool get_upper_bound(dimension_type k, bool closed,
                           Coefficient& n, Coefficient& d) const
Let $I$ be the interval corresponding to the k-th space dimension. If $I$ 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 $I$ is closed and is set to false otherwise; n and d are assigned the integers $n$ and $d$ such that the canonical fraction $n/d$ corresponds to the least upper bound of $I$.


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 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 $I$ be the interval corresponding to the k-th space dimension. If $I$ 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 $I$ is closed and is set to false otherwise; n and d are assigned the integers $n$ and $d$ such that the canonical fraction $n/d$ corresponds to the greatest lower bound of $I$. The fraction $n/d$ is in canonical form if and only if $n$ and $d$ have no common factors and $d$ is positive, $0/1$ being the unique representation for zero.
      bool get_upper_bound(dimension_type k, bool closed,
                           Coefficient& n, Coefficient& d) const
Let $I$ be the interval corresponding to the k-th space dimension. If $I$ 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 $I$ is closed and is set to false otherwise; n and d are assigned the integers $n$ and $d$ such that the canonical fraction $n/d$ corresponds to the least upper bound of $I$.
      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 $[n/d, +\infty)$. 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 $(-\infty, n/d]$. 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 $n/d$ will be in canonical form, that is, $n$ and $d$ have no common factors and $d$ is positive, $0/1$ 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 Creates a universe box of space_dimension dimensions. 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 $[n/d, +\infty)$. 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 $(-\infty, n/d]$. 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 $n/d$ will be in canonical form, that is, $n$ and $d$ have no common factors and $d$ is positive, $0/1$ 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 $\mathrm{var}' = \frac{\mathrm{expr}}{\mathrm{denominator}} \pmod{\mathrm{modulus}}$.

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 $\mathrm{var}' = \frac{\mathrm{expr}}{\mathrm{denominator}} \pmod{\mathrm{modulus}}$.

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 $\mathrm{lhs}' = \mathrm{rhs} \pmod{\mathrm{modulus}}$.

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 $\mathrm{lhs}' = \mathrm{rhs} \pmod{\mathrm{modulus}}$.

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 $\cL \sseq \Rset^2$ and adding a third space dimension, the result will be the grid

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

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

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

Parameters:
m The number of space dimensions to add.
Exceptions:
std::length_error Thrown if adding m new space dimensions would cause the vector space to exceed dimension max_space_dimension().
The new space dimensions will be those having the highest indexes in the new grid, which is characterized by a system of congruences in which the variables running through the new dimensions are all constrained to be equal to 0. For instance, when starting from the grid $\cL \sseq \Rset^2$ and adding a third space dimension, the result will be the grid

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

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

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

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

void Parma_Polyhedra_Library::Grid::remove_space_dimensions ( const Variables_Set 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 $f$ be the represented function and $k$ be the value of i. If $f$ is defined in $k$, then $f(k)$ is assigned to j and true is returned. If $f$ is undefined in $k$, then false is returned. This method is called at most $n$ times, where $n$ is the dimension of the vector space enclosing the grid.

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

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

Creates m copies of the space dimension corresponding to var.

Parameters:
var The variable corresponding to the space dimension to be replicated;
m The number of replicas to be created.
Exceptions:
std::invalid_argument Thrown if var does not correspond to a dimension of the vector space.
std::length_error Thrown if adding m new space dimensions would cause the vector space to exceed dimension max_space_dimension().
If *this has space dimension $n$, with $n > 0$, and var has space dimension $k \leq n$, then the $k$-th space dimension is expanded to m new space dimensions $n$, $n+1$, $\dots$, $n+m-1$.

void Parma_Polyhedra_Library::Grid::fold_space_dimensions ( const Variables_Set 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 $n$, with $n > 0$, var has space dimension $k \leq n$, to_be_folded is a set of variables whose maximum space dimension is also less than or equal to $n$, 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 $k$-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.


Generated on Sun Mar 12 09:14:31 2006 for PPL by  doxygen 1.4.6-20060227