From b0334271ff31ca880f1d481665284a6d3b057162 Mon Sep 17 00:00:00 2001
From: Michael Andreen <harv@ruin.nu>
Date: Thu, 16 Aug 2007 07:24:00 +0000
Subject: [PATCH] make the componenttree a minimal unoriented tree

---
 src/componenttree.cpp          | 17 +++++++++++++++++
 src/componenttree.h            | 15 +++++++++++++--
 src/test/componenttreetest.cpp | 29 +++++++++++++++++++++++++++++
 3 files changed, 59 insertions(+), 2 deletions(-)

diff --git a/src/componenttree.cpp b/src/componenttree.cpp
index 8390ed2..9059b47 100644
--- a/src/componenttree.cpp
+++ b/src/componenttree.cpp
@@ -67,3 +67,20 @@ ComponentTree::ComponentTree(const std::vector<Component>& components) : _root(0
 
 ComponentTree::~ComponentTree(){
 }
+
+void ComponentTree::makeUnoriented(){
+	removeOriented(&_root);
+}
+
+void ComponentTree::removeOriented(Node* n){
+	for (vector<ComponentTree::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)){
+			delete *c;
+			n->_children.erase(c);
+		}else{
+			++c;
+		}
+	}
+}
diff --git a/src/componenttree.h b/src/componenttree.h
index 7a99c91..212b4d8 100644
--- a/src/componenttree.h
+++ b/src/componenttree.h
@@ -24,8 +24,6 @@
 #include <vector>
 #include "misc.h"
 
-class ComponentTreeTest;
-
 class ComponentTree {
 	public:
 		struct Node {
@@ -36,16 +34,29 @@ class ComponentTree {
 			Component _comp;
 			std::vector<Node*> _children;
 		};
+
+		/**
+		 * Creates a component tree from a list of components.
+		 */
 		ComponentTree(const std::vector<Component>& components);
 
 		~ComponentTree();
 
+		/**
+		 * Transforms the tree into the minimal tree containing all unoriented componentes.
+		 * \todo come up with a better name
+		 */
+		void makeUnoriented();
+
 	private:
 		//Disable these, at least for now.
 		void operator=(const ComponentTree&){};
 		ComponentTree(const ComponentTree&): _root(0,Component()){};
 
+		void removeOriented(Node* n);
+
 		Node _root;
+
 	friend class ComponentTreeTest;
 };
 
diff --git a/src/test/componenttreetest.cpp b/src/test/componenttreetest.cpp
index 222d2d7..3bde9b1 100644
--- a/src/test/componenttreetest.cpp
+++ b/src/test/componenttreetest.cpp
@@ -23,6 +23,7 @@ class TESTNAME : public CPPUNIT_NS::TestFixture
 {
   CPPUNIT_TEST_SUITE( TESTNAME );
   CPPUNIT_TEST( testCreate );
+  CPPUNIT_TEST( testMakeUnoriented );
   CPPUNIT_TEST_SUITE_END();
 
 protected:
@@ -97,6 +98,34 @@ protected:
 
 	}
 
+	void testMakeUnoriented (){
+		GeneOrder go(_validPerm.begin(),_validPerm.end());
+		ComponentTree t(findComponents(go));
+		t.makeUnoriented();
+		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,n->_children.size());
+
+		GeneOrder go2(_validPerm4.begin(),_validPerm4.end());
+		ComponentTree t2(findComponents(go2));
+		t2.makeUnoriented();
+		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)2u,n->_children.size());
+		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 == go22);
+		CPPUNIT_ASSERT(n->_children[1]->_comp == go25);
+		CPPUNIT_ASSERT(n->_children[1]->_children[0]->_children[0]->_comp == go23);
+		CPPUNIT_ASSERT(n->_children[1]->_children[0]->_children[1]->_comp == go24);
+	}
+
 };
 
 CPPUNIT_TEST_SUITE_REGISTRATION( TESTNAME );
-- 
2.39.2