-module(test).
-compile(export_all).
%% API

-compile({inline, [  insert/2
                   , merge/2
                  ]}).

insert(E, []) -> [E];
insert(E, [E2|_] = H) when E =< E2 -> [E, H];
insert(E, [E2|H]) -> [E2, [E]|H].

merge(H1, []) -> H1;
merge([E1|H1], [E2|_]=H2) when E1 =< E2 -> [E1, H2|H1];
merge(H1, [E2|H2]) -> [E2, H1|H2].

merge_pairs([]) -> [];
merge_pairs([H]) -> H;
merge_pairs([A, B|T]) -> merge(merge(A, B), merge_pairs(T)).

run_pheap(List, Num) ->
    run_pheap(List, Num, []).

run_pheap(List, 0, Heap) ->
    pheap_full(List, Heap);
run_pheap([], 0, Heap) ->
    finish(Heap, []);
run_pheap([{Y, X, _} = H|T], N, Heap) ->
    run_pheap(T, N-1, insert({{X, Y}, H}, Heap)).

pheap_full([], Heap) ->
    finish(Heap, []);
pheap_full([{Y, X, _} = H|T], [{K, _}|HeapT] = Heap) ->
    case {X, Y} of
        N when N > K ->
            pheap_full(T, insert({N, H}, merge_pairs(HeapT)));
        _ ->
            pheap_full(T, Heap)
    end.

finish([], Acc) -> Acc;
finish([{_, H}|T], Acc) ->
    finish(merge_pairs(T), [H|Acc]).

run_all_sorted_sublist(List, Num) ->
    L = [ {{X, Y}, Z} || {Y, X, _} = Z <- List],
    [ X || {_, X} <- lists:sublist(lists:reverse(lists:sort(L)), Num) ].

run_gb_trees(List, Num) ->
    run_gb_trees(List, Num, gb_trees:empty()).

run_gb_trees([], _Num, Acc) ->
  lists:foldl(fun({Key1, Key2, Key3}, Sum) -> [{Key2, Key1, Key3}|Sum] end, [], gb_trees:keys(Acc));
run_gb_trees([{Key1, Key2, Key3}|List], Num, Acc) ->
    NewKey = {Key2, Key1, Key3},
    NewAcc =
        case gb_trees:size(Acc) < Num of
            true ->
                gb_trees:insert(NewKey, 0, Acc);
            false ->
                {Smallest,_} = gb_trees:smallest(Acc),
                case Smallest < NewKey of
                    true ->
                        Acc2 = gb_trees:delete(Smallest, Acc),
                        gb_trees:insert(NewKey, 0, Acc2);
                    false ->
                        Acc
                end
        end,
    run_gb_trees(List, Num, NewAcc).

run_ordered_set_ets(List, Num) ->
    run_ordered_set_ets(List, Num,
                        {0, ets:new(t, [ordered_set, public, {keypos, 2}])}).

run_ordered_set_ets([], _Num, {_, Table}) ->
    R = lists:reverse(ets:tab2list(Table)),
    ets:delete(Table),
    R;
run_ordered_set_ets([{_, K, _} = H | T], Num, {I, Table}) ->
    case I < Num of
        true ->
            ets:insert(Table, H);
        false ->
            SmallestK = ets:first(Table),
            case K > SmallestK of
                true ->
                    ets:delete(Table, SmallestK),
                    ets:insert(Table, H);
                false ->
                    ok
            end
    end,
    run_ordered_set_ets(T, Num, {I + 1, Table}).

run_small_to_big_order_list(List, Num) ->
    run_small_to_big_order_list(List, Num, 0, []).

run_small_to_big_order_list([], _Num, _, Acc) ->
    lists:foldl(fun({Key1, Key2, Key3}, Sum) -> [{Key2, Key1, Key3}|Sum] end, [], Acc);
run_small_to_big_order_list([{Key1, Key2, Key3}|List], Num, Len, Acc) ->
    NewKey = {Key2, Key1, Key3},
    {NewLen, NewAcc} =
        case Len < Num of
            true ->
                {Len + 1, lists:sort([NewKey|Acc])};
            false ->
                [Smallest|Acc2] = Acc,
                case Smallest < NewKey of
                    true ->
                        {Len, lists:sort([NewKey|Acc2])};
                    false ->
                        {Len, Acc}
                end
        end,
    run_small_to_big_order_list(List, Num, NewLen, NewAcc).

run_small_to_big_order_list_v2(List, Num) ->
    run_small_to_big_order_list_v2(List, Num, fun({X2, X1, _}, {Y2, Y1, _})
                                                  -> {X1, X2} =< {Y1, Y2} end, 0, []).

run_small_to_big_order_list_v2([], _, _, _, Acc) ->
    lists:reverse(Acc);
run_small_to_big_order_list_v2([NewKey|List], Num, Fun, Len, Acc) ->
    {NewLen, NewAcc} =
        if Len < Num -> {Len + 1, insert(NewKey, Acc, Fun)};
           true ->
                [Smallest|Acc2] = Acc,
                case Fun(Smallest,NewKey) of
                    true -> {Len, insert(NewKey, Acc2, Fun)};
                    false -> {Len, Acc}
                end
        end,
    run_small_to_big_order_list_v2(List, Num, Fun, NewLen, NewAcc).

insert(K, [], _) -> [K];
insert(K, [H|T], Fun) ->
    case Fun(K, H) of
        true -> [K, H|T];
        false -> [H|insert(K, T, Fun)]
    end.

run_big_to_small_order_list(List, Num) ->
    run_big_to_small_order_list(List, Num, 0, []).

run_big_to_small_order_list([], _Num, _, Acc) ->
    Acc;
run_big_to_small_order_list([Key|List], Num, Len, Acc) ->
    {NewLen, NewAcc} =
        case Len < Num of
            true ->
                {Len + 1, lists:sort(fun({X2, X1, _}, {Y2, Y1, _}) -> {X1, X2} > {Y1, Y2} end, [Key|Acc])};
            false ->
                Smallest = lists:last(Acc),
                case Smallest < Key of
                    true ->
                        Acc2 = lists:sublist(Acc, Len - 1),
                        {Len, lists:sort(fun({X2, X1, _}, {Y2, Y1, _}) -> {X1, X2} > {Y1, Y2} end, [Key|Acc2])};
                    false ->
                        {Len, Acc}
                end
        end,
    run_big_to_small_order_list(List, Num, NewLen, NewAcc).

test() ->
    [ test(TotalNum, TopNum)
     || TotalNum <- [5000, 10000, 15000, 20000, 25000],
        TopNum   <- [20, 30, 40, 50, 60, 70]].

test_big() ->
    [ test(TotalNum, TopNum)
     || TotalNum <- [25000],
        TopNum   <- [100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200]].

%% Test
test(TotalNum, TopNum) ->
    List = prepared_random_list(TotalNum),
    %io:format("~p~n", [List]),
    Self = self(),
    L = lists:keysort(2,
          [ receive {Pid, X} -> X end
          || {F, Type} <-
             [{run_all_sorted_sublist,         all_sorted_sublist________},
              {run_gb_trees,                   gb_tree___________________},
              {run_small_to_big_order_list,    small_to_big_order_list___},
              {run_big_to_small_order_list,    big_to_small_order_list___},
              {run_small_to_big_order_list_v2, small_to_big_order_list_v2},
              {run_pheap,                      pheap_____________________},
              {run_ordered_set_ets,            ordered_set_ets___________}],
          Pid <- [spawn_link(fun() ->
                                     {Time, Result} = timer:tc(?MODULE, F, [List, TopNum]),
                                     Self ! {self(), {Type, Time, Result}}
                             end)]
          ]),
    [{_, Time1, _}|_] = L,
    [_] = lists:ukeysort(3, L),
    {{TotalNum, TopNum}, [{Type,  Time, Time/Time1*100}
                          || {Type,  Time, _} <- L]}.

prepared_random_list(TotalNum) ->
    [ {X, X+1, X+2}
      || {_, X} <- lists:sort(
                     [ {rand:uniform(), X}
                       || X <- lists:seq(1, TotalNum) ])
    ].