A system of generators. More...

#include <Generator_System_defs.hh>

Collaboration diagram for Parma_Polyhedra_Library::Generator_System:

[legend]

Public Types
typedef Generator	row_type

typedef Generator_System_const_iterator	const_iterator

Public Member Functions
	Generator_System (Representation r=default_representation)
	Default constructor: builds an empty system of generators. More...

	Generator_System (const Generator &g, Representation r=default_representation)
	Builds the singleton system containing only generator `g`. More...

	Generator_System (const Generator_System &gs)

	Generator_System (const Generator_System &gs, Representation r)
	Copy constructor with specified representation. More...

	~Generator_System ()
	Destructor. More...

Generator_System &	operator= (const Generator_System &y)
	Assignment operator. More...

Representation	representation () const
	Returns the current representation of *this. More...

void	set_representation (Representation r)
	Converts *this to the specified representation. More...

dimension_type	space_dimension () const
	Returns the dimension of the vector space enclosing `*this`. More...

void	set_space_dimension (dimension_type space_dim)
	Sets the space dimension of the rows in the system to `space_dim` . More...

void	clear ()
	Removes all the generators from the generator system and sets its space dimension to 0. More...

void	insert (const Generator &g)
	Inserts in `*this` a copy of the generator `g`, increasing the number of space dimensions if needed. More...

void	insert (Generator &g, Recycle_Input)
	Inserts in `*this` the generator `g`, stealing its contents and increasing the number of space dimensions if needed. More...

bool	empty () const
	Returns `true` if and only if `*this` has no generators. More...

const_iterator	begin () const
	Returns the const_iterator pointing to the first generator, if `*this` is not empty; otherwise, returns the past-the-end const_iterator. More...

const_iterator	end () const
	Returns the past-the-end const_iterator. More...

bool	OK () const
	Checks if all the invariants are satisfied. 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...

void	m_swap (Generator_System &y)
	Swaps `*this` with `y`. More...

Static Public Member Functions
static dimension_type	max_space_dimension ()
	Returns the maximum space dimension a Generator_System can handle. More...

static void	initialize ()
	Initializes the class. More...

static void	finalize ()
	Finalizes the class. More...

static const Generator_System &	zero_dim_univ ()
	Returns the singleton system containing only Generator::zero_dim_point(). More...

Static Public Attributes
static const Representation	default_representation = SPARSE

Private Member Functions
bool	has_no_rows () const

void	remove_space_dimensions (const Variables_Set &vars)
	Removes all the specified dimensions from the generator system. More...

void	shift_space_dimensions (Variable v, dimension_type n)

void	permute_space_dimensions (const std::vector< Variable > &cycle)
	Permutes the space dimensions of the matrix. More...

void	swap_space_dimensions (Variable v1, Variable v2)
	Swaps the coefficients of the variables `v1` and `v2` . More...

dimension_type	num_rows () const

void	add_universe_rows_and_space_dimensions (dimension_type n)
	Adds `n` rows and space dimensions to the system. More...

Topology	topology () const

dimension_type	first_pending_row () const
	Returns the index of the first pending row. More...

void	unset_pending_rows ()
	Sets the index to indicate that the system has no pending rows. More...

void	set_sorted (bool b)
	Sets the sortedness flag of the system to `b`. More...

bool	is_sorted () const
	Returns the value of the sortedness flag. More...

void	set_index_first_pending_row (dimension_type i)
	Sets the index of the first pending row to `i`. More...

bool	is_necessarily_closed () const
	Returns `true` if and only if the system topology is `NECESSARILY_CLOSED`. More...

void	assign_with_pending (const Generator_System &y)
	Full assignment operator: pending rows are copied as pending. More...

dimension_type	num_pending_rows () const
	Returns the number of rows that are in the pending part of the system. More...

void	sort_pending_and_remove_duplicates ()
	Sorts the pending rows and eliminates those that also occur in the non-pending part of the system. More...

void	sort_and_remove_with_sat (Bit_Matrix &sat)
	Sorts the system, removing duplicates, keeping the saturation matrix consistent. More...

void	sort_rows ()
	Sorts the non-pending rows (in growing order) and eliminates duplicated ones. More...

bool	check_sorted () const
	Returns `true` if and only if `*this` is sorted, without checking for duplicates. More...

dimension_type	num_lines_or_equalities () const
	Returns the number of rows in the system that represent either lines or equalities. More...

void	remove_row (dimension_type i, bool keep_sorted=false)
	Makes the system shrink by removing its i-th row. More...

void	remove_rows (dimension_type first, dimension_type last, bool keep_sorted=false)
	Makes the system shrink by removing the rows in [first,last). More...

void	remove_rows (const std::vector< dimension_type > &indexes)

void	remove_trailing_rows (dimension_type n)
	Makes the system shrink by removing its `n` trailing rows. More...

dimension_type	gauss (dimension_type n_lines_or_equalities)
	Minimizes the subsystem of equations contained in `*this`. More...

void	back_substitute (dimension_type n_lines_or_equalities)
	Back-substitutes the coefficients to reduce the complexity of the system. More...

void	strong_normalize ()
	Strongly normalizes the system. More...

void	merge_rows_assign (const Generator_System &y)
	Assigns to `*this` the result of merging its rows with those of `y`, obtaining a sorted system. More...

void	insert (const Generator_System &y)
	Adds to `*this` a copy of the rows of `y`. More...

void	insert_pending (const Generator_System &r)
	Adds a copy of the rows of `y' to the pending part of `*this'. More...

	Generator_System (Topology topol, Representation r=default_representation)
	Builds an empty system of generators having the specified topology. More...

	Generator_System (Topology topol, dimension_type space_dim, Representation r=default_representation)
	Builds a system of rays/points on a `space_dim` dimensional space. If `topol` is `NOT_NECESSARILY_CLOSED` the $\epsilon$ dimension is added. More...

bool	adjust_topology_and_space_dimension (Topology new_topology, dimension_type new_space_dim)
	Adjusts `this` so that it matches the `new_topology` and `new_space_dim` (adding or removing columns if needed). Returns `false` if and only if `topol` is equal to `NECESSARILY_CLOSED` and `this` contains closure points. More...

void	add_corresponding_points ()
	For each unmatched closure point in `*this`, adds the corresponding point. More...

bool	has_points () const
	Returns `true` if and only if `*this` contains one or more points. More...

void	add_corresponding_closure_points ()
	For each unmatched point in `*this`, adds the corresponding closure point. More...

bool	has_closure_points () const
	Returns `true` if and only if `*this` contains one or more closure points. More...

void	convert_into_non_necessarily_closed ()

const Generator &	operator[] (dimension_type k) const
	Returns a constant reference to the `k-` th generator of the system. More...

Parma_Polyhedra_Library::Poly_Con_Relation	relation_with (const Constraint &c) const
	Returns the relations holding between the generator system and the constraint `c`. More...

bool	satisfied_by_all_generators (const Constraint &c) const
	Returns `true` if all the generators satisfy `c`. More...

bool	satisfied_by_all_generators_C (const Constraint &c) const
	Returns `true` if all the generators satisfy `c`. More...

bool	satisfied_by_all_generators_NNC (const Constraint &c) const
	Returns `true` if all the generators satisfy `c`. More...

void	affine_image (Variable v, const Linear_Expression &expr, Coefficient_traits::const_reference denominator)
	Assigns to a given variable an affine expression. More...

dimension_type	num_lines () const
	Returns the number of lines of the system. More...

dimension_type	num_rays () const
	Returns the number of rays of the system. More...

void	remove_invalid_lines_and_rays ()
	Removes all the invalid lines and rays. More...

void	simplify ()
	Applies Gaussian elimination and back-substitution so as to provide a partial simplification of the system of generators. More...

void	insert_pending (const Generator &g)
	Inserts in `*this` a copy of the generator `g`, increasing the number of space dimensions if needed. It is a pending generator. More...

void	insert_pending (Generator &g, Recycle_Input)
	Inserts in `*this` the generator `g`, stealing its contents and increasing the number of space dimensions if needed. It is a pending generator. More...

Private Attributes
Linear_System< Generator >	sys

Static Private Attributes
static const Generator_System *	zero_dim_univ_p = 0
	Holds (between class initialization and finalization) a pointer to the singleton system containing only Generator::zero_dim_point(). More...

Friends
class	Generator_System_const_iterator

class	Polyhedron

bool	operator== (const Generator_System &x, const Generator_System &y)

Related Functions
(Note that these are not member functions.)
std::ostream &	operator<< (std::ostream &s, const Generator_System &gs)

std::ostream &	operator<< (std::ostream &s, const Generator_System &gs)
	Output operator. More...

bool	operator== (const Generator_System &x, const Generator_System &y)
	Returns `true` if and only if `x` and `y` are identical. More...

bool	operator!= (const Generator_System &x, const Generator_System &y)
	Returns `true` if and only if `x` and `y` are different. More...

void	swap (Generator_System &x, Generator_System &y)

void	swap (Generator_System &x, Generator_System &y)

Detailed Description

A system of generators.

An object of the class Generator_System is a system of generators, i.e., a multiset of objects of the class Generator (lines, rays, points and closure points). When inserting generators in a system, space dimensions are automatically adjusted so that all the generators in the system are defined on the same vector space. A system of generators which is meant to define a non-empty polyhedron must include at least one point: the reason is that lines, rays and closure points need a supporting point (lines and rays only specify directions while closure points only specify points in the topological closure of the NNC polyhedron).

: In all the examples it is assumed that variables x and y are defined as follows:
Variable x(0);

Variable y(1);

Example 1: The following code defines the line having the same direction as the axis (i.e., the first Cartesian axis) in $\Rset^2$ :
Generator_System gs;

gs.insert(line(x + 0*y));

As said above, this system of generators corresponds to an empty polyhedron, because the line has no supporting point. To define a system of generators that does correspond to the axis, we can add the following code which inserts the origin of the space as a point:
gs.insert(point(0*x + 0*y));

Since space dimensions are automatically adjusted, the following code obtains the same effect:
gs.insert(point(0*x));

In contrast, if we had added the following code, we would have defined a line parallel to the axis through the point $(0, 1)^\transpose \in \Rset^2$ .
gs.insert(point(0*x + 1*y));

Example 2: The following code builds a ray having the same direction as the positive part of the axis in $\Rset^2$ :
Generator_System gs;

gs.insert(ray(x + 0*y));

To define a system of generators indeed corresponding to the set
$\bigl\{\, (x, 0)^\transpose \in \Rset^2 \bigm| x \geq 0 \,\bigr\},$
one just has to add the origin:
gs.insert(point(0*x + 0*y));

Example 3: The following code builds a system of generators having four points and corresponding to a square in $\Rset^2$ (the same as Example 1 for the system of constraints):
Generator_System gs;

gs.insert(point(0*x + 0*y));

gs.insert(point(0*x + 3*y));

gs.insert(point(3*x + 0*y));

gs.insert(point(3*x + 3*y));

Example 4: By using closure points, we can define the kernel (i.e., the largest open set included in a given set) of the square defined in the previous example. Note that a supporting point is needed and, for that purpose, any inner point could be considered.
Generator_System gs;

gs.insert(point(x + y));

gs.insert(closure_point(0*x + 0*y));

gs.insert(closure_point(0*x + 3*y));

gs.insert(closure_point(3*x + 0*y));

gs.insert(closure_point(3*x + 3*y));

Example 5: The following code builds a system of generators having two points and a ray, corresponding to a half-strip in $\Rset^2$ (the same as Example 2 for the system of constraints):
Generator_System gs;

gs.insert(point(0*x + 0*y));

gs.insert(point(0*x + 1*y));

gs.insert(ray(x - y));

Note: After inserting a multiset of generators in a generator system, there are no guarantees that an exact copy of them can be retrieved: in general, only an equivalent generator system will be available, where original generators may have been reordered, removed (if they are duplicate or redundant), etc.

Definition at line 188 of file Generator_System_defs.hh.

Member Typedef Documentation

typedef Generator_System_const_iterator Parma_Polyhedra_Library::Generator_System::const_iterator

Definition at line 258 of file Generator_System_defs.hh.

typedef Generator Parma_Polyhedra_Library::Generator_System::row_type

Definition at line 190 of file Generator_System_defs.hh.

Constructor & Destructor Documentation

Parma_Polyhedra_Library::Generator_System::Generator_System ( Representation r = default_representation )

inline

Default constructor: builds an empty system of generators.

Definition at line 32 of file Generator_System_inlines.hh.

33 : sys(NECESSARILY_CLOSED, r) {

34 }

Parma_Polyhedra_Library::Generator_System::sys

Linear_System< Generator > sys

Definition: Generator_System_defs.hh:651

Parma_Polyhedra_Library::NECESSARILY_CLOSED

Definition: Topology_types.hh:23

Parma_Polyhedra_Library::Generator_System::Generator_System	(	const Generator &	g,
		Representation	r = `default_representation`
	)

inlineexplicit

Builds the singleton system containing only generator g.

Definition at line 37 of file Generator_System_inlines.hh.

References sys.

   : sys(g.topology(), r) {
   sys.insert(g);
 }

Parma_Polyhedra_Library::Generator_System::Generator_System ( const Generator_System & gs )

inline

Ordinary copy constructor. The new Generator_System will have the same representation as `gs'.

Definition at line 43 of file Generator_System_inlines.hh.

44 : sys(gs.sys) {

45 }

Parma_Polyhedra_Library::Generator_System::sys

Linear_System< Generator > sys

Definition: Generator_System_defs.hh:651

Parma_Polyhedra_Library::Generator_System::Generator_System	(	const Generator_System &	gs,
		Representation	r
	)

inline

Copy constructor with specified representation.

Definition at line 48 of file Generator_System_inlines.hh.

50 : sys(gs.sys, r) {

51 }

Parma_Polyhedra_Library::Generator_System::sys

Linear_System< Generator > sys

Definition: Generator_System_defs.hh:651

Parma_Polyhedra_Library::Generator_System::~Generator_System ( )

inline

Destructor.

Definition at line 66 of file Generator_System_inlines.hh.

66 {

67 }

Parma_Polyhedra_Library::Generator_System::Generator_System	(	Topology	topol,
		Representation	r = `default_representation`
	)

inlineexplicitprivate

Builds an empty system of generators having the specified topology.

Definition at line 54 of file Generator_System_inlines.hh.

55 : sys(topol, r) {

56 }

Parma_Polyhedra_Library::Generator_System::sys

Linear_System< Generator > sys

Definition: Generator_System_defs.hh:651

Parma_Polyhedra_Library::Generator_System::Generator_System	(	Topology	topol,
		dimension_type	space_dim,
		Representation	r = `default_representation`
	)

inlineprivate

Builds a system of rays/points on a space_dim dimensional space. If topol is NOT_NECESSARILY_CLOSED the $\epsilon$ dimension is added.

Definition at line 59 of file Generator_System_inlines.hh.

62 : sys(topol, space_dim, r) {

63 }

Parma_Polyhedra_Library::Generator_System::sys

Linear_System< Generator > sys

Definition: Generator_System_defs.hh:651

Member Function Documentation

void Parma_Polyhedra_Library::Generator_System::add_corresponding_closure_points ( )

private

For each unmatched point in *this, adds the corresponding closure point.

It is assumed that the topology of *this is NOT_NECESSARILY_CLOSED.

Definition at line 85 of file Generator_System.cc.

References Parma_Polyhedra_Library::Generator::epsilon_coefficient(), Parma_Polyhedra_Library::Generator::expr, Parma_Polyhedra_Library::Linear_Expression::normalize(), Parma_Polyhedra_Library::Generator::set_epsilon_coefficient(), and sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), Parma_Polyhedra_Library::Polyhedron::Polyhedron(), and Parma_Polyhedra_Library::Polyhedron::positive_time_elapse_assign_impl().

                                                       {
   PPL_ASSERT(!sys.is_necessarily_closed());
   // NOTE: we always add (pending) rows at the end of the generator system.
   // Updating `index_first_pending', if needed, is done by the caller.
   Generator_System& gs = *this;
   const dimension_type n_rows = gs.sys.num_rows();
   for (dimension_type i = n_rows; i-- > 0; ) {
     const Generator& g = gs[i];
     if (g.epsilon_coefficient() > 0) {
       // `g' is a point: adding the closure point.
       Generator cp = g;
       cp.set_epsilon_coefficient(0);
       // Enforcing normalization.
       cp.expr.normalize();
       gs.insert_pending(cp, Recycle_Input());
     }
   }
   PPL_ASSERT(OK());
 }

void Parma_Polyhedra_Library::Generator_System::add_corresponding_points ( )

private

For each unmatched closure point in *this, adds the corresponding point.

It is assumed that the topology of *this is NOT_NECESSARILY_CLOSED.

Definition at line 111 of file Generator_System.cc.

References Parma_Polyhedra_Library::Generator::epsilon_coefficient(), Parma_Polyhedra_Library::Generator::expr, Parma_Polyhedra_Library::Linear_Expression::inhomogeneous_term(), Parma_Polyhedra_Library::Generator::is_line_or_ray(), Parma_Polyhedra_Library::Generator::set_epsilon_coefficient(), and sys.

                                               {
   PPL_ASSERT(!sys.is_necessarily_closed());
   // NOTE: we always add (pending) rows at the end of the generator system.
   // Updating `index_first_pending', if needed, is done by the caller.
   Generator_System& gs = *this;
   const dimension_type n_rows = gs.sys.num_rows();
   for (dimension_type i = 0; i < n_rows; ++i) {
     const Generator& g = gs[i];
     if (!g.is_line_or_ray() && g.epsilon_coefficient() == 0) {
       // `g' is a closure point: adding the point.
       // Note: normalization is preserved.
       Generator p = g;
       p.set_epsilon_coefficient(p.expr.inhomogeneous_term());
       gs.insert_pending(p, Recycle_Input());
     }
   }
   PPL_ASSERT(OK());
 }

void Parma_Polyhedra_Library::Generator_System::add_universe_rows_and_space_dimensions ( dimension_type n )

inlineprivate

Adds n rows and space dimensions to the system.

Parameters

n	The number of rows and space dimensions to be added: must be strictly positive.

Turns the system $M \in \Rset^r \times \Rset^c$ into the system $N \in \Rset^{r+n} \times \Rset^{c+n}$ such that $N = \bigl(\genfrac{}{}{0pt}{}{0}{M}\genfrac{}{}{0pt}{}{J}{o}\bigr)$ , where $J$ is the specular image of the $n \times n$ identity matrix.

Definition at line 155 of file Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::add_space_dimensions_and_embed().

                                                                          {
   sys.add_universe_rows_and_space_dimensions(n);
 }

bool Parma_Polyhedra_Library::Generator_System::adjust_topology_and_space_dimension	(	Topology	new_topology,
		dimension_type	new_space_dim
	)

private

Adjusts *this so that it matches the new_topology and new_space_dim (adding or removing columns if needed). Returns false if and only if topol is equal to NECESSARILY_CLOSED and *this contains closure points.

Definition at line 40 of file Generator_System.cc.

References convert_into_non_necessarily_closed(), has_closure_points(), Parma_Polyhedra_Library::NECESSARILY_CLOSED, OK(), space_dimension(), and sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), Parma_Polyhedra_Library::Polyhedron::generators(), and Parma_Polyhedra_Library::Polyhedron::Polyhedron().

                                                                         {
   PPL_ASSERT(space_dimension() <= new_space_dim);
 
   if (sys.topology() != new_topology) {
     if (new_topology == NECESSARILY_CLOSED) {
       // A NOT_NECESSARILY_CLOSED generator system
       // can be converted to a NECESSARILY_CLOSED one
       // only if it does not contain closure points.
       // This check has to be performed under the user viewpoint.
       if (has_closure_points()) {
         return false;
       }
       // For a correct implementation, we have to remove those
       // closure points that were matching a point (i.e., those
       // that are in the generator system, but are invisible to
       // the user).
       const Generator_System& gs = *this;
       for (dimension_type i = 0; i < sys.num_rows(); ) {
         if (gs[i].is_closure_point()) {
           sys.remove_row(i, false);
         }
         else {
           ++i;
         }
       }
       sys.set_necessarily_closed();
     }
     else {
       convert_into_non_necessarily_closed();
     }
   }
 
   sys.set_space_dimension(new_space_dim);
 
   // We successfully adjusted dimensions and topology.
   PPL_ASSERT(OK());
   return true;
 }

void Parma_Polyhedra_Library::Generator_System::affine_image	(	Variable	v,
		const Linear_Expression &	expr,
		Coefficient_traits::const_reference	denominator
	)

private

Assigns to a given variable an affine expression.

Parameters

v	The variable to which the affine transformation is assigned;
expr	The numerator of the affine transformation: $\sum_{i = 0}^{n - 1} a_i x_i + b$ ;
denominator	The denominator of the affine transformation.

We want to allow affine transformations (see the Introduction) having any rational coefficients. Since the coefficients of the constraints are integers we must also provide an integer denominator that will be used as denominator of the affine transformation. The denominator is required to be a positive integer.

The affine transformation assigns to each element of the column containing the coefficients of v the follow expression:

$\frac{\sum_{i = 0}^{n - 1} a_i x_i + b} {\mathrm{denominator}}.$

expr is a constant parameter and unaltered by this computation.

Definition at line 745 of file Generator_System.cc.

References Parma_Polyhedra_Library::Scalar_Products::assign(), Parma_Polyhedra_Library::Linear_Expression::coefficient(), Parma_Polyhedra_Library::Generator::expr, num_rows(), PPL_DIRTY_TEMP_COEFFICIENT, remove_invalid_lines_and_rays(), Parma_Polyhedra_Library::Linear_Expression::set_coefficient(), Parma_Polyhedra_Library::Variable::space_dimension(), space_dimension(), Parma_Polyhedra_Library::Linear_Expression::space_dimension(), and sys.

                                                               {
   Generator_System& x = *this;
   PPL_ASSERT(v.space_dimension() <= x.space_dimension());
   PPL_ASSERT(expr.space_dimension() <= x.space_dimension());
   PPL_ASSERT(denominator > 0);
 
   const dimension_type n_rows = x.sys.num_rows();
 
   // Compute the numerator of the affine transformation and assign it
   // to the column of `*this' indexed by `v'.
   PPL_DIRTY_TEMP_COEFFICIENT(numerator);
   for (dimension_type i = n_rows; i-- > 0; ) {
     Generator& row = sys.rows[i];
     Scalar_Products::assign(numerator, expr, row.expr);
     if (denominator != 1) {
       // Since we want integer elements in the matrix,
       // we multiply by `denominator' all the columns of `*this'
       // having an index different from `v'.
       // Note that this operation also modifies the coefficient of v, but
       // it will be overwritten by the set_coefficient() below.
       row.expr *= denominator;
     }
     row.expr.set_coefficient(v, numerator);
   }
 
   set_sorted(false);
 
   // If the mapping is not invertible we may have transformed
   // valid lines and rays into the origin of the space.
   const bool not_invertible = (v.space_dimension() > expr.space_dimension()
                                || expr.coefficient(v) == 0);
   if (not_invertible) {
     x.remove_invalid_lines_and_rays();
   }
 
   // TODO: Consider normalizing individual rows in the loop above.
   // Strong normalization also resets the sortedness flag.
   x.sys.strong_normalize();
 
 #ifndef NDEBUG
   // Make sure that the (remaining) generators are still OK after fiddling
   // with their internal data.
   for (dimension_type i = x.num_rows(); i-- > 0; ) {
     PPL_ASSERT(x.sys[i].OK());
   }
 #endif
 
   PPL_ASSERT(sys.OK());
 }

void Parma_Polyhedra_Library::Generator_System::ascii_dump ( std::ostream & s ) const

Writes to s an ASCII representation of *this.

Definition at line 798 of file Generator_System.cc.

                                                    {
   sys.ascii_dump(s);
 }

void Parma_Polyhedra_Library::Generator_System::ascii_dump ( ) const

Writes to std::cerr an ASCII representation of *this.

Referenced by Parma_Polyhedra_Library::Polyhedron::OK().

bool Parma_Polyhedra_Library::Generator_System::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.

Resizes the matrix of generators using the numbers of rows and columns read from s, then initializes the coordinates of each generator and its type reading the contents from s.

Definition at line 805 of file Generator_System.cc.

                                              {
   if (!sys.ascii_load(s)) {
     return false;
   }
 
   PPL_ASSERT(OK());
   return true;
 }

void Parma_Polyhedra_Library::Generator_System::assign_with_pending ( const Generator_System & y )

inlineprivate

Full assignment operator: pending rows are copied as pending.

Definition at line 195 of file Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::Polyhedron().

                                                                {
   sys.assign_with_pending(y.sys);
 }

void Parma_Polyhedra_Library::Generator_System::back_substitute ( dimension_type n_lines_or_equalities )

inlineprivate

Back-substitutes the coefficients to reduce the complexity of the system.

Takes an upper triangular system having n_lines_or_equalities rows. For each row, starting from the one having the minimum number of coefficients different from zero, computes the expression of an element as a function of the remaining ones and then substitutes this expression in all the other rows.

Definition at line 256 of file Generator_System_inlines.hh.

References sys.

                                                                       {
   sys.back_substitute(n_lines_or_equalities);
 }

Generator_System::const_iterator Parma_Polyhedra_Library::Generator_System::begin ( ) const

inline

Returns the const_iterator pointing to the first generator, if *this is not empty; otherwise, returns the past-the-end const_iterator.

Definition at line 366 of file Generator_System_inlines.hh.

References Parma_Polyhedra_Library::Generator_System_const_iterator::skip_forward(), and sys.

                               {
   const_iterator i(sys.begin(), *this);
   if (!sys.is_necessarily_closed()) {
     i.skip_forward();
   }
   return i;
 }

bool Parma_Polyhedra_Library::Generator_System::check_sorted ( ) const

inlineprivate

Returns true if and only if *this is sorted, without checking for duplicates.

Definition at line 220 of file Generator_System_inlines.hh.

References sys.

                                      {
   return sys.check_sorted();
 }

void Parma_Polyhedra_Library::Generator_System::clear ( )

inline

Removes all the generators from the generator system and sets its space dimension to 0.

Definition at line 116 of file Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_generators().

                         {
   sys.clear();
 }

void Parma_Polyhedra_Library::Generator_System::convert_into_non_necessarily_closed ( )

private

Converts this generator system into a non-necessarily closed generator system.

Definition at line 146 of file Generator_System.cc.

References Parma_Polyhedra_Library::Generator::expr, Parma_Polyhedra_Library::Linear_Expression::inhomogeneous_term(), Parma_Polyhedra_Library::Generator::is_line_or_ray(), and Parma_Polyhedra_Library::Generator::set_epsilon_coefficient().

Referenced by adjust_topology_and_space_dimension(), and Parma_Polyhedra_Library::Polyhedron::positive_time_elapse_assign_impl().

                                                          {
   // Padding the matrix with the column
   // corresponding to the epsilon coefficients:
   // all points must have epsilon coordinate equal to 1
   // (i.e., the epsilon coefficient is equal to the divisor);
   // rays and lines must have epsilon coefficient equal to 0.
   // Note: normalization is preserved.
   sys.set_not_necessarily_closed();
 
   for (dimension_type i = sys.rows.size(); i-- > 0; ) {
     Generator& gen = sys.rows[i];
     if (!gen.is_line_or_ray()) {
       gen.set_epsilon_coefficient(gen.expr.inhomogeneous_term());
     }
   }
 
   PPL_ASSERT(sys.OK());
 }

bool Parma_Polyhedra_Library::Generator_System::empty ( ) const

inline

Returns true if and only if *this has no generators.

Definition at line 356 of file Generator_System_inlines.hh.

References sys.

                               {
   return sys.has_no_rows();
 }

Generator_System::const_iterator Parma_Polyhedra_Library::Generator_System::end ( ) const

inline

Returns the past-the-end const_iterator.

Definition at line 375 of file Generator_System_inlines.hh.

References sys.

                             {
   const const_iterator i(sys.end(), *this);
   return i;
 }

memory_size_type Parma_Polyhedra_Library::Generator_System::external_memory_in_bytes ( ) const

inline

Returns the size in bytes of the memory managed by *this.

Definition at line 392 of file Generator_System_inlines.hh.

References sys.

Referenced by total_memory_in_bytes().

                                                  {
   return sys.external_memory_in_bytes();
 }

void Parma_Polyhedra_Library::Generator_System::finalize ( )

static

Finalizes the class.

Definition at line 845 of file Generator_System.cc.

Referenced by Parma_Polyhedra_Library::Init::~Init().

                               {
   PPL_ASSERT(zero_dim_univ_p != 0);
   delete zero_dim_univ_p;
   zero_dim_univ_p = 0;
 }

dimension_type Parma_Polyhedra_Library::Generator_System::first_pending_row ( ) const

inlineprivate

Returns the index of the first pending row.

Definition at line 165 of file Generator_System_inlines.hh.

References sys.

                                           {
   return sys.first_pending_row();
 }

dimension_type Parma_Polyhedra_Library::Generator_System::gauss ( dimension_type n_lines_or_equalities )

inlineprivate

Minimizes the subsystem of equations contained in *this.

This method works only on the equalities of the system: the system is required to be partially sorted, so that all the equalities are grouped at its top; it is assumed that the number of equalities is exactly n_lines_or_equalities. The method finds a minimal system for the equalities and returns its rank, i.e., the number of linearly independent equalities. The result is an upper triangular subsystem of equalities: for each equality, the pivot is chosen starting from the right-most columns.

Definition at line 251 of file Generator_System_inlines.hh.

References sys.

                                                             {
   return sys.gauss(n_lines_or_equalities);
 }

bool Parma_Polyhedra_Library::Generator_System::has_closure_points ( ) const

private

Returns true if and only if *this contains one or more closure points.

Note: the check for the presence of closure points is done under the point of view of the user. Namely, we scan the generator system using high-level iterators, so that closure points that are matching the corresponding points will be disregarded.

Definition at line 131 of file Generator_System.cc.

Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), and adjust_topology_and_space_dimension().

                                               {
   if (sys.is_necessarily_closed()) {
     return false;
   }
   // Adopt the point of view of the user.
   for (Generator_System::const_iterator i = begin(),
          this_end = end(); i != this_end; ++i) {
     if (i->is_closure_point()) {
       return true;
     }
   }
   return false;
 }

bool Parma_Polyhedra_Library::Generator_System::has_no_rows ( ) const

inlineprivate

Definition at line 361 of file Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), Parma_Polyhedra_Library::Polyhedron::BHRZ03_evolving_rays(), Parma_Polyhedra_Library::Polyhedron::map_space_dimensions(), and Parma_Polyhedra_Library::Polyhedron::Polyhedron().

                                     {
   return sys.has_no_rows();
 }

bool Parma_Polyhedra_Library::Generator_System::has_points ( ) const

private

Returns true if and only if *this contains one or more points.

Definition at line 166 of file Generator_System.cc.

Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), and Parma_Polyhedra_Library::Polyhedron::Polyhedron().

                                       {
   const Generator_System& gs = *this;
   // Avoiding the repeated tests on topology.
   if (sys.is_necessarily_closed()) {
     for (dimension_type i = sys.num_rows(); i-- > 0; ) {
       if (!gs[i].is_line_or_ray()) {
         return true;
       }
     }
   }
   else {
     // !is_necessarily_closed()
     for (dimension_type i = sys.num_rows(); i-- > 0; ) {
       if (gs[i].epsilon_coefficient() != 0) {
         return true;
       }
     }
   }
   return false;
 }

void Parma_Polyhedra_Library::Generator_System::initialize ( )

static

Initializes the class.

Definition at line 838 of file Generator_System.cc.

References Parma_Polyhedra_Library::Generator::zero_dim_point().

Referenced by Parma_Polyhedra_Library::Init::Init().

                                 {
   PPL_ASSERT(zero_dim_univ_p == 0);
   zero_dim_univ_p
     = new Generator_System(Generator::zero_dim_point());
 }

void Parma_Polyhedra_Library::Generator_System::insert ( const Generator & g )

Inserts in *this a copy of the generator g, increasing the number of space dimensions if needed.

Definition at line 206 of file Generator_System.cc.

                                               {
   Generator tmp = g;
   insert(tmp, Recycle_Input());
 }

void Parma_Polyhedra_Library::Generator_System::insert	(	Generator &	g,
		Recycle_Input
	)

Inserts in *this the generator g, stealing its contents and increasing the number of space dimensions if needed.

Definition at line 218 of file Generator_System.cc.

References Parma_Polyhedra_Library::Generator::expr, Parma_Polyhedra_Library::Linear_Expression::inhomogeneous_term(), Parma_Polyhedra_Library::Generator::is_line_or_ray(), Parma_Polyhedra_Library::Generator::set_epsilon_coefficient(), Parma_Polyhedra_Library::Generator::set_not_necessarily_closed(), Parma_Polyhedra_Library::Generator::set_space_dimension(), Parma_Polyhedra_Library::Generator::space_dimension(), and Parma_Polyhedra_Library::Generator::topology().

                                                        {
   // We are sure that the matrix has no pending rows
   // and that the new row is not a pending generator.
   PPL_ASSERT(sys.num_pending_rows() == 0);
   if (sys.topology() == g.topology()) {
     sys.insert(g, Recycle_Input());
   }
   else {
     // `*this' and `g' have different topologies.
     if (sys.is_necessarily_closed()) {
       convert_into_non_necessarily_closed();
       // Inserting the new generator.
       sys.insert(g, Recycle_Input());
     }
     else {
       // The generator system is NOT necessarily closed:
       // copy the generator, adding the missing dimensions
       // and the epsilon coefficient.
       const dimension_type new_space_dim = std::max(g.space_dimension(),
                                                     space_dimension());
       g.set_not_necessarily_closed();
       g.set_space_dimension(new_space_dim);
       // If it was a point, set the epsilon coordinate to 1
       // (i.e., set the coefficient equal to the divisor).
       // Note: normalization is preserved.
       if (!g.is_line_or_ray()) {
         g.set_epsilon_coefficient(g.expr.inhomogeneous_term());
       }
       // Inserting the new generator.
       sys.insert(g, Recycle_Input());
     }
   }
   PPL_ASSERT(OK());
 }

void Parma_Polyhedra_Library::Generator_System::insert ( const Generator_System & y )

inlineprivate

Adds to *this a copy of the rows of y.

It is assumed that *this has no pending rows.

Definition at line 271 of file Generator_System_inlines.hh.

References sys.

                                                   {
   sys.insert(y.sys);
 }

void Parma_Polyhedra_Library::Generator_System::insert_pending ( const Generator_System & r )

inlineprivate

Adds a copy of the rows of `y' to the pending part of `*this'.

Definition at line 276 of file Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::poly_hull_assign(), and Parma_Polyhedra_Library::Polyhedron::time_elapse_assign().

                                                           {
   sys.insert_pending(r.sys);
 }

void Parma_Polyhedra_Library::Generator_System::insert_pending ( const Generator & g )

private

Inserts in *this a copy of the generator g, increasing the number of space dimensions if needed. It is a pending generator.

Definition at line 212 of file Generator_System.cc.

                                                       {
   Generator tmp = g;
   insert_pending(tmp, Recycle_Input());
 }

void Parma_Polyhedra_Library::Generator_System::insert_pending	(	Generator &	g,
		Recycle_Input
	)

private

Inserts in *this the generator g, stealing its contents and increasing the number of space dimensions if needed. It is a pending generator.

Definition at line 254 of file Generator_System.cc.

                                                                {
   if (sys.topology() == g.topology()) {
     sys.insert_pending(g, Recycle_Input());
   }
   else {
     // `*this' and `g' have different topologies.
     if (sys.is_necessarily_closed()) {
       convert_into_non_necessarily_closed();
 
       // Inserting the new generator.
       sys.insert_pending(g, Recycle_Input());
     }
     else {
       // The generator system is NOT necessarily closed:
       // copy the generator, adding the missing dimensions
       // and the epsilon coefficient.
       const dimension_type new_space_dim = std::max(g.space_dimension(),
                                                     space_dimension());
       g.set_topology(NOT_NECESSARILY_CLOSED);
       g.set_space_dimension(new_space_dim);
       // If it was a point, set the epsilon coordinate to 1
       // (i.e., set the coefficient equal to the divisor).
       // Note: normalization is preserved.
       if (!g.is_line_or_ray()) {
         g.set_epsilon_coefficient(g.expr.inhomogeneous_term());
       }
       // Inserting the new generator.
       sys.insert_pending(g, Recycle_Input());
     }
   }
   PPL_ASSERT(OK());
 }

bool Parma_Polyhedra_Library::Generator_System::is_necessarily_closed ( ) const

inlineprivate

Returns true if and only if the system topology is NECESSARILY_CLOSED.

Definition at line 190 of file Generator_System_inlines.hh.

References sys.

                                               {
   return sys.is_necessarily_closed();
 }

bool Parma_Polyhedra_Library::Generator_System::is_sorted ( ) const

inlineprivate

Returns the value of the sortedness flag.

Definition at line 180 of file Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators_with_sat_g(), Parma_Polyhedra_Library::Polyhedron::poly_hull_assign(), Parma_Polyhedra_Library::Polyhedron::process_pending_generators(), Parma_Polyhedra_Library::Polyhedron::strongly_minimize_generators(), and Parma_Polyhedra_Library::Polyhedron::time_elapse_assign().

                                   {
   return sys.is_sorted();
 }

void Parma_Polyhedra_Library::Generator_System::m_swap ( Generator_System & y )

inline

Swaps *this with y.

Definition at line 387 of file Generator_System_inlines.hh.

References swap(), and sys.

Referenced by swap().

                                             {
   swap(sys, y.sys);
 }

dimension_type Parma_Polyhedra_Library::Generator_System::max_space_dimension ( )

inlinestatic

Returns the maximum space dimension a Generator_System can handle.

Definition at line 87 of file Generator_System_inlines.hh.

References Parma_Polyhedra_Library::Linear_System< Row >::max_space_dimension().

Referenced by Parma_Polyhedra_Library::Polyhedron::max_space_dimension().

                                       {
   return Linear_System<Generator>::max_space_dimension();
 }

void Parma_Polyhedra_Library::Generator_System::merge_rows_assign ( const Generator_System & y )

inlineprivate

Assigns to *this the result of merging its rows with those of y, obtaining a sorted system.

Duplicated rows will occur only once in the result. On entry, both systems are assumed to be sorted and have no pending rows.

Definition at line 266 of file Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::poly_hull_assign(), and Parma_Polyhedra_Library::Polyhedron::time_elapse_assign().

                                                              {
   sys.merge_rows_assign(y.sys);
 }

PPL::dimension_type Parma_Polyhedra_Library::Generator_System::num_lines ( ) const

private

Returns the number of lines of the system.

Definition at line 288 of file Generator_System.cc.

References num_rows().

Referenced by Parma_Polyhedra_Library::Polyhedron::OK(), Parma_Polyhedra_Library::Polyhedron::quick_equivalence_test(), and Parma_Polyhedra_Library::Polyhedron::strongly_minimize_generators().

                                      {
   // We are sure that this method is applied only to a matrix
   // that does not contain pending rows.
   PPL_ASSERT(sys.num_pending_rows() == 0);
   const Generator_System& gs = *this;
   dimension_type n = 0;
   // If sys happens to be sorted, take advantage of the fact
   // that lines are at the top of the system.
   if (sys.is_sorted()) {
     const dimension_type nrows = sys.num_rows();
     for (dimension_type i = 0; i < nrows && gs[i].is_line(); ++i) {
       ++n;
     }
   }
   else {
     for (dimension_type i = sys.num_rows(); i-- > 0 ; ) {
       if (gs[i].is_line()) {
         ++n;
       }
     }
   }
   return n;
 }

dimension_type Parma_Polyhedra_Library::Generator_System::num_lines_or_equalities ( ) const

inlineprivate

Returns the number of rows in the system that represent either lines or equalities.

Definition at line 225 of file Generator_System_inlines.hh.

References sys.

                                                 {
   return sys.num_lines_or_equalities();
 }

dimension_type Parma_Polyhedra_Library::Generator_System::num_pending_rows ( ) const

inlineprivate

Returns the number of rows that are in the pending part of the system.

Definition at line 200 of file Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::Polyhedron(), and Parma_Polyhedra_Library::Polyhedron::process_pending_generators().

                                          {
   return sys.num_pending_rows();
 }

PPL::dimension_type Parma_Polyhedra_Library::Generator_System::num_rays ( ) const

private

Returns the number of rays of the system.

Definition at line 313 of file Generator_System.cc.

Referenced by Parma_Polyhedra_Library::Polyhedron::OK().

                                     {
   // We are sure that this method is applied only to a matrix
   // that does not contain pending rows.
   PPL_ASSERT(sys.num_pending_rows() == 0);
   const Generator_System& gs = *this;
   dimension_type n = 0;
   // If sys happens to be sorted, take advantage of the fact
   // that rays and points are at the bottom of the system and
   // rays have the inhomogeneous term equal to zero.
   if (sys.is_sorted()) {
     for (dimension_type i = sys.num_rows();
          i != 0 && gs[--i].is_ray_or_point(); ) {
       if (gs[i].is_line_or_ray()) {
         ++n;
       }
     }
   }
   else {
     for (dimension_type i = sys.num_rows(); i-- > 0 ; ) {
       if (gs[i].is_ray()) {
         ++n;
       }
     }
   }
   return n;
 }

dimension_type Parma_Polyhedra_Library::Generator_System::num_rows ( ) const

inlineprivate

Definition at line 150 of file Generator_System_inlines.hh.

References sys.

                                  {
   return sys.num_rows();
 }

bool Parma_Polyhedra_Library::Generator_System::OK ( ) const

Checks if all the invariants are satisfied.

Definition at line 852 of file Generator_System.cc.

Referenced by adjust_topology_and_space_dimension(), and set_space_dimension().

                               {
   return sys.OK();
 }

Generator_System & Parma_Polyhedra_Library::Generator_System::operator= ( const Generator_System & y )

inline

Assignment operator.

Definition at line 70 of file Generator_System_inlines.hh.

References swap().

                                                      {
   Generator_System tmp = y;
   swap(*this, tmp);
   return *this;
 }

const Generator & Parma_Polyhedra_Library::Generator_System::operator[] ( dimension_type k ) const

inlineprivate

Returns a constant reference to the k- th generator of the system.

Definition at line 121 of file Generator_System_inlines.hh.

References sys.

                                                          {
   return sys[k];
 }

void Parma_Polyhedra_Library::Generator_System::permute_space_dimensions ( const std::vector< Variable > & cycle )

inlineprivate

Permutes the space dimensions of the matrix.

Definition at line 139 of file Generator_System_inlines.hh.

Referenced by Parma_Polyhedra_Library::Polyhedron::map_space_dimensions().

                                                            {
   sys.permute_space_dimensions(cycle);
 }

void Parma_Polyhedra_Library::Generator_System::print ( ) const

Prints *this to std::cerr using operator<<.

PPL::Poly_Con_Relation Parma_Polyhedra_Library::Generator_System::relation_with ( const Constraint & c ) const

private

Returns the relations holding between the generator system and the constraint c.

Definition at line 341 of file Generator_System.cc.

                                                             {
   // Note: this method is not public and it is the responsibility
   // of the caller to actually test for dimension compatibility.
   // We simply assert it.
   PPL_ASSERT(space_dimension() >= c.space_dimension());
   // Number of generators: the case of an empty polyhedron
   // has already been filtered out by the caller.
   const dimension_type n_rows = sys.num_rows();
   PPL_ASSERT(n_rows > 0);
   const Generator_System& gs = *this;
 
   // `result' will keep the relation holding between the generators
   // we have seen so far and the constraint `c'.
   Poly_Con_Relation result = Poly_Con_Relation::saturates();
 
   switch (c.type()) {
 
   case Constraint::EQUALITY:
     {
       // The hyperplane defined by the equality `c' is included
       // in the set of points satisfying `c' (it is the same set!).
       result = result && Poly_Con_Relation::is_included();
       // The following integer variable will hold the scalar product sign
       // of either the first point or the first non-saturating ray we find.
       // If it is equal to 2, then it means that we haven't found such
       // a generator yet.
       int first_point_or_nonsaturating_ray_sign = 2;
 
       for (dimension_type i = n_rows; i-- > 0; ) {
         const Generator& g = gs[i];
         const int sp_sign = Scalar_Products::sign(c, g);
         // Checking whether the generator saturates the equality.
         // If that is the case, then we have to do something only if
         // the generator is a point.
         if (sp_sign == 0) {
           if (g.is_point()) {
             if (first_point_or_nonsaturating_ray_sign == 2) {
               // It is the first time that we find a point and
               // we have not found a non-saturating ray yet.
               first_point_or_nonsaturating_ray_sign = 0;
             }
             else {
               // We already found a point or a non-saturating ray.
               if (first_point_or_nonsaturating_ray_sign != 0) {
                 return Poly_Con_Relation::strictly_intersects();
               }
             }
           }
         }
         else {
           // Here we know that sp_sign != 0.
           switch (g.type()) {
 
           case Generator::LINE:
             // If a line does not saturate `c', then there is a strict
             // intersection between the points satisfying `c'
             // and the points generated by `gs'.
             return Poly_Con_Relation::strictly_intersects();
 
           case Generator::RAY:
             if (first_point_or_nonsaturating_ray_sign == 2) {
               // It is the first time that we have a non-saturating ray
               // and we have not found any point yet.
               first_point_or_nonsaturating_ray_sign = sp_sign;
               result = Poly_Con_Relation::is_disjoint();
             }
             else
               // We already found a point or a non-saturating ray.
               if (sp_sign != first_point_or_nonsaturating_ray_sign) {
                 return Poly_Con_Relation::strictly_intersects();
               }
             break;
 
           case Generator::POINT:
           case Generator::CLOSURE_POINT:
             // NOTE: a non-saturating closure point is treated as
             // a normal point.
             if (first_point_or_nonsaturating_ray_sign == 2) {
               // It is the first time that we find a point and
               // we have not found a non-saturating ray yet.
               first_point_or_nonsaturating_ray_sign = sp_sign;
               result = Poly_Con_Relation::is_disjoint();
             }
             else
               // We already found a point or a non-saturating ray.
               if (sp_sign != first_point_or_nonsaturating_ray_sign) {
                 return Poly_Con_Relation::strictly_intersects();
               }
             break;
           }
         }
       }
     }
     break;
 
   case Constraint::NONSTRICT_INEQUALITY:
     {
       // The hyperplane implicitly defined by the non-strict inequality `c'
       // is included in the set of points satisfying `c'.
       result = result && Poly_Con_Relation::is_included();
       // The following Boolean variable will be set to `false'
       // as soon as either we find (any) point or we find a
       // non-saturating ray.
       bool first_point_or_nonsaturating_ray = true;
 
       for (dimension_type i = n_rows; i-- > 0; ) {
         const Generator& g = gs[i];
         const int sp_sign = Scalar_Products::sign(c, g);
         // Checking whether the generator saturates the non-strict
         // inequality. If that is the case, then we have to do something
         // only if the generator is a point.
         if (sp_sign == 0) {
           if (g.is_point()) {
             if (first_point_or_nonsaturating_ray) {
               // It is the first time that we have a point and
               // we have not found a non-saturating ray yet.
               first_point_or_nonsaturating_ray = false;
             }
             else {
               // We already found a point or a non-saturating ray before.
               if (result == Poly_Con_Relation::is_disjoint()) {
                 // Since g saturates c, we have a strict intersection if
                 // none of the generators seen so far are included in `c'.
                 return Poly_Con_Relation::strictly_intersects();
               }
             }
           }
         }
         else {
           // Here we know that sp_sign != 0.
           switch (g.type()) {
 
           case Generator::LINE:
             // If a line does not saturate `c', then there is a strict
             // intersection between the points satisfying `c' and
             // the points generated by `gs'.
             return Poly_Con_Relation::strictly_intersects();
 
           case Generator::RAY:
             if (first_point_or_nonsaturating_ray) {
               // It is the first time that we have a non-saturating ray
               // and we have not found any point yet.
               first_point_or_nonsaturating_ray = false;
               result = (sp_sign > 0)
                 ? Poly_Con_Relation::is_included()
                 : Poly_Con_Relation::is_disjoint();
             }
             else {
               // We already found a point or a non-saturating ray.
               if ((sp_sign > 0
                    && result == Poly_Con_Relation::is_disjoint())
                   || (sp_sign < 0
                       && result.implies(Poly_Con_Relation::is_included()))) {
                 // We have a strict intersection if either:
                 // - `g' satisfies `c' but none of the generators seen
                 //    so far are included in `c'; or
                 // - `g' does not satisfy `c' and all the generators
                 //    seen so far are included in `c'.
                 return Poly_Con_Relation::strictly_intersects();
               }
               if (sp_sign > 0) {
                 // Here all the generators seen so far either saturate
                 // or are included in `c'.
                 // Since `g' does not saturate `c' ...
                 result = Poly_Con_Relation::is_included();
               }
             }
             break;
 
           case Generator::POINT:
           case Generator::CLOSURE_POINT:
             // NOTE: a non-saturating closure point is treated as
             // a normal point.
             if (first_point_or_nonsaturating_ray) {
               // It is the first time that we have a point and
               // we have not found a non-saturating ray yet.
               // - If point `g' saturates `c', then all the generators
               //   seen so far saturate `c'.
               // - If point `g' is included (but does not saturate) `c',
               //   then all the generators seen so far are included in `c'.
               // - If point `g' does not satisfy `c', then all the
               //   generators seen so far are disjoint from `c'.
               first_point_or_nonsaturating_ray = false;
               if (sp_sign > 0) {
                 result = Poly_Con_Relation::is_included();
               }
               else if (sp_sign < 0) {
                 result = Poly_Con_Relation::is_disjoint();
               }
             }
             else {
               // We already found a point or a non-saturating ray before.
               if ((sp_sign > 0
                    && result == Poly_Con_Relation::is_disjoint())
                   || (sp_sign < 0
                       && result.implies(Poly_Con_Relation::is_included()))) {
                 // We have a strict intersection if either:
                 // - `g' satisfies or saturates `c' but none of the
                 //    generators seen so far are included in `c'; or
                 // - `g' does not satisfy `c' and all the generators
                 //    seen so far are included in `c'.
                 return Poly_Con_Relation::strictly_intersects();
               }
               if (sp_sign > 0) {
                 // Here all the generators seen so far either saturate
                 // or are included in `c'.
                 // Since `g' does not saturate `c' ...
                 result = Poly_Con_Relation::is_included();
               }
             }
             break;
           }
         }
       }
     }
     break;
 
   case Constraint::STRICT_INEQUALITY:
     {
       // The hyperplane implicitly defined by the strict inequality `c'
       // is disjoint from the set of points satisfying `c'.
       result = result && Poly_Con_Relation::is_disjoint();
       // The following Boolean variable will be set to `false'
       // as soon as either we find (any) point or we find a
       // non-saturating ray.
       bool first_point_or_nonsaturating_ray = true;
       for (dimension_type i = n_rows; i-- > 0; ) {
         const Generator& g = gs[i];
         // Using the reduced scalar product operator to avoid
         // both topology and space dimension mismatches.
         const int sp_sign = Scalar_Products::reduced_sign(c, g);
         // Checking whether the generator saturates the strict inequality.
         // If that is the case, then we have to do something
         // only if the generator is a point.
         if (sp_sign == 0) {
           if (g.is_point()) {
             if (first_point_or_nonsaturating_ray) {
               // It is the first time that we have a point and
               // we have not found a non-saturating ray yet.
               first_point_or_nonsaturating_ray = false;
             }
             else {
               // We already found a point or a non-saturating ray before.
               if (result == Poly_Con_Relation::is_included()) {
                 return Poly_Con_Relation::strictly_intersects();
               }
             }
           }
         }
         else {
           // Here we know that sp_sign != 0.
           switch (g.type()) {
 
           case Generator::LINE:
             // If a line does not saturate `c', then there is a strict
             // intersection between the points satisfying `c' and the points
             // generated by `gs'.
             return Poly_Con_Relation::strictly_intersects();
 
           case Generator::RAY:
             if (first_point_or_nonsaturating_ray) {
               // It is the first time that we have a non-saturating ray
               // and we have not found any point yet.
               first_point_or_nonsaturating_ray = false;
               result = (sp_sign > 0)
                 ? Poly_Con_Relation::is_included()
                 : Poly_Con_Relation::is_disjoint();
             }
             else {
               // We already found a point or a non-saturating ray before.
               if ((sp_sign > 0
                    && result.implies(Poly_Con_Relation::is_disjoint()))
                   ||
                   (sp_sign <= 0
                    && result == Poly_Con_Relation::is_included())) {
                 return Poly_Con_Relation::strictly_intersects();
               }
               if (sp_sign < 0) {
                 // Here all the generators seen so far either saturate
                 // or are disjoint from `c'.
                 // Since `g' does not saturate `c' ...
                 result = Poly_Con_Relation::is_disjoint();
               }
             }
             break;
 
           case Generator::POINT:
           case Generator::CLOSURE_POINT:
             if (first_point_or_nonsaturating_ray) {
               // It is the first time that we have a point and
               // we have not found a non-saturating ray yet.
               // - If point `g' saturates `c', then all the generators
               //   seen so far saturate `c'.
               // - If point `g' is included in (but does not saturate) `c',
               //   then all the generators seen so far are included in `c'.
               // - If point `g' strictly violates `c', then all the
               //   generators seen so far are disjoint from `c'.
               first_point_or_nonsaturating_ray = false;
               if (sp_sign > 0) {
                 result = Poly_Con_Relation::is_included();
               }
               else if (sp_sign < 0) {
                 result = Poly_Con_Relation::is_disjoint();
               }
             }
             else {
               // We already found a point or a non-saturating ray before.
               if ((sp_sign > 0
                    && result.implies(Poly_Con_Relation::is_disjoint()))
                   ||
                   (sp_sign <= 0
                    && result == Poly_Con_Relation::is_included())) {
                 return Poly_Con_Relation::strictly_intersects();
               }
               if (sp_sign < 0) {
                 // Here all the generators seen so far either saturate
                 // or are disjoint from `c'.
                 // Since `g' does not saturate `c' ...
                 result = Poly_Con_Relation::is_disjoint();
               }
             }
             break;
           }
         }
       }
     }
     break;
   }
   // We have seen all generators.
   return result;
 }

void Parma_Polyhedra_Library::Generator_System::remove_invalid_lines_and_rays ( )

private

Removes all the invalid lines and rays.

The invalid lines and rays are those with all the homogeneous terms set to zero.

Definition at line 815 of file Generator_System.cc.

References Parma_Polyhedra_Library::Linear_Expression::all_homogeneous_terms_are_zero(), Parma_Polyhedra_Library::Generator::expr, and Parma_Polyhedra_Library::Generator::is_line_or_ray().

Referenced by affine_image(), set_space_dimension(), and simplify().

                                                    {
   // The origin of the vector space cannot be a valid line/ray.
   // NOTE: the following swaps will mix generators without even trying
   // to preserve sortedness: as a matter of fact, it will almost always
   // be the case that the input generator system is NOT sorted.
 
   // Note that num_rows() is *not* constant, because it is decreased by
   // remove_row().
   for (dimension_type i = 0; i < num_rows(); ) {
     const Generator& g = (*this)[i];
     if (g.is_line_or_ray() && g.expr.all_homogeneous_terms_are_zero()) {
       sys.remove_row(i, false);
       set_sorted(false);
     }
     else {
       ++i;
     }
   }
 }

void Parma_Polyhedra_Library::Generator_System::remove_row	(	dimension_type	i,
		bool	keep_sorted = `false`
	)

inlineprivate

Makes the system shrink by removing its i-th row.

When keep_sorted is true and the system is sorted, sortedness will be preserved, but this method costs O(n).

Otherwise, this method just swaps the i-th row with the last and then removes it, so it costs O(1).

Definition at line 230 of file Generator_System_inlines.hh.

References sys.

                                                                {
   sys.remove_row(i, keep_sorted);
 }

void Parma_Polyhedra_Library::Generator_System::remove_rows	(	dimension_type	first,
		dimension_type	last,
		bool	keep_sorted = `false`
	)

inlineprivate

Makes the system shrink by removing the rows in [first,last).

When keep_sorted is true and the system is sorted, sortedness will be preserved, but this method costs O(num_rows()).

Otherwise, this method just swaps the rows with the last ones and then removes them, so it costs O(last - first).

Definition at line 235 of file Generator_System_inlines.hh.

References sys.

                                                 {
   sys.remove_rows(first, last, keep_sorted);
 }

void Parma_Polyhedra_Library::Generator_System::remove_rows ( const std::vector< dimension_type > & indexes )

inlineprivate

Removes the specified rows. The row ordering of remaining rows is preserved.

Parameters

indexes specifies a list of row indexes. It must be sorted.

Definition at line 241 of file Generator_System_inlines.hh.

References sys.

                                                                       {
   sys.remove_rows(indexes);
 }

void Parma_Polyhedra_Library::Generator_System::remove_space_dimensions ( const Variables_Set & vars )

inlineprivate

Removes all the specified dimensions from the generator system.

The space dimension of the variable with the highest space dimension in vars must be at most the space dimension of this.

Definition at line 127 of file Generator_System_inlines.hh.

                                                    {
   sys.remove_space_dimensions(vars);
 }

void Parma_Polyhedra_Library::Generator_System::remove_trailing_rows ( dimension_type n )

inlineprivate

Makes the system shrink by removing its n trailing rows.

Definition at line 246 of file Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::OK().

                                                        {
   sys.remove_trailing_rows(n);
 }

Representation Parma_Polyhedra_Library::Generator_System::representation ( ) const

inline

Returns the current representation of *this.

Definition at line 77 of file Generator_System_inlines.hh.

References sys.

                                        {
   return sys.representation();
 }

bool Parma_Polyhedra_Library::Generator_System::satisfied_by_all_generators ( const Constraint & c ) const

private

Returns true if all the generators satisfy c.

Definition at line 675 of file Generator_System.cc.

References Parma_Polyhedra_Library::Constraint::EQUALITY, Parma_Polyhedra_Library::Generator::is_line(), Parma_Polyhedra_Library::Generator::LINE, Parma_Polyhedra_Library::Constraint::NONSTRICT_INEQUALITY, Parma_Polyhedra_Library::Generator::POINT, Parma_Polyhedra_Library::Constraint::space_dimension(), Parma_Polyhedra_Library::Constraint::STRICT_INEQUALITY, sys, Parma_Polyhedra_Library::Constraint::type(), and Parma_Polyhedra_Library::Generator::type().

Referenced by Parma_Polyhedra_Library::Polyhedron::limited_BHRZ03_extrapolation_assign(), Parma_Polyhedra_Library::Polyhedron::limited_H79_extrapolation_assign(), and Parma_Polyhedra_Library::Polyhedron::simplify_using_context_assign().

                                                                           {
   PPL_ASSERT(c.space_dimension() <= space_dimension());
 
   // Setting `sps' to the appropriate scalar product sign operator.
   // This also avoids problems when having _legal_ topology mismatches
   // (which could also cause a mismatch in the number of space dimensions).
   const Topology_Adjusted_Scalar_Product_Sign sps(c);
 
   const Generator_System& gs = *this;
   switch (c.type()) {
   case Constraint::EQUALITY:
     // Equalities must be saturated by all generators.
     for (dimension_type i = gs.sys.num_rows(); i-- > 0; ) {
       if (sps(c, gs[i]) != 0) {
         return false;
       }
     }
     break;
   case Constraint::NONSTRICT_INEQUALITY:
     // Non-strict inequalities must be saturated by lines and
     // satisfied by all the other generators.
     for (dimension_type i = gs.sys.num_rows(); i-- > 0; ) {
       const Generator& g = gs[i];
       const int sp_sign = sps(c, g);
       if (g.is_line()) {
         if (sp_sign != 0) {
           return false;
         }
       }
       else
         // `g' is a ray, point or closure point.
         if (sp_sign < 0) {
           return false;
         }
     }
     break;
   case Constraint::STRICT_INEQUALITY:
     // Strict inequalities must be saturated by lines,
     // satisfied by all generators, and must not be saturated by points.
     for (dimension_type i = gs.sys.num_rows(); i-- > 0; ) {
       const Generator& g = gs[i];
       const int sp_sign = sps(c, g);
       switch (g.type()) {
       case Generator::POINT:
         if (sp_sign <= 0) {
           return false;
         }
         break;
       case Generator::LINE:
         if (sp_sign != 0) {
           return false;
         }
         break;
       default:
         // `g' is a ray or closure point.
         if (sp_sign < 0) {
           return false;
         }
         break;
       }
     }
     break;
   }
   // If we reach this point, `c' is satisfied by all generators.
   return true;
 }

bool Parma_Polyhedra_Library::Generator_System::satisfied_by_all_generators_C ( const Constraint & c ) const

private

Returns true if all the generators satisfy c.

It is assumed that c.is_necessarily_closed() holds.

bool Parma_Polyhedra_Library::Generator_System::satisfied_by_all_generators_NNC ( const Constraint & c ) const

private

Returns true if all the generators satisfy c.

It is assumed that c.is_necessarily_closed() does not hold.

void Parma_Polyhedra_Library::Generator_System::set_index_first_pending_row ( dimension_type i )

inlineprivate

Sets the index of the first pending row to i.

Definition at line 185 of file Generator_System_inlines.hh.

References sys.

                                                               {
   sys.set_index_first_pending_row(i);
 }

void Parma_Polyhedra_Library::Generator_System::set_representation ( Representation r )

inline

Converts *this to the specified representation.

Definition at line 82 of file Generator_System_inlines.hh.

References sys.

                                                      {
   sys.set_representation(r);
 }

void Parma_Polyhedra_Library::Generator_System::set_sorted ( bool b )

inlineprivate

Sets the sortedness flag of the system to b.

Definition at line 175 of file Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators_with_sat_g(), Parma_Polyhedra_Library::Polyhedron::Polyhedron(), Parma_Polyhedra_Library::Polyhedron::remove_pending_to_obtain_generators(), and Parma_Polyhedra_Library::Polyhedron::strongly_minimize_generators().

                                    {
   sys.set_sorted(b);
 }

void Parma_Polyhedra_Library::Generator_System::set_space_dimension ( dimension_type space_dim )

inline

Sets the space dimension of the rows in the system to space_dim .

Definition at line 97 of file Generator_System_inlines.hh.

References OK(), remove_invalid_lines_and_rays(), space_dimension(), and sys.

                                                               {
   const dimension_type old_space_dim = space_dimension();
   sys.set_space_dimension_no_ok(space_dim);
 
   if (space_dim < old_space_dim) {
     // We may have invalid lines and rays now.
     remove_invalid_lines_and_rays();
   }
 
 #ifndef NDEBUG
   for (dimension_type i = 0; i < sys.num_rows(); ++i) {
     PPL_ASSERT(sys[i].OK());
   }
 #endif
   PPL_ASSERT(sys.OK());
   PPL_ASSERT(OK());
 }

void Parma_Polyhedra_Library::Generator_System::shift_space_dimensions	(	Variable	v,
		dimension_type	n
	)

inlineprivate

Shift by n positions the coefficients of variables, starting from the coefficient of v. This increases the space dimension by n.

Definition at line 133 of file Generator_System_inlines.hh.

                                                      {
   sys.shift_space_dimensions(v, n);
 }

void Parma_Polyhedra_Library::Generator_System::simplify ( )

inlineprivate

Applies Gaussian elimination and back-substitution so as to provide a partial simplification of the system of generators.

It is assumed that the system has no pending generators.

Definition at line 402 of file Generator_System_inlines.hh.

References remove_invalid_lines_and_rays(), and sys.

                            {
   sys.simplify();
   remove_invalid_lines_and_rays();
 }

void Parma_Polyhedra_Library::Generator_System::sort_and_remove_with_sat ( Bit_Matrix & sat )

inlineprivate

Sorts the system, removing duplicates, keeping the saturation matrix consistent.

Parameters

sat	Bit matrix with rows corresponding to the rows of `*this`.

Definition at line 210 of file Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators(), and Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators_with_sat_g().

                                                           {
   sys.sort_and_remove_with_sat(sat);
 }

void Parma_Polyhedra_Library::Generator_System::sort_pending_and_remove_duplicates ( )

inlineprivate

Sorts the pending rows and eliminates those that also occur in the non-pending part of the system.

Definition at line 205 of file Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::process_pending_generators().

                                                      {
   return sys.sort_pending_and_remove_duplicates();
 }

void Parma_Polyhedra_Library::Generator_System::sort_rows ( )

inlineprivate

Sorts the non-pending rows (in growing order) and eliminates duplicated ones.

Definition at line 215 of file Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators(), Parma_Polyhedra_Library::Polyhedron::OK(), and Parma_Polyhedra_Library::Polyhedron::time_elapse_assign().

                             {
   sys.sort_rows();
 }

dimension_type Parma_Polyhedra_Library::Generator_System::space_dimension ( ) const

inline

Returns the dimension of the vector space enclosing *this.

Definition at line 92 of file Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), adjust_topology_and_space_dimension(), affine_image(), Parma_Polyhedra_Library::Affine_Space::Affine_Space(), Parma_Polyhedra_Library::Polyhedron::Polyhedron(), set_space_dimension(), and Parma_Polyhedra_Library::Polyhedron::throw_dimension_incompatible().

                                         {
   return sys.space_dimension();
 }

void Parma_Polyhedra_Library::Generator_System::strong_normalize ( )

inlineprivate

Strongly normalizes the system.

Definition at line 261 of file Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::OK().

                                    {
   sys.strong_normalize();
 }

void Parma_Polyhedra_Library::Generator_System::swap_space_dimensions	(	Variable	v1,
		Variable	v2
	)

inlineprivate

Swaps the coefficients of the variables v1 and v2 .

Definition at line 145 of file Generator_System_inlines.hh.

                                                 {
   sys.swap_space_dimensions(v1, v2);
 }

Topology Parma_Polyhedra_Library::Generator_System::topology ( ) const

inlineprivate

Definition at line 160 of file Generator_System_inlines.hh.

References sys.

                                  {
   return sys.topology();
 }

memory_size_type Parma_Polyhedra_Library::Generator_System::total_memory_in_bytes ( ) const

inline

Returns the total size in bytes of the memory occupied by *this.

Definition at line 397 of file Generator_System_inlines.hh.

References external_memory_in_bytes().

                                               {
   return external_memory_in_bytes() + sizeof(*this);
 }

void Parma_Polyhedra_Library::Generator_System::unset_pending_rows ( )

inlineprivate

Sets the index to indicate that the system has no pending rows.

Definition at line 170 of file Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Polyhedron::OK(), Parma_Polyhedra_Library::Polyhedron::Polyhedron(), Parma_Polyhedra_Library::Polyhedron::positive_time_elapse_assign_impl(), Parma_Polyhedra_Library::Polyhedron::remove_pending_to_obtain_generators(), and Parma_Polyhedra_Library::Polyhedron::time_elapse_assign().

                                      {
   sys.unset_pending_rows();
 }

const Generator_System & Parma_Polyhedra_Library::Generator_System::zero_dim_univ ( )

inlinestatic

Returns the singleton system containing only Generator::zero_dim_point().

Definition at line 381 of file Generator_System_inlines.hh.

References zero_dim_univ_p.

Referenced by Parma_Polyhedra_Library::Polyhedron::generators().

                                 {
   PPL_ASSERT(zero_dim_univ_p != 0);
   return *zero_dim_univ_p;
 }

Friends And Related Function Documentation

friend class Generator_System_const_iterator

friend

Definition at line 496 of file Generator_System_defs.hh.

bool operator!=	(	const Generator_System &	x,
		const Generator_System &	y
	)

Definition at line 286 of file Generator_System_inlines.hh.

                                                                  {
   return !(x == y);
 }

std::ostream & operator<<	(	std::ostream &	s,
		const Generator_System &	gs
	)

Writes false if gs is empty. Otherwise, writes on s the generators of gs, all in one row and separated by ", ".

std::ostream & operator<<	(	std::ostream &	s,
		const Generator_System &	gs
	)

References begin(), and end().

                                                                      {
   Generator_System::const_iterator i = gs.begin();
   const Generator_System::const_iterator gs_end = gs.end();
   if (i == gs_end) {
     return s << "false";
   }
   while (true) {
     s << *i;
     ++i;
     if (i == gs_end) {
       return s;
     }
     s << ", ";
   }
 }

bool operator==	(	const Generator_System &	x,
		const Generator_System &	y
	)

Definition at line 281 of file Generator_System_inlines.hh.

                                                                  {
   return x.sys == y.sys;
 }

bool operator==	(	const Generator_System &	x,
		const Generator_System &	y
	)

friend

Definition at line 281 of file Generator_System_inlines.hh.

                                                                  {
   return x.sys == y.sys;
 }

friend class Polyhedron

friend

Definition at line 656 of file Generator_System_defs.hh.

void swap	(	Generator_System &	x,
		Generator_System &	y
	)

void swap	(	Generator_System &	x,
		Generator_System &	y
	)

References m_swap().

                                                {
   x.m_swap(y);
 }

Member Data Documentation

const Representation Parma_Polyhedra_Library::Generator_System::default_representation = SPARSE

static

Definition at line 192 of file Generator_System_defs.hh.

Linear_System<Generator> Parma_Polyhedra_Library::Generator_System::sys

private

Definition at line 651 of file Generator_System_defs.hh.

Referenced by add_corresponding_closure_points(), add_corresponding_points(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), add_universe_rows_and_space_dimensions(), adjust_topology_and_space_dimension(), affine_image(), assign_with_pending(), back_substitute(), begin(), check_sorted(), clear(), empty(), end(), external_memory_in_bytes(), first_pending_row(), gauss(), Generator_System(), has_no_rows(), insert(), insert_pending(), is_necessarily_closed(), is_sorted(), m_swap(), merge_rows_assign(), num_lines_or_equalities(), num_pending_rows(), num_rows(), Parma_Polyhedra_Library::operator==(), operator[](), Parma_Polyhedra_Library::Polyhedron::positive_time_elapse_assign_impl(), remove_row(), remove_rows(), remove_trailing_rows(), representation(), satisfied_by_all_generators(), set_index_first_pending_row(), set_representation(), set_sorted(), set_space_dimension(), simplify(), sort_and_remove_with_sat(), sort_pending_and_remove_duplicates(), sort_rows(), space_dimension(), strong_normalize(), Parma_Polyhedra_Library::Polyhedron::strongly_minimize_generators(), Parma_Polyhedra_Library::Polyhedron::time_elapse_assign(), topology(), and unset_pending_rows().

const PPL::Generator_System * Parma_Polyhedra_Library::Generator_System::zero_dim_univ_p = 0

staticprivate

Holds (between class initialization and finalization) a pointer to the singleton system containing only Generator::zero_dim_point().

Definition at line 494 of file Generator_System_defs.hh.

Referenced by zero_dim_univ().

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

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Static Private Attributes

Friends

Related Functions

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation