From: Michael Andreen Date: Wed, 15 Aug 2007 11:37:28 +0000 (+0000) Subject: inital commit of componenttree with associated changes X-Git-Tag: v0.1~23 X-Git-Url: https://ruin.nu/git/?p=germs.git;a=commitdiff_plain;h=dcd966c5fca7dca53ca1f605f70f13f019d29771 inital commit of componenttree with associated changes --- diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 25cda6d..ba50614 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -13,7 +13,7 @@ ADD_DEFINITIONS(-Wall -pedantic -g) INCLUDE_DIRECTORIES(.) ADD_LIBRARY(GeneSort geneorder genealgorithms modelidentifier genesorter model - models) + models componenttree) ADD_EXECUTABLE(genesort main.cpp) SET(GENELIBS doublefann GeneSort) diff --git a/src/componenttree.cpp b/src/componenttree.cpp new file mode 100644 index 0000000..8390ed2 --- /dev/null +++ b/src/componenttree.cpp @@ -0,0 +1,69 @@ +/*************************************************************************** + * Copyright (C) 2006 by Michael Andreen * + * andreen@student.chalmers.se * + * * + * This program is free software; you can redistribute it and/or modify * + * it under the terms of the GNU General Public License as published by * + * the Free Software Foundation; either version 2 of the License, or * + * (at your option) any later version. * + * * + * This program is distributed in the hope that it will be useful, * + * but WITHOUT ANY WARRANTY; without even the implied warranty of * + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * + * GNU General Public License for more details. * + * * + * You should have received a copy of the GNU General Public License * + * along with this program; if not, write to the * + * Free Software Foundation, Inc., * + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA * + ***************************************************************************/ + +#include "componenttree.h" + +#include +using namespace std; + +ComponentTree::Node::Node(Node* parent, Component comp): _parent(parent), _comp(comp){ + if (_parent){ + _parent->_children.push_back(this); + } +} + +ComponentTree::Node::~Node(){ + for (vector::iterator c = _children.begin(); + c != _children.end(); ++c){ + delete *c; + } +} + +ComponentTree::ComponentTree(const std::vector& components) : _root(0,Component()){ + map starting; + map ending; + size_t max = 0; + for (vector::const_iterator c = components.begin(); c != components.end(); ++c){ + starting.insert(pair(c->i1,*c)); + ending.insert(pair(c->i2,*c)); + max = (c->i2 > max ? c->i2 : max); + } + + Node* q = &_root; + Node* p = new Node(q,starting[0]); + + for (size_t i = 1; i < max; ++i){ + map::iterator c = starting.find(i); + if (c != starting.end()){ + if (ending.find(i) == ending.end()){ + q = new Node(p,Component()); + } + p = new Node(q,c->second); + + }else if (ending.find(i) != ending.end()){ + p = q->_parent; + q = p->_parent; + } + } + +} + +ComponentTree::~ComponentTree(){ +} diff --git a/src/componenttree.h b/src/componenttree.h new file mode 100644 index 0000000..7a99c91 --- /dev/null +++ b/src/componenttree.h @@ -0,0 +1,52 @@ +/*************************************************************************** + * Copyright (C) 2006 by Michael Andreen * + * andreen@student.chalmers.se * + * * + * This program is free software; you can redistribute it and/or modify * + * it under the terms of the GNU General Public License as published by * + * the Free Software Foundation; either version 2 of the License, or * + * (at your option) any later version. * + * * + * This program is distributed in the hope that it will be useful, * + * but WITHOUT ANY WARRANTY; without even the implied warranty of * + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * + * GNU General Public License for more details. * + * * + * You should have received a copy of the GNU General Public License * + * along with this program; if not, write to the * + * Free Software Foundation, Inc., * + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA * + ***************************************************************************/ + +#ifndef __COMPONENTTREE_H__ +#define __COMPONENTTREE_H__ + +#include +#include "misc.h" + +class ComponentTreeTest; + +class ComponentTree { + public: + struct Node { + Node(Node* parent, Component comp); + ~Node(); + + Node* _parent; + Component _comp; + std::vector _children; + }; + ComponentTree(const std::vector& components); + + ~ComponentTree(); + + private: + //Disable these, at least for now. + void operator=(const ComponentTree&){}; + ComponentTree(const ComponentTree&): _root(0,Component()){}; + + Node _root; + friend class ComponentTreeTest; +}; + +#endif diff --git a/src/genealgorithms.cpp b/src/genealgorithms.cpp index f1e66aa..174c6f7 100644 --- a/src/genealgorithms.cpp +++ b/src/genealgorithms.cpp @@ -20,6 +20,7 @@ #include "genealgorithms.h" #include "geneorder.h" +#include "componenttree.h" #include #include @@ -146,7 +147,7 @@ std::vector findComponents(const GeneOrder& go){ s = Sdir.top(); } if (go[i] > 0 && dir[i] == dir[s] && static_cast(i - s) == p[i] - p[s]) - components.push_back(Component(p[s],p[i],(s+1 == i ? 0 : os[s]))); + components.push_back(Component(p[s],p[i],(s+1 == i ? 0 : os[s]),s,i)); //Reverse if (p[i-1] < p[i]) @@ -162,7 +163,7 @@ std::vector findComponents(const GeneOrder& go){ s = Srev.top(); } if (go[i] < 0 && rev[i] == rev[s] && static_cast(i - s) == p[s] - p[i]) - components.push_back(Component(-p[s],-p[i],(s+1 == i ? 0 : os[s]))); + components.push_back(Component(-p[s],-p[i],(s+1 == i ? 0 : os[s]),s,i)); //Update stacks if (go[i] > 0) diff --git a/src/genealgorithms.h b/src/genealgorithms.h index 6bc133f..1d74e71 100644 --- a/src/genealgorithms.h +++ b/src/genealgorithms.h @@ -24,16 +24,8 @@ #include class GeneOrder; +struct Component; -struct Component{ - Component(int b,int e,int s):begin(b),end(e),sign(s){} - bool operator==(const Component& c){ - return begin == c.begin && end == c.end && sign == c.sign; - } - int begin; - int end; - int sign; -}; struct Interval{ Interval(size_t f,size_t s,bool o = false):first(f),second(s),oriented(o){} diff --git a/src/misc.h b/src/misc.h index b9fb777..ee0b578 100644 --- a/src/misc.h +++ b/src/misc.h @@ -23,4 +23,16 @@ typedef int Gene; +struct Component{ + Component(int b = 0,int e = 0,int s = 0,size_t i1 = 0, size_t i2 = 0):begin(b),end(e),sign(s),i1(i1), i2(i2){} + bool operator==(const Component& c){ + return begin == c.begin && end == c.end && sign == c.sign && i1 == c.i1 && i2 == c.i2; + } + int begin; + int end; + int sign; + size_t i1; + size_t i2; +}; + #endif diff --git a/src/test/CMakeLists.txt b/src/test/CMakeLists.txt index 47a09fa..ca4fb56 100644 --- a/src/test/CMakeLists.txt +++ b/src/test/CMakeLists.txt @@ -9,7 +9,7 @@ SET(CMAKE_VERBOSE_MAKEFILE OFF) SET(TESTSRC geneordertest genealgorithmstest modelidentifiertest - genesortertest) + genesortertest componenttreetest) ADD_EXECUTABLE(tester main ${TESTSRC}) TARGET_LINK_LIBRARIES(tester ${GENELIBS} cppunit) diff --git a/src/test/componenttreetest.cpp b/src/test/componenttreetest.cpp new file mode 100644 index 0000000..3e0b505 --- /dev/null +++ b/src/test/componenttreetest.cpp @@ -0,0 +1,101 @@ +#include +#include + +#include +#include +#include +#include + +#include +#include +using namespace std; + +/* + * A test case that is designed to produce + * example errors and failures. + * + */ + +#define TESTNAME ComponentTreeTest + + +class TESTNAME : public CPPUNIT_NS::TestFixture +{ + CPPUNIT_TEST_SUITE( TESTNAME ); + CPPUNIT_TEST( testCreate ); + CPPUNIT_TEST_SUITE_END(); + +protected: + vector _validPerm; + vector _validPerm2; + vector _validPerm3; + vector _validPerm4; + +public: + + void setUp (){ + int validPerm[] = {1,2,3,4}; + _validPerm.assign(validPerm,validPerm+4); + int validPerm2[] = {1,-3,-2,4}; + _validPerm2.assign(validPerm2,validPerm2+4); + int validPerm3[] = {0,-2,-1,4,3,5,-8,6,7,9}; + _validPerm3.assign(validPerm3,validPerm3+10); + int validPerm4[] = {-3,1,2,4,6,5,7,-15,-13,-14,-12,-10,-11,-9,8}; + _validPerm4.assign(validPerm4,validPerm4+15); + + } + +protected: + + size_t count(ComponentTree::Node* n, bool all = false){ + size_t num = 0; + if (all || n->_comp.i2 != 0) + num += 1; + for (vector::iterator c = n->_children.begin(); + c != n->_children.end(); ++c){ + num += count(*c,all); + } + return num; + } + void testCreate (){ + GeneOrder go(_validPerm.begin(),_validPerm.end()); + ComponentTree t(findComponents(go)); + ComponentTree::Node* n = &t._root; + + CPPUNIT_ASSERT_EQUAL((size_t)4u,count(n)); + CPPUNIT_ASSERT_EQUAL((size_t)5u,count(n,true)); + CPPUNIT_ASSERT_EQUAL((size_t)4u,n->_children.size()); + + Component go10(0,1,0,0,1); + Component go11(1,2,0,1,2); + Component go12(2,3,0,2,3); + Component go13(3,4,0,3,4); + CPPUNIT_ASSERT(n->_children[0]->_comp == go10); + CPPUNIT_ASSERT(n->_children[1]->_comp == go11); + CPPUNIT_ASSERT(n->_children[2]->_comp == go12); + CPPUNIT_ASSERT(n->_children[3]->_comp == go13); + + GeneOrder go2(_validPerm4.begin(),_validPerm4.end()); + ComponentTree t2(findComponents(go2)); + n = &t2._root; + + CPPUNIT_ASSERT_EQUAL((size_t)6u,count(n)); + CPPUNIT_ASSERT_EQUAL((size_t)9u,count(n,true)); + CPPUNIT_ASSERT_EQUAL((size_t)3u,n->_children.size()); + Component go20(1,2,0,2,3); + Component go21(0,4,0,0,4); + Component go22(4,7,1,4,7); + Component go23(-15,-12,-1,8,11); + Component go24(-12,-9,-1,11,14); + Component go25(7,16,0,7,16); + CPPUNIT_ASSERT(n->_children[0]->_comp == go21); + CPPUNIT_ASSERT(n->_children[1]->_comp == go22); + CPPUNIT_ASSERT(n->_children[2]->_comp == go25); + + } + +}; + +CPPUNIT_TEST_SUITE_REGISTRATION( TESTNAME ); + +#undef TESTNAME diff --git a/src/test/genealgorithmstest.cpp b/src/test/genealgorithmstest.cpp index 43ba77f..ab7f9b8 100644 --- a/src/test/genealgorithmstest.cpp +++ b/src/test/genealgorithmstest.cpp @@ -166,10 +166,10 @@ protected: GeneOrder go(_validPerm.begin(),_validPerm.end()); vector v = findComponents(go); CPPUNIT_ASSERT_EQUAL((size_t)4u,v.size()); - Component go10(0,1,0); - Component go11(1,2,0); - Component go12(2,3,0); - Component go13(3,4,0); + Component go10(0,1,0,0,1); + Component go11(1,2,0,1,2); + Component go12(2,3,0,2,3); + Component go13(3,4,0,3,4); CPPUNIT_ASSERT(go10 == v[0]); CPPUNIT_ASSERT(go11 == v[1]); CPPUNIT_ASSERT(go12 == v[2]); @@ -178,12 +178,12 @@ protected: GeneOrder go2(_validPerm3.begin(),_validPerm3.end()); v = findComponents(go2); CPPUNIT_ASSERT_EQUAL((size_t)6u,v.size()); - Component go20(1,2,0); - Component go21(0,4,0); - Component go22(4,7,1); - Component go23(-15,-12,-1); - Component go24(-12,-9,-1); - Component go25(7,16,0); + Component go20(1,2,0,2,3); + Component go21(0,4,0,0,4); + Component go22(4,7,1,4,7); + Component go23(-15,-12,-1,8,11); + Component go24(-12,-9,-1,11,14); + Component go25(7,16,0,7,16); CPPUNIT_ASSERT(go20 == v[0]); CPPUNIT_ASSERT(go21 == v[1]); CPPUNIT_ASSERT(go22 == v[2]);