April 2010 - PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: fix bug in steepest_edge_float_entering_index().
by Marco Poletti 15 Apr '10

15 Apr '10

Module: ppl/ppl Branch: sparse_matrices Commit: 4647ea26e0af205e0c63547c4e5a3a0b23bc8ec3 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4647ea26e0af… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 21:20:49 2010 +0200 MIP_Problem: fix bug in steepest_edge_float_entering_index(). --- src/MIP_Problem.cc | 31 ++++++++++++++++--------------- 1 files changed, 16 insertions(+), 15 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index cb8d7c0..a7892fb 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -991,23 +991,24 @@ PPL::MIP_Problem::steepest_edge_float_entering_index() const { = tableau_i.unordered_end(); if (j != j_end && (*j).first == 0) ++j; - for ( ; j != j_end && (*j).first < tableau_num_columns_minus_1; ++j) { - const dimension_type j_index = (*j).first; - const Coefficient& cost_j = working_cost[j_index]; - const Coefficient& tableau_ij = (*j).second; - if (sgn(cost_j) == cost_sign) { - WEIGHT_BEGIN(); - if (tableau_ij != 0) { - PPL_ASSERT(tableau_i_base_i != 0); - assign(float_tableau_value, tableau_ij); - assign(float_tableau_denum, tableau_i_base_i); - float_tableau_value /= float_tableau_denum; - float_tableau_value *= float_tableau_value; - challenger_dens[j_index] += float_tableau_value; + for ( ; j != j_end; ++j) + if ((*j).first < tableau_num_columns_minus_1) { + const dimension_type j_index = (*j).first; + const Coefficient& cost_j = working_cost[j_index]; + const Coefficient& tableau_ij = (*j).second; + if (sgn(cost_j) == cost_sign) { + WEIGHT_BEGIN(); + if (tableau_ij != 0) { + PPL_ASSERT(tableau_i_base_i != 0); + assign(float_tableau_value, tableau_ij); + assign(float_tableau_denum, tableau_i_base_i); + float_tableau_value /= float_tableau_denum; + float_tableau_value *= float_tableau_value; + challenger_dens[j_index] += float_tableau_value; + } + WEIGHT_ADD_MUL(338, tableau_num_rows); } - WEIGHT_ADD_MUL(338, tableau_num_rows); } - } } for (dimension_type j = tableau.num_columns() - 1; j-- > 1; ) { const Coefficient& cost_j = working_cost[j];

1 0

[GIT] ppl/ppl(sparse_matrices): New commits
by Roberto Bagnara 14 Apr '10

14 Apr '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c6694c8da95c… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 18:30:50 2010 +0200 MIP_Problem: use unordered iterators in steepest_edge_exact_entering_index(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=07ad6ed2ab33… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 18:16:58 2010 +0200 MIP_Problem: use unordered iterators in steepest_edge_float_entering_index(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7c83bde40686… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 18:16:25 2010 +0200 MIP_Problem: add typedef for matrix_const_row_unordered_const_iterator. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=1a53663bfd4d… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 17:56:12 2010 +0200 PIP_Solution_Node: use unordered iterators in update_solution(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ba3f42a16be6… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 17:51:24 2010 +0200 PIP_Solution_Node: use unordered iterators in generate_cut(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7e9e34eb3f2f… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 17:40:14 2010 +0200 PIP_Solution_Node: use unordered iterators in solve(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=473badc29d4c… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 17:29:51 2010 +0200 PIP_Solution_Node: use unordered iterators in compatibility_check(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=779e4fd566ad… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 17:29:27 2010 +0200 PIP_Solution_Node: use unordered iterators in row_sign(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=1281f7c55ad1… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 17:20:50 2010 +0200 PIP_Solution_Node::Tableau: use unordered iterators in is_better_pivot(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=413e69f0e096… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 17:15:52 2010 +0200 PIP_Solution_Node::Tableau: use unsorted iterators in scale(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d88af39a9ba5… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 17:15:03 2010 +0200 PIP_Solution_Node::Tableau: use unsorted iterators in normalize(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=11dedacce252… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 17:14:28 2010 +0200 PIP_Tree.cc: use unsorted iterators in row_normalize(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d8f591a9b81f… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 17:14:00 2010 +0200 PIP_Tree.cc: use unsorted iterators in neg_assign_row(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7976df815af5… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 17:13:00 2010 +0200 PIP_Tree_Node: add typedef for matrix_const_row_unordered_const_iterator.

1 0

[GIT] ppl/ppl(sparse_matrices): Sparse_Row_Reference: use unordered iterators in for_each_nonzero() methods.
by Marco Poletti 14 Apr '10

14 Apr '10

Module: ppl/ppl Branch: sparse_matrices Commit: 83e901a31d523a00da664918df7b49c44c9490fc URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=83e901a31d52… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 16:35:15 2010 +0200 Sparse_Row_Reference: use unordered iterators in for_each_nonzero() methods. --- src/Sparse_Row.inlines.hh | 4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-) diff --git a/src/Sparse_Row.inlines.hh b/src/Sparse_Row.inlines.hh index 8cdba6d..0cfa013 100644 --- a/src/Sparse_Row.inlines.hh +++ b/src/Sparse_Row.inlines.hh @@ -719,14 +719,14 @@ template <typename Func> inline void Sparse_Row_Reference ::for_each_nonzero(const Func& func, const dimension_type /* n */) { - std::for_each(begin(), end(), apply_to_data(func)); + std::for_each(unordered_begin(), unordered_end(), apply_to_data(func)); } template <typename Func> inline void Sparse_Row_Reference ::for_each_nonzero(const Func& func, const dimension_type /* n */) const { - std::for_each(begin(), end(), apply_to_data(func)); + std::for_each(unordered_begin(), unordered_end(), apply_to_data(func)); } template <typename Func>

1 0

[GIT] ppl/ppl(sparse_matrices): CO_Tree: define iterator traits for unordered_iterator and unordered_const_iterator .
by Marco Poletti 14 Apr '10

14 Apr '10

Module: ppl/ppl Branch: sparse_matrices Commit: 1531f43166855d66cc3a91374a856e25d1c825d9 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=1531f4316685… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 16:32:09 2010 +0200 CO_Tree: define iterator traits for unordered_iterator and unordered_const_iterator. --- src/CO_Tree.defs.hh | 12 ++++++++++++ 1 files changed, 12 insertions(+), 0 deletions(-) diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh index 440fb21..5fdc636 100644 --- a/src/CO_Tree.defs.hh +++ b/src/CO_Tree.defs.hh @@ -354,6 +354,12 @@ public: public: + typedef std::forward_iterator_tag iterator_category; + typedef CO_Tree::value_type value_type; + typedef ptrdiff_t difference_type; + typedef value_type* pointer; + typedef value_type& reference; + unordered_iterator(value_type* p1 = 0); value_type& operator*(); @@ -376,6 +382,12 @@ public: public: + typedef std::forward_iterator_tag iterator_category; + typedef const CO_Tree::value_type value_type; + typedef ptrdiff_t difference_type; + typedef value_type* pointer; + typedef value_type& reference; + unordered_const_iterator(const value_type* p1 = 0); unordered_const_iterator(const unordered_iterator& itr);

1 0

[GIT] ppl/ppl(sparse_matrices): New commits
by Roberto Bagnara 14 Apr '10

14 Apr '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=87ac0a9329d0… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 15:59:12 2010 +0200 PIP_Problem: optimize solve() method for sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=54051a291914… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 15:58:39 2010 +0200 PIP_Tree_Node: add typedefs for matrix_row_unordered_iterator, matrix_row_unordered_const_iterator, matrix_row_copy_unordered_iterator and matrix_row_copy_unordered_const_iterator. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9aa2945394ad… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 15:57:48 2010 +0200 PIP_Problem: add typedefs for matrix_row_unordered_iterator, matrix_row_unordered_const_iterator, matrix_row_copy_unordered_iterator and matrix_row_copy_unordered_const_iterator. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8d076878fcda… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 15:57:24 2010 +0200 MIP_Problem: add typedefs for matrix_row_unordered_iterator, matrix_row_unordered_const_iterator, matrix_row_copy_unordered_iterator and matrix_row_copy_unordered_const_iterator. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b85cafc6e4fd… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 15:55:49 2010 +0200 Unlimited_Sparse_Row_Over_CO_Tree: optimize combine*() methods. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ef4fba206646… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 15:54:34 2010 +0200 Dense_Row: add unordered_iterator and unordered_const_iterator. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2b8a517fd7d4… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 15:54:06 2010 +0200 Sparse_Row, Sparse_Row_Reference: add unordered_iterator and unordered_const_iterator. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=74729c1b38e8… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 15:53:20 2010 +0200 Unlimited_Sparse_Row_Over_Linear_Sequence: add unordered_iterator and unordered_const_iterator. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=45afd77bc46a… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 15:52:55 2010 +0200 Unlimited_Sparse_Row_Over_CO_Tree: add unordered_iterator and unordered_const_iterator. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=45b777472771… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Apr 14 15:51:43 2010 +0200 CO_Tree: add unordered_iterator and unordered_const_iterator.

1 0

[GIT] ppl/ppl(master): Allow for the Shape_Preserving_Product to be generated
by Patricia Hill 14 Apr '10

14 Apr '10

Module: ppl/ppl Branch: master Commit: b51b3600e55ea768cab6fea39cf4009f8f9c9b81 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b51b3600e55e… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Wed Apr 14 07:54:49 2010 +0100 Allow for the Shape_Preserving_Product to be generated in the interfaces. --- instchk.hh | 8 ++++++++ interfaces/Prolog/Ciao/Makefile.am | 6 +++++- interfaces/Prolog/GNU/Makefile.am | 6 +++++- interfaces/Prolog/Prolog_interface.dox | 5 +++-- interfaces/Prolog/SICStus/Makefile.am | 6 +++++- interfaces/Prolog/SWI/Makefile.am | 6 +++++- interfaces/Prolog/XSB/Makefile.am | 6 +++++- interfaces/Prolog/YAP/Makefile.am | 6 +++++- interfaces/ppl_interface_generator_common_dat.m4 | 3 ++- 9 files changed, 43 insertions(+), 9 deletions(-) diff --git a/instchk.hh b/instchk.hh index 13c357d..0a07a08 100644 --- a/instchk.hh +++ b/instchk.hh @@ -377,4 +377,12 @@ public: } }; +template <typename D1, typename D2> +class Shape_Preserving_Product { +public: + static bool valid_instantiation() { + return D1::valid_Product_argument() && D2::valid_Product_argument(); + } +}; + } // namespace Parma_Polyhedra_Library diff --git a/interfaces/Prolog/Ciao/Makefile.am b/interfaces/Prolog/Ciao/Makefile.am index cfba3fc..2c6431a 100644 --- a/interfaces/Prolog/Ciao/Makefile.am +++ b/interfaces/Prolog/Ciao/Makefile.am @@ -143,7 +143,11 @@ nodist_EXTRA_libppl_ciao_la_SOURCES = \ ../ppl_prolog_Constraints_Product_C_Polyhedron_Grid.cc \ ../ppl_prolog_Constraints_Product_NNC_Polyhedron_Grid.cc \ ../ppl_prolog_Constraints_Product_Grid_C_Polyhedron.cc \ -../ppl_prolog_Constraints_Product_Grid_NNC_Polyhedron.cc +../ppl_prolog_Constraints_Product_Grid_NNC_Polyhedron.cc \ +../ppl_prolog_Shape_Preserving_Product_C_Polyhedron_Grid.cc \ +../ppl_prolog_Shape_Preserving_Product_NNC_Polyhedron_Grid.cc \ +../ppl_prolog_Shape_Preserving_Product_Grid_C_Polyhedron.cc \ +../ppl_prolog_Shape_Preserving_Product_Grid_NNC_Polyhedron.cc if NO_UNDEFINED diff --git a/interfaces/Prolog/GNU/Makefile.am b/interfaces/Prolog/GNU/Makefile.am index e99e385..962a9e1 100644 --- a/interfaces/Prolog/GNU/Makefile.am +++ b/interfaces/Prolog/GNU/Makefile.am @@ -138,7 +138,11 @@ nodist_EXTRA_libppl_gprolog_la_SOURCES = \ ../ppl_prolog_Constraints_Product_C_Polyhedron_Grid.cc \ ../ppl_prolog_Constraints_Product_NNC_Polyhedron_Grid.cc \ ../ppl_prolog_Constraints_Product_Grid_C_Polyhedron.cc \ -../ppl_prolog_Constraints_Product_Grid_NNC_Polyhedron.cc +../ppl_prolog_Constraints_Product_Grid_NNC_Polyhedron.cc \ +../ppl_prolog_Shape_Preserving_Product_C_Polyhedron_Grid.cc \ +../ppl_prolog_Shape_Preserving_Product_NNC_Polyhedron_Grid.cc \ +../ppl_prolog_Shape_Preserving_Product_Grid_C_Polyhedron.cc \ +../ppl_prolog_Shape_Preserving_Product_Grid_NNC_Polyhedron.cc if NO_UNDEFINED diff --git a/interfaces/Prolog/Prolog_interface.dox b/interfaces/Prolog/Prolog_interface.dox index f861f57..485b13f 100644 --- a/interfaces/Prolog/Prolog_interface.dox +++ b/interfaces/Prolog/Prolog_interface.dox @@ -106,8 +106,9 @@ on the use of the interface. a simple domain. - The product domains consist of Direct_Product_S_T, - Smash_Product_S_T and - Constraints_Product_S_T where S + Smash_Product_S_T, + Constraints_Product_S_T and + Shape_Preserving_Product_S_T where S and T are simple domains. - In the following, any of the above numerical abstract domains is called a PPL <EM>domain</EM> diff --git a/interfaces/Prolog/SICStus/Makefile.am b/interfaces/Prolog/SICStus/Makefile.am index 6847542..06635db 100644 --- a/interfaces/Prolog/SICStus/Makefile.am +++ b/interfaces/Prolog/SICStus/Makefile.am @@ -172,7 +172,11 @@ nodist_EXTRA_libppl_sicstus_la_SOURCES = \ ../ppl_prolog_Constraints_Product_C_Polyhedron_Grid.cc \ ../ppl_prolog_Constraints_Product_NNC_Polyhedron_Grid.cc \ ../ppl_prolog_Constraints_Product_Grid_C_Polyhedron.cc \ -../ppl_prolog_Constraints_Product_Grid_NNC_Polyhedron.cc +../ppl_prolog_Constraints_Product_Grid_NNC_Polyhedron.cc \ +../ppl_prolog_Shape_Preserving_Product_C_Polyhedron_Grid.cc \ +../ppl_prolog_Shape_Preserving_Product_NNC_Polyhedron_Grid.cc \ +../ppl_prolog_Shape_Preserving_Product_Grid_C_Polyhedron.cc \ +../ppl_prolog_Shape_Preserving_Product_Grid_NNC_Polyhedron.cc if NO_UNDEFINED diff --git a/interfaces/Prolog/SWI/Makefile.am b/interfaces/Prolog/SWI/Makefile.am index 98dffed..6ad3907 100644 --- a/interfaces/Prolog/SWI/Makefile.am +++ b/interfaces/Prolog/SWI/Makefile.am @@ -159,7 +159,11 @@ nodist_EXTRA_libppl_swiprolog_la_SOURCES = \ ../ppl_prolog_Constraints_Product_C_Polyhedron_Grid.cc \ ../ppl_prolog_Constraints_Product_NNC_Polyhedron_Grid.cc \ ../ppl_prolog_Constraints_Product_Grid_C_Polyhedron.cc \ -../ppl_prolog_Constraints_Product_Grid_NNC_Polyhedron.cc +../ppl_prolog_Constraints_Product_Grid_NNC_Polyhedron.cc \ +../ppl_prolog_Shape_Preserving_Product_C_Polyhedron_Grid.cc \ +../ppl_prolog_Shape_Preserving_Product_NNC_Polyhedron_Grid.cc \ +../ppl_prolog_Shape_Preserving_Product_Grid_C_Polyhedron.cc \ +../ppl_prolog_Shape_Preserving_Product_Grid_NNC_Polyhedron.cc if NO_UNDEFINED diff --git a/interfaces/Prolog/XSB/Makefile.am b/interfaces/Prolog/XSB/Makefile.am index 514664f..43b49c4 100644 --- a/interfaces/Prolog/XSB/Makefile.am +++ b/interfaces/Prolog/XSB/Makefile.am @@ -161,7 +161,11 @@ nodist_EXTRA_libppl_xsb_la_SOURCES = \ ../ppl_prolog_Constraints_Product_C_Polyhedron_Grid.cc \ ../ppl_prolog_Constraints_Product_NNC_Polyhedron_Grid.cc \ ../ppl_prolog_Constraints_Product_Grid_C_Polyhedron.cc \ -../ppl_prolog_Constraints_Product_Grid_NNC_Polyhedron.cc +../ppl_prolog_Constraints_Product_Grid_NNC_Polyhedron.cc \ +../ppl_prolog_Shape_Preserving_Product_C_Polyhedron_Grid.cc \ +../ppl_prolog_Shape_Preserving_Product_NNC_Polyhedron_Grid.cc \ +../ppl_prolog_Shape_Preserving_Product_Grid_C_Polyhedron.cc \ +../ppl_prolog_Shape_Preserving_Product_Grid_NNC_Polyhedron.cc if NO_UNDEFINED diff --git a/interfaces/Prolog/YAP/Makefile.am b/interfaces/Prolog/YAP/Makefile.am index 469e24c..875bae9 100644 --- a/interfaces/Prolog/YAP/Makefile.am +++ b/interfaces/Prolog/YAP/Makefile.am @@ -157,7 +157,11 @@ nodist_EXTRA_ppl_yap_la_SOURCES = \ ../ppl_prolog_Constraints_Product_C_Polyhedron_Grid.cc \ ../ppl_prolog_Constraints_Product_NNC_Polyhedron_Grid.cc \ ../ppl_prolog_Constraints_Product_Grid_C_Polyhedron.cc \ -../ppl_prolog_Constraints_Product_Grid_NNC_Polyhedron.cc +../ppl_prolog_Constraints_Product_Grid_NNC_Polyhedron.cc \ +../ppl_prolog_Shape_Preserving_Product_C_Polyhedron_Grid.cc \ +../ppl_prolog_Shape_Preserving_Product_NNC_Polyhedron_Grid.cc \ +../ppl_prolog_Shape_Preserving_Product_Grid_C_Polyhedron.cc \ +../ppl_prolog_Shape_Preserving_Product_Grid_NNC_Polyhedron.cc ppl_yap_la_LIBADD = \ @required_instantiations_prolog_cxx_objects@ \ diff --git a/interfaces/ppl_interface_generator_common_dat.m4 b/interfaces/ppl_interface_generator_common_dat.m4 index 57cd897..f0f79be 100644 --- a/interfaces/ppl_interface_generator_common_dat.m4 +++ b/interfaces/ppl_interface_generator_common_dat.m4 @@ -480,7 +480,8 @@ m4_define(`m4_box_group', Uint8_Box, Uint16_Box, Uint32_Box, Uint64_Box') m4_define(`m4_pointset_powerset_group', Pointset_Powerset) m4_define(`m4_product_group', - `Direct_Product, Smash_Product, Constraints_Product') + `Direct_Product, Smash_Product, Constraints_Product, + Shape_Preserving_Product') dnl ===================================================================== dnl ===== The next set of macros define the replacements =====

1 0

[GIT] ppl/ppl(master): Fixed a bug in the all_affine_ranking_functions*_Grid* tests
by Patricia Hill 14 Apr '10

14 Apr '10

Module: ppl/ppl Branch: master Commit: 037c5b2d0a722ad6c36d8bc7f3504b0f84d7781b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=037c5b2d0a72… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Wed Apr 14 07:53:21 2010 +0100 Fixed a bug in the all_affine_ranking_functions*_Grid* tests in Prolog interface. --- ...face_generator_prolog_generated_test_pl_code.m4 | 24 +++++-------------- 1 files changed, 7 insertions(+), 17 deletions(-) diff --git a/interfaces/Prolog/tests/ppl_interface_generator_prolog_generated_test_pl_code.m4 b/interfaces/Prolog/tests/ppl_interface_generator_prolog_generated_test_pl_code.m4 index 5afde30..b62dbb8 100644 --- a/interfaces/Prolog/tests/ppl_interface_generator_prolog_generated_test_pl_code.m4 +++ b/interfaces/Prolog/tests/ppl_interface_generator_prolog_generated_test_pl_code.m4 @@ -1861,14 +1861,9 @@ ppl_all_affine_ranking_functions_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_2_test :- ppl_@TOPOLOGY@@CLASS@_build_test_object(TEST_DATA1, PS1, Space_Dim), ppl_@TOPOLOGY@@CLASS@_build_test_object(TEST_DATA2, PS2, Space_Dim), ppl_@CLASS@_concatenate_assign(PS1, PS2), - (ppl_all_affine_ranking_functions_@TERMINATION_ID@_@TOPOLOGY@@CLASS@(PS1, - Ph) - -> - true - ; - true - ), - ppl_@CLASS@_OK(Ph), + ppl_all_affine_ranking_functions_@TERMINATION_ID@_@TOPOLOGY@@CLASS@(PS1, + Ph), + ppl_Polyhedron_OK(Ph), ppl_@CLASS@_OK(PS1), ppl_@CLASS@_OK(PS2), ppl_delete_@CLASS@(PS1), @@ -1889,15 +1884,10 @@ ppl_all_affine_ranking_functions_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_2_2_test :- ppl_@TOPOLOGY@@CLASS@_build_test_object(TEST_DATA1, PS1, Space_Dim), ppl_@TOPOLOGY@@CLASS@_build_test_object(TEST_DATA2, PS2, Space_Dim), ppl_@CLASS@_concatenate_assign(PS1, PS2), - (ppl_all_affine_ranking_functions_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_2(PS2, - PS1, - Ph) - -> - true - ; - true - ), - ppl_@CLASS@_OK(Ph), + ppl_all_affine_ranking_functions_@TERMINATION_ID@_@TOPOLOGY@@CLASS@_2(PS2, + PS1, + Ph), + ppl_Polyhedron_OK(Ph), ppl_@CLASS@_OK(PS1), ppl_@CLASS@_OK(PS2), ppl_delete_@CLASS@(PS1),

1 0

[GIT] ppl/ppl(sparse_matrices): CO_Tree: construct Coefficient objects only when needed.
by Marco Poletti 13 Apr '10

13 Apr '10

Module: ppl/ppl Branch: sparse_matrices Commit: 0ff013e62483a62c87273baaee583086175a020f URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0ff013e62483… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Apr 13 22:28:03 2010 +0200 CO_Tree: construct Coefficient objects only when needed. --- src/CO_Tree.cc | 45 +++++++++++++++++++++++++++++++++------------ src/CO_Tree.defs.hh | 3 +++ src/CO_Tree.inlines.hh | 27 ++++++++++----------------- 3 files changed, 46 insertions(+), 29 deletions(-) diff --git a/src/CO_Tree.cc b/src/CO_Tree.cc index d39529a..a84efaf 100644 --- a/src/CO_Tree.cc +++ b/src/CO_Tree.cc @@ -200,8 +200,9 @@ PPL::CO_Tree::copy_data_from(const CO_Tree& x) { } else { if (top_n == 1) { PPL_ASSERT(root->first == unused_index); + PPL_ASSERT(itr->first != unused_index); root->first = itr->first; - root->second = itr->second; + new (&(root->second)) data_type(itr->second); itr.get_next_value(); --stack_first_empty; } else { @@ -247,10 +248,11 @@ PPL::CO_Tree::init(dimension_type reserved_size1) { l++; reserved_size = ((dimension_type)1 << l) - 1; - data = new value_type[reserved_size + 1]; + data = static_cast<value_type *>(operator new(sizeof(value_type) + *(reserved_size + 1))); // Mark all pairs as unused. for (dimension_type i = 1; i <= reserved_size; ++i) - data[i].first = unused_index; + new (&(data[i].first)) dimension_type(unused_index); max_depth = l; rebuild_level_data(l); @@ -261,6 +263,22 @@ PPL::CO_Tree::init(dimension_type reserved_size1) { } void +PPL::CO_Tree::destroy() { + + if (reserved_size != 0) { + for (dimension_type i = 1; i <= reserved_size; ++i) { + if (data[i].first != unused_index) + data[i].second.~data_type(); + data[i].first.~dimension_type(); + } + + operator delete(data); + + delete [] level; + } +} + +void PPL::CO_Tree::move_data_from(CO_Tree& tree) { PPL_ASSERT(size == 0); if (tree.size == 0) @@ -327,7 +345,9 @@ PPL::CO_Tree::move_data_from(CO_Tree& tree) { } else { if (top_n == 1) { PPL_ASSERT(root->first == unused_index); + PPL_ASSERT(itr->first != unused_index); root->first = itr->first; + itr->first = unused_index; move_data_element(root->second, itr->second); itr.get_next_value(); --stack_first_empty; @@ -345,8 +365,8 @@ PPL::CO_Tree::move_data_from(CO_Tree& tree) { } } size = tree.size; - PPL_ASSERT(structure_OK()); - PPL_ASSERT(tree.OK()); + tree.size = 0; + PPL_ASSERT(tree.structure_OK()); } bool @@ -480,7 +500,7 @@ PPL::CO_Tree::insert(dimension_type key1, const data_type& data1, itr.get_root(); PPL_ASSERT(itr->first == unused_index); itr->first = key1; - itr->second = data1; + new (&(itr->second)) data_type(data1); size++; PPL_ASSERT(OK()); @@ -518,7 +538,7 @@ PPL::CO_Tree::insert(dimension_type key1, const data_type& data1, itr.get_right_child(); PPL_ASSERT(itr->first == unused_index); itr->first = key1; - itr->second = data1; + new (&(itr->second)) data_type(data1); size++; } else { @@ -612,8 +632,7 @@ PPL::CO_Tree::erase(inorder_iterator& itr) { if (size == 1) { // Deleting the only element of this tree, now it is empty. - delete [] data; - delete [] level; + destroy(); init(0); return; } @@ -642,6 +661,7 @@ PPL::CO_Tree::erase(inorder_iterator& itr) { > max_density); #endif + itr->second.~data_type(); while (1) { dimension_type& current_key = itr->first; data_type& current_data = itr->second; @@ -747,7 +767,7 @@ PPL::CO_Tree::redistribute_elements_in_subtree(inorder_iterator& itr, if (!added_key && can_add_key) { PPL_ASSERT(itr2->first == unused_index); itr2->first = key; - itr2->second = value; + new (&(itr2->second)) data_type(value); added_key = true; } else ++itr2; @@ -795,7 +815,7 @@ PPL::CO_Tree PPL_ASSERT(!first_unused.is_before_begin()); PPL_ASSERT(first_unused->first == unused_index); first_unused->first = key; - first_unused->second = value; + new (&(first_unused->second)) data_type(value); added_key = true; --first_unused; --subtree_size; @@ -901,9 +921,10 @@ PPL::CO_Tree if (top_n == 1) { if (!added_key && (itr.is_at_end() || itr->first > key)) { PPL_ASSERT(root != itr); + PPL_ASSERT(root->first == unused_index); added_key = true; root->first = key; - root->second = value; + new (&(root->second)) data_type(value); } else { if (root != itr) { PPL_ASSERT(root->first == unused_index); diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh index 10fb07e..56602f0 100644 --- a/src/CO_Tree.defs.hh +++ b/src/CO_Tree.defs.hh @@ -339,6 +339,9 @@ private: //! Initializes a tree with reserved size at least \p n . void init(dimension_type n); + //! Deallocates the tree. After this call, init() can be called again. + void destroy(); + //! Checks the invariant, but not the densities. bool structure_OK() const; diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh index bfad42f..e8cd662 100644 --- a/src/CO_Tree.inlines.hh +++ b/src/CO_Tree.inlines.hh @@ -54,11 +54,7 @@ CO_Tree::operator=(const CO_Tree& x) { if (this != &x) { - if (reserved_size != 0) { - delete [] data; - delete [] level; - } - + destroy(); init(x.reserved_size); copy_data_from(x); @@ -70,13 +66,9 @@ CO_Tree::operator=(const CO_Tree& x) { inline CO_Tree::~CO_Tree() { - PPL_ASSERT(OK()); - - if (level != NULL) - delete [] level; + PPL_ASSERT(structure_OK()); - if (data != NULL) - delete [] data; + destroy(); } inline dimension_type @@ -241,7 +233,7 @@ CO_Tree::lower_bound(inorder_const_iterator& itr, dimension_type key) const { inline void CO_Tree::move_data_element(data_type& to, data_type& from) { - std::swap(to, from); + std::memcpy(&to, &from, sizeof(data_type)); } inline void @@ -254,7 +246,7 @@ CO_Tree::rebuild_bigger_tree() { new_tree.init(new_reserved_size); new_tree.move_data_from(*this); swap(new_tree); - PPL_ASSERT(new_tree.OK()); + PPL_ASSERT(new_tree.structure_OK()); } PPL_ASSERT(structure_OK()); } @@ -262,8 +254,7 @@ CO_Tree::rebuild_bigger_tree() { inline void CO_Tree::rebuild_smaller_tree() { if (reserved_size == 3) { - delete [] data; - delete [] level; + destroy(); init(0); } else { dimension_type new_reserved_size = reserved_size / 2; @@ -271,7 +262,7 @@ CO_Tree::rebuild_smaller_tree() { new_tree.init(new_reserved_size); new_tree.move_data_from(*this); swap(new_tree); - PPL_ASSERT(new_tree.OK()); + PPL_ASSERT(new_tree.structure_OK()); } PPL_ASSERT(structure_OK()); } @@ -595,7 +586,6 @@ CO_Tree::inorder_iterator::get_next_value() { #ifndef NDEBUG const dimension_type previous_index = (*this)->first; #endif - PPL_ASSERT(previous_index != unused_index); if (get_right_child_value()) while (get_left_child_value()) ; @@ -610,6 +600,9 @@ CO_Tree::inorder_iterator::get_next_value() { #ifndef NDEBUG if (!at_end) + // previous_index could be unused_index because we deleted the current + // node, as we do in move_data_from(). + if (previous_index != unused_index) PPL_ASSERT((*this)->first != unused_index && (*this)->first > previous_index); #endif

1 0

[GIT] ppl/ppl(sparse_matrices): CO_Tree: inline simple methods.
by Marco Poletti 13 Apr '10

13 Apr '10

Module: ppl/ppl Branch: sparse_matrices Commit: 68851b8fbcc8146aec0dc9b98eee8846793e4267 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=68851b8fbcc8… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Apr 13 18:43:07 2010 +0200 CO_Tree: inline simple methods. --- src/CO_Tree.cc | 101 ------------------------------------------------ src/CO_Tree.inlines.hh | 100 +++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 100 insertions(+), 101 deletions(-) diff --git a/src/CO_Tree.cc b/src/CO_Tree.cc index bb600bb..d39529a 100644 --- a/src/CO_Tree.cc +++ b/src/CO_Tree.cc @@ -26,13 +26,6 @@ site: http://www.cs.unipr.it/ppl/ . */ namespace PPL = Parma_Polyhedra_Library; -PPL::CO_Tree::CO_Tree() { - - init(0); - - PPL_ASSERT(OK()); -} - PPL::CO_Tree::CO_Tree(const std::vector<data_type>& v) { dimension_type n = 0; @@ -267,27 +260,6 @@ PPL::CO_Tree::init(dimension_type reserved_size1) { PPL_ASSERT(structure_OK()); } -PPL::CO_Tree::~CO_Tree() { - - PPL_ASSERT(OK()); - - if (level != NULL) - delete [] level; - - if (data != NULL) - delete [] data; -} - -PPL::dimension_type -PPL::CO_Tree::external_memory_in_bytes() const { - dimension_type size = 0; - // Adding the size of data[] - size += (reserved_size + 1)*sizeof(data[0]); - // Adding the size of level[] - size += max_depth*sizeof(level[0]); - return size; -} - void PPL::CO_Tree::move_data_from(CO_Tree& tree) { PPL_ASSERT(size == 0); @@ -630,24 +602,6 @@ PPL::CO_Tree::rebalance(inorder_iterator& itr, dimension_type key, PPL_ASSERT(OK()); } -bool -PPL::CO_Tree::erase(dimension_type key) { - PPL_ASSERT(key != unused_index); - - if (size == 0) - return false; - - inorder_iterator itr(&*this); - lower_bound(itr, key); - - if (itr->first != key) - return false; - - erase(itr); - - return true; -} - void PPL::CO_Tree::erase(inorder_iterator& itr) { PPL_ASSERT(!itr.is_before_begin()); @@ -976,58 +930,3 @@ PPL::CO_Tree PPL_ASSERT(added_key); } - - -PPL::CO_Tree::inorder_iterator& -PPL::CO_Tree::inorder_iterator::operator=(const inorder_iterator& itr2) { - tree = itr2.tree; - if (tree != 0) { - at_end = itr2.at_end; - before_begin = itr2.before_begin; - if (!at_end && !before_begin) { - d = itr2.d; - i = itr2.i; - for (dimension_type i = 1; i <= itr2.d; ++i) - pos[i] = itr2.pos[i]; - } - } - - return *this; -} - - -PPL::CO_Tree::inorder_const_iterator& -PPL::CO_Tree::inorder_const_iterator -::operator=(const inorder_const_iterator& itr2) { - tree = itr2.tree; - if (tree != 0) { - at_end = itr2.at_end; - before_begin = itr2.before_begin; - if (!at_end && !before_begin) { - d = itr2.d; - i = itr2.i; - for (dimension_type i = 1; i <= itr2.d; ++i) - pos[i] = itr2.pos[i]; - } - } - - return *this; -} - -PPL::CO_Tree::inorder_const_iterator& -PPL::CO_Tree::inorder_const_iterator -::operator=(const inorder_iterator& itr2) { - tree = itr2.tree; - if (tree != 0) { - at_end = itr2.at_end; - before_begin = itr2.before_begin; - if (!at_end && !before_begin) { - d = itr2.d; - i = itr2.i; - for (dimension_type i = 1; i <= itr2.d; ++i) - pos[i] = itr2.pos[i]; - } - } - - return *this; -} diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh index 77e712a..bfad42f 100644 --- a/src/CO_Tree.inlines.hh +++ b/src/CO_Tree.inlines.hh @@ -31,6 +31,13 @@ site: http://www.cs.unipr.it/ppl/ . */ namespace Parma_Polyhedra_Library { +inline +CO_Tree::CO_Tree() { + + init(0); + + PPL_ASSERT(OK()); +} inline CO_Tree::CO_Tree(const CO_Tree& x) { @@ -60,6 +67,28 @@ CO_Tree::operator=(const CO_Tree& x) { return *this; } +inline +CO_Tree::~CO_Tree() { + + PPL_ASSERT(OK()); + + if (level != NULL) + delete [] level; + + if (data != NULL) + delete [] data; +} + +inline dimension_type +CO_Tree::external_memory_in_bytes() const { + dimension_type size = 0; + // Adding the size of data[] + size += (reserved_size + 1)*sizeof(data[0]); + // Adding the size of level[] + size += max_depth*sizeof(level[0]); + return size; +} + inline bool CO_Tree::empty() const { return size == 0; @@ -124,6 +153,24 @@ CO_Tree::insert(dimension_type key, const data_type& value) { PPL_ASSERT(OK()); } +inline bool +CO_Tree::erase(dimension_type key) { + PPL_ASSERT(key != unused_index); + + if (size == 0) + return false; + + inorder_iterator itr(&*this); + lower_bound(itr, key); + + if (itr->first != key) + return false; + + erase(itr); + + return true; +} + inline void CO_Tree::rebuild_level_data(dimension_type max_depth) { level = new level_data[max_depth]; @@ -609,6 +656,23 @@ CO_Tree::inorder_iterator::get_previous_value() { } } +inline CO_Tree::inorder_iterator& +CO_Tree::inorder_iterator::operator=(const inorder_iterator& itr2) { + tree = itr2.tree; + if (tree != 0) { + at_end = itr2.at_end; + before_begin = itr2.before_begin; + if (!at_end && !before_begin) { + d = itr2.d; + i = itr2.i; + for (dimension_type i = 1; i <= itr2.d; ++i) + pos[i] = itr2.pos[i]; + } + } + + return *this; +} + inline CO_Tree::inorder_const_iterator::inorder_const_iterator(const CO_Tree* tree1) @@ -972,6 +1036,42 @@ CO_Tree::inorder_const_iterator::get_previous_value() { } } +inline CO_Tree::inorder_const_iterator& +CO_Tree::inorder_const_iterator +::operator=(const inorder_const_iterator& itr2) { + tree = itr2.tree; + if (tree != 0) { + at_end = itr2.at_end; + before_begin = itr2.before_begin; + if (!at_end && !before_begin) { + d = itr2.d; + i = itr2.i; + for (dimension_type i = 1; i <= itr2.d; ++i) + pos[i] = itr2.pos[i]; + } + } + + return *this; +} + +inline CO_Tree::inorder_const_iterator& +CO_Tree::inorder_const_iterator +::operator=(const inorder_iterator& itr2) { + tree = itr2.tree; + if (tree != 0) { + at_end = itr2.at_end; + before_begin = itr2.before_begin; + if (!at_end && !before_begin) { + d = itr2.d; + i = itr2.i; + for (dimension_type i = 1; i <= itr2.d; ++i) + pos[i] = itr2.pos[i]; + } + } + + return *this; +} + } // namespace Parma_Polyhedra_Library #endif // !defined(PPL_CO_Tree_inlines_hh)

1 0

[GIT] ppl/ppl(master): Some tests now succeed even on initially empty polyhedra.
by Enea Zaffanella 13 Apr '10

13 Apr '10

Module: ppl/ppl Branch: master Commit: 95907486afa72008519841dbfe5ea5fd758657c2 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=95907486afa7… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Tue Apr 13 18:10:12 2010 +0200 Some tests now succeed even on initially empty polyhedra. --- tests/Polyhedron/termination2.cc | 11 ++++++----- 1 files changed, 6 insertions(+), 5 deletions(-) diff --git a/tests/Polyhedron/termination2.cc b/tests/Polyhedron/termination2.cc index 64c98fb..43fcceb 100644 --- a/tests/Polyhedron/termination2.cc +++ b/tests/Polyhedron/termination2.cc @@ -58,7 +58,7 @@ test04() { C_Polyhedron ph1(2, EMPTY); C_Polyhedron ph2(4); bool ok = termination_test_PR_2(ph1, ph2); - ok = ok && termination_test_MS_2(ph1, ph2); + ok = ok && termination_test_MS_2(ph1, ph2); return ok; } @@ -92,7 +92,7 @@ test07() { C_Polyhedron ph2(4); Generator witness(point()); bool ok = one_affine_ranking_function_PR_2(ph1, ph2, witness); - // ok = ok && one_affine_ranking_function_MS_2(ph1, ph2, witness); + ok = ok && one_affine_ranking_function_MS_2(ph1, ph2, witness); return ok; } @@ -102,7 +102,7 @@ test08() { C_Polyhedron ph2(4, EMPTY); Generator witness(point()); bool ok = one_affine_ranking_function_PR_2(ph1, ph2, witness); - // ok = ok && one_affine_ranking_function_MS_2(ph1, ph2, witness); + ok = ok && one_affine_ranking_function_MS_2(ph1, ph2, witness); return ok; } @@ -139,13 +139,14 @@ test10() { C_Polyhedron c_known_result(2, EMPTY); c_known_result.add_generator(point()); - NNC_Polyhedron nnc_known_result(2, EMPTY); + NNC_Polyhedron nnc_known_result(3, EMPTY); nnc_known_result.add_generator(point()); print_constraints(ph1, "*** ph ***"); print_constraints(c_mu_space, "*** c_mu_space ***"); print_constraints(nnc_known_result, "*** nnc_known_result ***"); print_constraints(nnc_mu_space, "*** nnc_mu_space ***"); + return ph1.OK() && (nnc_mu_space == nnc_known_result); } @@ -161,5 +162,5 @@ BEGIN_MAIN DO_TEST(test07); DO_TEST(test08); DO_TEST(test09); - DO_TEST(test10); + DO_TEST_F(test10); END_MAIN

1 0