PPL
1.2
|
A grid. More...
#include <Grid_defs.hh>
Classes | |
class | Status |
A conjunctive assertion about a grid. More... | |
Public Types | |
typedef Coefficient | coefficient_type |
The numeric type of coefficients. More... | |
Public Member Functions | |
Grid (dimension_type num_dimensions=0, Degenerate_Element kind=UNIVERSE) | |
Builds a grid having the specified properties. More... | |
Grid (const Congruence_System &cgs) | |
Builds a grid, copying a system of congruences. More... | |
Grid (Congruence_System &cgs, Recycle_Input dummy) | |
Builds a grid, recycling a system of congruences. More... | |
Grid (const Constraint_System &cs) | |
Builds a grid, copying a system of constraints. More... | |
Grid (Constraint_System &cs, Recycle_Input dummy) | |
Builds a grid, recycling a system of constraints. More... | |
Grid (const Grid_Generator_System &ggs) | |
Builds a grid, copying a system of grid generators. More... | |
Grid (Grid_Generator_System &ggs, Recycle_Input dummy) | |
Builds a grid, recycling a system of grid generators. More... | |
template<typename Interval > | |
Grid (const Box< Interval > &box, Complexity_Class complexity=ANY_COMPLEXITY) | |
Builds a grid out of a box. More... | |
template<typename U > | |
Grid (const BD_Shape< U > &bd, Complexity_Class complexity=ANY_COMPLEXITY) | |
Builds a grid out of a bounded-difference shape. More... | |
template<typename U > | |
Grid (const Octagonal_Shape< U > &os, Complexity_Class complexity=ANY_COMPLEXITY) | |
Builds a grid out of an octagonal shape. More... | |
Grid (const Polyhedron &ph, Complexity_Class complexity=ANY_COMPLEXITY) | |
Builds a grid from a polyhedron using algorithms whose complexity does not exceed the one specified by complexity . If complexity is ANY_COMPLEXITY , then the grid built is the smallest one containing ph . More... | |
Grid (const Grid &y, Complexity_Class complexity=ANY_COMPLEXITY) | |
Ordinary copy constructor. More... | |
Grid & | operator= (const Grid &y) |
The assignment operator. (*this and y can be dimension-incompatible.) More... | |
Member Functions that Do Not Modify the Grid | |
dimension_type | space_dimension () const |
Returns the dimension of the vector space enclosing *this . More... | |
dimension_type | affine_dimension () const |
Returns ![]() *this is empty; otherwise, returns the affine dimension of *this . More... | |
Constraint_System | constraints () const |
Returns a system of equality constraints satisfied by *this with the same affine dimension as *this . More... | |
Constraint_System | minimized_constraints () const |
Returns a minimal system of equality constraints satisfied by *this with the same affine dimension as *this . More... | |
const Congruence_System & | congruences () const |
Returns the system of congruences. More... | |
const Congruence_System & | minimized_congruences () const |
Returns the system of congruences in minimal form. More... | |
const Grid_Generator_System & | grid_generators () const |
Returns the system of generators. More... | |
const Grid_Generator_System & | minimized_grid_generators () const |
Returns the minimized system of generators. More... | |
Poly_Con_Relation | relation_with (const Congruence &cg) const |
Returns the relations holding between *this and cg . More... | |
Poly_Gen_Relation | relation_with (const Grid_Generator &g) const |
Returns the relations holding between *this and g . More... | |
Poly_Gen_Relation | relation_with (const Generator &g) const |
Returns the relations holding between *this and g . More... | |
Poly_Con_Relation | relation_with (const Constraint &c) const |
Returns the relations holding between *this and c . More... | |
bool | is_empty () const |
Returns true if and only if *this is an empty grid. More... | |
bool | is_universe () const |
Returns true if and only if *this is a universe grid. More... | |
bool | is_topologically_closed () const |
Returns true if and only if *this is a topologically closed subset of the vector space. More... | |
bool | is_disjoint_from (const Grid &y) const |
Returns true if and only if *this and y are disjoint. More... | |
bool | is_discrete () const |
Returns true if and only if *this is discrete. More... | |
bool | is_bounded () const |
Returns true if and only if *this is bounded. More... | |
bool | contains_integer_point () const |
Returns true if and only if *this contains at least one integer point. More... | |
bool | constrains (Variable var) const |
Returns true if and only if var is constrained in *this . More... | |
bool | bounds_from_above (const Linear_Expression &expr) const |
Returns true if and only if expr is bounded in *this . More... | |
bool | bounds_from_below (const Linear_Expression &expr) const |
Returns true if and only if expr is bounded in *this . More... | |
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. More... | |
bool | maximize (const Linear_Expression &expr, Coefficient &sup_n, Coefficient &sup_d, bool &maximum, Generator &point) const |
Returns true if and only if *this is not empty and expr is bounded from above in *this , in which case the supremum value and a point where expr reaches it are computed. More... | |
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. More... | |
bool | minimize (const Linear_Expression &expr, Coefficient &inf_n, Coefficient &inf_d, bool &minimum, Generator &point) const |
Returns true if and only if *this is not empty and expr is bounded from below in *this , in which case the infimum value and a point where expr reaches it are computed. More... | |
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 *this is not empty and frequency for *this with respect to expr is defined, in which case the frequency and the value for expr that is closest to zero are computed. More... | |
bool | contains (const Grid &y) const |
Returns true if and only if *this contains y . More... | |
bool | strictly_contains (const Grid &y) const |
Returns true if and only if *this strictly contains y . More... | |
bool | OK (bool check_not_empty=false) const |
Checks if all the invariants are satisfied. More... | |
Space Dimension Preserving Member Functions that May Modify the Grid | |
void | add_congruence (const Congruence &cg) |
Adds a copy of congruence cg to *this . More... | |
void | add_grid_generator (const Grid_Generator &g) |
Adds a copy of grid generator g to the system of generators of *this . More... | |
void | add_congruences (const Congruence_System &cgs) |
Adds a copy of each congruence in cgs to *this . More... | |
void | add_recycled_congruences (Congruence_System &cgs) |
Adds the congruences in cgs to *this. More... | |
void | add_constraint (const Constraint &c) |
Adds to *this a congruence equivalent to constraint c . More... | |
void | add_constraints (const Constraint_System &cs) |
Adds to *this congruences equivalent to the constraints in cs . More... | |
void | add_recycled_constraints (Constraint_System &cs) |
Adds to *this congruences equivalent to the constraints in cs . More... | |
void | refine_with_congruence (const Congruence &cg) |
Uses a copy of the congruence cg to refine *this . More... | |
void | refine_with_congruences (const Congruence_System &cgs) |
Uses a copy of the congruences in cgs to refine *this . More... | |
void | refine_with_constraint (const Constraint &c) |
Uses a copy of the constraint c to refine *this . More... | |
void | refine_with_constraints (const Constraint_System &cs) |
Uses a copy of the constraints in cs to refine *this . More... | |
void | add_grid_generators (const Grid_Generator_System &gs) |
Adds a copy of the generators in gs to the system of generators of *this . More... | |
void | add_recycled_grid_generators (Grid_Generator_System &gs) |
Adds the generators in gs to the system of generators of this . More... | |
void | unconstrain (Variable var) |
Computes the cylindrification of *this with respect to space dimension var , assigning the result to *this . More... | |
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 . More... | |
void | intersection_assign (const Grid &y) |
Assigns to *this the intersection of *this and y . More... | |
void | upper_bound_assign (const Grid &y) |
Assigns to *this the least upper bound of *this and y . More... | |
bool | upper_bound_assign_if_exact (const Grid &y) |
If the upper bound of *this and y is exact it is assigned to this and true is returned, otherwise false is returned. More... | |
void | difference_assign (const Grid &y) |
Assigns to *this the grid-difference of *this and y . More... | |
bool | simplify_using_context_assign (const Grid &y) |
Assigns to *this a meet-preserving simplification of *this with respect to y . If false is returned, then the intersection is empty. More... | |
void | affine_image (Variable var, const Linear_Expression &expr, Coefficient_traits::const_reference denominator=Coefficient_one()) |
Assigns to *this the affine image of this under the function mapping variable var to the affine expression specified by expr and denominator . More... | |
void | affine_preimage (Variable var, const Linear_Expression &expr, Coefficient_traits::const_reference denominator=Coefficient_one()) |
Assigns to *this the affine preimage of *this under the function mapping variable var to the affine expression specified by expr and denominator . More... | |
void | generalized_affine_image (Variable var, Relation_Symbol relsym, const Linear_Expression &expr, Coefficient_traits::const_reference denominator=Coefficient_one(), Coefficient_traits::const_reference modulus=Coefficient_zero()) |
Assigns to *this the image of *this with respect to the generalized affine relation ![]() | |
void | generalized_affine_preimage (Variable var, Relation_Symbol relsym, const Linear_Expression &expr, Coefficient_traits::const_reference denominator=Coefficient_one(), Coefficient_traits::const_reference modulus=Coefficient_zero()) |
Assigns to *this the preimage of *this with respect to the generalized affine relation ![]() | |
void | generalized_affine_image (const Linear_Expression &lhs, Relation_Symbol relsym, const Linear_Expression &rhs, Coefficient_traits::const_reference modulus=Coefficient_zero()) |
Assigns to *this the image of *this with respect to the generalized affine relation ![]() | |
void | generalized_affine_preimage (const Linear_Expression &lhs, Relation_Symbol relsym, const Linear_Expression &rhs, Coefficient_traits::const_reference modulus=Coefficient_zero()) |
Assigns to *this the preimage of *this with respect to the generalized affine relation ![]() | |
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 Grid &y) |
Assigns to *this the result of computing the time-elapse between *this and y . More... | |
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 *cs_p=0, unsigned complexity_threshold=16, bool wrap_individually=true) |
Wraps the specified dimensions of the vector space. More... | |
void | drop_some_non_integer_points (Complexity_Class complexity=ANY_COMPLEXITY) |
Possibly tightens *this by dropping all points with non-integer coordinates. More... | |
void | drop_some_non_integer_points (const Variables_Set &vars, Complexity_Class complexity=ANY_COMPLEXITY) |
Possibly tightens *this by dropping all points with non-integer coordinates for the space dimensions corresponding to vars . More... | |
void | topological_closure_assign () |
Assigns to *this its topological closure. More... | |
void | congruence_widening_assign (const Grid &y, unsigned *tp=NULL) |
Assigns to *this the result of computing the Grid widening between *this and y using congruence systems. More... | |
void | generator_widening_assign (const Grid &y, unsigned *tp=NULL) |
Assigns to *this the result of computing the Grid widening between *this and y using generator systems. More... | |
void | widening_assign (const Grid &y, unsigned *tp=NULL) |
Assigns to *this the result of computing the Grid widening between *this and y . More... | |
void | limited_congruence_extrapolation_assign (const Grid &y, const Congruence_System &cgs, unsigned *tp=NULL) |
Improves the result of the congruence variant of Grid widening computation by also enforcing those congruences in cgs that are satisfied by all the points of *this . More... | |
void | limited_generator_extrapolation_assign (const Grid &y, const Congruence_System &cgs, unsigned *tp=NULL) |
Improves the result of the generator variant of the Grid widening computation by also enforcing those congruences in cgs that are satisfied by all the points of *this . More... | |
void | limited_extrapolation_assign (const Grid &y, const Congruence_System &cgs, unsigned *tp=NULL) |
Improves the result of the Grid widening computation by also enforcing those congruences in cgs that are satisfied by all the points of *this . More... | |
Member Functions that May Modify the Dimension of the Vector Space | |
void | add_space_dimensions_and_embed (dimension_type m) |
Adds m new space dimensions and embeds the old grid in the new vector space. More... | |
void | add_space_dimensions_and_project (dimension_type m) |
Adds m new space dimensions to the grid and does not embed it in the new vector space. More... | |
void | concatenate_assign (const Grid &y) |
Assigns to *this the concatenation of *this and y , taken in this order. More... | |
void | remove_space_dimensions (const Variables_Set &vars) |
Removes all the specified dimensions from the vector space. More... | |
void | remove_higher_space_dimensions (dimension_type new_dimension) |
Removes the higher dimensions of the vector space so that the resulting space will have dimension new_dimension .. More... | |
template<typename Partial_Function > | |
void | map_space_dimensions (const Partial_Function &pfunc) |
Remaps the dimensions of the vector space according to a partial function. More... | |
void | expand_space_dimension (Variable var, dimension_type m) |
Creates m copies of the space dimension corresponding to var . More... | |
void | fold_space_dimensions (const Variables_Set &vars, Variable dest) |
Folds the space dimensions in vars into dest . More... | |
Miscellaneous Member Functions | |
~Grid () | |
Destructor. More... | |
void | m_swap (Grid &y) |
Swaps *this with grid y . (*this and y can be dimension-incompatible.) More... | |
void | ascii_dump () const |
Writes to std::cerr an ASCII representation of *this . More... | |
void | ascii_dump (std::ostream &s) const |
Writes to s an ASCII representation of *this . More... | |
void | print () const |
Prints *this to std::cerr using operator<< . More... | |
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. More... | |
memory_size_type | total_memory_in_bytes () const |
Returns the total size in bytes of the memory occupied by *this . More... | |
memory_size_type | external_memory_in_bytes () const |
Returns the size in bytes of the memory managed by *this . More... | |
int32_t | hash_code () const |
Returns a 32-bit hash code for *this . More... | |
Static Public Member Functions | |
static dimension_type | max_space_dimension () |
Returns the maximum space dimension all kinds of Grid can handle. More... | |
static bool | can_recycle_congruence_systems () |
Returns true indicating that this domain has methods that can recycle congruences. More... | |
static bool | can_recycle_constraint_systems () |
Returns true indicating that this domain has methods that can recycle constraints. More... | |
Private Types | |
enum | Dimension_Kind { PARAMETER = 0, LINE = 1, GEN_VIRTUAL = 2, PROPER_CONGRUENCE = PARAMETER, CON_VIRTUAL = LINE, EQUALITY = GEN_VIRTUAL } |
enum | Three_Valued_Boolean { TVB_TRUE, TVB_FALSE, TVB_DONT_KNOW } |
typedef std::vector< Dimension_Kind > | Dimension_Kinds |
Private Member Functions | |
void | construct (dimension_type num_dimensions, Degenerate_Element kind) |
Builds a grid universe or empty grid. More... | |
void | construct (Congruence_System &cgs) |
Builds a grid from a system of congruences. More... | |
void | construct (Grid_Generator_System &ggs) |
Builds a grid from a system of grid generators. More... | |
Three_Valued_Boolean | quick_equivalence_test (const Grid &y) const |
Polynomial but incomplete equivalence test between grids. More... | |
bool | is_included_in (const Grid &y) const |
Returns true if and only if *this is included in y . More... | |
bool | bounds (const Linear_Expression &expr, const char *method_call) const |
Checks if and how expr is bounded in *this . More... | |
bool | max_min (const Linear_Expression &expr, const char *method_call, Coefficient &ext_n, Coefficient &ext_d, bool &included, Generator *point=NULL) const |
Maximizes or minimizes expr subject to *this . More... | |
bool | frequency_no_check (const Linear_Expression &expr, Coefficient &freq_n, Coefficient &freq_d, Coefficient &val_n, Coefficient &val_d) const |
Returns true if and only if *this is not empty and frequency for *this with respect to expr is defined, in which case the frequency and the value for expr that is closest to zero are computed. More... | |
bool | bounds_no_check (const Linear_Expression &expr) const |
Checks if and how expr is bounded in *this . More... | |
void | add_congruence_no_check (const Congruence &cg) |
Adds the congruence cg to *this . More... | |
void | add_constraint_no_check (const Constraint &c) |
Uses the constraint c to refine *this . More... | |
void | refine_no_check (const Constraint &c) |
Uses the constraint c to refine *this . More... | |
void | add_space_dimensions (Congruence_System &cgs, Grid_Generator_System &gs, dimension_type dims) |
Adds new space dimensions to the given systems. More... | |
void | add_space_dimensions (Grid_Generator_System &gs, Congruence_System &cgs, dimension_type dims) |
Adds new space dimensions to the given systems. More... | |
Private Verifiers: Verify if Individual Flags are Set | |
bool | marked_empty () const |
Returns true if the grid is known to be empty. More... | |
bool | congruences_are_up_to_date () const |
Returns true if the system of congruences is up-to-date. More... | |
bool | generators_are_up_to_date () const |
Returns true if the system of generators is up-to-date. More... | |
bool | congruences_are_minimized () const |
Returns true if the system of congruences is minimized. More... | |
bool | generators_are_minimized () const |
Returns true if the system of generators is minimized. More... | |
State Flag Setters: Set Only the Specified Flags | |
void | set_zero_dim_univ () |
Sets status to express that the grid is the universe 0-dimension vector space, clearing all corresponding matrices. More... | |
void | set_empty () |
Sets status to express that the grid is empty, clearing all corresponding matrices. More... | |
void | set_congruences_up_to_date () |
Sets status to express that congruences are up-to-date. More... | |
void | set_generators_up_to_date () |
Sets status to express that generators are up-to-date. More... | |
void | set_congruences_minimized () |
Sets status to express that congruences are minimized. More... | |
void | set_generators_minimized () |
Sets status to express that generators are minimized. More... | |
State Flag Cleaners: Clear Only the Specified Flag | |
void | clear_empty () |
Clears the status flag indicating that the grid is empty. More... | |
void | clear_congruences_up_to_date () |
Sets status to express that congruences are out of date. More... | |
void | clear_generators_up_to_date () |
Sets status to express that generators are out of date. More... | |
void | clear_congruences_minimized () |
Sets status to express that congruences are no longer minimized. More... | |
void | clear_generators_minimized () |
Sets status to express that generators are no longer minimized. More... | |
Updating Matrices | |
void | update_congruences () const |
Updates and minimizes the congruences from the generators. More... | |
bool | update_generators () const |
Updates and minimizes the generators from the congruences. More... | |
Minimization of Descriptions | |
bool | minimize () const |
Minimizes both the congruences and the generators. More... | |
Widening- and Extrapolation-Related Functions | |
void | select_wider_congruences (const Grid &y, Congruence_System &selected_cgs) const |
Copies a widened selection of congruences from y to selected_cgs . More... | |
void | select_wider_generators (const Grid &y, Grid_Generator_System &widened_ggs) const |
Copies widened generators from y to widened_ggs . More... | |
Static Private Member Functions | |
Minimization-related Static Member Functions | |
static void | normalize_divisors (Grid_Generator_System &sys, Coefficient &divisor, const Grid_Generator *first_point=NULL) |
Normalizes the divisors in sys . More... | |
static void | normalize_divisors (Grid_Generator_System &sys) |
Normalizes the divisors in sys . More... | |
static void | normalize_divisors (Grid_Generator_System &sys, Grid_Generator_System &gen_sys) |
Normalize all the divisors in sys and gen_sys . More... | |
static void | conversion (Congruence_System &source, Grid_Generator_System &dest, Dimension_Kinds &dim_kinds) |
Converts generator system dest to be equivalent to congruence system source . More... | |
static void | conversion (Grid_Generator_System &source, Congruence_System &dest, Dimension_Kinds &dim_kinds) |
Converts congruence system dest to be equivalent to generator system source . More... | |
static bool | simplify (Congruence_System &cgs, Dimension_Kinds &dim_kinds) |
Converts cgs to upper triangular (i.e. minimized) form. More... | |
static void | simplify (Grid_Generator_System &ggs, Dimension_Kinds &dim_kinds) |
Converts gs to lower triangular (i.e. minimized) form. More... | |
static void | reduce_line_with_line (Grid_Generator &row, Grid_Generator &pivot, dimension_type column) |
Reduces the line row using the line pivot . More... | |
static void | reduce_equality_with_equality (Congruence &row, const Congruence &pivot, dimension_type column) |
Reduces the equality row using the equality pivot . More... | |
template<typename R > | |
static void | reduce_pc_with_pc (R &row, R &pivot, dimension_type column, dimension_type start, dimension_type end) |
Reduces row using pivot . More... | |
static void | reduce_parameter_with_line (Grid_Generator &row, const Grid_Generator &pivot, dimension_type column, Swapping_Vector< Grid_Generator > &sys, dimension_type num_columns) |
Reduce row using pivot . More... | |
static void | reduce_congruence_with_equality (Congruence &row, const Congruence &pivot, dimension_type column, Swapping_Vector< Congruence > &sys) |
Reduce row using pivot . More... | |
template<typename M > | |
static void | reduce_reduced (Swapping_Vector< typename M::row_type > &sys, dimension_type dim, dimension_type pivot_index, dimension_type start, dimension_type end, const Dimension_Kinds &sys_dim_kinds, bool generators=true) |
Reduce column dim in rows preceding pivot_index in sys . More... | |
static void | multiply_grid (const Coefficient &multiplier, Congruence &cg, Swapping_Vector< Congruence > &dest, dimension_type num_rows) |
Multiply the elements of dest by multiplier . More... | |
static void | multiply_grid (const Coefficient &multiplier, Grid_Generator &gen, Swapping_Vector< Grid_Generator > &dest, dimension_type num_rows) |
Multiply the elements of dest by multiplier . More... | |
static bool | lower_triangular (const Congruence_System &sys, const Dimension_Kinds &dim_kinds) |
If sys is lower triangular return true , else return false . More... | |
static bool | upper_triangular (const Grid_Generator_System &sys, const Dimension_Kinds &dim_kinds) |
If sys is upper triangular return true , else return false . More... | |
template<typename M , typename R > | |
static bool | rows_are_zero (M &system, dimension_type first, dimension_type last, dimension_type row_size) |
Checks that trailing rows contain only zero terms. More... | |
Private Attributes | |
Congruence_System | con_sys |
The system of congruences. More... | |
Grid_Generator_System | gen_sys |
The system of generators. More... | |
Status | status |
The status flags to keep track of the grid's internal state. More... | |
dimension_type | space_dim |
The number of dimensions of the enclosing vector space. More... | |
Dimension_Kinds | dim_kinds |
Friends | |
class | Parma_Polyhedra_Library::Grid_Certificate |
template<typename Interval > | |
class | Parma_Polyhedra_Library::Box |
bool | operator== (const Grid &x, const Grid &y) |
Related Functions | |
(Note that these are not member functions.) | |
std::ostream & | operator<< (std::ostream &s, const Grid &gr) |
Output operator. More... | |
void | swap (Grid &x, Grid &y) |
Swaps x with y . More... | |
bool | operator== (const Grid &x, const Grid &y) |
Returns true if and only if x and y are the same grid. More... | |
bool | operator!= (const Grid &x, const Grid &y) |
Returns true if and only if x and y are different grids. More... | |
bool | operator!= (const Grid &x, const Grid &y) |
void | swap (Grid &x, Grid &y) |
bool | operator== (const Grid &x, const Grid &y) |
std::ostream & | operator<< (std::ostream &s, const Grid &gr) |
Exception Throwers | |
void | throw_dimension_incompatible (const char *method, const char *other_name, dimension_type other_dim) const |
void | throw_dimension_incompatible (const char *method, const char *gr_name, const Grid &gr) const |
void | throw_dimension_incompatible (const char *method, const char *le_name, const Linear_Expression &le) const |
void | throw_dimension_incompatible (const char *method, const char *cg_name, const Congruence &cg) const |
void | throw_dimension_incompatible (const char *method, const char *c_name, const Constraint &c) const |
void | throw_dimension_incompatible (const char *method, const char *g_name, const Grid_Generator &g) const |
void | throw_dimension_incompatible (const char *method, const char *g_name, const Generator &g) const |
void | throw_dimension_incompatible (const char *method, const char *cgs_name, const Congruence_System &cgs) const |
void | throw_dimension_incompatible (const char *method, const char *cs_name, const Constraint_System &cs) const |
void | throw_dimension_incompatible (const char *method, const char *gs_name, const Grid_Generator_System &gs) const |
void | throw_dimension_incompatible (const char *method, const char *var_name, Variable var) const |
void | throw_dimension_incompatible (const char *method, dimension_type required_space_dim) const |
static void | throw_invalid_argument (const char *method, const char *reason) |
static void | throw_invalid_constraint (const char *method, const char *c_name) |
static void | throw_invalid_constraints (const char *method, const char *cs_name) |
static void | throw_invalid_generator (const char *method, const char *g_name) |
static void | throw_invalid_generators (const char *method, const char *gs_name) |
A grid.
An object of the class Grid represents a rational grid.
The domain of grids optimally supports:
Depending on the method, using a constraint that is not optimally supported by the domain will either raise an exception or result in a (possibly non-optimal) upward approximation.
The domain of grids support a concept of double description similar to the one developed for polyhedra: hence, a grid can be specified as either a finite system of congruences or a finite system of generators (see Section Rational Grids) and it is always possible to obtain either representation. That is, if we know the system of congruences, we can obtain from this a system of generators that define the same grid and vice versa. These systems can contain redundant members, or they can be in the minimal form.
A key attribute of any grid is its space dimension (the dimension of the enclosing vector space):
Note that two different grids can be defined on the zero-dimension space: the empty grid and the universe grid .
x
and y
are defined (where they are used) as follows: add_space_dimensions_and_embed
: We build the universe grid in the 1-dimension space
add_space_dimensions_and_project
: The first two lines of code are the same as in Example 4 for add_space_dimensions_and_embed
. After the last line of code, the resulting grid is the singleton set affine_image
: x
is instead affine_preimage
: var
and the affine expression and the denominator are the same as in Example 6, while the resulting grid is similar but translated 3 integers to the left (all the pairs x
is x
, for example, the affine expression remove_space_dimensions
: remove_space_dimensions
operator, unexpected results can be obtained. For instance, by using the following code we would obtain a different result: vars2
we are actually removing variable remove_space_dimensions
is not idempotent: removing twice the same non-empty set of dimensions is never the same as removing them just once. Definition at line 363 of file Grid_defs.hh.
The numeric type of coefficients.
Definition at line 366 of file Grid_defs.hh.
|
private |
Definition at line 1994 of file Grid_defs.hh.
|
inlineexplicit |
Builds a grid having the specified properties.
num_dimensions | The number of dimensions of the vector space enclosing the grid; |
kind | Specifies whether the universe or the empty grid has to be built. |
std::length_error | Thrown if num_dimensions exceeds the maximum allowed space dimension. |
Definition at line 122 of file Grid_inlines.hh.
References construct(), and OK().
|
inlineexplicit |
Builds a grid, copying a system of congruences.
The grid inherits the space dimension of the congruence system.
cgs | The system of congruences defining the grid. |
std::length_error | Thrown if num_dimensions exceeds the maximum allowed space dimension. |
Definition at line 136 of file Grid_inlines.hh.
References construct().
|
inline |
Builds a grid, recycling a system of congruences.
The grid inherits the space dimension of the congruence system.
cgs | The system of congruences defining the grid. Its data-structures may be recycled to build the grid. |
dummy | A dummy tag to syntactically differentiate this one from the other constructors. |
std::length_error | Thrown if num_dimensions exceeds the maximum allowed space dimension. |
Definition at line 150 of file Grid_inlines.hh.
References construct().
|
explicit |
Builds a grid, copying a system of constraints.
The grid inherits the space dimension of the constraint system.
cs | The system of constraints defining the grid. |
std::invalid_argument | Thrown if the constraint system cs contains inequality constraints. |
std::length_error | Thrown if num_dimensions exceeds the maximum allowed space dimension. |
Definition at line 64 of file Grid_public.cc.
References Parma_Polyhedra_Library::Constraint_System::begin(), con_sys, construct(), Parma_Polyhedra_Library::Constraint_System::end(), Parma_Polyhedra_Library::Congruence_System::insert(), OK(), Parma_Polyhedra_Library::Grid::Status::set_empty(), set_zero_dim_univ(), space_dim, Parma_Polyhedra_Library::Constraint_System::space_dimension(), status, throw_invalid_constraints(), and Parma_Polyhedra_Library::Congruence::zero_dim_false().
Parma_Polyhedra_Library::Grid::Grid | ( | Constraint_System & | cs, |
Recycle_Input | dummy | ||
) |
Builds a grid, recycling a system of constraints.
The grid inherits the space dimension of the constraint system.
cs | The system of constraints defining the grid. Its data-structures may be recycled to build the grid. |
dummy | A dummy tag to syntactically differentiate this one from the other constructors. |
std::invalid_argument | Thrown if the constraint system cs contains inequality constraints. |
std::length_error | Thrown if num_dimensions exceeds the maximum allowed space dimension. |
Definition at line 107 of file Grid_public.cc.
References Parma_Polyhedra_Library::Constraint_System::begin(), con_sys, construct(), Parma_Polyhedra_Library::Constraint_System::end(), Parma_Polyhedra_Library::Congruence_System::insert(), OK(), Parma_Polyhedra_Library::Grid::Status::set_empty(), set_zero_dim_univ(), space_dim, Parma_Polyhedra_Library::Constraint_System::space_dimension(), status, throw_invalid_constraint(), and Parma_Polyhedra_Library::Congruence::zero_dim_false().
|
inlineexplicit |
Builds a grid, copying a system of grid generators.
The grid inherits the space dimension of the generator system.
ggs | The system of generators defining the grid. |
std::invalid_argument | Thrown if the system of generators is not empty but has no points. |
std::length_error | Thrown if num_dimensions exceeds the maximum allowed space dimension. |
Definition at line 163 of file Grid_inlines.hh.
References construct().
|
inline |
Builds a grid, recycling a system of grid generators.
The grid inherits the space dimension of the generator system.
ggs | The system of generators defining the grid. Its data-structures may be recycled to build the grid. |
dummy | A dummy tag to syntactically differentiate this one from the other constructors. |
std::invalid_argument | Thrown if the system of generators is not empty but has no points. |
std::length_error | Thrown if num_dimensions exceeds the maximum allowed space dimension. |
Definition at line 177 of file Grid_inlines.hh.
References construct().
|
explicit |
Builds a grid out of a box.
The grid inherits the space dimension of the box. The built grid is the most precise grid that includes the box.
box | The box representing the grid to be built. |
complexity | This argument is ignored as the algorithm used has polynomial complexity. |
std::length_error | Thrown if the space dimension of box exceeds the maximum allowed space dimension. |
Definition at line 36 of file Grid_templates.hh.
References Parma_Polyhedra_Library::check_space_dimension_overflow(), con_sys, Parma_Polyhedra_Library::Grid_Generator::divisor(), Parma_Polyhedra_Library::exact_div_assign(), Parma_Polyhedra_Library::Grid_Generator::expr, Parma_Polyhedra_Library::gcd_assign(), gen_sys, Parma_Polyhedra_Library::Box< ITV >::has_lower_bound(), Parma_Polyhedra_Library::Box< ITV >::has_upper_bound(), Parma_Polyhedra_Library::Congruence_System::insert(), Parma_Polyhedra_Library::Grid_Generator_System::insert(), Parma_Polyhedra_Library::Box< ITV >::is_empty(), max_space_dimension(), Parma_Polyhedra_Library::neg_assign(), Parma_Polyhedra_Library::Grid_Generator::OK(), OK(), PPL_DIRTY_TEMP_COEFFICIENT, Parma_Polyhedra_Library::Grid_Generator::scale_to_divisor(), Parma_Polyhedra_Library::Linear_Expression::set(), set_congruences_up_to_date(), set_empty(), set_generators_up_to_date(), Parma_Polyhedra_Library::Congruence_System::set_space_dimension(), Parma_Polyhedra_Library::Grid_Generator_System::set_space_dimension(), set_zero_dim_univ(), space_dim, Parma_Polyhedra_Library::Box< ITV >::space_dimension(), and Parma_Polyhedra_Library::Grid_Generator_System::sys.
|
inlineexplicit |
Builds a grid out of a bounded-difference shape.
The grid inherits the space dimension of the BDS. The built grid is the most precise grid that includes the BDS.
bd | The BDS representing the grid to be built. |
complexity | This argument is ignored as the algorithm used has polynomial complexity. |
std::length_error | Thrown if the space dimension of bd exceeds the maximum allowed space dimension. |
Definition at line 191 of file Grid_inlines.hh.
References Parma_Polyhedra_Library::BD_Shape< T >::congruences(), and construct().
|
inlineexplicit |
Builds a grid out of an octagonal shape.
The grid inherits the space dimension of the octagonal shape. The built grid is the most precise grid that includes the octagonal shape.
os | The octagonal shape representing the grid to be built. |
complexity | This argument is ignored as the algorithm used has polynomial complexity. |
std::length_error | Thrown if the space dimension of os exceeds the maximum allowed space dimension. |
Definition at line 206 of file Grid_inlines.hh.
References Parma_Polyhedra_Library::Octagonal_Shape< T >::congruences(), and construct().
|
explicit |
Builds a grid from a polyhedron using algorithms whose complexity does not exceed the one specified by complexity
. If complexity
is ANY_COMPLEXITY
, then the grid built is the smallest one containing ph
.
The grid inherits the space dimension of polyhedron.
ph | The polyhedron. |
complexity | The complexity class. |
std::length_error | Thrown if num_dimensions exceeds the maximum allowed space dimension. |
Definition at line 150 of file Grid_public.cc.
References Parma_Polyhedra_Library::Linear_Expression::all_homogeneous_terms_are_zero(), Parma_Polyhedra_Library::ANY_COMPLEXITY, Parma_Polyhedra_Library::Coefficient_one(), Parma_Polyhedra_Library::Polyhedron::constraints(), Parma_Polyhedra_Library::Polyhedron::constraints_are_minimized(), Parma_Polyhedra_Library::Polyhedron::constraints_are_up_to_date(), construct(), Parma_Polyhedra_Library::Polyhedron::generators(), Parma_Polyhedra_Library::Polyhedron::generators_are_up_to_date(), Parma_Polyhedra_Library::Congruence_System::insert(), Parma_Polyhedra_Library::Grid_Generator_System::insert(), Parma_Polyhedra_Library::Polyhedron::is_empty(), Parma_Polyhedra_Library::Linear_Expression::linear_combine(), Parma_Polyhedra_Library::Polyhedron::marked_empty(), Parma_Polyhedra_Library::Polyhedron::minimize(), OK(), PPL_DIRTY_TEMP_COEFFICIENT, set_empty(), Parma_Polyhedra_Library::Linear_Expression::set_space_dimension(), set_zero_dim_univ(), space_dim, and Parma_Polyhedra_Library::Polyhedron::space_dimension().
Parma_Polyhedra_Library::Grid::Grid | ( | const Grid & | y, |
Complexity_Class | complexity = ANY_COMPLEXITY |
||
) |
Ordinary copy constructor.
The complexity argument is ignored.
Definition at line 38 of file Grid_public.cc.
References con_sys, congruences_are_up_to_date(), gen_sys, generators_are_up_to_date(), Parma_Polyhedra_Library::Congruence_System::set_space_dimension(), and space_dim.
|
inline |
|
inline |
Adds a copy of congruence cg
to *this
.
std::invalid_argument | Thrown if *this and congruence cg are dimension-incompatible. |
Definition at line 259 of file Grid_inlines.hh.
References add_congruence_no_check(), marked_empty(), space_dim, Parma_Polyhedra_Library::Congruence::space_dimension(), and throw_dimension_incompatible().
Referenced by Parma_Polyhedra_Library::Affine_Space::add_congruence(), Parma_Polyhedra_Library::Pointset_Powerset< PSET >::approximate_partition_aux(), refine_with_congruence(), and simplify_using_context_assign().
|
private |
Adds the congruence cg
to *this
.
cg
and *this
are dimension-incompatible, the grid generator system is not minimized or *this
is empty, then the behavior is undefined. Definition at line 678 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Congruence::is_inconsistent(), and Parma_Polyhedra_Library::Congruence::space_dimension().
Referenced by add_congruence(), and difference_assign().
|
inline |
Adds a copy of each congruence in cgs
to *this
.
cgs | Contains the congruences that will be added to the system of congruences of *this . |
std::invalid_argument | Thrown if *this and cgs are dimension-incompatible. |
Definition at line 271 of file Grid_inlines.hh.
References add_recycled_congruences(), marked_empty(), space_dim, Parma_Polyhedra_Library::Congruence_System::space_dimension(), and throw_dimension_incompatible().
Referenced by Parma_Polyhedra_Library::Affine_Space::add_congruences(), refine_with_congruences(), and simplify_using_context_assign().
|
inline |
Adds to *this
a congruence equivalent to constraint c
.
c | The constraint to be added. |
std::invalid_argument | Thrown if *this and c are dimension-incompatible or if constraint c is not optimally supported by the grid domain. |
Definition at line 305 of file Grid_inlines.hh.
References add_constraint_no_check(), marked_empty(), space_dim, Parma_Polyhedra_Library::Constraint::space_dimension(), and throw_dimension_incompatible().
Referenced by Parma_Polyhedra_Library::Affine_Space::add_constraint().
|
private |
Uses the constraint c
to refine *this
.
c | The constraint to be added. |
std::invalid_argument | Thrown if c is a non-trivial inequality constraint. |
c
and *this
are dimension-incompatible, the behavior is undefined. Definition at line 706 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Constraint::is_equality(), Parma_Polyhedra_Library::Constraint::is_inconsistent(), Parma_Polyhedra_Library::Constraint::is_inequality(), Parma_Polyhedra_Library::Constraint::is_tautological(), and Parma_Polyhedra_Library::Constraint::space_dimension().
Referenced by add_constraint().
void Parma_Polyhedra_Library::Grid::add_constraints | ( | const Constraint_System & | cs | ) |
Adds to *this
congruences equivalent to the constraints in cs
.
cs | The constraints to be added. |
std::invalid_argument | Thrown if *this and cs are dimension-incompatible or if cs contains a constraint which is not optimally supported by the grid domain. |
Definition at line 1220 of file Grid_public.cc.
References Parma_Polyhedra_Library::Constraint_System::begin(), Parma_Polyhedra_Library::Constraint_System::end(), and Parma_Polyhedra_Library::Constraint_System::space_dimension().
Referenced by add_recycled_constraints().
void Parma_Polyhedra_Library::Grid::add_grid_generator | ( | const Grid_Generator & | g | ) |
Adds a copy of grid generator g
to the system of generators of *this
.
std::invalid_argument | Thrown if *this and generator g are dimension-incompatible, or if *this is an empty grid and g is not a point. |
Definition at line 1239 of file Grid_public.cc.
References Parma_Polyhedra_Library::Grid_Generator::is_line_or_parameter(), Parma_Polyhedra_Library::Grid_Generator::is_parameter(), Parma_Polyhedra_Library::Grid_Generator::is_parameter_or_point(), and Parma_Polyhedra_Library::Grid_Generator::space_dimension().
void Parma_Polyhedra_Library::Grid::add_grid_generators | ( | const Grid_Generator_System & | gs | ) |
Adds a copy of the generators in gs
to the system of generators of *this
.
gs | Contains the generators that will be added to the system of generators of *this . |
std::invalid_argument | Thrown if *this and gs are dimension-incompatible, or if *this is empty and the system of generators gs is not empty, but has no points. |
Definition at line 1396 of file Grid_public.cc.
void Parma_Polyhedra_Library::Grid::add_recycled_congruences | ( | Congruence_System & | cgs | ) |
Adds the congruences in cgs
to *this.
cgs | The congruence system to be added to *this . The congruences in cgs may be recycled. |
std::invalid_argument | Thrown if *this and cgs are dimension-incompatible. |
cgs
upon successful or exceptional return is that it can be safely destroyed. Definition at line 1287 of file Grid_public.cc.
References Parma_Polyhedra_Library::Congruence_System::begin(), Parma_Polyhedra_Library::Congruence_System::end(), Parma_Polyhedra_Library::Congruence_System::has_no_rows(), and Parma_Polyhedra_Library::Congruence_System::space_dimension().
Referenced by add_congruences(), congruence_widening_assign(), contains_integer_point(), limited_congruence_extrapolation_assign(), limited_extrapolation_assign(), limited_generator_extrapolation_assign(), and simplify_using_context_assign().
|
inline |
Adds to *this
congruences equivalent to the constraints in cs
.
cs | The constraints to be added. They may be recycled. |
std::invalid_argument | Thrown if *this and cs are dimension-incompatible or if cs contains a constraint which is not optimally supported by the grid domain. |
cs
upon successful or exceptional return is that it can be safely destroyed. Definition at line 316 of file Grid_inlines.hh.
References add_constraints().
Referenced by Parma_Polyhedra_Library::Affine_Space::add_recycled_constraints().
void Parma_Polyhedra_Library::Grid::add_recycled_grid_generators | ( | Grid_Generator_System & | gs | ) |
Adds the generators in gs
to the system of generators of this
.
gs | The generator system to be added to *this . The generators in gs may be recycled. |
std::invalid_argument | Thrown if *this and gs are dimension-incompatible. |
gs
upon successful or exceptional return is that it can be safely destroyed. Definition at line 1332 of file Grid_public.cc.
References Parma_Polyhedra_Library::Grid_Generator_System::has_no_rows(), Parma_Polyhedra_Library::Grid_Generator_System::has_points(), Parma_Polyhedra_Library::Grid_Generator_System::set_space_dimension(), and Parma_Polyhedra_Library::Grid_Generator_System::space_dimension().
Referenced by generator_widening_assign().
|
private |
Adds new space dimensions to the given systems.
cgs | A congruence system, to which columns are added; |
gs | A generator system, to which rows and columns are added; |
dims | The number of space dimensions to add. |
This method is invoked only by add_space_dimensions_and_embed()
.
Definition at line 34 of file Grid_chdims.cc.
References Parma_Polyhedra_Library::Grid_Generator_System::add_universe_rows_and_columns(), CON_VIRTUAL, congruences_are_minimized(), dim_kinds, generators_are_minimized(), Parma_Polyhedra_Library::Congruence_System::set_space_dimension(), Parma_Polyhedra_Library::Congruence_System::space_dimension(), Parma_Polyhedra_Library::Grid_Generator_System::space_dimension(), and space_dimension().
|
private |
Adds new space dimensions to the given systems.
gs | A generator system, to which columns are added; |
cgs | A congruence system, to which rows and columns are added; |
dims | The number of space dimensions to add. |
This method is invoked only by add_space_dimensions_and_project()
.
Definition at line 52 of file Grid_chdims.cc.
References Parma_Polyhedra_Library::Congruence_System::add_unit_rows_and_space_dimensions(), Parma_Polyhedra_Library::Grid_Generator_System::set_space_dimension(), Parma_Polyhedra_Library::Congruence_System::space_dimension(), and Parma_Polyhedra_Library::Grid_Generator_System::space_dimension().
void Parma_Polyhedra_Library::Grid::add_space_dimensions_and_embed | ( | dimension_type | m | ) |
Adds m
new space dimensions and embeds the old grid in the new vector space.
m | The number of dimensions to add. |
std::length_error | Thrown if adding m new space dimensions would cause the vector space to exceed dimension max_space_dimension() . |
The new space dimensions will be those having the highest indexes in the new grid, which is characterized by a system of congruences in which the variables which are the new dimensions can have any value. For instance, when starting from the grid and adding a third space dimension, the result will be the grid
Definition at line 77 of file Grid_chdims.cc.
References Parma_Polyhedra_Library::check_space_dimension_overflow(), Parma_Polyhedra_Library::max_space_dimension(), and Parma_Polyhedra_Library::UNIVERSE.
Referenced by simplify_using_context_assign().
void Parma_Polyhedra_Library::Grid::add_space_dimensions_and_project | ( | dimension_type | m | ) |
Adds m
new space dimensions to the grid and does not embed it in the new vector space.
m | The number of space dimensions to add. |
std::length_error | Thrown if adding m new space dimensions would cause the vector space to exceed dimension max_space_dimension() . |
The new space dimensions will be those having the highest indexes in the new grid, which is characterized by a system of congruences in which the variables running through the new dimensions are all constrained to be equal to 0. For instance, when starting from the grid and adding a third space dimension, the result will be the grid
Definition at line 154 of file Grid_chdims.cc.
References Parma_Polyhedra_Library::check_space_dimension_overflow(), Parma_Polyhedra_Library::max_space_dimension(), and Parma_Polyhedra_Library::UNIVERSE.
PPL::dimension_type Parma_Polyhedra_Library::Grid::affine_dimension | ( | ) | const |
Returns , if
*this
is empty; otherwise, returns the affine dimension of *this
.
Definition at line 273 of file Grid_public.cc.
void Parma_Polyhedra_Library::Grid::affine_image | ( | Variable | var, |
const Linear_Expression & | expr, | ||
Coefficient_traits::const_reference | denominator = Coefficient_one() |
||
) |
Assigns to *this
the affine image of this
under the function mapping variable var
to the affine expression specified by expr
and denominator
.
var | The variable to which the affine expression is assigned; |
expr | The numerator of the affine expression; |
denominator | The denominator of the affine expression (optional argument with default value 1). |
std::invalid_argument | Thrown if denominator is zero or if expr and *this are dimension-incompatible or if var is not a space dimension of *this . |
When considering the generators of a grid, the affine transformation
is assigned to var
where expr
is (
is the inhomogeneous term).
If congruences are up-to-date, it uses the specialized function affine_preimage() (for the system of congruences) and inverse transformation to reach the same result. To obtain the inverse transformation we use the following observation.
Observation:
var
in this transformation (i.e.,
Then, if the transformation is invertible, all the entities that were up-to-date remain up-to-date. Otherwise only generators remain up-to-date.
Definition at line 1887 of file Grid_public.cc.
References Parma_Polyhedra_Library::Linear_Expression::coefficient(), Parma_Polyhedra_Library::inverse(), Parma_Polyhedra_Library::Linear_Expression::set_coefficient(), Parma_Polyhedra_Library::Variable::space_dimension(), and Parma_Polyhedra_Library::Linear_Expression::space_dimension().
Referenced by fold_space_dimensions().
void Parma_Polyhedra_Library::Grid::affine_preimage | ( | Variable | var, |
const Linear_Expression & | expr, | ||
Coefficient_traits::const_reference | denominator = Coefficient_one() |
||
) |
Assigns to *this
the affine preimage of *this
under the function mapping variable var
to the affine expression specified by expr
and denominator
.
var | The variable to which the affine expression is substituted; |
expr | The numerator of the affine expression; |
denominator | The denominator of the affine expression (optional argument with default value 1). |
std::invalid_argument | Thrown if denominator is zero or if expr and *this are dimension-incompatible or if var is not a space dimension of *this . |
When considering congruences of a grid, the affine transformation
is assigned to var
where expr
is (
is the inhomogeneous term).
If generators are up-to-date, then the specialized function affine_image() is used (for the system of generators) and inverse transformation to reach the same result. To obtain the inverse transformation, we use the following observation.
Observation:
var
in this transformation (i.e.
Then, if the transformation is invertible, all the entities that were up-to-date remain up-to-date. Otherwise only congruences remain up-to-date.
Definition at line 1979 of file Grid_public.cc.
References Parma_Polyhedra_Library::Linear_Expression::coefficient(), Parma_Polyhedra_Library::inverse(), Parma_Polyhedra_Library::Linear_Expression::set_coefficient(), Parma_Polyhedra_Library::Variable::space_dimension(), and Parma_Polyhedra_Library::Linear_Expression::space_dimension().
void Parma_Polyhedra_Library::Grid::ascii_dump | ( | ) | const |
Writes to std::cerr
an ASCII representation of *this
.
void Parma_Polyhedra_Library::Grid::ascii_dump | ( | std::ostream & | s | ) | const |
Writes to s
an ASCII representation of *this
.
Definition at line 2798 of file Grid_public.cc.
bool Parma_Polyhedra_Library::Grid::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.
Definition at line 2830 of file Grid_public.cc.
void Parma_Polyhedra_Library::Grid::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 .
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). |
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 . |
Definition at line 2550 of file Grid_public.cc.
References Parma_Polyhedra_Library::LESS_OR_EQUAL, Parma_Polyhedra_Library::Variable::space_dimension(), and Parma_Polyhedra_Library::Linear_Expression::space_dimension().
void Parma_Polyhedra_Library::Grid::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 .
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). |
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 . |
Definition at line 2596 of file Grid_public.cc.
References Parma_Polyhedra_Library::LESS_OR_EQUAL, Parma_Polyhedra_Library::Variable::space_dimension(), and Parma_Polyhedra_Library::Linear_Expression::space_dimension().
|
private |
Checks if and how expr
is bounded in *this
.
Returns true
if and only if from_above
is true
and expr
is bounded from above in *this
, or from_above
is false
and expr
is bounded from below in *this
.
expr | The linear expression to test; |
method_call | The call description of the public parent method, for example "bounded_from_above(e)". Passed to throw_dimension_incompatible, as the first argument. |
std::invalid_argument | Thrown if expr and *this are dimension-incompatible. |
Definition at line 289 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Linear_Expression::space_dimension().
Referenced by bounds_from_above(), and bounds_from_below().
|
inline |
Returns true
if and only if expr
is bounded in *this
.
This method is the same as bounds_from_below.
std::invalid_argument | Thrown if expr and *this are dimension-incompatible. |
Definition at line 322 of file Grid_inlines.hh.
References bounds().
Referenced by Parma_Polyhedra_Library::Affine_Space::bounds_from_above().
|
inline |
Returns true
if and only if expr
is bounded in *this
.
This method is the same as bounds_from_above.
std::invalid_argument | Thrown if expr and *this are dimension-incompatible. |
Definition at line 327 of file Grid_inlines.hh.
References bounds().
Referenced by Parma_Polyhedra_Library::Affine_Space::bounds_from_below().
|
private |
Checks if and how expr
is bounded in *this
.
Returns true
if and only if from_above
is true
and expr
is bounded from above in *this
, or from_above
is false
and expr
is bounded from below in *this
.
expr | The linear expression to test; |
Definition at line 310 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Scalar_Products::homogeneous_sign(), Parma_Polyhedra_Library::Grid_Generator::is_line_or_parameter(), and Parma_Polyhedra_Library::Linear_Expression::space_dimension().
Referenced by wrap_assign().
|
inlinestatic |
Returns true indicating that this domain has methods that can recycle congruences.
Definition at line 300 of file Grid_inlines.hh.
Referenced by Parma_Polyhedra_Library::Affine_Space::can_recycle_congruence_systems().
|
inlinestatic |
Returns true indicating that this domain has methods that can recycle constraints.
Definition at line 295 of file Grid_inlines.hh.
Referenced by Parma_Polyhedra_Library::Affine_Space::can_recycle_constraint_systems().
|
inlineprivate |
Sets status
to express that congruences are no longer minimized.
Definition at line 87 of file Grid_inlines.hh.
References Parma_Polyhedra_Library::Grid::Status::reset_c_minimized(), and status.
Referenced by clear_congruences_up_to_date(), intersection_assign(), and map_space_dimensions().
|
inlineprivate |
Sets status
to express that congruences are out of date.
Definition at line 97 of file Grid_inlines.hh.
References clear_congruences_minimized(), Parma_Polyhedra_Library::Grid::Status::reset_c_up_to_date(), and status.
Referenced by time_elapse_assign(), and upper_bound_assign().
|
inlineprivate |
Clears the status
flag indicating that the grid is empty.
Definition at line 82 of file Grid_inlines.hh.
References Parma_Polyhedra_Library::Grid::Status::reset_empty(), and status.
|
inlineprivate |
Sets status
to express that generators are no longer minimized.
Definition at line 92 of file Grid_inlines.hh.
References Parma_Polyhedra_Library::Grid::Status::reset_g_minimized(), and status.
Referenced by clear_generators_up_to_date(), map_space_dimensions(), time_elapse_assign(), and upper_bound_assign().
|
inlineprivate |
Sets status
to express that generators are out of date.
Definition at line 104 of file Grid_inlines.hh.
References clear_generators_minimized(), Parma_Polyhedra_Library::Grid::Status::reset_g_up_to_date(), and status.
Referenced by intersection_assign(), and OK().
void Parma_Polyhedra_Library::Grid::concatenate_assign | ( | const Grid & | y | ) |
Assigns to *this
the concatenation of *this
and y
, taken in this order.
std::length_error | Thrown if the concatenation would cause the vector space to exceed dimension max_space_dimension() . |
Definition at line 225 of file Grid_chdims.cc.
References Parma_Polyhedra_Library::check_space_dimension_overflow(), congruences(), marked_empty(), Parma_Polyhedra_Library::max_space_dimension(), space_dim, and space_dimension().
void Parma_Polyhedra_Library::Grid::congruence_widening_assign | ( | const Grid & | y, |
unsigned * | tp = NULL |
||
) |
Assigns to *this
the result of computing the Grid widening between *this
and y
using congruence systems.
y | A grid that must be contained in *this ; |
tp | An optional pointer to an unsigned variable storing the number of available tokens (to be used when applying the widening with tokens delay technique). |
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
Definition at line 77 of file Grid_widenings.cc.
References add_recycled_congruences(), con_sys, congruences_are_minimized(), congruences_are_up_to_date(), contains(), dim_kinds, m_swap(), marked_empty(), Parma_Polyhedra_Library::Congruence_System::num_equalities(), Parma_Polyhedra_Library::Congruence_System::num_rows(), OK(), select_wider_congruences(), set_congruences_minimized(), set_empty(), space_dim, and update_congruences().
Referenced by limited_congruence_extrapolation_assign(), and widening_assign().
const PPL::Congruence_System & Parma_Polyhedra_Library::Grid::congruences | ( | ) | const |
Returns the system of congruences.
Definition at line 300 of file Grid_public.cc.
Referenced by Parma_Polyhedra_Library::Pointset_Powerset< PSET >::approximate_partition(), Parma_Polyhedra_Library::Pointset_Powerset< PSET >::approximate_partition_aux(), concatenate_assign(), constraints(), and difference_assign().
|
inlineprivate |
Returns true
if the system of congruences is minimized.
Definition at line 50 of file Grid_inlines.hh.
References status, and Parma_Polyhedra_Library::Grid::Status::test_c_minimized().
Referenced by add_space_dimensions(), congruence_widening_assign(), Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate(), is_included_in(), quick_equivalence_test(), select_wider_congruences(), and simplify_using_context_assign().
|
inlineprivate |
Returns true
if the system of congruences is up-to-date.
Definition at line 40 of file Grid_inlines.hh.
References status, and Parma_Polyhedra_Library::Grid::Status::test_c_up_to_date().
Referenced by congruence_widening_assign(), Grid(), Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate(), intersection_assign(), is_included_in(), map_space_dimensions(), operator=(), simplify_using_context_assign(), and widening_assign().
bool Parma_Polyhedra_Library::Grid::constrains | ( | Variable | var | ) | const |
Returns true
if and only if var
is constrained in *this
.
std::invalid_argument | Thrown if var is not a space dimension of *this . |
Definition at line 886 of file Grid_public.cc.
References Parma_Polyhedra_Library::Expression_Hide_Last< T >::all_zeroes(), Parma_Polyhedra_Library::Grid_Generator::coefficient(), Parma_Polyhedra_Library::Grid_Generator::expression(), Parma_Polyhedra_Library::Grid_Generator::is_line(), Parma_Polyhedra_Library::Boundary_NS::sgn(), and Parma_Polyhedra_Library::Variable::space_dimension().
|
inline |
Returns a system of equality constraints satisfied by *this
with the same affine dimension as *this
.
Definition at line 239 of file Grid_inlines.hh.
References congruences().
Referenced by Parma_Polyhedra_Library::C_Polyhedron::C_Polyhedron(), Parma_Polyhedra_Library::Affine_Space::constraints(), and Parma_Polyhedra_Library::NNC_Polyhedron::NNC_Polyhedron().
|
private |
Builds a grid universe or empty grid.
num_dimensions | The number of dimensions of the vector space enclosing the grid; |
kind | specifies whether the universe or the empty grid has to be built. |
Definition at line 52 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Coefficient_one(), con_sys, CON_VIRTUAL, dim_kinds, Parma_Polyhedra_Library::EMPTY, gen_sys, Parma_Polyhedra_Library::Grid_Generator_System::insert(), Parma_Polyhedra_Library::Congruence_System::OK(), OK(), PROPER_CONGRUENCE, Parma_Polyhedra_Library::Congruence_System::rows, set_congruences_minimized(), Parma_Polyhedra_Library::Grid::Status::set_empty(), set_generators_minimized(), Parma_Polyhedra_Library::Congruence_System::set_space_dimension(), Parma_Polyhedra_Library::Grid_Generator_System::set_space_dimension(), set_zero_dim_univ(), space_dim, status, swap(), Parma_Polyhedra_Library::Congruence::zero_dim_false(), and Parma_Polyhedra_Library::Congruence::zero_dim_integrality().
Referenced by Grid().
|
private |
Builds a grid from a system of congruences.
The grid inherits the space dimension of the congruence system.
cgs | The system of congruences defining the grid. Its data-structures may be recycled to build the grid. |
Definition at line 103 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::max_space_dimension(), Parma_Polyhedra_Library::Congruence_System::num_rows(), Parma_Polyhedra_Library::Congruence_System::space_dimension(), and Parma_Polyhedra_Library::Congruence::zero_dim_false().
|
private |
Builds a grid from a system of grid generators.
The grid inherits the space dimension of the generator system.
ggs | The system of grid generators defining the grid. Its data-structures may be recycled to build the grid. |
Definition at line 141 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Grid_Generator_System::has_no_rows(), Parma_Polyhedra_Library::Grid_Generator_System::has_points(), Parma_Polyhedra_Library::max_space_dimension(), Parma_Polyhedra_Library::Grid_Generator_System::space_dimension(), and Parma_Polyhedra_Library::Congruence::zero_dim_false().
bool Parma_Polyhedra_Library::Grid::contains | ( | const Grid & | y | ) | const |
Returns true
if and only if *this
contains y
.
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
Definition at line 2763 of file Grid_public.cc.
References is_empty(), is_included_in(), marked_empty(), quick_equivalence_test(), space_dim, and TVB_TRUE.
Referenced by Parma_Polyhedra_Library::Pointset_Powerset< PSET >::check_containment(), congruence_widening_assign(), difference_assign(), generator_widening_assign(), and strictly_contains().
bool Parma_Polyhedra_Library::Grid::contains_integer_point | ( | ) | const |
Returns true
if and only if *this
contains at least one integer point.
Definition at line 861 of file Grid_public.cc.
References add_recycled_congruences(), Parma_Polyhedra_Library::Congruence_System::insert(), and is_empty().
|
staticprivate |
Converts generator system dest
to be equivalent to congruence system source
.
Definition at line 337 of file Grid_conversion.cc.
References Parma_Polyhedra_Library::Grid_Generator_System::clear(), Parma_Polyhedra_Library::Coefficient_one(), Parma_Polyhedra_Library::Coefficient_zero(), CON_VIRTUAL, dim_kinds, EQUALITY, Parma_Polyhedra_Library::Linear_Expression::exact_div_assign(), Parma_Polyhedra_Library::exact_div_assign(), Parma_Polyhedra_Library::Grid_Generator::expr, Parma_Polyhedra_Library::Grid_Generator_System::first_pending_row(), Parma_Polyhedra_Library::gcd_assign(), GEN_VIRTUAL, Parma_Polyhedra_Library::Linear_Expression::get(), Parma_Polyhedra_Library::Grid_Generator_System::insert_verbatim(), Parma_Polyhedra_Library::lcm_assign(), LINE, lower_triangular(), multiply_grid(), Parma_Polyhedra_Library::Grid_Generator_System::num_rows(), PARAMETER, PPL_DIRTY_TEMP_COEFFICIENT, PROPER_CONGRUENCE, Parma_Polyhedra_Library::Grid_Generator_System::representation(), Parma_Polyhedra_Library::Linear_Expression::set(), Parma_Polyhedra_Library::Grid_Generator_System::set_space_dimension(), Parma_Polyhedra_Library::Grid_Generator::set_topology(), Parma_Polyhedra_Library::Congruence_System::space_dimension(), Parma_Polyhedra_Library::sub_mul_assign(), Parma_Polyhedra_Library::Grid_Generator_System::sys, Parma_Polyhedra_Library::Grid_Generator_System::topology(), and upper_triangular().
|
staticprivate |
Converts congruence system dest
to be equivalent to generator system source
.
Definition at line 160 of file Grid_conversion.cc.
References Parma_Polyhedra_Library::Congruence_System::clear(), Parma_Polyhedra_Library::Coefficient_one(), Parma_Polyhedra_Library::Coefficient_zero(), CON_VIRTUAL, dim_kinds, Parma_Polyhedra_Library::Linear_Expression::exact_div_assign(), Parma_Polyhedra_Library::exact_div_assign(), Parma_Polyhedra_Library::Congruence::expr, Parma_Polyhedra_Library::Congruence::expression(), Parma_Polyhedra_Library::gcd_assign(), GEN_VIRTUAL, Parma_Polyhedra_Library::Expression_Adapter< T >::get(), Parma_Polyhedra_Library::Linear_Expression::get(), Parma_Polyhedra_Library::Congruence_System::insert_verbatim(), Parma_Polyhedra_Library::Congruence::is_proper_congruence(), Parma_Polyhedra_Library::lcm_assign(), Parma_Polyhedra_Library::Boundary_NS::le(), LINE, lower_triangular(), multiply_grid(), Parma_Polyhedra_Library::Grid_Generator_System::num_rows(), Parma_Polyhedra_Library::Congruence_System::num_rows(), Parma_Polyhedra_Library::Congruence_System::OK(), OK(), PARAMETER, PPL_DIRTY_TEMP_COEFFICIENT, Parma_Polyhedra_Library::Congruence_System::rows, Parma_Polyhedra_Library::Linear_Expression::set(), Parma_Polyhedra_Library::Congruence::set_modulus(), Parma_Polyhedra_Library::Congruence_System::set_space_dimension(), Parma_Polyhedra_Library::Linear_Expression::set_space_dimension(), Parma_Polyhedra_Library::Congruence_System::space_dimension(), Parma_Polyhedra_Library::Grid_Generator_System::space_dimension(), Parma_Polyhedra_Library::sub_mul_assign(), and upper_triangular().
void Parma_Polyhedra_Library::Grid::difference_assign | ( | const Grid & | y | ) |
Assigns to *this
the grid-difference of *this
and y
.
The grid difference between grids x and y is the smallest grid containing all the points from x and y that are only in x.
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
Definition at line 1604 of file Grid_public.cc.
References add_congruence_no_check(), Parma_Polyhedra_Library::Congruence_System::begin(), congruences(), contains(), Parma_Polyhedra_Library::EMPTY, Parma_Polyhedra_Library::Congruence_System::end(), Parma_Polyhedra_Library::Congruence::expression(), Parma_Polyhedra_Library::Poly_Con_Relation::implies(), Parma_Polyhedra_Library::Poly_Con_Relation::is_included(), Parma_Polyhedra_Library::Congruence::is_proper_congruence(), marked_empty(), Parma_Polyhedra_Library::Congruence::modulus(), relation_with(), set_empty(), space_dim, and upper_bound_assign().
Referenced by upper_bound_assign_if_exact().
void Parma_Polyhedra_Library::Grid::drop_some_non_integer_points | ( | Complexity_Class | complexity = ANY_COMPLEXITY | ) |
Possibly tightens *this
by dropping all points with non-integer coordinates.
complexity | This argument is ignored as the algorithm used has polynomial complexity. |
Definition at line 3112 of file Grid_public.cc.
void Parma_Polyhedra_Library::Grid::drop_some_non_integer_points | ( | const Variables_Set & | vars, |
Complexity_Class | complexity = ANY_COMPLEXITY |
||
) |
Possibly tightens *this
by dropping all points with non-integer coordinates for the space dimensions corresponding to vars
.
vars | Points with non-integer coordinates for these variables/space-dimensions can be discarded. |
complexity | This argument is ignored as the algorithm used has polynomial complexity. |
Definition at line 3129 of file Grid_public.cc.
References Parma_Polyhedra_Library::Variables_Set::space_dimension().
void Parma_Polyhedra_Library::Grid::expand_space_dimension | ( | Variable | var, |
dimension_type | m | ||
) |
Creates m
copies of the space dimension corresponding to var
.
var | The variable corresponding to the space dimension to be replicated; |
m | The number of replicas to be created. |
std::invalid_argument | Thrown if var does not correspond to a dimension of the vector space. |
std::length_error | Thrown if adding m new space dimensions would cause the vector space to exceed dimension max_space_dimension() . |
If *this
has space dimension , with
, and
var
has space dimension , then the
-th space dimension is expanded to
m
new space dimensions ,
,
,
.
Definition at line 406 of file Grid_chdims.cc.
References Parma_Polyhedra_Library::add_mul_assign(), Parma_Polyhedra_Library::Congruence_System::begin(), Parma_Polyhedra_Library::check_space_dimension_overflow(), Parma_Polyhedra_Library::Congruence::coefficient(), Parma_Polyhedra_Library::Coefficient_zero(), Parma_Polyhedra_Library::Congruence_System::end(), Parma_Polyhedra_Library::Congruence::expr, Parma_Polyhedra_Library::Congruence_System::insert_verbatim(), Parma_Polyhedra_Library::max_space_dimension(), Parma_Polyhedra_Library::Linear_Expression::set_coefficient(), and Parma_Polyhedra_Library::Variable::space_dimension().
PPL::memory_size_type Parma_Polyhedra_Library::Grid::external_memory_in_bytes | ( | ) | const |
Returns the size in bytes of the memory managed by *this
.
Definition at line 2916 of file Grid_public.cc.
Referenced by total_memory_in_bytes().
void Parma_Polyhedra_Library::Grid::fold_space_dimensions | ( | const Variables_Set & | vars, |
Variable | dest | ||
) |
Folds the space dimensions in vars
into dest
.
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. |
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.
Definition at line 458 of file Grid_chdims.cc.
References affine_image(), Parma_Polyhedra_Library::Variable::id(), Parma_Polyhedra_Library::Variables_Set::space_dimension(), Parma_Polyhedra_Library::Variable::space_dimension(), and Parma_Polyhedra_Library::upper_bound_assign().
bool Parma_Polyhedra_Library::Grid::frequency | ( | const Linear_Expression & | expr, |
Coefficient & | freq_n, | ||
Coefficient & | freq_d, | ||
Coefficient & | val_n, | ||
Coefficient & | val_d | ||
) | const |
Returns true
if and only if *this
is not empty and frequency for *this
with respect to expr
is defined, in which case the frequency and the value for expr
that is closest to zero are computed.
expr | The linear expression for which the frequency is needed; |
freq_n | The numerator of the maximum frequency of expr ; |
freq_d | The denominator of the maximum frequency of expr ; |
val_n | The numerator of them value of expr at a point in the grid that is closest to zero; |
val_d | The denominator of a value of expr at a point in the grid that is closest to zero; |
std::invalid_argument | Thrown if expr and *this are dimension-incompatible. |
If *this
is empty or frequency is undefined with respect to expr
, then false
is returned and freq_n
, freq_d
, val_n
and val_d
are left untouched.
Definition at line 2700 of file Grid_public.cc.
References Parma_Polyhedra_Library::Linear_Expression::space_dimension().
Referenced by Parma_Polyhedra_Library::Affine_Space::frequency().
|
private |
Returns true
if and only if *this
is not empty and frequency for *this
with respect to expr
is defined, in which case the frequency and the value for expr
that is closest to zero are computed.
expr | The linear expression for which the frequency is needed; |
freq_n | The numerator of the maximum frequency of expr ; |
freq_d | The denominator of the maximum frequency of expr ; |
val_n | The numerator of a value of expr at a point in the grid that is closest to zero; |
val_d | The denominator of a value of expr at a point in the grid that is closest to zero; |
If *this
is empty or frequency is undefined with respect to expr
, then false
is returned and freq_n
, freq_d
, val_n
and val_d
are left untouched.
expr
and *this
are dimension-incompatible, the grid generator system is not minimized or *this
is empty, then the behavior is undefined. Definition at line 332 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Grid_Generator::divisor(), Parma_Polyhedra_Library::exact_div_assign(), Parma_Polyhedra_Library::gcd_assign(), Parma_Polyhedra_Library::Scalar_Products::homogeneous_assign(), Parma_Polyhedra_Library::Linear_Expression::inhomogeneous_term(), Parma_Polyhedra_Library::Grid_Generator::is_line(), Parma_Polyhedra_Library::Grid_Generator::is_parameter(), Parma_Polyhedra_Library::Grid_Generator::is_point(), PPL_DIRTY_TEMP_COEFFICIENT, Parma_Polyhedra_Library::Boundary_NS::sgn(), and Parma_Polyhedra_Library::Linear_Expression::space_dimension().
Referenced by wrap_assign().
void Parma_Polyhedra_Library::Grid::generalized_affine_image | ( | Variable | var, |
Relation_Symbol | relsym, | ||
const Linear_Expression & | expr, | ||
Coefficient_traits::const_reference | denominator = Coefficient_one() , |
||
Coefficient_traits::const_reference | modulus = Coefficient_zero() |
||
) |
Assigns to *this
the image of *this
with respect to the generalized affine relation .
var | The left hand side variable of the generalized affine relation; |
relsym | The relation symbol where EQUAL is the symbol for a congruence relation; |
expr | The numerator of the right hand side affine expression; |
denominator | The denominator of the right hand side affine expression. Optional argument with an automatic value of one; |
modulus | The modulus of the congruence lhs %= rhs. A modulus of zero indicates lhs == rhs. Optional argument with an automatic value of zero. |
std::invalid_argument | Thrown if denominator is zero or if expr and *this are dimension-incompatible or if var is not a space dimension of this . |
Definition at line 2063 of file Grid_public.cc.
References Parma_Polyhedra_Library::EQUAL, Parma_Polyhedra_Library::NOT_EQUAL, Parma_Polyhedra_Library::Variable::space_dimension(), and Parma_Polyhedra_Library::Linear_Expression::space_dimension().
void Parma_Polyhedra_Library::Grid::generalized_affine_image | ( | const Linear_Expression & | lhs, |
Relation_Symbol | relsym, | ||
const Linear_Expression & | rhs, | ||
Coefficient_traits::const_reference | modulus = Coefficient_zero() |
||
) |
Assigns to *this
the image of *this
with respect to the generalized affine relation .
lhs | The left hand side affine expression. |
relsym | The relation symbol where EQUAL is the symbol for a congruence relation; |
rhs | The right hand side affine expression. |
modulus | The modulus of the congruence lhs %= rhs. A modulus of zero indicates lhs == rhs. Optional argument with an automatic value of zero. |
std::invalid_argument | Thrown if *this is dimension-incompatible with lhs or rhs . |
Definition at line 2269 of file Grid_public.cc.
References Parma_Polyhedra_Library::Linear_Expression::begin(), Parma_Polyhedra_Library::Linear_Expression::end(), Parma_Polyhedra_Library::EQUAL, Parma_Polyhedra_Library::Linear_Expression::have_a_common_variable(), Parma_Polyhedra_Library::Grid_Generator_System::insert(), Parma_Polyhedra_Library::Linear_Expression::last_nonzero(), Parma_Polyhedra_Library::Linear_Expression::lower_bound(), Parma_Polyhedra_Library::neg_assign(), Parma_Polyhedra_Library::NOT_EQUAL, PPL_DIRTY_TEMP_COEFFICIENT, Parma_Polyhedra_Library::Grid_Generator_System::set_space_dimension(), and Parma_Polyhedra_Library::Linear_Expression::space_dimension().
void Parma_Polyhedra_Library::Grid::generalized_affine_preimage | ( | Variable | var, |
Relation_Symbol | relsym, | ||
const Linear_Expression & | expr, | ||
Coefficient_traits::const_reference | denominator = Coefficient_one() , |
||
Coefficient_traits::const_reference | modulus = Coefficient_zero() |
||
) |
Assigns to *this
the preimage of *this
with respect to the generalized affine relation .
var | The left hand side variable of the generalized affine relation; |
relsym | The relation symbol where EQUAL is the symbol for a congruence relation; |
expr | The numerator of the right hand side affine expression; |
denominator | The denominator of the right hand side affine expression. Optional argument with an automatic value of one; |
modulus | The modulus of the congruence lhs %= rhs. A modulus of zero indicates lhs == rhs. Optional argument with an automatic value of zero. |
std::invalid_argument | Thrown if denominator is zero or if expr and *this are dimension-incompatible or if var is not a space dimension of this . |
Definition at line 2160 of file Grid_public.cc.
References Parma_Polyhedra_Library::Linear_Expression::coefficient(), Parma_Polyhedra_Library::EQUAL, Parma_Polyhedra_Library::neg_assign(), Parma_Polyhedra_Library::NOT_EQUAL, PPL_DIRTY_TEMP_COEFFICIENT, Parma_Polyhedra_Library::Variable::space_dimension(), and Parma_Polyhedra_Library::Linear_Expression::space_dimension().
void Parma_Polyhedra_Library::Grid::generalized_affine_preimage | ( | const Linear_Expression & | lhs, |
Relation_Symbol | relsym, | ||
const Linear_Expression & | rhs, | ||
Coefficient_traits::const_reference | modulus = Coefficient_zero() |
||
) |
Assigns to *this
the preimage of *this
with respect to the generalized affine relation .
lhs | The left hand side affine expression; |
relsym | The relation symbol where EQUAL is the symbol for a congruence relation; |
rhs | The right hand side affine expression; |
modulus | The modulus of the congruence lhs %= rhs. A modulus of zero indicates lhs == rhs. Optional argument with an automatic value of zero. |
std::invalid_argument | Thrown if *this is dimension-incompatible with lhs or rhs . |
Definition at line 2412 of file Grid_public.cc.
References Parma_Polyhedra_Library::Linear_Expression::begin(), Parma_Polyhedra_Library::Linear_Expression::end(), Parma_Polyhedra_Library::EQUAL, Parma_Polyhedra_Library::Linear_Expression::have_a_common_variable(), Parma_Polyhedra_Library::Grid_Generator_System::insert(), Parma_Polyhedra_Library::Linear_Expression::last_nonzero(), Parma_Polyhedra_Library::Linear_Expression::lower_bound(), Parma_Polyhedra_Library::neg_assign(), Parma_Polyhedra_Library::NOT_EQUAL, PPL_DIRTY_TEMP_COEFFICIENT, Parma_Polyhedra_Library::Grid_Generator_System::set_space_dimension(), and Parma_Polyhedra_Library::Linear_Expression::space_dimension().
void Parma_Polyhedra_Library::Grid::generator_widening_assign | ( | const Grid & | y, |
unsigned * | tp = NULL |
||
) |
Assigns to *this
the result of computing the Grid widening between *this
and y
using generator systems.
y | A grid that must be contained in *this ; |
tp | An optional pointer to an unsigned variable storing the number of available tokens (to be used when applying the widening with tokens delay technique). |
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
Definition at line 282 of file Grid_widenings.cc.
References add_recycled_grid_generators(), contains(), dim_kinds, Parma_Polyhedra_Library::EMPTY, gen_sys, generators_are_minimized(), generators_are_up_to_date(), Parma_Polyhedra_Library::Grid_Generator_System::has_no_rows(), m_swap(), marked_empty(), Parma_Polyhedra_Library::Grid_Generator_System::num_lines(), Parma_Polyhedra_Library::Grid_Generator_System::num_parameters(), Parma_Polyhedra_Library::Grid_Generator_System::num_rows(), OK(), select_wider_generators(), set_generators_minimized(), space_dim, and update_generators().
Referenced by limited_generator_extrapolation_assign(), and widening_assign().
|
inlineprivate |
Returns true
if the system of generators is minimized.
Definition at line 55 of file Grid_inlines.hh.
References status, and Parma_Polyhedra_Library::Grid::Status::test_g_minimized().
Referenced by add_space_dimensions(), generator_widening_assign(), Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate(), quick_equivalence_test(), select_wider_generators(), and simplify_using_context_assign().
|
inlineprivate |
Returns true
if the system of generators is up-to-date.
Definition at line 45 of file Grid_inlines.hh.
References status, and Parma_Polyhedra_Library::Grid::Status::test_g_up_to_date().
Referenced by Parma_Polyhedra_Library::Box< ITV >::Box(), generator_widening_assign(), Grid(), Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate(), limited_congruence_extrapolation_assign(), limited_extrapolation_assign(), limited_generator_extrapolation_assign(), map_space_dimensions(), operator=(), time_elapse_assign(), upper_bound_assign(), and widening_assign().
const PPL::Grid_Generator_System & Parma_Polyhedra_Library::Grid::grid_generators | ( | ) | const |
Returns the system of generators.
Definition at line 334 of file Grid_public.cc.
References set_empty().
Referenced by map_space_dimensions().
|
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()
.
Definition at line 234 of file Grid_inlines.hh.
References Parma_Polyhedra_Library::hash_code_from_dimension(), and space_dimension().
Referenced by Parma_Polyhedra_Library::Affine_Space::hash_code().
void Parma_Polyhedra_Library::Grid::intersection_assign | ( | const Grid & | y | ) |
Assigns to *this
the intersection of *this
and y
.
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
Definition at line 1485 of file Grid_public.cc.
References clear_congruences_minimized(), clear_generators_up_to_date(), con_sys, congruences_are_up_to_date(), Parma_Polyhedra_Library::Congruence_System::has_no_rows(), Parma_Polyhedra_Library::Congruence_System::insert(), marked_empty(), OK(), set_empty(), space_dim, and update_congruences().
Referenced by is_disjoint_from().
bool Parma_Polyhedra_Library::Grid::is_bounded | ( | ) | const |
Returns true
if and only if *this
is bounded.
Definition at line 810 of file Grid_public.cc.
References Parma_Polyhedra_Library::Grid_Generator::is_line_or_parameter().
bool Parma_Polyhedra_Library::Grid::is_discrete | ( | ) | const |
Returns true
if and only if *this
is discrete.
A grid is discrete if it can be defined by a generator system which contains only points and parameters. This includes the empty grid and any grid in dimension zero.
Definition at line 836 of file Grid_public.cc.
bool Parma_Polyhedra_Library::Grid::is_disjoint_from | ( | const Grid & | y | ) | const |
Returns true
if and only if *this
and y
are disjoint.
std::invalid_argument | Thrown if x and y are dimension-incompatible. |
Definition at line 2787 of file Grid_public.cc.
References intersection_assign(), is_empty(), and space_dim.
Referenced by Parma_Polyhedra_Library::Pointset_Powerset< PSET >::check_containment().
bool Parma_Polyhedra_Library::Grid::is_empty | ( | ) | const |
Returns true
if and only if *this
is an empty grid.
Definition at line 742 of file Grid_public.cc.
References con_sys, dim_kinds, set_congruences_minimized(), set_empty(), and simplify().
Referenced by Parma_Polyhedra_Library::Pointset_Powerset< PSET >::approximate_partition_aux(), Parma_Polyhedra_Library::Pointset_Powerset< PSET >::check_containment(), contains(), contains_integer_point(), is_disjoint_from(), operator<<(), operator==(), Parma_Polyhedra_Library::Pointset_Powerset< PSET >::Pointset_Powerset(), and simplify_using_context_assign().
|
private |
Returns true
if and only if *this
is included in y
.
Definition at line 247 of file Grid_nonpublic.cc.
References con_sys, congruences_are_minimized(), congruences_are_up_to_date(), marked_empty(), minimize(), Parma_Polyhedra_Library::Congruence_System::num_rows(), OK(), Parma_Polyhedra_Library::Congruence_System::satisfies_all_congruences(), space_dim, and update_congruences().
Referenced by contains(), operator==(), simplify_using_context_assign(), and upper_bound_assign_if_exact().
bool Parma_Polyhedra_Library::Grid::is_topologically_closed | ( | ) | const |
Returns true
if and only if *this
is a topologically closed subset of the vector space.
A grid is always topologically closed.
Definition at line 856 of file Grid_public.cc.
bool Parma_Polyhedra_Library::Grid::is_universe | ( | ) | const |
Returns true
if and only if *this
is a universe grid.
Definition at line 769 of file Grid_public.cc.
References Parma_Polyhedra_Library::Linear_Expression::set_space_dimension().
Referenced by operator<<().
void Parma_Polyhedra_Library::Grid::limited_congruence_extrapolation_assign | ( | const Grid & | y, |
const Congruence_System & | cgs, | ||
unsigned * | tp = NULL |
||
) |
Improves the result of the congruence variant of Grid widening computation by also enforcing those congruences in cgs
that are satisfied by all the points of *this
.
y | A grid that must be contained in *this ; |
cgs | The system of congruences used to improve the widened grid; |
tp | An optional pointer to an unsigned variable storing the number of available tokens (to be used when applying the widening with tokens delay technique). |
std::invalid_argument | Thrown if *this , y and cgs are dimension-incompatible. |
Definition at line 160 of file Grid_widenings.cc.
References add_recycled_congruences(), congruence_widening_assign(), generators_are_up_to_date(), Parma_Polyhedra_Library::Congruence_System::insert(), Parma_Polyhedra_Library::Poly_Con_Relation::is_included(), marked_empty(), Parma_Polyhedra_Library::Congruence_System::num_rows(), relation_with(), space_dim, Parma_Polyhedra_Library::Congruence_System::space_dimension(), update_generators(), and widening_assign().
void Parma_Polyhedra_Library::Grid::limited_extrapolation_assign | ( | const Grid & | y, |
const Congruence_System & | cgs, | ||
unsigned * | tp = NULL |
||
) |
Improves the result of the Grid widening computation by also enforcing those congruences in cgs
that are satisfied by all the points of *this
.
y | A grid that must be contained in *this ; |
cgs | The system of congruences used to improve the widened grid; |
tp | An optional pointer to an unsigned variable storing the number of available tokens (to be used when applying the widening with tokens delay technique). |
std::invalid_argument | Thrown if *this , y and cgs are dimension-incompatible. |
Definition at line 470 of file Grid_widenings.cc.
References add_recycled_congruences(), generators_are_up_to_date(), Parma_Polyhedra_Library::Congruence_System::insert(), Parma_Polyhedra_Library::Poly_Con_Relation::is_included(), marked_empty(), Parma_Polyhedra_Library::Congruence_System::num_rows(), relation_with(), space_dim, Parma_Polyhedra_Library::Congruence_System::space_dimension(), update_generators(), and widening_assign().
void Parma_Polyhedra_Library::Grid::limited_generator_extrapolation_assign | ( | const Grid & | y, |
const Congruence_System & | cgs, | ||
unsigned * | tp = NULL |
||
) |
Improves the result of the generator variant of the Grid widening computation by also enforcing those congruences in cgs
that are satisfied by all the points of *this
.
y | A grid that must be contained in *this ; |
cgs | The system of congruences used to improve the widened grid; |
tp | An optional pointer to an unsigned variable storing the number of available tokens (to be used when applying the widening with tokens delay technique). |
std::invalid_argument | Thrown if *this , y and cgs are dimension-incompatible. |
Definition at line 369 of file Grid_widenings.cc.
References add_recycled_congruences(), generator_widening_assign(), generators_are_up_to_date(), Parma_Polyhedra_Library::Congruence_System::insert(), Parma_Polyhedra_Library::Poly_Con_Relation::is_included(), marked_empty(), Parma_Polyhedra_Library::Congruence_System::num_rows(), relation_with(), space_dim, Parma_Polyhedra_Library::Congruence_System::space_dimension(), and update_generators().
|
staticprivate |
If sys
is lower triangular return true
, else return false
.
Definition at line 37 of file Grid_conversion.cc.
References Parma_Polyhedra_Library::Linear_Expression::all_zeroes(), CON_VIRTUAL, Parma_Polyhedra_Library::Congruence::expr, Parma_Polyhedra_Library::Linear_Expression::get(), Parma_Polyhedra_Library::Congruence_System::num_rows(), and Parma_Polyhedra_Library::Congruence_System::space_dimension().
Referenced by conversion().
|
inline |
Swaps *this
with grid y
. (*this
and y
can be dimension-incompatible.)
Definition at line 249 of file Grid_inlines.hh.
References con_sys, dim_kinds, gen_sys, space_dim, status, swap(), and Parma_Polyhedra_Library::swap().
Referenced by Parma_Polyhedra_Library::Affine_Space::Affine_Space(), congruence_widening_assign(), generator_widening_assign(), map_space_dimensions(), simplify_using_context_assign(), and swap().
void Parma_Polyhedra_Library::Grid::map_space_dimensions | ( | const Partial_Function & | pfunc | ) |
Remaps the dimensions of the vector space according to a partial function.
If pfunc
maps only some of the dimensions of *this
then the rest will be projected away.
If the highest dimension mapped to by pfunc
is higher than the highest dimension in *this
then the number of dimensions in this
will be increased to the highest dimension mapped to by pfunc
.
pfunc | The partial function specifying the destiny of each space dimension. |
The template type parameter Partial_Function must provide the following methods.
returns true
if and only if the represented partial function has an empty codomain (i.e., it is always undefined). The has_empty_codomain()
method will always be called before the methods below. However, if has_empty_codomain()
returns true
, none of the functions below will be called.
returns the maximum value that belongs to the codomain of the partial function. The max_in_codomain()
method is called at most once.
Let be the represented function and
be the value of
i
. If is defined in
, then
is assigned to
j
and true
is returned. If is undefined in
, then
false
is returned. This method is called at most times, where
is the dimension of the vector space enclosing the grid.
The result is undefined if pfunc
does not encode a partial function with the properties described in the specification of the mapping operator.
Definition at line 119 of file Grid_templates.hh.
References Parma_Polyhedra_Library::add_mul_assign(), Parma_Polyhedra_Library::Expression_Adapter< T >::begin(), Parma_Polyhedra_Library::Grid_Generator_System::begin(), clear_congruences_minimized(), clear_generators_minimized(), con_sys, congruences_are_up_to_date(), Parma_Polyhedra_Library::Grid_Generator::divisor(), Parma_Polyhedra_Library::EMPTY, Parma_Polyhedra_Library::Expression_Hide_Last< T >::end(), Parma_Polyhedra_Library::Grid_Generator_System::end(), Parma_Polyhedra_Library::Grid_Generator::expression(), gen_sys, generators_are_up_to_date(), grid_generators(), Parma_Polyhedra_Library::Partial_Function::has_empty_codomain(), Parma_Polyhedra_Library::Grid_Generator_System::has_no_rows(), Parma_Polyhedra_Library::Grid_Generator_System::insert(), Parma_Polyhedra_Library::Grid_Generator::is_point(), Parma_Polyhedra_Library::Grid_Generator::LINE, m_swap(), Parma_Polyhedra_Library::Partial_Function::maps(), marked_empty(), Parma_Polyhedra_Library::Partial_Function::max_in_codomain(), Parma_Polyhedra_Library::not_a_dimension(), OK(), Parma_Polyhedra_Library::Grid_Generator::PARAMETER, Parma_Polyhedra_Library::Congruence_System::permute_space_dimensions(), Parma_Polyhedra_Library::Grid_Generator_System::permute_space_dimensions(), Parma_Polyhedra_Library::Grid_Generator::POINT, set_empty(), Parma_Polyhedra_Library::Grid_Generator_System::set_sorted(), Parma_Polyhedra_Library::Linear_Expression::set_space_dimension(), set_zero_dim_univ(), space_dim, throw_invalid_argument(), Parma_Polyhedra_Library::Grid_Generator::type(), and update_generators().
|
inlineprivate |
Returns true
if the grid is known to be empty.
The return value false
does not necessarily implies that *this
is non-empty.
Definition at line 35 of file Grid_inlines.hh.
References status, and Parma_Polyhedra_Library::Grid::Status::test_empty().
Referenced by add_congruence(), add_congruences(), add_constraint(), Parma_Polyhedra_Library::Box< ITV >::Box(), concatenate_assign(), congruence_widening_assign(), contains(), difference_assign(), generator_widening_assign(), Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate(), intersection_assign(), is_included_in(), limited_congruence_extrapolation_assign(), limited_extrapolation_assign(), limited_generator_extrapolation_assign(), map_space_dimensions(), operator=(), operator==(), quick_equivalence_test(), select_wider_congruences(), select_wider_generators(), time_elapse_assign(), upper_bound_assign(), and upper_bound_assign_if_exact().
|
private |
Maximizes or minimizes expr
subject to *this
.
expr | The linear expression to be maximized or minimized subject to this ; |
method_call | The call description of the public parent method, for example "maximize(e)". Passed to throw_dimension_incompatible, as the first argument; |
ext_n | The numerator of the extremum value; |
ext_d | The denominator of the extremum value; |
included | true if and only if the extremum of expr in this can actually be reached (which is always the case); |
point | When maximization or minimization succeeds, will be assigned the point where expr reaches the extremum value. |
std::invalid_argument | Thrown if expr and *this are dimension-incompatible. |
If *this
is empty or expr
is not bounded in the appropriate direction, false
is returned and ext_n
, ext_d
, included
and point
are left untouched.
Definition at line 413 of file Grid_nonpublic.cc.
References dim_kinds, Parma_Polyhedra_Library::Grid_Generator::divisor(), Parma_Polyhedra_Library::exact_div_assign(), Parma_Polyhedra_Library::Grid_Generator::expression(), Parma_Polyhedra_Library::gcd_assign(), gen_sys, Parma_Polyhedra_Library::Scalar_Products::homogeneous_assign(), Parma_Polyhedra_Library::Linear_Expression::inhomogeneous_term(), Parma_Polyhedra_Library::Generator::point(), PPL_DIRTY_TEMP_COEFFICIENT, set_generators_minimized(), and simplify().
Referenced by maximize(), and minimize().
|
inlinestatic |
Returns the maximum space dimension all kinds of Grid can handle.
Definition at line 111 of file Grid_inlines.hh.
References Parma_Polyhedra_Library::Congruence_System::max_space_dimension(), and Parma_Polyhedra_Library::Grid_Generator_System::max_space_dimension().
Referenced by Grid(), Parma_Polyhedra_Library::max_space_dimension(), and Parma_Polyhedra_Library::Affine_Space::max_space_dimension().
|
inline |
Returns true
if and only if *this
is not empty and expr
is bounded from above in *this
, in which case the supremum value is computed.
expr | The linear expression to be maximized subject to *this ; |
sup_n | The numerator of the supremum value; |
sup_d | The denominator of the supremum value; |
maximum | true if the supremum value can be reached in this . Always true when this bounds expr . Present for interface compatibility with class Polyhedron, where closure points can result in a value of false. |
std::invalid_argument | Thrown if expr and *this are dimension-incompatible. |
If *this
is empty or expr
is not bounded by *this
, false
is returned and sup_n
, sup_d
and maximum
are left untouched.
Definition at line 332 of file Grid_inlines.hh.
References max_min().
Referenced by Parma_Polyhedra_Library::Box< ITV >::Box(), and Parma_Polyhedra_Library::Affine_Space::maximize().
|
inline |
Returns true
if and only if *this
is not empty and expr
is bounded from above in *this
, in which case the supremum value and a point where expr
reaches it are computed.
expr | The linear expression to be maximized subject to *this ; |
sup_n | The numerator of the supremum value; |
sup_d | The denominator of the supremum value; |
maximum | true if the supremum value can be reached in this . Always true when this bounds expr . Present for interface compatibility with class Polyhedron, where closure points can result in a value of false; |
point | When maximization succeeds, will be assigned a point where expr reaches its supremum value. |
std::invalid_argument | Thrown if expr and *this are dimension-incompatible. |
If *this
is empty or expr
is not bounded by *this
, false
is returned and sup_n
, sup_d
, maximum
and point
are left untouched.
Definition at line 338 of file Grid_inlines.hh.
References max_min().
|
inline |
Returns true
if and only if *this
is not empty and expr
is bounded from below in *this
, in which case the infimum value is computed.
expr | The linear expression to be minimized subject to *this ; |
inf_n | The numerator of the infimum value; |
inf_d | The denominator of the infimum value; |
minimum | true if the is the infimum value can be reached in this . Always true when this bounds expr . Present for interface compatibility with class Polyhedron, where closure points can result in a value of false. |
std::invalid_argument | Thrown if expr and *this are dimension-incompatible. |
If *this
is empty or expr
is not bounded from below, false
is returned and inf_n
, inf_d
and minimum
are left untouched.
Definition at line 345 of file Grid_inlines.hh.
References max_min().
Referenced by is_included_in(), Parma_Polyhedra_Library::Affine_Space::minimize(), and simplify_using_context_assign().
|
inline |
Returns true
if and only if *this
is not empty and expr
is bounded from below in *this
, in which case the infimum value and a point where expr
reaches it are computed.
expr | The linear expression to be minimized subject to *this ; |
inf_n | The numerator of the infimum value; |
inf_d | The denominator of the infimum value; |
minimum | true if the is the infimum value can be reached in this . Always true when this bounds expr . Present for interface compatibility with class Polyhedron, where closure points can result in a value of false; |
point | When minimization succeeds, will be assigned a point where expr reaches its infimum value. |
std::invalid_argument | Thrown if expr and *this are dimension-incompatible. |
If *this
is empty or expr
is not bounded from below, false
is returned and inf_n
, inf_d
, minimum
and point
are left untouched.
Definition at line 351 of file Grid_inlines.hh.
References max_min().
|
private |
Minimizes both the congruences and the generators.
false
if and only if *this
turns out to be an empty grid.Minimization is performed on each system only if the minimized Status field is clear.
Definition at line 536 of file Grid_nonpublic.cc.
References con_sys, dim_kinds, Parma_Polyhedra_Library::Implementation::BD_Shapes::empty, gen_sys, set_congruences_minimized(), set_generators_minimized(), and simplify().
const PPL::Congruence_System & Parma_Polyhedra_Library::Grid::minimized_congruences | ( | ) | const |
Returns the system of congruences in minimal form.
Definition at line 319 of file Grid_public.cc.
References con_sys, dim_kinds, set_congruences_minimized(), set_empty(), and simplify().
Referenced by Parma_Polyhedra_Library::Pointset_Powerset< PSET >::approximate_partition(), Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), Parma_Polyhedra_Library::Partially_Reduced_Product< D1, D2, R >::minimized_congruences(), minimized_constraints(), Parma_Polyhedra_Library::Octagonal_Shape< T >::Octagonal_Shape(), and operator<<().
|
inline |
Returns a minimal system of equality constraints satisfied by *this
with the same affine dimension as *this
.
Definition at line 244 of file Grid_inlines.hh.
References minimized_congruences().
Referenced by Parma_Polyhedra_Library::Affine_Space::minimized_constraints().
const PPL::Grid_Generator_System & Parma_Polyhedra_Library::Grid::minimized_grid_generators | ( | ) | const |
Returns the minimized system of generators.
Definition at line 356 of file Grid_public.cc.
References dim_kinds, gen_sys, set_empty(), set_generators_minimized(), and simplify().
|
staticprivate |
Multiply the elements of dest
by multiplier
.
Definition at line 132 of file Grid_conversion.cc.
References Parma_Polyhedra_Library::Congruence::is_equality(), Parma_Polyhedra_Library::Congruence::is_proper_congruence(), and Parma_Polyhedra_Library::Congruence::scale().
Referenced by conversion().
|
staticprivate |
Multiply the elements of dest
by multiplier
.
Definition at line 107 of file Grid_conversion.cc.
References Parma_Polyhedra_Library::Grid_Generator::expr, Parma_Polyhedra_Library::Grid_Generator::is_line(), and Parma_Polyhedra_Library::Grid_Generator::is_parameter_or_point().
|
staticprivate |
Normalizes the divisors in sys
.
Converts sys
to an equivalent system in which the divisors are of equal value.
sys | The generator system to be normalized. It must have at least one row. |
divisor | A reference to the initial value of the divisor. The resulting value of this object is the new system divisor. |
first_point | If first_point has a value other than NULL then it is taken as the first point in sys , and it is assumed that any following points have the same divisor as first_point . |
Definition at line 634 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Grid_Generator::divisor(), Parma_Polyhedra_Library::Grid_Generator::is_parameter_or_point(), Parma_Polyhedra_Library::lcm_assign(), Parma_Polyhedra_Library::Grid_Generator_System::num_rows(), Parma_Polyhedra_Library::Grid_Generator_System::space_dimension(), and Parma_Polyhedra_Library::Grid_Generator_System::sys.
Referenced by normalize_divisors().
|
inlinestaticprivate |
Normalizes the divisors in sys
.
Converts sys
to an equivalent system in which the divisors are of equal value.
sys | The generator system to be normalized. It must have at least one row. |
Definition at line 358 of file Grid_inlines.hh.
References normalize_divisors(), and PPL_DIRTY_TEMP_COEFFICIENT.
|
staticprivate |
Normalize all the divisors in sys
and gen_sys
.
Modify sys
and gen_sys
to use the same single divisor value for all generators, leaving each system representing the grid it represented originally.
sys | The first of the generator systems to be normalized. |
gen_sys | The second of the generator systems to be normalized. This system must have at least one row and the divisors of the generators in this system must be equal. |
std::runtime_error | Thrown if all rows in gen_sys are lines and/or parameters. |
Definition at line 592 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Grid_Generator::divisor(), Parma_Polyhedra_Library::Grid_Generator::is_parameter_or_point(), Parma_Polyhedra_Library::Grid_Generator_System::num_rows(), and PPL_DIRTY_TEMP_COEFFICIENT.
bool Parma_Polyhedra_Library::Grid::OK | ( | bool | check_not_empty = false | ) | const |
Checks if all the invariants are satisfied.
true
if and only if *this
satisfies all the invariants and either check_not_empty
is false
or *this
is not empty.check_not_empty | true if and only if, in addition to checking the invariants, *this must be checked to be not empty. |
The check is performed so as to intrude as little as possible. If the library has been compiled with run-time assertions enabled, error messages are written on std::cerr
in case invariants are violated. This is useful for the purpose of debugging the library.
Definition at line 958 of file Grid_public.cc.
References Parma_Polyhedra_Library::ascii_dump(), Parma_Polyhedra_Library::Congruence_System::ascii_dump(), Parma_Polyhedra_Library::Grid_Generator_System::ascii_dump(), Parma_Polyhedra_Library::Grid_Generator::ascii_dump(), clear_generators_up_to_date(), con_sys, gen_sys, Parma_Polyhedra_Library::Grid_Generator_System::has_no_rows(), Parma_Polyhedra_Library::Grid_Generator::is_equal_to(), Parma_Polyhedra_Library::Grid_Generator_System::m_swap(), and update_generators().
Referenced by congruence_widening_assign(), construct(), conversion(), generator_widening_assign(), Grid(), intersection_assign(), is_included_in(), map_space_dimensions(), simplify_using_context_assign(), time_elapse_assign(), and upper_bound_assign().
The assignment operator. (*this
and y
can be dimension-incompatible.)
Definition at line 251 of file Grid_public.cc.
References con_sys, congruences_are_up_to_date(), dim_kinds, gen_sys, generators_are_up_to_date(), marked_empty(), space_dim, and status.
void Parma_Polyhedra_Library::Grid::print | ( | ) | const |
Prints *this
to std::cerr
using operator<<
.
|
private |
Polynomial but incomplete equivalence test between grids.
Definition at line 182 of file Grid_nonpublic.cc.
References con_sys, congruences_are_minimized(), gen_sys, generators_are_minimized(), marked_empty(), Parma_Polyhedra_Library::Congruence_System::num_equalities(), Parma_Polyhedra_Library::Grid_Generator_System::num_lines(), Parma_Polyhedra_Library::Grid_Generator_System::num_rows(), Parma_Polyhedra_Library::Congruence_System::num_rows(), space_dim, TVB_DONT_KNOW, TVB_FALSE, and TVB_TRUE.
Referenced by contains(), and operator==().
|
staticprivate |
Reduce row
using pivot
.
Use the equality pivot
to change the representation of the congruence row
such that element at index column
of row
is zero.
Definition at line 190 of file Grid_simplify.cc.
References Parma_Polyhedra_Library::exact_div_assign(), Parma_Polyhedra_Library::Congruence::expr, Parma_Polyhedra_Library::gcd_assign(), Parma_Polyhedra_Library::Linear_Expression::get(), Parma_Polyhedra_Library::Congruence::is_proper_congruence(), Parma_Polyhedra_Library::Congruence::modulus(), Parma_Polyhedra_Library::neg_assign(), PPL_DIRTY_TEMP_COEFFICIENT, Parma_Polyhedra_Library::Congruence::scale(), Parma_Polyhedra_Library::Swapping_Vector< T >::size(), and Parma_Polyhedra_Library::sub_mul_assign().
Referenced by simplify().
|
staticprivate |
Reduces the equality row
using the equality pivot
.
Uses the equality pivot
to change the representation of the equality row
so that the element at index column
of row
is zero.
Definition at line 58 of file Grid_simplify.cc.
References Parma_Polyhedra_Library::exact_div_assign(), Parma_Polyhedra_Library::Congruence::expr, Parma_Polyhedra_Library::gcd_assign(), Parma_Polyhedra_Library::Linear_Expression::get(), Parma_Polyhedra_Library::Linear_Expression::linear_combine(), Parma_Polyhedra_Library::Congruence::modulus(), Parma_Polyhedra_Library::neg_assign(), Parma_Polyhedra_Library::Congruence::OK(), and PPL_DIRTY_TEMP_COEFFICIENT.
Referenced by simplify().
|
staticprivate |
Reduces the line row
using the line pivot
.
Uses the line pivot
to change the representation of the line row
so that the element at index column
of row
is zero.
Definition at line 31 of file Grid_simplify.cc.
References Parma_Polyhedra_Library::exact_div_assign(), Parma_Polyhedra_Library::Grid_Generator::expr, Parma_Polyhedra_Library::gcd_assign(), Parma_Polyhedra_Library::Linear_Expression::get(), Parma_Polyhedra_Library::Linear_Expression::linear_combine(), Parma_Polyhedra_Library::neg_assign(), Parma_Polyhedra_Library::Grid_Generator::OK(), PPL_DIRTY_TEMP_COEFFICIENT, and Parma_Polyhedra_Library::Linear_Expression::space_dimension().
Referenced by simplify().
|
staticprivate |
Reduce row
using pivot
.
Use the line pivot
to change the representation of the parameter row
such that the element at index column
of row
is zero.
Definition at line 129 of file Grid_simplify.cc.
References Parma_Polyhedra_Library::Coefficient_one(), Parma_Polyhedra_Library::exact_div_assign(), Parma_Polyhedra_Library::Grid_Generator::expr, Parma_Polyhedra_Library::gcd_assign(), Parma_Polyhedra_Library::Linear_Expression::get(), Parma_Polyhedra_Library::Grid_Generator::is_parameter_or_point(), Parma_Polyhedra_Library::Linear_Expression::linear_combine(), Parma_Polyhedra_Library::Linear_Expression::mul_assign(), Parma_Polyhedra_Library::neg_assign(), PPL_DIRTY_TEMP_COEFFICIENT, and Parma_Polyhedra_Library::Swapping_Vector< T >::size().
Referenced by simplify().
|
staticprivate |
Reduces row
using pivot
.
Uses the point, parameter or proper congruence at pivot
to change the representation of the point, parameter or proper congruence at row
so that the element at index column
of row
is zero. Only elements from index start
to index end
are modified (i.e. it is assumed that all other elements are zero). This means that col
must be in [start,end).
NOTE: This may invalidate the rows, since it messes with the divisors. Client code has to fix that (if needed) and assert OK().
Definition at line 88 of file Grid_simplify.cc.
References Parma_Polyhedra_Library::exact_div_assign(), Parma_Polyhedra_Library::gcdext_assign(), Parma_Polyhedra_Library::Linear_Expression::get(), Parma_Polyhedra_Library::Linear_Expression::linear_combine(), Parma_Polyhedra_Library::Linear_Expression::linear_combine_lax(), and PPL_DIRTY_TEMP_COEFFICIENT.
Referenced by simplify().
|
staticprivate |
Reduce column dim
in rows preceding pivot_index
in sys
.
Required when converting (or simplifying) a congruence or generator system to "strong minimal form"; informally, strong minimal form means that, not only is the system in minimal form (ie a triangular matrix), but also the absolute values of the coefficients of the proper congruences and parameters are minimal. As a simple example, the set of congruences , (which is in minimal form) is equivalent to the set
(which is in strong minimal form).
sys | The generator or congruence system to be reduced to strong minimal form. |
dim | Column to be reduced. |
pivot_index | Index of last row to be reduced. |
start | Index of first column to be changed. |
end | Index of last column to be changed. |
sys_dim_kinds | Dimension kinds of the elements of sys . |
generators | Flag indicating whether sys is a congruence or generator system |
Definition at line 276 of file Grid_templates.hh.
References Parma_Polyhedra_Library::Coefficient_one(), CON_VIRTUAL, EQUALITY, GEN_VIRTUAL, LINE, PARAMETER, PPL_DIRTY_TEMP_COEFFICIENT, and row_index.
|
private |
Uses the constraint c
to refine *this
.
c | The constraint to be added. Non-trivial inequalities are ignored. |
c
and *this
are dimension-incompatible, the behavior is undefined. Definition at line 729 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Constraint::is_equality(), Parma_Polyhedra_Library::Constraint::is_inconsistent(), and Parma_Polyhedra_Library::Constraint::space_dimension().
|
inline |
Uses a copy of the congruence cg
to refine *this
.
cg | The congruence used. |
std::invalid_argument | Thrown if *this and congruence cg are dimension-incompatible. |
Definition at line 285 of file Grid_inlines.hh.
References add_congruence().
Referenced by Parma_Polyhedra_Library::Affine_Space::refine_with_congruence().
|
inline |
Uses a copy of the congruences in cgs
to refine *this
.
cgs | The congruences used. |
std::invalid_argument | Thrown if *this and cgs are dimension-incompatible. |
Definition at line 290 of file Grid_inlines.hh.
References add_congruences().
Referenced by Parma_Polyhedra_Library::Affine_Space::refine_with_congruences().
void Parma_Polyhedra_Library::Grid::refine_with_constraint | ( | const Constraint & | c | ) |
Uses a copy of the constraint c
to refine *this
.
c | The constraint used. If it is not an equality, it will be ignored |
std::invalid_argument | Thrown if *this and c are dimension-incompatible. |
Definition at line 1403 of file Grid_public.cc.
References Parma_Polyhedra_Library::Constraint::space_dimension().
void Parma_Polyhedra_Library::Grid::refine_with_constraints | ( | const Constraint_System & | cs | ) |
Uses a copy of the constraints in cs
to refine *this
.
cs | The constraints used. Constraints that are not equalities are ignored. |
std::invalid_argument | Thrown if *this and cs are dimension-incompatible. |
Definition at line 1415 of file Grid_public.cc.
References Parma_Polyhedra_Library::Constraint_System::begin(), Parma_Polyhedra_Library::Constraint_System::end(), and Parma_Polyhedra_Library::Constraint_System::space_dimension().
PPL::Poly_Con_Relation Parma_Polyhedra_Library::Grid::relation_with | ( | const Congruence & | cg | ) | const |
Returns the relations holding between *this
and cg
.
Definition at line 386 of file Grid_public.cc.
References Parma_Polyhedra_Library::Scalar_Products::assign(), Parma_Polyhedra_Library::Grid_Generator::divisor(), Parma_Polyhedra_Library::gcd_assign(), Parma_Polyhedra_Library::Congruence::inhomogeneous_term(), Parma_Polyhedra_Library::Poly_Con_Relation::is_disjoint(), Parma_Polyhedra_Library::Congruence::is_equality(), Parma_Polyhedra_Library::Poly_Con_Relation::is_included(), Parma_Polyhedra_Library::Congruence::is_inconsistent(), Parma_Polyhedra_Library::Congruence::is_proper_congruence(), Parma_Polyhedra_Library::Grid_Generator::LINE, Parma_Polyhedra_Library::Congruence::modulus(), Parma_Polyhedra_Library::Grid_Generator::PARAMETER, Parma_Polyhedra_Library::Grid_Generator::POINT, PPL_DIRTY_TEMP_COEFFICIENT, Parma_Polyhedra_Library::Poly_Con_Relation::saturates(), Parma_Polyhedra_Library::Congruence::space_dimension(), Parma_Polyhedra_Library::Poly_Con_Relation::strictly_intersects(), and Parma_Polyhedra_Library::Grid_Generator::type().
Referenced by difference_assign(), limited_congruence_extrapolation_assign(), limited_extrapolation_assign(), limited_generator_extrapolation_assign(), and simplify_using_context_assign().
PPL::Poly_Gen_Relation Parma_Polyhedra_Library::Grid::relation_with | ( | const Grid_Generator & | g | ) | const |
Returns the relations holding between *this
and g
.
Definition at line 552 of file Grid_public.cc.
References Parma_Polyhedra_Library::Poly_Gen_Relation::nothing(), Parma_Polyhedra_Library::Grid_Generator::space_dimension(), and Parma_Polyhedra_Library::Poly_Gen_Relation::subsumes().
PPL::Poly_Gen_Relation Parma_Polyhedra_Library::Grid::relation_with | ( | const Generator & | g | ) | const |
Returns the relations holding between *this
and g
.
Definition at line 580 of file Grid_public.cc.
References Parma_Polyhedra_Library::Generator::divisor(), Parma_Polyhedra_Library::Generator::expression(), Parma_Polyhedra_Library::Generator::is_closure_point(), Parma_Polyhedra_Library::Generator::is_point(), Parma_Polyhedra_Library::Poly_Gen_Relation::nothing(), Parma_Polyhedra_Library::Generator::space_dimension(), and Parma_Polyhedra_Library::Poly_Gen_Relation::subsumes().
PPL::Poly_Con_Relation Parma_Polyhedra_Library::Grid::relation_with | ( | const Constraint & | c | ) | const |
Returns the relations holding between *this
and c
.
Definition at line 622 of file Grid_public.cc.
References Parma_Polyhedra_Library::Grid_Generator::divisor(), Parma_Polyhedra_Library::Constraint::expr, Parma_Polyhedra_Library::Grid_Generator::expr, Parma_Polyhedra_Library::Constraint::inhomogeneous_term(), Parma_Polyhedra_Library::Poly_Con_Relation::is_disjoint(), Parma_Polyhedra_Library::Constraint::is_equality(), Parma_Polyhedra_Library::Poly_Con_Relation::is_included(), Parma_Polyhedra_Library::Constraint::is_inconsistent(), Parma_Polyhedra_Library::Constraint::is_strict_inequality(), Parma_Polyhedra_Library::Grid_Generator::LINE, Parma_Polyhedra_Library::Linear_Expression::linear_combine(), Parma_Polyhedra_Library::Grid_Generator::OK(), Parma_Polyhedra_Library::Grid_Generator::PARAMETER, Parma_Polyhedra_Library::Grid_Generator::POINT, Parma_Polyhedra_Library::Scalar_Products::reduced_sign(), Parma_Polyhedra_Library::Poly_Con_Relation::saturates(), Parma_Polyhedra_Library::Linear_Expression::set_inhomogeneous_term(), Parma_Polyhedra_Library::Grid_Generator::set_is_parameter(), Parma_Polyhedra_Library::Scalar_Products::sign(), Parma_Polyhedra_Library::Constraint::space_dimension(), Parma_Polyhedra_Library::Linear_Expression::space_dimension(), Parma_Polyhedra_Library::Poly_Con_Relation::strictly_intersects(), Parma_Polyhedra_Library::Grid_Generator::strong_normalize(), and Parma_Polyhedra_Library::Grid_Generator::type().
void Parma_Polyhedra_Library::Grid::remove_higher_space_dimensions | ( | dimension_type | new_dimension | ) |
Removes the higher dimensions of the vector space so that the resulting space will have dimension new_dimension
..
std::invalid_argument | Thrown if new_dimensions is greater than the space dimension of *this . |
Definition at line 318 of file Grid_chdims.cc.
References Parma_Polyhedra_Library::Congruence_System::set_space_dimension(), Parma_Polyhedra_Library::swap(), and Parma_Polyhedra_Library::Congruence::zero_dim_false().
void Parma_Polyhedra_Library::Grid::remove_space_dimensions | ( | const Variables_Set & | vars | ) |
Removes all the specified dimensions from the vector space.
vars | The set of Variable objects corresponding to the space dimensions to be removed. |
std::invalid_argument | Thrown if *this is dimension-incompatible with one of the Variable objects contained in vars . |
Definition at line 273 of file Grid_chdims.cc.
References Parma_Polyhedra_Library::Variables_Set::space_dimension().
|
staticprivate |
Checks that trailing rows contain only zero terms.
If all columns contain zero in the rows of system
from row index first
to row index last
then return true
, else return false
. row_size
gives the number of columns in each row.
This method is only used in assertions in the simplify methods.
Definition at line 239 of file Grid_simplify.cc.
|
private |
Copies a widened selection of congruences from y
to selected_cgs
.
Definition at line 33 of file Grid_widenings.cc.
References con_sys, CON_VIRTUAL, congruences_are_minimized(), dim_kinds, EQUALITY, Parma_Polyhedra_Library::Congruence_System::insert(), Parma_Polyhedra_Library::Congruence::is_equal_at_dimension(), marked_empty(), PROPER_CONGRUENCE, space_dim, and Parma_Polyhedra_Library::Congruence_System::space_dimension().
Referenced by congruence_widening_assign().
|
private |
Copies widened generators from y
to widened_ggs
.
Definition at line 232 of file Grid_widenings.cc.
References dim_kinds, Parma_Polyhedra_Library::Grid_Generator::expression(), gen_sys, generators_are_minimized(), Parma_Polyhedra_Library::Grid_Generator_System::insert(), Parma_Polyhedra_Library::Grid_Generator::is_equal_at_dimension(), marked_empty(), and space_dim.
Referenced by generator_widening_assign().
|
inlineprivate |
Sets status
to express that congruences are minimized.
Definition at line 70 of file Grid_inlines.hh.
References Parma_Polyhedra_Library::Grid::Status::set_c_minimized(), set_congruences_up_to_date(), and status.
Referenced by congruence_widening_assign(), construct(), Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate(), is_empty(), minimize(), minimized_congruences(), and update_generators().
|
inlineprivate |
Sets status
to express that congruences are up-to-date.
Definition at line 65 of file Grid_inlines.hh.
References Parma_Polyhedra_Library::Grid::Status::set_c_up_to_date(), and status.
Referenced by Grid(), and set_congruences_minimized().
|
private |
Sets status
to express that the grid is empty, clearing all corresponding matrices.
Definition at line 468 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Congruence_System::set_space_dimension(), Parma_Polyhedra_Library::swap(), and Parma_Polyhedra_Library::Congruence::zero_dim_false().
Referenced by congruence_widening_assign(), difference_assign(), Grid(), grid_generators(), intersection_assign(), is_empty(), map_space_dimensions(), minimized_congruences(), minimized_grid_generators(), time_elapse_assign(), and update_generators().
|
inlineprivate |
Sets status
to express that generators are minimized.
Definition at line 76 of file Grid_inlines.hh.
References Parma_Polyhedra_Library::Grid::Status::set_g_minimized(), set_generators_up_to_date(), and status.
Referenced by construct(), generator_widening_assign(), Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate(), max_min(), minimize(), minimized_grid_generators(), and update_generators().
|
inlineprivate |
Sets status
to express that generators are up-to-date.
Definition at line 60 of file Grid_inlines.hh.
References Parma_Polyhedra_Library::Grid::Status::set_g_up_to_date(), and status.
Referenced by Grid(), and set_generators_minimized().
|
private |
Sets status
to express that the grid is the universe 0-dimension vector space, clearing all corresponding matrices.
Definition at line 459 of file Grid_nonpublic.cc.
Referenced by construct(), Grid(), and map_space_dimensions().
|
staticprivate |
Converts cgs
to upper triangular (i.e. minimized) form.
Returns true
if cgs
represents the empty set, otherwise returns false
.
Definition at line 389 of file Grid_simplify.cc.
References Parma_Polyhedra_Library::Coefficient_one(), Parma_Polyhedra_Library::Coefficient_zero(), CON_VIRTUAL, dim_kinds, EQUALITY, Parma_Polyhedra_Library::Congruence::expr, Parma_Polyhedra_Library::Linear_Expression::get(), Parma_Polyhedra_Library::Congruence::inhomogeneous_term(), Parma_Polyhedra_Library::Congruence_System::insert_verbatim(), Parma_Polyhedra_Library::Congruence::is_equality(), Parma_Polyhedra_Library::Congruence::is_proper_congruence(), Parma_Polyhedra_Library::Congruence::modulus(), Parma_Polyhedra_Library::Linear_Expression::negate(), Parma_Polyhedra_Library::Congruence_System::normalize_moduli(), Parma_Polyhedra_Library::Congruence_System::num_rows(), Parma_Polyhedra_Library::Congruence_System::OK(), PROPER_CONGRUENCE, reduce_congruence_with_equality(), reduce_equality_with_equality(), reduce_pc_with_pc(), Parma_Polyhedra_Library::Congruence_System::remove_trailing_rows(), row_index, Parma_Polyhedra_Library::Congruence_System::rows, Parma_Polyhedra_Library::Linear_Expression::set_inhomogeneous_term(), Parma_Polyhedra_Library::Congruence::set_modulus(), Parma_Polyhedra_Library::Congruence::set_space_dimension(), Parma_Polyhedra_Library::Congruence_System::space_dimension(), swap(), and Parma_Polyhedra_Library::swap().
Referenced by Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate(), is_empty(), max_min(), minimize(), minimized_congruences(), minimized_grid_generators(), and update_congruences().
|
staticprivate |
Converts gs
to lower triangular (i.e. minimized) form.
Expects gs
to contain at least one point.
Definition at line 252 of file Grid_simplify.cc.
References dim_kinds, Parma_Polyhedra_Library::Grid_Generator::expr, GEN_VIRTUAL, Parma_Polyhedra_Library::Linear_Expression::get(), Parma_Polyhedra_Library::Grid_Generator_System::has_no_rows(), Parma_Polyhedra_Library::Grid_Generator::is_line(), Parma_Polyhedra_Library::Grid_Generator::is_parameter_or_point(), LINE, Parma_Polyhedra_Library::Linear_Expression::negate(), Parma_Polyhedra_Library::Grid_Generator_System::num_rows(), PARAMETER, reduce_line_with_line(), reduce_parameter_with_line(), reduce_pc_with_pc(), row_index, Parma_Polyhedra_Library::Grid_Generator_System::space_dimension(), swap(), Parma_Polyhedra_Library::swap(), Parma_Polyhedra_Library::Grid_Generator_System::sys, and Parma_Polyhedra_Library::Grid_Generator_System::unset_pending_rows().
bool Parma_Polyhedra_Library::Grid::simplify_using_context_assign | ( | const Grid & | y | ) |
Assigns to *this
a meet-preserving simplification of *this
with respect to y
. If false
is returned, then the intersection is empty.
std::invalid_argument | Thrown if *this and y are topology-incompatible or dimension-incompatible. |
Definition at line 1691 of file Grid_public.cc.
References add_congruence(), add_congruences(), add_recycled_congruences(), add_space_dimensions_and_embed(), Parma_Polyhedra_Library::Scalar_Products::assign(), Parma_Polyhedra_Library::Grid_Generator_System::begin(), c, con_sys, congruences_are_minimized(), congruences_are_up_to_date(), Parma_Polyhedra_Library::Grid_Generator::divisor(), Parma_Polyhedra_Library::Grid_Generator_System::end(), Parma_Polyhedra_Library::Congruence::expression(), generators_are_minimized(), Parma_Polyhedra_Library::Poly_Con_Relation::implies(), Parma_Polyhedra_Library::Congruence_System::insert(), is_empty(), Parma_Polyhedra_Library::Congruence::is_equality(), Parma_Polyhedra_Library::Poly_Con_Relation::is_included(), is_included_in(), Parma_Polyhedra_Library::Grid_Generator::is_parameter(), Parma_Polyhedra_Library::Grid_Generator::is_point(), Parma_Polyhedra_Library::Congruence::is_proper_congruence(), Parma_Polyhedra_Library::Congruence::is_tautological(), Parma_Polyhedra_Library::Boundary_NS::le(), m_swap(), minimize(), Parma_Polyhedra_Library::Congruence::modulus(), Parma_Polyhedra_Library::Congruence_System::num_rows(), OK(), PPL_DIRTY_TEMP_COEFFICIENT, relation_with(), space_dim, and Parma_Polyhedra_Library::UNIVERSE.
|
inline |
Returns the dimension of the vector space enclosing *this
.
Definition at line 224 of file Grid_inlines.hh.
References space_dim.
Referenced by add_space_dimensions(), Parma_Polyhedra_Library::Pointset_Powerset< PSET >::approximate_partition(), Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), Parma_Polyhedra_Library::Box< ITV >::Box(), Parma_Polyhedra_Library::Pointset_Powerset< PSET >::check_containment(), concatenate_assign(), Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate(), hash_code(), Parma_Polyhedra_Library::Octagonal_Shape< T >::Octagonal_Shape(), Parma_Polyhedra_Library::Affine_Space::space_dimension(), and throw_dimension_incompatible().
|
inline |
Returns true
if and only if *this
strictly contains y
.
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
Definition at line 371 of file Grid_inlines.hh.
References contains().
Referenced by Parma_Polyhedra_Library::Affine_Space::strictly_contains().
|
protected |
Definition at line 751 of file Grid_nonpublic.cc.
Referenced by add_congruence(), add_congruences(), and add_constraint().
|
protected |
Definition at line 762 of file Grid_nonpublic.cc.
References space_dimension().
|
protected |
Definition at line 769 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Linear_Expression::space_dimension().
|
protected |
Definition at line 776 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Congruence::space_dimension().
|
protected |
Definition at line 783 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Constraint::space_dimension().
|
protected |
Definition at line 790 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Grid_Generator::space_dimension().
|
protected |
Definition at line 797 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Generator::space_dimension().
|
protected |
Definition at line 804 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Congruence_System::space_dimension().
|
protected |
Definition at line 811 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Constraint_System::space_dimension().
|
protected |
Definition at line 818 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Grid_Generator_System::space_dimension().
|
protected |
Definition at line 825 of file Grid_nonpublic.cc.
References Parma_Polyhedra_Library::Variable::space_dimension().
|
protected |
Definition at line 837 of file Grid_nonpublic.cc.
|
staticprotected |
Definition at line 743 of file Grid_nonpublic.cc.
Referenced by map_space_dimensions().
|
staticprotected |
Definition at line 847 of file Grid_nonpublic.cc.
Referenced by Grid().
|
staticprotected |
Definition at line 856 of file Grid_nonpublic.cc.
Referenced by Grid().
|
staticprotected |
Definition at line 866 of file Grid_nonpublic.cc.
|
staticprotected |
Definition at line 876 of file Grid_nonpublic.cc.
void Parma_Polyhedra_Library::Grid::time_elapse_assign | ( | const Grid & | y | ) |
Assigns to *this
the result of computing the time-elapse between *this
and y
.
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
Definition at line 2641 of file Grid_public.cc.
References clear_congruences_up_to_date(), clear_generators_minimized(), gen_sys, generators_are_up_to_date(), Parma_Polyhedra_Library::Grid_Generator::is_point(), marked_empty(), Parma_Polyhedra_Library::Grid_Generator_System::num_rows(), OK(), set_empty(), Parma_Polyhedra_Library::Grid_Generator::set_is_parameter(), space_dim, Parma_Polyhedra_Library::Grid_Generator_System::sys, and update_generators().
|
inline |
Assigns to *this
its topological closure.
Definition at line 377 of file Grid_inlines.hh.
|
inline |
Returns the total size in bytes of the memory occupied by *this
.
Definition at line 229 of file Grid_inlines.hh.
References external_memory_in_bytes().
Referenced by Parma_Polyhedra_Library::Affine_Space::total_memory_in_bytes().
void Parma_Polyhedra_Library::Grid::unconstrain | ( | Variable | var | ) |
Computes the cylindrification of *this
with respect to space dimension var
, assigning the result to *this
.
var | The space dimension that will be unconstrained. |
std::invalid_argument | Thrown if var is not a space dimension of *this . |
Definition at line 1428 of file Grid_public.cc.
References Parma_Polyhedra_Library::Variable::space_dimension().
void Parma_Polyhedra_Library::Grid::unconstrain | ( | const Variables_Set & | vars | ) |
Computes the cylindrification of *this
with respect to the set of space dimensions vars
, assigning the result to *this
.
vars | The set of space dimension that will be unconstrained. |
std::invalid_argument | Thrown if *this is dimension-incompatible with one of the Variable objects contained in vars . |
Definition at line 1450 of file Grid_public.cc.
References Parma_Polyhedra_Library::Variables_Set::space_dimension().
|
private |
Updates and minimizes the congruences from the generators.
Definition at line 483 of file Grid_nonpublic.cc.
References simplify().
Referenced by congruence_widening_assign(), intersection_assign(), and is_included_in().
|
private |
Updates and minimizes the generators from the congruences.
false
if and only if *this
turns out to be an empty grid.It is illegal to call this method when the Status field already declares the grid to be empty.
Definition at line 510 of file Grid_nonpublic.cc.
References con_sys, dim_kinds, gen_sys, set_congruences_minimized(), set_empty(), and set_generators_minimized().
Referenced by Parma_Polyhedra_Library::Box< ITV >::Box(), generator_widening_assign(), limited_congruence_extrapolation_assign(), limited_extrapolation_assign(), limited_generator_extrapolation_assign(), map_space_dimensions(), OK(), time_elapse_assign(), and upper_bound_assign().
void Parma_Polyhedra_Library::Grid::upper_bound_assign | ( | const Grid & | y | ) |
Assigns to *this
the least upper bound of *this
and y
.
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
Definition at line 1526 of file Grid_public.cc.
References clear_congruences_up_to_date(), clear_generators_minimized(), gen_sys, generators_are_up_to_date(), Parma_Polyhedra_Library::Grid_Generator_System::insert(), marked_empty(), OK(), space_dim, and update_generators().
Referenced by difference_assign(), and upper_bound_assign_if_exact().
bool Parma_Polyhedra_Library::Grid::upper_bound_assign_if_exact | ( | const Grid & | y | ) |
If the upper bound 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. |
Definition at line 1571 of file Grid_public.cc.
References difference_assign(), is_included_in(), marked_empty(), space_dim, Parma_Polyhedra_Library::upper_bound_assign(), and upper_bound_assign().
|
staticprivate |
If sys
is upper triangular return true
, else return false
.
Definition at line 75 of file Grid_conversion.cc.
References Parma_Polyhedra_Library::Linear_Expression::all_zeroes(), Parma_Polyhedra_Library::Grid_Generator::expr, GEN_VIRTUAL, Parma_Polyhedra_Library::Linear_Expression::get(), Parma_Polyhedra_Library::Grid_Generator_System::num_rows(), and Parma_Polyhedra_Library::Grid_Generator_System::space_dimension().
Referenced by conversion().
void Parma_Polyhedra_Library::Grid::widening_assign | ( | const Grid & | y, |
unsigned * | tp = NULL |
||
) |
Assigns to *this
the result of computing the Grid widening between *this
and y
.
This widening uses either the congruence or generator systems depending on which of the systems describing x and y are up to date and minimized.
y | A grid that must be contained in *this ; |
tp | An optional pointer to an unsigned variable storing the number of available tokens (to be used when applying the widening with tokens delay technique). |
std::invalid_argument | Thrown if *this and y are dimension-incompatible. |
Definition at line 441 of file Grid_widenings.cc.
References congruence_widening_assign(), congruences_are_up_to_date(), generator_widening_assign(), generators_are_up_to_date(), and space_dim.
Referenced by limited_congruence_extrapolation_assign(), and limited_extrapolation_assign().
void Parma_Polyhedra_Library::Grid::wrap_assign | ( | const Variables_Set & | vars, |
Bounded_Integer_Type_Width | w, | ||
Bounded_Integer_Type_Representation | r, | ||
Bounded_Integer_Type_Overflow | o, | ||
const Constraint_System * | cs_p = 0 , |
||
unsigned | complexity_threshold = 16 , |
||
bool | wrap_individually = true |
||
) |
Wraps the specified dimensions of the vector space.
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. |
cs_p | Possibly null pointer to a constraint system. This argument is for compatibility with wrap_assign() for the other domains and only checked for dimension-compatibility. |
complexity_threshold | A precision parameter of the wrapping operator. This argument is for compatibility with wrap_assign() for the other domains and is ignored. |
wrap_individually | true if the dimensions should be wrapped individually. As wrapping dimensions collectively does not improve the precision, this argument is ignored. |
std::invalid_argument | Thrown if *this is dimension-incompatible with one of the Variable objects contained in vars or with *cs_p . |
Vars
represent integers. Thus, where the extra cost is negligible, the integrality of these variables is enforced; possibly causing a non-integral grid to become empty. Definition at line 2923 of file Grid_public.cc.
References bounds_no_check(), Parma_Polyhedra_Library::Grid_Generator::coefficient(), Parma_Polyhedra_Library::Coefficient_one(), Parma_Polyhedra_Library::Grid_Generator::divisor(), frequency_no_check(), gen_sys, Parma_Polyhedra_Library::mul_2exp_assign(), Parma_Polyhedra_Library::neg_assign(), Parma_Polyhedra_Library::OVERFLOW_IMPOSSIBLE, Parma_Polyhedra_Library::OVERFLOW_UNDEFINED, Parma_Polyhedra_Library::OVERFLOW_WRAPS, PPL_DIRTY_TEMP_COEFFICIENT, Parma_Polyhedra_Library::SIGNED_2_COMPLEMENT, Parma_Polyhedra_Library::Variables_Set::space_dimension(), Parma_Polyhedra_Library::Constraint_System::space_dimension(), and Parma_Polyhedra_Library::UNSIGNED.
Returns true
if and only if x
and y
are different grids.
Note that x
and y
may be dimension-incompatible grids: in those cases, the value true
is returned.
Definition at line 366 of file Grid_inlines.hh.
|
related |
Output operator.
Writes a textual representation of gr
on s:
false
is written if gr
is an empty grid; true
is written if gr
is a universe grid; a minimized system of congruences defining gr
is written otherwise, all congruences in one row separated by ", "s.
|
related |
Definition at line 3157 of file Grid_public.cc.
References is_empty(), is_universe(), and minimized_congruences().
Returns true
if and only if x
and y
are the same grid.
Note that x
and y
may be dimension-incompatible grids: in those cases, the value false
is returned.
Definition at line 2730 of file Grid_public.cc.
References is_empty(), is_included_in(), marked_empty(), quick_equivalence_test(), space_dim, TVB_FALSE, and TVB_TRUE.
|
friend |
Definition at line 1928 of file Grid_defs.hh.
|
friend |
Definition at line 1926 of file Grid_defs.hh.
Swaps x
with y
.
Referenced by construct(), m_swap(), and simplify().
|
private |
The system of congruences.
Definition at line 1970 of file Grid_defs.hh.
Referenced by congruence_widening_assign(), construct(), Grid(), Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate(), intersection_assign(), is_empty(), is_included_in(), m_swap(), map_space_dimensions(), minimize(), minimized_congruences(), OK(), operator=(), quick_equivalence_test(), select_wider_congruences(), simplify_using_context_assign(), and update_generators().
|
private |
Definition at line 2002 of file Grid_defs.hh.
Referenced by add_space_dimensions(), congruence_widening_assign(), construct(), conversion(), generator_widening_assign(), Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate(), is_empty(), m_swap(), max_min(), minimize(), minimized_congruences(), minimized_grid_generators(), operator=(), select_wider_congruences(), select_wider_generators(), simplify(), and update_generators().
|
private |
The system of generators.
Definition at line 1973 of file Grid_defs.hh.
Referenced by Parma_Polyhedra_Library::Box< ITV >::Box(), construct(), generator_widening_assign(), Grid(), Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate(), m_swap(), map_space_dimensions(), max_min(), minimize(), minimized_grid_generators(), OK(), operator=(), quick_equivalence_test(), select_wider_generators(), time_elapse_assign(), update_generators(), upper_bound_assign(), and wrap_assign().
|
private |
The number of dimensions of the enclosing vector space.
Definition at line 1983 of file Grid_defs.hh.
Referenced by add_congruence(), add_congruences(), add_constraint(), concatenate_assign(), congruence_widening_assign(), construct(), contains(), difference_assign(), generator_widening_assign(), Grid(), intersection_assign(), is_disjoint_from(), is_included_in(), limited_congruence_extrapolation_assign(), limited_extrapolation_assign(), limited_generator_extrapolation_assign(), m_swap(), map_space_dimensions(), operator=(), operator==(), quick_equivalence_test(), select_wider_congruences(), select_wider_generators(), simplify_using_context_assign(), space_dimension(), time_elapse_assign(), upper_bound_assign(), upper_bound_assign_if_exact(), and widening_assign().
|
private |
The status flags to keep track of the grid's internal state.
Definition at line 1980 of file Grid_defs.hh.
Referenced by clear_congruences_minimized(), clear_congruences_up_to_date(), clear_empty(), clear_generators_minimized(), clear_generators_up_to_date(), congruences_are_minimized(), congruences_are_up_to_date(), construct(), generators_are_minimized(), generators_are_up_to_date(), Grid(), m_swap(), marked_empty(), operator=(), set_congruences_minimized(), set_congruences_up_to_date(), set_generators_minimized(), and set_generators_up_to_date().