/**
 * Reading and writing Binary Search Tree from/to file
 * In addition, a method for deleting elements from the btree
 * Uses C99 dialect, so compile with -std=gnu99 or -std=c99
 * or via IDE-s Visual Studio 2013 (and higher) / DevC++5.7 (and higher)
 */
#include <stdio.h>  // fopen|fclose
#include <stdlib.h> // malloc|free
#include <string.h> // strcpy
#include <conio.h>  // getch



/**
 * Text based Binary Search Tree Node
 */
typedef struct _BTNode {
	struct _BTNode* left;
	struct _BTNode* right;
	char text[80];
} BTNode;



/**
 * Create a new node
 */
BTNode* BST_NewNode(const char* text)
{
	BTNode* node = malloc(sizeof(BTNode));
	node->left    = NULL;
	node->right   = NULL;
	strcpy(node->text, text);
	return node;
}



/** 
 * Destroy an entire tree
 */
void BST_Destroy(BTNode* root)
{
	if (root == NULL) return; // nothing to do here
	BST_Destroy(root->left);
	BST_Destroy(root->right);
	free(root);
}



/**
 * Find element from binary tree
 */
BTNode* BST_Search(BTNode* root, const char* str)
{
	if (!root)
		return NULL;
	
	int compare = strcmp(root->text, str);
	if (compare == 0) // perfect match
		return root;

	if (compare < 0)  // traverse left node (smaller)
		return BST_Search(root->left, str);
	return BST_Search(root->right, str);   // traverse right node (bigger)
}



/**
 * Insert element into binary tree
 */
BTNode* BST_Insert(BTNode** root, const char* str)
{
	if (*root == NULL)
		return *root = BST_NewNode(str);
	
	BTNode* r = *root;
	int compare = strcmp(r->text, str);
	if (compare == 0) // perfect match
		return r;  // this item already exists

	if (compare < 0)  // less than, so insert to left
		return BST_Insert(&r->left, str);
	return BST_Insert(&r->right, str);   // insert to right (bigger)
}


/**
 * Insert an existing node into the binary tree
 * @return TRUE if element was inserted, FALSE if it already exists in the tree
 */
int BST_InsertNode(BTNode** root, BTNode* node)
{
	if (*root = NULL) {
		*root = node;
		return 1; // success
	}

	BTNode* r = *root;
	int compare = strcmp(r->text, node->text);
	if (compare == 0) // perfect match, this item already exists!?
		return 0; // failed to insert

	if (compare < 0) // insert left
		return BST_InsertNode(&r->left, node);
	return BST_InsertNode(&r->right, node); // insert to right (bigger)
}


/**
 * Erase an element from the binary tree
 * @note The replace algorithm is a real pain
 * @return TRUE if the element was erased, FALSE otherwise
 */
int BST_Erase(BTNode** root, const char* str)
{
	if (*root == NULL)
		return 0; // FALSE

	BTNode* r = *root;
	int compare = strcmp(r->text, str);
	if (compare == 0) // found match?
	{
		// delete this node and replace the pointer
		if (r->left)
		{
			*root = r->left; // left && right
			if (r->right && !BST_InsertNode(root, r->right))
				free(r->right); // this is a really bad edge case
		}
		else if (r->right) // !left && right
			*root = r->right;
		else // !left && !right
			*root = NULL;

		free(r); // finally, delete this node
		return 1; // TRUE
	}

	if (compare < 0)  // less than, so search from left
		return BST_Erase(&r->left, str);
	return BST_Erase(&r->right, str);
}



void _BST_Print(BTNode* root, int level) //// @note Recursive helper function
{
	if (!root)
		return;

	// print as right - root - left to get descending order
	_BST_Print(root->right, level + 1);
	// -- simple version --
	// ("%*s", N, "") is a hack to print whitespace
	printf("%*s%s\n", level*2, "", root->text); 
	_BST_Print(root->left, level+1);
}
/**
 * Print all elements in a BST
 */
void BST_Print(BTNode* root)
{
	printf("====== TREE ======\n");
	if (root) _BST_Print(root, 0);
	else      printf("|-\n");
	printf("==================\n");
}



void _BST_Save(FILE* f, BTNode* node) //// @note Recursive helper function
{
	// write node data first, then left and right
	fwrite(node, sizeof(BTNode), 1, f);

	// -- debug --
	//printf("Save: %s\n", node->text);

	if (node->left)  _BST_Save(f, node->left);
	if (node->right) _BST_Save(f, node->right);
}
/**
 * Save entire Tree to file
 */
int BST_Save(const char* filename, BTNode* root)
{
	if (root == NULL)
		return 1; // nothing to save, success.

	FILE* f = fopen(filename, "wb");
	if (f == NULL)
	{
		fprintf(stderr, "File '%s' access denied.\n", filename);
		return 0; // failed
	}

	_BST_Save(f, root);
	fclose(f);
	return 1; // success
}



void _BST_Load(FILE* f, BTNode** node) //// @note Recursive helper function
{
	BTNode* n = *node = malloc(sizeof(BTNode));
	fread(n, sizeof(BTNode), 1, f); // read node, then left && right

	// -- debug --
	//printf("Read: %s\n", n->text);

	if (n->left)  _BST_Load(f, &n->left);
	if (n->right) _BST_Load(f, &n->right);
}
/**
 * Load entire Tree from file
 */
BTNode* BST_Load(const char* filename)
{
	FILE* f = fopen(filename, "rb");
	if (f == NULL)
		return NULL; // fail silently, since the file might not exist

	fseek(f, 0, SEEK_END);
	int filesize = ftell(f); // get filesize
	fseek(f, 0, SEEK_SET);

	BTNode* root = NULL;
	if (filesize) // do we actually have any data?
	{
		if ((filesize % sizeof(BTNode)) != 0) // ensure filesize makes sense
			fprintf(stderr, "BST_Load: Binary data in '%s' not in expected layout", filename);
		else 
			_BST_Load(f, &root);
	}
	fclose(f);
	return root;
}



void clear() // Clear the console screen
{
	#if _WIN32
		system("cls");
	#else
		system("clear");
	#endif
}



int main(int argc, char** argv)
{
	char input[80];
	BTNode* node;
	BTNode* root = BST_Load("sdpuu.bin"); // try to load something
	BST_Print(root);

	for (;;) // infinite loop
	{
		printf("key: ");
		if (*gets(input) == '\0')
			break; // no input, exit

		clear();
		if (node = BST_Search(root, input)) // try to find
		{
			printf("=> found key '%s'\n", node->text);
			printf("Do you want to delete this node? (y/n): ");
			if (getche() == 'y')
			{
				if (BST_Erase(&root, node->text)) printf("Deleted node");
				else                              printf("Error while deleting node");
			}
			printf("\n");
		}
		else // not found
		{
			node = BST_Insert(&root, input); // insert new item
			printf("=> inserted  '%s'\n", input);
		}
		BST_Print(root);

		// flush entire tree to file
		if (!BST_Save("sdpuu.bin", root))
			break; // failed
	}
	BST_Destroy(root); // cleanup
	return 0;
}