#include "config.h"

#include <assert.h>
#include <errno.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "logerr.h"
#include "util.h"

#include "tree.h"



struct Tree {
	const void *const value;
	const size_t value_size;
	const struct Tree *left;
	const struct Tree *right;
	size_t height;
};



int
tree_new(const size_t value_size, const struct Tree **const out) {
	int rc = -1;

	const struct Tree *ret = NULL;

	ret = malloc(sizeof(*ret));
	if (ret == NULL) {
		logerr("malloc(): %s", strerror(errno));
		goto out;
	}

	memcpy((void *)ret, &(struct Tree) {
		.value      = NULL,
		.value_size = value_size,
		.left       = NULL,
		.right      = NULL,
		.height     = 0U,
	}, sizeof(*ret));
	*out = ret;
	rc = 0;
out:
	if (rc) {
		if (ret != NULL) {
			freeit((void *)&ret);
		}
	}
	return rc;
}

void
tree_free(const struct Tree **const t) {
	const struct Tree *const tree = *t;
	assert(tree != NULL);

	const struct Tree *left  = tree->left;
	const struct Tree *right = tree->right;

	if (left != NULL) {
		tree_free(&left);
	}

	if (right != NULL) {
		tree_free(&right);
	}

	freeit((void *)t);
}

static void
insert_node(
	const struct Tree *const t,
	const struct Tree *node,
	const void *const value
) {
	struct Tree *const t_mut = (struct Tree *const)t;
	const int cmp = memcmp(value, t->value, t->value_size);
	if (cmp == 0) {
		tree_free(&node);
	} else if (cmp > 0) {
		if (t->left == NULL) {
			t_mut->left = (void *)node;
		} else {
			insert_node(t->left, node, value);
		}
		struct Tree *const t_left_mut = (struct Tree *const)t->left;
		t_left_mut->height++;
	} else {
		if (t->right == NULL) {
			t_mut->right = node;
		} else {
			insert_node(t->right, node, value);
		}
		struct Tree *const t_right_mut = (struct Tree *const)t->right;
		t_right_mut->height++;
	}
}

int
tree_add(const struct Tree *const t, const void *const value) {
	int rc = -1;

	const struct Tree *new = NULL;
	struct Tree *const t_mut = (struct Tree *const)t;

	if (t->value == NULL) {
		memcpy((void *)t->value, value, t->value_size);
		t_mut->height++;
		goto out;
	}

	if (tree_new(t->value_size, &new)) {
		logerr("tree_new()");
		goto out;
	}

	insert_node(t, new, value);

	rc = 0;
out:
	if (rc) {
		if (new != NULL) {
			tree_free(&new);
		}
	}
	return rc;
}

static bool
remove_ref(
	const struct Tree *t,
	const void *const value,
	const struct Tree **const parent_ptr
) {
	if (t->value == NULL) {
		return false;
	}

	struct Tree *const t_mut = (struct Tree *const)t;

	const int cmp = memcmp(value, t->value, t->value_size);
	if (cmp == 0) {
		if ((t->left == NULL) && (t->right == NULL)) {
			if (parent_ptr != NULL) {
				*parent_ptr = NULL;
			}
		} else if (t->left != NULL) {
			if (parent_ptr != NULL) {
				*parent_ptr = t->left;
			}
		} else if (t->right != NULL) {
			if (parent_ptr != NULL) {
				*parent_ptr = t->right;
			}
		} else {
			// FIXME: pivot
			assert(false);
		}
		tree_free(&t);
		return true;
	} else if (cmp > 0) {
		if (t->left == NULL) {
			return false;
		}
		return remove_ref(t->left, value, &t_mut->left);
	} else {
		if (t->right == NULL) {
			return false;
		}
		return remove_ref(t->right, value, &t_mut->right);
	}
}

bool
tree_remove(const struct Tree *const t, const void *const value) {
	return remove_ref(t, value, NULL);
}

bool
tree_contains(const struct Tree *const t, const void *const value) {
	if (t->value == NULL) {
		return false;
	}

	const int cmp = memcmp(value, t->value, t->value_size);
	if (cmp == 0) {
		return true;
	} else if (cmp < 0) {
		if (t->left == NULL) {
			return false;
		}
		return tree_contains(t->left, value);
	} else {
		if (t->right == NULL) {
			return false;
		}
		return tree_contains(t->right, value);
	}
}