#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdint.h>
#include <math.h>
#include <string.h>
#include <SDL2/SDL.h>
#include <SDL2/SDL_image.h>
#include <SDL2/SDL_ttf.h>

SDL_Window* gWin;
SDL_Renderer* gRdr;
SDL_Surface* gSfc;
TTF_Font* gFnt;

typedef struct node node;
struct node {
	node* l;
	node* r;
	node* p;
	int d;
	char c;
};

const int rect_sz = 30;
const int mgn_ln = 30;
const int wWidth = 1920;
const int wHeight = 1080;

int max(int a,int b) {
	if(a > b) return a;
	return b;
}

void draw_graph_rec(int x,int y,int w,int h,node* root) {
	SDL_Rect r;
	r.x = x+w/2-rect_sz/2;
	r.y = y;
	r.w = rect_sz;
	r.h = rect_sz;
	if(root == NULL) SDL_RenderDrawRect(gRdr,&r);
	else {
		SDL_RenderFillRect(gRdr,&r);
		char b[16];
		sprintf(b,"%d",root->d);
		SDL_Color c = {0xff,0,0};
		SDL_Surface* s =TTF_RenderText_Solid(gFnt,b,c);
		SDL_Texture* t = SDL_CreateTextureFromSurface(gRdr,s);

		SDL_RenderCopy(gRdr,t,NULL,&r);

		SDL_DestroyTexture(t);
		SDL_FreeSurface(s);
	}
	if(root != NULL) {
		SDL_RenderDrawLine(gRdr,x+w/2,y+rect_sz,x+w/4,y+rect_sz+mgn_ln);
		SDL_RenderDrawLine(gRdr,x+w/2,y+rect_sz,x+w*3/4,y+rect_sz+mgn_ln);
		draw_graph_rec(x,y+rect_sz+mgn_ln,w/2,0,root->l);
		draw_graph_rec(x+w/2,y+rect_sz+mgn_ln,w/2,0,root->r);
	}
}

void draw_graph(node* root) {
	SDL_SetRenderDrawColor(gRdr,0xff,0xff,0xff,0xff);
	SDL_RenderClear(gRdr);
	SDL_SetRenderDrawColor(gRdr,0,0,0xff,0xff);

	int depth = get_depth(root);
	draw_graph_rec(0,0,wWidth,0,root);

	SDL_RenderPresent(gRdr);
}

node* mknode(node* l,node* r,node* p,int d,char c) {
	node* ret = malloc(sizeof(node));
	ret->l = l;
	ret->r = r;
	ret->p = p;
	ret->d = d;
	ret->c = c;
	return ret;
}

void insBST(node* n,node* root) {
	node* c = root;
	while(1) {
		if(c->d > n->d) {
			if(c->r == NULL) {
				c->r = n;
				n->p = c;
				break;
			} else c = c->r;
		} else if(c->d < n->d) {
			if(c->l == NULL) {
				c->l = n;
				n->p = c;
				break;
			} else c = c->l;
		} else break;
	}
}

int main() {
	SDL_Init(SDL_INIT_VIDEO);
	gWin = SDL_CreateWindow("Binary Search Tree",SDL_WINDOWPOS_UNDEFINED,SDL_WINDOWPOS_UNDEFINED,wWidth,wHeight,SDL_WINDOW_SHOWN);
	gSfc = SDL_GetWindowSurface(gWin);
	gRdr = SDL_CreateRenderer(gWin,-1,SDL_RENDERER_ACCELERATED);
	TTF_Init();
	gFnt = TTF_OpenFont("ipag.ttf",30);
	if(gFnt == NULL) return -1;
	node* root = mknode(NULL,NULL,NULL,1000,0);

	time_t t;
	srand((unsigned) time(&t));
	for(int i = 0;i < 100;i++) {
		insBST(mknode(NULL,NULL,NULL,rand()%2000,0),root);
	}

  	draw_graph(root);
	SDL_Delay(5000);

	TTF_CloseFont(gFnt);
	TTF_Quit();
	SDL_DestroyWindow(gWin);
	SDL_Quit();
}