[PPL-devel] [GIT] ppl/ppl(sparse_matrices): MIP_Problem: use std:: sort on a vector instead of using a map, in method OK().

[Marco Poletti]

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

Author: Marco Poletti <poletti.marco at 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;