#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(countCycles(temp) != temp.size() - 1){
- 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 other cases here.
+ 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;
+}
+