Parma_Polyhedra_Library::Bounding_Box Class Reference
[C++ Language Interface]

A not necessarily closed bounding-box. More...

#include <Bounding_Box.defs.hh>

Collaboration diagram for Parma_Polyhedra_Library::Bounding_Box:

Collaboration graph
[legend]

List of all members.

Public Member Functions

 Bounding_Box (dimension_type num_dimensions)
 Constructs a universe bounding box of dimension num_dimensions.
dimension_type space_dimension () const
 Returns the dimension of the vector space enclosing *this.
const Intervaloperator[] (dimension_type k) const
 Returns a reference the interval that bounds the box on the k-th space dimension.
bool is_empty () const
 Returns true if and only if *this is empty.
bool get_lower_bound (dimension_type k, bool &closed, Coefficient &n, Coefficient &d) const
 If the k-th space dimension is unbounded below, returns false. Otherwise returns true and set closed, n and d accordingly.
bool get_upper_bound (dimension_type k, bool &closed, Coefficient &n, Coefficient &d) const
 If the k-th space dimension is unbounded above, returns false. Otherwise returns true and set closed, n and d accordingly.
void set_empty ()
 Causes the box to become empty, i.e., to represent the empty set.
void raise_lower_bound (dimension_type k, bool closed, Coefficient_traits::const_reference n, Coefficient_traits::const_reference d)
 Raises the lower bound of the interval corresponding to the k-th space dimension.
void lower_upper_bound (dimension_type k, bool closed, Coefficient_traits::const_reference n, Coefficient_traits::const_reference d)
 Lowers the upper bound of the interval corresponding to the k-th space dimension.
Constraint_System constraints () const
 Returns a system of constraints corresponding to *this.
void CC76_widening_assign (const Bounding_Box &y)
 Assigns to *this the result of computing the CC76-widening between *this and y.
template<typename Iterator>
void CC76_widening_assign (const Bounding_Box &y, Iterator first, Iterator last)
 Assigns to *this the result of computing the CC76-widening between *this and y.

Private Attributes

std::vector< Intervalvec
 A vector of rational intervals, one for each dimension of the vector space.
bool empty
 A boolean flag indicating emptiness of the bounding box. Only meaningful when empty_up_to_date is true.
bool empty_up_to_date
 Tells whether or not the flag empty is meaningful.

Static Private Attributes

static ERational default_stop_points []
 Records the stop points for CC76_widening_assign(const Bounding_Box&).

Related Functions

(Note that these are not member functions.)

std::ostream & operator<< (std::ostream &s, const Bounding_Box &bbox)
 Output operator.


Detailed Description

A not necessarily closed bounding-box.

A Bounding_Box object represents the Cartesian product of $n$ not necessarily closed and possibly unbounded intervals, where $n$ is the space dimension of the box.

Definition at line 44 of file Bounding_Box.defs.hh.


Constructor & Destructor Documentation

Parma_Polyhedra_Library::Bounding_Box::Bounding_Box ( dimension_type  num_dimensions  )  [inline]

Constructs a universe bounding box of dimension num_dimensions.

Definition at line 29 of file Bounding_Box.inlines.hh.

00030   : vec(num_dimensions), empty(false), empty_up_to_date(true) {
00031 }


Member Function Documentation

dimension_type Parma_Polyhedra_Library::Bounding_Box::space_dimension (  )  const [inline]

Returns the dimension of the vector space enclosing *this.

Definition at line 34 of file Bounding_Box.inlines.hh.

References vec.

Referenced by constraints(), and operator<<().

00034                                     {
00035   return vec.size();
00036 }

const Interval & Parma_Polyhedra_Library::Bounding_Box::operator[] ( dimension_type  k  )  const [inline]

Returns a reference the interval that bounds the box on the k-th space dimension.

Definition at line 39 of file Bounding_Box.inlines.hh.

References vec.

00039                                                      {
00040   assert(k < vec.size());
00041   return vec[k];
00042 }

bool Parma_Polyhedra_Library::Bounding_Box::is_empty (  )  const [inline]

Returns true if and only if *this is empty.

Definition at line 45 of file Bounding_Box.inlines.hh.

References empty, empty_up_to_date, and vec.

Referenced by constraints(), and operator<<().

00045                              {
00046   if (empty_up_to_date)
00047     return empty;
00048   else {
00049     empty_up_to_date = true;
00050     for (dimension_type k = vec.size(); k-- > 0; )
00051       if (vec[k].is_empty()) {
00052         empty = true;
00053         return true;
00054       }
00055     empty = false;
00056     return false;
00057   }
00058 }

bool Parma_Polyhedra_Library::Bounding_Box::get_lower_bound ( dimension_type  k,
bool &  closed,
Coefficient n,
Coefficient d 
) const [inline]

If the k-th space dimension is unbounded below, returns false. Otherwise returns true and set closed, n and d accordingly.

Let $I$ the interval corresponding to the k-th space dimension. If $I$ is not bounded from below, simply return false. Otherwise, set closed, n and d as follows: closed is set to true if the the lower boundary of $I$ is closed and is set to false otherwise; n and d are assigned the integers $n$ and $d$ such that the canonical fraction $n/d$ corresponds to the greatest lower bound of $I$. The fraction $n/d$ is in canonical form if and only if $n$ and $d$ have no common factors and $d$ is positive, $0/1$ being the unique representation for zero.

An undefined behavior is obtained if k is greater than or equal to the space dimension of *this.

Definition at line 61 of file Bounding_Box.inlines.hh.

References Parma_Polyhedra_Library::is_minus_infinity(), Parma_Polyhedra_Library::is_plus_infinity(), Parma_Polyhedra_Library::raw_value(), and vec.

Referenced by constraints(), and operator<<().

00062                                                                     {
00063   assert(k < vec.size());
00064   const LBoundary& lb = vec[k].lower_bound();
00065   const ERational& lr = lb.bound();
00066 
00067   if (is_plus_infinity(lr) || is_minus_infinity(lr))
00068     return false;
00069 
00070   closed = lb.is_closed();
00071   n = raw_value(lr).get_num();
00072   d = raw_value(lr).get_den();
00073 
00074   return true;
00075 }

bool Parma_Polyhedra_Library::Bounding_Box::get_upper_bound ( dimension_type  k,
bool &  closed,
Coefficient n,
Coefficient d 
) const [inline]

If the k-th space dimension is unbounded above, returns false. Otherwise returns true and set closed, n and d accordingly.

Let $I$ the interval corresponding to the k-th space dimension. If $I$ is not bounded from above, simply return false. Otherwise, set closed, n and d as follows: closed is set to true if the the upper boundary of $I$ is closed and is set to false otherwise; n and d are assigned the integers $n$ and $d$ such that the canonical fraction $n/d$ corresponds to the least upper bound of $I$.

An undefined behavior is obtained if k is greater than or equal to the space dimension of *this.

Definition at line 78 of file Bounding_Box.inlines.hh.

References Parma_Polyhedra_Library::is_minus_infinity(), Parma_Polyhedra_Library::is_plus_infinity(), Parma_Polyhedra_Library::raw_value(), and vec.

Referenced by constraints(), and operator<<().

00079                                                                    {
00080   assert(k < vec.size());
00081   const UBoundary& ub = vec[k].upper_bound();
00082   const ERational& ur = ub.bound();
00083 
00084   if (is_plus_infinity(ur) || is_minus_infinity(ur))
00085     return false;
00086 
00087   closed = ub.is_closed();
00088   n = raw_value(ur).get_num();
00089   d = raw_value(ur).get_den();
00090 
00091   return true;
00092 }

void Parma_Polyhedra_Library::Bounding_Box::set_empty (  )  [inline]

Causes the box to become empty, i.e., to represent the empty set.

Definition at line 95 of file Bounding_Box.inlines.hh.

References empty, empty_up_to_date, and vec.

Referenced by ppl_new_C_Polyhedron_from_bounding_box(), and ppl_new_NNC_Polyhedron_from_bounding_box().

00095                         {
00096   for (dimension_type k = vec.size(); k-- > 0; )
00097     vec[k].set_empty();
00098   empty = empty_up_to_date = true;
00099 }

void Parma_Polyhedra_Library::Bounding_Box::raise_lower_bound ( dimension_type  k,
bool  closed,
Coefficient_traits::const_reference  n,
Coefficient_traits::const_reference  d 
) [inline]

Raises the lower bound of the interval corresponding to the k-th space dimension.

Intersects the interval corresponding to the k-th space dimension with $[n/d, +\infty)$ if closed is true, with $(n/d, +\infty)$ if closed is false. An undefined behavior is obtained if k is greater than or equal to the space dimension of *this or if d is equal to zero.

Definition at line 102 of file Bounding_Box.inlines.hh.

References Parma_Polyhedra_Library::assign_r(), Parma_Polyhedra_Library::LBoundary::CLOSED, empty_up_to_date, Parma_Polyhedra_Library::LBoundary::OPEN, and vec.

Referenced by ppl_new_C_Polyhedron_from_bounding_box(), and ppl_new_NNC_Polyhedron_from_bounding_box().

00104                                                                      {
00105   assert(k < vec.size());
00106   assert(d != 0);
00107   mpq_class q;
00108   assign_r(q.get_num(), n, ROUND_NOT_NEEDED);
00109   assign_r(q.get_den(), d, ROUND_NOT_NEEDED);
00110   q.canonicalize();
00111   vec[k].raise_lower_bound(LBoundary(ERational(q, ROUND_NOT_NEEDED),
00112                                      (closed
00113                                       ? LBoundary::CLOSED
00114                                       : LBoundary::OPEN)));
00115   empty_up_to_date = false;
00116 }

void Parma_Polyhedra_Library::Bounding_Box::lower_upper_bound ( dimension_type  k,
bool  closed,
Coefficient_traits::const_reference  n,
Coefficient_traits::const_reference  d 
) [inline]

Lowers the upper bound of the interval corresponding to the k-th space dimension.

Intersects the interval corresponding to the k-th space dimension with $(-\infty, n/d]$ if closed is true, with $(-\infty, n/d)$ if closed is false. An undefined behavior is obtained if k is greater than or equal to the space dimension of *this or if d is equal to zero.

Definition at line 119 of file Bounding_Box.inlines.hh.

References Parma_Polyhedra_Library::assign_r(), Parma_Polyhedra_Library::UBoundary::CLOSED, empty_up_to_date, Parma_Polyhedra_Library::UBoundary::OPEN, and vec.

Referenced by ppl_new_C_Polyhedron_from_bounding_box(), and ppl_new_NNC_Polyhedron_from_bounding_box().

00121                                                                      {
00122   assert(k < vec.size());
00123   assert(d != 0);
00124   mpq_class q;
00125   assign_r(q.get_num(), n, ROUND_NOT_NEEDED);
00126   assign_r(q.get_den(), d, ROUND_NOT_NEEDED);
00127   q.canonicalize();
00128   vec[k].lower_upper_bound(UBoundary(ERational(q, ROUND_NOT_NEEDED),
00129                                      (closed
00130                                       ? UBoundary::CLOSED
00131                                       : UBoundary::OPEN)));
00132   empty_up_to_date = false;
00133 }

PPL::Constraint_System Parma_Polyhedra_Library::Bounding_Box::constraints (  )  const

Returns a system of constraints corresponding to *this.

Definition at line 91 of file Bounding_Box.cc.

References get_lower_bound(), get_upper_bound(), Parma_Polyhedra_Library::Constraint_System::insert(), is_empty(), space_dimension(), and Parma_Polyhedra_Library::Constraint_System::zero_dim_empty().

Referenced by Parma_Polyhedra_Library::Polyhedron::bounded_BHRZ03_extrapolation_assign(), and Parma_Polyhedra_Library::Polyhedron::bounded_H79_extrapolation_assign().

00091                                    {
00092   Constraint_System cs;
00093   dimension_type space_dim = space_dimension();
00094   if (space_dim == 0) {
00095     if (is_empty())
00096       cs = Constraint_System::zero_dim_empty();
00097   }
00098   else if (is_empty())
00099     cs.insert(0*Variable(space_dim-1) <= -1);
00100   else {
00101     // KLUDGE: in the future `cs' will be constructed of the right dimension.
00102     // For the time being, we force the dimension with the following line.
00103     cs.insert(0*Variable(space_dim-1) <= 0);
00104 
00105     for (dimension_type k = 0; k < space_dim; ++k) {
00106       bool closed = false;
00107       PPL::Coefficient n;
00108       PPL::Coefficient d;
00109       if (get_lower_bound(k, closed, n, d)) {
00110         if (closed)
00111           cs.insert(d*Variable(k) >= n);
00112         else
00113           cs.insert(d*Variable(k) > n);
00114       }
00115       if (get_upper_bound(k, closed, n, d)) {
00116         if (closed)
00117           cs.insert(d*Variable(k) <= n);
00118         else
00119           cs.insert(d*Variable(k) < n);
00120       }
00121     }
00122   }
00123   return cs;
00124 }

void Parma_Polyhedra_Library::Bounding_Box::CC76_widening_assign ( const Bounding_Box y  ) 

Assigns to *this the result of computing the CC76-widening between *this and y.

Parameters:
y A bounding box that must be contained in *this.
Exceptions:
std::invalid_argument Thrown if *this and y are dimension-incompatible.

Definition at line 76 of file Bounding_Box.cc.

Referenced by Parma_Polyhedra_Library::Polyhedron::bounded_BHRZ03_extrapolation_assign(), and Parma_Polyhedra_Library::Polyhedron::bounded_H79_extrapolation_assign().

00076                                                            {
00077   static ERational stop_points[] = {
00078     ERational(-2, ROUND_NOT_NEEDED),
00079     ERational(-1, ROUND_NOT_NEEDED),
00080     ERational(0, ROUND_NOT_NEEDED),
00081     ERational(1, ROUND_NOT_NEEDED),
00082     ERational(2, ROUND_NOT_NEEDED)
00083   };
00084   CC76_widening_assign(y,
00085                        stop_points,
00086                        stop_points
00087                        + sizeof(stop_points)/sizeof(stop_points[0]));
00088 }

template<typename Iterator>
void Parma_Polyhedra_Library::Bounding_Box::CC76_widening_assign ( const Bounding_Box y,
Iterator  first,
Iterator  last 
) [inline]

Assigns to *this the result of computing the CC76-widening between *this and y.

Parameters:
y A bounding box that must be contained in *this.
first An iterator that points to the first stop-point.
last An iterator that points one past the last stop-point.
Exceptions:
std::invalid_argument Thrown if *this and y are dimension-incompatible.

Definition at line 34 of file Bounding_Box.cc.

References Parma_Polyhedra_Library::Boundary::bound(), Parma_Polyhedra_Library::Interval::lower_bound(), Parma_Polyhedra_Library::MINUS_INFINITY, Parma_Polyhedra_Library::LBoundary::OPEN, Parma_Polyhedra_Library::UBoundary::OPEN, Parma_Polyhedra_Library::PLUS_INFINITY, Parma_Polyhedra_Library::Interval::upper_bound(), and vec.

00035                                                                        {
00036   for (dimension_type i = vec.size(); i-- > 0; ) {
00037     Interval& x_vec_i = vec[i];
00038     const Interval& y_vec_i = y.vec[i];
00039 
00040     // Upper bound.
00041     UBoundary& x_ub = x_vec_i.upper_bound();
00042     ERational& x_ubb = x_ub.bound();
00043     const ERational& y_ubb = y_vec_i.upper_bound().bound();
00044     assert(y_ubb <= x_ubb);
00045     if (y_ubb < x_ubb) {
00046       Iterator k = std::lower_bound(first, last, x_ubb);
00047       if (k != last) {
00048         if (x_ubb < *k)
00049           x_ubb = *k;
00050       }
00051       else
00052         x_ub = UBoundary(ERational(PLUS_INFINITY), UBoundary::OPEN);
00053     }
00054 
00055     // Lower bound.
00056     LBoundary& x_lb = x_vec_i.lower_bound();
00057     ERational& x_lbb = x_lb.bound();
00058     const ERational& y_lbb = y_vec_i.lower_bound().bound();
00059     assert(y_lbb >= x_lbb);
00060     if (y_lbb > x_lbb) {
00061       Iterator k = std::lower_bound(first, last, x_lbb);
00062       if (k != last) {
00063         if (x_lbb < *k)
00064           if (k != first)
00065             x_lbb = *--k;
00066           else
00067             x_lb = LBoundary(ERational(MINUS_INFINITY), LBoundary::OPEN);
00068       }
00069       else
00070         x_lbb = *--k;
00071     }
00072   }
00073 }


Friends And Related Function Documentation

std::ostream & operator<< ( std::ostream &  s,
const Bounding_Box bbox 
) [related]

Output operator.

Definition at line 128 of file Bounding_Box.cc.

References get_lower_bound(), get_upper_bound(), is_empty(), and space_dimension().

00128                                                                       {
00129   if (bbox.is_empty()) {
00130     s << "empty";
00131     return s;
00132   }
00133   const dimension_type dimension = bbox.space_dimension();
00134   for (dimension_type k = 0; k < dimension; ++k) {
00135     bool closed = false;
00136     PPL::Coefficient n;
00137     PPL::Coefficient d;
00138     if (bbox.get_lower_bound(k, closed, n, d)) {
00139       s << (closed ? "[" : "(")
00140         << n;
00141       if (d != 1)
00142         s << "/" << d;
00143       s << ", ";
00144     }
00145     else
00146       s << "(-inf, ";
00147     if (bbox.get_upper_bound(k, closed, n, d)) {
00148       s << n;
00149       if (d != 1)
00150         s << "/" << d;
00151       s << (closed ? "]" : ")");
00152     }
00153     else
00154       s << "+inf)";
00155     s << "\n";
00156   }
00157   return s;
00158 }


Member Data Documentation

A vector of rational intervals, one for each dimension of the vector space.

Definition at line 180 of file Bounding_Box.defs.hh.

Referenced by CC76_widening_assign(), get_lower_bound(), get_upper_bound(), is_empty(), lower_upper_bound(), operator[](), raise_lower_bound(), set_empty(), and space_dimension().

A boolean flag indicating emptiness of the bounding box. Only meaningful when empty_up_to_date is true.

Definition at line 185 of file Bounding_Box.defs.hh.

Referenced by is_empty(), and set_empty().

Tells whether or not the flag empty is meaningful.

Definition at line 187 of file Bounding_Box.defs.hh.

Referenced by is_empty(), lower_upper_bound(), raise_lower_bound(), and set_empty().

Records the stop points for CC76_widening_assign(const Bounding_Box&).

Definition at line 190 of file Bounding_Box.defs.hh.


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

Generated on Wed Jul 16 22:55:50 2008 for PPL by  doxygen 1.5.6