Module: ppl/ppl Branch: products Commit: 46be509da515e0e7f8909d4a31846876b00bfa02 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=46be509da515e...

Author: Patricia Hill p.m.hill@leeds.ac.uk Date: Fri May 22 15:32:07 2009 +0100

Added the method frequency() to the Box domain.

---

src/Box.defs.hh | 33 ++++++++ src/Box.templates.hh | 73 ++++++++++++++++ tests/Box/Makefile.am | 3 + tests/Box/frequency1.cc | 210 +++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 319 insertions(+), 0 deletions(-)

diff --git a/src/Box.defs.hh b/src/Box.defs.hh index 2981336..217f55d 100644 --- a/src/Box.defs.hh +++ b/src/Box.defs.hh @@ -682,6 +682,39 @@ public: Generator& g) const;

/*! \brief + Returns <CODE>true</CODE> if and only if \p *this is not empty and + \p expr is discrete in \p *this, in which case the maximum frequency + and the value for \p expr that is closest to zero are computed. + + \param expr + The linear expression for which the frequency is needed; + + \param freq_n + The numerator of the maximum frequency of \p expr; + + \param freq_d + The denominator of the maximum frequency of \p expr; + + \param val_n + The numerator of a value of \p expr at a point in the grid + that is closest to zero; + + \param val_d + The denominator of a value of \p expr at a point in the grid + that is closest to zero; + + \exception std::invalid_argument + Thrown if \p expr and \p *this are dimension-incompatible. + + If \p *this is empty or \p expr can take any real number in \p *this, + <CODE>false</CODE> is returned and \p freq_n, \p freq_d, + \p val_n and \p val_d are left untouched. + */ + bool frequency(const Linear_Expression& expr, + Coefficient& freq_n, Coefficient& freq_d, + Coefficient& val_n, Coefficient& val_d) const; + + /*! \brief Returns <CODE>true</CODE> if and only if \p *this contains \p y.

\exception std::invalid_argument diff --git a/src/Box.templates.hh b/src/Box.templates.hh index 9918363..232b42d 100644 --- a/src/Box.templates.hh +++ b/src/Box.templates.hh @@ -1355,6 +1355,79 @@ Box<ITV>::contains_integer_point() const {

template <typename ITV> bool +Box<ITV>::frequency(const Linear_Expression& expr, + Coefficient& freq_n, Coefficient& freq_d, + Coefficient& val_n, Coefficient& val_d) const { + dimension_type space_dim = space_dimension(); + // The dimension of `expr' must be at most the dimension of *this. + if (space_dim < expr.space_dimension()) + throw_dimension_incompatible("frequency(e, ...)", "e", expr); + + // Check if `expr' has a constant value. + // If it is constant, set the frequency `freq_n' to 0 + // and return true. Otherwise the values for \p expr + // are not discrete so return false. + + // Space dimension = 0: if empty, then return false; + // otherwise the frequency is 0 and the value is the inhomogeneous term. + if (space_dim == 0) { + if (is_empty()) + return false; + freq_n = 0; + freq_d = 1; + val_n = expr.inhomogeneous_term(); + val_d = 1; + return true; + } + + // For an empty Box, we simply return false. + if (marked_empty()) + return false; + + // The Box has at least 1 dimension and is not empty. + PPL_DIRTY_TEMP_COEFFICIENT(coeff); + PPL_DIRTY_TEMP_COEFFICIENT(num); + PPL_DIRTY_TEMP_COEFFICIENT(den); + PPL_DIRTY_TEMP0(mpq_class, tmp); + Linear_Expression le = expr; + + PPL_DIRTY_TEMP_COEFFICIENT(val_den); + val_den = 1; + + for (dimension_type i = space_dim; i-- > 0; ) { + const Variable v(i); + coeff = le.coefficient(v); + if (coeff == 0) { + continue; + } + + const ITV& seq_i = seq[i]; + // Check if `v' is constant in the BD shape. + if (seq_i.is_singleton()) { + // If `v' is constant, replace it in `le' by the value. + assign_r(tmp, seq_i.lower(), ROUND_NOT_NEEDED); + num = tmp.get_num(); + den = tmp.get_den(); + le -= coeff*v; + le = den*le + num*coeff; + val_den *= den; + continue; + } + // The expression `expr' is not constant. + return false; + } + + // The expression `expr' is constant. + freq_n = 0; + freq_d = 1; + + // Reduce `val_n' and `val_d'. + normalize2(le.inhomogeneous_term(), val_den, val_n, val_d); + return true; +} + +template <typename ITV> +bool Box<ITV>::constrains(Variable var) const { // `var' should be one of the dimensions of the polyhedron. const dimension_type var_space_dim = var.space_dimension(); diff --git a/tests/Box/Makefile.am b/tests/Box/Makefile.am index 965ee15..bd37972 100644 --- a/tests/Box/Makefile.am +++ b/tests/Box/Makefile.am @@ -77,6 +77,7 @@ empty1 \ equality1 \ expandspacedim1 \ foldspacedims1 \ +frequency1 \ frombdshape1 \ frombox1 \ fromgensys1 \ @@ -211,6 +212,8 @@ expandspacedim1_SOURCES = expandspacedim1.cc

foldspacedims1_SOURCES = foldspacedims1.cc

+frequency1_SOURCES = frequency1.cc + frombdshape1_SOURCES = frombdshape1.cc

frombox1_SOURCES = frombox1.cc diff --git a/tests/Box/frequency1.cc b/tests/Box/frequency1.cc new file mode 100644 index 0000000..9b03553 --- /dev/null +++ b/tests/Box/frequency1.cc @@ -0,0 +1,210 @@ +/* Test Box::frequency(). + Copyright (C) 2001-2009 Roberto Bagnara bagnara@cs.unipr.it + +This file is part of the Parma Polyhedra Library (PPL). + +The PPL is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by the +Free Software Foundation; either version 3 of the License, or (at your +option) any later version. + +The PPL is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software Foundation, +Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA. + +For the most up-to-date information see the Parma Polyhedra Library +site: http://www.cs.unipr.it/ppl/ . */ + +#include "ppl_test.hh" + +using namespace Parma_Polyhedra_Library::IO_Operators; + +namespace { + +// Universe and empty bd shape. +bool +test01() { + Variable A(0); + + TBox box1(1); + + TBox box2(1, EMPTY); + + Coefficient num1; + Coefficient den1; + Coefficient valn1; + Coefficient vald1; + Coefficient num2; + Coefficient den2; + Coefficient valn2; + Coefficient vald2; + bool ok = (!box1.frequency(A, num1, den1, valn1, vald1) + && !box2.frequency(A, num2, den2, valn2, vald2)); + print_constraints(box1, "*** box1 ***"); + print_constraints(box2, "*** box2 ***"); + + return ok; +} + +// 0-dimension polyhedra. +bool +test02() { + TBox box1(0); + + TBox box2(0, EMPTY); + + Coefficient num1; + Coefficient den1; + Coefficient valn1; + Coefficient vald1; + Coefficient num2; + Coefficient den2; + Coefficient valn2; + Coefficient vald2; + bool ok = (box1.frequency(Linear_Expression(3), num1, den1, valn1, vald1) + && num1 == 0 && den1 == 1 && valn1 == 3 && vald1 == 1 + && !box2.frequency(Linear_Expression(3), num2, den2, valn2, vald2)); + print_constraints(box1, "*** box1 ***"); + print_constraints(box2, "*** box2 ***"); + + return ok; +} + +// Non-relational test. +bool +test03() { + Variable A(0); + + TBox box(1); + box.add_constraint(A == 0); + + Coefficient num; + Coefficient den; + Coefficient valn; + Coefficient vald; + bool ok = (box.frequency(Linear_Expression(A), num, den, valn, vald) + && num == 0 && den == 1 && valn == 0 && vald == 1); + print_constraints(box, "*** box ***"); + + return ok; +} + +bool +test04() { + Variable A(0); + Variable B(1); + + TBox box(2); + box.add_constraint(A >= 0); + + Coefficient num; + Coefficient den; + Coefficient valn; + Coefficient vald; + bool ok = (!box.frequency(Linear_Expression(A), num, den, valn, vald)); + print_constraints(box, "*** box ***"); + + return ok; +} + +bool +test05() { + Variable A(0); + Variable B(1); + + TBox box(2); + box.add_constraint(A <= 0); + box.add_constraint(B >= 5); + + Coefficient num; + Coefficient den; + Coefficient valn; + Coefficient vald; + bool ok = (!box.frequency(Linear_Expression(B), num, den, valn, vald)); + print_constraints(box, "*** box ***"); + + return ok; +} + +bool +test06() { + Variable A(0); + Variable B(1); + + TBox box(2); + box.add_constraint(2*A == 1); + box.add_constraint(B == 2); + + Coefficient num; + Coefficient den; + Coefficient valn; + Coefficient vald; + bool ok = (box.frequency(Linear_Expression(A + B - 3), num, den, valn, vald) + && num == 0 && den == 1 && valn == -1 && vald == 2); + print_constraints(box, "*** box ***"); + nout << "valn " << valn << ", vald " << vald << endl; + + return ok; +} + +bool +test07() { + Variable A(0); + Variable B(1); + + TBox box(2); + box.add_constraint(A <= 1); + box.add_constraint(A >= 0); + + Coefficient num; + Coefficient den; + Coefficient valn; + Coefficient vald; + bool ok = (!box.frequency(Linear_Expression(A - B), num, den, valn, vald)); + print_constraints(box, "*** box ***"); + + return ok; +} + +bool +test08() { + Variable A(0); + Variable B(1); + Variable C(2); + + TBox box(3); + box.add_constraint(A == 1); + box.add_constraint(2*B == -1); + box.add_constraint(3*C == 2); + box.add_constraint(B <= 2); + + Coefficient num; + Coefficient den; + Coefficient valn; + Coefficient vald; + bool ok = (box.frequency(Linear_Expression(A - B + C + 1), + num, den, valn, vald) + && num == 0 && den == 1 && valn == 19 && vald == 6); + print_constraints(box, "*** box ***"); + nout << "valn " << valn << ", vald " << vald << endl; + + return ok; +} + +} // namespace + +BEGIN_MAIN + DO_TEST(test01); + DO_TEST(test02); + DO_TEST(test03); + DO_TEST(test04); + DO_TEST(test05); + DO_TEST(test06); + DO_TEST(test07); + DO_TEST(test08); +END_MAIN