X-Git-Url: https://ruin.nu/git/?p=germs.git;a=blobdiff_plain;f=src%2Fgenesorter.cpp;h=3198543fae391f4805211406a5f8f76ccf28c889;hp=8643702250f82ac6b90bbfd08f6b65aaf0e85ee2;hb=34293060b5be57f6e2ea620ad4c3ff0f94e1d305;hpb=8827131c37c21740b5ac8acf6da9ff598de3f166 diff --git a/src/genesorter.cpp b/src/genesorter.cpp index 8643702..3198543 100644 --- a/src/genesorter.cpp +++ b/src/genesorter.cpp @@ -26,27 +26,74 @@ #include "genealgorithms.h" +#include "model.h" + #include using namespace std; -GeneSorter::ActionList GeneSorter::sort(const GeneOrder& go){ +struct ScoreCmp { + template + 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(countCycles(temp) != temp.size() - 1){ - ActionList safe = safeActions(go); + size_t dist = inversionDistance(temp); + while(dist > 0){ + //cout << "Distance: " << inversionDistance(temp) << " : "; + //copy(temp.begin(), temp.end(), ostream_iterator(cout, " ")); + //cout << endl; + ActionList safe = safeActions(temp); if (safe.size() > 0){ - safe[0](temp); - al.push_back(safe[0]); + priority_queue,vector >, ScoreCmp > pq; + for (ActionList::iterator sa = safe.begin(); sa != safe.end(); ++sa){ + pq.push(pair(m.score(*sa,temp),*sa)); + } + SortAction sa = pq.top().second; + sa(temp); + al.push_back(sa); + --dist; }else - return ActionList(); //TODO: Need to handle other cases here. + return ActionList(); //TODO: Need to handle hurdles. } return al; } + 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 intervals = findIntervals(go); + priority_queue,vector >, 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(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 intervals = findIntervals(temp); + int o = 0; + for (vector::iterator in = intervals.begin(); in != intervals.end(); ++in){ + if (in->oriented) + ++o; + } + return o; +} +