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

diff --git a/src/componenttree.cpp b/src/componenttree.cpp
index 9059b47..f28c7ee 100644
--- a/src/componenttree.cpp
+++ b/src/componenttree.cpp
@@ -20,7 +20,6 @@
 
 #include "componenttree.h"
 
-#include <map>
 using namespace std;
 
 ComponentTree::Node::Node(Node* parent, Component comp): _parent(parent), _comp(comp){
@@ -36,7 +35,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 +49,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 +69,25 @@ 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;
+		_root->_parent = 0;
+	}
 }
 
 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,52 @@ 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;
+}
+
+void ComponentTree::branches (Node* n, map<Node*,size_t> & b){
+	if (n->_children.empty() && n->_parent != 0){
+		Node* p = n;
+		while (p->_parent != 0 && p->_children.size() < 2)
+			p = p->_parent;
+		++b[p];
+		return;
+	}
+	for (vector<Node*>::iterator c = n->_children.begin();
+			c != n->_children.end(); ++c){
+		branches(*c,b);
+	}
+}
+
+size_t ComponentTree::shortBranches(){
+	map<Node*,size_t> br;
+	branches(_root,br);
+	if (_root->_children.size() < 2 && _root->_comp.sign != 0){
+		br[_root]++;
+	}
+	size_t sb = 0;
+	for (map<Node*,size_t>::iterator b = br.begin(); b != br.end(); ++b){
+		if (b->second == 1)
+			++sb;
+	}
+	return sb;
+}
+