MqTree: New type

1 files changed, 226 insertions, 0 deletions

diff --git a/src/tree.c b/src/tree.c
new file mode 100644
index 0000000..618503d
--- /dev/null
+++ b/src/tree.c
@@ -0,0 +1,226 @@
+/*
+ * 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->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);
+}