/*
btree.c
Pedro Flynn - pflynn@microsoftsucks.org
*/

#include "btree.h"

struct btree* btree_create(void (*destroy)(void *data))
{
struct btree* new_btree;
	
new_btree = (struct btree*) malloc(sizeof(struct btree));
new_btree->b_size = 0;
new_btree->b_destroy = destroy;
new_btree->b_root = NULL;

return new_btree;
}

struct btree_node* btree_insert_node_left(struct btree* btree,struct btree_node* root,const void* data)
{
struct btree_node* new_node;
struct btree_node** pos;
	
if(!btree)
	return NULL;

if(!root)
{
	if(btree->b_size) /*nao inserir no nodo root se ele ja existir */
		return NULL;
	pos = &btree->b_root;
}else{
	if(root->bn_left) /* nao inserir no nodo esquerdo se ele ja existir */
		return NULL;
	pos = &root->bn_left;
}

new_node = (struct btree_node*) malloc(sizeof(struct btree_node));
new_node->bn_left = new_node->bn_right = NULL;
new_node->bn_data = (void*) data;

*pos = new_node;

btree->b_size++;
return new_node;
}


struct btree_node* btree_insert_node_right(struct btree* btree,struct btree_node* root,const void* data)
{
struct btree_node* new_node;
struct btree_node** pos;
	
if(!btree)
	return NULL;

if(!root)
{
	if(btree->b_size) /* na inserir no nodo root se ele ja existir */
		return NULL;
	pos = &btree->b_root;
}else{
	if(root->bn_right) /* nao inserir no nodo direito se ele ja existir */
		return NULL;
	pos = &root->bn_right;
}

new_node = (struct btree_node*) malloc(sizeof(struct btree_node));
new_node->bn_left = new_node->bn_right = NULL;
new_node->bn_data = (void*) data;

*pos = new_node;

btree->b_size++;
return new_node;
}

int btree_remove_node_left(struct btree* btree,struct btree_node* node)
{
struct btree_node **oldnode;

if(!btree)
	return -1;

if(!btree->b_size)
	return -1;

if(!node)
	oldnode = &btree->b_root;
else
  oldnode = &node->bn_left;

if(*oldnode){
btree_remove_node_left(btree,*oldnode);
btree_remove_node_right(btree,*oldnode);

if(btree->b_destroy)
	btree->b_destroy((*oldnode)->bn_data);

free(*oldnode);
*oldnode = NULL;	
btree->b_size--;	
	}

return 0;
}

int btree_remove_node_right(struct btree* btree,struct btree_node* node)
{
struct btree_node **oldnode;

if(!btree)
	return -1;

if(!btree->b_size)
	return -1;

if(!node)
	oldnode = &btree->b_root;
else
  oldnode = &node->bn_right;

if(*oldnode){
btree_remove_node_left(btree,*oldnode);
btree_remove_node_right(btree,*oldnode);

if(btree->b_destroy)
	btree->b_destroy((*oldnode)->bn_data);

free(*oldnode);
*oldnode = NULL;	
btree->b_size--;	
	}

return 0;
}

void btree_destroy(struct btree* btree)
{

	btree_remove_node_left(btree,NULL);
  free(btree);
	return;
	
}

struct btree* btree_merge(struct btree* left,struct btree* right,void* data)
{
struct btree* merge;
	
if(!(left && right))
	return NULL;

merge = btree_create(left->b_destroy);

btree_insert_node_left(merge,NULL,data);

merge->b_root->bn_left = left->b_root;
merge->b_root->bn_right = right->b_root;

merge->b_size = merge->b_size + left->b_size + right->b_size;

left->b_root = right->b_root = NULL;
left->b_size = right->b_size = 0;

return merge;
}

/*SO DEBUG !!!!*/
void printnodes(const struct btree* tree,const struct btree_node* node)
{
struct btree_node *r,*l;

if(!node)
	return;

r = node->bn_right;
l = node->bn_left;

fprintf(stdout,"%f\n",*((float*)node->bn_data));
printnodes(tree,r);
printnodes(tree,l);

}