Module: ppl/ppl Branch: sparse_matrices Commit: 70cb7f3a54ea6f97489dc8b52b8ea11fbd30167e URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=70cb7f3a54ea6...

Author: Marco Poletti poletti.marco@gmail.com Date: Mon Mar 22 14:14:00 2010 +0100

MIP_Problem: use std::sort on a vector instead of using a map, in method OK().

---

src/MIP_Problem.cc | 22 ++++++++++++---------- 1 files changed, 12 insertions(+), 10 deletions(-)

diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 52a4817..6c97648 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -32,7 +32,7 @@ site: http://www.cs.unipr.it/ppl/ . */ #include "Scalar_Products.defs.hh" #include <stdexcept> #include <deque> -#include <map> +#include <vector> #include <algorithm> #include <cmath>

@@ -2391,24 +2391,26 @@ PPL::MIP_Problem::OK() const { } { // Needed to sort accesses to tableau_j, improving performance. - std::map<dimension_type,dimension_type> var_in_base; + typedef std::vector<std::pair<dimension_type,dimension_type> > + pair_vector_t; + pair_vector_t vars_in_base; for (dimension_type i = base.size(); i-- > 0; ) - var_in_base[base[i]] = i; + vars_in_base.push_back(std::make_pair(base[i],i)); + + std::sort(vars_in_base.begin(),vars_in_base.end());

for (dimension_type j = tableau_nrows; j-- > 0; ) { matrix_row_const_reference_type tableau_j = tableau[j]; - std::map<dimension_type,dimension_type>::iterator i - = var_in_base.begin(); - std::map<dimension_type,dimension_type>::iterator i_end - = var_in_base.end(); + pair_vector_t::iterator i = vars_in_base.begin(); + pair_vector_t::iterator i_end = vars_in_base.end(); matrix_const_row_const_iterator itr = tableau_j.begin(); matrix_const_row_const_iterator itr_end = tableau_j.end(); - for ( ; i!=i_end; ++i) { + for ( ; i!=i_end && itr!=itr_end; ++i) { // tableau[i][base[i] must be different from zero. // tableau[i][base[j], with i different from j, must not be a zero. - if ((itr != itr_end) && (*itr).first < i->first) + if ((*itr).first < i->first) itr = tableau_j.lower_bound((*itr).first, itr); - if (i->second != j && (itr != itr_end) && (*itr).first == i->first + if (i->second != j && (*itr).first == i->first && (*itr).second != 0) { #ifndef NDEBUG cerr << "tableau[i][base[i] must be different from zero" << endl;