--- /dev/null
+/***************************************************************************
+ * Copyright (C) 2006 by Michael Andreen *
+ * andreen@student.chalmers.se *
+ * *
+ * This program is free software; you can redistribute it and/or modify *
+ * it under the terms of the GNU General Public License as published by *
+ * the Free Software Foundation; either version 2 of the License, or *
+ * (at your option) any later version. *
+ * *
+ * This program is distributed in the hope that it will be useful, *
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of *
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
+ * GNU General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU General Public License *
+ * along with this program; if not, write to the *
+ * Free Software Foundation, Inc., *
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA *
+ ***************************************************************************/
+
+#include "componenttree.h"
+
+#include <map>
+using namespace std;
+
+ComponentTree::Node::Node(Node* parent, Component comp): _parent(parent), _comp(comp){
+ if (_parent){
+ _parent->_children.push_back(this);
+ }
+}
+
+ComponentTree::Node::~Node(){
+ for (vector<Node*>::iterator c = _children.begin();
+ c != _children.end(); ++c){
+ delete *c;
+ }
+}
+
+ComponentTree::ComponentTree(const std::vector<Component>& components) : _root(0,Component()){
+ map<size_t,Component> starting;
+ map<size_t,Component> ending;
+ size_t max = 0;
+ for (vector<Component>::const_iterator c = components.begin(); c != components.end(); ++c){
+ starting.insert(pair<size_t,Component>(c->i1,*c));
+ ending.insert(pair<size_t,Component>(c->i2,*c));
+ max = (c->i2 > max ? c->i2 : max);
+ }
+
+ Node* q = &_root;
+ Node* p = new Node(q,starting[0]);
+
+ for (size_t i = 1; i < max; ++i){
+ map<size_t,Component>::iterator c = starting.find(i);
+ if (c != starting.end()){
+ if (ending.find(i) == ending.end()){
+ q = new Node(p,Component());
+ }
+ p = new Node(q,c->second);
+
+ }else if (ending.find(i) != ending.end()){
+ p = q->_parent;
+ q = p->_parent;
+ }
+ }
+
+}
+
+ComponentTree::~ComponentTree(){
+}