-module('dp13a-gy7').
-compile(export_all).
-author('patai@iit.bme.hu, hanak@iit.bme.hu, kapolnai@iit.bme.hu').
-vsn('$LastChangedDate: 2013-11-06 16:09:56 +0100 (Wed, 06 Nov 2013) $$').

%---------------------------------------------------------------------------
%                           I. RÉSZ: FÁK
%---------------------------------------------------------------------------

% 1.
fa_noveltje(level) ->
    level;
fa_noveltje({C,Bfa,Jfa}) ->
    {C+1, fa_noveltje(Bfa), fa_noveltje(Jfa)}.

% 2.
fa_tukorkepe(level) ->
    level;
fa_tukorkepe({C,Bfa,Jfa}) ->
    {C, fa_tukorkepe(Jfa), fa_tukorkepe(Bfa)}.

% 3. a)
fa_balerteke(level) ->
    error;
fa_balerteke({C,level,_}) ->
    {ok, C};
fa_balerteke({_,Bfa,_}) ->
    fa_balerteke(Bfa).

% 3. b)
fa_jobberteke(level) ->
    error;
fa_jobberteke({C,_,level}) ->
    {ok, C};
fa_jobberteke({_,_,Jfa}) ->
    fa_jobberteke(Jfa).

% 4.
rendezett_fa(level) ->
    true;
rendezett_fa({C,Bfa,Jfa}) ->
    case fa_jobberteke(Bfa) of
        error  -> true;
        {ok,J} -> J < C
    end andalso
        rendezett_fa(Bfa) andalso
    case fa_balerteke(Jfa) of
        error  -> true;
        {ok,B} -> C < B
    end andalso
        rendezett_fa(Jfa).

% 4. kicsit hatékonyabb változatokban a fájl végén, kiegészítő anyag

% 5.
tartalmaz(_, level) ->
    false;
tartalmaz(C, {C,_,_}) ->
    true;
tartalmaz(C, {_,Bfa,Jfa}) ->
    tartalmaz(C, Bfa) orelse tartalmaz(C, Jfa).

% 6.
elofordul(_, level) ->
    0;
elofordul(C, {R,Bfa,Jfa}) ->
    if C =:= R -> 1;
       true    -> 0
    end
        + elofordul(C, Bfa) + elofordul(C, Jfa).

% 7.
utak(Fa) -> utak(Fa, []).

% @spec utak(F::fa(), Eddigi::ut()) -> CimkezettUtak::[{C::term(), U::ut()}].
% A CimkezettUtak lista az F fa minden csomópontjához egy kételemű ennest
% társít, amelynek első eleme (C) a csp. címkéje, második eleme (U) az
% Eddigi útvonal és a csp. útvonala összefűzve.
utak(level, _) ->
    [];
utak({C,Bfa,Jfa}, Eddigi) ->
    Eddigi1 = Eddigi ++ [C], % Költséges művelet!
    [{C, Eddigi} | utak(Bfa, Eddigi1)] ++ utak(Jfa, Eddigi1).

% 8. a)
cutak_a(C, Fa) ->
    [CU || {C0,_} = CU <- utak(Fa), C0 =:= C].

% 8. b)           
cutak_b(C, Fa) -> cutak(C, Fa, []).

% @spec ut(C::term(), F::fa(), Eddigi::ut()) ->
%               CimkezettUtak::[{C::term(), U::ut()}].
% A CimkezettUtak lista az F fa minden C címkéjű csomópontjához egy kételemű
% ennest társít, amelynek első eleme C, második eleme az Eddigi útvonal és
% és a csp. útvonala összefűzve.
cutak(_, level, _) ->
    [];
cutak(C, {R,Bfa,Jfa}, Eddigi) ->
    Eddigi1 = Eddigi ++ [R],
    Cutak = cutak(C, Bfa, Eddigi1) ++ cutak(C, Jfa, Eddigi1),
    if R =:= C -> [{C, Eddigi} | Cutak];
       true    -> Cutak
    end.

% 9.
cimkek(Fa) -> cimkek(Fa, []).

cimkek(level, L) ->
    L;
cimkek({R,Bfa,Jfa}, L) ->
    cimkek(Bfa, [R|cimkek(Jfa, L)]).

% 10.
duplak([]) -> [];
duplak(L) ->
    [ E || {E,E} <- lists:zip(lists:sublist(L, length(L)-1), tl(L)) ].

% 11.
all(Pred, [Hd|Tail]) ->
    case Pred(Hd) of
	true -> all(Pred, Tail);
	false -> false
    end;
all(Pred, []) when is_function(Pred, 1) ->
    true. 

% 12.
transpose([]) ->
    [];
transpose([[] | Matrix]) ->
    transpose(Matrix);
transpose(Matrix) ->
%    [lists:map(fun hd/1, Matrix) | transpose(lists:map(fun tl/1, Matrix))].
    [[H || [H|_] <- Matrix] | transpose([T || [_|T] <- Matrix])].



test(fa) ->
    T1 = {4,
          {3,level,level},
          {6,
           {5,level,level},
           {7,level,level}}},
    T2 = {a,
          {b, {x,level,level}, level},
          {c,
           level,
           {d,
            {x,{e,level,level},level},
            {a, {x,level,level},{x,level,level}}}}},
    T3 = {4,
          {3,
           {2,level,level},
           {1,level,level}},
          {6,
           {5,level,level},
           {7,level,level}}},
%    lists:foldl(fun erlang:'and'/2, true,
    [fa_noveltje(T1) =:= {5,{4,level,level},{7,{6,level,level},{8,level,level}}},
     fa_tukorkepe(T1) =:= {4,{6,{7,level,level},{5,level,level}},{3,level,level}},
     fa_balerteke(T1) =:= {ok, 3},
     fa_balerteke(level) =:= error,
     fa_balerteke(T2) =:= {ok, x},
     fa_jobberteke(T1) =:= {ok, 7},
     rendezett_fa(T1) =:= true,
     rendezett_fa(T2) =:= false,
     rendezett_fa(T3) =:= false,
     tartalmaz(x, T1) =:= false,
     tartalmaz(x, T2) =:= true,
     elofordul(x, T1) =:= 0,
     elofordul(x, T2) =:= 4,
     utak(T1) =:= [{4,[]},{3,[4]},{6,[4]},{5,[4,6]},{7,[4,6]}],
     utak(T2) =:= [{a,[]},{b,[a]},{x,[a,b]},{c,[a]},{d,[a,c]},{x,[a,c,d]},
                   {e,[a,c,d,x]},{a,[a,c,d]},{x,[a,c,d,a]},{x,[a,c,d,a]}],
     cutak_a(x,T1) =:= [],
     cutak_a(x,T2) =:= [{x,[a,b]},{x,[a,c,d]},{x,[a,c,d,a]},{x,[a,c,d,a]}],
     cutak_a(x,T1) =:= cutak_b(x,T1),
     cutak_a(x,T2) =:= cutak_b(x,T2),
     cimkek(T1) =:= [3,4,5,6,7]
    ]
%	       )
        ;


test(lista) ->
    [duplak([1,2,3]) =:= [],
     duplak([1,1,2,3,3,3]) =:= [1,3,3],
     all(fun is_atom/1, [a,b,c]) and not all(fun is_atom/1, [a,b,1]),
     transpose([[a,b],
                [c,d],
                [e,f]]) =:= [[a,c,e],
                             [b,d,f]]
     ].