#include <stdio.h>
#include <stdlib.h>

#include "stack.h"
#include "list.h"

struct node
{
	struct node* nextS;
       	struct node* nextB;
	int data;
};

struct node* root;

struct node** getSmallest(struct node** _root)
{
	struct node** current = _root;

	while((*current)->nextS)
		current = &((*current)->nextS);

	return current;
}

struct node removeNode(int _data)
{
	struct node **current = &root;
	struct node *removeNode = NULL;
	struct node **newRoot = NULL;
	struct node returnNode;

	while((*current)->data != _data)
		current = (*current)->data < _data ? &(*current)->nextB : &(*current)->nextS;


	printf("node to remove:%i\n", (*current)->data);
	removeNode = *current;

	if(removeNode->nextB)
	{
		newRoot = getSmallest(&removeNode->nextB);
		*current = *newRoot;
		*newRoot = (*newRoot)->nextB;

		(*current)->nextS = removeNode->nextS;
		(*current)->nextB = removeNode->nextB;
	}
	else
		*current = (*current)->nextS;;

	returnNode = *removeNode;
	free(removeNode);

	return returnNode;
}

void insert(int _data)
{
	struct node** current = &root;
	struct node* new = malloc(sizeof(*new));

	new->nextS = NULL;
	new->nextB = NULL;
	new->data=_data;

	while (*current)
		current = (*current)->data > _data ? &((*current)->nextS) : &((*current)->nextB);

	*current = new; 
}

void draw(void)
{
	struct node* current = root;
	struct node* stackTop = NULL;
	struct stack* stackpointer = NULL;
	int depth = 0;
	
	stack_init(&stackpointer);

start:

	while (current)
	{
		stack_add( (void*) current , &stackpointer);

		int i;
		for(i = 0; i < depth; i++)
			printf(" ");

		printf("|:%i\n", current->data);

		current = current->nextS;
		
		depth++;	
	}
nextinstack:

	stackTop = (struct node*)stack_get(&stackpointer);
	if(!stackTop)
		return;
	
	current = stackTop->nextB;

	if(current)
		goto start;
	
	depth --;
	goto nextinstack;
}

void balance()
{
	struct node *current = root;
	struct node *stackTop = NULL;
	struct stack *stackpointer = NULL;
	struct list *listroot = NULL;


	stack_init(&stackpointer);
	list_init(&listroot);

	//Create Inorder List
start:	
	while(current)
	{
		stack_add( (void*) current, &stackpointer);
		current = current->nextS;
	}

	stackTop = (struct stack*) stack_pop(&stackpointer);
	stackTop ? current = stackTop->nextB :;
	
	if(current)
	{
		list_add(current->data, &listroot);
		goto start;
	}

	//TODO Balance

}

int main(int argc, char* argv[])
{
	root = NULL;

	insert(7);
	insert(5);
	insert(10);
	insert(11);
	insert(1);
	
	//draw();
	balance();

	printf("balanced");
	//removeNode(7);

	//draw();

	printf("%i is the smallest obejct\n", (*getSmallest(&root))->data);
	return 0;
}