X-Git-Url: https://ruin.nu/git/?p=germs.git;a=blobdiff_plain;f=src%2Fcomponenttree.cpp;fp=src%2Fcomponenttree.cpp;h=8390ed2557b35a41e63112c365b8999c73e9264d;hp=0000000000000000000000000000000000000000;hb=dcd966c5fca7dca53ca1f605f70f13f019d29771;hpb=8e617d91244bf6c8b22503850e10909fa2071c44

diff --git a/src/componenttree.cpp b/src/componenttree.cpp
new file mode 100644
index 0000000..8390ed2
--- /dev/null
+++ b/src/componenttree.cpp
@@ -0,0 +1,69 @@
+/***************************************************************************
+ *   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(){
+}