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

typedef struct uzol
{
	int x;
	struct uzol *r;
	struct uzol *l;
	int hladina;
	struct uzol *dalsi;
	char fikt;
}UZOL;

UZOL *koren=0, *zac_fronty=0, *kon_fronty=0;
int max_hladina=0;

void pridaj(UZOL **koren, int i)
{
	UZOL *akt;

	while(*koren && (*koren)->x !=i)
	{
		if((*koren)->x >i) koren=&(*koren)->l;
		else koren=&(*koren)->r;
	}

	if(!*koren)
	{
		akt=(UZOL *) malloc(sizeof(UZOL));
		akt->x=i;
		akt->l=0;
		akt->r=0;
		*koren=akt;
	}

	return;
}

void do_fronty(UZOL *akt, int f, int uroven)
{
	UZOL *pom=akt;

	if(!f) 
	{
		pom=(UZOL *) malloc(sizeof(UZOL));
		pom->fikt='f';
		pom->l=0;
		pom->r=0;
		pom->hladina=uroven;
	}
	else 
	{
		pom->fikt='s';
	}
	if(!kon_fronty) zac_fronty=pom;
	if(kon_fronty) kon_fronty->dalsi=pom;
	pom->dalsi=0;
	kon_fronty=pom;	
}

UZOL *z_fronty(void)
{
	UZOL *pom=zac_fronty;

	if(!zac_fronty->dalsi) kon_fronty=0;
	zac_fronty=zac_fronty->dalsi;

	return pom;
}

void hlbka(UZOL *koren, int uroven)
{
	if(!koren) return;
	if((uroven+1) > max_hladina) max_hladina=uroven+1;
	koren->hladina=uroven+1;

	hlbka(koren->l, uroven+1);
	hlbka(koren->r, uroven+1);
}

#define TERM_WIDTH 64

void vypis_cislo(int level, int cislo, int *nevojde_sa)
{
	int pom=TERM_WIDTH/(1<<(level-1));
	int sirka_cisla=1, mezer_vpravo,mezer_vlevo,l,r;

	if(cislo!=0) sirka_cisla=ceilf(log10f(abs(cislo)));
	if(cislo<0) ++sirka_cisla;
	mezer_vlevo=pom-sirka_cisla;
	mezer_vlevo/=2;
	mezer_vpravo=pom-mezer_vlevo-sirka_cisla;
	for(;mezer_vlevo>0;--mezer_vlevo) printf(" ");
	if(sirka_cisla>pom)
	{
		*nevojde_sa=1;
		l=(sirka_cisla-1)/2;
		r=sirka_cisla-l-1;
		for(;l>0;--l) printf(" ");
		printf("x");
		for(;r>0;--r) printf(" ");
	}
	else printf("%d",cislo);
	for(;mezer_vpravo>0;--mezer_vpravo) printf(" ");
}

void vypis_fiktivni_uzel(int level)
{
	int i=TERM_WIDTH/(1<<(level-1));
	for(;i;--i) printf(" ");
}

void vypis_graficky(UZOL *koren)
{
	UZOL *akt;
	int level=0, nevojde_sa=0;
	
	if(!koren) return;

	zac_fronty=kon_fronty=0;
	do_fronty(koren,1,1);
	while((akt=z_fronty()) && ((akt->hladina)<=(max_hladina)) && level<=7)
	{
		if(akt->l) do_fronty(akt->l,1,(akt->hladina)+1);		
		else do_fronty(0,0,(akt->hladina)+1);
		if(akt->r) do_fronty(akt->r,1,(akt->hladina)+1);		
		else do_fronty(0,0,(akt->hladina)+1);
		
		if(akt->hladina>level) 
		{
			printf("\n\n\n");
			++level;
		}
		if(akt->fikt=='s')
			vypis_cislo(level,akt->x,&nevojde_sa);
		else
			vypis_fiktivni_uzel(level);
	}
	if(level>7) printf("sori, osmu a dalsie hladiny uz nejde zobrazit");
	if(nevojde_sa) printf("\n[niektore cisla pre svoju velkost nemohli byt zobrazene,\n\tpreto sa na ich pozicii vyskytuje \"x\"]");
}

UZOL **zisti_max(UZOL **uzol)
{
	while((*uzol)->r) uzol=&(*uzol)->r;
	return uzol;
}


void vymazaj(UZOL **koren, int i)
{
	UZOL *pom, **pom2;

	while(*koren && (*koren)->x != i)
	{
		if((*koren)->x >i) koren=&(*koren)->l;
		else koren=&(*koren)->r;
	}

	if(!(*koren)) return;

	if((*koren)->l ==0 || (*koren)->r ==0)
	{
		pom=*koren;
		*koren=((*koren)->l ==0) ? (*koren)->r : (*koren)->l;

		free(pom);
	}
	else
	{
		pom2=zisti_max(&(*koren)->l);
		(*koren)->x = (*pom2)->x;
		pom=*pom2;
		if((*pom2)->l ==0) *pom2=0;
		else *pom2=(*pom2)->l;
		free(pom);
	}
}

int main(int argc, char *argv[])
{
	int i=1, kresli=0, vstup;
	char *pom;

	if(argc<2) return 1;
	if(*((*(argv+1))+1)=='v')
		kresli=1;
	if(kresli) ++i;

	for(;i<argc;++i)
	{
		pom=*(argv+i);
		if(strlen(pom) <=1) continue;
		if( ((pom[0]!='i')&&(pom[0]!='d')) ||
			( (pom[1]!='-') && ! ( (pom[1]>='0')&&(pom[1]<='9')))) 
			continue;

		vstup=atoi(pom+1);
		if(*pom=='i') pridaj(&koren,vstup);
		if(*pom=='d') vymazaj(&koren,vstup);
		if(kresli) 
		{
			max_hladina=0;
			hlbka(koren,0);
			vypis_graficky(koren);
			if(i!=argc-1) printf("\ndalsia zmena:");
			else printf("\n");
		}
	}
	
	if(!kresli)
	{
		hlbka(koren,0);
		vypis_graficky(koren);
		printf("\n");
	}
	return;
}