Module: ppl/ppl Branch: master Commit: cb5a410c4e262c28b62c1c07d72ef0d99358688e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=cb5a410c4e262... Author: Patricia Hill <p.m.hill@leeds.ac.uk> Date: Sat Apr 10 20:23:19 2010 +0100 Added drop_some_non_integer_points() to the product domain --- src/Partially_Reduced_Product.defs.hh | 14 +++ src/Partially_Reduced_Product.inlines.hh | 10 ++ tests/Partially_Reduced_Product/Makefile.am | 3 + .../dropsomenonintegerpoints1.cc | 96 ++++++++++++++++++++ 4 files changed, 123 insertions(+), 0 deletions(-) diff --git a/src/Partially_Reduced_Product.defs.hh b/src/Partially_Reduced_Product.defs.hh index 1116633..bb6079f 100644 --- a/src/Partially_Reduced_Product.defs.hh +++ b/src/Partially_Reduced_Product.defs.hh @@ -1357,6 +1357,20 @@ public: void widening_assign(const Partially_Reduced_Product& y, unsigned* tp = NULL); + /*! \brief + Possibly tightens \p *this by dropping some points with non-integer + coordinates. + + \param complexity + The maximal complexity of any algorithms used. + + \note + Currently there is no optimality guarantee, not even if + \p complexity is <CODE>ANY_COMPLEXITY</CODE>. + */ + void drop_some_non_integer_points(Complexity_Class complexity + = ANY_COMPLEXITY); + //@} // Space Dimension Preserving Member Functions that May Modify [...] //! \name Member Functions that May Modify the Dimension of the Vector Space diff --git a/src/Partially_Reduced_Product.inlines.hh b/src/Partially_Reduced_Product.inlines.hh index 88f921f..eacbddd 100644 --- a/src/Partially_Reduced_Product.inlines.hh +++ b/src/Partially_Reduced_Product.inlines.hh @@ -444,6 +444,16 @@ Partially_Reduced_Product<D1, D2, R> } template <typename D1, typename D2, typename R> +inline void +Partially_Reduced_Product<D1, D2, R> +::drop_some_non_integer_points(Complexity_Class complexity) { + reduce(); + d1.drop_some_non_integer_points(complexity); + d2.drop_some_non_integer_points(complexity); + clear_reduced_flag(); +} + +template <typename D1, typename D2, typename R> inline Partially_Reduced_Product<D1, D2, R>& Partially_Reduced_Product<D1, D2, R> ::operator=(const Partially_Reduced_Product& y) { diff --git a/tests/Partially_Reduced_Product/Makefile.am b/tests/Partially_Reduced_Product/Makefile.am index 4bf657d..16db2be 100644 --- a/tests/Partially_Reduced_Product/Makefile.am +++ b/tests/Partially_Reduced_Product/Makefile.am @@ -71,6 +71,7 @@ dimension1 \ directproduct1 \ discrete1 \ disjoint1 \ +dropsomenonintegerpoints1 \ equals1 \ frombdshape1 \ frombox1 \ @@ -146,6 +147,8 @@ discrete1_SOURCES = discrete1.cc disjoint1_SOURCES = disjoint1.cc +dropsomenonintegerpoints1_SOURCES = dropsomenonintegerpoints1.cc + equals1_SOURCES = equals1.cc frombdshape1_SOURCES = frombdshape1.cc diff --git a/tests/Partially_Reduced_Product/dropsomenonintegerpoints1.cc b/tests/Partially_Reduced_Product/dropsomenonintegerpoints1.cc new file mode 100644 index 0000000..729e682 --- /dev/null +++ b/tests/Partially_Reduced_Product/dropsomenonintegerpoints1.cc @@ -0,0 +1,96 @@ +/* Test Product<NNC_Polyhedron, Grid>::drop_some_non_integer_points(). + 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" +#include "partially_reduced_product_test.hh" + +typedef NNC_Polyhedron DOMAIN1; +typedef Grid DOMAIN2; +typedef Domain_Product<DOMAIN1x, DOMAIN2x>::Constraints_Product Product; + +namespace { + +// drop_some_non_integer_points(ANY_COMPLEXITY) +bool +test01() { + Variable A(0); + Variable B(1); + Variable C(2); + + Product prp1(3); + prp1.refine_with_constraint(A >= 0); + prp1.refine_with_constraint(B >= 0); + prp1.refine_with_constraint(A + B >= 3); + prp1.refine_with_constraint(2*A - B == 0); + prp1.refine_with_constraint(3*A + C == 0); + prp1.refine_with_congruence(3*A %= 0); + + prp1.drop_some_non_integer_points(ANY_COMPLEXITY); + + Product known_prp(3); + known_prp.refine_with_constraint(3*A + C == 0); + known_prp.refine_with_constraint(2*A - B == 0); + known_prp.refine_with_constraint(A >= 1); + known_prp.refine_with_congruence(A %= 0); + + bool ok = (prp1 == known_prp); + + print_congruences(prp1, "*** prp1.time_elapse_assign(prp1) congruences ***"); + print_constraints(prp1, "*** prp1.time_elapse_assign(prp1) constraints ***"); + + return ok; +} + +// drop_some_non_integer_points(ANY_COMPLEXITY) +// where the initial products are not reduced +// and the second product has non-intersecting single point components. +bool +test02() { + Variable A(0); + + + Product prp1(1); + + print_congruences(prp1, "*** prp1 congruences ***"); + print_constraints(prp1, "*** prp1 constraints ***"); + + prp1.drop_some_non_integer_points(ANY_COMPLEXITY); + + Product known_prp(1); + known_prp.refine_with_congruence(A %= 0); + + bool ok = prp1.OK() && (prp1 == known_prp); + + print_congruences(prp1, + "*** prp1.drop_some_non_integer_points(ANY_COMPLEXITY) congruences ***"); + print_constraints(prp1, + "*** prp1.drop_some_non_integer_points(ANY_COMPLEXITY) constraints ***"); + + return ok; +} + +} // namespace + +BEGIN_MAIN + DO_TEST_F8(test01); + DO_TEST(test02); +END_MAIN