#include "componenttree.h"
-#include <map>
using namespace std;
ComponentTree::Node::Node(Node* parent, Component comp): _parent(parent), _comp(comp){
}
}
-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;
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){
}
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;
+ }
+}
+
+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;
+}
+