-module(rend).
-compile(export_all).

%% ------ Insertion sort

%% @spec ins1(X::any(),Ys::[any()]) -> Zs::[any()]
%% @pre: Ys az =< reláció szerint rendezve van
%%   Zs az =< reláció alapján beszúrt X-szel bővített Ys
ins1(X,[]) ->
    [X];
ins1(X,[Y|Ys]) when X=<Y ->
    [X,Y|Ys];
ins1(X,[Y|Ys]) ->
    [Y|ins1(X,Ys)].

%% @spec inssort11(Xs::[any()]) -> Zs::[any()]
%%   Zs az =< reláció szerint rendezett Ys
inssort11([]) ->
    [];
inssort11([X|Xs]) ->
    ins1(X,inssort11(Xs)).

%% ------ Generic insertion sort

%% @spec inssort12(F:pred(),Xs::[any()]) -> Zs::[any()]
%% @type ins() = (any(),[any()]) -> [any()]
%%   Zs az F beszúró függvénnyel az =<
%%   reláció szerint rendezett Ys
inssort12(_F,[]) ->
    [];
inssort12(F,[X|Xs]) ->
    F(X,inssort12(F,Xs)).

ti11()->
    rend:inssort11([9,7,8,3,1,5]).
ti12()->
    rend:inssort12(fun(A,Ls)->ins1(A,Ls) end,[9,7,8,3,1,5]).

%% @spec ins2(F::pred(),X::any(),Ys::[any()]) -> Zs::[any()]
%% @type pred() = (any(), any()) -> bool()
%% @pre Ys az =< reláció szerint rendezve van
%%   Zs az F reláció alapján beszúrt X-szel bővített Ys
ins2(_F,X,[]) ->
    [X];
ins2(F,X,[Y|Ys]) ->
    case F(X,Y) of
        true ->
            [X,Y|Ys];
        false ->
            [Y|ins2(F,X,Ys)]
    end.

%% @spec inssort2*(F:pred(),Xs::[any()]) -> Zs::[any()]
%% @type pred() = (any(), any()) -> bool()
%%   Zs az F reláció szerint rendezett Ys
inssort21(_F,[]) ->
    [];
inssort21(F,[X|Xs]) ->
    ins2(F,X,inssort21(F,Xs)).

inssort22(F,Xs) ->
    inssort22(F,Xs,[]).

inssort22(_F,[],Zs) ->
    Zs;
inssort22(F,[X|Xs],Zs) ->
    inssort22(F,Xs,ins2(F,X,Zs)).

ti21()->
    rend:inssort21(fun(A,B)->A=<B end,[9,7,8,3,1,5]).
ti22()->
    rend:inssort22(fun(A,B)->A>=B end,[9,7,8,3,1,5]).

inssortR(F,Xs) ->
    lists:foldr(fun(A,Ls) -> ins2(F,A,Ls) end,[],Xs).

inssortL(F,Xs) ->
    lists:foldl(fun(A,Ls) -> ins2(F,A,Ls) end,[],Xs).

ti31()->
    rend:inssortR(fun(A,B)->A<B end,[9,7,8,3,1,5]).
ti32()->
    rend:inssortR(fun(A,B)->A>=B end,[9,7,8,3,1,5]).

ti33()->
    rend:inssort21(fun(A,B)->A=<B end,[4.24, 4.1, 5.67, 1.12, 4.1, 0.33, 8.0]).
ti34()->
    rend:inssort22(fun(A,B)->A>=B end,[4, 4, 5, 1, 0, 8]).
ti35()->
    rend:inssort22(fun(A,B)->A<B end,"qwer").
ti36()->
    rend:inssortR(fun(A,B)->A>=B end,[4, 4, 5, 1, 0, 8]).
ti37()->
    rend:inssortL(fun(A,B)->A=<B end,[4.24, 4.1, 5.67, 1.12, 4.1, 0.33, 8.0]).

%% ------ Generic selection sort

%% @spec selsort(F:pred(),Xs::[any()]) -> Zs::[any()]
%% @type pred() = (any(), any()) -> bool()
%%   Zs az F reláció szerint rendezett Xs
selsort(F,Xs) ->
    ssort(F,Xs,[]).

%% @spec ssort(F::pred(),Xs::[any()],Ys::[any()]) -> Zs::[any()]
%% @type pred() = (any(), any()) -> bool()
%%   Zs az F szerinti sorrendben az Ys elé fűzött Xs
ssort(_F,[],Ws) ->
    Ws;
ssort(F,[X|Xs],Ws) ->
    {M,Ms} = maxSelect(F,X,Xs,[]),
    ssort(F,Ms,[M|Ws]).

%% @spec maxSelect(F::pred(),X::any(),Ys::[any()],
%%                   Zs::[any()]) -> {M::any,Ms::[any()]}
%% @type pred() = (any(), any()) -> bool()
%%   M az [X|Ys] lista F szerinti legnagyobb eleme,
%%   Ms az [X|Ys] többi eleméből és a Zs elemeiből álló lista
maxSelect(_F,X,[],Zs) ->
    {X,Zs};
maxSelect(F,X,[Y|Ys],Zs) ->
    maxSelect(F,max(F,X,Y),Ys,[min(F,X,Y)|Zs]).

max(F,X,Y) ->
    case F(X,Y) of
        true ->
            X;
        false ->
            Y
    end.

min(F,X,Y) ->
    case F(X,Y) of
        true ->
            Y;
        false ->
            X
    end.

ts1() ->
    rend:selsort(fun(A,B) -> A=<B end,[1,2,3,4,5,6,7,8,9]).
ts2() ->
    rend:selsort(fun(A,B) -> A=<B end,[9,8,7,6,5,4,3,2,1]).
ts3() ->
    rend:selsort(fun(A,B) -> A=<B end,[4.5,6.7,3.6,4.3,1.2,0.9,8.9,9.8,2.0]).
ts4() ->
    rend:selsort(fun(A,B) -> A=<B end,"Ej mi a ko tyukanyo").

%% ------ Quicksort

%% @spec qsort*(Xs::[any()]) -> Zs::[any()]
%% @type pred() = (any(), any()) -> bool()
%%   Zs az =< reláció szerint rendezett Xs
qsort1([]) ->
    [];
qsort1([X|Xs]) ->
    Ls = [E || E <- Xs, E=<X],
    Rs = [E || E <- Xs, E>X],
    qsort1(Ls) ++ [X] ++ qsort1(Rs).

qsort2([]) ->
    [];
qsort2([X|Xs]) ->
    Ls = [E || E <- Xs, E<X],
    Ms = [E || E <- Xs, E==X],
    Rs = [E || E <- Xs, E>X],
    qsort2(Ls) ++ [X|Ms] ++ qsort2(Rs).

qsort3(Xs) ->
    qsort3(Xs,[]).

%% @spec qsort*(Xs::[any()],Zs::[any()]) -> Ws::[any()]
%% @type pred() = (any(), any()) -> bool()
%%   Ws az =< reláció szerint rendezett Xs a Zs elé fűzve
qsort3([],Zs) ->
    Zs;
qsort3([X|Xs],Zs) ->
    Ls = [E || E <- Xs, E<X],
    Ms = [E || E <- Xs, E==X],
    Rs = [E || E <- Xs, E>X],
    qsort3(Ls,[X|Ms++qsort3(Rs,Zs)]).

%% ------ Generic quicksort

%% @spec qsort*(F:pred(),Xs::[any()],Zs::[any()]) -> Ws::[any()]
%% @type pred() = (any(), any()) -> bool()
%%   Ws az F reláció szerint rendezett Ys a Zs elé fűzve
gqsort2(_F,[]) ->
    [];
gqsort2(F,[X|Xs]) ->
    Ls = [E || E <- Xs, F(E,X)],
    Ms = [E || E <- Xs, E==X],
    Rs = [E || E <- Xs, F(X,E)],
    gqsort2(F,Ls) ++ [X|Ms] ++ gqsort2(F,Rs).

gqsort3(F,Xs) ->
    gqsort3(F,Xs,[]).

gqsort3(_F,[],Zs) ->
    Zs;
gqsort3(F,[X|Xs],Zs) ->
    Ls = [E || E <- Xs, F(E,X)],
    Ms = [E || E <- Xs, E==X],
    Rs = [E || E <- Xs, F(X,E)],
    gqsort3(F,Ls,[X|Ms++gqsort3(F,Rs,Zs)]).

tq1() ->
    rend:qsort1("abrakadabra").
tq2() ->
    rend:qsort2("abrakadabra").
tq3() ->
    rend:qsort3("abrakadabra").
tq4() ->
    rend:gqsort2(fun(A,B) -> A<B end,"abrakadabra").
tq5() ->
    rend:gqsort3(fun(A,B) -> A<B end,"abrakadabra").

%% ------ Top-down mergesort

%% @spec merge(Xs::[any()],Ys::[any()]) -> Zs::[any()]
%%   az Xs és az Ys <= reláció szerinti összefésülése Zs
merge([],Ys) ->
    Ys;
merge(Xs,[]) ->
    Xs;
merge([X|Xs]=XXs,[Y|Ys]=YYs) ->
    if
        X=<Y  ->
            [X|merge(Xs,YYs)];
        true ->
            [Y|merge(XXs,Ys)]
    end.

%% @spec tmsort(Xs::[any()]) -> Zs::[any()]
%%   Zs az =< reláció szerint rendezett Ys
tmsort(Xs) ->
    H = length(Xs),
    K = H div 2,
    if
        H>1 ->
            merge(tmsort(take(Xs,K)),tmsort(drop(Xs,K)));
        true ->
            Xs
    end.

take(Xs,K) ->
    lists:sublist(Xs,K).

drop(Xs,K) ->
    lists:nthtail(K,Xs).

%% ------ Bottom-up mergesort

%% @spec bmsort(Xs::[any()]) -> Zs::[any()]
%%   Zs az =< reláció szerint rendezett Ys
bmsort(Xs) ->
    sorting(Xs,[],0).

%% @spec sorting(Xs::[any()),Lss::[[any()]],K) -> Zs::[any()]
%% @pre K>=0
%%   Zs a még rendezetlen Xs és a már rendezett részlistákból
%%   álló, K db listát tartalmazó Lss összefűzésének az eredménye
sorting([X|Xs],Lss,K) ->
    sorting(Xs,mergepairs([[X]|Lss],K+1),K+1);
sorting([],Lss,_K) ->
    hd(mergepairs(Lss,0)).

%% @spec mergepairs(Lss::[[any()]],K) -> Zss::[[any()]]
%% @pre K>=0
%%   Zs Lss-nek olyan változata, amely az Lss első két
%%   részlistája helyett, ha egyforma a hosszuk, az
%%   összefuttatásuk eredményét tartalmazza
mergepairs(LLLss=[L1s,L2s|Lss],K) ->
    %% legalább kételemű a lista
    if K rem 2 == 1 ->
            LLLss;
       true ->
            mergepairs([merge(L1s,L2s)|Lss],K div 2)
    end;
mergepairs(Lss,_K) ->
                  Lss. % egyelemű a lista

%% ------ Smoothsort

%% @spec nextrun(Run::[any()],Xs::[any()]) ->
%%         {Rs::[any()],Ms::[any()]}
%%   Rs az Xs egy, a < reláció szerint növekvő futama
%%   Run elé fűzve, Ms pedig az Xs maradéka
nextrun(Run,[X|Xs]) ->
    if X < hd(Run) ->
            {lists:reverse(Run),[X|Xs]};
       true ->
            nextrun([X|Run],Xs)
    end;
nextrun(Run,[]) ->
    {lists:reverse(Run),[]}.

%% @spec smsorting(Xs::[any()),Lss::[[any()]],K) -> Zs::[any()]
%% @pre K>=0
%%   Zs a még rendezetlen Xs és a már K rendezett
%%   részlistát tartalmazó Lss összefűzésének eredménye
smsorting([X|Xs],Lss,K) ->
    {Run,Tail} = nextrun([X],Xs),
    smsorting(Tail,mergepairs([Run|Lss],K+1),K+2);
smsorting([],Lss,_K) ->
    hd(mergepairs(Lss,0)).

%% @spec smsort(Xs::[any()]) -> Zs::[any()]
%%   Zs az =< reláció szerint rendezett Ys
smsort(Xs) ->
    smsorting(Xs,[],0).

tm1() ->
    rend:tmsort("abrakadabra").
tm2() ->
    rend:bmsort("abrakadabra").
tm3() ->
    rend:smsort("abrakadabra").

%% ------ Generic top-down mergesort
%%

tmsort(F,Xs) ->
    H = length(Xs),
    K = H div 2,
    if
        H>1 ->
            lists:merge(F,tmsort(F,take(Xs,K)),tmsort(F,drop(Xs,K)));
        true ->
            Xs
    end.

%% ------ Generic bottom-up mergesort
%%

bmsort(F,Xs) ->
    sorting(F,Xs,[],0).

sorting(F,[X|Xs],Lss,K) ->
    sorting(F,Xs,mergepairs(F,[[X]|Lss],K+1),K+1);
sorting(F,[],Lss,_K) ->
    hd(mergepairs(F,Lss,0)).

mergepairs(F,LLLss=[L1s,L2s|Lss],K) ->
    %% legalább kételemű a lista
    if K rem 2 == 1 ->
            LLLss;
       true ->
            mergepairs(F,[lists:merge(F,L1s,L2s)|Lss],K div 2)
    end;
mergepairs(_F,Lss,_K) ->
    Lss. % egyelemű a lista

%% ------ Generic smoothsort
%%

nextrun(F,Run,[X|Xs]) ->
    %%! if F(X,hd(Run)) ->
    case F(X,hd(Run)) of
        true->
            {lists:reverse(Run),[X|Xs]};
        false ->
            nextrun(F,[X|Run],Xs)
    end;
nextrun(_F,Run,[]) ->
    {lists:reverse(Run),[]}.

smsorting(F,[X|Xs],Lss,K) ->
    {Run,Tail} = nextrun(F,[X],Xs),
    smsorting(F,Tail,mergepairs(F,[Run|Lss],K+1),K+2);
smsorting(F,[],Lss,_K) ->
    hd(mergepairs(F,Lss,0)).

smsort(F,Xs) ->
    smsorting(F,Xs,[],0).

tgm11() ->
    rend:tmsort(fun(A,B) -> A<B end,"abrakadabra").
tgm12() ->
    rend:tmsort(fun(A,B) -> A>B end,"abrakadabra").
tgm21() ->
    rend:bmsort(fun(A,B) -> A<B end,"abrakadabra").
tgm22() ->
    rend:bmsort(fun(A,B) -> A>B end,"abrakadabra").
tgm31() ->
    rend:smsort(fun(A,B) -> A<B end,"abrakadabra").
tgm32() ->
    rend:smsort(fun(A,B) -> A>B end,"abrakadabra").

%% ------ Futási idők mérése
%%

randlist(N,Max) ->
    randlist(N,Max,[]).

randlist(0,_Max,Zs) ->
    Zs;
randlist(N,Max,Zs) ->
    randlist(N-1,Max,[random:uniform(Max)|Zs]).

randlist(N) ->
    randlist(N,1000000).

runlist(0,_Max,Zs) ->
    Zs;
runlist(N,Max,Zs) ->
    runlist(N-1,Max,lists:seq(1,random:uniform(Max))++Zs).

runlist(N) ->
    runlist(N,100,[]).

runtime(S,F,Xs) ->
    T1 = now(),
    F(Xs),
    T2 = now(),
    T = timer:now_diff(T2,T1),
    io:fwrite("~w. Length: ~w, time: ~w ms~n",[S,length(Xs),T div 1000]).

measure() ->
    R3000 = randlist(3000),
    Rr70  = runlist(70),
    _R10000 = randlist(10000),
    _R20000 = randlist(20000),
    Lt = fun(A,B) -> A =< B end,
    Gt = fun erlang:'>='/2,
    runtime(inssort11,fun inssort11/1,R3000),
    runtime(inssort12,fun(Xs) -> inssort12(fun ins1/2, Xs) end,R3000),
    runtime(inssort21,fun(Xs) -> inssort21(Lt, Xs) end,R3000),
    runtime(inssort22,fun(Xs) -> inssort22(Gt, Xs) end,R3000),
    runtime(inssortR,fun(Xs)  -> inssortR(Lt, Xs) end,R3000),
    runtime(inssortL,fun(Xs)  -> inssortL(Lt, Xs) end,R3000),
    runtime(selsort,fun(Xs)   -> selsort(Lt, Xs) end,R3000),
    runtime(qsort1,fun(Xs)    -> qsort1(Xs) end,R3000),
    runtime(qsort2,fun(Xs)    -> qsort2(Xs) end,R3000),
    runtime(qsort3,fun(Xs)    -> qsort3(Xs) end,R3000),
    runtime(gqsort2,fun(Xs)   -> gqsort2(Lt,Xs) end,R3000),
    runtime(gqsort3,fun(Xs)   -> gqsort3(Lt,Xs) end,R3000),
    runtime(tmsort,fun(Xs)    -> tmsort(Xs) end,R3000),
    runtime(bmsort,fun(Xs)    -> bmsort(Xs) end,R3000),
    runtime(smsort,fun(Xs)    -> smsort(Xs) end,R3000),
    runtime(smsort,fun(Xs)    -> smsort(Xs) end,Rr70),
    runtime(gtmsort,fun(Xs)   -> tmsort(Lt,Xs) end,R3000),
    runtime(gbmsort,fun(Xs)   -> bmsort(Lt,Xs) end,R3000),
    runtime(gsmsort,fun(Xs)   -> smsort(Lt,Xs) end,R3000),
    runtime(gsmsort,fun(Xs)   -> smsort(Lt,Xs) end,Rr70),
    runtime('lists:sort/1',fun lists:sort/1,R3000),
    runtime('lists:sort/2',fun(Xs) -> lists:sort(Lt,Xs) end,R3000),
    runtime('lists:usort/1',fun lists:usort/1,R3000),
    runtime('lists:usort/2',fun(Xs) -> lists:usort(Lt,Xs) end,R3000).