/* btree_poisto.c SJ */

#include <stdio.h>

#include <TRA.h>

/* seuraaja sisäjärjestyksessä */
BTREE_NODE inorder_btree_next(BTREE T, BTREE_NODE n)
{
  /* poistettu */
} /* inorder_btree_next() */
			
	
/* poisto sisäjärjestetystä binääripuusta */
void inorder_btree_delete(BTREE T, ELEMENT x)
{
  BTREE_NODE n, par, lc, rc, korv;
  int loytyi;
  BTREE_DIR suunta;
  ELEMENT korv_elem;

	/* alku kuten lisäyksessäkin */
	loytyi = 0;
	n = BTREE_ROOT(T);
	par = BTREE_NIL;
	/* haetaan paikka */
	while ((n != BTREE_NIL) && ( ! loytyi))  {
		if (BTREE_SAME(T, x, BTREE_RETRIEVE(T, n))) 
			loytyi = 1;
		else {
			par = n;
			if (BTREE_LESS(T, x, BTREE_RETRIEVE(T, n)))  {
				n = BTREE_LEFTCHILD(T, n);
				suunta = left;
			} else {
				n = BTREE_RIGHTCHILD(T, n);
				suunta = right;
			}
		}
	}
	
	if (loytyi)  {

		/* lapset apumuuttujiin */
		lc = BTREE_LEFTCHILD(T, n);
		rc = BTREE_RIGHTCHILD(T, n);

		/* 0-1 -lapsiset tapaukset erikseen: */
		/* jos juuri, ei vasenta lasta */
		if ((n == BTREE_ROOT(T)) && (lc == BTREE_NIL)) 
			BTREE_ASSIGN_ROOT(T, rc);

		/* jos juuri, ei oikeaa lasta */
		else if ((n == BTREE_ROOT(T)) && (rc == BTREE_NIL)) 
			BTREE_ASSIGN_ROOT(T, lc);

		/* jos ei juuri, ei vasenta lasta */
		else if (lc == BTREE_NIL) 
			BTREE_ASSIGN_CHILD(T, par, suunta, rc);

		/* jos ei juuri, ei oikeaa lasta */
		else if (rc == BTREE_NIL) 
			BTREE_ASSIGN_CHILD(T, par, suunta, lc);

		/* molemmat lapset */
		else {

			/* korvaavaksi solmuksi seuraaja */
			korv = inorder_btree_next(T, n);
			korv_elem = BTREE_RETRIEVE(T, korv);

			/* poistetaan rekursiivisesti korvaava */
			inorder_btree_delete(T, korv_elem);

			/* oikea lapsi saattoi muuttua */
			rc = BTREE_RIGHTCHILD(T, n);

			/* uusi solmu */
			korv = BTREE_CREATE_NODE(korv_elem);

			/* poistettavan solmun paikalle */
			if (n == BTREE_ROOT(T)) 
				BTREE_ASSIGN_ROOT(T, korv);
			else
				BTREE_ASSIGN_CHILD(T, par, suunta, korv);

			/* palautetaan lapset */
			BTREE_ASSIGN_CHILD(T, korv, left, lc);
			BTREE_ASSIGN_CHILD(T, korv, right, rc);
		}

		/* vapautetaan poistettava solmu */
		BTREE_ASSIGN_CHILD(T, n, left, BTREE_NIL);
		BTREE_ASSIGN_CHILD(T, n, right, BTREE_NIL);
		BTREE_DESTROY_NODE(T, n); 
	}

} /* inorder_btree_delete() */


/* muita palikoita ja harjoitelmia */
/* tulostus sisäjärjestyksessä, oksa */
void inorder_print_branch(BTREE T, BTREE_NODE n)
{
	if (n != BTREE_NIL)  {
		inorder_print_branch(T, BTREE_LEFTCHILD(T, n));
		TREE_PRINT_NODE(T, n);		/* tms hyödyllistä */
		printf(" ");
		inorder_print_branch(T, BTREE_RIGHTCHILD(T, n));
	}
}

/* tulostus sisäjärjestyksessä, koko puu */
void inorder_print(BTREE T)
{
	inorder_print_branch(T, BTREE_ROOT(T));
}


/* haku sisäjärjestetystä binääripuusta */
int inorder_btree_search(BTREE T, ELEMENT x)
{
	int loytyi = 0;
  	BTREE_NODE n = BTREE_ROOT(T);

	while (( ! loytyi) && (n != BTREE_NIL)) 
		if (BTREE_SAME(T, BTREE_RETRIEVE(T, n), x) )
			loytyi = 1;
		else
			if (BTREE_LESS(T, x, BTREE_RETRIEVE(T, n))) 
				n = BTREE_LEFTCHILD(T, n);
			else
				n = BTREE_RIGHTCHILD(T, n);

	return loytyi;
}


/* kokeellinen osa */
const	N = 30, /* lisättävät alkiot */
	M = 100, /* maksimi alkio */
	K = 20; /* kokeilut */

int main()
{
  int i, s;
  BTREE puu;
  BTREE_NODE x;

	INT_BTREE_CREATE(puu);

	printf("Puuhun : \n");
	for (i = 1 ; i <= N; i++)  {
		s = rand() % M;
		printf("%d ",s);
		inorder_btree_insert(puu, INT_ELEMENT(s));
	}
	putchar('\n');

	printf("Järjestyksessä : \n");
	inorder_print(puu);
	putchar('\n');

	printf("Läpikäyntikokeilu\n");
	x = inorder_btree_next(puu, BTREE_NIL);
	while (x != BTREE_NIL)  {
		printf("%d ", INT_BTREE_RETRIEVE(puu, x));
		x = inorder_btree_next(puu, x);
	}
	printf("\n");

	printf("Haku\n");
	for (i = 1 ; i <= K; i++ ) {
		s = rand() % M;
		printf("%d ", s);
		if (inorder_btree_search(puu, INT_ELEMENT(s))) 
			printf(" löytyi\n");
		else
			printf(" ei löytynyt\n");
	}



	printf("Poistetaan : \n");
	for (i = 1 ; i <= N ; i++ ) {
		s = rand() % M;
		printf("%d", s);
		if (inorder_btree_search(puu, INT_ELEMENT(s))) 
			printf("*");
		printf(" ");
		inorder_btree_delete(puu, INT_ELEMENT(s));
	}
	printf("\n");

	printf("Järjestyksessä : \n");
	inorder_print(puu);
	printf("\n");

	printf("Haku");
	for (i = 1 ; i <= K ; i++) {
		s = rand() % M;
		printf("%d ",s);
		if (inorder_btree_search(puu, INT_ELEMENT(s))) 
			printf(" löytyi\n");
		else
			printf(" ei löytynyt\n");
	}

	printf("Poistetaan kaikki: \n");
	for (i = 1 ; i <= M ; i++) {
		printf("%d", i);
		if (inorder_btree_search(puu, INT_ELEMENT(i))) 
			printf("*");
		printf(" ");
		inorder_btree_delete(puu, INT_ELEMENT(i));
	}
	printf("\n");

	printf("Järjestyksessä : \n");
	inorder_print(puu);
	printf("\n");

	BTREE_FREE(puu);

	exit(0);
}