#include "genealgorithms.h"
#include "geneorder.h"
+#include "componenttree.h"
#include <algorithm>
#include <set>
};
-int countCycles(const GeneOrder& go){
- int cycles = 0;
+size_t countCycles(const GeneOrder& go){
+ size_t cycles = 0;
set<size_t> marked;
vector<Interval> intervals = findIntervals(go);
vector<Interval> points = findIntervalsAtPoints(intervals);
return cycles;
}
+size_t inversionDistance(const GeneOrder& go){
+ size_t distance = go.size() - 1;
+ distance -= countCycles(go);
+
+ ComponentTree t(findComponents(go));
+ t.makeUnoriented();
+ size_t leaves = t.countLeaves();
+ distance += leaves;
+ if (leaves % 2 != 0){
+ size_t sb = t.shortBranches();
+ if (sb == 0)
+ distance += 1;
+ }
+
+ return distance;
+}
+
int sign(Gene g){
if (g > 0)
return 1;
os[Sdir.top()] = (os[Sdir.top()] == os[s] ? os[s] : 0);
s = Sdir.top();
}
- if (go[i] > 0 && dir[i] == dir[s] && i - s == p[i] - p[s])
- components.push_back(Component(p[s],p[i],(s+1 == i ? 0 : os[s])));
-
+ if (go[i] > 0 && dir[i] == dir[s] && static_cast<Gene>(i - s) == p[i] - p[s])
+ components.push_back(Component(p[s],p[i],(s+1 == i ? 0 : os[s]),s,i));
//Reverse
if (p[i-1] < p[i])
os[Srev.top()] *= (os[Srev.top()] == os[s] ? 1 : 0);
s = Srev.top();
}
- if (go[i] < 0 && rev[i] == rev[s] && i - s == p[s] - p[i])
- components.push_back(Component(-p[s],-p[i],os[s]));
+ if (go[i] < 0 && rev[i] == rev[s] && static_cast<Gene>(i - s) == p[s] - p[i])
+ components.push_back(Component(-p[s],-p[i],(s+1 == i ? 0 : os[s]),s,i));
//Update stacks
if (go[i] > 0)
return components;
}
+int sign2(Gene g){
+ if (g < 0)
+ return -1;
+ return 1;
+}
/**
*
*/
std::vector<Interval> findIntervals(const GeneOrder& go){
- vector<Interval> intervals(go.size()-1,Interval(go.size(),go.size()));
+ const size_t max = go.size();
+ vector<Interval> intervals(go.size()-1,Interval(max,max,false));
size_t n = 0;
- for (GeneOrder::iterator g = go.begin(); g != go.end(); ++g, ++n){
+ const GeneOrder::iterator end = go.end();
+ for (GeneOrder::iterator g = go.begin(); g != end; ++g, ++n){
size_t i = abs(*g);
- if (i < go.size() - 1)
- intervals[i].first = n + (*g >= 0 ? 1 : 0);
- if (i > 0)
- intervals[i-1].second = n + (*g < 0 ? 1 : 0);
+ if (i < max - 1){
+ Interval& curr = intervals[i];
+ curr.first = n + (*g >= 0 ? 1 : 0);
+
+ if (curr.second == max)
+ curr.oriented = *g < 0;
+ else
+ curr.oriented ^= *g < 0;
+ }
+ if (i > 0){
+ Interval& prev = intervals[i-1];
+ prev.second = n + (*g < 0 ? 1 : 0);
+
+ if (prev.first == max)
+ prev.oriented = *g < 0;
+ else
+ prev.oriented ^= *g < 0;
+ }
+
}
return intervals;
}
*/
std::vector<Interval> findIntervalsAtPoints(const vector<Interval>& intervals){
size_t max = intervals.size()+1;
- vector<Interval> points(max,Interval(max,max));
+ vector<Interval> points(max,Interval(max,max,false));
size_t n = 0;
for (vector<Interval>::const_iterator i = intervals.begin(); i != intervals.end(); ++i, ++n){
if (points[i->first].first == max){