diff options
Diffstat (limited to 'src/tree.c')
| -rw-r--r-- | src/tree.c | 226 |
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); +} |