-module(dp4).
-compile(export_all).

% @spec rampa1(Xs::[any()],Rs::[any()]) -> {Zs::[any()],Ms::[any()]}.
% Zs = Xs első monoton növekvő futama Rs mögé fűzve; Ms = Xs maradéka.
rampa1([], Rs) ->
    {lists:reverse(Rs), []};
rampa1([X], Rs) ->
    {lists:reverse([X|Rs]), []};
rampa1([X1,X2|Xs], Rs) when X1 > X2 ->
    {lists:reverse([X1|Rs]),[X2|Xs]};
rampa1([X|Xs], Rs) ->
    rampa1(Xs, [X|Rs]).

% @spec rampa1(Xs::[any()]) -> {Zs::[any()],Ms::[any()]}.
% Zs = Xs első monoton növekvő futama, Ms = Xs maradéka.
rampa1(L) ->
    rampa1(L, []).

% @spec rampak1(Xs::[any()]) -> Xss::[[any()]].
% Xss = Xs monoton növekvő futamainak listája.
rampak1([]) ->
    [];
rampak1(Xs) ->
    {Rs,Ms} = rampa1(Xs),
    [Rs|rampak1(Ms)].

% dp4:rampak1([1,2,2,3,2,4,5,6,6,6,7,6,8,2,3,3,4,5,6,0,6,5,4,3,2,1]).

% @spec tails(Ls::[any()]) -> Zss::[[any()]].
% Zss = az Xs-ből és egyre rövidülő farkaiból álló lista.
tails([]) ->
    [[]];
tails(L=[_|Ls]) ->
    [L|tails(Ls)].

% dp4:tails([a,b,c,d,1,2,3]).

% @spec rampa2: mint rampa1.
% erőltetett és nagyon nehezen érthető
rampa2(L) ->
    F = fun([X1,X2|_]) -> X1 =< X2; (_) -> false end,
    {R=[E|_],[_|M]} = lists:splitwith(F, tails(L)),
%    {R,M}.
    {[hd(E)|[X || [_,X|_] <- R]],[X || [X|_] <- M]}.

% lists:splitwith(fun erlang:is_atom/1, [a,b,c,d,1,2,3,4,e,f,5,6,7]).

% @spec dif1(Ls::[number()],N::number(),Rs::[number()]) ->
%                                   {Ds::[number()], Zs::[number()]}.
% Ds = az Ls N különbségű számtani sorozatot alkotó prefixuma Rs elé
% fűzve, Zs = Ls maradéka.
dif1([], _, Rs) ->
    {lists:reverse(Rs), []};
dif1([X], _, Rs) ->
    {lists:reverse([X|Rs]), []};
dif1([X1,X2|Xs], N, Rs) when X2-X1 /= N ->
    {lists:reverse([X1|Rs]),[X2|Xs]};
dif1([X|Xs], N, Rs) ->
    dif1(Xs, N, [X|Rs]).

% @spec dif1(Ls::[number()]) -> {Ds::[number()], Zs::[number()]}.
% Ds = Ls számtani sorozatot alkotó prefixuma, Zs = Ls maradéka.
dif1(Ls) ->
    if
	length(Ls) < 2 ->
	    {Ls,[]};
	true ->
	    [X1,X2|_] = Ls,
	    dif1(Ls, X2-X1, [])
    end.

% @spec dif2: mint dif1.
dif2([X1,X2|_]=Ls) ->
    dif1(Ls, X2-X1, []);
dif2(Ls) -> {Ls,[]}.

% @spec difek1(Xs::[number()]) -> Dss::[[number()]].
% Dss = Xs számtani sorozatot alkotó részlistáinak listája.
difek1([]) ->
    [];
difek1(Xs) ->
    {Rs,Ms} = dif1(Xs),
    [Rs|difek1(Ms)].

unfoldr(_F,[]) ->
    [];
unfoldr(F,Xs) ->
    {Rs,Ms} = F(Xs),
    [Rs|unfoldr(F,Ms)].

rampak2(Xs) ->
    unfoldr(fun rampa1/1,Xs).

difek2(Xs) ->
    unfoldr(fun dif2/1,Xs).

% dp4:difek1([1,2,3,4,8,16,32,33,34]).
% dp4:difek1([1,2,3,4,5,6,7,8,16,24,32,33,34]).

% feladat: úgy módosítani dif1-et, hogy ha egy szám az egyik
% számtani sorozat utolsó és egyben a következő első eleme is
% lehet, akkor mindkettőben vegyük figyelembe
% NB. Ilyenkor egy sorozat záróeleme mindenképpen egy következő
% sorozat kezdőeleme is lesz egyben, hiszen már két elem is
% számtani sorozatot alkot.

dif3([], _, Rs) ->
    {lists:reverse(Rs), []};
dif3([X], _, Rs) ->
    {lists:reverse([X|Rs]), []};
dif3([X1,X2|Xs], N, Rs) when X2-X1 /= N ->
    {lists:reverse([X1|Rs]),[X1,X2|Xs]};
dif3([X|Xs], N, Rs) ->
    dif3(Xs, N, [X|Rs]).

% @spec dif3: majdnem mint dif1.
dif3([X1,X2|_]=Ls) ->
    dif3(Ls, X2-X1, []);
dif3(Ls) -> {Ls,[]}.

% dp4:unfoldr(fun dp4:dif3/1,[1,2,3,4,5,6,7,8,16,24,32,33,34]).
% dp4:unfoldr(fun dp4:dif3/1,[1,2,3,4,5,6,7,16,24,32,33,34]).

% @type btree() = e | {n,int(),btree(),btree()}

% @spec nagyobbak0(T::btree(),E::int()) -> Rs::[btree()]
% Rs =  a T keresőfa tulajdonságú fa E-nél nagyobb
%       értéket tartalmazó csomópontjainak listája,
s(e) ->
    [];
s(N={n,_X,L,R}) ->
    s(L) ++ [N] ++ s(R).

nagyobbak0(e,_) ->
    [];
nagyobbak0(T={n,X,L,R},E) when X > E ->
    nagyobbak0(L,E) ++ [T] ++ s(R);
nagyobbak0({n,_X,_L,R},E) ->
    nagyobbak0(R,E).

%                   3
%             2           9
%           1   e       4   6
%          e e         e e e e
%
% dp4:nagyobbak0({n,3,{n,2,{n,1,e,e},e},{n,9,{n,4,e,e},{n,6,e,e}}},2).
% 
%  ->
% 
% [{n,3,{n,2,{n,1,e,e},e},{n,9,{n,4,e,e},{n,6,e,e}}},
%  {n,4,e,e},
%  {n,9,{n,4,e,e},{n,6,e,e}},
%  {n,6,e,e}]

% @spec nagyobbak1(T::btree(), E::int()) -> Rs::[btree()]
% Rs = {V, Bs} párokból álló lista, ahol V a T bináris fa valamely
%      csomópontjában található, E-nél nagyobb érték, Bs pedig a V
%      érték elérési útvonalát a b(alra), illetve j(obbra) atomomokkal
%      jelző lista
nagyobbak1(e,_) ->
    [];
nagyobbak1({n,X,B,J}, E) ->
    Uk = fun() ->
		 [{Y,[b|U]} || {Y,U} <- nagyobbak1(B, E)] ++
		 [{Y,[j|U]} || {Y,U} <- nagyobbak1(J, E)]
	 end,
    if
	X > E ->
	    [{X,[]}|Uk()];
	true ->
	    Uk()
    end.

%                   0
%             1           9
%           3   e       4   6
%          e e         e e e e
%
% dp4:nagyobbak1({n,0,{n,1,{n,3,e,e},e},{n,9,{n,4,e,e},{n,6,e,e}}},2).
% 
%  ->
% 
% [{3,[b,b]},{9,[j]},{4,[j,b]},{6,[j,j]}]

%                   0
%             1             9
%           3   e       4      6
%          e e         e e   7   8
%                           e e e e
%
% dp4:nagyobbak1({n,0,{n,1,{n,3,e,e},e},{n,9,{n,4,e,e},{n,6,{n,7,e,e},{n,8,e,e}}}},2).
% 
%  ->
% 
% [{3,[b,b]},{9,[j]},{4,[j,b]},{6,[j,j]},{7,[j,j,b]},{8,[j,j,j]}]

% @spec nagyobbak2: mint nagyobbak1
nagyobbak2(e,_) ->
    [];
nagyobbak2({n,X,B,J}, E) ->
    Uk = [{Y,[b|U]} || {Y,U} <- nagyobbak2(B, E)] ++
	 [{Y,[j|U]} || {Y,U} <- nagyobbak2(J, E)],
    if
	X > E ->
	    [{X,[]}|Uk];
	true ->
	    Uk
    end.

% dp4:nagyobbak2({n,0,{n,1,{n,3,e,e},e},{n,9,{n,4,e,e},{n,6,e,e}}},2).