summaryrefslogtreecommitdiffstats
path: root/src/tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/tree.c')
-rw-r--r--src/tree.c226
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);
+}