X-Git-Url: https://ruin.nu/git/?a=blobdiff_plain;f=src%2Fgenesorter.cpp;h=3ce89ad493d6163ee568a0f4e3697a1face13946;hb=90e2c43b99205b0d7a300209011231cd8d11f7a0;hp=5f8699c62d0991f504520713d18a517fc555a01f;hpb=d0abe1592fcbb10f4ac303e7b66c384624d4d439;p=germs.git

diff --git a/src/genesorter.cpp b/src/genesorter.cpp
index 5f8699c..3ce89ad 100644
--- a/src/genesorter.cpp
+++ b/src/genesorter.cpp
@@ -24,12 +24,71 @@
 #include "sortaction.h"
 #include "reverseaction.h"
 
+#include "genealgorithms.h"
+
+#include <queue>
+#include <iostream>
+#include <iterator>
 using namespace std;
 
-GeneSorter::ActionList GeneSorter::sort(const GeneOrder& go1){
-	return ActionList();
+GeneSorter::ActionList GeneSorter::sort(const GeneOrder& go){
+	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){
+			safe[0](temp);
+			cout << "Action: " << safe[0].toString() << endl;
+			al.push_back(safe[0]);
+		}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;
 }
 
-GeneSorter::ActionList GeneSorter::safeActions(const GeneOrder& go1){
-	return ActionList();
+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;
+	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));
+		}				
+	}
+	while (pq.size() > 0){
+		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;
+}
+