# Parma_Polyhedra_Library::BD_Shape< T > Class Template Reference
[C++ Language Interface]

A bounded difference shape. More...

`#include <ppl.hh>`

List of all members.

## Public Types

typedef T | coefficient_type_base
| The numeric base type upon which bounded differences are built.
typedef N | coefficient_type
| The (extended) numeric type of the inhomogeneous term of the inequalities defining a BDS.

## Public Member Functions

void | ascii_dump () const
| Writes to `std::cerr` an ASCII representation of `*this`.
void | ascii_dump (std::ostream &s) const
| Writes to `s` an ASCII representation of `*this`.
void | print () const
| Prints `*this` to `std::cerr` using `operator<<`.
bool | ascii_load (std::istream &s)
| Loads from `s` an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets `*this` accordingly. Returns `true` if successful, `false` otherwise.
memory_size_type | total_memory_in_bytes () const
| Returns the total size in bytes of the memory occupied by `*this`.
memory_size_type | external_memory_in_bytes () const
| Returns the size in bytes of the memory managed by `*this`.
int32_t | hash_code () const
| Returns a 32-bit hash code for `*this`.
Constructors, Assignment, Swap and Destructor
| BD_Shape (dimension_type num_dimensions=0, Degenerate_Element kind=UNIVERSE)
| Builds a universe or empty BDS of the specified space dimension.
| BD_Shape (const BD_Shape &y, Complexity_Class complexity=ANY_COMPLEXITY)
| Ordinary copy constructor.
template<typename U >
| BD_Shape (const BD_Shape< U > &y, Complexity_Class complexity=ANY_COMPLEXITY)
| Builds a conservative, upward approximation of `y`.
| BD_Shape (const Constraint_System &cs)
| Builds a BDS from the system of constraints `cs`.
| BD_Shape (const Congruence_System &cgs)
| Builds a BDS from a system of congruences.
| BD_Shape (const Generator_System &gs)
| Builds a BDS from the system of generators `gs`.
| BD_Shape (const Polyhedron &ph, Complexity_Class complexity=ANY_COMPLEXITY)
| Builds a BDS from the polyhedron `ph`.
template<typename Interval >
| BD_Shape (const Box< Interval > &box, Complexity_Class complexity=ANY_COMPLEXITY)
| Builds a BDS out of a box.
| BD_Shape (const Grid &grid, Complexity_Class complexity=ANY_COMPLEXITY)
| Builds a BDS out of a grid.
template<typename U >
| BD_Shape (const Octagonal_Shape< U > &os, Complexity_Class complexity=ANY_COMPLEXITY)
| Builds a BDS from an octagonal shape.
BD_Shape & | operator= (const BD_Shape &y)
| The assignment operator (`*this` and `y` can be dimension-incompatible).
void | swap (BD_Shape &y)
| Swaps `*this` with `y` (`*this` and `y` can be dimension-incompatible).
| ~BD_Shape ()
| Destructor.
Member Functions that Do Not Modify the BD_Shape
dimension_type | space_dimension () const
| Returns the dimension of the vector space enclosing `*this`.
dimension_type | affine_dimension () const
| Returns , if `*this` is empty; otherwise, returns the affine dimension of `*this`.
Constraint_System | constraints () const
| Returns a system of constraints defining `*this`.
Constraint_System | minimized_constraints () const
| Returns a minimized system of constraints defining `*this`.
Congruence_System | congruences () const
| Returns a system of (equality) congruences satisfied by `*this`.
Congruence_System | minimized_congruences () const
| Returns a minimal system of (equality) congruences satisfied by `*this` with the same affine dimension as `*this`.
bool | bounds_from_above (const Linear_Expression &expr) const
| Returns `true` if and only if `expr` is bounded from above in `*this`.
bool | bounds_from_below (const Linear_Expression &expr) const
| Returns `true` if and only if `expr` is bounded from below 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, Generator &g) 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, Generator &g) 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 | frequency (const Linear_Expression &expr, Coefficient &freq_n, Coefficient &freq_d, Coefficient &val_n, Coefficient &val_d) const
| Returns `true` if and only if there exist a unique value `val` such that `*this` saturates the equality `expr = val`.
bool | contains (const BD_Shape &y) const
| Returns `true` if and only if `*this` contains `y`.
bool | strictly_contains (const BD_Shape &y) const
| Returns `true` if and only if `*this` strictly contains `y`.
bool | is_disjoint_from (const BD_Shape &y) const
| Returns `true` if and only if `*this` and `y` are disjoint.
Poly_Con_Relation | relation_with (const Constraint &c) const
| Returns the relations holding between `*this` and the constraint `c`.
Poly_Con_Relation | relation_with (const Congruence &cg) const
| Returns the relations holding between `*this` and the congruence `cg`.
Poly_Gen_Relation | relation_with (const Generator &g) const
| Returns the relations holding between `*this` and the generator `g`.
bool | is_empty () const
| Returns `true` if and only if `*this` is an empty BDS.
bool | is_universe () const
| Returns `true` if and only if `*this` is a universe BDS.
bool | is_discrete () const
| Returns `true` if and only if `*this` is discrete.
bool | is_topologically_closed () const
| Returns `true` if and only if `*this` is a topologically closed subset of the vector space.
bool | is_bounded () const
| Returns `true` if and only if `*this` is a bounded BDS.
bool | contains_integer_point () const
| Returns `true` if and only if `*this` contains at least one integer point.
bool | constrains (Variable var) const
| Returns `true` if and only if `var` is constrained in `*this`.
bool | OK () const
| Returns `true` if and only if `*this` satisfies all its invariants.
Space-Dimension Preserving Member Functions that May Modify the BD_Shape
void | add_constraint (const Constraint &c)
| Adds a copy of constraint `c` to the system of bounded differences defining `*this`.
void | add_congruence (const Congruence &cg)
| Adds a copy of congruence `cg` to the system of congruences of `*this`.
void | add_constraints (const Constraint_System &cs)
| Adds the constraints in `cs` to the system of bounded differences defining `*this`.
void | add_recycled_constraints (Constraint_System &cs)
| Adds the constraints in `cs` to the system of constraints of `*this`.
void | add_congruences (const Congruence_System &cgs)
| Adds to `*this` constraints equivalent to the congruences in `cgs`.
void | add_recycled_congruences (Congruence_System &cgs)
| Adds to `*this` constraints equivalent to the congruences in `cgs`.
void | refine_with_constraint (const Constraint &c)
| Uses a copy of constraint `c` to refine the system of bounded differences defining `*this`.
void | refine_with_congruence (const Congruence &cg)
| Uses a copy of congruence `cg` to refine the system of bounded differences of `*this`.
void | refine_with_constraints (const Constraint_System &cs)
| Uses a copy of the constraints in `cs` to refine the system of bounded differences defining `*this`.
void | refine_with_congruences (const Congruence_System &cgs)
| Uses a copy of the congruences in `cgs` to refine the system of bounded differences defining `*this`.
void | unconstrain (Variable var)
| Computes the cylindrification of `*this` with respect to space dimension `var`, assigning the result to `*this`.
void | unconstrain (const Variables_Set &vars)
| Computes the cylindrification of `*this` with respect to the set of space dimensions `vars`, assigning the result to `*this`.
void | intersection_assign (const BD_Shape &y)
| Assigns to `*this` the intersection of `*this` and `y`.
void | upper_bound_assign (const BD_Shape &y)
| Assigns to `*this` the smallest BDS containing the union of `*this` and `y`.
bool | upper_bound_assign_if_exact (const BD_Shape &y)
| If the upper bound of `*this` and `y` is exact, it is assigned to `*this` and `true` is returned, otherwise `false` is returned.
bool | integer_upper_bound_assign_if_exact (const BD_Shape &y)
| If the integer upper bound of `*this` and `y` is exact, it is assigned to `*this` and `true` is returned; otherwise `false` is returned.
void | difference_assign (const BD_Shape &y)
| Assigns to `*this` the smallest BD shape containing the set difference of `*this` and `y`.
bool | simplify_using_context_assign (const BD_Shape &y)
| Assigns to `*this` a meet-preserving simplification of `*this` with respect to `y`. If `false` is returned, then the intersection is empty.
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` into 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` into the affine expression specified by `expr` and `denominator`.
void | generalized_affine_image (Variable var, Relation_Symbol relsym, const Linear_Expression &expr, Coefficient_traits::const_reference denominator=Coefficient_one())
| Assigns to `*this` the image of `*this` with respect to the affine relation , where is the relation symbol encoded by `relsym`.
void | generalized_affine_image (const Linear_Expression &lhs, Relation_Symbol relsym, const Linear_Expression &rhs)
| Assigns to `*this` the image of `*this` with respect to the affine relation , where is the relation symbol encoded by `relsym`.
void | generalized_affine_preimage (Variable var, Relation_Symbol relsym, const Linear_Expression &expr, Coefficient_traits::const_reference denominator=Coefficient_one())
| Assigns to `*this` the preimage of `*this` with respect to the affine relation , where is the relation symbol encoded by `relsym`.
void | generalized_affine_preimage (const Linear_Expression &lhs, Relation_Symbol relsym, const Linear_Expression &rhs)
| Assigns to `*this` the preimage of `*this` with respect to the affine relation , where is the relation symbol encoded by `relsym`.
void | bounded_affine_image (Variable var, const Linear_Expression &lb_expr, const Linear_Expression &ub_expr, Coefficient_traits::const_reference denominator=Coefficient_one())
| Assigns to `*this` the image of `*this` with respect to the bounded affine relation .
void | bounded_affine_preimage (Variable var, const Linear_Expression &lb_expr, const Linear_Expression &ub_expr, Coefficient_traits::const_reference denominator=Coefficient_one())
| Assigns to `*this` the preimage of `*this` with respect to the bounded affine relation .
void | time_elapse_assign (const BD_Shape &y)
| Assigns to `*this` the result of computing the time-elapse between `*this` and `y`.
void | wrap_assign (const Variables_Set &vars, Bounded_Integer_Type_Width w, Bounded_Integer_Type_Representation r, Bounded_Integer_Type_Overflow o, const Constraint_System *pcs=0, unsigned complexity_threshold=16, bool wrap_individually=true)
| Wraps the specified dimensions of the vector space.
void | drop_some_non_integer_points (Complexity_Class complexity=ANY_COMPLEXITY)
| Possibly tightens `*this` by dropping some points with non-integer coordinates.
void | drop_some_non_integer_points (const Variables_Set &vars, Complexity_Class complexity=ANY_COMPLEXITY)
| Possibly tightens `*this` by dropping some points with non-integer coordinates for the space dimensions corresponding to `vars`.
void | topological_closure_assign ()
| Assigns to `*this` its topological closure.
void | CC76_extrapolation_assign (const BD_Shape &y, unsigned *tp=0)
| Assigns to `*this` the result of computing the CC76-extrapolation between `*this` and `y`.
template<typename Iterator >
void | CC76_extrapolation_assign (const BD_Shape &y, Iterator first, Iterator last, unsigned *tp=0)
| Assigns to `*this` the result of computing the CC76-extrapolation between `*this` and `y`.
void | BHMZ05_widening_assign (const BD_Shape &y, unsigned *tp=0)
| Assigns to `*this` the result of computing the BHMZ05-widening of `*this` and `y`.
void | limited_BHMZ05_extrapolation_assign (const BD_Shape &y, const Constraint_System &cs, unsigned *tp=0)
| Improves the result of the BHMZ05-widening computation by also enforcing those constraints in `cs` that are satisfied by all the points of `*this`.
void | CC76_narrowing_assign (const BD_Shape &y)
| Assigns to `*this` the result of restoring in `y` the constraints of `*this` that were lost by CC76-extrapolation applications.
void | limited_CC76_extrapolation_assign (const BD_Shape &y, const Constraint_System &cs, unsigned *tp=0)
| Improves the result of the CC76-extrapolation computation by also enforcing those constraints in `cs` that are satisfied by all the points of `*this`.
void | H79_widening_assign (const BD_Shape &y, unsigned *tp=0)
| Assigns to `*this` the result of computing the H79-widening between `*this` and `y`.
void | widening_assign (const BD_Shape &y, unsigned *tp=0)
| Same as H79_widening_assign(y, tp).
void | limited_H79_extrapolation_assign (const BD_Shape &y, const Constraint_System &cs, unsigned *tp=0)
| Improves the result of the H79-widening computation by also enforcing those constraints in `cs` 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 dimensions and embeds the old BDS into the new space.
void | add_space_dimensions_and_project (dimension_type m)
| Adds `m` new dimensions to the BDS and does not embed it in the new vector space.
void | concatenate_assign (const BD_Shape &y)
| Assigns to `*this` the concatenation of `*this` and `y`, taken in this order.
void | remove_space_dimensions (const Variables_Set &vars)
| Removes all the specified dimensions.
void | remove_higher_space_dimensions (dimension_type new_dimension)
| Removes the higher dimensions 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 &vars, Variable dest)
| Folds the space dimensions in `vars` into `dest`.

## Static Public Member Functions

static dimension_type | max_space_dimension ()
| Returns the maximum space dimension that a BDS can handle.
static bool | can_recycle_constraint_systems ()
| Returns `false` indicating that this domain cannot recycle constraints.
static bool | can_recycle_congruence_systems ()
| Returns `false` indicating that this domain cannot recycle congruences.

## Friends

bool | operator== (const BD_Shape< T > &x, const BD_Shape< T > &y)
| Returns `true` if and only if `x` and `y` are the same BDS.

## Related Functions

(Note that these are not member functions.)
template<typename T >
std::ostream & | operator<< (std::ostream &s, const BD_Shape< T > &bds)
| Output operator.
template<typename T >
bool | operator!= (const BD_Shape< T > &x, const BD_Shape< T > &y)
| Returns `true` if and only if `x` and `y` aren't the same BDS.
template<typename To , typename T >
bool | rectilinear_distance_assign (Checked_Number< To, Extended_Number_Policy > &r, const BD_Shape< T > &x, const BD_Shape< T > &y, Rounding_Dir dir)
| Computes the rectilinear (or Manhattan) distance between `x` and `y`.
template<typename Temp , typename To , typename T >
bool | rectilinear_distance_assign (Checked_Number< To, Extended_Number_Policy > &r, const BD_Shape< T > &x, const BD_Shape< T > &y, Rounding_Dir dir, Temp &tmp0, Temp &tmp1, Temp &tmp2)
| Computes the rectilinear (or Manhattan) distance between `x` and `y`.
template<typename To , typename T >
bool | euclidean_distance_assign (Checked_Number< To, Extended_Number_Policy > &r, const BD_Shape< T > &x, const BD_Shape< T > &y, Rounding_Dir dir)
| Computes the euclidean distance between `x` and `y`.
template<typename Temp , typename To , typename T >
bool | euclidean_distance_assign (Checked_Number< To, Extended_Number_Policy > &r, const BD_Shape< T > &x, const BD_Shape< T > &y, Rounding_Dir dir, Temp &tmp0, Temp &tmp1, Temp &tmp2)
| Computes the euclidean distance between `x` and `y`.
template<typename To , typename T >
bool | l_infinity_distance_assign (Checked_Number< To, Extended_Number_Policy > &r, const BD_Shape< T > &x, const BD_Shape< T > &y, Rounding_Dir dir)
| Computes the distance between `x` and `y`.
template<typename Temp , typename To , typename T >
bool | l_infinity_distance_assign (Checked_Number< To, Extended_Number_Policy > &r, const BD_Shape< T > &x, const BD_Shape< T > &y, Rounding_Dir dir, Temp &tmp0, Temp &tmp1, Temp &tmp2)
| Computes the distance between `x` and `y`.
template<typename T >
void | swap (Parma_Polyhedra_Library::BD_Shape< T > &x, Parma_Polyhedra_Library::BD_Shape< T > &y)
| Specializes `std::swap`.

## Detailed Description

### template<typename T>
class Parma_Polyhedra_Library::BD_Shape< T >

A bounded difference shape.

The class template BD_Shape<T> allows for the efficient representation of a restricted kind of topologically closed convex polyhedra called bounded difference shapes (BDSs, for short). The name comes from the fact that the closed affine half-spaces that characterize the polyhedron can be expressed by constraints of the form or , where the inhomogeneous term is a rational number.

Based on the class template type parameter `T`, a family of extended numbers is built and used to approximate the inhomogeneous term of bounded differences. These extended numbers provide a representation for the value , as well as rounding-aware implementations for several arithmetic functions. The value of the type parameter `T` may be one of the following:

- a bounded precision integer type (e.g., `int32_t` or `int64_t`);
- a bounded precision floating point type (e.g., `float` or `double`);
- an unbounded integer or rational type, as provided by GMP (i.e., `mpz_class` or `mpq_class`).

The user interface for BDSs is meant to be as similar as possible to the one developed for the polyhedron class C_Polyhedron.

The domain of BD shapes optimally supports:

- tautological and inconsistent constraints and congruences;
- bounded difference constraints;
- non-proper congruences (i.e., equalities) that are expressible as bounded-difference constraints.

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

A constraint is a bounded difference if it has the form

where and , , are integer coefficients such that , or , or . The user is warned that the above bounded difference Constraint object will be mapped into a correct and optimal approximation that, depending on the expressive power of the chosen template argument `T`, may loose some precision. Also note that strict constraints are not bounded differences.

For instance, a Constraint object encoding will be approximated by:

- , if `T` is a (bounded or unbounded) integer type;
- , if `T` is the unbounded rational type `mpq_class`;
- , where , if `T` is a floating point type (having no exact representation for ).

On the other hand, depending from the context, a Constraint object encoding will be either upward approximated (e.g., by safely ignoring it) or it will cause an exception.

In the following examples it is assumed that the type argument `T` is one of the possible instances listed above and that variables `x`, `y` and `z` are defined (where they are used) as follows:

        Variable x(0);
        Variable y(1);
        Variable z(2);

Example 1
  The following code builds a BDS corresponding to a cube in , given as a system of constraints:

          Constraint_System cs;
          cs.insert(x >= 0);
          cs.insert(x <= 1);
          cs.insert(y >= 0);
          cs.insert(y <= 1);
          cs.insert(z >= 0);
          cs.insert(z <= 1);
          BD_Shape<T> bd(cs);

  Since only those constraints having the syntactic form of a bounded difference are optimally supported, the following code will throw an exception (caused by constraints 7, 8 and 9):

          Constraint_System cs;
          cs.insert(x >= 0);
          cs.insert(x <= 1);
          cs.insert(y >= 0);
          cs.insert(y <= 1);
          cs.insert(z >= 0);
          cs.insert(z <= 1);
          cs.insert(x + y <= 0);      // 7
          cs.insert(x - z + x >= 0);  // 8
          cs.insert(3*z - y <= 1);    // 9
          BD_Shape<T> bd(cs);

## Constructor & Destructor Documentation

template<typename T >

Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape | ( | dimension_type | num_dimensions = `0`,
|  | Degenerate_Element | kind = `UNIVERSE` |
| ) |  |  | `[inline, explicit]`

Builds a universe or empty BDS of the specified space dimension.

Parameters:

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

template<typename T >

Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape | ( | const BD_Shape< T > & | y,
|  | Complexity_Class | complexity = `ANY_COMPLEXITY` |
| ) |  |  | `[inline]`

Ordinary copy constructor.

The complexity argument is ignored.

template<typename T >
template<typename U >

Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape | ( | const BD_Shape< U > & | y,
|  | Complexity_Class | complexity = `ANY_COMPLEXITY` |
| ) |  |  | `[inline, explicit]`

Builds a conservative, upward approximation of `y`.

The complexity argument is ignored.

template<typename T >

Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape | ( | const Constraint_System & | cs | ) | `[inline, explicit]`

Builds a BDS from the system of constraints `cs`.

The BDS inherits the space dimension of `cs`.

Parameters:

  | cs | A system of BD constraints.

Exceptions:

  | std::invalid_argument | Thrown if `cs` contains a constraint which is not optimally supported by the BD shape domain.

template<typename T >

Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape | ( | const Congruence_System & | cgs | ) | `[inline, explicit]`

Builds a BDS from a system of congruences.

The BDS inherits the space dimension of `cgs`

Parameters:

  | cgs | A system of congruences.

Exceptions:

  | std::invalid_argument | Thrown if `cgs` contains congruences which are not optimally supported by the BD shape domain.

template<typename T >

Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape | ( | const Generator_System & | gs | ) | `[inline, explicit]`

Builds a BDS from the system of generators `gs`.

Builds the smallest BDS containing the polyhedron defined by `gs`. The BDS inherits the space dimension of `gs`.

Exceptions:

  | std::invalid_argument | Thrown if the system of generators is not empty but has no points.

template<typename T >

Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape | ( | const Polyhedron & | ph,
|  | Complexity_Class | complexity = `ANY_COMPLEXITY` |
| ) |  |  | `[inline, explicit]`

Builds a BDS from the polyhedron `ph`.

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

template<typename T >
template<typename Interval >

Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape | ( | const Box< Interval > & | box,
|  | Complexity_Class | complexity = `ANY_COMPLEXITY` |
| ) |  |  | `[inline, explicit]`

Builds a BDS out of a box.

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

Parameters:

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

Exceptions:

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

template<typename T >

Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape | ( | const Grid & | grid,
|  | Complexity_Class | complexity = `ANY_COMPLEXITY` |
| ) |  |  | `[inline, explicit]`

Builds a BDS out of a grid.

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

Parameters:

  | grid | The grid used to build the BDS.
  | complexity | This argument is ignored as the algorithm used has polynomial complexity.

Exceptions:

  | std::length_error | Thrown if the space dimension of `grid` exceeds the maximum allowed space dimension.

template<typename T >
template<typename U >

Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape | ( | const Octagonal_Shape< U > & | os,
|  | Complexity_Class | complexity = `ANY_COMPLEXITY` |
| ) |  |  | `[inline, explicit]`

Builds a BDS from an octagonal shape.

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

Parameters:

  | os | The octagonal shape used to build the BDS.
  | complexity | This argument is ignored as the algorithm used has polynomial complexity.

Exceptions:

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

## Member Function Documentation

template<typename T >

bool Parma_Polyhedra_Library::BD_Shape< T >::bounds_from_above | ( | const Linear_Expression & | expr | ) | const`[inline]`

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

Exceptions:

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

template<typename T >

bool Parma_Polyhedra_Library::BD_Shape< T >::bounds_from_below | ( | const Linear_Expression & | expr | ) | const`[inline]`

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

Exceptions:

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

template<typename T >

bool Parma_Polyhedra_Library::BD_Shape< T >::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 and only if the supremum is also the maximum value.

Exceptions:

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

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

template<typename T >

bool Parma_Polyhedra_Library::BD_Shape< T >::maximize | ( | const Linear_Expression & | expr,
|  | Coefficient & | sup_n,
|  | Coefficient & | sup_d,
|  | bool & | maximum,
|  | Generator & | g |
| ) |  |  | 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 and only if the supremum is also the maximum value;
  | g | When maximization succeeds, will be assigned the point or closure 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 from above, `false` is returned and `sup_n`, `sup_d`, `maximum` and `g` are left untouched.

template<typename T >

bool Parma_Polyhedra_Library::BD_Shape< T >::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 and only if the infimum is also the minimum 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` and `minimum` are left untouched.

template<typename T >

bool Parma_Polyhedra_Library::BD_Shape< T >::minimize | ( | const Linear_Expression & | expr,
|  | Coefficient & | inf_n,
|  | Coefficient & | inf_d,
|  | bool & | minimum,
|  | Generator & | g |
| ) |  |  | 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 and only if the infimum is also the minimum value;
  | g | When minimization succeeds, will be assigned a point or closure 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 `g` are left untouched.

template<typename T >

bool Parma_Polyhedra_Library::BD_Shape< T >::frequency | ( | const Linear_Expression & | expr,
|  | Coefficient & | freq_n,
|  | Coefficient & | freq_d,
|  | Coefficient & | val_n,
|  | Coefficient & | val_d |
| ) |  |  | const`[inline]`

Returns `true` if and only if there exist a unique value `val` such that `*this` saturates the equality `expr = val`.

Parameters:

  | expr | The linear expression for which the frequency is needed;
  | freq_n | If `true` is returned, the value is set to ; Present for interface compatibility with class Grid, where the frequency can have a non-zero value;
  | freq_d | If `true` is returned, the value is set to ;
  | val_n | The numerator of `val`;
  | val_d | The denominator of `val`;

Exceptions:

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

If `false` is returned, then `freq_n`, `freq_d`, `val_n` and `val_d` are left untouched.

template<typename T >

bool Parma_Polyhedra_Library::BD_Shape< T >::contains | ( | const BD_Shape< T > & | y | ) | const`[inline]`

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

Exceptions:

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

template<typename T >

bool Parma_Polyhedra_Library::BD_Shape< T >::strictly_contains | ( | const BD_Shape< T > & | 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 T >

bool Parma_Polyhedra_Library::BD_Shape< T >::is_disjoint_from | ( | const BD_Shape< T > & | y | ) | const`[inline]`

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

Exceptions:

  | std::invalid_argument | Thrown if `x` and `y` are topology-incompatible or dimension-incompatible.

template<typename T >

Poly_Con_Relation Parma_Polyhedra_Library::BD_Shape< T >::relation_with | ( | const Constraint & | c | ) | const`[inline]`

Returns the relations holding between `*this` and the constraint `c`.

Exceptions:

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

template<typename T >

Poly_Con_Relation Parma_Polyhedra_Library::BD_Shape< T >::relation_with | ( | const Congruence & | cg | ) | const`[inline]`

Returns the relations holding between `*this` and the congruence `cg`.

Exceptions:

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

template<typename T >

Poly_Gen_Relation Parma_Polyhedra_Library::BD_Shape< T >::relation_with | ( | const Generator & | g | ) | const`[inline]`

Returns the relations holding between `*this` and the generator `g`.

Exceptions:

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

template<typename T >

bool Parma_Polyhedra_Library::BD_Shape< T >::constrains | ( | Variable | var | ) | const`[inline]`

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

Exceptions:

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::add_constraint | ( | const Constraint & | c | ) | `[inline]`

Adds a copy of constraint `c` to the system of bounded differences defining `*this`.

Parameters:

  | c | The constraint to be added.

Exceptions:

  | std::invalid_argument | Thrown if `*this` and constraint `c` are dimension-incompatible, or `c` is not optimally supported by the BD shape domain.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::add_congruence | ( | const Congruence & | cg | ) | `[inline]`

Adds a copy of congruence `cg` to the system of congruences of `*this`.

Parameters:

  | cg | The congruence to be added.

Exceptions:

  | std::invalid_argument | Thrown if `*this` and congruence `cg` are dimension-incompatible, or `cg` is not optimally supported by the BD shape domain.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::add_constraints | ( | const Constraint_System & | cs | ) | `[inline]`

Adds the constraints in `cs` to the system of bounded differences defining `*this`.

Parameters:

  | cs | The constraints that will be added.

Exceptions:

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::add_recycled_constraints | ( | Constraint_System & | cs | ) | `[inline]`

Adds the constraints in `cs` to the system of constraints of `*this`.

Parameters:

  | cs | The constraint system to be added to `*this`. The constraints in `cs` may be recycled.

Exceptions:

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

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::add_congruences | ( | const Congruence_System & | cgs | ) | `[inline]`

Adds to `*this` constraints equivalent to the congruences in `cgs`.

Parameters:

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

Exceptions:

  | std::invalid_argument | Thrown if `*this` and `cgs` are dimension-incompatible, or `cgs` contains a congruence which is not optimally supported by the BD shape domain.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::add_recycled_congruences | ( | Congruence_System & | cgs | ) | `[inline]`

Adds to `*this` constraints equivalent to the congruences in `cgs`.

Parameters:

  | cgs | Contains the congruences that will be added to the system of constraints of `*this`. Its elements may be recycled.

Exceptions:

  | std::invalid_argument | Thrown if `*this` and `cgs` are dimension-incompatible, or `cgs` contains a congruence which is not optimally supported by the BD shape domain.

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::refine_with_constraint | ( | const Constraint & | c | ) | `[inline]`

Uses a copy of constraint `c` to refine the system of bounded differences defining `*this`.

Parameters:

  | c | The constraint. If it is not a bounded difference, it will be ignored.

Exceptions:

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::refine_with_congruence | ( | const Congruence & | cg | ) | `[inline]`

Uses a copy of congruence `cg` to refine the system of bounded differences of `*this`.

Parameters:

  | cg | The congruence. If it is not a bounded difference equality, it will be ignored.

Exceptions:

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::refine_with_constraints | ( | const Constraint_System & | cs | ) | `[inline]`

Uses a copy of the constraints in `cs` to refine the system of bounded differences defining `*this`.

Parameters:

  | cs | The constraint system to be used. Constraints that are not bounded differences are ignored.

Exceptions:

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::refine_with_congruences | ( | const Congruence_System & | cgs | ) | `[inline]`

Uses a copy of the congruences in `cgs` to refine the system of bounded differences defining `*this`.

Parameters:

  | cgs | The congruence system to be used. Congruences that are not bounded difference equalities are ignored.

Exceptions:

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::unconstrain | ( | Variable | var | ) | `[inline]`

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

Parameters:

  | var | The space dimension that will be unconstrained.

Exceptions:

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::unconstrain | ( | const Variables_Set & | vars | ) | `[inline]`

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

Parameters:

  | vars | The set of space dimension that will be unconstrained.

Exceptions:

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::intersection_assign | ( | const BD_Shape< T > & | y | ) | `[inline]`

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

Exceptions:

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::upper_bound_assign | ( | const BD_Shape< T > & | y | ) | `[inline]`

Assigns to `*this` the smallest BDS containing the union of `*this` and `y`.

Exceptions:

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

template<typename T >

bool Parma_Polyhedra_Library::BD_Shape< T >::upper_bound_assign_if_exact | ( | const BD_Shape< T > & | y | ) | `[inline]`

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

Exceptions:

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

template<typename T >

bool Parma_Polyhedra_Library::BD_Shape< T >::integer_upper_bound_assign_if_exact | ( | const BD_Shape< T > & | y | ) | `[inline]`

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

Exceptions:

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

Note:
  The integer upper bound of two rational BDS is the smallest rational BDS containing all the integral points of the two arguments. This method requires that the coefficient type parameter `T` is an integral type.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::difference_assign | ( | const BD_Shape< T > & | y | ) | `[inline]`

Assigns to `*this` the smallest BD shape containing the set difference of `*this` and `y`.

Exceptions:

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

template<typename T >

bool Parma_Polyhedra_Library::BD_Shape< T >::simplify_using_context_assign | ( | const BD_Shape< T > & | y | ) | `[inline]`

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

Exceptions:

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::affine_image | ( | Variable | var,
|  | const Linear_Expression & | expr,
|  | Coefficient_traits::const_reference | denominator = `Coefficient_one()` |
| ) |  |  | `[inline]`

Assigns to `*this` the affine image of `*this` under the function mapping variable `var` into 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.

Exceptions:

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::affine_preimage | ( | Variable | var,
|  | const Linear_Expression & | expr,
|  | Coefficient_traits::const_reference | denominator = `Coefficient_one()` |
| ) |  |  | `[inline]`

Assigns to `*this` the affine preimage of `*this` under the function mapping variable `var` into 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.

Exceptions:

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::generalized_affine_image | ( | Variable | var,
|  | Relation_Symbol | relsym,
|  | const Linear_Expression & | expr,
|  | Coefficient_traits::const_reference | denominator = `Coefficient_one()` |
| ) |  |  | `[inline]`

Assigns to `*this` the image of `*this` with respect to the affine relation , where is the relation symbol encoded by `relsym`.

Parameters:

  | var | The left hand side variable of the generalized affine transfer function.
  | relsym | The relation symbol.
  | expr | The numerator of the right hand side affine expression.
  | denominator | The denominator of the right hand side affine expression.

Exceptions:

  | std::invalid_argument | Thrown if `denominator` is zero or if `expr` and `*this` are dimension-incompatible or if `var` is not a dimension of `*this` or if `relsym` is a strict relation symbol.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::generalized_affine_image | ( | const Linear_Expression & | lhs,
|  | Relation_Symbol | relsym,
|  | const Linear_Expression & | rhs |
| ) |  |  | `[inline]`

Assigns to `*this` the image of `*this` with respect to the affine relation , where is the relation symbol encoded by `relsym`.

Parameters:

  | lhs | The left hand side affine expression.
  | relsym | The relation symbol.
  | rhs | The right hand side affine expression.

Exceptions:

  | std::invalid_argument | Thrown if `*this` is dimension-incompatible with `lhs` or `rhs` or if `relsym` is a strict relation symbol.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::generalized_affine_preimage | ( | Variable | var,
|  | Relation_Symbol | relsym,
|  | const Linear_Expression & | expr,
|  | Coefficient_traits::const_reference | denominator = `Coefficient_one()` |
| ) |  |  | `[inline]`

Assigns to `*this` the preimage of `*this` with respect to the affine relation , where is the relation symbol encoded by `relsym`.

Parameters:

  | var | The left hand side variable of the generalized affine transfer function.
  | relsym | The relation symbol.
  | expr | The numerator of the right hand side affine expression.
  | denominator | The denominator of the right hand side affine expression.

Exceptions:

  | std::invalid_argument | Thrown if `denominator` is zero or if `expr` and `*this` are dimension-incompatible or if `var` is not a dimension of `*this` or if `relsym` is a strict relation symbol.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::generalized_affine_preimage | ( | const Linear_Expression & | lhs,
|  | Relation_Symbol | relsym,
|  | const Linear_Expression & | rhs |
| ) |  |  | `[inline]`

Assigns to `*this` the preimage of `*this` with respect to the affine relation , where is the relation symbol encoded by `relsym`.

Parameters:

  | lhs | The left hand side affine expression.
  | relsym | The relation symbol.
  | rhs | The right hand side affine expression.

Exceptions:

  | std::invalid_argument | Thrown if `*this` is dimension-incompatible with `lhs` or `rhs` or if `relsym` is a strict relation symbol.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::bounded_affine_image | ( | Variable | var,
|  | const Linear_Expression & | lb_expr,
|  | const Linear_Expression & | ub_expr,
|  | Coefficient_traits::const_reference | denominator = `Coefficient_one()` |
| ) |  |  | `[inline]`

Assigns to `*this` the image of `*this` with respect to the bounded affine relation .

Parameters:

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

Exceptions:

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::bounded_affine_preimage | ( | Variable | var,
|  | const Linear_Expression & | lb_expr,
|  | const Linear_Expression & | ub_expr,
|  | Coefficient_traits::const_reference | denominator = `Coefficient_one()` |
| ) |  |  | `[inline]`

Assigns to `*this` the preimage of `*this` with respect to the bounded affine relation .

Parameters:

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

Exceptions:

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::time_elapse_assign | ( | const BD_Shape< T > & | y | ) | `[inline]`

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.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::wrap_assign | ( | const Variables_Set & | vars,
|  | Bounded_Integer_Type_Width | w,
|  | Bounded_Integer_Type_Representation | r,
|  | Bounded_Integer_Type_Overflow | o,
|  | const Constraint_System * | pcs = `0`,
|  | unsigned | complexity_threshold = `16`,
|  | bool | wrap_individually = `true` |
| ) |  |  | `[inline]`

Wraps the specified dimensions of the vector space.

Parameters:

  | vars | The set of Variable objects corresponding to the space dimensions to be wrapped.
  | w | The width of the bounded integer type corresponding to all the dimensions to be wrapped.
  | r | The representation of the bounded integer type corresponding to all the dimensions to be wrapped.
  | o | The overflow behavior of the bounded integer type corresponding to all the dimensions to be wrapped.

  pcs

  Possibly null pointer to a constraint system whose variables are contained in `vars`. If `*pcs` depends on variables not in `vars`, the behavior is undefined. When non-null, the pointed-to constraint system is assumed to represent the conditional or looping construct guard with respect to which wrapping is performed. Since wrapping requires the computation of upper bounds and due to non-distributivity of constraint refinement over upper bounds, passing a constraint system in this way can be more precise than refining the result of the wrapping operation with the constraints in `*pcs`.

  | complexity_threshold | A precision parameter of the wrapping operator: higher values result in possibly improved precision.
  | wrap_individually | `true` if the dimensions should be wrapped individually (something that results in much greater efficiency to the detriment of precision).

Exceptions:

  | std::invalid_argument | Thrown if `*pcs` is dimension-incompatible with `vars`, or if `*this` is dimension-incompatible `vars` or with `*pcs`.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::drop_some_non_integer_points | ( | Complexity_Class | complexity = `ANY_COMPLEXITY` | ) | `[inline]`

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

Parameters:

  | complexity | The maximal complexity of any algorithms used.

Note:
  Currently there is no optimality guarantee, not even if `complexity` is `ANY_COMPLEXITY`.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::drop_some_non_integer_points | ( | const Variables_Set & | vars,
|  | Complexity_Class | complexity = `ANY_COMPLEXITY` |
| ) |  |  | `[inline]`

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

Parameters:

  | vars | Points with non-integer coordinates for these variables/space-dimensions can be discarded.
  | complexity | The maximal complexity of any algorithms used.

Note:
  Currently there is no optimality guarantee, not even if `complexity` is `ANY_COMPLEXITY`.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::CC76_extrapolation_assign | ( | const BD_Shape< T > & | y,
|  | unsigned * | tp = `0` |
| ) |  |  | `[inline]`

Assigns to `*this` the result of computing the CC76-extrapolation between `*this` and `y`.

Parameters:

  | y | A BDS 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.

template<typename T >
template<typename Iterator >

void Parma_Polyhedra_Library::BD_Shape< T >::CC76_extrapolation_assign | ( | const BD_Shape< T > & | y,
|  | Iterator | first,
|  | Iterator | last,
|  | unsigned * | tp = `0` |
| ) |  |  | `[inline]`

Assigns to `*this` the result of computing the CC76-extrapolation between `*this` and `y`.

Parameters:

  | y | A BDS that must be contained in `*this`.
  | first | An iterator referencing the first stop-point.
  | last | An iterator referencing one past the last stop-point.
  | 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.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::BHMZ05_widening_assign | ( | const BD_Shape< T > & | y,
|  | unsigned * | tp = `0` |
| ) |  |  | `[inline]`

Assigns to `*this` the result of computing the BHMZ05-widening of `*this` and `y`.

Parameters:

  | y | A BDS 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.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::limited_BHMZ05_extrapolation_assign | ( | const BD_Shape< T > & | y,
|  | const Constraint_System & | cs,
|  | unsigned * | tp = `0` |
| ) |  |  | `[inline]`

Improves the result of the BHMZ05-widening computation by also enforcing those constraints in `cs` that are satisfied by all the points of `*this`.

Parameters:

  | y | A BDS that must be contained in `*this`.
  | cs | The system of constraints used to improve the widened BDS.
  | 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 or if `cs` contains a strict inequality.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::CC76_narrowing_assign | ( | const BD_Shape< T > & | y | ) | `[inline]`

Assigns to `*this` the result of restoring in `y` the constraints of `*this` that were lost by CC76-extrapolation applications.

Parameters:

  | y | A BDS that must contain `*this`.

Exceptions:

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

Note:
  As was the case for widening operators, the argument `y` is meant to denote the value computed in the previous iteration step, whereas `*this` denotes the value computed in the current iteration step (in the decreasing iteration sequence). Hence, the call `x.CC76_narrowing_assign(y)` will assign to `x` the result of the computation .

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::limited_CC76_extrapolation_assign | ( | const BD_Shape< T > & | y,
|  | const Constraint_System & | cs,
|  | unsigned * | tp = `0` |
| ) |  |  | `[inline]`

Improves the result of the CC76-extrapolation computation by also enforcing those constraints in `cs` that are satisfied by all the points of `*this`.

Parameters:

  | y | A BDS that must be contained in `*this`.
  | cs | The system of constraints used to improve the widened BDS.
  | 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 or if `cs` contains a strict inequality.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::H79_widening_assign | ( | const BD_Shape< T > & | y,
|  | unsigned * | tp = `0` |
| ) |  |  | `[inline]`

Assigns to `*this` the result of computing the H79-widening between `*this` and `y`.

Parameters:

  | y | A BDS 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.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::limited_H79_extrapolation_assign | ( | const BD_Shape< T > & | y,
|  | const Constraint_System & | cs,
|  | unsigned * | tp = `0` |
| ) |  |  | `[inline]`

Improves the result of the H79-widening computation by also enforcing those constraints in `cs` that are satisfied by all the points of `*this`.

Parameters:

  | y | A BDS that must be contained in `*this`.
  | cs | The system of constraints used to improve the widened BDS.
  | 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.

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::add_space_dimensions_and_embed | ( | dimension_type | m | ) | `[inline]`

Adds `m` new dimensions and embeds the old BDS into the new space.

Parameters:

  | m | The number of dimensions to add.

The new dimensions will be those having the highest indexes in the new BDS, which is defined by a system of bounded differences in which the variables running through the new dimensions are unconstrained. For instance, when starting from the BDS and adding a third dimension, the result will be the BDS

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::add_space_dimensions_and_project | ( | dimension_type | m | ) | `[inline]`

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

Parameters:

  | m | The number of dimensions to add.

The new dimensions will be those having the highest indexes in the new BDS, which is defined by a system of bounded differences in which the variables running through the new dimensions are all constrained to be equal to 0. For instance, when starting from the BDS and adding a third dimension, the result will be the BDS

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::concatenate_assign | ( | const BD_Shape< T > & | y | ) | `[inline]`

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::remove_space_dimensions | ( | const Variables_Set & | vars | ) | `[inline]`

Removes all the specified dimensions.

Parameters:

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

Exceptions:

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::remove_higher_space_dimensions | ( | dimension_type | new_dimension | ) | `[inline]`

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

Exceptions:

  | std::invalid_argument | Thrown if `new_dimension` is greater than the space dimension of `*this`.

template<typename T >
template<typename Partial_Function >

void Parma_Polyhedra_Library::BD_Shape< T >::map_space_dimensions | ( | const Partial_Function & | pfunc | ) | `[inline]`

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

Parameters:

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

The template type parameter Partial_Function must provide the following methods.

          bool has_empty_codomain() const

returns `true` if and only if the represented partial function has an empty co-domain (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 co-domain of the partial function.

          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.

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::expand_space_dimension | ( | Variable | var,
|  | dimension_type | m |
| ) |  |  | `[inline]`

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

template<typename T >

void Parma_Polyhedra_Library::BD_Shape< T >::fold_space_dimensions | ( | const Variables_Set & | vars,
|  | Variable | dest |
| ) |  |  | `[inline]`

Folds the space dimensions in `vars` into `dest`.

Parameters:

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

Exceptions:

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

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

template<typename T >

int32_t Parma_Polyhedra_Library::BD_Shape< T >::hash_code | ( |  | ) | const`[inline]`

Returns a 32-bit hash code for `*this`.

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

## Friends And Related Function Documentation

template<typename T >

bool operator== | ( | const BD_Shape< T > & | x,
|  | const BD_Shape< T > & | y |
| ) |  |  | `[friend]`

Returns `true` if and only if `x` and `y` are the same BDS.

Note that `x` and `y` may be dimension-incompatible shapes: in this case, the value `false` is returned.

template<typename T >

std::ostream & operator<< | ( | std::ostream & | s,
|  | const BD_Shape< T > & | c |
| ) |  |  | `[related]`

Output operator.

Writes a textual representation of `bds` on `s:` `false` is written if `bds` is an empty polyhedron; `true` is written if `bds` is the universe polyhedron; a system of constraints defining `bds` is written otherwise, all constraints separated by ", ".

template<typename T >

bool operator!= | ( | const BD_Shape< T > & | x,
|  | const BD_Shape< T > & | y |
| ) |  |  | `[related]`

Returns `true` if and only if `x` and `y` aren't the same BDS.

Note that `x` and `y` may be dimension-incompatible shapes: in this case, the value `true` is returned.

template<typename To , typename T >

bool rectilinear_distance_assign | ( | Checked_Number< To, Extended_Number_Policy > & | r,
|  | const BD_Shape< T > & | x,
|  | const BD_Shape< T > & | y,
|  | Rounding_Dir | dir |
| ) |  |  | `[related]`

Computes the rectilinear (or Manhattan) distance between `x` and `y`.

If the rectilinear distance between `x` and `y` is defined, stores an approximation of it into `r` and returns `true`; returns `false` otherwise.

The direction of the approximation is specified by `dir`.

All computations are performed using variables of type Checked_Number<To, Extended_Number_Policy>.

If the rectilinear distance between `x` and `y` is defined, stores an approximation of it into `r` and returns `true`; returns `false` otherwise.

The direction of the approximation is specified by `dir`.

All computations are performed using variables of type Checked_Number<Temp, Extended_Number_Policy>.

template<typename Temp , typename To , typename T >

bool rectilinear_distance_assign | ( | Checked_Number< To, Extended_Number_Policy > & | r,
|  | const BD_Shape< T > & | x,
|  | const BD_Shape< T > & | y,
|  | Rounding_Dir | dir,
|  | Temp & | tmp0,
|  | Temp & | tmp1,
|  | Temp & | tmp2 |
| ) |  |  | `[related]`

Computes the rectilinear (or Manhattan) distance between `x` and `y`.

If the rectilinear distance between `x` and `y` is defined, stores an approximation of it into `r` and returns `true`; returns `false` otherwise.

The direction of the approximation is specified by `dir`.

All computations are performed using the temporary variables `tmp0`, `tmp1` and `tmp2`.

template<typename To , typename T >

bool euclidean_distance_assign | ( | Checked_Number< To, Extended_Number_Policy > & | r,
|  | const BD_Shape< T > & | x,
|  | const BD_Shape< T > & | y,
|  | Rounding_Dir | dir |
| ) |  |  | `[related]`

Computes the euclidean distance between `x` and `y`.

If the euclidean distance between `x` and `y` is defined, stores an approximation of it into `r` and returns `true`; returns `false` otherwise.

The direction of the approximation is specified by `dir`.

All computations are performed using variables of type Checked_Number<To, Extended_Number_Policy>.

If the euclidean distance between `x` and `y` is defined, stores an approximation of it into `r` and returns `true`; returns `false` otherwise.

The direction of the approximation is specified by `dir`.

All computations are performed using variables of type Checked_Number<Temp, Extended_Number_Policy>.

template<typename Temp , typename To , typename T >

bool euclidean_distance_assign | ( | Checked_Number< To, Extended_Number_Policy > & | r,
|  | const BD_Shape< T > & | x,
|  | const BD_Shape< T > & | y,
|  | Rounding_Dir | dir,
|  | Temp & | tmp0,
|  | Temp & | tmp1,
|  | Temp & | tmp2 |
| ) |  |  | `[related]`

Computes the euclidean distance between `x` and `y`.

If the euclidean distance between `x` and `y` is defined, stores an approximation of it into `r` and returns `true`; returns `false` otherwise.

The direction of the approximation is specified by `dir`.

All computations are performed using the temporary variables `tmp0`, `tmp1` and `tmp2`.

template<typename To , typename T >

bool l_infinity_distance_assign | ( | Checked_Number< To, Extended_Number_Policy > & | r,
|  | const BD_Shape< T > & | x,
|  | const BD_Shape< T > & | y,
|  | Rounding_Dir | dir |
| ) |  |  | `[related]`

Computes the distance between `x` and `y`.

If the distance between `x` and `y` is defined, stores an approximation of it into `r` and returns `true`; returns `false` otherwise.

The direction of the approximation is specified by `dir`.

All computations are performed using variables of type Checked_Number<To, Extended_Number_Policy>.

If the distance between `x` and `y` is defined, stores an approximation of it into `r` and returns `true`; returns `false` otherwise.

The direction of the approximation is specified by `dir`.

All computations are performed using variables of type Checked_Number<Temp, Extended_Number_Policy>.

template<typename Temp , typename To , typename T >

bool l_infinity_distance_assign | ( | Checked_Number< To, Extended_Number_Policy > & | r,
|  | const BD_Shape< T > & | x,
|  | const BD_Shape< T > & | y,
|  | Rounding_Dir | dir,
|  | Temp & | tmp0,
|  | Temp & | tmp1,
|  | Temp & | tmp2 |
| ) |  |  | `[related]`

Computes the distance between `x` and `y`.

If the distance between `x` and `y` is defined, stores an approximation of it into `r` and returns `true`; returns `false` otherwise.

The direction of the approximation is specified by `dir`.

All computations are performed using the temporary variables `tmp0`, `tmp1` and `tmp2`.

template<typename T >

void swap | ( | Parma_Polyhedra_Library::BD_Shape< T > & | x,
|  | Parma_Polyhedra_Library::BD_Shape< T > & | y |
| ) |  |  | `[related]`

Specializes `std::swap`.

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

- ppl.hh