sorting without hurdles seems to work

[germs.git] / src / genesorter.cpp

diff --git a/src/genesorter.cpp b/src/genesorter.cpp
index 8126d6aaa5781336ab03ba3a822f4d72f4c8820d..03f19db1d8949ced3f18cb229671b590cb19acc0 100644 (file)
--- a/src/genesorter.cpp
+++ b/src/genesorter.cpp
@@ -27,26 +27,69 @@
 #include "genealgorithms.h"
 
 #include <queue>
+#include <iostream>
+#include <iterator>
 using namespace std;
 
 GeneSorter::ActionList GeneSorter::sort(const GeneOrder& go){
        ActionList al;
        GeneOrder temp(go);
-       while(inversionDistance(go) > 0){
-               ActionList safe = safeActions(go);
+       while(inversionDistance(temp) > 0){
+               cout << "AL: " << al.size() << " : ";
+               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() << " : ";
                }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)
                return ActionList();
        ActionList al;
-       //al.push_back(SortAction(new ReverseAction(2,3)));
+       vector<Interval> intervals = findIntervals(go);
+       priority_queue<pair<size_t,SortAction>,vector<pair<size_t,SortAction> >, ScoreCmp > pq;
+       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;
+                       pq.push(pair<size_t,SortAction>(score,sa));
+               }                               
+       }
+       while (pq.size() > 0){
+               al.push_back(pq.top().second);
+               pq.pop();
+       }
        return al;
 }
+
+size_t GeneSorter::scoreActions(const GeneOrder& go, SortAction& sa){
+       GeneOrder temp(go);
+       sa(temp);
+       vector<Interval> intervals = findIntervals(temp);
+       int o = 0;
+       for (vector<Interval>::iterator in = intervals.begin(); in != intervals.end(); ++in){
+               if (in->oriented)
+                       ++o;
+       }
+       return o;
+}
+