[PPL-devel] [GIT] ppl/ppl(sparse_matrices): PIP_Tree.cc: don' t uselessly copy the candidates set in find_lexico_minimum_column_in_set().

[Marco Poletti]

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

Author: Marco Poletti <poletti.marco at gmail.com>
Date:   Thu Mar 11 13:11:37 2010 +0100

PIP_Tree.cc: don't uselessly copy the candidates set in find_lexico_minimum_column_in_set().

---

 src/PIP_Tree.cc |   43 +++++++++++++++++++++++--------------------
 1 files changed, 23 insertions(+), 20 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index edb0cea..bac549a 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -419,30 +419,26 @@ column_lower(const PIP_Tree_Node::matrix_type& tableau,
 /* Find the column j in revised simplex tableau such as
   - j is in candidates
   - (column j) / pivot_row[j] is lexico-minimal
+  When this function returns, candidates contains the minimum(s) column(s)
+  index(es).
 */
-bool
-find_lexico_minimum_column_in_set(const std::set<dimension_type>& candidates,
+void
+find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates,
                                   const PIP_Tree_Node::matrix_type& tableau,
                                   const std::vector<dimension_type>& mapping,
                                   const std::vector<bool>& basis,
                                   PIP_Tree_Node::
-                                    matrix_row_const_reference_type pivot_row,
-                                  dimension_type& j_out) {
-  const dimension_type num_cols = tableau.num_columns();
+                                  matrix_row_const_reference_type pivot_row) {
   const dimension_type num_vars = mapping.size();
-  if (candidates.empty()) {
-    j_out = num_cols;
-    return false;
-  }
-  std::set<dimension_type> current_candidates = candidates;
+  PPL_ASSERT(!candidates.empty());
   for (dimension_type var_index=0; var_index<num_vars; ++var_index) {
     if (basis[var_index])
       continue;
     const dimension_type row_index = mapping[var_index];
     PIP_Tree_Node::matrix_row_const_reference_type row = tableau[row_index];
     PIP_Tree_Node::matrix_const_row_const_iterator row_end = row.end();
-    std::set<dimension_type>::iterator i = current_candidates.begin();
-    std::set<dimension_type>::iterator i_end = current_candidates.end();
+    std::set<dimension_type>::iterator i = candidates.begin();
+    std::set<dimension_type>::iterator i_end = candidates.end();
     PPL_ASSERT(i != i_end);
     dimension_type min_index = *i;
     ++i;
@@ -457,7 +453,7 @@ find_lexico_minimum_column_in_set(const std::set<dimension_type>& candidates,
       if (current_itr != row_end)
         for (++current_itr; current_itr!=row_end; ++current_itr)
           if ((*current_itr).second != 0)
-            current_candidates.erase((*current_itr).first);
+            candidates.erase((*current_itr).first);
     } else {
       PPL_ASSERT((*current_itr).first == min_index);
       PIP_Tree_Node::matrix_const_row_const_iterator last_itr = current_itr;
@@ -488,13 +484,11 @@ find_lexico_minimum_column_in_set(const std::set<dimension_type>& candidates,
         // If min_value < challenger_value, we don't add *i to new_candidates,
         // so it will be ignored in the next pass.
       }
-      std::swap(current_candidates,new_candidates);
+      std::swap(candidates,new_candidates);
     }
-    PPL_ASSERT(!current_candidates.empty());
+    PPL_ASSERT(!candidates.empty());
   }
-  PPL_ASSERT(!current_candidates.empty());
-  j_out = *(current_candidates.begin());
-  return true;
+  PPL_ASSERT(!candidates.empty());
 }
 
 /* Find the column j in revised simplex tableau such as
@@ -516,8 +510,17 @@ find_lexico_minimum_column(const PIP_Tree_Node::matrix_type& tableau,
     if (c > 0)
       candidates.insert(j);
   }
-  return find_lexico_minimum_column_in_set(candidates,tableau,mapping,basis,
-                                           pivot_row, j_out);
+  if (candidates.empty()) {
+    j_out = num_cols;
+    return false;
+  }
+
+  find_lexico_minimum_column_in_set(candidates,tableau,mapping,basis,
+                                    pivot_row);
+  PPL_ASSERT(!candidates.empty());
+  j_out = *(candidates.begin());
+
+  return true;
 }
 
 // Divide all coefficients in row x and denominator y by their GCD.