%%% -*- erlang-indent-level: 2 -*-
%%%-------------------------------------------------------------------
%%% Author: Kostis Sagonas
%%%
%%% A test for list handling created using the 'random' module.
%%%-------------------------------------------------------------------
-module(basic_random).
-export([test/0]).
%% It can be used as a benchmark by playing with the following defines
-define(N, 1000).
-define(Iter, 500).
test() ->
ok = random(?N).
random(N) ->
random(N, ?Iter).
random(N, Iter) ->
random:seed(1, 2, 3),
t(ranlist(N, [], N*100), Iter).
ranlist(0, L, _N) -> L;
ranlist(N, L, N0) -> ranlist(N-1, [random:uniform(N0)+300 | L], N0).
t(_, 0) -> ok;
t(L, Iter) ->
%% io:format("Sort starting~n"),
sort(L),
t(L, Iter-1).
sort([X, Y | L]) when X =< Y ->
split_1(X, Y, L, [], []);
sort([X, Y | L]) ->
split_2(X, Y, L, [], []);
sort(L) ->
L.
%% Ascending.
split_1(X, Y, [Z | L], R, Rs) when Z >= Y ->
split_1(Y, Z, L, [X | R], Rs);
split_1(X, Y, [Z | L], R, Rs) when Z >= X ->
split_1(Z, Y, L, [X | R], Rs);
split_1(X, Y, [Z | L], [], Rs) ->
split_1(X, Y, L, [Z], Rs);
split_1(X, Y, [Z | L], R, Rs) ->
split_1_1(X, Y, L, R, Rs, Z);
split_1(X, Y, [], R, Rs) ->
rmergel([[Y, X | R] | Rs], []).
%% One out-of-order element, S.
split_1_1(X, Y, [Z | L], R, Rs, S) when Z >= Y ->
split_1_1(Y, Z, L, [X | R], Rs, S);
split_1_1(X, Y, [Z | L], R, Rs, S) when Z >= X ->
split_1_1(Z, Y, L, [X | R], Rs, S);
split_1_1(X, Y, [Z | L], R, Rs, S) when S =< Z ->
split_1(S, Z, L, [], [[Y, X | R] | Rs]);
split_1_1(X, Y, [Z | L], R, Rs, S) ->
split_1(Z, S, L, [], [[Y, X | R] | Rs]);
split_1_1(X, Y, [], R, Rs, S) ->
rmergel([[S], [Y, X | R] | Rs], []).
%% Descending.
split_2(X, Y, [Z | L], R, Rs) when Z =< Y ->
split_2(Y, Z, L, [X | R], Rs);
split_2(X, Y, [Z | L], R, Rs) when Z =< X ->
split_2(Z, Y, L, [X | R], Rs);
split_2(X, Y, [Z | L], [], Rs) ->
split_2(X, Y, L, [Z], Rs);
split_2(X, Y, [Z | L], R, Rs) ->
split_2_1(X, Y, L, R, Rs, Z);
split_2(X, Y, [], R, Rs) ->
mergel([[Y, X | R] | Rs], []).
split_2_1(X, Y, [Z | L], R, Rs, S) when Z =< Y ->
split_2_1(Y, Z, L, [X | R], Rs, S);
split_2_1(X, Y, [Z | L], R, Rs, S) when Z =< X ->
split_2_1(Z, Y, L, [X | R], Rs, S);
split_2_1(X, Y, [Z | L], R, Rs, S) when S > Z ->
split_2(S, Z, L, [], [[Y, X | R] | Rs]);
split_2_1(X, Y, [Z | L], R, Rs, S) ->
split_2(Z, S, L, [], [[Y, X | R] | Rs]);
split_2_1(X, Y, [], R, Rs, S) ->
mergel([[S], [Y, X | R] | Rs], []).
mergel([[] | L], Acc) ->
mergel(L, Acc);
mergel([A, [H2 | T2], [H3 | T3] | L], Acc) ->
mergel(L, [merge3_1(A, [], H2, T2, H3, T3) | Acc]);
mergel([A, [H | T]], Acc) ->
rmergel([merge2_1(A, H, T, []) | Acc], []);
mergel([L], []) ->
L;
mergel([L], Acc) ->
rmergel([lists:reverse(L, []) | Acc], []);
mergel([], []) ->
[];
mergel([], Acc) ->
rmergel(Acc, []);
mergel([A, [] | L], Acc) ->
mergel([A | L], Acc);
mergel([A, B, [] | L], Acc) ->
mergel([A, B | L], Acc).
rmergel([A, [H2 | T2], [H3 | T3] | L], Acc) ->
rmergel(L, [rmerge3_1(A, [], H2, T2, H3, T3) | Acc]);
rmergel([A, [H | T]], Acc) ->
mergel([rmerge2_1(A, H, T, []) | Acc], []);
rmergel([L], Acc) ->
mergel([lists:reverse(L, []) | Acc], []);
rmergel([], Acc) ->
mergel(Acc, []).
%% Take L1 apart.
merge3_1([H1 | T1], M, H2, T2, H3, T3) when H1 =< H2 ->
merge3_12(T1, H1, H2, T2, H3, T3, M);
merge3_1([H1 | T1], M, H2, T2, H3, T3) ->
merge3_21(T1, H1, H2, T2, H3, T3, M);
merge3_1(_nil, M, H2, T2, H3, T3) when H2 =< H3 ->
merge2_1(T2, H3, T3, [H2 | M]);
merge3_1(_nil, M, H2, T2, H3, T3) ->
merge2_1(T3, H2, T2, [H3 | M]).
%% Take L2 apart.
merge3_2(T1, H1, M, [H2 | T2], H3, T3) when H1 =< H2 ->
merge3_12(T1, H1, H2, T2, H3, T3, M);
merge3_2(T1, H1, M, [H2 | T2], H3, T3) ->
merge3_21(T1, H1, H2, T2, H3, T3, M);
merge3_2(T1, H1, M, _nil, H3, T3) when H1 =< H3 ->
merge2_1(T1, H3, T3, [H1 | M]);
merge3_2(T1, H1, M, _nil, H3, T3) ->
merge2_1(T3, H1, T1, [H3 | M]).
%% H1 <= H2. Inlined.
merge3_12(T1, H1, H2, T2, H3, T3, M) when H3 < H1 ->
merge3_12_3(T1, H1, H2, T2, [H3 | M], T3);
merge3_12(T1, H1, H2, T2, H3, T3, M) ->
merge3_1(T1, [H1 | M], H2, T2, H3, T3).
%% H1 <= H2, take L3 apart.
merge3_12_3(T1, H1, H2, T2, M, [H3 | T3]) when H3 < H1 ->
merge3_12_3(T1, H1, H2, T2, [H3 | M], T3);
merge3_12_3(T1, H1, H2, T2, M, [H3 | T3]) ->
merge3_1(T1, [H1 | M], H2, T2, H3, T3);
merge3_12_3(T1, H1, H2, T2, M, _nil) ->
merge2_1(T1, H2, T2, [H1 | M]).
%% H1 > H2. Inlined.
merge3_21(T1, H1, H2, T2, H3, T3, M) when H3 < H2 ->
merge3_21_3(T1, H1, H2, T2, [H3 | M], T3);
merge3_21(T1, H1, H2, T2, H3, T3, M) ->
merge3_2(T1, H1, [H2 | M], T2, H3, T3).
%% H1 > H2, take L3 apart.
merge3_21_3(T1, H1, H2, T2, M, [H3 | T3]) when H3 < H2 ->
merge3_21_3(T1, H1, H2, T2, [H3 | M], T3);
merge3_21_3(T1, H1, H2, T2, M, [H3 | T3]) ->
merge3_2(T1, H1, [H2 | M], T2, H3, T3);
merge3_21_3(T1, H1, H2, T2, M, _nil) ->
merge2_1(T2, H1, T1, [H2 | M]).
%% Take L1 apart.
rmerge3_1([H1 | T1], M, H2, T2, H3, T3) when H1 > H2 ->
rmerge3_12(T1, H1, H2, T2, H3, T3, M);
rmerge3_1([H1 | T1], M, H2, T2, H3, T3) ->
rmerge3_21(T1, H1, H2, T2, H3, T3, M);
rmerge3_1(_nil, M, H2, T2, H3, T3) when H2 > H3 ->
rmerge2_1(T2, H3, T3, [H2 | M]);
rmerge3_1(_nil, M, H2, T2, H3, T3) ->
rmerge2_1(T3, H2, T2, [H3 | M]).
%% Take L2 apart.
rmerge3_2(T1, H1, M, [H2 | T2], H3, T3) when H1 > H2 ->
rmerge3_12(T1, H1, H2, T2, H3, T3, M);
rmerge3_2(T1, H1, M, [H2 | T2], H3, T3) ->
rmerge3_21(T1, H1, H2, T2, H3, T3, M);
rmerge3_2(T1, H1, M, _nil, H3, T3) when H1 > H3 ->
rmerge2_1(T1, H3, T3, [H1 | M]);
rmerge3_2(T1, H1, M, _nil, H3, T3) ->
rmerge2_1(T3, H1, T1, [H3 | M]).
%% H1 > H2. Inlined.
rmerge3_12(T1, H1, H2, T2, H3, T3, M) when H3 >= H1 ->
rmerge3_12_3(T1, H1, H2, T2, [H3 | M], T3);
rmerge3_12(T1, H1, H2, T2, H3, T3, M) ->
rmerge3_1(T1, [H1 | M], H2, T2, H3, T3).
%% H1 > H2, take L3 apart.
rmerge3_12_3(T1, H1, H2, T2, M, [H3 | T3]) when H3 >= H1 ->
rmerge3_12_3(T1, H1, H2, T2, [H3 | M], T3);
rmerge3_12_3(T1, H1, H2, T2, M, [H3 | T3]) ->
rmerge3_1(T1, [H1 | M], H2, T2, H3, T3);
rmerge3_12_3(T1, H1, H2, T2, M, _nil) ->
rmerge2_1(T1, H2, T2, [H1 | M]).
%% H1 =< H2. Inlined.
rmerge3_21(T1, H1, H2, T2, H3, T3, M) when H3 >= H2 ->
rmerge3_21_3(T1, H1, H2, T2, [H3 | M], T3);
rmerge3_21(T1, H1, H2, T2, H3, T3, M) ->
rmerge3_2(T1, H1, [H2 | M], T2, H3, T3).
%% H1 =< H2, take L3 apart.
rmerge3_21_3(T1, H1, H2, T2, M, [H3 | T3]) when H3 >= H2 ->
rmerge3_21_3(T1, H1, H2, T2, [H3 | M], T3);
rmerge3_21_3(T1, H1, H2, T2, M, [H3 | T3]) ->
rmerge3_2(T1, H1, [H2 | M], T2, H3, T3);
rmerge3_21_3(T1, H1, H2, T2, M, _nil) ->
rmerge2_1(T2, H1, T1, [H2 | M]).
merge2_1([H1 | T1], H2, T2, M) when H2 < H1 ->
merge2_2(T1, H1, T2, [H2 | M]);
merge2_1([H1 | T1], H2, T2, M) ->
merge2_1(T1, H2, T2, [H1 | M]);
merge2_1(_nil, H2, T2, M) ->
lists:reverse(T2, [H2 | M]).
merge2_2(T1, H1, [H2 | T2], M) when H1 < H2 ->
merge2_1(T1, H2, T2, [H1 | M]);
merge2_2(T1, H1, [H2 | T2], M) ->
merge2_2(T1, H1, T2, [H2 | M]);
merge2_2(T1, H1, _nil, M) ->
lists:reverse(T1, [H1 | M]).
rmerge2_1([H1 | T1], H2, T2, M) when H2 >= H1 ->
rmerge2_2(T1, H1, T2, [H2 | M]);
rmerge2_1([H1 | T1], H2, T2, M) ->
rmerge2_1(T1, H2, T2, [H1 | M]);
rmerge2_1(_nil, H2, T2, M) ->
lists:reverse(T2, [H2 | M]).
rmerge2_2(T1, H1, [H2 | T2], M) when H1 >= H2 ->
rmerge2_1(T1, H2, T2, [H1 | M]);
rmerge2_2(T1, H1, [H2 | T2], M) ->
rmerge2_2(T1, H1, T2, [H2 | M]);
rmerge2_2(T1, H1, _nil, M) ->
lists:reverse(T1, [H1 | M]).
