From efe42ca948704593c847996d0ae8da71d15bb75b Mon Sep 17 00:00:00 2001 From: Michael Andreen Date: Fri, 3 Aug 2007 13:38:54 +0000 Subject: [PATCH] genesorter now uses models to score actions, specific actions are now derived from SortActionImpl instead of SortAction, the latter is just an empty shell now --- src/genesorter.cpp | 35 +++++++++++++++------------- src/genesorter.h | 3 ++- src/main.cpp | 20 ++++++++++++---- src/models.cpp | 1 + src/reverseaction.h | 10 ++++---- src/sortaction.h | 46 ++++++++++++++++++++++++++++++------- src/test/genesortertest.cpp | 10 ++++---- 7 files changed, 87 insertions(+), 38 deletions(-) diff --git a/src/genesorter.cpp b/src/genesorter.cpp index 3ce89ad..602a6dd 100644 --- a/src/genesorter.cpp +++ b/src/genesorter.cpp @@ -26,12 +26,19 @@ #include "genealgorithms.h" +#include "model.h" + #include -#include -#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(inversionDistance(temp) > 0){ @@ -40,24 +47,19 @@ GeneSorter::ActionList GeneSorter::sort(const GeneOrder& go){ //cout << endl; ActionList safe = safeActions(temp); if (safe.size() > 0){ - safe[0](temp); - cout << "Action: " << safe[0].toString() << endl; - 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),*sa)); + } + SortAction sa = pq.top().second; + sa(temp); + al.push_back(sa); }else return ActionList(); //TODO: Need to handle hurdles. } - cout << "Distance: " << inversionDistance(temp) << " : "; - copy(temp.begin(), temp.end(), ostream_iterator(cout, " ")); - cout << endl; return al; } -struct ScoreCmp { - template - bool operator()(T s1, T s2){ - return s1.first < s2.first; - } -}; GeneSorter::ActionList GeneSorter::safeActions(const GeneOrder& go){ if (countCycles(go) == go.size() - 1) @@ -73,7 +75,8 @@ GeneSorter::ActionList GeneSorter::safeActions(const GeneOrder& go){ pq.push(pair(score,sa)); } } - while (pq.size() > 0){ + size_t max = pq.top().first; + while (pq.size() > 0 && pq.top().first >= max){ al.push_back(pq.top().second); pq.pop(); } diff --git a/src/genesorter.h b/src/genesorter.h index e06bedf..6ec4047 100644 --- a/src/genesorter.h +++ b/src/genesorter.h @@ -25,6 +25,7 @@ class SortAction; class GeneOrder; +class Model; /** * Sorts genes @@ -39,7 +40,7 @@ class GeneSorter{ * Takes a GeneOrder, finds the actions to transform it into a sorted * permutation and returns the list with required actions. */ - ActionList sort(const GeneOrder& go1); + ActionList sort(const GeneOrder& go1, const Model& m); /** * Find the safe actions for this GeneOrder. diff --git a/src/main.cpp b/src/main.cpp index 153aff4..90d3564 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -12,6 +12,7 @@ using namespace std; #include "modelidentifier.h" #include "genesorter.h" #include "sortaction.h" +#include "genealgorithms.h" #include "model.h" int main(int argc, char** argv){ @@ -60,15 +61,24 @@ int main(int argc, char** argv){ //TODO: Identify ModelIdentifier mi(ann); priority_queue > pq = mi.identify(go); - while (pq.size() > 0){ - cout << "Model: " << pq.top().second.name() << " score: " << pq.top().first << endl; - pq.pop(); - } + Model model = pq.top().second; + //while (pq.size() > 0){ + cout << "Model: " << model.name() << " score: " << pq.top().first << endl; + //pq.pop(); + //} + + cout << "Distance: " << inversionDistance(go) << " : "; + copy(go.begin(), go.end(), ostream_iterator(cout, " ")); + cout << endl; //TODO: Chose a sorter GeneSorter so; //TODO: Sort - GeneSorter::ActionList al = so.sort(go); + GeneSorter::ActionList al = so.sort(go,model); + + for (GeneSorter::ActionList::iterator sa = al.begin(); sa != al.end(); ++sa){ + cout << "Action: " << sa->toString() << " model score: " << model.score(*sa) << endl; + } //TODO: Print result return EXIT_SUCCESS; } diff --git a/src/models.cpp b/src/models.cpp index cd89ef8..0a7577a 100644 --- a/src/models.cpp +++ b/src/models.cpp @@ -19,6 +19,7 @@ ***************************************************************************/ #include "models.h" +#include "reverseaction.h" using namespace std; diff --git a/src/reverseaction.h b/src/reverseaction.h index 006c9eb..d69af75 100644 --- a/src/reverseaction.h +++ b/src/reverseaction.h @@ -23,6 +23,7 @@ #include "sortaction.h" #include "genealgorithms.h" +#include "geneorder.h" #include #include @@ -32,15 +33,16 @@ * * \author Michael Andreen */ -class ReverseAction : public SortAction{ +class ReverseAction : public SortActionImpl{ public: /** * Creates a new reverse action for the interval [i,j] */ - ReverseAction(size_t i, size_t j): SortAction(0),_i(i),_j(j){ + ReverseAction(size_t i, size_t j): _i(i),_j(j){ } - ReverseAction(Interval i): SortAction(0){ + + ReverseAction(Interval i){ _i = std::min(i.first,i.second); _j = std::max(i.first,i.second)-1; } @@ -53,7 +55,7 @@ class ReverseAction : public SortAction{ return go; } - virtual bool operator==(const SortAction& sa) const{ + virtual bool operator==(const SortActionImpl& sa) const{ if (const ReverseAction* psa = dynamic_cast(&sa)){ if (_i == psa->_i && _j == psa->_j) return true; diff --git a/src/sortaction.h b/src/sortaction.h index 66c337c..c56d0ee 100644 --- a/src/sortaction.h +++ b/src/sortaction.h @@ -24,6 +24,29 @@ #include #include class GeneOrder; + + +class SortActionImpl{ + public: + + virtual ~SortActionImpl(){}; + + /** + * Applies the action on the GeneOrder and returning it. + */ + virtual GeneOrder& operator()(GeneOrder& go) const = 0; + + /** + * Compares sort actions. + */ + virtual bool operator==(const SortActionImpl& sa) const = 0; + + /** + * Gives a string representation of the action, for output + */ + virtual std::string toString() const = 0; +}; + /** * Abstraction of a sort action, all child actions has to be immutable. * @@ -31,44 +54,51 @@ class GeneOrder; */ class SortAction{ public: - typedef std::tr1::shared_ptr ActionPointer; + typedef std::tr1::shared_ptr ActionPointer; /** * Creates a new sort action, given a specified action. * SortAction promises to remove the given action. */ - SortAction(SortAction* sa): _action(sa){ + SortAction(SortActionImpl* sa): _action(sa){ } SortAction(const SortAction& sa): _action(sa._action){ } - virtual const SortAction& operator=(const SortAction& sa){ + const SortAction& operator=(const SortAction& sa){ if (this != &sa) _action = sa._action; return *this; } - virtual ~SortAction(){}; + ~SortAction(){}; /** * Applies the action on the GeneOrder and returning it. */ - virtual GeneOrder& operator()(GeneOrder& go) const{ + GeneOrder& operator()(GeneOrder& go) const{ return (*_action)(go); } /** * Compares sort actions. */ - virtual bool operator==(const SortAction& sa) const{ - return (*_action) == (sa._action.get() == 0 ? sa : *sa._action); + bool operator==(const SortAction& sa) const{ + return (*_action) == (*sa._action); + } + + /** + * Compares sort actions. + */ + bool operator==(const SortActionImpl& sa) const{ + return (*_action) == sa; } /** * Gives a string representation of the action, for output */ - virtual std::string toString() const{ + std::string toString() const{ return _action->toString(); } private: diff --git a/src/test/genesortertest.cpp b/src/test/genesortertest.cpp index 1625dbd..c84ead8 100644 --- a/src/test/genesortertest.cpp +++ b/src/test/genesortertest.cpp @@ -5,6 +5,8 @@ #include #include #include +#include +#include #include #include @@ -56,11 +58,11 @@ protected: void testSort (){ GeneSorter so; GeneOrder go(_validPerm.begin(),_validPerm.end()); - GeneSorter::ActionList al = so.sort(go); + GeneSorter::ActionList al = so.sort(go,Model(new Models::ModelImpl)); CPPUNIT_ASSERT_EQUAL((size_t)0u,al.size()); GeneOrder go2(_validPerm2.begin(),_validPerm2.end()); - al = so.sort(go2); + al = so.sort(go2,Model(new Models::ModelImpl)); CPPUNIT_ASSERT_EQUAL((size_t)1u,al.size()); CPPUNIT_ASSERT(al[0] == ReverseAction(2,3)); @@ -68,7 +70,7 @@ protected: CPPUNIT_ASSERT(equal(go.begin(),go.end(),go2.begin())); GeneOrder go3(_validPerm3.begin(),_validPerm3.end()); - al = so.sort(go3); + al = so.sort(go3,Model(new Models::ModelImpl)); CPPUNIT_ASSERT_EQUAL((size_t)5u,al.size()); for (size_t i = 0; i < al.size(); ++i) al[i](go3); @@ -76,7 +78,7 @@ protected: CPPUNIT_ASSERT(equal(go3.begin(),go3.end(),perm)); GeneOrder go4(_validPerm4.begin(),_validPerm4.end()); - al = so.sort(go4); + al = so.sort(go4,Model(new Models::ModelImpl)); CPPUNIT_ASSERT_EQUAL((size_t)13u,al.size()); for (size_t i = 0; i < al.size(); ++i) al[i](go3); -- 2.39.2