#include <Bounding_Box.defs.hh>
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 Interval & | operator[] (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< Interval > | vec |
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. |
A Bounding_Box object represents the Cartesian product of not necessarily closed and possibly unbounded intervals, where
is the space dimension of the box.
Definition at line 44 of file Bounding_Box.defs.hh.
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 }
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.
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 the interval corresponding to the
k
-th space dimension. If 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 is closed and is set to
false
otherwise; n
and d
are assigned the integers and
such that the canonical fraction
corresponds to the greatest lower bound of
. The fraction
is in canonical form if and only if
and
have no common factors and
is positive,
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 the interval corresponding to the
k
-th space dimension. If 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 is closed and is set to
false
otherwise; n
and d
are assigned the integers and
such that the canonical fraction
corresponds to the least upper bound of
.
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 if
closed
is true
, with 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 if
closed
is true
, with 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
.
y | A bounding box that must be contained in *this . |
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 }
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
.
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. |
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 }
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 }
std::vector<Interval> Parma_Polyhedra_Library::Bounding_Box::vec [private] |
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().
bool Parma_Polyhedra_Library::Bounding_Box::empty [mutable, private] |
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().
bool Parma_Polyhedra_Library::Bounding_Box::empty_up_to_date [mutable, private] |
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().
ERational Parma_Polyhedra_Library::Bounding_Box::default_stop_points[] [static, private] |
Records the stop points for CC76_widening_assign(const Bounding_Box&).
Definition at line 190 of file Bounding_Box.defs.hh.