Small optimization in sort()

[germs.git] / src / genesorter.cpp

diff --git a/src/genesorter.cpp b/src/genesorter.cpp
index 03f19db1d8949ced3f18cb229671b590cb19acc0..3198543fae391f4805211406a5f8f76ccf28c889 100644 (file)
--- a/src/genesorter.cpp
+++ b/src/genesorter.cpp
@@ -26,39 +26,42 @@
 
 #include "genealgorithms.h"
 
+#include "model.h"
+
 #include <queue>
-#include <iostream>
-#include <iterator>
 using namespace std;
 
-GeneSorter::ActionList GeneSorter::sort(const GeneOrder& go){
+struct ScoreCmp {
+       template<typename T>
+       bool operator()(T s1, T s2){
+               return s1.first < s2.first;
+       }
+};
+
+GeneSorter::ActionList GeneSorter::sort(const GeneOrder& go, const Model& m){
        ActionList al;
        GeneOrder temp(go);
-       while(inversionDistance(temp) > 0){
-               cout << "AL: " << al.size() << " : ";
-               cout << "Distance: " << inversionDistance(temp) << " : ";
-               copy(temp.begin(), temp.end(), ostream_iterator<int>(cout, " "));
-               cout << endl;
+       size_t dist = inversionDistance(temp);
+       while(dist > 0){
+               //cout << "Distance: " << inversionDistance(temp) << " : ";
+               //copy(temp.begin(), temp.end(), ostream_iterator<int>(cout, " "));
+               //cout << endl;
                ActionList safe = safeActions(temp);
                if (safe.size() > 0){
-                       safe[0](temp);
-                       al.push_back(safe[0]);
-                       cout << "AL: " << al.size() << " : ";
+                       priority_queue<pair<double,SortAction>,vector<pair<double,SortAction> >, ScoreCmp > pq;
+                       for (ActionList::iterator sa = safe.begin(); sa != safe.end(); ++sa){
+                               pq.push(pair<double,SortAction>(m.score(*sa,temp),*sa));
+                       }
+                       SortAction sa = pq.top().second;
+                       sa(temp);
+                       al.push_back(sa);
+                       --dist;
                }else
                        return ActionList(); //TODO: Need to handle hurdles.
        }
-       cout << "Distance: " << inversionDistance(temp) << " : ";
-       copy(temp.begin(), temp.end(), ostream_iterator<int>(cout, " "));
-       cout << endl;
        return al;
 }
 
-struct ScoreCmp {
-       template<typename T>
-       bool operator()(T s1, T s2){
-               return s1.first < s2.first;
-       }
-};
 
 GeneSorter::ActionList GeneSorter::safeActions(const GeneOrder& go){
        if (countCycles(go) == go.size() - 1)
@@ -69,19 +72,20 @@ GeneSorter::ActionList GeneSorter::safeActions(const GeneOrder& go){
        for (size_t i = 0; i < intervals.size(); ++i){
                if (intervals[i].oriented && intervals[i].first != intervals[i].second){
                        SortAction sa(new ReverseAction(intervals[i]));
-                       size_t score = scoreActions(go,sa);
-                       cout << "Inversion: " << min(intervals[i].first,intervals[i].second) << ":" << max(intervals[i].first,intervals[i].second)-1 << " Score: " << score <<  endl;
+                       size_t score = scoreAction(go,sa);
+                       //cout << "Inversion: " << min(intervals[i].first,intervals[i].second) << ":" << max(intervals[i].first,intervals[i].second)-1 << " Score: " << score <<  endl;
                        pq.push(pair<size_t,SortAction>(score,sa));
                }                               
        }
-       while (pq.size() > 0){
+       size_t max = pq.top().first;
+       while (pq.size() > 0 && pq.top().first >= max){
                al.push_back(pq.top().second);
                pq.pop();
        }
        return al;
 }
 
-size_t GeneSorter::scoreActions(const GeneOrder& go, SortAction& sa){
+size_t GeneSorter::scoreAction(const GeneOrder& go, SortAction& sa){
        GeneOrder temp(go);
        sa(temp);
        vector<Interval> intervals = findIntervals(temp);