BUGFIX: forgot to set parent to 0 on child when removing parent node

[germs.git] / src / componenttree.cpp

diff --git a/src/componenttree.cpp b/src/componenttree.cpp
index 8390ed2557b35a41e63112c365b8999c73e9264d..f28c7eed83efbf03f1c966db5729526d1101fbeb 100644 (file)
--- 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,4 +69,78 @@ ComponentTree::ComponentTree(const std::vector<Component>& components) : _root(0
 }
 
 ComponentTree::~ComponentTree(){
+       delete _root;
 }
+
+void ComponentTree::makeUnoriented(){
+       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<Node*>::iterator c = n->_children.begin();
+                       c != n->_children.end(); /*empty*/){
+               removeOriented(*c);
+               if ((*c)->_children.empty() && (*c)->_comp.sign == 0){
+                       delete *c;
+                       n->_children.erase(c);
+               }else{
+                       ++c;
+               }
+       }
+}
+
+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;
+}
+