src/componenttree.cpp

   1 /***************************************************************************
   2  *   Copyright (C) 2006 by Michael Andreen                                 *
   3  *   andreen@student.chalmers.se                                           *
   4  *                                                                         *
   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.                                   *
   9  *                                                                         *
  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.                          *
  14  *                                                                         *
  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  ***************************************************************************/
  20
  21 #include "componenttree.h"
  22
  23 #include <map>
  24 using namespace std;
  25
  26 ComponentTree::Node::Node(Node* parent, Component comp): _parent(parent), _comp(comp){
  27         if (_parent){
  28                 _parent->_children.push_back(this);
  29         }
  30 }
  31
  32 ComponentTree::Node::~Node(){
  33         for (vector<Node*>::iterator c = _children.begin();
  34                         c != _children.end(); ++c){
  35                 delete *c;
  36         }
  37 }
  38
  39 ComponentTree::ComponentTree(const std::vector<Component>& components) : _root(0,Component()){
  40         map<size_t,Component> starting;
  41         map<size_t,Component> ending;
  42         size_t max = 0;
  43         for (vector<Component>::const_iterator c = components.begin(); c != components.end(); ++c){
  44                 starting.insert(pair<size_t,Component>(c->i1,*c));
  45                 ending.insert(pair<size_t,Component>(c->i2,*c));
  46                 max = (c->i2 > max ? c->i2 : max);
  47         }
  48
  49         Node* q = &_root;
  50         Node* p = new Node(q,starting[0]);
  51
  52         for (size_t i = 1; i < max; ++i){
  53                 map<size_t,Component>::iterator c = starting.find(i);
  54                 if (c != starting.end()){
  55                         if (ending.find(i) == ending.end()){
  56                                 q = new Node(p,Component());
  57                         }
  58                         p = new Node(q,c->second);
  59
  60                 }else if (ending.find(i) != ending.end()){
  61                         p = q->_parent;
  62                         q = p->_parent;
  63                 }
  64         }
  65
  66 }
  67
  68 ComponentTree::~ComponentTree(){
  69 }
  70
  71 void ComponentTree::makeUnoriented(){
  72         removeOriented(&_root);
  73 }
  74
  75 void ComponentTree::removeOriented(Node* n){
  76         for (vector<ComponentTree::Node*>::iterator c = n->_children.begin();
  77                         c != n->_children.end(); /*empty*/){
  78                 removeOriented(*c);
  79                 if ((*c)->_children.size() == 0 && ((*c)->_comp.i2 == 0 || (*c)->_comp.sign == 0)){
  80                         delete *c;
  81                         n->_children.erase(c);
  82                 }else{
  83                         ++c;
  84                 }
  85         }
  86 }