count leaves

[germs.git] / src / componenttree.cpp

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