Public Types | |
typedef T | base_type |
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 | |
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) | |
Ordinary copy-constructor. | |
template<typename U> | |
BD_Shape (const BD_Shape< U > &y) | |
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 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 . | |
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 ![]() *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 . | |
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 . | |
Poly_Con_Relation | relation_with (const Constraint &c) const |
Returns the relations holding between *this and the constraint c . | |
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 | 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 . | |
bool | add_constraint_and_minimize (const Constraint &c) |
Adds a copy of constraint c to the system of bounded differences defining *this . | |
void | add_constraints (const Constraint_System &cs) |
Adds the constraints in cs to the system of bounded differences defining *this . | |
bool | add_constraints_and_minimize (const Constraint_System &cs) |
Adds the constraints in cs to the system of bounded differences defining *this . | |
void | intersection_assign (const BD_Shape &y) |
Assigns to *this the intersection of *this and y . | |
bool | intersection_assign_and_minimize (const BD_Shape &y) |
Assigns to *this the intersection of *this and y . | |
void | bds_hull_assign (const BD_Shape &y) |
Assigns to *this the smallest BDS containing the convex union of *this and y . | |
bool | bds_hull_assign_and_minimize (const BD_Shape &y) |
Assigns to *this the smallest BDS containing the convex union of *this and y . | |
void | upper_bound_assign (const BD_Shape &y) |
Same as bds_hull_assign. | |
bool | bds_hull_assign_if_exact (const BD_Shape &y) |
If the bds-hull 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 BD_Shape &y) |
Same as bds_hull_assign_if_exact. | |
void | bds_difference_assign (const BD_Shape &y) |
Assigns to *this the poly-difference of *this and y . | |
void | difference_assign (const BD_Shape &y) |
Same as bds_difference_assign. | |
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 ![]() ![]() 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 ![]() ![]() 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 ![]() ![]() relsym . | |
void | time_elapse_assign (const BD_Shape &y) |
Assigns to *this the result of computing the time-elapse between *this and y . | |
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 | 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) |
Seeing a BDS as a set of tuples (its points), assigns to *this all the tuples that can be obtained by concatenating, in the order given, a tuple of *this with a tuple of y . | |
void | remove_space_dimensions (const Variables_Set &to_be_removed) |
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 PartialFunction> | |
void | map_space_dimensions (const PartialFunction &pfunc) |
Remaps the dimensions of the vector space according to a partial function. | |
Static Public Member Functions | |
static dimension_type | max_space_dimension () |
Returns the maximum space dimension that a BDS can handle. | |
Friends | |
std::ostream & | operator<< (std::ostream &s, const BD_Shape< T > &c) |
Output operator. | |
Related Functions | |
(Note that these are not member functions.) | |
template<typename T> | |
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. | |
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, const 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, const 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, const 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, const 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, const Rounding_Dir dir) |
Computes the ![]() 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, const Rounding_Dir dir, Temp &tmp0, Temp &tmp1, Temp &tmp2) |
Computes the ![]() 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 . |
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:
int32_t
or int64_t
);float
or double
);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. At the interface level, bounded differences are specified using objects of type Constraint: such a constraint is a bounded difference if it is of the form
where and
,
,
are integer coefficients such that
, or
, or
. The user is warned that the above Constraint object will be mapped into a correct approximation that, depending on the expressive power of the chosen template argument
T
, may loose some precision. In particular, constraint objects that do not encode a bounded difference will be simply (and safely) ignored.
For instance, a Constraint object encoding will be approximated by:
T
is a (bounded or unbounded) integer type;T
is the unbounded rational type mpq_class
;T
is a floating point type (having no exact representation for
On the other hand, a Constraint object encoding will be safely ignored in all of the above cases.
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);
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);
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);
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.
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. |
Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape | ( | const Constraint_System & | cs | ) | [inline] |
Builds a BDS from the system of constraints cs
.
The BDS inherits the space dimension of cs
.
cs | A system of constraints: constraints that are not bounded differences are ignored (even though they may have contributed to the space dimension). |
std::invalid_argument | Thrown if the system of constraints cs contains strict inequalities. |
Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape | ( | const Generator_System & | gs | ) | [inline] |
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
.
std::invalid_argument | Thrown if the system of generators is not empty but has no points. |
Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape | ( | const Polyhedron & | ph, | |
Complexity_Class | complexity = ANY_COMPLEXITY | |||
) | [inline] |
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
.
bool Parma_Polyhedra_Library::BD_Shape< T >::contains | ( | const BD_Shape< T > & | y | ) | const [inline] |
Returns true
if and only if *this
contains y
.
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
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
.
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
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
.
std::invalid_argument | Thrown if *this and constraint c are dimension-incompatible or if c is a strict inequality or if c is not a bounded difference constraint. |
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
.
std::invalid_argument | Thrown if *this and generator g are dimension-incompatible. |
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
.
c | The constraint to be added. If it is not a bounded difference, it will be simply ignored. |
std::invalid_argument | Thrown if *this and constraint c are dimension-incompatible, or if c is a strict inequality. |
bool Parma_Polyhedra_Library::BD_Shape< T >::add_constraint_and_minimize | ( | const Constraint & | c | ) | [inline] |
Adds a copy of constraint c
to the system of bounded differences defining *this
.
false
if and only if the result is empty.c | The constraint to be added. If it is not a bounded difference, it will be simply ignored. |
std::invalid_argument | Thrown if *this and constraint c are dimension-incompatible, or if c is a strict inequality. |
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
.
cs | The constraints that will be added. Constraints that are not bounded differences will be simply ignored. |
std::invalid_argument | Thrown if *this and cs are dimension-incompatible, or if cs contains a strict inequality. |
bool Parma_Polyhedra_Library::BD_Shape< T >::add_constraints_and_minimize | ( | const Constraint_System & | cs | ) | [inline] |
Adds the constraints in cs
to the system of bounded differences defining *this
.
false
if and only if the result is empty.cs | The constraints that will be added. Constraints that are not bounded differences will be simply ignored. |
std::invalid_argument | Thrown if *this and cs are dimension-incompatible, or if cs contains a strict inequality. |
void Parma_Polyhedra_Library::BD_Shape< T >::intersection_assign | ( | const BD_Shape< T > & | y | ) | [inline] |
Assigns to *this
the intersection of *this
and y
.
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
bool Parma_Polyhedra_Library::BD_Shape< T >::intersection_assign_and_minimize | ( | const BD_Shape< T > & | y | ) | [inline] |
Assigns to *this
the intersection of *this
and y
.
false
if and only if the result is empty.std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
void Parma_Polyhedra_Library::BD_Shape< T >::bds_hull_assign | ( | const BD_Shape< T > & | y | ) | [inline] |
Assigns to *this
the smallest BDS containing the convex union of *this
and y
.
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
bool Parma_Polyhedra_Library::BD_Shape< T >::bds_hull_assign_and_minimize | ( | const BD_Shape< T > & | y | ) | [inline] |
Assigns to *this
the smallest BDS containing the convex union of *this
and y
.
false
if and only if the result is empty.std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
bool Parma_Polyhedra_Library::BD_Shape< T >::bds_hull_assign_if_exact | ( | const BD_Shape< T > & | y | ) | [inline] |
If the bds-hull of *this
and y
is exact, it is assigned to *this
and true
is returned, otherwise false
is returned.
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
void Parma_Polyhedra_Library::BD_Shape< T >::bds_difference_assign | ( | const BD_Shape< T > & | y | ) | [inline] |
Assigns to *this
the poly-difference of *this
and y
.
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
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
.
var | The variable to which the affine expression is assigned. | |
expr | The numerator of the affine expression. | |
denominator | The denominator of the affine expression. |
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 . |
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
.
var | The variable to which the affine expression is substituted. | |
expr | The numerator of the affine expression. | |
denominator | The denominator of the affine expression. |
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 . |
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
.
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. |
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. |
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
.
lhs | The left hand side affine expression. | |
relsym | The relation symbol. | |
rhs | The right hand side affine expression. |
std::invalid_argument | Thrown if *this is dimension-incompatible with lhs or rhs or if relsym is a strict relation symbol. |
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
.
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. |
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. |
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
.
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
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
.
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). |
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
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
.
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). |
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
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
.
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). |
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
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
.
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). |
std::invalid_argument | Thrown if *this , y and cs are dimension-incompatible or if cs contains a strict inequality. |
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.
y | A BDS that must contain *this . |
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
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 descreasing iteration sequence). Hence, the call x.CC76_narrowing_assign(y)
will assign to x
the result of the computation 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
.
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). |
std::invalid_argument | Thrown if *this , y and cs are dimension-incompatible or if cs contains a strict inequality. |
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
.
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). |
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
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
.
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). |
std::invalid_argument | Thrown if *this , y and cs are dimension-incompatible. |
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.
m | The number of dimensions to add. |
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.
m | The number of dimensions to add. |
void Parma_Polyhedra_Library::BD_Shape< T >::concatenate_assign | ( | const BD_Shape< T > & | y | ) | [inline] |
Seeing a BDS as a set of tuples (its points), assigns to *this
all the tuples that can be obtained by concatenating, in the order given, a tuple of *this
with a tuple of y
.
Let and
be the BDSs corresponding, on entry, to
*this
and y
, respectively. Upon successful completion, *this
will represent the BDS such that
Another way of seeing it is as follows: first increases the space dimension of *this
by adding y.space_dimension()
new dimensions; then adds to the system of constraints of *this
a renamed-apart version of the constraints of y
.
void Parma_Polyhedra_Library::BD_Shape< T >::remove_space_dimensions | ( | const Variables_Set & | to_be_removed | ) | [inline] |
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
.
std::invalid_argument | Thrown if new_dimension is greater than the space dimension of *this . |
void Parma_Polyhedra_Library::BD_Shape< T >::map_space_dimensions | ( | const PartialFunction & | pfunc | ) | [inline] |
Remaps the dimensions of the vector space according to a partial function.
pfunc | The partial function specifying the destiny of each dimension. |
bool has_empty_codomain() const
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
bool maps(dimension_type i, dimension_type& j) const
i
. If j
and true
is returned. If 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.
std::ostream & operator<< | ( | std::ostream & | s, | |
const BD_Shape< T > & | c | |||
) | [friend] |
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 ", ".
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.
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.
bool rectilinear_distance_assign | ( | Checked_Number< To, Extended_Number_Policy > & | r, | |
const BD_Shape< T > & | x, | |||
const BD_Shape< T > & | y, | |||
const 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>.
bool rectilinear_distance_assign | ( | Checked_Number< To, Extended_Number_Policy > & | r, | |
const BD_Shape< T > & | x, | |||
const BD_Shape< T > & | y, | |||
const 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
.
bool euclidean_distance_assign | ( | Checked_Number< To, Extended_Number_Policy > & | r, | |
const BD_Shape< T > & | x, | |||
const BD_Shape< T > & | y, | |||
const 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>.
bool euclidean_distance_assign | ( | Checked_Number< To, Extended_Number_Policy > & | r, | |
const BD_Shape< T > & | x, | |||
const BD_Shape< T > & | y, | |||
const 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
.
bool l_infinity_distance_assign | ( | Checked_Number< To, Extended_Number_Policy > & | r, | |
const BD_Shape< T > & | x, | |||
const BD_Shape< T > & | y, | |||
const 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>.
bool l_infinity_distance_assign | ( | Checked_Number< To, Extended_Number_Policy > & | r, | |
const BD_Shape< T > & | x, | |||
const BD_Shape< T > & | y, | |||
const 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
.
void swap | ( | Parma_Polyhedra_Library::BD_Shape< T > & | x, | |
Parma_Polyhedra_Library::BD_Shape< T > & | y | |||
) | [related] |
Specializes std::swap
.