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

Author: Marco Poletti poletti.marco@gmail.com Date: Wed Mar 24 14:45:17 2010 +0100

PIP_Tree.cc: use std::vector instead of std::set in find_lexico_minimum_column().

---

src/PIP_Tree.cc | 27 +++++++++++++++------------ 1 files changed, 15 insertions(+), 12 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index ed775ea..c838a45 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -346,7 +346,7 @@ column_lower(const PIP_Tree_Node::matrix_type& tableau, index(es). */ void -find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, +find_lexico_minimum_column_in_set(std::vector<dimension_type>& candidates, const PIP_Tree_Node::matrix_type& tableau, const std::vector<dimension_type>& mapping, const std::vector<bool>& basis, @@ -355,12 +355,14 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, const dimension_type num_vars = mapping.size();

PPL_ASSERT(!candidates.empty()); + // This is used as a set, it is always sorted. + std::vector<dimension_type> new_candidates; for (dimension_type var_index = 0; var_index < num_vars; ++var_index) { - std::set<dimension_type> new_candidates; - std::set<dimension_type>::const_iterator i = candidates.begin(); - std::set<dimension_type>::const_iterator i_end = candidates.end(); + new_candidates.clear(); + std::vector<dimension_type>::const_iterator i = candidates.begin(); + std::vector<dimension_type>::const_iterator i_end = candidates.end(); PPL_ASSERT(!candidates.empty()); - new_candidates.insert(*i); + new_candidates.push_back(*i); dimension_type min_column = *i; ++i; if (i == i_end) @@ -391,10 +393,10 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, new_candidates.clear(); min_column = *i; sij_b = &sij_a; - new_candidates.insert(min_column); + new_candidates.push_back(min_column); } else // Optimizing for: lhs == 0 && rhs == 0; - new_candidates.insert(*i); + new_candidates.push_back(*i); } } } else { @@ -440,7 +442,7 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, min_column = *i; row_jb = row_ja; sij_b = &sij_a; - new_candidates.insert(min_column); + new_candidates.push_back(min_column); } } else { // lhs is actually the left-hand side with toggled sign. @@ -448,14 +450,14 @@ find_lexico_minimum_column_in_set(std::set<dimension_type>& candidates, lhs = *sij_b * *row_ja; rhs = sij_a * *row_jb; if (lhs == rhs) - new_candidates.insert(*i); + new_candidates.push_back(*i); else if (lhs < rhs) { new_candidates.clear(); min_column = *i; row_jb = row_ja; sij_b = &sij_a; - new_candidates.insert(min_column); + new_candidates.push_back(min_column); } } } @@ -477,11 +479,12 @@ find_lexico_minimum_column(const PIP_Tree_Node::matrix_type& tableau, const dimension_type start_j, dimension_type& j_out) { const dimension_type num_cols = tableau.num_columns(); - std::set<dimension_type> candidates; + // This is used as a set, it is always sorted. + std::vector<dimension_type> candidates; for (dimension_type j = start_j; j < num_cols; ++j) { const Coefficient& c = pivot_row[j]; if (c > 0) - candidates.insert(j); + candidates.push_back(j); } if (candidates.empty()) { j_out = num_cols;