#include <Congruence.defs.hh>
Public Member Functions | |
Congruence (const Congruence &cg) | |
Ordinary copy-constructor. | |
Congruence (const Constraint &c) | |
Copy-constructs (modulo 0) from equality constraint c . | |
~Congruence () | |
Destructor. | |
Congruence & | operator= (const Congruence &cg) |
Assignment operator. | |
dimension_type | space_dimension () const |
Returns the dimension of the vector space enclosing *this . | |
Coefficient_traits::const_reference | coefficient (Variable v) const |
Returns the coefficient of v in *this . | |
Coefficient_traits::const_reference | inhomogeneous_term () const |
Returns the inhomogeneous term of *this . | |
Coefficient_traits::const_reference | modulus () const |
Returns a const reference to the modulus of *this . | |
Congruence & | operator/= (Coefficient_traits::const_reference k) |
Multiplies k into the modulus of *this . | |
bool | is_tautological () const |
Returns true if and only if *this is a tautology (i.e., an always true congruence). | |
bool | is_inconsistent () const |
Returns true if and only if *this is inconsistent (i.e., an always false congruence). | |
bool | is_proper_congruence () const |
Returns true if the modulus is greater than zero. | |
bool | is_equality () const |
Returns true if *this is an equality. | |
bool | is_equal_at_dimension (dimension_type dim, const Congruence &cg) const |
Returns true if *this is equal to cg in dimension dim . | |
memory_size_type | total_memory_in_bytes () const |
Returns a lower bound to the total size in bytes of the memory occupied by *this . | |
memory_size_type | external_memory_in_bytes () const |
Returns the size in bytes of the memory managed by *this . | |
void | ascii_dump () const |
Writes to std::cerr an ASCII representation of *this . | |
void | ascii_dump (std::ostream &s) const |
Writes to s an ASCII representation of *this . | |
void | print () const |
Prints *this to std::cerr using operator<< . | |
bool | ascii_load (std::istream &s) |
Loads from s an ASCII representation of the internal representation of *this . | |
bool | OK () const |
Checks if all the invariants are satisfied. | |
Static Public Member Functions | |
static dimension_type | max_space_dimension () |
Returns the maximum space dimension a Congruence can handle. | |
static void | initialize () |
Initializes the class. | |
static void | finalize () |
Finalizes the class. | |
static const Congruence & | zero_dim_integrality () |
Returns a reference to the true (zero-dimension space) congruence ![]() | |
static const Congruence & | zero_dim_false () |
Returns a reference to the false (zero-dimension space) congruence ![]() | |
static Congruence | create (const Linear_Expression &e1, const Linear_Expression &e2) |
Returns the congruence ![]() | |
static Congruence | create (const Linear_Expression &e, Coefficient_traits::const_reference n) |
Returns the congruence ![]() | |
static Congruence | create (Coefficient_traits::const_reference n, const Linear_Expression &e) |
Returns the congruence ![]() | |
Protected Member Functions | |
void | sign_normalize () |
Normalizes the signs. | |
void | normalize () |
Normalizes signs and the inhomogeneous term. | |
void | strong_normalize () |
Calls normalize, then divides out common factors. | |
Private Member Functions | |
void | set_is_equality () |
Marks this congruence as a linear equality. | |
void | negate (dimension_type start, dimension_type end) |
Negates the elements from index start to index end . | |
Congruence () | |
Default constructor: private and not implemented. | |
Congruence (const Congruence &cg, dimension_type sz, dimension_type capacity) | |
Copy-constructs with specified size and capacity. | |
Congruence (const Constraint &c, dimension_type sz, dimension_type capacity) | |
Constructs from a constraint, with specified size and capacity. | |
Congruence (const Congruence &cg, Coefficient_traits::const_reference k) | |
Copy-constructs from cg , multiplying k into the modulus. | |
Congruence (Linear_Expression &le, Coefficient_traits::const_reference m) | |
Constructs from Linear_Expression le , using modulus m . | |
void | swap (Congruence &y) |
Swaps *this with y . | |
void | throw_invalid_argument (const char *method, const char *message) const |
Throws a std::invalid_argument exception containing error message message . | |
void | throw_dimension_incompatible (const char *method, const char *v_name, Variable v) const |
Throws a std::invalid_argument exception containing the appropriate error message. | |
Static Private Attributes | |
static const Congruence * | zero_dim_false_p = 0 |
Holds (between class initialization and finalization) a pointer to the false (zero-dimension space) congruence ![]() | |
static const Congruence * | zero_dim_integrality_p = 0 |
Holds (between class initialization and finalization) a pointer to the true (zero-dimension space) congruence ![]() | |
Friends | |
class | Parma_Polyhedra_Library::Scalar_Products |
class | Parma_Polyhedra_Library::Constraint |
class | Parma_Polyhedra_Library::Congruence_System |
class | Parma_Polyhedra_Library::Congruence_System::const_iterator |
class | Parma_Polyhedra_Library::Grid |
class | Parma_Polyhedra_Library::Linear_Expression |
Congruence | operator/ (const Congruence &cg, Coefficient_traits::const_reference k) |
Returns a copy of cg , multiplying k into the copy's modulus. | |
Congruence | operator/ (const Constraint &c, Coefficient_traits::const_reference m) |
Creates a congruence from c , with m as the modulus. | |
bool | operator== (const Congruence &x, const Congruence &y) |
Returns true if and only if x and y are equivalent. | |
bool | operator!= (const Congruence &x, const Congruence &y) |
Returns false if and only if x and y are equivalent. | |
std::ostream & | operator<< (std::ostream &s, const Congruence_System &cgs) |
Output operator. | |
void | swap (Parma_Polyhedra_Library::Congruence &x, Parma_Polyhedra_Library::Congruence &y) |
Specializes std::swap . | |
Related Functions | |
(Note that these are not member functions.) | |
std::ostream & | operator<< (std::ostream &s, const Congruence &c) |
Output operators. | |
Congruence | operator%= (const Linear_Expression &e1, const Linear_Expression &e2) |
Returns the congruence ![]() | |
Congruence | operator%= (const Linear_Expression &e, Coefficient_traits::const_reference n) |
Returns the congruence ![]() |
An object of the class Congruence is a congruence:
where is the dimension of the space,
is the integer coefficient of variable
,
is the integer inhomogeneous term and
is the integer modulus; if
, then
represents the equality congruence
and, if
, then the congruence
is said to be a proper congruence.
%=
' to a pair of linear expressions. Congruences with modulus m
are typically constructed by building a congruence m
using the modulus symbol is `/
'.
x
, y
and z
are defined as follows: Variable x(0); Variable y(1); Variable z(2);
Congruence eq_cg((3*x + 5*y - z %= 0) / 0);
Congruence mod1_cg(4*x %= 2*y - 13);
Congruence mod2_cg((4*x %= 2*y - 13) / 2);
Congruence false_cg = Congruence::zero_dim_false();
Congruence false_cg1((Linear_Expression::zero() %= 1) / 0); Congruence false_cg2((Linear_Expression::zero() %= 1) / 2);
Congruence false_cg3((0*z %= 1) / 0);
e
and modulus m
(in this case m
but where the linear expression is Congruence cg1((x - 5*y + 3*z %= 4) / 5); cout << "Congruence cg1: " << cg1 << endl; const Coefficient& m = cg1.modulus(); if (m == 0) cout << "Congruence cg1 is an equality." << endl; else { Linear_Expression e; for (dimension_type i = cg1.space_dimension(); i-- > 0; ) e += 2 * cg1.coefficient(Variable(i)) * Variable(i); e += 2 * cg1.inhomogeneous_term(); Congruence cg2((e %= 0) / m); cout << "Congruence cg2: " << cg2 << endl; }
Congruence cg1: A - 5*B + 3*C %= 4 / 5 Congruence cg2: 2*A - 10*B + 6*C %= 8 / 5
Definition at line 210 of file Congruence.defs.hh.
Parma_Polyhedra_Library::Congruence::Congruence | ( | const Congruence & | cg | ) | [inline] |
Ordinary copy-constructor.
Definition at line 34 of file Congruence.inlines.hh.
00035 : Row(cg) { 00036 }
Parma_Polyhedra_Library::Congruence::Congruence | ( | const Constraint & | c | ) | [explicit] |
Copy-constructs (modulo 0) from equality constraint c
.
std::invalid_argument | Thrown if c is an inequality. |
Definition at line 36 of file Congruence.cc.
References Parma_Polyhedra_Library::Row::size().
00037 : Row(c.is_equality() 00038 ? c 00039 : (throw_invalid_argument("Congruence(c)", 00040 "constraint c must be an equality."), 00041 c), 00042 c.space_dimension() + 2, 00043 compute_capacity(c.space_dimension() + 2, Row::max_size())) { 00044 (*this)[size()-1] = 0; 00045 }
Parma_Polyhedra_Library::Congruence::~Congruence | ( | ) | [inline] |
Parma_Polyhedra_Library::Congruence::Congruence | ( | ) | [private] |
Parma_Polyhedra_Library::Congruence::Congruence | ( | const Congruence & | cg, | |
dimension_type | sz, | |||
dimension_type | capacity | |||
) | [inline, private] |
Copy-constructs with specified size and capacity.
Definition at line 39 of file Congruence.inlines.hh.
00041 : Row(cg, sz, capacity) { 00042 }
Parma_Polyhedra_Library::Congruence::Congruence | ( | const Constraint & | c, | |
dimension_type | sz, | |||
dimension_type | capacity | |||
) | [private] |
Constructs from a constraint, with specified size and capacity.
Definition at line 47 of file Congruence.cc.
00049 : Row(c.is_equality() 00050 ? c 00051 : (throw_invalid_argument("Congruence(c)", 00052 "constraint c must be an equality."), 00053 c), 00054 sz, 00055 capacity) { 00056 assert(sz > 1); 00057 (*this)[sz-1] = 0; 00058 }
Parma_Polyhedra_Library::Congruence::Congruence | ( | const Congruence & | cg, | |
Coefficient_traits::const_reference | k | |||
) | [inline, private] |
Copy-constructs from cg
, multiplying k
into the modulus.
If cg
represents the congruence , then the result represents the congruence
.
Definition at line 45 of file Congruence.inlines.hh.
References Parma_Polyhedra_Library::Row::size().
00047 : Row(cg) { 00048 if (k >= 0) 00049 (*this)[size()-1] *= k; 00050 else 00051 (*this)[size()-1] *= -k; 00052 }
Parma_Polyhedra_Library::Congruence::Congruence | ( | Linear_Expression & | le, | |
Coefficient_traits::const_reference | m | |||
) | [inline, private] |
Constructs from Linear_Expression le
, using modulus m
.
Builds a congruence with modulus m
, stealing the coefficients from le
.
le | The Linear_Expression holding the coefficients. | |
m | The modulus for the congruence, which must be zero or greater. |
Definition at line 59 of file Congruence.inlines.hh.
References Parma_Polyhedra_Library::Row::size(), and Parma_Polyhedra_Library::swap().
00060 { 00061 Row::swap(static_cast<Row&>(le)); 00062 assert(m >= 0); 00063 (*this)[size()-1] = m; 00064 }
Congruence & Parma_Polyhedra_Library::Congruence::operator= | ( | const Congruence & | cg | ) | [inline] |
Assignment operator.
Definition at line 116 of file Congruence.inlines.hh.
References Parma_Polyhedra_Library::Row::operator=().
00116 { 00117 Row::operator=(c); 00118 return *this; 00119 }
dimension_type Parma_Polyhedra_Library::Congruence::max_space_dimension | ( | ) | [inline, static] |
Returns the maximum space dimension a Congruence can handle.
Definition at line 154 of file Congruence.inlines.hh.
References Parma_Polyhedra_Library::Row::max_size().
00154 { 00155 // The first coefficient holds the inhomogeneous term, while 00156 // the last coefficient is for the modulus. 00157 return max_size() - 2; 00158 }
dimension_type Parma_Polyhedra_Library::Congruence::space_dimension | ( | ) | const [inline] |
Returns the dimension of the vector space enclosing *this
.
Definition at line 161 of file Congruence.inlines.hh.
References Parma_Polyhedra_Library::Row::size().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_congruence(), Parma_Polyhedra_Library::Octagonal_Shape< T >::add_congruence(), Parma_Polyhedra_Library::Grid::add_congruence(), Parma_Polyhedra_Library::Box< ITV >::add_congruence(), Parma_Polyhedra_Library::BD_Shape< T >::add_congruence(), Parma_Polyhedra_Library::Grid::add_congruence_no_check(), Parma_Polyhedra_Library::Box< ITV >::add_congruence_no_check(), coefficient(), Parma_Polyhedra_Library::Constraint::Constraint(), Parma_Polyhedra_Library::extract_interval_congruence(), is_inconsistent(), is_tautological(), operator<<(), Parma_Polyhedra_Library::Octagonal_Shape< T >::refine_no_check(), Parma_Polyhedra_Library::Box< ITV >::refine_no_check(), Parma_Polyhedra_Library::BD_Shape< T >::refine_no_check(), Parma_Polyhedra_Library::Polyhedron::refine_with_congruence(), Parma_Polyhedra_Library::Octagonal_Shape< T >::refine_with_congruence(), Parma_Polyhedra_Library::Box< ITV >::refine_with_congruence(), Parma_Polyhedra_Library::BD_Shape< T >::refine_with_congruence(), Parma_Polyhedra_Library::Polyhedron::relation_with(), Parma_Polyhedra_Library::Octagonal_Shape< T >::relation_with(), Parma_Polyhedra_Library::Grid::relation_with(), Parma_Polyhedra_Library::Box< ITV >::relation_with(), Parma_Polyhedra_Library::BD_Shape< T >::relation_with(), Parma_Polyhedra_Library::Polyhedron::throw_dimension_incompatible(), Parma_Polyhedra_Library::Octagonal_Shape< T >::throw_dimension_incompatible(), Parma_Polyhedra_Library::Grid::throw_dimension_incompatible(), throw_dimension_incompatible(), Parma_Polyhedra_Library::Box< ITV >::throw_dimension_incompatible(), and Parma_Polyhedra_Library::BD_Shape< T >::throw_dimension_incompatible().
00161 { 00162 return size() - 2; 00163 }
Coefficient_traits::const_reference Parma_Polyhedra_Library::Congruence::coefficient | ( | Variable | v | ) | const [inline] |
Returns the coefficient of v
in *this
.
std::invalid_argument | thrown if the index of v is greater than or equal to the space dimension of *this . |
Definition at line 166 of file Congruence.inlines.hh.
References Parma_Polyhedra_Library::Variable::id(), space_dimension(), Parma_Polyhedra_Library::Variable::space_dimension(), and throw_dimension_incompatible().
Referenced by Parma_Polyhedra_Library::Box< ITV >::add_congruence_no_check(), Parma_Polyhedra_Library::Grid::expand_space_dimension(), Parma_Polyhedra_Library::extract_interval_congruence(), operator<<(), Parma_Polyhedra_Library::Box< ITV >::refine_no_check(), Parma_Polyhedra_Library::Polyhedron::relation_with(), Parma_Polyhedra_Library::Octagonal_Shape< T >::relation_with(), Parma_Polyhedra_Library::Box< ITV >::relation_with(), and Parma_Polyhedra_Library::BD_Shape< T >::relation_with().
00166 { 00167 if (v.space_dimension() > space_dimension()) 00168 throw_dimension_incompatible("coefficient(v)", "v", v); 00169 return (*this)[v.id()+1]; 00170 }
Coefficient_traits::const_reference Parma_Polyhedra_Library::Congruence::inhomogeneous_term | ( | ) | const [inline] |
Returns the inhomogeneous term of *this
.
Definition at line 173 of file Congruence.inlines.hh.
Referenced by Parma_Polyhedra_Library::Box< ITV >::add_congruence_no_check(), Parma_Polyhedra_Library::Pointset_Powerset< PS >::approximate_partition_aux(), Parma_Polyhedra_Library::Grid::expand_space_dimension(), is_inconsistent(), is_tautological(), operator<<(), Parma_Polyhedra_Library::Box< ITV >::refine_no_check(), Parma_Polyhedra_Library::Polyhedron::relation_with(), Parma_Polyhedra_Library::Octagonal_Shape< T >::relation_with(), Parma_Polyhedra_Library::Grid::relation_with(), Parma_Polyhedra_Library::Box< ITV >::relation_with(), Parma_Polyhedra_Library::BD_Shape< T >::relation_with(), and Parma_Polyhedra_Library::Grid::simplify().
Coefficient_traits::const_reference Parma_Polyhedra_Library::Congruence::modulus | ( | ) | const [inline] |
Returns a const reference to the modulus of *this
.
Definition at line 178 of file Congruence.inlines.hh.
References Parma_Polyhedra_Library::Row::size().
Referenced by Parma_Polyhedra_Library::Pointset_Powerset< PS >::approximate_partition_aux(), Parma_Polyhedra_Library::Grid::difference_assign(), Parma_Polyhedra_Library::Grid::expand_space_dimension(), is_equal_at_dimension(), is_equality(), is_inconsistent(), is_proper_congruence(), is_tautological(), normalize(), Parma_Polyhedra_Library::Congruence_System::normalize_moduli(), OK(), operator<<(), Parma_Polyhedra_Library::Grid::reduce_congruence_with_equality(), Parma_Polyhedra_Library::Grid::reduce_equality_with_equality(), Parma_Polyhedra_Library::Polyhedron::relation_with(), Parma_Polyhedra_Library::Octagonal_Shape< T >::relation_with(), Parma_Polyhedra_Library::Grid::relation_with(), Parma_Polyhedra_Library::Box< ITV >::relation_with(), Parma_Polyhedra_Library::BD_Shape< T >::relation_with(), Parma_Polyhedra_Library::Congruence_System::satisfies_all_congruences(), and Parma_Polyhedra_Library::Grid::simplify().
Congruence & Parma_Polyhedra_Library::Congruence::operator/= | ( | Coefficient_traits::const_reference | k | ) | [inline] |
Multiplies k
into the modulus of *this
.
If called with *this
representing the congruence , then it returns with *this representing the congruence
.
Definition at line 129 of file Congruence.inlines.hh.
References Parma_Polyhedra_Library::Row::size().
00129 { 00130 if (k >= 0) 00131 (*this)[size()-1] *= k; 00132 else 00133 (*this)[size()-1] *= -k; 00134 return *this; 00135 }
bool Parma_Polyhedra_Library::Congruence::is_tautological | ( | ) | const |
Returns true
if and only if *this
is a tautology (i.e., an always true congruence).
A tautological congruence has one the following two forms:
Definition at line 182 of file Congruence.cc.
References inhomogeneous_term(), is_equality(), is_proper_congruence(), modulus(), and space_dimension().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_congruence(), Parma_Polyhedra_Library::Octagonal_Shape< T >::add_congruence(), Parma_Polyhedra_Library::BD_Shape< T >::add_congruence(), Parma_Polyhedra_Library::Box< ITV >::add_congruence_no_check(), Parma_Polyhedra_Library::Polyhedron::add_congruences(), and Parma_Polyhedra_Library::Polyhedron::refine_with_congruence().
00182 { 00183 if ((is_equality() && inhomogeneous_term() == 0) 00184 || (is_proper_congruence() 00185 && (inhomogeneous_term() % modulus() == 0))) { 00186 for (unsigned i = space_dimension(); i > 0; --i) 00187 if (operator[](i) != 0) 00188 return false; 00189 return true; 00190 } 00191 return false; 00192 }
bool Parma_Polyhedra_Library::Congruence::is_inconsistent | ( | ) | const |
Returns true
if and only if *this
is inconsistent (i.e., an always false congruence).
An inconsistent congruence has one of the following two forms:
Definition at line 195 of file Congruence.cc.
References inhomogeneous_term(), is_proper_congruence(), modulus(), and space_dimension().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_congruence(), Parma_Polyhedra_Library::Octagonal_Shape< T >::add_congruence(), Parma_Polyhedra_Library::BD_Shape< T >::add_congruence(), Parma_Polyhedra_Library::Grid::add_congruence_no_check(), Parma_Polyhedra_Library::Box< ITV >::add_congruence_no_check(), Parma_Polyhedra_Library::Polyhedron::add_congruences(), Parma_Polyhedra_Library::Octagonal_Shape< T >::refine_no_check(), Parma_Polyhedra_Library::Box< ITV >::refine_no_check(), Parma_Polyhedra_Library::BD_Shape< T >::refine_no_check(), Parma_Polyhedra_Library::Polyhedron::relation_with(), Parma_Polyhedra_Library::Octagonal_Shape< T >::relation_with(), Parma_Polyhedra_Library::Grid::relation_with(), Parma_Polyhedra_Library::Box< ITV >::relation_with(), and Parma_Polyhedra_Library::BD_Shape< T >::relation_with().
00195 { 00196 if (inhomogeneous_term() == 0 00197 || (is_proper_congruence() 00198 && ((inhomogeneous_term() % modulus()) == 0))) 00199 return false; 00200 for (unsigned i = space_dimension(); i > 0; --i) 00201 if (operator[](i) != 0) 00202 return false; 00203 return true; 00204 }
bool Parma_Polyhedra_Library::Congruence::is_proper_congruence | ( | ) | const [inline] |
Returns true
if the modulus is greater than zero.
A congruence with a modulus of 0 is a linear equality.
Definition at line 184 of file Congruence.inlines.hh.
References modulus().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_congruence(), Parma_Polyhedra_Library::Octagonal_Shape< T >::add_congruence(), Parma_Polyhedra_Library::BD_Shape< T >::add_congruence(), Parma_Polyhedra_Library::Box< ITV >::add_congruence_no_check(), Parma_Polyhedra_Library::Polyhedron::add_congruences(), Parma_Polyhedra_Library::Grid::difference_assign(), is_inconsistent(), is_tautological(), Parma_Polyhedra_Library::Grid::multiply_grid(), Parma_Polyhedra_Library::Congruence_System::num_proper_congruences(), operator<<(), Parma_Polyhedra_Library::Grid::reduce_congruence_with_equality(), Parma_Polyhedra_Library::Octagonal_Shape< T >::refine_no_check(), Parma_Polyhedra_Library::Box< ITV >::refine_no_check(), Parma_Polyhedra_Library::BD_Shape< T >::refine_no_check(), Parma_Polyhedra_Library::Grid::relation_with(), and Parma_Polyhedra_Library::Grid::simplify().
00184 { 00185 return modulus() > 0; 00186 }
bool Parma_Polyhedra_Library::Congruence::is_equality | ( | ) | const [inline] |
Returns true
if *this
is an equality.
A modulus of zero denotes a linear equality.
Definition at line 189 of file Congruence.inlines.hh.
References modulus().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_congruence(), Parma_Polyhedra_Library::Octagonal_Shape< T >::add_congruence(), Parma_Polyhedra_Library::BD_Shape< T >::add_congruence(), Parma_Polyhedra_Library::Box< ITV >::add_congruence_no_check(), Parma_Polyhedra_Library::Polyhedron::add_congruences(), Parma_Polyhedra_Library::extract_interval_congruence(), is_tautological(), Parma_Polyhedra_Library::Grid::multiply_grid(), Parma_Polyhedra_Library::Octagonal_Shape< T >::refine_no_check(), Parma_Polyhedra_Library::Box< ITV >::refine_no_check(), Parma_Polyhedra_Library::BD_Shape< T >::refine_no_check(), Parma_Polyhedra_Library::Polyhedron::refine_with_congruence(), Parma_Polyhedra_Library::Polyhedron::relation_with(), Parma_Polyhedra_Library::Octagonal_Shape< T >::relation_with(), Parma_Polyhedra_Library::Grid::relation_with(), Parma_Polyhedra_Library::Box< ITV >::relation_with(), Parma_Polyhedra_Library::BD_Shape< T >::relation_with(), Parma_Polyhedra_Library::Congruence_System::satisfies_all_congruences(), and Parma_Polyhedra_Library::Grid::simplify().
00189 { 00190 return modulus() == 0; 00191 }
bool Parma_Polyhedra_Library::Congruence::is_equal_at_dimension | ( | dimension_type | dim, | |
const Congruence & | cg | |||
) | const [inline] |
Returns true
if *this
is equal to cg
in dimension dim
.
Definition at line 194 of file Congruence.inlines.hh.
References modulus(), and Parma_Polyhedra_Library::Row::operator[]().
Referenced by Parma_Polyhedra_Library::Grid::select_wider_congruences().
00195 { 00196 return operator[](dim) * cg.modulus() == cg[dim] * modulus(); 00197 }
void Parma_Polyhedra_Library::Congruence::initialize | ( | ) | [static] |
Initializes the class.
Definition at line 274 of file Congruence.cc.
References Congruence(), Parma_Polyhedra_Library::Linear_Expression::zero(), zero_dim_false_p, and zero_dim_integrality_p.
00274 { 00275 assert(zero_dim_false_p == 0); 00276 zero_dim_false_p 00277 = new Congruence((Linear_Expression::zero() %= Coefficient(-1)) / 0); 00278 00279 assert(zero_dim_integrality_p == 0); 00280 zero_dim_integrality_p 00281 = new Congruence(Linear_Expression::zero() %= Coefficient(-1)); 00282 }
void Parma_Polyhedra_Library::Congruence::finalize | ( | ) | [static] |
Finalizes the class.
Definition at line 285 of file Congruence.cc.
References zero_dim_false_p, and zero_dim_integrality_p.
00285 { 00286 assert(zero_dim_false_p != 0); 00287 delete zero_dim_false_p; 00288 zero_dim_false_p = 0; 00289 00290 assert(zero_dim_integrality_p != 0); 00291 delete zero_dim_integrality_p; 00292 zero_dim_integrality_p = 0; 00293 }
const Congruence & Parma_Polyhedra_Library::Congruence::zero_dim_integrality | ( | ) | [inline, static] |
Returns a reference to the true (zero-dimension space) congruence , also known as the integrality congruence.
Definition at line 106 of file Congruence.inlines.hh.
References zero_dim_integrality_p.
Referenced by Parma_Polyhedra_Library::Grid::construct().
00106 { 00107 return *zero_dim_integrality_p; 00108 }
const Congruence & Parma_Polyhedra_Library::Congruence::zero_dim_false | ( | ) | [inline, static] |
Returns a reference to the false (zero-dimension space) congruence .
Definition at line 111 of file Congruence.inlines.hh.
References zero_dim_false_p.
Referenced by Parma_Polyhedra_Library::Grid::construct(), Parma_Polyhedra_Library::Grid::Grid(), Parma_Polyhedra_Library::Congruence_System::initialize(), Parma_Polyhedra_Library::Grid::remove_higher_space_dimensions(), and Parma_Polyhedra_Library::Grid::set_empty().
00111 { 00112 return *zero_dim_false_p; 00113 }
PPL::Congruence Parma_Polyhedra_Library::Congruence::create | ( | const Linear_Expression & | e1, | |
const Linear_Expression & | e2 | |||
) | [static] |
Returns the congruence .
Definition at line 110 of file Congruence.cc.
References Parma_Polyhedra_Library::Linear_Expression::space_dimension().
Referenced by operator%=().
00111 { 00112 // Ensure that diff is created with capacity for the modulus. 00113 dimension_type dim, e1_dim, e2_dim; 00114 e1_dim = e1.space_dimension(); 00115 e2_dim = e2.space_dimension(); 00116 if (e1_dim > e2_dim) 00117 dim = e1_dim; 00118 else 00119 dim = e2_dim; 00120 Linear_Expression diff(e1_dim > e2_dim ? e1 : e2, 00121 dim + 2); 00122 diff -= (e1_dim > e2_dim ? e2 : e1); 00123 Congruence cg(diff, 1); 00124 return cg; 00125 }
Congruence Parma_Polyhedra_Library::Congruence::create | ( | const Linear_Expression & | e, | |
Coefficient_traits::const_reference | n | |||
) | [inline, static] |
Returns the congruence .
Definition at line 67 of file Congruence.inlines.hh.
References Parma_Polyhedra_Library::Linear_Expression::space_dimension().
00068 { 00069 // Ensure that diff has capacity for the modulus. 00070 Linear_Expression diff(e, e.space_dimension() + 2); 00071 diff -= n; 00072 Congruence cg(diff, 1); 00073 return cg; 00074 }
Congruence Parma_Polyhedra_Library::Congruence::create | ( | Coefficient_traits::const_reference | n, | |
const Linear_Expression & | e | |||
) | [inline, static] |
Returns the congruence .
Definition at line 77 of file Congruence.inlines.hh.
References Parma_Polyhedra_Library::Linear_Expression::space_dimension().
00078 { 00079 // Ensure that diff has capacity for the modulus. 00080 Linear_Expression diff(e, e.space_dimension() + 2); 00081 diff -= n; 00082 Congruence cg(diff, 1); 00083 return cg; 00084 }
memory_size_type Parma_Polyhedra_Library::Congruence::total_memory_in_bytes | ( | ) | const [inline] |
Returns a lower bound to the total size in bytes of the memory occupied by *this
.
Reimplemented from Parma_Polyhedra_Library::Row.
Definition at line 216 of file Congruence.inlines.hh.
References Parma_Polyhedra_Library::total_memory_in_bytes().
00216 { 00217 return Row::total_memory_in_bytes(); 00218 }
memory_size_type Parma_Polyhedra_Library::Congruence::external_memory_in_bytes | ( | ) | const [inline] |
Returns the size in bytes of the memory managed by *this
.
Reimplemented from Parma_Polyhedra_Library::Row.
Definition at line 211 of file Congruence.inlines.hh.
References Parma_Polyhedra_Library::external_memory_in_bytes().
00211 { 00212 return Row::external_memory_in_bytes(); 00213 }
void Parma_Polyhedra_Library::Congruence::ascii_dump | ( | ) | const |
Writes to std::cerr
an ASCII representation of *this
.
Reimplemented from Parma_Polyhedra_Library::Row.
void Parma_Polyhedra_Library::Congruence::ascii_dump | ( | std::ostream & | s | ) | const |
Writes to s
an ASCII representation of *this
.
Reimplemented from Parma_Polyhedra_Library::Row.
Definition at line 207 of file Congruence.cc.
References Parma_Polyhedra_Library::Row::size().
00207 { 00208 const Row& x = *this; 00209 const dimension_type x_size = x.size(); 00210 s << "size " << x_size << " "; 00211 if (x_size > 0) { 00212 for (dimension_type i = 0; i < x_size - 1; ++i) 00213 s << x[i] << ' '; 00214 s << "m " << x[x_size - 1]; 00215 } 00216 s << std::endl; 00217 }
void Parma_Polyhedra_Library::Congruence::print | ( | ) | const |
bool Parma_Polyhedra_Library::Congruence::ascii_load | ( | std::istream & | s | ) |
Loads from s
an ASCII representation of the internal representation of *this
.
Reimplemented from Parma_Polyhedra_Library::Row.
Definition at line 222 of file Congruence.cc.
References Parma_Polyhedra_Library::Row::shrink(), Parma_Polyhedra_Library::Row::size(), and Parma_Polyhedra_Library::Row::swap().
00222 { 00223 std::string str; 00224 if (!(s >> str) || str != "size") 00225 return false; 00226 dimension_type new_size; 00227 if (!(s >> new_size)) 00228 return false; 00229 00230 Row& x = *this; 00231 const dimension_type old_size = x.size(); 00232 if (new_size < old_size) 00233 x.shrink(new_size); 00234 else if (new_size > old_size) { 00235 Row y(new_size, Row::Flags()); 00236 x.swap(y); 00237 } 00238 00239 if (new_size > 0) { 00240 for (dimension_type col = 0; col < new_size - 1; ++col) 00241 if (!(s >> x[col])) 00242 return false; 00243 if (!(s >> str) || (str.compare("m") != 0)) 00244 return false; 00245 if (!(s >> x[new_size-1])) 00246 return false; 00247 } 00248 return true; 00249 }
bool Parma_Polyhedra_Library::Congruence::OK | ( | ) | const |
Checks if all the invariants are satisfied.
Reimplemented from Parma_Polyhedra_Library::Row.
Definition at line 252 of file Congruence.cc.
References modulus(), and Parma_Polyhedra_Library::Row::OK().
Referenced by Parma_Polyhedra_Library::Congruence_System::OK().
00252 { 00253 // A Congruence must be a valid Row. 00254 if (!Row::OK()) 00255 return false; 00256 00257 // Modulus check. 00258 if (modulus() < 0) { 00259 #ifndef NDEBUG 00260 std::cerr << "Congruence has a negative modulus " << modulus() << "." 00261 << std::endl; 00262 #endif 00263 return false; 00264 } 00265 00266 // All tests passed. 00267 return true; 00268 }
void Parma_Polyhedra_Library::Congruence::sign_normalize | ( | ) | [protected] |
Normalizes the signs.
The signs of the coefficients and the inhomogeneous term are normalized, leaving the first non-zero homogeneous coefficient positive.
Definition at line 61 of file Congruence.cc.
References Parma_Polyhedra_Library::neg_assign(), and Parma_Polyhedra_Library::Row::size().
Referenced by normalize().
00061 { 00062 Row& x = *this; 00063 const dimension_type sz = x.size() - 1; 00064 // `first_non_zero' indicates the index of the first 00065 // coefficient of the row different from zero, disregarding 00066 // the very first coefficient (inhomogeneous term). 00067 dimension_type first_non_zero; 00068 for (first_non_zero = 1; first_non_zero < sz; ++first_non_zero) 00069 if (x[first_non_zero] != 0) 00070 break; 00071 if (first_non_zero < sz) 00072 // If the first non-zero coefficient of the row is negative, 00073 // negate all the coefficients and the inhomogeneous term. 00074 if (x[first_non_zero] < 0) { 00075 for (dimension_type j = first_non_zero; j < sz; ++j) 00076 neg_assign(x[j]); 00077 // Also negate the inhomogeneous term. 00078 neg_assign(x[0]); 00079 } 00080 }
void Parma_Polyhedra_Library::Congruence::normalize | ( | ) | [protected] |
Normalizes signs and the inhomogeneous term.
Applies sign_normalize, then reduces the inhomogeneous term to the smallest possible positive number.
Reimplemented from Parma_Polyhedra_Library::Row.
Definition at line 83 of file Congruence.cc.
References modulus(), sign_normalize(), and Parma_Polyhedra_Library::Row::size().
Referenced by strong_normalize().
00083 { 00084 sign_normalize(); 00085 00086 dimension_type sz = size(); 00087 if (sz == 0) 00088 return; 00089 00090 const Coefficient& mod = modulus(); 00091 if (mod == 0) 00092 return; 00093 00094 Coefficient& row_0 = (*this)[0]; 00095 // Factor the modulus out of the inhomogeneous term. 00096 row_0 %= mod; 00097 if (row_0 < 0) 00098 // Make inhomogeneous term positive. 00099 row_0 += mod; 00100 return; 00101 }
void Parma_Polyhedra_Library::Congruence::strong_normalize | ( | ) | [protected] |
Calls normalize, then divides out common factors.
Strongly normalized Congruences have equivalent semantics if and only if their syntaxes (as output by operator<<) are equal.
Definition at line 104 of file Congruence.cc.
References Parma_Polyhedra_Library::Row::normalize(), and normalize().
00104 { 00105 normalize(); 00106 Row::normalize(); 00107 }
void Parma_Polyhedra_Library::Congruence::set_is_equality | ( | ) | [inline, private] |
Marks this congruence as a linear equality.
Definition at line 200 of file Congruence.inlines.hh.
References Parma_Polyhedra_Library::Row::size().
Referenced by Parma_Polyhedra_Library::Grid::simplify().
00200 { 00201 (*this)[size()-1] = 0; 00202 }
void Parma_Polyhedra_Library::Congruence::negate | ( | dimension_type | start, | |
dimension_type | end | |||
) | [inline, private] |
Negates the elements from index start
to index end
.
Definition at line 205 of file Congruence.inlines.hh.
References Parma_Polyhedra_Library::neg_assign().
Referenced by Parma_Polyhedra_Library::Grid::simplify().
00205 { 00206 while (start <= end) 00207 neg_assign(operator[](start++)); 00208 }
void Parma_Polyhedra_Library::Congruence::swap | ( | Congruence & | y | ) | [inline, private] |
Swaps *this
with y
.
Definition at line 221 of file Congruence.inlines.hh.
References Parma_Polyhedra_Library::swap().
00221 { 00222 Row::swap(y); 00223 }
void Parma_Polyhedra_Library::Congruence::throw_invalid_argument | ( | const char * | method, | |
const char * | message | |||
) | const [private] |
Throws a std::invalid_argument
exception containing error message message
.
Definition at line 128 of file Congruence.cc.
Referenced by throw_dimension_incompatible().
00129 { 00130 std::ostringstream s; 00131 s << "PPL::Congruence::" << method << ":" << std::endl 00132 << message; 00133 throw std::invalid_argument(s.str()); 00134 }
void Parma_Polyhedra_Library::Congruence::throw_dimension_incompatible | ( | const char * | method, | |
const char * | v_name, | |||
Variable | v | |||
) | const [private] |
Throws a std::invalid_argument
exception containing the appropriate error message.
Definition at line 137 of file Congruence.cc.
References Parma_Polyhedra_Library::Variable::space_dimension(), space_dimension(), and throw_invalid_argument().
Referenced by coefficient().
00139 { 00140 std::ostringstream s; 00141 s << "this->space_dimension() == " << space_dimension() << ", " 00142 << v_name << ".space_dimension() == " << v.space_dimension() << "."; 00143 std::string str = s.str(); 00144 throw_invalid_argument(method, str.c_str()); 00145 }
friend class Parma_Polyhedra_Library::Scalar_Products [friend] |
Definition at line 465 of file Congruence.defs.hh.
friend class Parma_Polyhedra_Library::Constraint [friend] |
Definition at line 466 of file Congruence.defs.hh.
friend class Parma_Polyhedra_Library::Congruence_System [friend] |
Definition at line 467 of file Congruence.defs.hh.
friend class Parma_Polyhedra_Library::Congruence_System::const_iterator [friend] |
Definition at line 468 of file Congruence.defs.hh.
friend class Parma_Polyhedra_Library::Grid [friend] |
Definition at line 471 of file Congruence.defs.hh.
friend class Parma_Polyhedra_Library::Linear_Expression [friend] |
Definition at line 472 of file Congruence.defs.hh.
Congruence operator/ | ( | const Congruence & | cg, | |
Coefficient_traits::const_reference | k | |||
) | [friend] |
Returns a copy of cg
, multiplying k
into the copy's modulus.
If cg
represents the congruence , then the result represents the congruence
.
Definition at line 100 of file Congruence.inlines.hh.
00100 { 00101 Congruence ret(cg, k); 00102 return ret; 00103 }
Congruence operator/ | ( | const Constraint & | c, | |
Coefficient_traits::const_reference | m | |||
) | [friend] |
Creates a congruence from c
, with m
as the modulus.
Definition at line 123 of file Congruence.inlines.hh.
00123 { 00124 Congruence ret(c); 00125 return ret / m; 00126 }
bool operator== | ( | const Congruence & | x, | |
const Congruence & | y | |||
) | [friend] |
Returns true
if and only if x
and y
are equivalent.
Definition at line 139 of file Congruence.inlines.hh.
00139 { 00140 Congruence x_temp(x); 00141 Congruence y_temp(y); 00142 x_temp.strong_normalize(); 00143 y_temp.strong_normalize(); 00144 return static_cast<const Row&>(x_temp) == static_cast<const Row&>(y_temp); 00145 }
bool operator!= | ( | const Congruence & | x, | |
const Congruence & | y | |||
) | [friend] |
Returns false
if and only if x
and y
are equivalent.
Definition at line 149 of file Congruence.inlines.hh.
std::ostream & operator<< | ( | std::ostream & | s, | |
const Congruence_System & | cgs | |||
) | [friend] |
Output operator.
Writes true
if cgs
is empty. Otherwise, writes on s
the congruences of cgs
, all in one row and separated by ", ".
Definition at line 473 of file Congruence_System.cc.
00473 { 00474 Congruence_System::const_iterator i = cgs.begin(); 00475 const Congruence_System::const_iterator cgs_end = cgs.end(); 00476 if (i == cgs_end) 00477 return s << "true"; 00478 while (true) { 00479 Congruence cg = *i++; 00480 cg.strong_normalize(); 00481 s << cg; 00482 if (i == cgs_end) 00483 return s; 00484 s << ", "; 00485 } 00486 }
void swap | ( | Parma_Polyhedra_Library::Congruence & | x, | |
Parma_Polyhedra_Library::Congruence & | y | |||
) | [friend] |
Specializes std::swap
.
Definition at line 231 of file Congruence.inlines.hh.
00232 { 00233 x.swap(y); 00234 }
std::ostream & operator<< | ( | std::ostream & | s, | |
const Congruence & | c | |||
) | [related] |
Output operators.
Definition at line 149 of file Congruence.cc.
References coefficient(), Parma_Polyhedra_Library::Coefficient_zero(), inhomogeneous_term(), is_proper_congruence(), modulus(), Parma_Polyhedra_Library::neg_assign(), space_dimension(), and TEMP_INTEGER.
00149 { 00150 const dimension_type num_variables = c.space_dimension(); 00151 TEMP_INTEGER(cv); 00152 bool first = true; 00153 for (dimension_type v = 0; v < num_variables; ++v) { 00154 cv = c.coefficient(Variable(v)); 00155 if (cv != 0) { 00156 if (!first) { 00157 if (cv > 0) 00158 s << " + "; 00159 else { 00160 s << " - "; 00161 neg_assign(cv); 00162 } 00163 } 00164 else 00165 first = false; 00166 if (cv == -1) 00167 s << "-"; 00168 else if (cv != 1) 00169 s << cv << "*"; 00170 s << PPL::Variable(v); 00171 } 00172 } 00173 if (first) 00174 s << Coefficient_zero(); 00175 s << " = " << -c.inhomogeneous_term(); 00176 if (c.is_proper_congruence()) 00177 s << " (mod " << c.modulus() << ")"; 00178 return s; 00179 }
Congruence operator%= | ( | const Linear_Expression & | e1, | |
const Linear_Expression & | e2 | |||
) | [related] |
Returns the congruence .
Definition at line 88 of file Congruence.inlines.hh.
References create().
00088 { 00089 return Congruence::create(e1, e2); 00090 }
Congruence operator%= | ( | const Linear_Expression & | e, | |
Coefficient_traits::const_reference | n | |||
) | [related] |
Returns the congruence .
Definition at line 94 of file Congruence.inlines.hh.
References create().
00094 { 00095 return Congruence::create(e, n); 00096 }
const PPL::Congruence * Parma_Polyhedra_Library::Congruence::zero_dim_false_p = 0 [static, private] |
Holds (between class initialization and finalization) a pointer to the false (zero-dimension space) congruence .
Definition at line 380 of file Congruence.defs.hh.
Referenced by finalize(), initialize(), and zero_dim_false().
const PPL::Congruence * Parma_Polyhedra_Library::Congruence::zero_dim_integrality_p = 0 [static, private] |
Holds (between class initialization and finalization) a pointer to the true (zero-dimension space) congruence , also known as the integrality congruence.
Definition at line 387 of file Congruence.defs.hh.
Referenced by finalize(), initialize(), and zero_dim_integrality().