path: root/src/tree.c

/*
 * 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/>.
 */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include "tree.h"

#include <inttypes.h>

#include <glib.h>

#if MQ_TREE_DEBUG

static void
print_tree_recurse(MqTree *node, gsize indent)
{
	gsize i;

	for (; node; node = node->next) {
		for (i = 0; i < indent; ++i) {
			g_print("\t");
		}
		g_print("\t0x%" PRIxPTR "\n", (uintptr_t) node);

		if (node->first_child) {
			print_tree_recurse(node->first_child, indent + 1);
		}
	}
}

static void
print_tree(MqTree *node)
{
	node = node->root;

	g_print("New tree (size %d):\n", node->size);

	print_tree_recurse(node, 0);
}

static void
print_node(MqTree *node)
{
	g_print("\t0x%" PRIxPTR "\n", (uintptr_t) node);
}

static void
print_head(const gchar *head, MqTree *node)
{
	g_print("%s, starting at 0x%" PRIxPTR "\n", head, (uintptr_t) node);
}

#else  /* MQ_TREE_DEBUG */

#define print_tree(node)
#define print_node(node)
#define print_head(head, node)

#endif  /* MQ_TREE_DEBUG */

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 gboolean
update_position(MqTree *node, gpointer user_data)
{
	gint *step;

	step = (gint *) user_data;

	node->position += *step;

	return MQ_TREE_CONTINUE;
}

static void
update_positions(MqTree *node, gint step)
{
	print_head("Updating positions", node);

	mq_tree_foreach_from(node, update_position, &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;

	print_tree(node);

	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;

	print_tree(node);

	return node;
}

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

MqTree *
seek(MqTree *node, gint offset)
{
	/* 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 seek(node->first_child, offset);
}

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

	return seek(node, offset);
}

static gboolean
foreach_down(MqTree *node, gboolean (*cb)(MqTree *node, gpointer user_data),
	gpointer user_data)
{
	for (; node; node = node->next) {
		/* XXX: Warning: Does not skip root node */
		print_node(node);
		if (cb(node, user_data) == MQ_TREE_STOP) {
			return MQ_TREE_STOP;
		}

		if (node->first_child) {
			if (foreach_down(node->first_child, cb, user_data) ==
					MQ_TREE_STOP) {
				return MQ_TREE_STOP;
			}
		}
	}

	return MQ_TREE_CONTINUE;
}

void
mq_tree_foreach(MqTree *node, gboolean (*cb)(MqTree *node, gpointer user_data),
	gpointer user_data)
{
	print_head("Traversing full tree", node);

	foreach_down(node->root->first_child, cb, user_data);
}

static gboolean
foreach_up(MqTree *node, gboolean (*cb)(MqTree *node, gpointer user_data),
	gpointer user_data)
{
	if (node->next) {
		if (foreach_down(node->next, cb, user_data) == MQ_TREE_STOP) {
			return MQ_TREE_STOP;
		}
	}

	if (node->parent) {
		if (foreach_up(node->parent, cb, user_data) == MQ_TREE_STOP) {
			return MQ_TREE_STOP;
		}
	}

	return MQ_TREE_CONTINUE;
}

void
mq_tree_foreach_from(MqTree *node,
	gboolean (*cb)(MqTree *node, gpointer user_data), gpointer user_data)
{
	print_head("Traversing tree from position", node);

	if (foreach_down(node, cb, user_data) == MQ_TREE_CONTINUE) {
		foreach_up(node, cb, user_data);
	}
}