// 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;
}