#include <stdio.h>
#include <time.h>
#include <stdbool.h>

#define t 2
#define NUM_OF_KEYS 1000
#define RAND_NUMBER_MAX 1000

typedef struct node
{
	int n;				// number of nodes in leaf
	int key[2 * t - 1];		// array of keys

	bool leaf;			// is leaf

	struct node* c[2 * t];		// if not leaf the pointers to childs

} node;

typedef struct tree {
	node* root;
} tree;

node *b_tree_new_node()
{
	node *n = (node*)malloc(sizeof(node));

	for (int i = 0; i < 2 * t; i++)
	{
		n->c[i] = NULL;
	}

	for (int i = 0; i < 2 * t - 1; i++)
	{
		n->key[i] = NULL;
	}

	return n;

}

void b_tree_split_child(node* x, int i)
{
	node* z = b_tree_new_node();

	node* y = x->c[i];

	z->leaf = y->leaf;
	z->n = t - 1;

	for (int j = 0; j < t - 1; j++)
	{
		z->key[j] = y->key[j + t];
	}

	if (y->leaf == false)
	{
		for (int j = 0; j < t; j++)
		{
			z->c[j] = y->c[j + t];
		}
	}

	y->n = t;

	for (int j = x->n; j > i; j--)
	{
		x->c[j + 1] = x->c[j];
	}
	x->c[i + 1] = z;

	for (int j = x->n; j > i; j--)
	{
		x->key[j] = x->key[j - 1];
	}

	x->key[i] = y->key[t - 1];
	x->n = x->n + 1;

	// DISK WRITE Y
	// DISK WRITE Z
	// DISK WRITE X
}

void b_tree_insert_nonfull(node* x, int k)
{

	int i = x->n;

	if (x->leaf == true)
	{
		while (i > 0 && k < x->key[i - 1])
		{
			x->key[i] = x->key[i - 1];
			i = i - 1;
		}

		x->key[i] = k;
		x->n = x->n + 1;
		// DISK WRITE X
	}
	else
	{


		while (i > 0 && k < x->key[i - 1])
		{
			i = i - 1;
		}

		// DISK READ X->C[I]

		// if chosen child is full
		if (x->c[i]->n == 2 * t - 1)
		{
			b_tree_split_child(x, i);

			if (k > x->key[i])
			{
				i = i + 1;
			}
		}
		b_tree_insert_nonfull(x->c[i], k);
	}
}

void b_tree_insert(tree *T, int k)
{
	// temp pointer to root
	node* r = T->root;

	// if node is full
	if (r->n == (2 * t - 1))
	{
		// create new node
		node* s = b_tree_new_node();
		// new node is now the root
		T->root = s;
		// new node won't be leaf
		s->leaf = false;
		// new node is empty
		s->n = 0;
		// new node points to previous root
		s->c[0] = r;

		b_tree_split_child(s, 0);
		b_tree_insert_nonfull(s, k);
	}

	// if node is not full
	else
	{
		b_tree_insert_nonfull(r, k);
	}
}

bool b_tree_search(node* x, int k)
{
	int i = 0;

	while (i < x->n && k > x->key[i])
	{
		i = i + 1;
	}
	if (i <= x->n && k == x->key[i])
	{
		return true;
	}
	else if (x->leaf)
	{
		return NULL;
	}
	else
	{
		return b_tree_search(x->c[i], k);
	}
}

void init_random_generator()
{
	srand(time(NULL));
}

int random_number()
{
	rand();
	return rand() % RAND_NUMBER_MAX + 1;
}

void init_array(int **n, int numToAdd)
{
	*n = (int*)malloc(sizeof(int));

	if (*n == NULL)
	{
		printf("Error in malloc!");
		return;
	}

	(*n)[0] = numToAdd;
}

void add_to_array(int **n, int numToAdd)
{
	static int sizeCount = 0;
	sizeCount++;
	int tempcount = sizeCount;

	int *temp;

	temp = (int*)realloc(*n, (sizeCount + 1) * sizeof(int));

	if (temp == NULL)
	{
		printf("Error in realloc!");
		return;
	}

	*n = temp;

	(*n)[sizeCount] = numToAdd;

}

void print_test_array(int *test_array) {
	for (int i = 0; i < NUM_OF_KEYS; i++)
	{
		printf("[%d]", test_array[i]);
	}
	printf("\n");
}

bool check_for_duplicates(int **test_array, int a_number)
{
	for (int i = 0; i < NUM_OF_KEYS; i++)
	{
		if ((*test_array)[i] == a_number)
		{
			return true;
		}
	}
	return false;
}

void load_array_data(int **test_array)
{
	for (int i = 0; i < NUM_OF_KEYS; i++)
	{
		if (*test_array == NULL)
		{
			init_array(test_array, random_number());
		}
		else
		{
			int a_number = random_number();

			while (check_for_duplicates(test_array, a_number) == true)
			{
				a_number = random_number();
			}

			add_to_array(test_array, a_number);
		}
	}

}

int main()
{
	init_random_generator();
	int *test_array = NULL;		// { 3, 7, 1, 2, 5, 6, 8, 9, 4, 10, 11 };
	printf(">loading test data\n");
	load_array_data(&test_array);
	//print_test_array(test_array);

	node *x = b_tree_new_node();
	x->leaf = true;
	x->n = 0;

	tree T;
	T.root = x;

	printf(">building tree\n");

	int known_random_number = random_number();

	// insert nodes
	for (int i = 0; i < NUM_OF_KEYS; i++) {
		int random = random_number();
		b_tree_insert(&T, test_array[i]);
	}

	int failed_tests = 0;

	printf(">searching all keys\n");

	for (int i = 0; i < NUM_OF_KEYS; i++)
	{
		if (b_tree_search(T.root, test_array[i]) == false)
		{
			printf("Element not found: %d\n", test_array[i]);
			failed_tests++;
		}
	}


	if (failed_tests == 0)
	{
		printf(">all tests passed successfully\n");
	}

	getchar();

	return 0;
}