Merge branch 'rework-directory-structure'

1 files changed, 806 insertions, 0 deletions

diff --git a/src/tree.c b/src/tree.c
new file mode 100644
index 0000000..93690e2
--- /dev/null
+++ b/src/tree.c
@@ -0,0 +1,806 @@
+// Binary Search Tree
+#include <limits.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#include "util.h"
+
+/* --8<-- tree_type */
+typedef int T;
+
+struct tree_node {
+        struct tree_node *left, *right;
+        T                 key;
+        int               count; /* collision counter */
+                                 /* ggf. weitere Felder... */
+};
+/* -->8-- */
+
+/* --8<-- tree_isBst */
+static bool
+tree_isBstUntil(struct tree_node *tree, T min, T max)
+{
+        if ( tree == NULL )
+                return true;
+
+        if ( tree->key < min || tree->key > max )
+                return false;
+
+        return tree_isBstUntil(tree->left, min, tree->key - 1) &&
+               tree_isBstUntil(tree->right, tree->key + 1, max);
+}
+
+bool
+tree_isBst(struct tree_node *tree)
+{
+        return tree_isBstUntil(tree, INT_MIN, INT_MAX);
+}
+/* -->8-- */
+
+/* --8<-- tree_insert */
+struct tree_node *
+tree_insert(struct tree_node *tree, T key)
+{
+        if ( tree == NULL ) {
+                tree = malloc(sizeof *tree);
+                if ( tree ) {
+                        tree->key   = key;
+                        tree->count = 1;
+                        tree->left  = NULL;
+                        tree->right = NULL;
+                }
+                else
+                        ERROR("out of memory");
+        }
+        else if ( key < tree->key )
+                tree->left = tree_insert(tree->left, key);
+        else if ( key > tree->key )
+                tree->right = tree_insert(tree->right, key);
+        else               /* key == tree->key */
+                tree->count++; /* handle collision */
+
+        return tree;
+}
+/* -->8-- */
+
+/* --8<-- tree_insert_it */
+struct tree_node *
+tree_insert_it(struct tree_node *tree, T key)
+{
+        struct tree_node *parent = NULL;
+
+        for ( struct tree_node *curr = tree; curr; ) {
+                parent = curr;
+
+                if ( key < curr->key ) {
+                        curr = curr->left;
+                }
+                else if ( key > curr->key ) {
+                        curr = curr->right;
+                }
+                else { /* key == current->key */
+                        curr->count++;
+                        return tree;
+                }
+        }
+
+        struct tree_node *new_node;
+
+        new_node = malloc(sizeof *new_node);
+        if ( new_node ) {
+                new_node->key   = key;
+                new_node->count = 1;
+                new_node->left  = NULL;
+                new_node->right = NULL;
+
+                if ( parent == NULL ) {
+                        tree = new_node;
+                }
+                else if ( key < parent->key ) {
+                        parent->left = new_node;
+                }
+                else {
+                        parent->right = new_node;
+                }
+        }
+        else {
+                ERROR("out of memory");
+        }
+
+        return tree;
+}
+/* -->8-- */
+
+/* --8<-- tree_detach_min */
+static struct tree_node *
+tree_detach_min(struct tree_node **ptree)
+{
+        struct tree_node *tree = *ptree;
+
+        if ( tree == NULL )
+                return NULL;
+        else if ( tree->left )
+                return tree_detach_min(&tree->left);
+        else {
+                *ptree = tree->right;
+                return tree;
+        }
+}
+/* -->8-- */
+
+/* --8<-- tree_remove */
+struct tree_node *
+tree_remove(struct tree_node *tree, T key)
+{
+        if ( tree == NULL )
+                return NULL;
+
+        if ( key < tree->key )
+                tree->left = tree_remove(tree->left, key);
+        else if ( key > tree->key )
+                tree->right = tree_remove(tree->right, key);
+        else {                          /* key == tree->key */
+                if ( --tree->count == 0 ) { /* Handle Collision */
+                        struct tree_node *temp = tree;
+
+                        if ( tree->left == NULL ) {
+                                tree = tree->right;
+                        }
+                        else if ( tree->right == NULL ) {
+                                tree = tree->left;
+                        }
+                        else {
+                                struct tree_node *min = tree_detach_min(&tree->right);
+
+                                min->left  = tree->left;
+                                min->right = tree->right;
+
+                                tree = min;
+                        }
+
+                        free(temp);
+                }
+        }
+        return tree;
+}
+/* -->8-- */
+
+/* --8<-- tree_clear */
+void
+tree_clear(struct tree_node *tree)
+{
+        if ( tree ) {
+                tree_clear(tree->left);
+                tree_clear(tree->right);
+                free(tree);
+        }
+}
+/* -->8-- */
+
+/* --8<-- tree_lookup */
+struct tree_node *
+tree_lookup(struct tree_node *tree, T key)
+{
+        while ( tree )
+                if ( key < tree->key )
+                        tree = tree->left;
+                else if ( key > tree->key )
+                        tree = tree->right;
+                else /* key == tree->key */
+                        break;
+
+        return tree;
+}
+/* -->8-- */
+
+/* --8<-- tree_minimum */
+struct tree_node *
+tree_minimum(struct tree_node *tree)
+{
+        if ( tree )
+                while ( tree->left )
+                        tree = tree->left;
+
+        return tree;
+}
+/* -->8-- */
+
+/* --8<-- tree_maximum */
+struct tree_node *
+tree_maximum(struct tree_node *tree)
+{
+        if ( tree )
+                while ( tree->right )
+                        tree = tree->right;
+
+        return tree;
+}
+/* -->8-- */
+
+/* --8<-- tree_height */
+size_t
+tree_height(struct tree_node *tree)
+{
+        if ( tree ) {
+                size_t hl = tree_height(tree->left);
+                size_t hr = tree_height(tree->right);
+
+                return ((hl > hr) ? hl : hr) + 1;
+        }
+
+        return 0;
+}
+/* -->8-- */
+
+/* --8<-- tree_count */
+size_t
+tree_count(struct tree_node *tree)
+{
+        if ( tree )
+                return tree_count(tree->left) + tree_count(tree->right) + 1;
+
+        return 0;
+}
+/* -->8-- */
+
+/* --8<-- tree_copy */
+struct tree_node *
+tree_copy(struct tree_node *tree)
+{
+        if ( tree ) {
+                struct tree_node *new_node;
+
+                new_node = malloc(sizeof *new_node);
+                if ( new_node ) {
+                        new_node->key   = tree->key;
+                        new_node->count = tree->count;
+                        new_node->left  = tree_copy(tree->left);
+                        new_node->right = tree_copy(tree->right);
+                }
+                else {
+                        ERROR("out of memory");
+                }
+
+                return new_node;
+        }
+        return NULL;
+}
+/* -->8-- */
+
+/* --8<-- tree_isleaf */
+bool
+tree_isleaf(struct tree_node *tree)
+{
+        return tree->left == NULL && tree->right == NULL;
+}
+/* -->8-- */
+
+/* --8<-- tree_apply_preorder */
+void
+tree_apply_preorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
+{
+        if ( tree ) {
+                visit(tree->key, cl);
+                tree_apply_preorder(tree->left, visit, cl);
+                tree_apply_preorder(tree->right, visit, cl);
+        }
+}
+/* -->8-- */
+
+/* --8<-- tree_apply_inorder */
+void
+tree_apply_inorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
+{
+        if ( tree ) {
+                tree_apply_inorder(tree->left, visit, cl);
+                visit(tree->key, cl);
+                tree_apply_inorder(tree->right, visit, cl);
+        }
+}
+/* -->8-- */
+
+/* --8<-- tree_apply_postorder */
+void
+tree_apply_postorder(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
+{
+        if ( tree ) {
+                tree_apply_postorder(tree->left, visit, cl);
+                tree_apply_postorder(tree->right, visit, cl);
+                visit(tree->key, cl);
+        }
+}
+/* -->8-- */
+
+/* ===== */
+
+/* --8<-- tree_stack_type */
+struct stack_item {
+        struct stack_item *next;
+        struct tree_node * data;
+};
+
+struct stack {
+        struct stack_item *head;
+};
+/* -->8-- */
+
+/* --8<-- tree_stack_init */
+static void
+stack_init(struct stack *stack)
+{
+        stack->head = NULL;
+}
+/* -->8-- */
+
+/* --8<-- tree_stack_push */
+static void
+stack_push(struct stack *stack, struct tree_node *data)
+{
+        struct stack_item *new_item;
+
+        if ( (new_item = malloc(sizeof *new_item)) ) {
+                new_item->data = data;
+                new_item->next = stack->head;
+                stack->head    = new_item;
+        }
+        else
+                ERROR("out of memory");
+}
+/* -->8-- */
+
+/* --8<-- tree_stack_pop */
+static bool
+stack_pop(struct stack *stack, struct tree_node **data)
+{
+        if ( stack->head ) {
+                struct stack_item *next;
+
+                next  = stack->head->next;
+                *data = stack->head->data;
+
+                free(stack->head);
+                stack->head = next;
+
+                return true;
+        }
+        else
+                return false;
+}
+/* -->8-- */
+
+/* --8<-- tree_stack_peek */
+static struct tree_node *
+stack_peek(struct stack *stack)
+{
+        return (stack->head) ? stack->head->data : NULL;
+}
+/* -->8-- */
+
+/* --8<-- tree_stack_empty */
+static bool
+stack_empty(struct stack *stack)
+{
+        return stack->head == NULL;
+}
+/* -->8-- */
+
+/* --8<-- tree_stack_free */
+void
+stack_free(struct stack *stack)
+{
+        struct stack_item *item, *next;
+
+        for ( item = stack->head; item; item = next ) {
+                next = item->next;
+                free(item);
+        }
+}
+/* -->8-- */
+
+/* ===== */
+
+/* --8<-- tree_queue_type */
+struct queue_item {
+        struct queue_item *next;
+        struct tree_node * data;
+};
+
+struct queue {
+        struct queue_item *head, *tail;
+};
+/* -->8-- */
+
+/* --8<-- tree_queue_init */
+void
+queue_init(struct queue *queue)
+{
+        queue->head = NULL;
+}
+/* -->8-- */
+
+/* --8<-- tree_queue_put */
+void
+queue_put(struct queue *queue, struct tree_node *data)
+{
+        struct queue_item *new_item;
+
+        if ( (new_item = malloc(sizeof *new_item)) ) {
+                struct queue_item *tail;
+
+                tail           = queue->tail;
+                new_item->data = data;
+                new_item->next = NULL;
+                queue->tail    = new_item;
+
+                if ( queue->head == NULL )
+                        queue->head = queue->tail;
+                else
+                        tail->next = queue->tail;
+        }
+        else
+                ERROR("out of memory");
+}
+/* -->8-- */
+
+/* --8<-- tree_queue_get */
+bool
+queue_get(struct queue *queue, struct tree_node **data)
+{
+        if ( queue->head ) {
+                struct queue_item *next;
+
+                next  = queue->head->next;
+                *data = queue->head->data;
+
+                free(queue->head);
+                queue->head = next;
+
+                return true;
+        }
+        else
+                return false;
+}
+/* -->8-- */
+
+/* --8<-- tree_queue_empty */
+bool
+queue_empty(struct queue *queue)
+{
+        return queue->head == NULL;
+}
+/* -->8-- */
+
+/* --8<-- tree_queue_free */
+void
+queue_free(struct queue *queue)
+{
+        struct queue_item *item, *next;
+
+        for ( item = queue->head; item; item = next ) {
+                next = item->next;
+                free(item);
+        }
+}
+/* -->8-- */
+
+/* ===== */
+
+/* --8<-- tree_apply_preorder_it */
+void
+tree_apply_preorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
+{
+        if ( tree ) {
+                struct stack stack;
+
+                stack_init(&stack);
+
+                stack_push(&stack, tree);
+
+                while ( stack_pop(&stack, &tree) ) {
+                        visit(tree->key, cl);
+
+                        if ( tree->right )
+                                stack_push(&stack, tree->right);
+                        if ( tree->left )
+                                stack_push(&stack, tree->left);
+                }
+
+                stack_free(&stack);
+        }
+}
+/* -->8-- */
+
+/* --8<-- tree_apply_inorder_it */
+void
+tree_apply_inorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
+{
+        if ( tree ) {
+                struct stack stack;
+
+                stack_init(&stack);
+
+                while ( !stack_empty(&stack) || tree ) {
+                        if ( tree ) {
+                                stack_push(&stack, tree);
+                                tree = tree->left;
+                        }
+                        else {
+                                stack_pop(&stack, &tree);
+                                visit(tree->key, cl);
+                                tree = tree->right;
+                        }
+                }
+
+                stack_free(&stack);
+        }
+}
+/* -->8-- */
+
+// Hier eine Version für PostOrder-Iterativ:
+// Quelle: https://stackoverflow.com/a/16092333
+
+/* --8<-- tree_apply_postorder_it */
+void
+tree_apply_postorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
+{
+        if ( tree ) {
+                struct stack stack;
+
+                stack_init(&stack);
+                stack_push(&stack, tree);
+
+                while ( !stack_empty(&stack) ) {
+                        struct tree_node *next = stack_peek(&stack);
+
+                        bool finishedSubtrees = (next->left == tree || next->right == tree);
+
+                        if ( finishedSubtrees || tree_isleaf(next) ) {
+                                stack_pop(&stack, &next);
+
+                                visit(next->key, cl);
+
+                                tree = next;
+                        }
+                        else {
+                                if ( next->right ) {
+                                        stack_push(&stack, next->right);
+                                }
+                                if ( next->left ) {
+                                        stack_push(&stack, next->left);
+                                }
+                        }
+                }
+                stack_free(&stack);
+        }
+}
+/* -->8-- */
+
+/* --8<-- tree_apply_levelorder_it */
+void
+tree_apply_levelorder_it(struct tree_node *tree, void (*visit)(T key, void *cl), void *cl)
+{
+        if ( tree ) {
+                struct queue queue;
+
+                queue_init(&queue);
+
+                queue_put(&queue, tree);
+
+                while ( queue_get(&queue, &tree) ) {
+                        visit(tree->key, cl);
+
+                        if ( tree->left )
+                                queue_put(&queue, tree->left);
+                        if ( tree->right )
+                                queue_put(&queue, tree->right);
+                }
+
+                queue_free(&queue);
+        }
+}
+/* -->8-- */
+
+/* ======================== */
+
+/* --8<-- tree_iterator_type */
+struct tree_iterator {
+        struct stack stack;
+};
+/* -->8-- */
+
+/* --8<-- tree_iterator_push_leftmost */
+static void
+tree_iterator_push_leftmost(struct stack *stack, struct tree_node *node)
+{
+        for ( ; node; node = node->left ) {
+                stack_push(stack, node);
+        }
+}
+/* -->8-- */
+
+/* --8<-- tree_iterator_next */
+struct tree_node *
+tree_iterator_next(struct tree_iterator *it)
+{
+        struct tree_node *node = NULL;
+
+        if ( stack_pop(&it->stack, &node) ) {
+                tree_iterator_push_leftmost(&it->stack, node->right);
+        }
+
+        return node;
+}
+/* -->8-- */
+
+/* --8<-- tree_iterator_first */
+struct tree_node *
+tree_iterator_first(struct tree_iterator *it, struct tree_node *tree)
+{
+        stack_init(&it->stack);
+
+        tree_iterator_push_leftmost(&it->stack, tree);
+
+        return tree_iterator_next(it);
+}
+/* -->8-- */
+
+/* --8<-- tree_iterator_free */
+void
+tree_iterator_free(struct tree_iterator *it)
+{
+        stack_free(&it->stack);
+}
+/* -->8-- */
+
+/* --8<-- tree_preorder_iterator_next */
+struct tree_node *
+tree_preorder_iterator_next(struct tree_iterator *it)
+{
+        struct tree_node *node = NULL;
+
+        if ( stack_pop(&it->stack, &node) ) {
+                if ( node->right ) {
+                        stack_push(&it->stack, node->right);
+                }
+                if ( node->left ) {
+                        stack_push(&it->stack, node->left);
+                }
+        }
+
+        return node;
+}
+/* -->8-- */
+
+/* --8<-- tree_preorder_iterator_first */
+struct tree_node *
+tree_preorder_iterator_first(struct tree_iterator *it, struct tree_node *tree)
+{
+        stack_init(&it->stack);
+
+        if ( tree ) {
+                stack_push(&it->stack, tree);
+
+                return tree_preorder_iterator_next(it);
+        }
+        else {
+                return NULL;
+        }
+}
+/* -->8-- */
+
+/* ===== */
+
+void
+print(T data, void *cl)
+{
+        (void) cl;
+        printf("%d\n", data);
+}
+
+#include "treeutil.h"
+
+int
+main_(void)
+{
+        // Teste den Fall von mycodeschool
+
+        struct tree_node *tree = NULL;
+
+        tree = tree_insert(tree, 12);
+        tree = tree_insert(tree, 5);
+        tree = tree_insert(tree, 15);
+        tree = tree_insert(tree, 3);
+        tree = tree_insert(tree, 7);
+        tree = tree_insert(tree, 13);
+        tree = tree_insert(tree, 17);
+        tree = tree_insert(tree, 1);
+        tree = tree_insert(tree, 9);
+        tree = tree_insert(tree, 14);
+        tree = tree_insert(tree, 20);
+        tree = tree_insert(tree, 8);
+        tree = tree_insert(tree, 11);
+        tree = tree_insert(tree, 18);
+
+        tree = tree_remove(tree, 15);
+
+        if ( !tree_isBst(tree) ) {
+                fprintf(stderr, "Tree ist kein BST!!\n");
+                return EXIT_FAILURE;
+        }
+
+        show_tree(tree, 0, 0);
+
+        tree_clear(tree);
+
+        return EXIT_SUCCESS;
+}
+
+int
+main__(void)
+{
+        struct tree_node *tree = NULL;
+
+        tree = tree_insert(tree, 5);
+        tree = tree_insert(tree, 3);
+        tree = tree_insert(tree, 7);
+        tree = tree_insert(tree, 2);
+        tree = tree_insert(tree, 4);
+        tree = tree_insert(tree, 6);
+        tree = tree_insert(tree, 8);
+
+        tree = tree_remove(tree, 2);
+        tree = tree_remove(tree, 3);
+        tree = tree_remove(tree, 5);
+
+        if ( !tree_isBst(tree) ) {
+                fprintf(stderr, "Tree ist kein BST!!\n");
+                return EXIT_FAILURE;
+        }
+
+        show_tree(tree, 0, 0);
+
+        tree_clear(tree);
+
+        return EXIT_SUCCESS;
+}
+
+int
+main(void)
+{
+        struct tree_node *tree = NULL;
+
+        tree = tree_insert_it(tree, 10);
+        tree = tree_insert_it(tree, 5);
+        tree = tree_insert_it(tree, 20);
+        tree = tree_insert_it(tree, 1);
+        tree = tree_insert_it(tree, 7);
+        tree = tree_insert_it(tree, 15);
+        tree = tree_insert_it(tree, 18);
+
+        tree_apply_preorder(tree, print, NULL);
+        puts("postorder:");
+        tree_apply_postorder(tree, print, NULL);
+        puts("postorder_it:");
+        tree_apply_postorder_it(tree, print, NULL);
+        show_tree(tree, 0, 0);
+
+        puts("levelorder_it:");
+        tree_apply_levelorder_it(tree, print, NULL);
+
+        show_tree(tree, 0, 0);
+
+        struct tree_iterator it;
+        struct tree_node *   node = tree_preorder_iterator_first(&it, tree);
+        while ( node ) {
+                fprintf(stdout, "%d\n", node->key);
+
+                node = tree_preorder_iterator_next(&it);
+        }
+        tree_iterator_free(&it);
+
+        tree_clear(tree);
+
+        return EXIT_SUCCESS;
+}