X-Git-Url: https://ruin.nu/git/?p=germs.git;a=blobdiff_plain;f=src%2Fcomponenttree.cpp;h=5832c3683bcda2ebee8970220a6b60a7906e5ccc;hp=9059b473b5464e0263963d85f844275155f2df29;hb=35ac6a57e0314a8c557f327ec540415ff20bc2dc;hpb=b0334271ff31ca880f1d481665284a6d3b057162

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;
+}