1 /***************************************************************************
2 * Copyright (C) 2006 by Michael Andreen *
3 * andreen@student.chalmers.se *
5 * This program is free software; you can redistribute it and/or modify *
6 * it under the terms of the GNU General Public License as published by *
7 * the Free Software Foundation; either version 2 of the License, or *
8 * (at your option) any later version. *
10 * This program is distributed in the hope that it will be useful, *
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13 * GNU General Public License for more details. *
15 * You should have received a copy of the GNU General Public License *
16 * along with this program; if not, write to the *
17 * Free Software Foundation, Inc., *
18 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA *
19 ***************************************************************************/
21 #include "genesorter.h"
23 #include "geneorder.h"
24 #include "sortaction.h"
25 #include "reverseaction.h"
27 #include "genealgorithms.h"
36 bool operator()(T s1, T s2){
37 return s1.first < s2.first;
41 GeneSorter::ActionList GeneSorter::sort(const GeneOrder& go, const Model& m){
44 while(inversionDistance(temp) > 0){
45 //cout << "Distance: " << inversionDistance(temp) << " : ";
46 //copy(temp.begin(), temp.end(), ostream_iterator<int>(cout, " "));
48 ActionList safe = safeActions(temp);
50 priority_queue<pair<double,SortAction>,vector<pair<double,SortAction> >, ScoreCmp > pq;
51 for (ActionList::iterator sa = safe.begin(); sa != safe.end(); ++sa){
52 pq.push(pair<double,SortAction>(m.score(*sa),*sa));
54 SortAction sa = pq.top().second;
58 return ActionList(); //TODO: Need to handle hurdles.
64 GeneSorter::ActionList GeneSorter::safeActions(const GeneOrder& go){
65 if (countCycles(go) == go.size() - 1)
68 vector<Interval> intervals = findIntervals(go);
69 priority_queue<pair<size_t,SortAction>,vector<pair<size_t,SortAction> >, ScoreCmp > pq;
70 for (size_t i = 0; i < intervals.size(); ++i){
71 if (intervals[i].oriented && intervals[i].first != intervals[i].second){
72 SortAction sa(new ReverseAction(intervals[i]));
73 size_t score = scoreAction(go,sa);
74 //cout << "Inversion: " << min(intervals[i].first,intervals[i].second) << ":" << max(intervals[i].first,intervals[i].second)-1 << " Score: " << score << endl;
75 pq.push(pair<size_t,SortAction>(score,sa));
78 size_t max = pq.top().first;
79 while (pq.size() > 0 && pq.top().first >= max){
80 al.push_back(pq.top().second);
86 size_t GeneSorter::scoreAction(const GeneOrder& go, SortAction& sa){
89 vector<Interval> intervals = findIntervals(temp);
91 for (vector<Interval>::iterator in = intervals.begin(); in != intervals.end(); ++in){