-- AUTOR: Elvira Mayordomo Cámara
-- PROYECTO: módulo de implementación del TAD arboles 
-- FICHERO: arboles.adb
-- FECHA: 22-10-02, basado en el libro de Javier Campos (ver bibliografía)

with unchecked_deallocation;
package body arboles is

procedure disponer is new unchecked_deallocation(nodo,arbol);

procedure creaVacio(b:out bosque) is
-- Post: b=bVacío
-- coste en tiempo O(1)
begin
b.primArbol:=null;
b.ultArbol:=null;
b.long:=0;
b.altura:=-1;
end creaVacio;

procedure anadeDch(b:in out bosque; a:in arbol) is
-- Pre: b=b0
-- Post: b=+dcha(b0,a)
-- NO HACE COPIA DE a
-- coste en tiempo O(1)
begin
if long(b)=0 then
b.primArbol:=a;
else
b.ultArbol.sighermano:=a;
end if;
b.ultArbol:=a;
b.long:=b.long+1;
b.altura:=integer'max(b.altura,a.altura);
end anadeDch;

function long(b:in bosque) return integer is
-- Post: long(b)=longitud(b)
-- coste en tiempo O(1)
begin
	return(b.long);
end long;
procedure observa(b:in bosque; i:in integer; a:out arbol) is
-- Pre: 1<=i<=longitud(b) 
-- Post: a=b[i]
-- HACE COPIA
-- coste en tiempo: para un árbol de n nodos tarda O(n)
aux: arbol;
begin
	aux:=b.primarbol;
	for n in 2..i loop
		aux:=aux.sighermano;
	end loop;
	asignaArbol(a,aux);
	a.sighermano:=null;
end observa;

function altBosque(b:bosque) return integer is
-- Post: altBosque(b)=alturaB(b)
-- coste en tiempo O(1)
begin
	return(b.altura);
end altBosque;
procedure enraizar(e:in elemento; b:in bosque; a:out arbol) is
-- Post: a=enraizar(e,b)
-- NO HACE COPIA DE b
-- coste en tiempo O(1)
begin
	a:=new nodo'(e,b.primArbol,null,b.altura+1,b.long);
end enraizar;

function raiz(a:arbol) return elemento is
-- Post: raiz(a)=raíz(a)
-- coste en tiempo O(1)
begin
	return(a.dato);
end raiz;

procedure subarbol(a:in arbol; i:in integer; sa:out arbol) is
-- Pre: 1<=i<=numHijosRaiz(a)
-- Post: sa=subárbol(a,i)
-- HACE COPIA
-- coste en tiempo: para un árbol de n nodos tarda O(n)
aux: arbol;
begin
	aux:=a.primogenito;
	for n in 2..i loop
		aux:=aux.sighermano;
	end loop;
	asignaArbol(sa,aux);
	sa.sighermano:=null;
end subarbol;

procedure subarbolsc(a:in arbol; i:in integer; sa:out arbol) is
-- Pre: 1<=i<=numHijosRaiz(a)
-- Post: sa=subárbol(a,i)
-- NO HACE COPIA
-- coste en tiempo O(i)
aux: arbol;
begin
	for n in 2..i loop
		aux:=aux.sighermano;
	end loop;
	sa:=aux;
	sa.sighermano:=null;
end subarbolsc;

function numHijos(a:arbol) return integer is
-- Post: numHijos(a)=numHijosRaiz(a)
-- coste en tiempo O(1)
begin
	return(a.numHijos);
end numHijos;

function esHoja(a:arbol) return boolean is
-- Post: esHoja(a)=eshoja(a)
-- coste en tiempo O(1)
begin
	return(a.numHijos=0);
end esHoja;

function altArbol(a:arbol) return integer is 
-- Post: altArbol(a)=alturaA(a)
-- coste en tiempo O(1)
begin
	return(a.altura);
end altArbol;

procedure elBosque(a:in arbol; b:out bosque) is
-- Guarda en b la lista de subárboles de a.
-- No actualiza b.ultimo
-- No duplica
-- coste en tiempo O(1)
begin
b.primArbol:=a.primogenito;
b.long:=a.numHijos;
b.altura:=a.altura-1;
end elBosque;

procedure asignaBosque(nuevo:out bosque; viejo:in bosque) is
-- Duplica la representación del bosque viejo
-- guardándolo en nuevo.
-- No utiliza viejo.ultArbol
-- coste en tiempo: para un bosque de n nodos tarda O(n)
auxV,auxN:arbol;
begin
if viejo.primArbol=null 
then
 creaVacio(nuevo);
else
asignaArbol(auxN,viejo.primArbol);
nuevo.primArbol:=auxN;
nuevo.long:=viejo.long;
nuevo.altura:=viejo.altura;
auxV:=viejo.primArbol.sigHermano;
while auxV/=null loop
	asignaArbol(auxN.sigHermano,auxV);
	auxV:=auxV.sigHermano;
	auxN:=auxN.sigHermano;
end loop;
nuevo.ultArbol:=auxN;
auxN.sigHermano:=null;
end if;
end asignaBosque;

procedure liberaBosque(b:in out bosque) is
-- Libera la memoria dinámica accesible 
-- desde b, quedando b vacío.
-- No utiliza b.ultArbol
-- coste en tiempo: para un bosque de n nodos tarda O(n)
aux,aux2:arbol;
begin
if b.primArbol/=null then
aux:=b.primArbol;
aux2:=b.primArbol.sigHermano;
for i in 1..b.long loop 	
liberaArbol(aux);
aux:=aux2;
aux2:=aux2.sigHermano;
end loop;
creaVacio(b);
end if;
end liberaBosque;

procedure asignaArbol(nuevo:out arbol;
viejo:in arbol) is
-- Duplica la representación del árbol viejo 
-- guardándolo en nuevo.
-- coste en tiempo: para un árbol de n nodos tarda O(n)
baux,baux2:bosque;
begin
baux.primArbol:=viejo.primogenito;
baux.long:=viejo.numHijos;
baux.altura:=viejo.altura-1;
-- asignaBosque no necesita baux.ultArbol
asignaBosque(baux2,baux);
enraizar(raiz(viejo),baux2,nuevo);
end asignaArbol;

procedure liberaArbol(a:in out arbol) is
-- Libera la memoria dinámica accesible 
-- desde a.
-- coste en tiempo: para un árbol de n nodos tarda O(n)
baux:bosque;
begin
baux.primArbol:=a.primogenito;
baux.long:=a.numHijos;
baux.altura:=a.altura-1;
-- liberaBosque no necesita baux.ultArbol
liberaBosque(baux);
disponer(a);
end liberaArbol;

end arboles;