#include<iostream>

// Rappresentazione mediante lista dei figli

typedef char TipoInfo;

struct NodoSCL;

typedef struct{
	TipoInfo info;
	struct NodoSCL* figli;
} NodoAlbero;

struct NodoSCL{
	NodoAlbero* figlio;
	struct NodoSCL* next;
};

typedef NodoAlbero* Albero;

int grado(NodoAlbero* n){
	int g = 0;
	NodoSCL* aux = n -> figli;
	while (aux != NULL){ //Scansiona tutti i figli
		g += 1; // aggiunge 1 a g per ogni figlio del nodo n
		aux = aux -> next;
	}
	return g;
}

int numNodi(Albero a){
	if (a == NULL) //albero vuoto
		return 0;
	
	int n = 1; //conta nodo radice
	
	NodoSCL* aux = a->figli;
	while (aux != NULL){ //Scansiona tutti i figli
		n += numNodi(aux->figlio); // aggiunge ad n il numero di nodi del figlio corrente
		aux = aux -> next;
	}
	return n;
}

NodoAlbero* padre(Albero a, NodoAlbero* n){
	if (a == NULL || a == n) // albero vuoto o n radice
		return NULL; // n non ha padre nell'albero a
	
	// Esegue una visita in profondita', cercando il nodo che ha per figlio n
	NodoSCL* aux = a -> figli;
	while (aux != NULL){ //Scansiona tutti i figli (finche' non trova padre di n)
		if (aux -> figlio == n) // a e' padre di n
			return a;
		NodoAlbero* p = padre(aux -> figlio, n); // cerca il padre p nel sottoalbero con radice il figlio corrente
		if (p != NULL) // padre trovato
			return p;
		aux = aux -> next;
	}
	return NULL; // n non appartiene all'albero a
}

NodoSCL* figli(NodoAlbero* n){
	return n -> figli;
}

NodoAlbero* aggiungiNodo(NodoAlbero* n){
	NodoAlbero* nuovo = (NodoAlbero*) malloc(sizeof(NodoAlbero)); // crea nuovo nodo
	nuovo -> figli = NULL;
	if (n != NULL){// albero non vuoto
		// inserisce nuovo nodo in testa alla lista dei figli
		NodoSCL* nodoSCL = (NodoSCL*) malloc(sizeof(NodoSCL));
		nodoSCL -> figlio = nuovo;
		nodoSCL -> next = n -> figli;
		n -> figli = nodoSCL;
	}
	return nuovo;
}

void aggiungiSottoalbero(Albero a, NodoAlbero* n){
	if (a == NULL || n == NULL) // albero vuoto
		return;
	// inserisce la radice di a come primo figlio del nodo n
	NodoSCL* nodoSCL = (NodoSCL*) malloc(sizeof(NodoSCL));
	nodoSCL -> figlio = a;
	nodoSCL -> next = n -> figli;
	n -> figli = nodoSCL;
}

Albero rimuoviSottoalbero(Albero* a, NodoAlbero* n){ // Albero a passato tramite puntatore per poter modificare anche la radice
	if (a == NULL || n == NULL) // albero non valido o vuoto o nodo non valido
		return NULL;
	// Trova il padre di n
	NodoAlbero* p = padre(*a, n);
	if (p == NULL){ // il nodo da scollegare e' la radice
		*a = NULL;
		return n;
	}
	NodoSCL* aux = p -> figli;
	if (aux -> figlio == n){ // n e' il primo figlio di p
		// Eliminazione dell'elemento in testa
		p -> figli = p -> figli -> next;
		free(aux);
		return n;
	}
	// Scansiona i figli di p fino a trovare il predecessore di n
	while(aux -> next != NULL){
		if (aux -> next -> figlio == n){// aux punta al predecessore di n
			// elimina il nodo n dai figli di p
			NodoSCL* aux2 = aux -> next;
			aux -> next = aux -> next -> next;
			free(aux2);
			return n;
		}
		aux = aux -> next;
	}
	return NULL; // Non viene mai eseguito
}

void stampa(Albero a){// stampa dell'albero in notazione parentetica
	if (a == NULL){ //albero vuoto
		std::cout << "()";
		return;
	}
	std::cout << "(" << a -> info;
	NodoSCL* aux = a -> figli;
	while (aux != NULL){
		stampa(aux -> figlio);
		aux = aux -> next;
	}
	std::cout << ")";
}

int main(){
	std::cout << "Crea albero a" << std::endl;
	Albero a = NULL;
	std::cout << "a=";
	stampa(a);
	std::cout << std::endl;
	std::cout << "L'albero a contiene " << numNodi(a) << " nodi" << std::endl;
	NodoAlbero* n = aggiungiNodo(NULL);
	n -> info = 'a';
	a = n;
	std::cout << "a=";
	stampa(a);
	std::cout << std::endl;
	std::cout << "L'albero a contiene " << numNodi(a) << " nodi" << std::endl;
	NodoAlbero* m = aggiungiNodo(n);
	m -> info = 'b';
	m = aggiungiNodo(n);
	m -> info = 'c';
	std::cout << "a=";
	stampa(a);
	std::cout << std::endl;
	std::cout << "L'albero a contiene " << numNodi(a) << " nodi" << std::endl;
	n = aggiungiNodo(m);
	n -> info = 'd';
	n = aggiungiNodo(m);
	n -> info = 'e';
	n = aggiungiNodo(m);
	n -> info = 'f';
	std::cout << "a=";
	stampa(a);
	std::cout << std::endl;
	std::cout << "L'albero a contiene " << numNodi(a) << " nodi" << std::endl;
	std::cout << "Il padre del nodo " << m -> info << " e' il nodo " << padre(a,m) -> info << std::endl;
	std::cout << "Il padre del nodo " << n -> info << " e' il nodo " << padre(a,n) -> info << std::endl << std::endl;
	
	std::cout << "Crea albero b" << std::endl;
	// Crea albero b
	Albero b = NULL;
	NodoAlbero* n2 = aggiungiNodo(NULL);
	n2 -> info = 'x';
	b = n2;
	NodoAlbero* n3 = aggiungiNodo(n2);
	n3 -> info = 'z';
	n3 = aggiungiNodo(n2);
	n3 -> info = 'y';
	std::cout << "b=";
	stampa(b);
	std::cout << std::endl;
	std::cout << std::endl;

	std::cout << "Aggiungi albero b al nodo c dell'albero a" << std::endl;
	aggiungiSottoalbero(b, m);
	std::cout << "a=";
	stampa(a);
	std::cout << std::endl;
	std::cout << "L'albero a contiene " << numNodi(a) << " nodi" << std::endl << std::endl;
	std::cout << std::endl;
	
	std::cout << "Rimuovi il sottoalbero con radice nel nodo c da a" << std::endl;
	Albero c = rimuoviSottoalbero(&a, m);
	std::cout << "a=";
	stampa(a);
	std::cout << std::endl;
	std::cout << "c=";
	stampa(c);
	std::cout << std::endl;
	std::cout << std::endl;

	std::cout << "Rimuovi il sottoalbero con radice nel nodo f da c" << std::endl;
	Albero d = rimuoviSottoalbero(&c, n);
	std::cout << "c=";
	stampa(c);
	std::cout << std::endl;
	std::cout << "d=";
	stampa(d);
	std::cout << std::endl;
}