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"
34 GeneSorter::ActionList GeneSorter::sort(const GeneOrder& go){
37 while(inversionDistance(temp) > 0){
38 cout << "AL: " << al.size() << " : ";
39 cout << "Distance: " << inversionDistance(temp) << " : ";
40 copy(temp.begin(), temp.end(), ostream_iterator<int>(cout, " "));
42 ActionList safe = safeActions(temp);
45 al.push_back(safe[0]);
46 cout << "AL: " << al.size() << " : ";
48 return ActionList(); //TODO: Need to handle hurdles.
50 cout << "Distance: " << inversionDistance(temp) << " : ";
51 copy(temp.begin(), temp.end(), ostream_iterator<int>(cout, " "));
58 bool operator()(T s1, T s2){
59 return s1.first < s2.first;
63 GeneSorter::ActionList GeneSorter::safeActions(const GeneOrder& go){
64 if (countCycles(go) == go.size() - 1)
67 vector<Interval> intervals = findIntervals(go);
68 priority_queue<pair<size_t,SortAction>,vector<pair<size_t,SortAction> >, ScoreCmp > pq;
69 for (size_t i = 0; i < intervals.size(); ++i){
70 if (intervals[i].oriented && intervals[i].first != intervals[i].second){
71 SortAction sa(new ReverseAction(intervals[i]));
72 size_t score = scoreActions(go,sa);
73 cout << "Inversion: " << min(intervals[i].first,intervals[i].second) << ":" << max(intervals[i].first,intervals[i].second)-1 << " Score: " << score << endl;
74 pq.push(pair<size_t,SortAction>(score,sa));
77 while (pq.size() > 0){
78 al.push_back(pq.top().second);
84 size_t GeneSorter::scoreActions(const GeneOrder& go, SortAction& sa){
87 vector<Interval> intervals = findIntervals(temp);
89 for (vector<Interval>::iterator in = intervals.begin(); in != intervals.end(); ++in){