/**
 * Reading and writing Binary Search Tree from/to file
 * 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* node = *root;
	int compare = strcmp(node->text, str);
	if (compare == 0) // perfect match
		return node;  // this item already exists

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



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("spuu.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);
		}
		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("spuu.bin", root))
			break; // failed
	}
	BST_Destroy(root); // cleanup
	return 0;
}