path: root/src/nodetree.cc

/* -*- 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"
#include "exceptions.h"

#define ROOT_PARENT_ID -1

static inline std::string id2str(nodeid_t id)
{
	return std::to_string(id);
}

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())
	{
		if(ai->first != "dragged") // Do not persist 'dragged' attribute
		{
			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());
}

NodeTree::NodeTree()
{
}

NodeTree::~NodeTree()
{
}

nodeid_t NodeTree::createId()
{
	nodeid_t nodeid;

	do
	{
		nodeid = nextid++;
	}
	while(hasId(nodeid));

	return nodeid;
}

bool NodeTree::hasId(nodeid_t nodeid) const
{
	return id2node.find(nodeid) != id2node.end();
}

static nodeid_t rootid = -1;

NodeIdList NodeTree::insertAsChild(nodeid_t parentid, nodeid_t id,
                                   node_t data, nodeid_t insertBeforeId)
{
	NodeIdList affectedNodes;

	if(parentid == id)
	{
		throw Error::NewParentIsSelf(); // Node and new parent are the same node.
	}

	// Initialized?
	if(!root)
	{
		rootid = id;
		Node* node = createNode(id);
		root = node;
		node->data = data;
		affectedNodes.push_back(id);
	}
	else
	{
		if(!hasId(parentid))
		{
			throw Error::MissingParent();
		}

		Node* parent = id2node.at(parentid);
		Node* child = createNode(id);

		child->data = data;
		insertChild(parent, child, insertBeforeId);
		affectedNodes.push_back(id);

		NodeIdList ancestors = ancestorList(id);
		concatNodeIdLists(affectedNodes, ancestors);
	}

	return affectedNodes;
}

NodeIdList NodeTree::remove(nodeid_t id)
{
	if(!hasId(id))
	{
		throw Error::NoSuchId();
	}

	NodeIdList affectedNodes;
	affectedNodes.push_back(id);
	NodeIdList ancestors = ancestorList(id);
	concatNodeIdLists(affectedNodes, ancestors);

	Node* node = id2node.at(id);

	node->parent->children.remove(node);

	NodeIdList idlist = bfs(id);
	NodeIdList::reverse_iterator it = idlist.rbegin();
	while(it != idlist.rend())
	{
		node_t node = data(*it);
		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, nodeid_t beforeId)
{
	NodeIdList affectedNodes;

	if(id == toid)
	{
		throw Error::NewParentIsSelf(); // Node and new parent are the same node.
	}

	if(!hasId(id))
	{
		throw Error::NoSuchId();
	}

	Node* child = id2node.at(id);

	if(!hasId(toid))
	{
		throw Error::MissingParent();
	}

	Node* newparent = id2node.at(toid);

	// Test if new parent is a child of the node itself...
	if(findNode(newparent, child))
	{
		throw Error::NewParentIsChildOfSelf();
	}

	if(!child->parent)
	{
		throw Error::System("Node does not have a parent.");
	}

	child->parent->children.remove(child);
	bool inserted{false};
	for(auto it = newparent->children.begin();
	    it != newparent->children.end();
	    ++it)
	{
		if((*it)->id == beforeId)
		{
			newparent->children.insert(it, child);
			inserted = true;
		}
	}
	if(!inserted)
	{
		// beforeId was not found in parent - inserting last instead.
		newparent->children.push_back(child);
	}

	child->parent = newparent;

	affectedNodes.push_back(id);

	NodeIdList ancestors = ancestorList(id);
	concatNodeIdLists(affectedNodes, ancestors);
	affectedNodes.push_back(toid);
	ancestors = ancestorList(toid);

	return affectedNodes;
}

NodeIdList NodeTree::updateData(nodeid_t id, const std::string &name,
                                const std::string &value)
{
	if(!hasId(id))
	{
		throw Error::NoSuchId();
	}

	NodeIdList affectedNodes;

	Node* node = id2node.at(id);
	node->data.attributes[name] = value;

	affectedNodes.push_back(id);
	NodeIdList ancestors = ancestorList(id);
	concatNodeIdLists(affectedNodes, ancestors);

	return affectedNodes;
}

node_t NodeTree::data(nodeid_t id)
{
	if(!hasId(id))
	{
		throw Error::NoSuchId();
	}

	node_t t;

	Node* node = id2node.at(id);
	node_t tmp = node->data;
	t.id = node->id;
	t.attributes = tmp.attributes;

	if(node->parent)
	{
		t.parentid = node->parent->id;
	}
	else
	{
		if(t.id != rootid)
		{
			throw Error::System("Node has no parent, but node is not root.");
		}
		t.parentid = -1;
	}

	return t;
}

// bfs search from id in tree
NodeIdList NodeTree::bfs(nodeid_t id)
{
	if(!hasId(id))
	{
		throw Error::NoSuchId();
	}

	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)
{
	NodeIdList ancestors;

	if(!hasId(id))
	{
		throw Error::NoSuchId();
	}

	Node* current = id2node.at(id);
	auto origin = current;
	while(current->parent)
	{
		ancestors.push_back(current->parent->id);
		current = current->parent;
		if(current == origin)
		{
			throw Error::System("Cycle detected.");
		}
	}

	return ancestors;
}

Node* NodeTree::createNode(nodeid_t id)
{
	if(hasId(id))
	{
		throw Error::IdAlreadyExists();
	}

	Node* node = new Node();
	node->parent = NULL;
	node->id = id;
	id2node[id] = node;
	return node;
}

void NodeTree::insertChild(Node* parent, Node* child, nodeid_t insertBeforeId)
{
	if(parent)
	{
		bool inserted{false};
		for(auto it = parent->children.begin();
		    it != parent->children.end();
		    ++it)
		{
			if((*it)->id == insertBeforeId)
			{
				parent->children.insert(it, child);
				inserted = true;
			}
		}
		if(!inserted)
		{
			// beforeId was not found in parent - inserting last instead.
			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(), (int)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()
{
	std::string xml;
	xml += "<?xml version='1.0' encoding='UTF-8'?>\n";
	xml += "<nodetree nextid=\""+id2str(nextid)+"\">\n";
	if(root)
	{
		xml += root->toXML("  ");
	}
	xml += "</nodetree>";

	return xml;
}

void NodeTree::fromXML(const std::string& xml)
{
	XmlParser p(this);
	p.parse(xml.data(), xml.size());
}