1 /***************************************************************************
2 * Copyright (C) 2006 by Michael Andreen *
3 * andreen@student.chalmers.se *
5 * This program is free software; you can redistribute it and/or modify *
6 * it under the terms of the GNU General Public License as published by *
7 * the Free Software Foundation; either version 2 of the License, or *
8 * (at your option) any later version. *
10 * This program is distributed in the hope that it will be useful, *
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13 * GNU General Public License for more details. *
15 * You should have received a copy of the GNU General Public License *
16 * along with this program; if not, write to the *
17 * Free Software Foundation, Inc., *
18 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA *
19 ***************************************************************************/
21 #include "componenttree.h"
25 ComponentTree::Node::Node(Node* parent, Component comp): _parent(parent), _comp(comp){
27 _parent->_children.push_back(this);
31 ComponentTree::Node::~Node(){
32 for (vector<Node*>::iterator c = _children.begin();
33 c != _children.end(); ++c){
39 * Implemented as O(n*log n), should be possible in O(n), but this is pretty clean, and should
42 ComponentTree::ComponentTree(const std::vector<Component>& components) : _root(new Node(0,Component())){
43 map<size_t,Component> starting;
44 map<size_t,Component> ending;
46 for (vector<Component>::const_iterator c = components.begin(); c != components.end(); ++c){
47 starting.insert(pair<size_t,Component>(c->i1,*c));
48 ending.insert(pair<size_t,Component>(c->i2,*c));
49 max = (c->i2 > max ? c->i2 : max);
53 Node* p = new Node(q,starting[0]);
55 for (size_t i = 1; i < max; ++i){
56 map<size_t,Component>::iterator c = starting.find(i);
57 if (c != starting.end()){
58 if (ending.find(i) == ending.end()){
59 q = new Node(p,Component());
61 p = new Node(q,c->second);
63 }else if (ending.find(i) != ending.end()){
71 ComponentTree::~ComponentTree(){
75 void ComponentTree::makeUnoriented(){
76 removeOriented(_root);
77 while (_root->_children.size() == 1 && _root->_comp.sign == 0){
78 Node* n = _root->_children[0];
79 _root->_children.clear();
85 void ComponentTree::removeOriented(Node* n){
86 for (vector<Node*>::iterator c = n->_children.begin();
87 c != n->_children.end(); /*empty*/){
89 if ((*c)->_children.empty() && (*c)->_comp.sign == 0){
91 n->_children.erase(c);
98 size_t ComponentTree::countLeaves(){
99 size_t leaves = countLeaves(_root);
100 if (_root->_children.size() < 2 && _root->_comp.sign != 0){
106 size_t ComponentTree::countLeaves(Node* n){
107 if (n != _root && n->_children.empty()){
111 for (vector<Node*>::iterator c = n->_children.begin();
112 c != n->_children.end(); ++c){
113 leaves += countLeaves(*c);
118 void ComponentTree::branches (Node* n, map<Node*,size_t> & b){
119 if (n->_children.empty() && n->_parent != 0){
121 while (p->_parent != 0 && p->_children.size() < 2)
126 for (vector<Node*>::iterator c = n->_children.begin();
127 c != n->_children.end(); ++c){
132 size_t ComponentTree::shortBranches(){
133 map<Node*,size_t> br;
135 if (_root->_children.size() < 2 && _root->_comp.sign != 0){
139 for (map<Node*,size_t>::iterator b = br.begin(); b != br.end(); ++b){