From 35ac6a57e0314a8c557f327ec540415ff20bc2dc Mon Sep 17 00:00:00 2001
From: Michael Andreen <harv@ruin.nu>
Date: Thu, 16 Aug 2007 08:20:42 +0000
Subject: [PATCH] count leaves

---
 src/componenttree.cpp          | 41 +++++++++++++++++++++++++++++-----
 src/componenttree.h            |  7 ++++--
 src/test/componenttreetest.cpp | 25 +++++++++++++++++----
 3 files changed, 62 insertions(+), 11 deletions(-)

diff --git a/src/componenttree.cpp b/src/componenttree.cpp
index 9059b47..5832c36 100644
--- 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;
@@ -46,7 +50,7 @@ ComponentTree::ComponentTree(const std::vector<Component>& components) : _root(0
 		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){
@@ -66,17 +70,24 @@ ComponentTree::ComponentTree(const std::vector<Component>& components) : _root(0
 }
 
 ComponentTree::~ComponentTree(){
+	delete _root;
 }
 
 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){
-	for (vector<ComponentTree::Node*>::iterator c = n->_children.begin();
+	for (vector<Node*>::iterator c = n->_children.begin();
 			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{
@@ -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 212b4d8..aad4ddb 100644
--- a/src/componenttree.h
+++ b/src/componenttree.h
@@ -48,14 +48,17 @@ class ComponentTree {
 		 */
 		void makeUnoriented();
 
+		size_t countLeaves();
+
 	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);
+		size_t countLeaves(Node* n);
 
-		Node _root;
+		Node* _root;
 
 	friend class ComponentTreeTest;
 };
diff --git a/src/test/componenttreetest.cpp b/src/test/componenttreetest.cpp
index 3bde9b1..d85c59a 100644
--- 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( testCountLeaves );
   CPPUNIT_TEST_SUITE_END();
 
 protected:
@@ -61,7 +62,7 @@ protected:
 	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));
@@ -78,7 +79,7 @@ protected:
 
 		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));
@@ -102,7 +103,7 @@ protected:
 		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));
@@ -111,7 +112,7 @@ protected:
 		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));
@@ -126,6 +127,22 @@ protected:
 		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 );
-- 
2.39.2