count leaves

diff --git a/src/componenttree.cpp b/src/componenttree.cpp
index 9059b473b5464e0263963d85f844275155f2df29..5832c3683bcda2ebee8970220a6b60a7906e5ccc 100644 (file)
--- a/src/componenttree.cpp
+++ b/src/componenttree.cpp
@@ -36,7 +36,11 @@ ComponentTree::Node::~Node(){
        }
 }
 
        }
 }
 

-ComponentTree::ComponentTree(const std::vector<Component>& components) : _root(0,Component()){
+/**
+ * Implemented as O(n*log n), should be possible in O(n), but this is pretty clean, and should
+ * be fast enough
+ */
+ComponentTree::ComponentTree(const std::vector<Component>& components) : _root(new Node(0,Component())){

        map<size_t,Component> starting;
        map<size_t,Component> ending;
        size_t max = 0;
        map<size_t,Component> starting;
        map<size_t,Component> ending;
        size_t max = 0;


@@ -46,7 +50,7 @@ ComponentTree::ComponentTree(const std::vector<Component>& components) : _root(0
                max = (c->i2 > max ? c->i2 : max);
        }
 
                max = (c->i2 > max ? c->i2 : max);
        }
 

-       Node* q = &_root;
+       Node* q = _root;

        Node* p = new Node(q,starting[0]);
 
        for (size_t i = 1; i < max; ++i){
        Node* p = new Node(q,starting[0]);
 
        for (size_t i = 1; i < max; ++i){


@@ -66,17 +70,24 @@ ComponentTree::ComponentTree(const std::vector<Component>& components) : _root(0
 }
 
 ComponentTree::~ComponentTree(){
 }
 
 ComponentTree::~ComponentTree(){

+       delete _root;

 }
 
 void ComponentTree::makeUnoriented(){
 }
 
 void ComponentTree::makeUnoriented(){

-       removeOriented(&_root);
+       removeOriented(_root);
+       while (_root->_children.size() == 1 && _root->_comp.sign == 0){
+               Node* n = _root->_children[0];
+               _root->_children.clear();
+               delete _root;
+               _root = n;
+       }

 }
 
 void ComponentTree::removeOriented(Node* n){
 }
 
 void ComponentTree::removeOriented(Node* n){

-       for (vector<ComponentTree::Node*>::iterator c = n->_children.begin();
+       for (vector<Node*>::iterator c = n->_children.begin();

                        c != n->_children.end(); /*empty*/){
                removeOriented(*c);
                        c != n->_children.end(); /*empty*/){
                removeOriented(*c);

-               if ((*c)->_children.size() == 0 && ((*c)->_comp.i2 == 0 || (*c)->_comp.sign == 0)){
+               if ((*c)->_children.empty() && (*c)->_comp.sign == 0){

                        delete *c;
                        n->_children.erase(c);
                }else{
                        delete *c;
                        n->_children.erase(c);
                }else{


@@ -84,3 +95,23 @@ void ComponentTree::removeOriented(Node* n){
                }
        }
 }
                }
        }
 }

+
+size_t ComponentTree::countLeaves(){
+       size_t leaves = countLeaves(_root);
+       if (_root->_children.size() < 2 && _root->_comp.sign != 0){
+               ++leaves;
+       }
+       return leaves;
+}
+
+size_t ComponentTree::countLeaves(Node* n){
+       if (n != _root && n->_children.empty()){
+               return 1;
+       }
+       size_t leaves = 0;
+       for (vector<Node*>::iterator c = n->_children.begin();
+                       c != n->_children.end(); ++c){
+               leaves += countLeaves(*c);
+       }
+       return leaves;
+}

diff --git a/src/componenttree.h b/src/componenttree.h
index 212b4d8edc0a03fee77b4c9143adced17cbb8cec..aad4ddbdd076cc4c6c5cbb42437f1c61199696fd 100644 (file)
--- a/src/componenttree.h
+++ b/src/componenttree.h
@@ -48,14 +48,17 @@ class ComponentTree {
                 */
                void makeUnoriented();
 
                 */
                void makeUnoriented();
 

+               size_t countLeaves();
+

        private:
                //Disable these, at least for now.
                void operator=(const ComponentTree&){};
        private:
                //Disable these, at least for now.
                void operator=(const ComponentTree&){};

-               ComponentTree(const ComponentTree&): _root(0,Component()){};
+               ComponentTree(const ComponentTree&): _root(0){};

 
                void removeOriented(Node* n);
 
                void removeOriented(Node* n);

+               size_t countLeaves(Node* n);

 
 

-               Node _root;
+               Node* _root;

 
        friend class ComponentTreeTest;
 };
 
        friend class ComponentTreeTest;
 };

diff --git a/src/test/componenttreetest.cpp b/src/test/componenttreetest.cpp
index 3bde9b196eb94ebaee11cd650b14eb6d71e70ec3..d85c59a429c9a0fffd693a6d001da5e37fc38fb8 100644 (file)
--- a/src/test/componenttreetest.cpp
+++ b/src/test/componenttreetest.cpp
@@ -24,6 +24,7 @@ class TESTNAME : public CPPUNIT_NS::TestFixture
   CPPUNIT_TEST_SUITE( TESTNAME );
   CPPUNIT_TEST( testCreate );
   CPPUNIT_TEST( testMakeUnoriented );
   CPPUNIT_TEST_SUITE( TESTNAME );
   CPPUNIT_TEST( testCreate );
   CPPUNIT_TEST( testMakeUnoriented );

+  CPPUNIT_TEST( testCountLeaves );

   CPPUNIT_TEST_SUITE_END();
 
 protected:
   CPPUNIT_TEST_SUITE_END();
 
 protected:


@@ -61,7 +62,7 @@ protected:
        void testCreate (){
                GeneOrder go(_validPerm.begin(),_validPerm.end());
                ComponentTree t(findComponents(go));
        void testCreate (){
                GeneOrder go(_validPerm.begin(),_validPerm.end());
                ComponentTree t(findComponents(go));

-               ComponentTree::Node* n = &t._root;
+               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,count(n));
                CPPUNIT_ASSERT_EQUAL((size_t)5u,count(n,true));


@@ -78,7 +79,7 @@ protected:
 
                GeneOrder go2(_validPerm4.begin(),_validPerm4.end());
                ComponentTree t2(findComponents(go2));
 
                GeneOrder go2(_validPerm4.begin(),_validPerm4.end());
                ComponentTree t2(findComponents(go2));

-               n = &t2._root;
+               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)6u,count(n));
                CPPUNIT_ASSERT_EQUAL((size_t)9u,count(n,true));


@@ -102,7 +103,7 @@ protected:
                GeneOrder go(_validPerm.begin(),_validPerm.end());
                ComponentTree t(findComponents(go));
                t.makeUnoriented();
                GeneOrder go(_validPerm.begin(),_validPerm.end());
                ComponentTree t(findComponents(go));
                t.makeUnoriented();

-               ComponentTree::Node* n = &t._root;
+               ComponentTree::Node* n = t._root;

 
                CPPUNIT_ASSERT_EQUAL((size_t)0u,count(n));
                CPPUNIT_ASSERT_EQUAL((size_t)1u,count(n,true));
 
                CPPUNIT_ASSERT_EQUAL((size_t)0u,count(n));
                CPPUNIT_ASSERT_EQUAL((size_t)1u,count(n,true));


@@ -111,7 +112,7 @@ protected:
                GeneOrder go2(_validPerm4.begin(),_validPerm4.end());
                ComponentTree t2(findComponents(go2));
                t2.makeUnoriented();
                GeneOrder go2(_validPerm4.begin(),_validPerm4.end());
                ComponentTree t2(findComponents(go2));
                t2.makeUnoriented();

-               n = &t2._root;
+               n = t2._root;

 
                CPPUNIT_ASSERT_EQUAL((size_t)4u,count(n));
                CPPUNIT_ASSERT_EQUAL((size_t)6u,count(n,true));
 
                CPPUNIT_ASSERT_EQUAL((size_t)4u,count(n));
                CPPUNIT_ASSERT_EQUAL((size_t)6u,count(n,true));


@@ -126,6 +127,22 @@ protected:
                CPPUNIT_ASSERT(n->_children[1]->_children[0]->_children[1]->_comp == go24);
        }
 
                CPPUNIT_ASSERT(n->_children[1]->_children[0]->_children[1]->_comp == go24);
        }
 

+       void testCountLeaves (){
+               GeneOrder go(_validPerm.begin(),_validPerm.end());
+               ComponentTree t(findComponents(go));
+               t.makeUnoriented();
+
+               //CPPUNIT_ASSERT_EQUAL((size_t)0u,t.countLeaves());
+
+               GeneOrder go2(_validPerm4.begin(),_validPerm4.end());
+               ComponentTree t2(findComponents(go2));
+               t2.makeUnoriented();
+               ComponentTree::Node* n = t2._root;
+               CPPUNIT_ASSERT_EQUAL((size_t)2u,n->_children.size());
+               CPPUNIT_ASSERT_EQUAL(false,n->_children.empty());
+               CPPUNIT_ASSERT_EQUAL((size_t)3u,t2.countLeaves());
+       }
+

 };
 
 CPPUNIT_TEST_SUITE_REGISTRATION( TESTNAME );
 };
 
 CPPUNIT_TEST_SUITE_REGISTRATION( TESTNAME );