/*
 * Tree data structure
 *
 * Copyright (C) 2017  Patrick McDermott
 *
 * This file is part of Marquee.
 *
 * Marquee 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 3 of the License, or
 * (at your option) any later version.
 *
 * Marquee 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 Marquee.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "tree.h"

#include <glib.h>

MqTree *
mq_tree_insert_root_allocated(MqTree *node, gpointer data)
{
	node->root = node;
	node->size = 1;
	node->data = data;

	return node;
}

static void
update_sizes(MqTree *node, gint step)
{
	if (node) {
		node->size += step;
		update_sizes(node->parent, step);
	}
}

static void
update_positions(MqTree *node, gint step)
{
	for (; node; node = node->next) {
		node->position += step;
		if (node->first_child) {
			update_positions(node->first_child, step);
		}
		if (node->parent && node->parent->next) {
			update_positions(node->parent->next, step);
		}
	}
}

MqTree *
mq_tree_insert_child_allocated(MqTree *node, MqTree *parent, gpointer data)
{
	/* Copy ancestor pointers. */
	node->root   = parent->root;
	node->parent = parent;

	if (parent->last_child) {
		/* Parent has children, so get position from sibling and append
		 * to list of children. */
		node->position = parent->last_child->position;
		node->prev = parent->last_child;
		parent->last_child->next = node;
	} else {
		/* Parent has no children, so get position from parent and add
		 * first child to parent. */
		node->position = parent->position;
		parent->first_child = node;
	}
	parent->last_child = node;
	update_positions(node, 1);

	node->size = 0;
	update_sizes(node, 1);

	node->data = data;

	return node;
}

MqTree *
mq_tree_insert_sibling_allocated(MqTree *node, MqTree *sibling, gpointer data)
{
	/* Copy ancestor pointers. */
	node->root   = sibling->root;
	node->parent = sibling->parent;

	/* Link to next sibling, if any. */
	if (sibling->next) {
		node->next = sibling->next;
		sibling->next->prev = node;
	}

	/* Link to previous sibling. */
	node->prev = sibling;
	sibling->next = node;

	node->size = 0;
	update_sizes(node, 1);

	node->position = sibling->position;
	update_positions(node, 1);

	node->data = data;

	return node;
}

void
mq_tree_remove(MqTree *node)
{
	/* TODO */
	node = node;
}

MqTree *
mq_tree_seek(MqTree *node, gint offset)
{
	/* XXX: Only forward seeking from a tree's root is supported. */
	g_assert(node && node->position == 0);
	g_assert(offset > 0);

	/* Skip forward to the containing subtree. */
	while (node && node->position + node->size <= offset) {
		node = node->next;
	}

	/* Check whether we've gone past the end of the tree. */
	if (!node) {
		return NULL;
	}

	/* Check whether the sibling we've reached is the node we want. */
	if (node->position == offset) {
		return node;
	}

	/* Recurse down the subtree. */
	return mq_tree_seek(node->first_child, offset);
}

static gboolean
foreach(MqTree *node, gboolean (*cb)(MqTree *node, va_list ap), va_list ap)
{
	va_list  aq;
	gboolean ret;

	ret = MQ_TREE_CONTINUE;
	for (; node; node = node->next) {
		/* XXX: Warning: Does not skip root node */
		va_copy(ap, aq);
		ret = cb(node, aq);
		va_end(aq);
		if (ret == MQ_TREE_STOP) {
			break;
		}

		if (node->first_child) {
			va_copy(ap, aq);
			ret = foreach(node->first_child, cb, aq);
			va_end(aq);
			if (ret == MQ_TREE_STOP) {
				break;
			}
		}

		if (node->parent && node->parent->next) {
			va_copy(ap, aq);
			ret = foreach(node->parent->next, cb, aq);
			va_end(aq);
			if (ret == MQ_TREE_STOP) {
				break;
			}
		}
	}

	return ret;
}

void
mq_tree_foreach(MqTree *node, gboolean (*cb)(MqTree *node, va_list ap), ...)
{
	va_list ap;

	va_start(ap, cb);
	foreach(node->root->first_child, cb, ap);
	va_end(ap);
}

static gboolean
foreach_child(MqTree *node, gboolean (*cb)(MqTree *node, va_list ap),
	va_list ap)
{
	va_list  aq;
	gboolean ret;

	ret = MQ_TREE_CONTINUE;
	for (node = node->first_child; node; node = node->next) {
		va_copy(ap, aq);
		ret = cb(node, aq);
		va_end(aq);
		if (ret == MQ_TREE_STOP) {
			break;
		}
	}

	return ret;
}

void
mq_tree_foreach_child(MqTree *node, gboolean (*cb)(MqTree *node, va_list ap),
	...)
{
	va_list ap;

	va_start(ap, cb);
	foreach_child(node->root->first_child, cb, ap);
	va_end(ap);
}