PPL  0.12.1
Classes | Public Types | Public Member Functions | Static Public Member Functions | Friends | Related Functions
Parma_Polyhedra_Library::Linear_Row Class Reference
C++ Language Interface

The base class for linear expressions, constraints and generators. More...

#include <Linear_Row.defs.hh>

Inheritance diagram for Parma_Polyhedra_Library::Linear_Row:
Inheritance graph
[legend]
Collaboration diagram for Parma_Polyhedra_Library::Linear_Row:
Collaboration graph
[legend]

List of all members.

Classes

class  Flags
 The type of the object to which the coefficients refer to, encoding both topology and kind. More...

Public Types

enum  Kind { LINE_OR_EQUALITY = 0, RAY_OR_POINT_OR_INEQUALITY = 1 }
 The possible kinds of Linear_Row objects. More...

Public Member Functions

 Linear_Row ()
 Pre-constructs a row: construction must be completed by construct().
 Linear_Row (dimension_type sz, Flags f)
 Tight constructor: resizing will require reallocation.
 Linear_Row (dimension_type sz, dimension_type capacity, Flags f)
 Sizing constructor with capacity.
 Linear_Row (const Linear_Row &y)
 Ordinary copy constructor.
 Linear_Row (const Linear_Row &y, dimension_type capacity)
 Copy constructor with specified capacity.
 Linear_Row (const Linear_Row &y, dimension_type sz, dimension_type capacity)
 Copy constructor with specified size and capacity.
 ~Linear_Row ()
 Destructor.
dimension_type space_dimension () const
 Returns the dimension of the vector space enclosing *this.
Coefficient_traits::const_reference inhomogeneous_term () const
 Returns the inhomogeneous term.
Coefficient_traits::const_reference coefficient (dimension_type n) const
 Returns the coefficient $a_n$.
void sign_normalize ()
 Normalizes the sign of the coefficients so that the first non-zero (homogeneous) coefficient of a line-or-equality is positive.
void strong_normalize ()
 Strong normalization: ensures that different Linear_Row objects represent different hyperplanes or hyperspaces.
bool check_strong_normalized () const
 Returns true if and only if the coefficients are strongly normalized.
void linear_combine (const Linear_Row &y, dimension_type k)
 Linearly combines *this with y so that *this[k] is 0.
bool is_zero () const
 Returns true if and only if all the terms of *this are $0$.
bool all_homogeneous_terms_are_zero () const
 Returns true if and only if all the homogeneous terms of *this are $0$.
void ascii_dump () const
 Writes to std::cerr an ASCII representation of *this.
void ascii_dump (std::ostream &s) const
 Writes to s an ASCII representation of *this.
void print () const
 Prints *this to std::cerr using operator<<.
bool ascii_load (std::istream &s)
 Loads from s an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets *this accordingly. Returns true if successful, false otherwise.
bool OK () const
 Checks if all the invariants are satisfied.
bool OK (dimension_type row_size, dimension_type row_capacity) const
 Checks if all the invariants are satisfied and that the actual size and capacity match the values provided as arguments.
Flags inspection methods
const Flags flags () const
 Returns the flags of *this.
void set_flags (Flags f)
 Sets f as the flags of *this.
Topology topology () const
 Returns the topological kind of *this.
bool is_not_necessarily_closed () const
 Returns true if and only if the topology of *this row is not necessarily closed.
bool is_necessarily_closed () const
 Returns true if and only if the topology of *this row is necessarily closed.
bool is_line_or_equality () const
 Returns true if and only if *this row represents a line or an equality.
bool is_ray_or_point_or_inequality () const
 Returns true if and only if *this row represents a ray, a point or an inequality.
Flags coercion methods
void set_necessarily_closed ()
 Sets to NECESSARILY_CLOSED the topological kind of *this row.
void set_not_necessarily_closed ()
 Sets to NOT_NECESSARILY_CLOSED the topological kind of *this row.
void set_is_line_or_equality ()
 Sets to LINE_OR_EQUALITY the kind of *this row.
void set_is_ray_or_point_or_inequality ()
 Sets to RAY_OR_POINT_OR_INEQUALITY the kind of *this row.

Static Public Member Functions

static dimension_type max_space_dimension ()
 Returns the maximum space dimension a Linear_Row can handle.

Friends

class Parma_Polyhedra_Library::Linear_Expression
class Parma_Polyhedra_Library::Constraint
class Parma_Polyhedra_Library::Generator

Related Functions

(Note that these are not member functions.)

template<typename C >
bool operator== (const Linear_Form< C > &x, const Linear_Form< C > &y)
int compare (const Linear_Row &x, const Linear_Row &y)
void swap (Linear_Row &x, Linear_Row &y)
 Swaps x with y.
void iter_swap (std::vector< Linear_Row >::iterator x, std::vector< Linear_Row >::iterator y)
 Swaps the objects referred by x and y.
bool operator== (const Linear_Row &x, const Linear_Row &y)
 Returns true if and only if x and y are equal.
bool operator!= (const Linear_Row &x, const Linear_Row &y)
 Returns true if and only if x and y are different.
int compare (const Linear_Row &x, const Linear_Row &y)
 The basic comparison function.
bool operator== (const Linear_Row &x, const Linear_Row &y)
bool operator!= (const Linear_Row &x, const Linear_Row &y)
void swap (Linear_Row &x, Linear_Row &y)
void iter_swap (std::vector< Linear_Row >::iterator x, std::vector< Linear_Row >::iterator y)

Detailed Description

The base class for linear expressions, constraints and generators.

The class Linear_Row allows us to build objects of the form $[b, a_0, \ldots, a_{d-1}]_{(t, k)}$, i.e., a finite sequence of coefficients subscripted by a pair of flags, which are both stored in a Linear_Row::Flags object. The flag $t \in \{ \mathrm{c}, \mathrm{nnc} \}$ represents the topology and the flag $k \in \{\mathord{=}, \mathord{\geq} \}$ represents the kind of the Linear_Row object. Note that, even though all the four possible combinations of topology and kind values will result in a legal Linear_Row::Flags object, some of these pose additional constraints on the values of the Linear_Row's coefficients.

When $t = c$, we have the following cases ( $d$ is the dimension of the vector space):

  • $[b, a_0, \ldots, a_{d-1}]_{(c,=)}$ represents the equality constraint $\sum_{i=0}^{d-1} a_i x_i + b = 0$.
  • $[b, a_0, \ldots, a_{d-1}]_{(c,\geq)}$ represents the non-strict inequality constraint $\sum_{i=0}^{d-1} a_i x_i + b \geq 0$.
  • $[0, a_0, \ldots, a_{d-1}]_{(c,=)}$ represents the line of direction $\vect{l} = (a_0, \ldots, a_{d-1})^\transpose$.
  • $[0, a_0, \ldots, a_{d-1}]_{(c,\geq)}$ represents the ray of direction $\vect{r} = (a_0, \ldots, a_{d-1})^\transpose$.
  • $[b, a_0, \ldots, a_{d-1}]_{(c,\geq)}$, with $b > 0$, represents the point $\vect{p} = (\frac{a_0}{b}, \ldots, \frac{a_{d-1}}{b})^\transpose$.

When $t = \mathrm{nnc}$, the last coefficient of the Linear_Row is associated to the slack variable $\epsilon$, so that we have the following cases ( $d$ is again the dimension of the vector space, but this time we have $d+2$ coefficients):

  • $[b, a_0, \ldots, a_{d-1}, 0]_{(\mathrm{nnc},=)}$ represents the equality constraint $\sum_{i=0}^{d-1} a_i x_i + b = 0$.
  • $[b, a_0, \ldots, a_{d-1}, 0]_{(\mathrm{nnc},\geq)}$ represents the non-strict inequality constraint $\sum_{i=0}^{d-1} a_i x_i + b \geq 0$.
  • $[b, a_0, \ldots, a_{d-1}, e]_{(\mathrm{nnc},\geq)}$, with $e < 0$, represents the strict inequality constraint $\sum_{i=0}^{d-1} a_i x_i + b > 0$.
  • $[0, a_0, \ldots, a_{d-1}, 0]_{(\mathrm{nnc},=)}$ represents the line of direction $\vect{l} = (a_0, \ldots, a_{d-1})^\transpose$.
  • $[0, a_0, \ldots, a_{d-1}, 0]_{(\mathrm{nnc},\geq)}$ represents the ray of direction $\vect{r} = (a_0, \ldots, a_{d-1})^\transpose$.
  • $[b, a_0, \ldots, a_{d-1}, e]_{(\mathrm{nnc},\geq)}$, with $b > 0$ and $e > 0$, represents the point $\vect{p} = (\frac{a_0}{b}, \ldots, \frac{a_{d-1}}{b})^\transpose$.
  • $[b, a_0, \ldots, a_{d-1}, 0]_{(\mathrm{nnc},\geq)}$, with $b > 0$, represents the closure point $\vect{c} = (\frac{a_0}{b}, \ldots, \frac{a_{d-1}}{b})^\transpose$.

So, a Linear_Row can be both a constraint and a generator: it can be an equality, a strict or non-strict inequality, a line, a ray, a point or a closure point.

The inhomogeneous term of a constraint can be zero or different from zero.

Points and closure points must have a positive inhomogeneous term (which is used as a common divisor for all the other coefficients), lines and rays must have the inhomogeneous term equal to zero. If needed, the coefficients of points and closure points are negated at creation time so that they satisfy this invariant. The invariant is maintained because, when combining a point or closure point with another generator, we only consider positive combinations.

The $\epsilon$ coefficient, when present, is negative for strict inequality constraints, positive for points and equal to zero in all the other cases. Note that the above description corresponds to the end-user, high-level view of a Linear_Row object. In the implementation, to allow for code reuse, it is sometimes useful to regard an $\mathrm{nnc}$-object on the vector space $\Rset^d$ as if it was a $\mathrm{c}$-object on the vector space $\Rset^{d+1}$, therefore interpreting the slack variable $\epsilon$ as an ordinary dimension of the vector space.

A Linear_Row object implementing a Linear_Expression is always of the form $[0, a_0, \ldots, a_{d-1}]_{(c,=)}$, which represents the linear expression $\sum_{i=0}^{d-1} a_i x_i$.

Definition at line 125 of file Linear_Row.defs.hh.

Member Enumeration Documentation

enum Parma_Polyhedra_Library::Linear_Row::Kind

The possible kinds of Linear_Row objects.

Enumerator:
LINE_OR_EQUALITY 
RAY_OR_POINT_OR_INEQUALITY 

Definition at line 128 of file Linear_Row.defs.hh.

            {
    LINE_OR_EQUALITY = 0,
    RAY_OR_POINT_OR_INEQUALITY = 1
  };

Constructor & Destructor Documentation

Parma_Polyhedra_Library::Linear_Row::Linear_Row ( )
inline

Pre-constructs a row: construction must be completed by construct().

Definition at line 169 of file Linear_Row.inlines.hh.

  : Dense_Row() {
}
Parma_Polyhedra_Library::Linear_Row::Linear_Row ( dimension_type  sz,
Flags  f 
)
inline

Tight constructor: resizing will require reallocation.

Definition at line 180 of file Linear_Row.inlines.hh.

  : Dense_Row(sz, f) {
}
Parma_Polyhedra_Library::Linear_Row::Linear_Row ( dimension_type  sz,
dimension_type  capacity,
Flags  f 
)
inline

Sizing constructor with capacity.

Definition at line 174 of file Linear_Row.inlines.hh.

  : Dense_Row(sz, capacity, f) {
}
Parma_Polyhedra_Library::Linear_Row::Linear_Row ( const Linear_Row &  y)
inline

Ordinary copy constructor.

Definition at line 185 of file Linear_Row.inlines.hh.

  : Dense_Row(y) {
}
Parma_Polyhedra_Library::Linear_Row::Linear_Row ( const Linear_Row &  y,
dimension_type  capacity 
)
inline

Copy constructor with specified capacity.

It is assumed that capacity is greater than or equal to y size.

Definition at line 190 of file Linear_Row.inlines.hh.

  : Dense_Row(y, capacity) {
}
Parma_Polyhedra_Library::Linear_Row::Linear_Row ( const Linear_Row &  y,
dimension_type  sz,
dimension_type  capacity 
)
inline

Copy constructor with specified size and capacity.

It is assumed that sz is greater than or equal to the size of y and, of course, that sz is less than or equal to capacity.

Definition at line 196 of file Linear_Row.inlines.hh.

  : Dense_Row(y, sz, capacity) {
}
Parma_Polyhedra_Library::Linear_Row::~Linear_Row ( )
inline

Destructor.

Definition at line 202 of file Linear_Row.inlines.hh.

                        {
}

Member Function Documentation

bool Parma_Polyhedra_Library::Linear_Row::all_homogeneous_terms_are_zero ( ) const

Returns true if and only if all the homogeneous terms of *this are $0$.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator, and Parma_Polyhedra_Library::Linear_Expression.

Definition at line 134 of file Linear_Row.cc.

References Parma_Polyhedra_Library::Dense_Row::size().

Referenced by Parma_Polyhedra_Library::Polyhedron::BFT00_poly_hull_assign_if_exact(), Parma_Polyhedra_Library::Constraint::is_inconsistent(), Parma_Polyhedra_Library::Constraint::is_tautological(), Parma_Polyhedra_Library::Generator::OK(), Parma_Polyhedra_Library::Generator_System::remove_invalid_lines_and_rays(), and Parma_Polyhedra_Library::Polyhedron::time_elapse_assign().

                                                    {
  const Linear_Row& x = *this;
  for (dimension_type i = x.size(); --i > 0; )
    if (x[i] != 0)
      return false;
  return true;
}
void Parma_Polyhedra_Library::Linear_Row::ascii_dump ( ) const

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

Reimplemented from Parma_Polyhedra_Library::Dense_Row.

Reimplemented in Parma_Polyhedra_Library::Constraint, Parma_Polyhedra_Library::Generator, Parma_Polyhedra_Library::Grid_Generator, Parma_Polyhedra_Library::Linear_Expression, and Parma_Polyhedra_Library::PIP_Tree_Node::Artificial_Parameter.

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

Writes to s an ASCII representation of *this.

Reimplemented from Parma_Polyhedra_Library::Dense_Row.

Reimplemented in Parma_Polyhedra_Library::Constraint, Parma_Polyhedra_Library::Generator, Parma_Polyhedra_Library::Grid_Generator, Parma_Polyhedra_Library::Linear_Expression, and Parma_Polyhedra_Library::PIP_Tree_Node::Artificial_Parameter.

Definition at line 207 of file Linear_Row.cc.

References Parma_Polyhedra_Library::Dense_Row::ascii_dump(), and Parma_Polyhedra_Library::Dense_Row::size().

                                             {
  const Dense_Row& x = *this;
  const dimension_type x_size = x.size();
  s << "size " << x_size << " ";
  for (dimension_type i = 0; i < x_size; ++i)
    s << x[i] << ' ';
  s << "f ";
  flags().ascii_dump(s);
  s << "\n";
}
bool Parma_Polyhedra_Library::Linear_Row::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.

Reimplemented from Parma_Polyhedra_Library::Dense_Row.

Reimplemented in Parma_Polyhedra_Library::Constraint, Parma_Polyhedra_Library::Generator, Parma_Polyhedra_Library::Grid_Generator, Parma_Polyhedra_Library::Linear_Expression, and Parma_Polyhedra_Library::PIP_Tree_Node::Artificial_Parameter.

Definition at line 221 of file Linear_Row.cc.

References Parma_Polyhedra_Library::Linear_Row::Flags::ascii_load(), Parma_Polyhedra_Library::Dense_Row::m_swap(), Parma_Polyhedra_Library::Dense_Row::shrink(), and Parma_Polyhedra_Library::Dense_Row::size().

                                       {
  std::string str;
  if (!(s >> str) || str != "size")
    return false;
  dimension_type new_size;
  if (!(s >> new_size))
    return false;

  Dense_Row& x = *this;
  const dimension_type old_size = x.size();
  if (new_size < old_size)
    x.shrink(new_size);
  else if (new_size > old_size) {
    Dense_Row y(new_size, Dense_Row::Flags());
    x.m_swap(y);
  }

  for (dimension_type col = 0; col < new_size; ++col)
    if (!(s >> x[col]))
      return false;
  if (!(s >> str) || str != "f")
    return false;
  
  Flags f;
  if (!f.ascii_load(s))
    return false;
  set_flags(f);
  
  return true;
}
bool Parma_Polyhedra_Library::Linear_Row::check_strong_normalized ( ) const

Returns true if and only if the coefficients are strongly normalized.

Definition at line 57 of file Linear_Row.cc.

References strong_normalize().

Referenced by Parma_Polyhedra_Library::Linear_System::add_pending_row(), Parma_Polyhedra_Library::Linear_System::add_row(), Parma_Polyhedra_Library::Linear_System::insert(), and Parma_Polyhedra_Library::Linear_System::insert_pending().

                                             {
  Linear_Row tmp = *this;
  tmp.strong_normalize();
  return compare(*this, tmp) == 0;
}
Coefficient_traits::const_reference Parma_Polyhedra_Library::Linear_Row::coefficient ( dimension_type  n) const
inline

Returns the coefficient $a_n$.

Definition at line 254 of file Linear_Row.inlines.hh.

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

                                                    {
  return (*this)[n+1];
}
const Linear_Row::Flags Parma_Polyhedra_Library::Linear_Row::flags ( ) const
inline

Returns the flags of *this.

Reimplemented from Parma_Polyhedra_Library::Dense_Row.

Definition at line 139 of file Linear_Row.inlines.hh.

References Parma_Polyhedra_Library::Dense_Row::flags().

Referenced by is_line_or_equality(), is_necessarily_closed(), is_ray_or_point_or_inequality(), operator==(), set_is_line_or_equality(), set_is_ray_or_point_or_inequality(), set_necessarily_closed(), set_not_necessarily_closed(), and topology().

                        {
  return Flags(Dense_Row::flags());
}
Coefficient_traits::const_reference Parma_Polyhedra_Library::Linear_Row::inhomogeneous_term ( ) const
inline

Returns the inhomogeneous term.

Reimplemented in Parma_Polyhedra_Library::Linear_Expression, and Parma_Polyhedra_Library::Constraint.

Definition at line 249 of file Linear_Row.inlines.hh.

Referenced by Parma_Polyhedra_Library::Generator::divisor().

                                     {
  return (*this)[0];
}
bool Parma_Polyhedra_Library::Linear_Row::is_line_or_equality ( ) const
inline

Returns true if and only if *this row represents a line or an equality.

Definition at line 206 of file Linear_Row.inlines.hh.

References flags(), and Parma_Polyhedra_Library::Linear_Row::Flags::is_line_or_equality().

Referenced by Parma_Polyhedra_Library::Polyhedron::BFT00_poly_hull_assign_if_exact(), compare(), Parma_Polyhedra_Library::Constraint::is_equality(), Parma_Polyhedra_Library::Generator::is_line(), and sign_normalize().

                                      {
  return flags().is_line_or_equality();
}
bool Parma_Polyhedra_Library::Linear_Row::is_necessarily_closed ( ) const
inline

Returns true if and only if the topology of *this row is necessarily closed.

Definition at line 149 of file Linear_Row.inlines.hh.

References flags(), and Parma_Polyhedra_Library::Linear_Row::Flags::is_necessarily_closed().

Referenced by Parma_Polyhedra_Library::Polyhedron::add_generator(), Parma_Polyhedra_Library::Generator::is_equivalent_to(), Parma_Polyhedra_Library::Generator::OK(), Parma_Polyhedra_Library::Topology_Adjusted_Scalar_Product_Sign::operator()(), Parma_Polyhedra_Library::Scalar_Products::reduced_assign(), Parma_Polyhedra_Library::Polyhedron::refine_no_check(), Parma_Polyhedra_Library::Polyhedron::refine_with_constraints(), space_dimension(), Parma_Polyhedra_Library::Linear_Row::Flags::topology(), Parma_Polyhedra_Library::Constraint::type(), and Parma_Polyhedra_Library::Generator::type().

                                        {
  return flags().is_necessarily_closed();
}
bool Parma_Polyhedra_Library::Linear_Row::is_not_necessarily_closed ( ) const

Returns true if and only if the topology of *this row is not necessarily closed.

Referenced by Parma_Polyhedra_Library::Linear_Row::Flags::is_necessarily_closed().

bool Parma_Polyhedra_Library::Linear_Row::is_ray_or_point_or_inequality ( ) const
inline

Returns true if and only if *this row represents a ray, a point or an inequality.

Definition at line 211 of file Linear_Row.inlines.hh.

References flags(), and Parma_Polyhedra_Library::Linear_Row::Flags::is_ray_or_point_or_inequality().

Referenced by Parma_Polyhedra_Library::Polyhedron::conversion(), Parma_Polyhedra_Library::Constraint::is_inequality(), Parma_Polyhedra_Library::Linear_Row::Flags::is_line_or_equality(), Parma_Polyhedra_Library::Grid_Generator::is_parameter_or_point(), and Parma_Polyhedra_Library::Generator::is_ray_or_point().

                                                {
  return flags().is_ray_or_point_or_inequality();
}
bool Parma_Polyhedra_Library::Linear_Row::is_zero ( ) const

Returns true if and only if all the terms of *this are $0$.

Reimplemented in Parma_Polyhedra_Library::Linear_Expression.

Definition at line 125 of file Linear_Row.cc.

References Parma_Polyhedra_Library::Dense_Row::size().

                             {
  const Linear_Row& x = *this;
  for (dimension_type i = x.size(); i-- > 0; )
    if (x[i] != 0)
      return false;
  return true;
}
void Parma_Polyhedra_Library::Linear_Row::linear_combine ( const Linear_Row &  y,
dimension_type  k 
)

Linearly combines *this with y so that *this[k] is 0.

Parameters:
yThe Linear_Row that will be combined with *this object;
kThe position of *this that have to be $0$.

Computes a linear combination of *this and y having the element of index k equal to $0$. Then it assigns the resulting Linear_Row to *this and normalizes it.

Definition at line 103 of file Linear_Row.cc.

References Parma_Polyhedra_Library::normalize2(), PPL_ASSERT, PPL_DIRTY_TEMP_COEFFICIENT, Parma_Polyhedra_Library::Dense_Row::size(), strong_normalize(), and Parma_Polyhedra_Library::sub_mul_assign().

Referenced by Parma_Polyhedra_Library::Linear_System::back_substitute(), and Parma_Polyhedra_Library::Polyhedron::BHRZ03_evolving_points().

                                                                         {
  Linear_Row& x = *this;
  // We can combine only vector of the same dimension.
  PPL_ASSERT(x.size() == y.size());
  PPL_ASSERT(y[k] != 0 && x[k] != 0);
  // Let g be the GCD between `x[k]' and `y[k]'.
  // For each i the following computes
  //   x[i] = x[i]*y[k]/g - y[i]*x[k]/g.
  PPL_DIRTY_TEMP_COEFFICIENT(normalized_x_k);
  PPL_DIRTY_TEMP_COEFFICIENT(normalized_y_k);
  normalize2(x[k], y[k], normalized_x_k, normalized_y_k);
  for (dimension_type i = size(); i-- > 0; )
    if (i != k) {
      Coefficient& x_i = x[i];
      x_i *= normalized_y_k;
      sub_mul_assign(x_i, y[i], normalized_x_k);
    }
  x[k] = 0;
  x.strong_normalize();
}
dimension_type Parma_Polyhedra_Library::Linear_Row::max_space_dimension ( )
inlinestatic

Returns the maximum space dimension a Linear_Row can handle.

Reimplemented in Parma_Polyhedra_Library::Linear_Expression, Parma_Polyhedra_Library::Generator, Parma_Polyhedra_Library::Constraint, and Parma_Polyhedra_Library::Grid_Generator.

Definition at line 154 of file Linear_Row.inlines.hh.

References Parma_Polyhedra_Library::Dense_Row::max_size().

                                {
  // The first coefficient holds the inhomogeneous term or the divisor.
  // In NNC rows, the last coefficient is for the epsilon dimension.
  return max_size() - 2;
}
bool Parma_Polyhedra_Library::Linear_Row::OK ( ) const

Checks if all the invariants are satisfied.

Reimplemented from Parma_Polyhedra_Library::Dense_Row.

Reimplemented in Parma_Polyhedra_Library::Constraint, Parma_Polyhedra_Library::Generator, Parma_Polyhedra_Library::Grid_Generator, Parma_Polyhedra_Library::Linear_Expression, and Parma_Polyhedra_Library::PIP_Tree_Node::Artificial_Parameter.

Definition at line 253 of file Linear_Row.cc.

References Parma_Polyhedra_Library::Dense_Row::OK().

Referenced by Parma_Polyhedra_Library::Linear_Expression::OK(), Parma_Polyhedra_Library::Generator::OK(), and Parma_Polyhedra_Library::Constraint::OK().

                        {
  return Dense_Row::OK();
}
bool Parma_Polyhedra_Library::Linear_Row::OK ( dimension_type  row_size,
dimension_type  row_capacity 
) const

Checks if all the invariants are satisfied and that the actual size and capacity match the values provided as arguments.

Reimplemented from Parma_Polyhedra_Library::Dense_Row.

Definition at line 258 of file Linear_Row.cc.

References Parma_Polyhedra_Library::Dense_Row::OK().

                                                             {
  return Dense_Row::OK(row_size, row_capacity);
}
void Parma_Polyhedra_Library::Linear_Row::print ( ) const

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

Reimplemented from Parma_Polyhedra_Library::Dense_Row.

Reimplemented in Parma_Polyhedra_Library::Constraint, Parma_Polyhedra_Library::Generator, Parma_Polyhedra_Library::Grid_Generator, Parma_Polyhedra_Library::Linear_Expression, and Parma_Polyhedra_Library::PIP_Tree_Node::Artificial_Parameter.

void Parma_Polyhedra_Library::Linear_Row::set_flags ( Flags  f)
inline

Sets f as the flags of *this.

Definition at line 144 of file Linear_Row.inlines.hh.

Referenced by Parma_Polyhedra_Library::Constraint::Constraint(), Parma_Polyhedra_Library::Generator::Generator(), set_is_line_or_equality(), set_is_ray_or_point_or_inequality(), set_necessarily_closed(), and set_not_necessarily_closed().

                             {
  Dense_Row::set_flags(f);
}
void Parma_Polyhedra_Library::Linear_Row::set_is_line_or_equality ( )
inline

Sets to LINE_OR_EQUALITY the kind of *this row.

Definition at line 221 of file Linear_Row.inlines.hh.

References flags(), set_flags(), and Parma_Polyhedra_Library::Linear_Row::Flags::set_is_line_or_equality().

Referenced by Parma_Polyhedra_Library::Linear_System::add_rows_and_columns(), Parma_Polyhedra_Library::Polyhedron::minimize(), Parma_Polyhedra_Library::Constraint::set_is_equality(), Parma_Polyhedra_Library::Generator::set_is_line(), and Parma_Polyhedra_Library::Polyhedron::simplify_using_context_assign().

                                    {
  Flags f = flags();
  f.set_is_line_or_equality();
  set_flags(f);
}
void Parma_Polyhedra_Library::Linear_Row::set_is_ray_or_point_or_inequality ( )
inline

Sets to RAY_OR_POINT_OR_INEQUALITY the kind of *this row.

Definition at line 228 of file Linear_Row.inlines.hh.

References flags(), set_flags(), and Parma_Polyhedra_Library::Linear_Row::Flags::set_is_ray_or_point_or_inequality().

Referenced by Parma_Polyhedra_Library::Polyhedron::BFT00_poly_hull_assign_if_exact(), Parma_Polyhedra_Library::Constraint::set_is_inequality(), and Parma_Polyhedra_Library::Generator::set_is_ray_or_point().

                                              {
  Flags f = flags();
  f.set_is_ray_or_point_or_inequality();
  set_flags(f);
}
void Parma_Polyhedra_Library::Linear_Row::set_necessarily_closed ( )
inline

Sets to NECESSARILY_CLOSED the topological kind of *this row.

Definition at line 235 of file Linear_Row.inlines.hh.

References flags(), set_flags(), and Parma_Polyhedra_Library::Linear_Row::Flags::set_necessarily_closed().

                                   {
  Flags f = flags();
  f.set_necessarily_closed();
  set_flags(f);
}
void Parma_Polyhedra_Library::Linear_Row::set_not_necessarily_closed ( )
inline

Sets to NOT_NECESSARILY_CLOSED the topological kind of *this row.

Definition at line 242 of file Linear_Row.inlines.hh.

References flags(), set_flags(), and Parma_Polyhedra_Library::Linear_Row::Flags::set_not_necessarily_closed().

Referenced by Parma_Polyhedra_Library::Generator::closure_point(), and Parma_Polyhedra_Library::Constraint::operator>().

                                       {
  Flags f = flags();
  f.set_not_necessarily_closed();
  set_flags(f);
}
void Parma_Polyhedra_Library::Linear_Row::sign_normalize ( )

Normalizes the sign of the coefficients so that the first non-zero (homogeneous) coefficient of a line-or-equality is positive.

Definition at line 33 of file Linear_Row.cc.

References is_line_or_equality(), Parma_Polyhedra_Library::neg_assign(), and Parma_Polyhedra_Library::Dense_Row::size().

Referenced by Parma_Polyhedra_Library::Polyhedron::BFT00_poly_hull_assign_if_exact(), Parma_Polyhedra_Library::Polyhedron::simplify_using_context_assign(), and strong_normalize().

                              {
  if (is_line_or_equality()) {
    Linear_Row& x = *this;
    const dimension_type sz = x.size();
    // `first_non_zero' indicates the index of the first
    // coefficient of the row different from zero, disregarding
    // the very first coefficient (inhomogeneous term / divisor).
    dimension_type first_non_zero;
    for (first_non_zero = 1; first_non_zero < sz; ++first_non_zero)
      if (x[first_non_zero] != 0)
        break;
    if (first_non_zero < sz)
      // If the first non-zero coefficient of the row is negative,
      // we negate the entire row.
      if (x[first_non_zero] < 0) {
        for (dimension_type j = first_non_zero; j < sz; ++j)
          neg_assign(x[j]);
        // Also negate the first coefficient.
        neg_assign(x[0]);
      }
  }
}
dimension_type Parma_Polyhedra_Library::Linear_Row::space_dimension ( ) const
inline

Returns the dimension of the vector space enclosing *this.

Reimplemented in Parma_Polyhedra_Library::Linear_Expression, Parma_Polyhedra_Library::Generator, Parma_Polyhedra_Library::Constraint, and Parma_Polyhedra_Library::Grid_Generator.

Definition at line 161 of file Linear_Row.inlines.hh.

References is_necessarily_closed(), and Parma_Polyhedra_Library::Dense_Row::size().

                                  {
  const dimension_type sz = size();
  return (sz == 0)
    ? 0
    : (sz - (is_necessarily_closed() ? 1U : 2U));
}
void Parma_Polyhedra_Library::Linear_Row::strong_normalize ( )
inline

Strong normalization: ensures that different Linear_Row objects represent different hyperplanes or hyperspaces.

Applies both Linear_Row::normalize() and Linear_Row::sign_normalize().

Reimplemented in Parma_Polyhedra_Library::Grid_Generator.

Definition at line 259 of file Linear_Row.inlines.hh.

References Parma_Polyhedra_Library::Dense_Row::normalize(), and sign_normalize().

Referenced by Parma_Polyhedra_Library::Polyhedron::add_congruence(), Parma_Polyhedra_Library::Polyhedron::add_congruences(), check_strong_normalized(), Parma_Polyhedra_Library::Constraint::Constraint(), Parma_Polyhedra_Library::Polyhedron::conversion(), Parma_Polyhedra_Library::Generator::line(), linear_combine(), Parma_Polyhedra_Library::Generator::OK(), Parma_Polyhedra_Library::Constraint::OK(), Parma_Polyhedra_Library::Constraint::operator==(), Parma_Polyhedra_Library::Polyhedron::refine_with_congruence(), and Parma_Polyhedra_Library::Polyhedron::refine_with_congruences().

                             {
  normalize();
  sign_normalize();
}
Topology Parma_Polyhedra_Library::Linear_Row::topology ( ) const
inline

Returns the topological kind of *this.

Definition at line 216 of file Linear_Row.inlines.hh.

References flags(), and Parma_Polyhedra_Library::Linear_Row::Flags::topology().

Referenced by Parma_Polyhedra_Library::Constraint_System::insert(), Parma_Polyhedra_Library::Generator_System::insert(), Parma_Polyhedra_Library::Linear_System::insert(), Parma_Polyhedra_Library::Linear_System::insert_pending(), Parma_Polyhedra_Library::Constraint_System::insert_pending(), Parma_Polyhedra_Library::Generator_System::insert_pending(), and Parma_Polyhedra_Library::Generator::is_matching_closure_point().

                           {
  return flags().topology();
}

Friends And Related Function Documentation

int compare ( const Linear_Row &  x,
const Linear_Row &  y 
)
related

Definition at line 65 of file Linear_Row.cc.

References Parma_Polyhedra_Library::cmp(), is_line_or_equality(), Parma_Polyhedra_Library::Boundary_NS::sgn(), and Parma_Polyhedra_Library::Dense_Row::size().

                                                     {
  const bool x_is_line_or_equality = x.is_line_or_equality();
  const bool y_is_line_or_equality = y.is_line_or_equality();
  if (x_is_line_or_equality != y_is_line_or_equality)
    // Equalities (lines) precede inequalities (ray/point).
    return y_is_line_or_equality ? 2 : -2;

  // Compare all the coefficients of the row starting from position 1.
  const dimension_type xsz = x.size();
  const dimension_type ysz = y.size();
  const dimension_type min_sz = std::min(xsz, ysz);
  dimension_type i;
  for (i = 1; i < min_sz; ++i)
    if (const int comp = cmp(x[i], y[i]))
      // There is at least a different coefficient.
      return (comp > 0) ? 2 : -2;

  // Handle the case where `x' and `y' are of different size.
  if (xsz != ysz) {
    for( ; i < xsz; ++i)
      if (const int sign = sgn(x[i]))
        return (sign > 0) ? 2 : -2;
    for( ; i < ysz; ++i)
      if (const int sign = sgn(y[i]))
        return (sign < 0) ? 2 : -2;
  }

  // If all the coefficients in `x' equal all the coefficients in `y'
  // (starting from position 1) we compare coefficients in position 0,
  // i.e., inhomogeneous terms.
  if (const int comp = cmp(x[0], y[0]))
    return (comp > 0) ? 1 : -1;

  // `x' and `y' are equal.
  return 0;
}
int compare ( const Linear_Row &  x,
const Linear_Row &  y 
)
related

The basic comparison function.

Returns:
The returned absolute value can be $0$, $1$ or $2$.
Parameters:
xA row of coefficients;
yAnother row.

Compares x and y, where x and y may be of different size, in which case the "missing" coefficients are assumed to be zero. The comparison is such that:

  1. equalities are smaller than inequalities;
  2. lines are smaller than points and rays;
  3. the ordering is lexicographic;
  4. the positions compared are, in decreasing order of significance, 1, 2, ..., size(), 0;
  5. the result is negative, zero, or positive if x is smaller than, equal to, or greater than y, respectively;
  6. when x and y are different, the absolute value of the result is 1 if the difference is due to the coefficient in position 0; it is 2 otherwise.

When x and y represent the hyper-planes associated to two equality or inequality constraints, the coefficient at 0 is the known term. In this case, the return value can be characterized as follows:

  • -2, if x is smaller than y and they are not parallel;
  • -1, if x is smaller than y and they are parallel;
  • 0, if x and y are equal;
  • +1, if y is smaller than x and they are parallel;
  • +2, if y is smaller than x and they are not parallel.
void iter_swap ( std::vector< Linear_Row >::iterator  x,
std::vector< Linear_Row >::iterator  y 
)
related

Definition at line 285 of file Linear_Row.inlines.hh.

References Parma_Polyhedra_Library::swap().

                                           {
  swap(*x, *y);
}
void iter_swap ( std::vector< Linear_Row >::iterator  x,
std::vector< Linear_Row >::iterator  y 
)
related

Swaps the objects referred by x and y.

bool operator!= ( const Linear_Row &  x,
const Linear_Row &  y 
)
related

Definition at line 273 of file Linear_Row.inlines.hh.

                                                     {
  return !(x == y);
}
bool operator!= ( const Linear_Row &  x,
const Linear_Row &  y 
)
related

Returns true if and only if x and y are different.

bool operator== ( const Linear_Row &  x,
const Linear_Row &  y 
)
related

Definition at line 266 of file Linear_Row.inlines.hh.

References flags().

                                                     {
  return x.flags() == y.flags()
    && static_cast<const Dense_Row&>(x) == static_cast<const Dense_Row&>(y);
}
template<typename C >
bool operator== ( const Linear_Form< C > &  x,
const Linear_Form< C > &  y 
)
related

Definition at line 328 of file Linear_Form.templates.hh.

References Parma_Polyhedra_Library::Linear_Form< C >::size(), and Parma_Polyhedra_Library::Linear_Form< C >::zero.

Referenced by Parma_Polyhedra_Library::Linear_Row::Flags::operator!=().

                                                             {
  const dimension_type x_size = x.size();
  const dimension_type y_size = y.size();
  if (x_size >= y_size) {
    for (dimension_type i = y_size; i-- > 0; )
      if (x[i] != y[i])
        return false;

    for (dimension_type i = x_size; --i >= y_size; )
      if (x[i] != x.zero)
        return false;

  }
  else {
    for (dimension_type i = x_size; i-- > 0; )
      if (x[i] != y[i])
        return false;

    for (dimension_type i = y_size; --i >= x_size; )
      if (y[i] != x.zero)
        return false;

  }

  return true;
}
bool operator== ( const Linear_Row &  x,
const Linear_Row &  y 
)
related

Returns true if and only if x and y are equal.

friend class Parma_Polyhedra_Library::Constraint
friend

Reimplemented in Parma_Polyhedra_Library::Linear_Expression.

Definition at line 372 of file Linear_Row.defs.hh.

friend class Parma_Polyhedra_Library::Generator
friend

Reimplemented in Parma_Polyhedra_Library::Linear_Expression.

Definition at line 373 of file Linear_Row.defs.hh.

friend class Parma_Polyhedra_Library::Linear_Expression
friend

Definition at line 371 of file Linear_Row.defs.hh.

void swap ( Linear_Row &  x,
Linear_Row &  y 
)
related

Definition at line 279 of file Linear_Row.inlines.hh.

References Parma_Polyhedra_Library::Dense_Row::m_swap().

                                   {
  x.m_swap(y);
}
void swap ( Linear_Row &  x,
Linear_Row &  y 
)
related

Swaps x with y.

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