#include "sortaction.h"
#include "reverseaction.h"
+#include "genealgorithms.h"
+
+#include "model.h"
+
+#include <queue>
using namespace std;
-GeneSorter::ActionList GeneSorter::sort(const GeneOrder& go1){
- return ActionList();
+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 << "Distance: " << inversionDistance(temp) << " : ";
+ //copy(temp.begin(), temp.end(), ostream_iterator<int>(cout, " "));
+ //cout << endl;
+ ActionList safe = safeActions(temp);
+ if (safe.size() > 0){
+ 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);
+ }else
+ return ActionList(); //TODO: Need to handle hurdles.
+ }
+ return al;
}
-GeneSorter::ActionList GeneSorter::safeActions(const GeneOrder& go1){
- return ActionList();
+
+GeneSorter::ActionList GeneSorter::safeActions(const GeneOrder& go){
+ if (countCycles(go) == go.size() - 1)
+ return ActionList();
+ ActionList al;
+ 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 = 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));
+ }
+ }
+ 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::scoreAction(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;
+}
+