[PPL-devel] [GIT] ppl/ppl(master): Fixed bugs in Octagonal_Shape: drop_some_on_integer_points().
Enea Zaffanella
zaffanella at cs.unipr.it
Mon Apr 5 18:15:30 CEST 2010
Module: ppl/ppl
Branch: master
Commit: 930f0a20a7bfdc920dc8baff9cae2c3347669cd7
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=930f0a20a7bfdc920dc8baff9cae2c3347669cd7
Author: Enea Zaffanella <zaffanella at cs.unipr.it>
Date: Mon Apr 5 18:14:15 2010 +0200
Fixed bugs in Octagonal_Shape:drop_some_on_integer_points().
---
src/Octagonal_Shape.templates.hh | 50 +++++++++++++++++---
tests/Octagonal_Shape/dropsomenonintegerpoints1.cc | 34 +++++++++----
2 files changed, 66 insertions(+), 18 deletions(-)
diff --git a/src/Octagonal_Shape.templates.hh b/src/Octagonal_Shape.templates.hh
index fb123c4..7dfb781 100644
--- a/src/Octagonal_Shape.templates.hh
+++ b/src/Octagonal_Shape.templates.hh
@@ -7572,6 +7572,23 @@ Octagonal_Shape<T>::drop_some_non_integer_points(Complexity_Class) {
i_end = matrix.element_end(); i != i_end; ++i)
drop_some_non_integer_points_helper(*i);
+ // Unary constraints should have an even integer boundary.
+ PPL_DIRTY_TEMP(N, temp_one);
+ assign_r(temp_one, 1, ROUND_NOT_NEEDED);
+ for (dimension_type i = 0; i < 2*space_dim; i += 2) {
+ const dimension_type ci = i+1;
+ N& mat_i_ci = matrix[i][ci];
+ if (!is_plus_infinity(mat_i_ci) && !is_even(mat_i_ci)) {
+ sub_assign_r(mat_i_ci, mat_i_ci, temp_one, ROUND_UP);
+ reset_strongly_closed();
+ }
+ N& mat_ci_i = matrix[ci][i];
+ if (!is_plus_infinity(mat_ci_i) && !is_even(mat_ci_i)) {
+ sub_assign_r(mat_ci_i, mat_ci_i, temp_one, ROUND_UP);
+ reset_strongly_closed();
+ }
+ }
+
PPL_ASSERT(OK());
}
@@ -7593,21 +7610,40 @@ Octagonal_Shape<T>
if (marked_empty())
return;
+ PPL_DIRTY_TEMP(N, temp_one);
+ assign_r(temp_one, 1, ROUND_NOT_NEEDED);
+
const Variables_Set::const_iterator v_begin = vars.begin();
const Variables_Set::const_iterator v_end = vars.end();
PPL_ASSERT(v_begin != v_end);
typedef typename OR_Matrix<N>::row_reference_type Row_Reference;
for (Variables_Set::const_iterator v_i = v_begin; v_i != v_end; ++v_i) {
- const dimension_type i = *v_i;
- Row_Reference m_i = matrix[i];
+ const dimension_type i = 2 * (*v_i);
const dimension_type ci = i + 1;
+ Row_Reference m_i = matrix[i];
Row_Reference m_ci = matrix[ci];
- // Unary constaints.
- drop_some_non_integer_points_helper(m_i[ci]);
- drop_some_non_integer_points_helper(m_ci[i]);
- // Binary constraint (note: only consider j < i).
+
+ // Unary constaints: should be even integers.
+ N& m_i_ci = m_i[ci];
+ if (!is_plus_infinity(m_i_ci)) {
+ drop_some_non_integer_points_helper(m_i_ci);
+ if (!is_even(m_i_ci)) {
+ sub_assign_r(m_i_ci, m_i_ci, temp_one, ROUND_UP);
+ reset_strongly_closed();
+ }
+ }
+ N& m_ci_i = m_ci[i];
+ if (!is_plus_infinity(m_ci_i)) {
+ drop_some_non_integer_points_helper(m_ci_i);
+ if (!is_even(m_ci_i)) {
+ sub_assign_r(m_ci_i, m_ci_i, temp_one, ROUND_UP);
+ reset_strongly_closed();
+ }
+ }
+
+ // Binary constraints (note: only consider j < i).
for (Variables_Set::const_iterator v_j = v_begin; v_j != v_i; ++v_j) {
- const dimension_type j = *v_j;
+ const dimension_type j = 2 * (*v_j);
const dimension_type cj = j + 1;
drop_some_non_integer_points_helper(m_i[j]);
drop_some_non_integer_points_helper(m_i[cj]);
diff --git a/tests/Octagonal_Shape/dropsomenonintegerpoints1.cc b/tests/Octagonal_Shape/dropsomenonintegerpoints1.cc
index f5dca86..588c858 100644
--- a/tests/Octagonal_Shape/dropsomenonintegerpoints1.cc
+++ b/tests/Octagonal_Shape/dropsomenonintegerpoints1.cc
@@ -154,7 +154,7 @@ test06() {
Variable A(0);
Variable B(1);
- Octagonal_Shape<mpq_class>os(2);
+ Octagonal_Shape<mpq_class> os(2);
os.add_constraint(2*A <= 1);
os.add_constraint(2*B <= -1);
os.add_constraint(4*A - 4*B <= 7);
@@ -163,7 +163,12 @@ test06() {
os.drop_some_non_integer_points();
- bool ok = true; //(os1 == os2);
+ Octagonal_Shape<mpq_class> known_result(2);
+ known_result.add_constraint(A <= 0);
+ known_result.add_constraint(B <= -1);
+ known_result.add_constraint(A - B <= 1);
+
+ bool ok = (os == known_result);
print_constraints(os, "*** after os.drop_some_non_integer_points() ***");
@@ -190,11 +195,12 @@ test07() {
Octagonal_Shape<mpq_class> known_result(2);
known_result.add_constraint(A >= 1);
known_result.add_constraint(2*B >= -1);
- known_result.add_constraint(2*A + 2*B >= 1);
+ known_result.add_constraint(2*A - 2*B >= 1);
bool ok = (os == known_result);
- print_constraints(os, "*** after os.drop_some_non_integer_points() ***");
+ print_constraints(os,
+ "*** after os.drop_some_non_integer_points(varset_A) ***");
return ok;
}
@@ -311,7 +317,7 @@ test12() {
Variables_Set varset_A;
varset_A.insert(A);
- Octagonal_Shape<mpq_class>os(2);
+ Octagonal_Shape<mpq_class> os(2);
os.add_constraint(2*A <= 1);
os.add_constraint(2*B <= -1);
os.add_constraint(4*A - 4*B <= 7);
@@ -320,9 +326,15 @@ test12() {
os.drop_some_non_integer_points(varset_A);
- bool ok = true; //(os1 == os2);
+ Octagonal_Shape<mpq_class> known_result(2);
+ known_result.add_constraint(A <= 0);
+ known_result.add_constraint(2*B <= -1);
+ known_result.add_constraint(4*A - 4*B <= 7);
- print_constraints(os, "*** after os.drop_some_non_integer_points() ***");
+ bool ok = (os == known_result);
+
+ print_constraints(os,
+ "*** after os.drop_some_non_integer_points(varset_A) ***");
return ok;
}
@@ -330,16 +342,16 @@ test12() {
} // namespace
BEGIN_MAIN
- DO_TEST_F(test01);
+ DO_TEST(test01);
DO_TEST(test02);
DO_TEST(test03);
DO_TEST(test04);
- DO_TEST_F(test05);
+ DO_TEST(test05);
DO_TEST(test06);
- DO_TEST_F(test07);
+ DO_TEST(test07);
DO_TEST(test08);
DO_TEST(test09);
DO_TEST(test10);
-// DO_TEST(test11);
+ DO_TEST(test11);
DO_TEST(test12);
END_MAIN
More information about the PPL-devel
mailing list