[PPL-devel] [GIT] ppl/ppl(products): Added the method frequency() to the Box domain.
Patricia Hill
p.m.hill at leeds.ac.uk
Fri May 22 16:35:03 CEST 2009
Module: ppl/ppl
Branch: products
Commit: 46be509da515e0e7f8909d4a31846876b00bfa02
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=46be509da515e0e7f8909d4a31846876b00bfa02
Author: Patricia Hill <p.m.hill at 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 at 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
More information about the PPL-devel
mailing list