/* -*- 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)
{
	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());
	//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, nodeid_t insertBeforeId)
	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, insertBeforeId);

			//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, nodeid_t beforeId)
	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);
		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);
		//    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, 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()
{
	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(const std::string& xml)
{
	XmlParser p(this);
	p.parse(xml.data(), xml.size());
}