Rename task to node everywhere.

1 files changed, 475 insertions, 0 deletions

diff --git a/src/nodetree.cc b/src/nodetree.cc
new file mode 100644
index 0000000..1c3992e
--- /dev/null
+++ b/src/nodetree.cc
@@ -0,0 +1,475 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set et sw=2 ts=2: */
+/***************************************************************************
+ *            nodetree.cc
+ *
+ *  Tue Mar 27 11:07:48 CEST 2012
+ *  Copyright 2012 Jonas Suhr Christensen
+ *  jsc@umbraculum.org
+ ****************************************************************************/
+
+/*
+ *  This file is part of Munia.
+ *
+ *  Munia 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.
+ *
+ *  Munia 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 Munia; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA.
+ */
+#include "nodetree.h"
+
+#include <stdio.h>
+
+#include "xmlparser.h"
+
+#include "hugin.hpp"
+
+#include "xml_encode_decode.h"
+
+#define ROOT_PARENT_ID -1
+
+static inline std::string id2str(nodeid_t id)
+{
+	char buf[32];
+	sprintf(buf, "%u", id);
+	return buf;
+}
+
+std::string Node::toXML(std::string prefix)
+{
+	std::string xml;
+
+	xml += prefix + "<node id=\""+id2str(id)+"\">\n";
+	xml += prefix + "  <attributes>\n";
+	std::map<std::string, std::string>::iterator ai = data.attributes.begin();
+	while(ai != data.attributes.end())
+	{
+		xml += prefix + "    <attribute name=\"" + xml_encode(ai->first) + "\">"
+			+ xml_encode(ai->second) + "</attribute>\n";
+		ai++;
+	}
+	xml += prefix + "  </attributes>\n";
+	xml += prefix + "  <children>\n";
+	NodeList::iterator ni = children.begin();
+	while(ni != children.end())
+	{
+		xml += (*ni)->toXML(prefix + "    ");
+		ni++;
+	}
+	xml += prefix + "  </children>\n";
+	xml += prefix + "</node>\n";
+
+	return xml;
+}
+
+static void concatNodeIdLists(NodeIdList& pre, NodeIdList& post)
+{
+	pre.insert(pre.end(), post.begin(), post.end());
+	//for(NodeIdList::iterator it = post.begin();
+	//it != post.end(); it++)
+	//{
+	//  pre.push_back(
+	//}
+}
+
+NodeTree::NodeTree()
+{
+	root = NULL;
+	nextid = 10;
+}
+
+NodeTree::~NodeTree()
+{
+	// cleanup tree
+}
+
+nodeid_t NodeTree::createId()
+{
+	nodeid_t nodeid;
+
+	do
+	{
+		nodeid = nextid++;
+	}
+	while(id2node.find(nodeid) != id2node.end());
+
+	return nodeid;
+}
+
+static nodeid_t rootid = -1;
+
+NodeIdList NodeTree::insertAsChild(nodeid_t parentid, nodeid_t id, node_t data)
+	throw (std::exception)
+{
+	NodeIdList affectedNodes;
+
+	// Initialize
+	if(!root)
+	{
+		rootid = id;
+		Node* node = createNode(id);
+		root = node;
+		node->data = data;
+		affectedNodes.push_back(id);
+	}
+	else
+	{
+		try
+		{
+			Node* parent = id2node.at(parentid);
+			Node* child = createNode(id);
+			//DEBUG(nodetree, "!!!!!!!id in insert: %d\n", data.id);
+			child->data = data;
+			insertChild(parent, child);
+
+			//affectedNodes.push_back(parentid);
+			affectedNodes.push_back(id);
+			NodeIdList ancestors = ancestorList(id);
+			concatNodeIdLists(affectedNodes, ancestors);
+		}
+		catch(std::exception& e)
+		{
+			throw e;
+		}
+	}
+
+	//DEBUG(nodetree, "Child %d added to %d, affecting %d nodes\n",
+	//      id, parentid, affectedNodes.size());
+	return affectedNodes;
+}
+
+NodeIdList NodeTree::remove(nodeid_t id)
+	throw (std::exception)
+{
+	NodeIdList affectedNodes;
+	affectedNodes.push_back(id);
+	NodeIdList ancestors = ancestorList(id);
+	concatNodeIdLists(affectedNodes, ancestors);
+
+	//DEBUG(nodetree, "Removing %d\n", id);
+	//DEBUG(nodetree, "!!!!!affected nodes %d\n", affectedNodes.size());
+
+	Node* node = id2node[id];
+
+	//DEBUG(nodetree, "node: %p, id %d, parent %p\n", node, node->data.id, node->parent);
+
+	//DEBUG(nodetree, "!!!!!size %d\n", node->parent->children.size());
+	node->parent->children.remove(node);
+	for(NodeList::iterator it = node->parent->children.begin();
+	    it != node->parent->children.end();
+	    it++)
+	{
+		//DEBUG(nodetree, "%p\n", *it);
+	}
+	//DEBUG(nodetree, "!!!!!size %d\n", node->parent->children.size());
+
+	NodeIdList idlist = bfs(id);
+	NodeIdList::reverse_iterator it = idlist.rbegin();
+	while(it != idlist.rend())
+	{
+		node_t node = data(*it);
+		//Node* n = id2node[node.id];
+		//delete(n);
+		it++;
+	}
+
+	return affectedNodes;
+}
+
+static bool findNode(Node *needle, Node *haystack)
+{
+	if(needle == haystack) return true;
+	NodeList::iterator i = haystack->children.begin();
+	while(i != haystack->children.end())
+	{
+		if(findNode(needle, *i))
+		{
+			return true;
+		}
+		i++;
+	}
+	return false;
+}
+
+NodeIdList NodeTree::move(nodeid_t id, nodeid_t toid)
+	throw (std::exception)
+{
+	NodeIdList affectedNodes;
+
+	try
+	{
+		Node* child = id2node.at(id);
+		Node* newparent = id2node.at(toid);
+
+		// Test if new parent is a child of the node itself...
+		if(findNode(newparent, child))
+		{
+			throw std::exception();
+		}
+
+		if(!child->parent)
+		{
+			throw std::exception();
+		}
+
+		child->parent->children.remove(child);
+		newparent->children.push_back(child);
+
+		child->parent = newparent;
+
+		affectedNodes.push_back(id);
+		//    affectedNodes.push_back(child->parent->id);
+		NodeIdList ancestors = ancestorList(id);
+		concatNodeIdLists(affectedNodes, ancestors);
+		affectedNodes.push_back(toid);
+		ancestors = ancestorList(toid);
+	}
+	catch(std::exception& e)
+	{
+		throw e;
+	}
+
+	return affectedNodes;
+}
+
+NodeIdList NodeTree::updateData(nodeid_t id, const std::string &name,
+                                const std::string &value)
+  throw (std::exception)
+{
+	NodeIdList affectedNodes;
+
+	try
+	{
+		Node* node = id2node.at(id);
+		node->data.attributes[name] = value;
+
+		affectedNodes.push_back(id);
+		NodeIdList ancestors = ancestorList(id);
+		concatNodeIdLists(affectedNodes, ancestors);
+	}
+	catch(std::exception& e)
+	{
+		throw e;
+	}
+
+	return affectedNodes;
+}
+
+node_t NodeTree::data(nodeid_t id)
+	throw (std::exception)
+{
+	node_t t;
+
+	try
+	{
+		Node* node = id2node.at(id);
+		node_t tmp = node->data;
+		t.id = node->id;
+		t.attributes = tmp.attributes;
+		//DEBUG(nodetree, "!!!!t.id and tmp.id in data: %d and %d\n", t.id, tmp.id);
+		if(node->parent)
+		{
+			t.parentid = node->parent->id;
+		}
+		else
+		{
+			if(t.id != rootid)
+			{
+				throw std::exception();
+			}
+			t.parentid = -1;
+		}
+	}
+	catch(std::exception& e)
+	{
+		throw e;
+	}
+
+	return t;
+}
+
+// bfs search from id in tree
+NodeIdList NodeTree::bfs(nodeid_t id)
+	throw (std::exception)
+{
+	NodeIdList lst;
+	lst.push_back(id);
+
+	std::list<Node*> queue;
+	Node* current = id2node.at(id);
+	while(true)
+	{
+		NodeList children = current->children;
+		for(NodeList::iterator it = children.begin(); it != children.end(); it++)
+		{
+			Node* child = *it;
+			queue.push_back(child);
+			lst.push_back(child->id);
+		}
+
+		if(!queue.empty())
+		{
+			current = queue.front();
+			queue.pop_front();
+		}
+		else
+		{
+			break;
+		}
+	}
+
+	return lst;
+}
+
+NodeIdList NodeTree::ancestorList(nodeid_t id)
+	throw (std::exception)
+{
+	NodeIdList ancestors;
+
+	try
+	{
+		Node* current = id2node.at(id);
+		while(current->parent)
+		{
+			ancestors.push_back(current->parent->id);
+			current = current->parent;
+		}
+	}
+	catch(std::exception& e)
+	{
+		throw e;
+	}
+
+	//DEBUG(nodetree, "Collected %d ancestors to %u\n", ancestors.size(), id);
+	//for(NodeIdList::iterator it = ancestors.begin();
+	//    it != ancestors.end(); it++)
+	//{
+	//	DEBUG(nodetree, "\tancestor %u\n", *it);
+	//}
+	return ancestors;
+}
+
+Node* NodeTree::createNode(nodeid_t id)
+{
+	Node* node = new Node();
+	node->parent = NULL;
+	node->id = id;
+	id2node[id] = node;
+	return node;
+}
+
+void NodeTree::insertChild(Node* parent, Node* child)
+{
+	if(parent)
+	{
+		parent->children.push_back(child);
+	}
+	else
+	{
+		rootid = child->id;
+		root = child;
+	}
+	child->parent = parent;
+}
+
+static void printNode(Node* node, std::string prefix)
+{
+	if(!node)
+	{
+	  return;
+	}
+	node_t t = node->data;
+	DEBUG(nodetree, "%s- %u - %s (%p)\n", prefix.c_str(), node->id,
+	      t.attributes["title"].c_str(), node);
+
+	NodeList::iterator it;
+	for(it = node->children.begin(); it != node->children.end(); it++)
+	{
+		Node* child = *it;
+		printNode(child, "  " + prefix);
+	}
+}
+
+void NodeTree::toStdOut()
+{
+	printNode(root, "");
+}
+
+std::string NodeTree::toXML()
+{
+	Node *root = id2node.at(rootid);
+
+	std::string xml;
+	xml += "<?xml version='1.0' encoding='UTF-8'?>\n";
+	xml += "<nodetree nextid=\""+id2str(nextid)+"\">\n";
+	xml += root->toXML("  ");
+	xml += "</nodetree>";
+
+	return xml;
+}
+
+void NodeTree::fromXML(std::string xml)
+{
+	XmlParser p(this);
+	p.parse(xml.c_str(), xml.size());
+}
+
+
+#ifdef TEST_NODETREE
+//Additional dependency files
+//deps: debug.cc log.cc
+//Required cflags (autoconf vars may be used)
+//cflags: -I..
+//Required link options (autoconf vars may be used)
+//libs:
+#include "test.h"
+#include <exception>
+
+#define ROOT_ID 0
+#define LOSTFOUND_ID 1
+#define FINISHED_ID 2
+#define BACKLOG_ID 3
+#define PROJECTS_ID 4
+#define FIRST_NODE_ID 10
+
+TEST_BEGIN;
+
+NodeTree tree;
+
+node_t t;
+t.attributes["title"] = "root";
+t.id = ROOT_ID;
+tree.insertAsChild(0, ROOT_ID, t);
+
+t.attributes["title"] = "Finished";
+t.id = FINISHED_ID;
+tree.insertAsChild(ROOT_ID, FINISHED_ID, t);
+
+t.attributes["title"] = "Backlog";
+t.id = BACKLOG_ID;
+tree.insertAsChild(ROOT_ID, BACKLOG_ID, t);
+
+t.attributes["title"] = "Lost+Found";
+t.id = LOSTFOUND_ID;
+tree.insertAsChild(ROOT_ID, LOSTFOUND_ID, t);
+
+t.attributes["title"] = "Projects";
+t.id = PROJECTS_ID;
+tree.insertAsChild(ROOT_ID, PROJECTS_ID, t);
+
+TEST_EQUAL_INT(5, tree.bfs(0).size(), "Testing BFS function");
+TEST_EQUAL_INT(PROJECTS_ID, tree.data(PROJECTS_ID).id, "Testing project id");
+TEST_EQUAL_INT(ROOT_ID, tree.data(ROOT_ID).id, "Testing root id");
+
+TEST_END;
+
+#endif/*TEST_NODETREE*/