#include<iostream.h>
#include<stdlib.h>
#include"tree.h"



/* alloca la radice  senza infilarci niente */
struct tnodo *crea_albero(void){
	return crea_nodo();
}

/* alloca un nodo */
struct tnodo *crea_nodo(void){
	struct tnodo *p;

	if((p=new struct tnodo[1])==NULL){
		cerr << "crea_nodo" << endl;
		exit(EXIT_FAILURE);
	}
	p->maggiori=p->minori=NULL;
	return p;
}

/* attraversamenti ricorsivi */
void inorder_r(struct tnodo *p){
	if(!p)return;
	inorder_r(p->minori);
	cout <<  p->key << endl;
	inorder_r(p->maggiori);
}

void preorder_r(struct tnodo *p){
	if(!p)return;
	cout <<  p->key << endl;
	preorder_r(p->minori);
	preorder_r(p->maggiori);
}

void postorder_r(struct tnodo *p){
	if(!p)return;
	postorder_r(p->minori);
	postorder_r(p->maggiori);
	cout <<  p->key << endl;
}

/* libera ricorsivamente la memoria dell'albero */
void destroy_tree(struct tnodo *p){
	if(!p)return;
	destroy_tree(p->minori);
	destroy_tree(p->maggiori);
	delete[] p;
}

/* copia l'albero in un altro sfruttando sempre la ricorsione */
struct tnodo *tree_copy(struct tnodo *p){
	struct tnodo *n;

	if(!p) return NULL;
	n=crea_nodo();
	memcpy(n,p,sizeof(struct tnodo));
	n->maggiori=tree_copy(p->maggiori);
	n->minori=tree_copy(p->minori);
	return n;
}

/* verifica l'eguaglianza di due alberi nodo per nodo
 * ritorna 0 in caso non siano uguali
 * NON E' CORRETTA nel caso degli alberi binari di ricerca */
int tree_match(struct tnodo *t1, struct tnodo *t2){
	return(((!t1)&&(!t2))||
			(t1&&t2&&(t1->key==t2->key)&&
			 (tree_match(t1->maggiori,t2->maggiori))&&
			 (tree_match(t1->minori,t2->minori))));
}

/* restituisce l'altezza massima di un albero binario */
int tree_height(struct tnodo *p){
	int hsx,hdx;
	if(!p) return 0;
	hsx=tree_height(p->maggiori);
	hdx=tree_height(p->minori);
	return (1 + (hsx>hdx?hsx:hdx));
}

/* restituisce la dimensione (in numero nodi) di un albero. E' banale, visto
 * che la dimensione sara' o 0 nel caso dell'albero vuoto oppure pari alla somma
 * della dimensione dei sottoalberi + 1 per la radice */
int tree_size(struct tnodo *tree){
	if(!tree)return 0;
	return 1+tree_size(tree->maggiori)+tree_size(tree->minori);
}
/* inserisce in un albero binario di ricerca un nodo n
 * precedentemente definito */
struct tnodo *tree_insert(struct tnodo *tree, struct tnodo *n){
	struct tnodo *p;

        if(!tree)
	   return n;
	  
	// la chiave DEVE essere univoca
	if(tree->key==n->key) return NULL;

	if(tree->key>n->key){
	  p=tree_insert(tree->minori, n);
	  if(p)
	   tree->minori=p;
	  else
	   return NULL;
	}
	else{
	  p=tree_insert(tree->maggiori, n);
	  if(p)
	    tree->maggiori=p;
	  else
	    return NULL;
	}

	return tree;
}

/* ricerca in un albero binario di ricerca il valore chiave */
struct tnodo *tree_search(struct tnodo *p, tipo_chiave v){
	if(!p)return NULL;
	if(p->key==v)return p;
	if(p->key < v ) return tree_search(p->maggiori, v);
	return tree_search(p->minori, v);
}

/* ricerca iterativa in un albero binario di ricerca */
struct tnodo *tree_search_i(struct tnodo *p, tipo_chiave v){
	while(p){
	  if(v==p->key) return p;
	  if(p->key<v) p=p->maggiori;
	  else p=p->minori;
	 }
	return NULL;
}


/* rotazioni a destra e a sinistra, servono per l'inserimento in radice */
struct tnodo *rotR(struct tnodo *h){
	struct tnodo *x;

	x=h->maggiori;
	h->maggiori=x->minori;
	x->minori=h;

	return x;
}

struct tnodo *rotL(struct tnodo *h){
	struct tnodo *x;

	x=h->minori;
	h->minori=x->maggiori;
	x->maggiori=h;

	return x;
}

/* inserimento  in  radice,  in  genere nelle  applicazioni  che  mescolano
 * inserimento  e ricerca,  e'  piu' frequente  la  ricerca degli  elementi
 * appena inseriti.  Di conseguenza un  piccolo vantaggio si  puo' ottenere
 * inserendo in radice  i nuovi elementi e non come  foglie; in questo caso
 * la ricerca dei valori recentemente inseriti e' molto breve */

struct tnodo *root_tree_insert(struct tnodo *tree, struct tnodo *n){
	struct tnodo *p;

        if(!tree)
	   return n;
	  
	/* cerco l'elemento tramite la sua chiave,
	 * se esistesse sarebbe un errore inserirlo e quindi 
	 * esco */
	p=tree_search_i(tree, n->key);
	if(p) return NULL;


	/* assodato che non c'e' chiamo la routine reale */
	tree=root_tree_insert_w(tree,n);
	return tree;

}

struct tnodo *root_tree_insert_w(struct tnodo *tree, struct tnodo *n){
	if (!tree)
		return n;

	if(tree->key>n->key){
	   tree->minori=root_tree_insert_w(tree->minori, n);
	   tree=rotL(tree);
	}else{
	   tree->maggiori=root_tree_insert_w(tree->maggiori, n);
	   tree=rotR(tree);
	}
	return tree;
}

/* mi restituisce il nodo di indice index */
struct tnodo *tree_select(struct tnodo *p, int index){
	int t;
        
	if(!p) return NULL;
	/* guardo la dimensione del sottoalbero dei valori
	 * piu' piccoli, corrispondera' all'indice della radice */
	t=tree_size(p->minori);
	/* se l'indice della mia radice e' maggiore di quello
	 * che cercavo devo quardare a destra */
	if(t>index)return tree_select(p->minori,index);
	/* se e' minore guardo a sinistra e sottraggo
	 * dall'indice l'indice della radice e lo diminuisco di 1 
	 * visto che riduco le dimensioni dell'albero in cui cerco */
	if(t<index)return tree_select(p->maggiori,index-t-1);
	/* altrimenti l'ho gia' trovato */
	return(p);
}

/* la partizione e' un'operazione che permette di portare in radice il nodo 
 * di indice k. Si ottiene banalmente modificando la selezione con aggiunta
 * di rotazioni */
struct tnodo *tree_partition(struct tnodo *p, int k){
	int t;
        
	if(!p) return NULL;
	t=tree_size(p->minori);
	if(t>k){
	  p->minori=tree_partition(p->minori,k);
	  p=rotL(p);
	}
	if(t<k){
	  p->maggiori=tree_partition(p->maggiori,k-t-1);
	  p=rotR(p);
	}
	return(p);
}

/* riunisce i due sottoalberi. ATTENZIONE non  e' una vera unione in quanto
 * non  verifico  la  presenza  di  chiavi  duplicate  e  ipotizzo  che  il
 * sottoalbero a contenga chiavi con valori piu' piccoli*/

struct tnodo *tree_join_delete(struct tnodo *a, struct tnodo *b){
	/* se non esiste a ho gia' fatto */
	if(!b) return a;
	/* altrimenti porto il piu' piccolo valore di b in radice*/
	b=tree_partition(b,0);
	b->minori=a;
	return b;
}

/* cancella il nodo avente chiave key, e' molto simile alla partizione. */
struct tnodo *tree_delete(struct tnodo *p, tipo_chiave v){
	struct tnodo *x;

	if(!p) return NULL;
	if(p->key>v)
		p->minori=tree_delete(p->minori,v);
	if(p->key<v)
		p->maggiori=tree_delete(p->maggiori,v);
	if(p->key==v){
		x=p;
		p=tree_join_delete(p->minori,p->maggiori);
		delete [] x;
	}
	return p;
}


/* inserimento casuale, l'inserimento casuale dovrebbe evitare che
 * l'inserzione consecutiva di valori gia' ordinati non mi porti a
 * alberi esageratamente sbilanciati 
 * 
 * inserendo 1000 numeri consecutivi si ottiene un albero di altezza 22
 * contro un minimo di circa 10 ! */

struct tnodo *rand_tree_insert(struct tnodo *tree, struct tnodo *n){

	/* la probabilita' di inserimento in radice
	 * man mano ricorsivamente ci si avvicina alle foglie
	 * in funzione delle dimensioni dell'albero */
	if(rand()<RAND_MAX/(1+tree_size(tree)))
	  return root_tree_insert(tree,n);

	/* non ho inserito in radice ritento 
	 * con l'inserimento casuale */
	if(tree->key>n->key)
	   tree->minori=rand_tree_insert(tree->minori,n);
	else
	   tree->maggiori=rand_tree_insert(tree->maggiori,n);

	return tree;

}

struct tnodo *tree_balance(struct tnodo *p){
	int h;

	h=tree_size(p);

	if(h<2)return p;

	p=tree_partition(p, h/2);
	p->minori=tree_balance(p->minori);
	p->maggiori=tree_balance(p->maggiori);
	return p;
}

/* unisco due alberi a e b, attenzione a non viene distrutto
 * e b viene modificato
 * NON viene fatta verifica sulla presenza di chiavi duplicate */

struct tnodo *tree_join(struct tnodo *a, struct tnodo *b){

	struct tnodo *tmp;

	if(!b)return a;
	if(!a)return b;
	tmp=crea_nodo();
	memcpy(tmp,a,sizeof(struct tnodo));
	tmp->minori=tmp->maggiori=NULL;
	b=root_tree_insert(b,tmp);
	b->minori=tree_join(b->minori,a->minori);
	b->maggiori=tree_join(b->maggiori,a->maggiori);
	return b;
}