-module(d10sg3).
-author(hanak@inf.bme.hu).
-vsn('2010-03-20').
%-export([]).
-compile(export_all).

%%% Deklaratív programozás, 3. gyakorlat
%%% Erlang programozás: struktúrák, listák
%%% 2010. 03. 17.

%% @type level() = integer().
%% @type cspnt() = {fa(),fa()}.
%% @type fa() = level() | cspnt().

%% @type egeszlista() = [integer()].

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 1. Bináris fa csomópontjainak száma

%% @spec faPontszama(F::fa()) -> N::integer().
%% Az F fa csomópontjainak száma N.

faPontszama({Bf,Jf}) ->
    1 + faPontszama(Bf) + faPontszama(Jf);
faPontszama(_) ->
    0.

t1(1) ->
    faPontszama({1,{2,3}}) == 2;
t1(2) ->
    faPontszama({1,{2,{3,4}}}) == 3.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 2.  Bináris fa mélysége

%% @spec faMelysege(F::fa()) -> M::integer().
%% Az F fa mélysége, azaz az egymásba skatulyázott csomópontjainak maximális
%% száma M.


faMelysege0({Bf,Jf}) ->
    Bm = faMelysege0(Bf),
    Jm = faMelysege0(Jf),
    1 + if Bm > Jm ->
		Bm;
	   true ->
		Jm
	end;
faMelysege0(_) ->
    0.

faMelysege({Bf,Jf}) ->
    1 + erlang:max(faMelysege(Bf),faMelysege(Jf));
faMelysege(_) ->
    0.

%   Megjegyzés: az érthetőséget növeli a max függvény használata.

t2(1) ->
    faMelysege({{1,4},{2,3}}) == 2;
t2(2) ->
    faMelysege({1,{2,{4,3}}}) == 3.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 3.  Lista hossza

%% @spec listaHossza(L::egeszlista()) -> H::integer().
%% Az L egészlista hossza, azaz elemeinek száma H.

listaHossza0([]) ->
    0;
listaHossza0([_|Xs]) ->
    1 + listaHossza0(Xs).

listaHossza(Xs) ->
    listaHossza(Xs,0).

listaHossza([],H) ->
    H;
listaHossza([_|Xs],H) ->
    listaHossza(Xs,H+1).

t3(1) ->
    listaHossza([1,3,5]) == 3.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 4.  Bináris fa minden levélértékének növelése

%% @spec faNoveltje(F0::fa()) -> F::fa().
%% Az F fa az F0 fának olyan másolata, amelynek ugyanannyi levele és
%% csomópontja van, mint az F0-nak, de az F minden levelének értéke
%% pontosan eggyel nagyobb, mint az F0 megfelelő levelének az értéke.

faNoveltje({Bf,Jf}) ->
    {faNoveltje(Bf),faNoveltje(Jf)};
faNoveltje(V) ->
    V+1.

t4(1) ->
    faNoveltje({1,{2,3}}) == {2,{3,4}}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 5.  Számlista minden elemének növelése

%% @spec listaNoveltje(L0::egeszlista()) -> L::egeszlista().
%% Az L egészlista az L0 egészlistának olyan másolata, amelynek ugyanannyi
%% eleme van, mint az L0-nak, de az L minden elemének értéke pontosan
%% eggyel nagyobb, mint az L0 megfelelő elemének az értéke.

listaNoveltje0([X|Xs]) ->
    [X+1|listaNoveltje0(Xs)];
listaNoveltje0([]) ->
    [].

listaNoveltje(Xs) ->
    [X+1 || X <- Xs].

t5(1) ->
    listaNoveltje([1,5,2]) == [2,6,3].


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 6.  Bináris fa legbaloldalibb levélértékének meghatározása

%% @spec faBalerteke(F::fa()) -> E::level().
%% Az F fa legbaloldalibb levelének értéke E.

faBalerteke({Bf,_Jf}) ->
    faBalerteke(Bf);
faBalerteke(V) ->
    V.
t6(1) ->
    faBalerteke({{1,4},{2,3}}) == 1;
t6(2) ->
    faBalerteke({{{9,8},7},{6,{5,4}}}) == 9.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 7.  Bináris fa legjobboldalibb levélértékének meghatározása

%% @spec faJobberteke(F::fa()) -> E::level().
%% Az F fa legjobboldalibb levelének értéke E.

faJobberteke({_Bf,Jf}) ->
    faJobberteke(Jf);
faJobberteke(V) ->
    V.
t7(1) ->
    faJobberteke({{1,4},{2,3}}) == 3;
t7(2) ->
    faJobberteke({{{9,8},7},{6,{5,4}}}) == 4.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 8.  Egy lista utolsó elemének meghatározása

%% @spec listaUtolsoEleme(L::egeszlista()) -> E::integer().
%% Az L egészlista utolsó eleme E.

listaUtolsoEleme([E]) ->
    E;
listaUtolsoEleme([_|Xs]) ->
    listaUtolsoEleme(Xs).

t8(1) ->
    listaUtolsoEleme([5,1,2,8,7]) == 7.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 9.  Bináris fa részfái


%% @spec faReszfai(F::fa()) -> Reszfalista::[fa()].
%% Reszfalista az F fa részfáinak listája. A listában a részfák sorrendje
%% tetszőleges, de minden részfa csak egyszer fordulhat elő.
%% Egy fa (nem feltétlenül valódi) részfájának nevezzük saját magát, valamint
%% -- ha a fa egy csomópont -- a bal és a jobb oldali ágának részfáit.

faReszfai(F={Bf,Jf}) ->
    [F|faReszfai(Bf) ++ faReszfai(Jf)];
faReszfai(V) ->
    [V].

%% terminálisan rekurzív verziója, akkumulátorral

faReszfai2({Bf,Jf}=F,Ls) ->
    [F|faReszfai2(Bf,faReszfai2(Jf,Ls))];
faReszfai2(V,Ls) ->
    [V|Ls].

faReszfai2(F) ->
    faReszfai2(F,[]).

t9(1) ->
    faReszfai({1,{2,3}}) == [{1,{2,3}},1,{2,3},2,3];
t9(2) ->
    faReszfai({1,{2,{3,4}}}) == [{1,{2,{3,4}}},1,{2,{3,4}},2,{3,4},3,4];
t9(3) ->
    faReszfai2({1,{2,3}}) == [{1,{2,3}},1,{2,3},2,3];
t9(4) ->
    faReszfai2({1,{2,{3,4}}}) == [{1,{2,{3,4}}},1,{2,{3,4}},2,{3,4},3,4].


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 10. Egy lista szuffixumai

%% @spec listaSzuffixumai(L::egeszlista()) -> Szuffixlista::[egeszlista()].
%% Szuffixlista az L lista szuffixumainak listája. A listában a szuffixumok
%% sorrendje tetszőleges, de minden szuffixum csak egyszer fordulhat elő.
%% Egy n-elemű L lista k-elemű szuffixumának nevezzük azt a listát, amely az
%% L utolsó k elemét tartalmazza az elemek L-beli sorrendjének megtartása
%% mellett (0 =< k =< n).

listaSzuffixumai([]) ->
    [[]];
listaSzuffixumai(XXs=[_X|Xs]) ->
    [XXs|listaSzuffixumai(Xs)].

t10(1) ->
    listaSzuffixumai([1,4,2]) == [[1,4,2],[4,2],[2],[]].


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 11. Bináris fa tükörképe

%% @spec faTukorkepe(F0::fa()) -> F::fa().
%% F az F0 fa tükörképe.

faTukorkepe({Bf,Jf}) ->
    {faTukorkepe(Jf),faTukorkepe(Bf)};
faTukorkepe(V) ->
    V.

t11(1) ->
    faTukorkepe({{1,4},{2,3}}) == {{3,2},{4,1}};
t11(2) ->
    faTukorkepe({{1,4},{4,1}}) == {{1,4},{4,1}};
t11(3) ->
    faTukorkepe({{1,{2,3}},4}) == {4,{{3,2},1}}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 12. Bináris fa tükörszimmetrikus voltának ellenőrzése

%%@spec tukorszimmetrikusFa(F::fa()) -> B::bool().
%% B igaz, ha az F fa tükörszimmetrikus.

tukorszimmetrikusFa(F) ->
    F == faTukorkepe(F).

t12(1) ->
    tukorszimmetrikusFa({{1,4},{4,1}}) == true;
t12(2) ->
    tukorszimmetrikusFa({{1,4},{2,3}}) == false.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 13. Bináris fa leveleiben található értékek listája

%% @spec faLevelertekei(F::fa()) -> Levlista::[level()].
%% Levlista az F fa leveleiben található értékek listája. A listában az elemek
%% sorrendje tetszőleges, de minden elem csak egyszer fordulhat elő.

faLevelertekei({Bf,Jf}) ->
    faLevelertekei(Bf) ++ faLevelertekei(Jf);
faLevelertekei(V) ->
    [V].

t13(1) ->
    faLevelertekei({1,{2,3}}) == [1,2,3];
t13(2) ->
    faLevelertekei({{1,4},{2,3}}) == [1,4,2,3];
t13(3) ->
    faLevelertekei({{1,{2,{3,4}}},5}) == [1,2,3,4,5].


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 14. Bináris fa rendezettsége

%% @spec rendezettFa(F::fa()) -> B::Bool
%% B igaz, ha az F fa rendezett.
%% Egy fát rendezettnek mondunk, ha a fában balról jobbra haladva a
%% levelekben található értékek szigorúan monoton növő sorozatot alkotnak.

%%% A megoldásban célszerű a 6. és a 7. feladat eljárásait segédeljárásként
%%% felhasználni, így nem szükséges további segédeljárást definiálni.

rendezettFa({Bf,Jf}) ->
     faJobberteke(Bf) < faBalerteke(Jf) andalso
	rendezettFa(Bf) andalso rendezettFa(Jf);
rendezettFa(_) ->
    true.

%% Keressen hatékonyabb megoldást is, amelyben a fastruktúrát csak egyszer
%% járja be. Ehhez egy megfelelő segédeljárás szükséges.

rendezettFa2(F) ->
    Ls = fabolLista(F),
   lists:sort(Ls) == Ls.

rendezettFa3({Bf,Jf},BalMin) ->
    {BEred,BJobb} = rendezettFa3(Bf,BalMin),
    {JEred,JJobb} = rendezettFa3(Jf,BJobb),
    {BEred andalso JEred,JJobb};
rendezettFa3(E,BalMin) ->
    {BalMin < E, E}.

rendezettFa3(F) ->
    {Ered, _} = rendezettFa3(F,-999),
    Ered.

t14(1) ->
    rendezettFa({{1,4},{2,3}}) == false;
t14(2) ->
    rendezettFa({{1,3},{5,{6,9}}}) == true;
t14(3) ->
    rendezettFa2({{1,4},{2,3}}) == false;
t14(4) ->
    rendezettFa2({{1,3},{5,{6,9}}}) == true.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 15. Fából lista

%% @spec fabolLista(F::fa()) -> Ls::egeszlista().
%% Az F fa balról jobbra haladva előállított elemeinek listája Ls.

fabolLista({Bf,Jf}) ->
    fabolLista(Bf) ++ fabolLista(Jf);
fabolLista(E) ->
    [E].

fabolLista2({Bf,Jf},Ls) ->
    fabolLista2(Bf,fabolLista2(Jf,Ls));
fabolLista2(E,Ls) ->
    [E|Ls].

fabolLista2(F) ->
    fabolLista2(F,[]).

t15(1) ->
    fabolLista({{1,4},{2,3}});
t15(2) ->
    fabolLista({{1,3},{5,{6,9}}});
t15(3) ->
    fabolLista2({{1,4},{2,3}});
t15(4) ->
    fabolLista2({{1,3},{5,{6,9}}}).