- PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(floating_point): Use is_empty instead of marked_empty for
by Fabio Bossi 23 Sep '10

23 Sep '10

Module: ppl/ppl Branch: floating_point Commit: 17f7473e9cbe0dac0c5759396234c80acf50c347 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=17f7473e9cbe… Author: Fabio Bossi <bossi(a)cs.unipr.it> Date: Thu Sep 23 15:46:00 2010 +0200 Use is_empty instead of marked_empty for maximum safety. --- src/Octagonal_Shape.templates.hh | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/src/Octagonal_Shape.templates.hh b/src/Octagonal_Shape.templates.hh index 44c04e2..54de5ce 100644 --- a/src/Octagonal_Shape.templates.hh +++ b/src/Octagonal_Shape.templates.hh @@ -7665,7 +7665,7 @@ Octagonal_Shape<T> strong_closure_assign(); - if (marked_empty()) { + if (is_empty()) { dest.set_empty(); return; }

1 0

[GIT] ppl/ppl(floating_point): Added method export_interval_constraints.
by Fabio Bossi 23 Sep '10

23 Sep '10

Module: ppl/ppl Branch: floating_point Commit: 7bd3f0121f60355f34ba32c3a976983ff66607df URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7bd3f0121f60… Author: Fabio Bossi <bossi(a)cs.unipr.it> Date: Thu Sep 23 12:24:39 2010 +0200 Added method export_interval_constraints. --- src/Octagonal_Shape.defs.hh | 33 ++++++++++++++++++++++++++++ src/Octagonal_Shape.templates.hh | 44 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 77 insertions(+), 0 deletions(-) diff --git a/src/Octagonal_Shape.defs.hh b/src/Octagonal_Shape.defs.hh index b84575a..2200ab9 100644 --- a/src/Octagonal_Shape.defs.hh +++ b/src/Octagonal_Shape.defs.hh @@ -1805,6 +1805,39 @@ public: */ void fold_space_dimensions(const Variables_Set& vars, Variable dest); + //! Applies to \p dest the interval constraints embedded in \p *this. + /*! + \param dest + The object to which the constraints will be added. + + \exception std::invalid_argument + Thrown if \p *this is dimension-incompatible with \p dest. + + The template type parameter U must provide the following methods. + \code + dimension_type space_dimension() const + \endcode + returns the space dimension of the object. + \code + void set_empty() + \endcode + sets the object to an empty object. + \code + bool restrict_lower(dimension_type dim, const T& lb) + \endcode + restricts the object by applying the lower bound \p lb to the space + dimension \p dim and returns <CODE>false</CODE> if and only if the + object becomes empty. + \code + bool restrict_upper(dimension_type dim, const T& ub) + \endcode + restricts the object by applying the upper bound \p ub to the space + dimension \p dim and returns <CODE>false</CODE> if and only if the + object becomes empty. + */ + template <typename U> + void export_interval_constraints(U& dest) const; + //! Refines \p store with the constraints defining \p *this. /*! \param store diff --git a/src/Octagonal_Shape.templates.hh b/src/Octagonal_Shape.templates.hh index 4b76797..44c04e2 100644 --- a/src/Octagonal_Shape.templates.hh +++ b/src/Octagonal_Shape.templates.hh @@ -7654,6 +7654,50 @@ Octagonal_Shape<T> PPL_ASSERT(OK()); } +template <typename T> +template <typename U> +void +Octagonal_Shape<T> +::export_interval_constraints(U& dest) const { + if (space_dim > dest.space_dimension()) + throw std::invalid_argument( + "Octagonal_Shape<T>::export_interval_constraints"); + + strong_closure_assign(); + + if (marked_empty()) { + dest.set_empty(); + return; + } + + PPL_DIRTY_TEMP(N, lbound); + PPL_DIRTY_TEMP(N, ubound); + for (dimension_type i = space_dim; i-- > 0; ) { + const dimension_type ii = 2*i; + const dimension_type cii = ii + 1; + + // Set the upper bound. + const N& twice_ub = matrix[cii][ii]; + if (!is_plus_infinity(twice_ub)) { + assign_r(ubound, twice_ub, ROUND_NOT_NEEDED); + div_2exp_assign_r(ubound, ubound, 1, ROUND_UP); + if (!dest.restrict_upper(i, ubound)) + return; + } + + // Set the lower bound. + const N& twice_lb = matrix[ii][cii]; + if (!is_plus_infinity(twice_lb)) { + assign_r(lbound, twice_lb, ROUND_NOT_NEEDED); + neg_assign_r(lbound, lbound, ROUND_NOT_NEEDED); + div_2exp_assign_r(lbound, lbound, 1, ROUND_DOWN); + if (!dest.restrict_lower(i, lbound)) + return; + } + } + +} + /*! \relates Parma_Polyhedra_Library::Octagonal_Shape */ template <typename T> std::ostream&

1 0

[GIT] ppl/ppl(floating_point): New commits
by Roberto Bagnara 21 Sep '10

21 Sep '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=954d985eb038… Merge: a6202d3f6416fd1ca3d1cd40cb25f5418c1354cd d8484a4794afafb978c01c718ea784465d835171 Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Tue Sep 21 09:35:49 2010 +0200 Merge branch 'master' into floating_point URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d8484a4794af… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 20 20:20:16 2010 +0200 Bit_Matrix, Sparse_Matrix: rename the {rows,columns}_erase_to_end() methods into remove_trailing_{rows,columns}(), changing the argument's meaning. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7c153292b94f… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 20 15:07:20 2010 +0200 Dense_Matrix, Sparse_Matrix: rename the erase_to_end() method into remove_trailing_rows(), changing the argument's meaning. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f9bb908fe1ba… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 20 15:06:06 2010 +0200 Grid_Generator_System: remove unused erase_to_end() private method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a4cbaaa95199… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 20 09:17:17 2010 +0200 Fix comment. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=1ac324043fc8… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 20 08:57:39 2010 +0200 Sparse_Row: weaken the lower_bound() requirements on the argument. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=23bd68d17e27… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 20 08:56:47 2010 +0200 Sparse_Row: make the constructor from a Dense_Row work even when Coefficient_traits::const_reference is Coefficient. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=670621abc730… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 19 16:42:03 2010 +0200 MIP_Problem: add a linear_combine() method that takes a Dense_Row and a Sparse_Row, to re-allow dense working costs with sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=33c81bff707a… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 19 16:39:41 2010 +0200 MIP_Problem: add assertion. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e36503c4407e… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 19 16:39:14 2010 +0200 MIP_Problem: use working_cost_type instead of using Row directly. Remove unnecessary specialized implementation for sparse working costs. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=16f3e918c5fc… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 18 19:45:16 2010 +0200 Sparse_Row, Dense_Row: rename find_create() methods into insert(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ae21af77d26c… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 18 18:38:25 2010 +0200 Sparse_Row: add documentation. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=466439403713… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 18 18:34:06 2010 +0200 test/Sparse_Matrix: add test for the Sparse_Row's constructor from a Dense_Row. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2fe651ae4ee6… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 18 18:33:31 2010 +0200 Sparse_Row: add a constructor from a Dense_Row. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9cd84e2dc61e… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 18 18:33:06 2010 +0200 CO_Tree: add a constructor from a sequence of elements. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=35d00bb24afe… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 18 18:32:13 2010 +0200 src/Makefile.am: remove duplicate filenames from the list. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d1c29cf37d2f… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 18 17:15:13 2010 +0200 Indentation fixes, mainly to avoid line wraps. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b1b240cfb51f… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 18 17:14:09 2010 +0200 Fix typo in comment. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d5385797ea5f… Merge: bc20af849dbe0aa805e4e0216a73a94c837b515f 7f6f8d36f5f925c7ef440823d0223a9fa1b72962 Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sat Sep 18 14:48:22 2010 +0200 Merge remote branch 'origin/master' into sparse_matrices URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7f6f8d36f5f9… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Sep 18 09:49:08 2010 +0200 The Solaris sed bug affects all language interfaces (not just the Java one). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=bc20af849dbe… Merge: 90d9338c35f62fa89a86c3b7192b2fa8172d1b20 6cab0f23dfda89b788bf1f7cbb92b5fcbec9dc83 Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Fri Sep 17 21:00:57 2010 +0200 Merge remote branch 'origin/master' into sparse_matrices Conflicts: src/MIP_Problem.cc URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6cab0f23dfda… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Fri Sep 17 17:42:19 2010 +0200 Do destroy the MIP object before returning from solve_with_simplex. Do destroy the Polyhedron object before returning from solve_with_generators. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f1b3b29529f9… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Fri Sep 17 16:35:35 2010 +0200 Prefer neg_assign to the use of unary minus on Coefficient objects. Use add_mul_assign even in code only activated during debugging. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=719f973998fc… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Fri Sep 17 15:42:03 2010 +0200 Mention the correction of an efficiency bug in the C interface. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=90d9338c35f6… Merge: ff67a6bed878e178880fcb16019ebe662e56ea51 d91c33b33dbc8b59332d279550366ed55ae9ae38 Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Sep 16 21:08:52 2010 +0200 Merge remote branch 'origin/master' into sparse_matrices URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ff67a6bed878… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 19:12:40 2010 +0200 MIP_Problem: remove useless reset() from linear_conbine(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c4547fd8dd86… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 19:12:08 2010 +0200 Sparse_Row: optimize the linear_combine() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e4cdaa38008b… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 19:11:39 2010 +0200 Sparse_Row: don't create stored zeroes in combine_needs_second(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=241a4a6fcb61… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 18:42:33 2010 +0200 Sparse_Row: document that linear_combine() parameters must not be 0. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c8d497ffeae2… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 18:38:44 2010 +0200 MIP_Problem: use Row::linear_combine() in linear_combine(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9a2ab566f2c5… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 18:38:14 2010 +0200 Sparse_Row: add a linear_combine() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e752bae13ff6… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 18:37:58 2010 +0200 Dense_Row: add a linear_combine() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=41c1b88df329… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 17:49:08 2010 +0200 MIP_Problem: remove some optimizations meant for dense matrices when using sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=eed6e5900dac… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 17:27:20 2010 +0200 PIP_Tree: remove useless code. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f9c4de14d8ad… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 17:25:23 2010 +0200 PIP_Tree: remove unnecessary temporary variables. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b423bf3864d7… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 17:17:49 2010 +0200 Row, Matrix: avoid inclusion of unnecessary files. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ccad0ef8e489… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 17:17:01 2010 +0200 tests/Sparse_Matrix: run the tests only when using sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=46143fc9a592… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 17:10:52 2010 +0200 CO_Tree: run tests only when using sparse matrices, avoiding compiler errors. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=432dd51be380… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 16:43:54 2010 +0200 PIP_Tree: use Row and Matrix, simplifying code. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e37b5f946405… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 16:16:32 2010 +0200 PIP_Problem: use Row and Matrix, simplifying code. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=15f178d464a4… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 16:15:55 2010 +0200 CO_Tree.defs.hh: include CO_Tree.types.hh. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7994e8aef25d… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 14:50:55 2010 +0200 Declare typedefs for Row and Matrix, and use them in MIP_Problem. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=abc0e90fa8ef… Merge: df7a6c989c0c19ed661e1a0af488096f98fc8d0b 10c6e068e1bffe92c73954fbc1e4943756d7fdb8 Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 14:39:50 2010 +0200 Merge remote branch 'origin/master' into sparse_matrices Conflicts: src/MIP_Problem.cc URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=df7a6c989c0c… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 14:34:23 2010 +0200 tests/Sparse_Matrix/sparserow1: don't trigger assertions in Sparse_Row::lower_bound(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=129497d5d417… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 14:26:23 2010 +0200 PIP_Tree: return if there are no candidates, in find_lexico_minimum_column(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=02cc3ed26b0c… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 11:44:24 2010 +0200 MIP_Problem: add comment. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=856f1052f1a7… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 11:41:44 2010 +0200 MIP_Problem: optimize further steepest_edge_exact_entering_index() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=343524886abe… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 11:32:27 2010 +0200 MIP_Problem: use a hint iterator for insertions in working_cost, in process_pending_constraints(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c68f9092edf4… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 14:56:42 2010 +0200 MIP_Problem: optimize further steepest_edge_float_entering_index() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=30a048b00fe9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 14:56:03 2010 +0200 MIP_Problem: optimize process_pending_constraints() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f2479e2b3e49… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 14:34:19 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=07dfb14d484e… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 14:26:46 2010 +0200 MIP_Problem: fix regression in textbook_entering_index(), introduced in commit 6880A6. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f6a93645a5b8… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:39:00 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows (#4). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2c0d6052ae00… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:38:42 2010 +0200 MIP_Problem: avoid an unnecessary copy of the working_cost row, in second_phase(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2d1cbd6415ae… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:26:37 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows (#3). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8bbd7540511b… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:24:01 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows (#2). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=42a7e27f4267… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:21:59 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows (#1). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b5e34c885640… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 12:36:09 2010 +0200 MIP_Problem: little optimizations for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6880a6746e15… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 12:30:38 2010 +0200 MIP_Problem: optimize textbook_entering_index() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=92e46ffb3c10… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 12:28:37 2010 +0200 MIP_Problem: optimize steepest_edge_float_entering_index() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c2aa82c4a7c9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 12:23:52 2010 +0200 MIP_Problem: optimize steepest_edge_exact_entering_index() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ee1d1d7f9add… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 11:53:55 2010 +0200 MIP_Problem: optimize process_pending_constraints() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=1c643c264345… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 11:53:30 2010 +0200 Sparse_Row: add some assertions. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=24ec2790edae… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 10:39:22 2010 +0200 MIP_Problem: use a sparse working_cost when using sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ffe3720ee015… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 10:38:34 2010 +0200 Sparse_Row: add a constructor and two copy-constructors that take a capacity parameter.

1 0

[GIT] ppl/ppl(master): Bit_Matrix, Sparse_Matrix: rename the {rows, columns}_erase_to_end() methods into remove_trailing_{rows, columns}(), changing the argument's meaning.
by Marco Poletti 20 Sep '10

20 Sep '10

Module: ppl/ppl Branch: master Commit: d8484a4794afafb978c01c718ea784465d835171 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d8484a4794af… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 20 20:20:16 2010 +0200 Bit_Matrix, Sparse_Matrix: rename the {rows,columns}_erase_to_end() methods into remove_trailing_{rows,columns}(), changing the argument's meaning. --- src/Bit_Matrix.defs.hh | 8 ++++---- src/Bit_Matrix.inlines.hh | 18 +++++++++--------- src/Linear_System.cc | 2 +- src/Polyhedron_widenings.cc | 5 +++-- src/conversion.cc | 7 ++++--- src/simplify.cc | 2 +- 6 files changed, 22 insertions(+), 20 deletions(-) diff --git a/src/Bit_Matrix.defs.hh b/src/Bit_Matrix.defs.hh index b7c0629..97191ce 100644 --- a/src/Bit_Matrix.defs.hh +++ b/src/Bit_Matrix.defs.hh @@ -102,11 +102,11 @@ public: */ void add_recycled_row(Bit_Row& row); - //! Erases the rows from the \p first_to_erase -th to the last one. - void rows_erase_to_end(dimension_type first_to_erase); + //! Removes the last \p n rows. + void remove_trailing_rows(dimension_type n); - //! Erases the columns from the \p first_to_erase -th to the last one. - void columns_erase_to_end(dimension_type first_to_erase); + //! Removes the last \p n columns. + void remove_trailing_columns(dimension_type n); //! Resizes the matrix copying the old contents. void resize(dimension_type new_n_rows, dimension_type new_n_columns); diff --git a/src/Bit_Matrix.inlines.hh b/src/Bit_Matrix.inlines.hh index fade705..a4d8c59 100644 --- a/src/Bit_Matrix.inlines.hh +++ b/src/Bit_Matrix.inlines.hh @@ -57,21 +57,21 @@ Bit_Matrix::~Bit_Matrix() { } inline void -Bit_Matrix::rows_erase_to_end(const dimension_type first_to_erase) { - // The first row to be erased cannot be greater +Bit_Matrix::remove_trailing_rows(const dimension_type n) { + // The number of rows to be erased cannot be greater // than the actual number of the rows of the matrix. - PPL_ASSERT(first_to_erase <= rows.size()); - if (first_to_erase < rows.size()) - rows.erase(rows.begin() + first_to_erase, rows.end()); + PPL_ASSERT(n <= rows.size()); + if (n != 0) + rows.erase(rows.end() - n, rows.end()); PPL_ASSERT(OK()); } inline void -Bit_Matrix::columns_erase_to_end(const dimension_type first_to_erase) { - // The first column to be erased cannot be greater +Bit_Matrix::remove_trailing_columns(const dimension_type n) { + // The number of columns to be erased cannot be greater // than the actual number of the columns of the matrix. - PPL_ASSERT(first_to_erase <= row_size); - row_size = first_to_erase; + PPL_ASSERT(n <= row_size); + row_size -= n; PPL_ASSERT(OK()); } diff --git a/src/Linear_System.cc b/src/Linear_System.cc index 9bc4893..3657206 100644 --- a/src/Linear_System.cc +++ b/src/Linear_System.cc @@ -530,7 +530,7 @@ PPL::Linear_System::sort_and_remove_with_sat(Bit_Matrix& sat) { sys.remove_trailing_rows(num_duplicates); sys.set_index_first_pending_row(new_first_pending_row); // ... and the corresponding rows of the saturation matrix. - sat.rows_erase_to_end(sat.num_rows() - num_duplicates); + sat.remove_trailing_rows(num_duplicates); PPL_ASSERT(sys.check_sorted()); // Now the system is sorted. sys.set_sorted(true); diff --git a/src/Polyhedron_widenings.cc b/src/Polyhedron_widenings.cc index 716886b..d8927c8 100644 --- a/src/Polyhedron_widenings.cc +++ b/src/Polyhedron_widenings.cc @@ -97,13 +97,14 @@ PPL::Polyhedron // this is needed in order to widen the polyhedron and not the // corresponding homogenized polyhedral cone. const Constraint_System& y_cs = y.con_sys; - dimension_type num_rows = y_cs.num_rows(); + const dimension_type old_num_rows = y_cs.num_rows(); + dimension_type num_rows = old_num_rows; for (dimension_type i = 0; i < num_rows; ++i) if (y_cs[i].is_tautological()) { --num_rows; std::swap(tmp_sat_g[i], tmp_sat_g[num_rows]); } - tmp_sat_g.rows_erase_to_end(num_rows); + tmp_sat_g.remove_trailing_rows(old_num_rows - num_rows); tmp_sat_g.sort_rows(); // A constraint in `con_sys' is copied to `cs_selected' diff --git a/src/conversion.cc b/src/conversion.cc index bf321e4..a7297ec 100644 --- a/src/conversion.cc +++ b/src/conversion.cc @@ -822,7 +822,7 @@ PPL::Polyhedron::conversion(Linear_System& source, if (source_num_redundant > 0) { PPL_ASSERT(source_num_redundant == source.num_rows() - source_num_rows); source.remove_trailing_rows(source_num_redundant); - sat.columns_erase_to_end(source_num_rows); + sat.remove_trailing_columns(source_num_redundant); } // If `start == 0', then `source' was sorted and remained so. // If otherwise `start > 0', then the two sub-system made by the @@ -839,11 +839,12 @@ PPL::Polyhedron::conversion(Linear_System& source, // We may have identified some redundant rays in `dest', // which have been swapped at the end of the system. if (dest_num_rows < dest.num_rows()) { - dest.remove_trailing_rows(dest.num_rows() - dest_num_rows); + const dimension_type num_removed_rows = dest.num_rows() - dest_num_rows; + dest.remove_trailing_rows(num_removed_rows); // Be careful: we might have erased some of the non-pending rows. if (dest.first_pending_row() > dest_num_rows) dest.unset_pending_rows(); - sat.rows_erase_to_end(dest_num_rows); + sat.remove_trailing_rows(num_removed_rows); } if (dest.is_sorted()) // If the non-pending generators in `dest' are still declared to be diff --git a/src/simplify.cc b/src/simplify.cc index 7d24813..330f93b 100644 --- a/src/simplify.cc +++ b/src/simplify.cc @@ -295,7 +295,7 @@ PPL::Polyhedron::simplify(Linear_System& sys, Bit_Matrix& sat) { // moved to the bottom of `sys' and the corresponding `sat' rows. sys.remove_trailing_rows(old_num_rows - num_rows); sys.unset_pending_rows(); - sat.rows_erase_to_end(num_rows); + sat.remove_trailing_rows(old_num_rows - num_rows); // At this point the first `num_lines_or_equalities' rows of 'sys' // represent the irredundant equalities, while the remaining rows // (i.e., those having indexes from `num_lines_or_equalities' to

1 0

[GIT] ppl/ppl(master): Dense_Matrix, Sparse_Matrix: rename the erase_to_end () method into remove_trailing_rows(), changing the argument's meaning.
by Marco Poletti 20 Sep '10

20 Sep '10

Module: ppl/ppl Branch: master Commit: 7c153292b94f572a5f68a6e578ef44360d64e8f7 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7c153292b94f… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 20 15:07:20 2010 +0200 Dense_Matrix, Sparse_Matrix: rename the erase_to_end() method into remove_trailing_rows(), changing the argument's meaning. --- src/Constraint_System.cc | 7 ++++--- src/Dense_Matrix.defs.hh | 7 ++----- src/Dense_Matrix.inlines.hh | 8 ++++---- src/Generator_System.cc | 7 ++++--- src/Grid_chdims.cc | 4 ++-- src/Grid_simplify.cc | 6 +++--- src/Linear_System.cc | 12 +++++++----- src/MIP_Problem.cc | 2 +- src/PIP_Tree.cc | 10 +++++----- src/Polyhedron.templates.hh | 2 +- src/Polyhedron_nonpublic.cc | 12 +++++++----- src/Polyhedron_public.cc | 13 ++++++++----- src/Sparse_Matrix.defs.hh | 11 +++++------ src/Sparse_Matrix.inlines.hh | 4 ++-- src/conversion.cc | 4 ++-- src/simplify.cc | 5 +++-- 16 files changed, 60 insertions(+), 54 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=7c153292…

1 0

[GIT] ppl/ppl(master): Grid_Generator_System: remove unused erase_to_end() private method.
by Marco Poletti 20 Sep '10

20 Sep '10

Module: ppl/ppl Branch: master Commit: f9bb908fe1ba4c45176563026327d6f28ed025c4 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f9bb908fe1ba… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 20 15:06:06 2010 +0200 Grid_Generator_System: remove unused erase_to_end() private method. --- src/Grid_Generator_System.defs.hh | 6 ------ src/Grid_Generator_System.inlines.hh | 5 ----- 2 files changed, 0 insertions(+), 11 deletions(-) diff --git a/src/Grid_Generator_System.defs.hh b/src/Grid_Generator_System.defs.hh index 1fe1e4a..7d16b29 100644 --- a/src/Grid_Generator_System.defs.hh +++ b/src/Grid_Generator_System.defs.hh @@ -489,12 +489,6 @@ private: */ dimension_type num_columns() const; - /*! \brief - Erases from the matrix all the rows but those having an index less - than \p first_to_erase. - */ - void erase_to_end(dimension_type first_to_erase); - //! Permutes the columns of the matrix. /* \param cycles diff --git a/src/Grid_Generator_System.inlines.hh b/src/Grid_Generator_System.inlines.hh index 7e3e9fc..ece3baf 100644 --- a/src/Grid_Generator_System.inlines.hh +++ b/src/Grid_Generator_System.inlines.hh @@ -55,11 +55,6 @@ Grid_Generator_System::num_columns() const { } inline void -Grid_Generator_System::erase_to_end(dimension_type first_to_erase) { - return Generator_System::erase_to_end(first_to_erase); -} - -inline void Grid_Generator_System ::permute_columns(const std::vector<dimension_type>& cycles) { return Generator_System::permute_columns(cycles);

1 0

[GIT] ppl/ppl(MPI): Merge remote branch 'origin/sparse_matrices' into MPI
by Marco Poletti 20 Sep '10

20 Sep '10

Module: ppl/ppl Branch: MPI Commit: 9c2a7cf107a17a07e5076e25577a69260a583b6e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9c2a7cf107a1… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 20 09:18:34 2010 +0200 Merge remote branch 'origin/sparse_matrices' into MPI Conflicts: src/CO_Tree.templates.hh ---

1 0

[GIT] ppl/ppl(MPI): Fix comment.
by Marco Poletti 20 Sep '10

20 Sep '10

Module: ppl/ppl Branch: MPI Commit: a4cbaaa9519967dd69e60865a18eaafdd21d44a4 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a4cbaaa95199… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 20 09:17:17 2010 +0200 Fix comment. --- src/CO_Tree.templates.hh | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/src/CO_Tree.templates.hh b/src/CO_Tree.templates.hh index 430e387..441c523 100644 --- a/src/CO_Tree.templates.hh +++ b/src/CO_Tree.templates.hh @@ -1,5 +1,5 @@ -/* Sparse_Row class implementation: non-inline template functions. +/* CO_Tree class implementation: non-inline template functions. Copyright (C) 2001-2010 Roberto Bagnara <bagnara(a)cs.unipr.it> This file is part of the Parma Polyhedra Library (PPL).

1 0

[GIT] ppl/ppl(master): Fix comment.
by Marco Poletti 20 Sep '10

20 Sep '10

Module: ppl/ppl Branch: master Commit: a4cbaaa9519967dd69e60865a18eaafdd21d44a4 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a4cbaaa95199… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 20 09:17:17 2010 +0200 Fix comment. --- src/CO_Tree.templates.hh | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/src/CO_Tree.templates.hh b/src/CO_Tree.templates.hh index 430e387..441c523 100644 --- a/src/CO_Tree.templates.hh +++ b/src/CO_Tree.templates.hh @@ -1,5 +1,5 @@ -/* Sparse_Row class implementation: non-inline template functions. +/* CO_Tree class implementation: non-inline template functions. Copyright (C) 2001-2010 Roberto Bagnara <bagnara(a)cs.unipr.it> This file is part of the Parma Polyhedra Library (PPL).

1 0

[GIT] ppl/ppl(sparse_matrices): Fix comment.
by Marco Poletti 20 Sep '10

20 Sep '10

Module: ppl/ppl Branch: sparse_matrices Commit: a4cbaaa9519967dd69e60865a18eaafdd21d44a4 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a4cbaaa95199… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 20 09:17:17 2010 +0200 Fix comment. --- src/CO_Tree.templates.hh | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/src/CO_Tree.templates.hh b/src/CO_Tree.templates.hh index 430e387..441c523 100644 --- a/src/CO_Tree.templates.hh +++ b/src/CO_Tree.templates.hh @@ -1,5 +1,5 @@ -/* Sparse_Row class implementation: non-inline template functions. +/* CO_Tree class implementation: non-inline template functions. Copyright (C) 2001-2010 Roberto Bagnara <bagnara(a)cs.unipr.it> This file is part of the Parma Polyhedra Library (PPL).

1 0