%              Deklaratív Programozás gyakorlat 2010.02.17.
% 		  Prolog programozás: struktúrák, listák
%		                MEGOLDÁSOK
% ---------------------------------------------------------------

% 1. feladat
% fa_pontszama(+Fa, -N): A Fa bináris fa csomópontjainak száma N.
fa_pontszama(leaf(_), 0).
fa_pontszama(node(L,R), P) :-
	fa_pontszama(L, LP),
	fa_pontszama(R, RP),
	P is LP+RP+1.

% 2. feladat
% fa_melysege(+Fa, ?M): A Fa bináris fa mélysége M. 
fa_melysege(leaf(_), 0).
fa_melysege(node(L,R), M) :-
	fa_melysege(L, LM),
	fa_melysege(R, RM),
	M is max(LM,RM)+1.

% 3. feladat
% lista_hossza(+Lista, -Hossz): A Lista egészlista hossza Hossz.
lista_hossza([], 0).
lista_hossza([_|L], H) :-
	lista_hossza(L, H0),
	H is H0+1.

% 4. feladat
% fa_noveltje(+Fa0, ?Fa): Fa úgy áll elő a Fa0 bináris fából, hogy az
% utóbbi minden egyes levelében levő értéket 1-gyel megnöveljük.
fa_noveltje(leaf(X), leaf(Y)) :-
	Y is X+1.
fa_noveltje(node(L,R), node(NL,NR)) :-
	fa_noveltje(L, NL),
	fa_noveltje(R, NR).

% 5. feladat
% lista_noveltje(+L0, ?L): Az L számlista úgy áll elő az L0		  
% számlistából, hogy az utóbbi minden egyes elemét 1-gyel megnöveljük.
lista_noveltje([], []).
lista_noveltje([X|L], [NX|NL]) :-
	NX is X+1,
	lista_noveltje(L, NL).

% 6. feladat
% fa_balerteke(+Fa, ?Ertek): A Fa bináris fa legbaloldalibb levelében
% az Ertek egész érték szerepel.
fa_balerteke(leaf(X), X).
fa_balerteke(node(L,_), B) :-
	fa_balerteke(L, B).

% 7. feladat
% fa_jobberteke(+Fa, ?Ertek): A Fa bináris fa legjobboldalibb levelében 
% az Ertek egész érték szerepel.
fa_jobberteke(leaf(X), X).
fa_jobberteke(node(_,R), J) :-
	fa_jobberteke(R, J).

% 8. feladat
% lista_utolso_eleme(+L, ?Ertek): A Lista egészlista utolsó eleme Ertek.
lista_utolso_eleme([E], E).
lista_utolso_eleme([_|L], E) :-
	lista_utolso_eleme(L, E).

% 9. feladat
% fa_reszfaja(+Fa, -Resz): Resz a Fa bináris fa részfája.
fa_reszfaja(Fa, Fa).
fa_reszfaja(node(L,_), Fa) :-
	fa_reszfaja(L, Fa).
fa_reszfaja(node(_,R), Fa) :-
	fa_reszfaja(R, Fa).

% 10. feladat
% lista_szuffixuma(+L0, -L): L az L0 szuffixuma.
lista_szuffixuma(L, L).
lista_szuffixuma([_|L], S) :-
	lista_szuffixuma(L, S).

% 11. feladat
% listaminta_adott_hosszal(-Listaminta, +Hossz): A Listaminta hossza Hossz.
listaminta_adott_hosszal([], 0).
listaminta_adott_hosszal([_|L], H) :-
	H > 0,
	H1 is H-1,
	listaminta_adott_hosszal(L, H1).

% 12. feladat
% faminta_melysege_max(-Faminta, +MaxMelyseg): 
% A Faminta binárisfa-minta mélysége =< MaxMelyseg. 
faminta_melysege_max(leaf(_), MaxD) :-
	MaxD >= 0.
faminta_melysege_max(node(L,R), MaxD) :-
	MaxD >= 1,
	MaxD1 is MaxD-1,
	faminta_melysege_max(L, MaxD1),
	faminta_melysege_max(R, MaxD1).

% 13. feladat
% fa_tukorkepe(+Fa0, ?Fa): Fa a Fa0 bináris fa tükörképe.
fa_tukorkepe(leaf(X), leaf(X)).
fa_tukorkepe(node(L,R), node(TR,TL)) :-
	fa_tukorkepe(L, TL),
	fa_tukorkepe(R, TR).

% 14. feladat
% fa_tukros(+Fa): A Fa bináris fa tükörszimmetrikus.
fa_tukros(Fa) :-
	fa_tukorkepe(Fa, Fa).

% 15. feladat
% fa_levelerteke(+Fa, -Ertek): A Fa bináris fa egy levelében található
% érték az Ertek.
fa_levelerteke(Fa, E) :-
	fa_reszfaja(Fa, leaf(E)).

% 16. feladat
% fa_rendezett(+Fa): A Fa bináris fa rendezett.
fa_rendezett(leaf(_)).
fa_rendezett(node(L,R)) :-
	fa_rendezett(L), 
	fa_rendezett(R),
	fa_jobberteke(L, LJ),
	fa_balerteke(R, RB),
	LJ < RB.

% fa_rendezett(+Fa): A Fa bináris fa rendezett. Hatékonyabb megoldás.
fa_rendezett2(Fa) :-
	fa_rendezett(Fa, -inf, _).
			% -inf a -végtelen értékű lebegőpontos szám

% fa_rendezett(+Fa, +BalMin, -Jobb): A Fa rendezett,  balszélső levelértéke
% nagyobb mint BalMin, jobbszélső levelének értéke Jobb.
fa_rendezett(leaf(E), BalMin, Jobb) :-
	BalMin < E, Jobb = E.
fa_rendezett(node(L, R), BalMin0, Jobb) :-
	fa_rendezett(L, BalMin0, Jobb0),
	fa_rendezett(R, Jobb0, Jobb).

% 17. feladat
% faminta_adott_pontszammal(-Faminta, +Pontszam): A Faminta
% binárisfa-minta csomópontjainak száma Pontszam.
faminta_adott_pontszammal(Fa, MaxL) :-
	faminta_pontszama_max(Fa, MaxL, 0).

% faminta_pontszama_max(-Fa, +Max0, -Max): A Fa faminta pontszáma P,
% ahol P =< Max0, es Max = Max0-P.
faminta_pontszama_max(leaf(_), MaxL0, MaxL0) :-
	MaxL0 >= 0.
faminta_pontszama_max(node(L,R), MaxL0, MaxL) :-
	MaxL0 >= 1,
	MaxL1 is MaxL0-1,
	faminta_pontszama_max(L, MaxL1, MaxL2),
	faminta_pontszama_max(R, MaxL2, MaxL).