diff options
Diffstat (limited to 'lib/stdlib/src/lists.erl')
| -rw-r--r-- | lib/stdlib/src/lists.erl | 2462 |
1 files changed, 2462 insertions, 0 deletions
diff --git a/lib/stdlib/src/lists.erl b/lib/stdlib/src/lists.erl new file mode 100644 index 0000000000..e1f8d1c200 --- /dev/null +++ b/lib/stdlib/src/lists.erl @@ -0,0 +1,2462 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 1996-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% +-module(lists). + +-export([append/2, append/1, subtract/2, reverse/1, + nth/2, nthtail/2, prefix/2, suffix/2, last/1, + seq/2, seq/3, sum/1, duplicate/2, min/1, max/1, sublist/2, sublist/3, + delete/2, + unzip/1, unzip3/1, zip/2, zip3/3, zipwith/3, zipwith3/4, + sort/1, merge/1, merge/2, rmerge/2, merge3/3, rmerge3/3, + usort/1, umerge/1, umerge3/3, umerge/2, rumerge3/3, rumerge/2, + concat/1, flatten/1, flatten/2, flat_length/1, flatlength/1, + keydelete/3, keyreplace/4, keytake/3, keystore/4, + keysort/2, keymerge/3, rkeymerge/3, rukeymerge/3, + ukeysort/2, ukeymerge/3, keymap/3]). + +%% Bifs: member/2, reverse/2 +%% Bifs: keymember/3, keysearch/3, keyfind/3 + +-export([merge/3, rmerge/3, sort/2, umerge/3, rumerge/3, usort/2]). + +-export([all/2,any/2,map/2,flatmap/2,foldl/3,foldr/3,filter/2, + partition/2,zf/2, + mapfoldl/3,mapfoldr/3,foreach/2,takewhile/2,dropwhile/2,splitwith/2, + split/2]). + +-deprecated([flat_length/1]). + +%% member(X, L) -> (true | false) +%% test if X is a member of the list L +%% Now a BIF! + +%member(X, [X|_]) -> true; +%member(X, [_|Y]) -> +% member(X, Y); +%member(X, []) -> false. + +%% append(X, Y) appends lists X and Y + +-spec append([T], [T]) -> [T]. + +append(L1, L2) -> L1 ++ L2. + +%% append(L) appends the list of lists L + +-spec append([[T]]) -> [T]. + +append([E]) -> E; +append([H|T]) -> H ++ append(T); +append([]) -> []. + +%% subtract(List1, List2) subtract elements in List2 form List1. + +-spec subtract([T], [T]) -> [T]. + +subtract(L1, L2) -> L1 -- L2. + +%% reverse(L) reverse all elements in the list L. Is now a BIF! + +-spec reverse([T]) -> [T]. + +reverse([] = L) -> + L; +reverse([_] = L) -> + L; +reverse([A, B]) -> + [B, A]; +reverse([A, B | L]) -> + lists:reverse(L, [B, A]). + +%reverse([H|T], Y) -> +% reverse(T, [H|Y]); +%reverse([], X) -> X. + + +%% nth(N, L) returns the N`th element of the list L +%% nthtail(N, L) returns the N`th tail of the list L + +-spec nth(pos_integer(), [T,...]) -> T. + +nth(1, [H|_]) -> H; +nth(N, [_|T]) when N > 1 -> + nth(N - 1, T). + +-spec nthtail(non_neg_integer(), [T,...]) -> [T]. + +nthtail(1, [_|T]) -> T; +nthtail(N, [_|T]) when N > 1 -> + nthtail(N - 1, T); +nthtail(0, L) when is_list(L) -> L. + +%% prefix(Prefix, List) -> (true | false) + +-spec prefix([T], [T]) -> boolean(). + +prefix([X|PreTail], [X|Tail]) -> + prefix(PreTail, Tail); +prefix([], List) when is_list(List) -> true; +prefix([_|_], List) when is_list(List) -> false. + +%% suffix(Suffix, List) -> (true | false) + +-spec suffix([T], [T]) -> boolean(). + +suffix(Suffix, List) -> + Delta = length(List) - length(Suffix), + Delta >= 0 andalso nthtail(Delta, List) =:= Suffix. + +%% last(List) returns the last element in a list. + +-spec last([T,...]) -> T. + +last([E|Es]) -> last(E, Es). + +last(_, [E|Es]) -> last(E, Es); +last(E, []) -> E. + +%% seq(Min, Max) -> [Min,Min+1, ..., Max] +%% seq(Min, Max, Incr) -> [Min,Min+Incr, ..., Max] +%% returns the sequence Min..Max +%% Min <= Max and Min and Max must be integers + +-spec seq(integer(), integer()) -> [integer()]. + +seq(First, Last) + when is_integer(First), is_integer(Last), First-1 =< Last -> + seq_loop(Last-First+1, Last, []). + +seq_loop(N, X, L) when N >= 4 -> + seq_loop(N-4, X-4, [X-3,X-2,X-1,X|L]); +seq_loop(N, X, L) when N >= 2 -> + seq_loop(N-2, X-2, [X-1,X|L]); +seq_loop(1, X, L) -> + [X|L]; +seq_loop(0, _, L) -> + L. + +-spec seq(integer(), integer(), integer()) -> [integer()]. + +seq(First, Last, Inc) + when is_integer(First), is_integer(Last), is_integer(Inc) -> + if + Inc > 0, First - Inc =< Last; + Inc < 0, First - Inc >= Last -> + N = (Last - First + Inc) div Inc, + seq_loop(N, Inc*(N-1)+First, Inc, []); + Inc =:= 0, First =:= Last -> + seq_loop(1, First, Inc, []) + end. + +seq_loop(N, X, D, L) when N >= 4 -> + Y = X-D, Z = Y-D, W = Z-D, + seq_loop(N-4, W-D, D, [W,Z,Y,X|L]); +seq_loop(N, X, D, L) when N >= 2 -> + Y = X-D, + seq_loop(N-2, Y-D, D, [Y,X|L]); +seq_loop(1, X, _, L) -> + [X|L]; +seq_loop(0, _, _, L) -> + L. + +%% sum(L) returns the sum of the elements in L + +-spec sum([number()]) -> number(). + +sum(L) -> sum(L, 0). + +sum([H|T], Sum) -> sum(T, Sum + H); +sum([], Sum) -> Sum. + +%% duplicate(N, X) -> [X,X,X,.....,X] (N times) +%% return N copies of X + +-spec duplicate(non_neg_integer(), T) -> [T]. + +duplicate(N, X) when is_integer(N), N >= 0 -> duplicate(N, X, []). + +duplicate(0, _, L) -> L; +duplicate(N, X, L) -> duplicate(N-1, X, [X|L]). + +%% min(L) -> returns the minimum element of the list L + +-spec min([T,...]) -> T. + +min([H|T]) -> min(T, H). + +min([H|T], Min) when H < Min -> min(T, H); +min([_|T], Min) -> min(T, Min); +min([], Min) -> Min. + +%% max(L) -> returns the maximum element of the list L + +-spec max([T,...]) -> T. + +max([H|T]) -> max(T, H). + +max([H|T], Max) when H > Max -> max(T, H); +max([_|T], Max) -> max(T, Max); +max([], Max) -> Max. + +%% sublist(List, Start, Length) +%% Returns the sub-list starting at Start of length Length. + +-spec sublist([T], pos_integer(), non_neg_integer()) -> [T]. + +sublist(List, S, L) when is_integer(L), L >= 0 -> + sublist(nthtail(S-1, List), L). + +-spec sublist([T], non_neg_integer()) -> [T]. + +sublist(List, L) when is_integer(L), is_list(List) -> + sublist_2(List, L). + +sublist_2([H|T], L) when L > 0 -> + [H|sublist_2(T, L-1)]; +sublist_2(_, 0) -> + []; +sublist_2(List, L) when is_list(List), L > 0 -> + []. + +%% delete(Item, List) -> List' +%% Delete the first occurrence of Item from the list L. + +-spec delete(T, [T]) -> [T]. + +delete(Item, [Item|Rest]) -> Rest; +delete(Item, [H|Rest]) -> + [H|delete(Item, Rest)]; +delete(_, []) -> []. + +%% Return [{X0, Y0}, {X1, Y1}, ..., {Xn, Yn}] for lists [X0, X1, ..., +%% Xn] and [Y0, Y1, ..., Yn]. + +-spec zip([A], [B]) -> [{A, B}]. + +zip([X | Xs], [Y | Ys]) -> [{X, Y} | zip(Xs, Ys)]; +zip([], []) -> []. + +%% Return {[X0, X1, ..., Xn], [Y0, Y1, ..., Yn]}, for a list [{X0, Y0}, +%% {X1, Y1}, ..., {Xn, Yn}]. + +-spec unzip([{A, B}]) -> {[A], [B]}. + +unzip(Ts) -> unzip(Ts, [], []). + +unzip([{X, Y} | Ts], Xs, Ys) -> unzip(Ts, [X | Xs], [Y | Ys]); +unzip([], Xs, Ys) -> {reverse(Xs), reverse(Ys)}. + +%% Return [{X0, Y0, Z0}, {X1, Y1, Z1}, ..., {Xn, Yn, Zn}] for lists [X0, +%% X1, ..., Xn], [Y0, Y1, ..., Yn] and [Z0, Z1, ..., Zn]. + +-spec zip3([A], [B], [C]) -> [{A, B, C}]. + +zip3([X | Xs], [Y | Ys], [Z | Zs]) -> [{X, Y, Z} | zip3(Xs, Ys, Zs)]; +zip3([], [], []) -> []. + +%% Return {[X0, X1, ..., Xn], [Y0, Y1, ..., Yn], [Z0, Z1, ..., Zn]}, for +%% a list [{X0, Y0, Z0}, {X1, Y1, Z1}, ..., {Xn, Yn, Zn}]. + +-spec unzip3([{A, B, C}]) -> {[A], [B], [C]}. + +unzip3(Ts) -> unzip3(Ts, [], [], []). + +unzip3([{X, Y, Z} | Ts], Xs, Ys, Zs) -> + unzip3(Ts, [X | Xs], [Y | Ys], [Z | Zs]); +unzip3([], Xs, Ys, Zs) -> + {reverse(Xs), reverse(Ys), reverse(Zs)}. + +%% Return [F(X0, Y0), F(X1, Y1), ..., F(Xn, Yn)] for lists [X0, X1, ..., +%% Xn] and [Y0, Y1, ..., Yn]. + +-spec zipwith(fun((X, Y) -> R), [X], [Y]) -> [R]. + +zipwith(F, [X | Xs], [Y | Ys]) -> [F(X, Y) | zipwith(F, Xs, Ys)]; +zipwith(F, [], []) when is_function(F, 2) -> []. + +%% Return [F(X0, Y0, Z0), F(X1, Y1, Z1), ..., F(Xn, Yn, Zn)] for lists +%% [X0, X1, ..., Xn], [Y0, Y1, ..., Yn] and [Z0, Z1, ..., Zn]. + +-spec zipwith3(fun((X, Y, Z) -> R), [X], [Y], [Z]) -> [R]. + +zipwith3(F, [X | Xs], [Y | Ys], [Z | Zs]) -> + [F(X, Y, Z) | zipwith3(F, Xs, Ys, Zs)]; +zipwith3(F, [], [], []) when is_function(F, 3) -> []. + +%% sort(List) -> L +%% sorts the list L + +-spec sort([T]) -> [T]. + +sort([X, Y | L] = L0) when X =< Y -> + case L of + [] -> + L0; + [Z] when Y =< Z -> + L0; + [Z] when X =< Z -> + [X, Z, Y]; + [Z] -> + [Z, X, Y]; + _ when X == Y -> + sort_1(Y, L, [X]); + _ -> + split_1(X, Y, L, [], []) + end; +sort([X, Y | L]) -> + case L of + [] -> + [Y, X]; + [Z] when X =< Z -> + [Y, X | L]; + [Z] when Y =< Z -> + [Y, Z, X]; + [Z] -> + [Z, Y, X]; + _ -> + split_2(X, Y, L, [], []) + end; +sort([_] = L) -> + L; +sort([] = L) -> + L. + +sort_1(X, [Y | L], R) when X == Y -> + sort_1(Y, L, [X | R]); +sort_1(X, [Y | L], R) when X < Y -> + split_1(X, Y, L, R, []); +sort_1(X, [Y | L], R) -> + split_2(X, Y, L, R, []); +sort_1(X, [], R) -> + lists:reverse(R, [X]). + +%% merge(List) -> L +%% merges a list of sorted lists + +-spec merge([T]) -> [T]. + +merge(L) -> + mergel(L, []). + +%% merge3(X, Y, Z) -> L +%% merges three sorted lists X, Y and Z + +-spec merge3([_], [_], [_]) -> [_]. + +merge3(L1, [], L3) -> + merge(L1, L3); +merge3(L1, L2, []) -> + merge(L1, L2); +merge3(L1, [H2 | T2], [H3 | T3]) -> + lists:reverse(merge3_1(L1, [], H2, T2, H3, T3), []). + +%% rmerge3(X, Y, Z) -> L +%% merges three reversed sorted lists X, Y and Z + +-spec rmerge3([_], [_], [_]) -> [_]. + +rmerge3(L1, [], L3) -> + rmerge(L1, L3); +rmerge3(L1, L2, []) -> + rmerge(L1, L2); +rmerge3(L1, [H2 | T2], [H3 | T3]) -> + lists:reverse(rmerge3_1(L1, [], H2, T2, H3, T3), []). + +%% merge(X, Y) -> L +%% merges two sorted lists X and Y + +-spec merge([_], [_]) -> [_]. + +merge(T1, []) -> + T1; +merge(T1, [H2 | T2]) -> + lists:reverse(merge2_1(T1, H2, T2, []), []). + +%% rmerge(X, Y) -> L +%% merges two reversed sorted lists X and Y + +%% reverse(rmerge(reverse(A),reverse(B))) is equal to merge(I,A,B). + +-spec rmerge([_], [_]) -> [_]. + +rmerge(T1, []) -> + T1; +rmerge(T1, [H2 | T2]) -> + lists:reverse(rmerge2_1(T1, H2, T2, []), []). + +%% concat(L) concatenate the list representation of the elements +%% in L - the elements in L can be atoms, numbers of strings. +%% Returns a list of characters. + +-type concat_thing() :: atom() | integer() | float() | string(). +-spec concat([concat_thing()]) -> string(). + +concat(List) -> + flatmap(fun thing_to_list/1, List). + +thing_to_list(X) when is_integer(X) -> integer_to_list(X); +thing_to_list(X) when is_float(X) -> float_to_list(X); +thing_to_list(X) when is_atom(X) -> atom_to_list(X); +thing_to_list(X) when is_list(X) -> X. %Assumed to be a string + +%% flatten(List) +%% flatten(List, Tail) +%% Flatten a list, adding optional tail. + +-spec flatten([_]) -> [_]. + +flatten(List) when is_list(List) -> + do_flatten(List, []). + +-spec flatten([_], [_]) -> [_]. + +flatten(List, Tail) when is_list(List), is_list(Tail) -> + do_flatten(List, Tail). + +do_flatten([H|T], Tail) when is_list(H) -> + do_flatten(H, do_flatten(T, Tail)); +do_flatten([H|T], Tail) -> + [H|do_flatten(T, Tail)]; +do_flatten([], Tail) -> + Tail. + +%% flat_length(List) (undocumented can be removed later) +%% Calculate the length of a list of lists. + +-spec flat_length([_]) -> non_neg_integer(). + +flat_length(List) -> flatlength(List). + +%% flatlength(List) +%% Calculate the length of a list of lists. + +-spec flatlength([_]) -> non_neg_integer(). + +flatlength(List) -> + flatlength(List, 0). + +flatlength([H|T], L) when is_list(H) -> + flatlength(H, flatlength(T, L)); +flatlength([_|T], L) -> + flatlength(T, L + 1); +flatlength([], L) -> L. + +%% keymember(Key, Index, [Tuple]) Now a BIF! +%% keysearch(Key, Index, [Tuple]) Now a BIF! +%% keydelete(Key, Index, [Tuple]) +%% keyreplace(Key, Index, [Tuple], NewTuple) +%% keytake(Key, Index, [Tuple]) +%% keystore(Key, Index, [Tuple], NewTuple) +%% keysort(Index, [Tuple]) +%% keymerge(Index, [Tuple], [Tuple]) +%% ukeysort(Index, [Tuple]) +%% ukeymerge(Index, [Tuple], [Tuple]) +%% keymap(Function, Index, [Tuple]) +%% keymap(Function, ExtraArgs, Index, [Tuple]) + +%keymember(K,N,L) when is_integer(N), N > 0 -> +% keymember3(K,N,L). + +%keymember3(Key, N, [T|Ts]) when element(N, T) == Key -> true; +%keymember3(Key, N, [T|Ts]) -> +% keymember3(Key, N, Ts); +%keymember3(Key, N, []) -> false. + +%keysearch(K, N, L) when is_integer(N), N > 0 -> +% keysearch3(K, N, L). + +%keysearch3(Key, N, [H|T]) when element(N, H) == Key -> +% {value, H}; +%keysearch3(Key, N, [H|T]) -> +% keysearch3(Key, N, T); +%keysearch3(Key, N, []) -> false. + +-spec keydelete(_, pos_integer(), [T]) -> [T]. + +keydelete(K, N, L) when is_integer(N), N > 0 -> + keydelete3(K, N, L). + +keydelete3(Key, N, [H|T]) when element(N, H) == Key -> T; +keydelete3(Key, N, [H|T]) -> + [H|keydelete3(Key, N, T)]; +keydelete3(_, _, []) -> []. + +-spec keyreplace(_, pos_integer(), [_], tuple()) -> [_]. + +keyreplace(K, N, L, New) when is_integer(N), N > 0, is_tuple(New) -> + keyreplace3(K, N, L, New). + +keyreplace3(Key, Pos, [Tup|Tail], New) when element(Pos, Tup) == Key -> + [New|Tail]; +keyreplace3(Key, Pos, [H|T], New) -> + [H|keyreplace3(Key, Pos, T, New)]; +keyreplace3(_, _, [], _) -> []. + +-spec keytake(_, pos_integer(), [_]) -> {'value', tuple(), [_]} | 'false'. + +keytake(Key, N, L) when is_integer(N), N > 0 -> + keytake(Key, N, L, []). + +keytake(Key, N, [H|T], L) when element(N, H) == Key -> + {value, H, lists:reverse(L, T)}; +keytake(Key, N, [H|T], L) -> + keytake(Key, N, T, [H|L]); +keytake(_K, _N, [], _L) -> false. + +-spec keystore(_, pos_integer(), [_], tuple()) -> [_]. +keystore(K, N, L, New) when is_integer(N), N > 0, is_tuple(New) -> + keystore2(K, N, L, New). + +keystore2(Key, N, [H|T], New) when element(N, H) == Key -> + [New|T]; +keystore2(Key, N, [H|T], New) -> + [H|keystore2(Key, N, T, New)]; +keystore2(_Key, _N, [], New) -> + [New]. + +-spec keysort(pos_integer(), [T]) -> [T] when is_subtype(T, tuple()). + +keysort(I, L) when is_integer(I), I > 0 -> + case L of + [] -> L; + [_] -> L; + [X, Y | T] -> + case {element(I, X), element(I, Y)} of + {EX, EY} when EX =< EY -> + case T of + [] -> + L; + [Z] -> + case element(I, Z) of + EZ when EY =< EZ -> + L; + EZ when EX =< EZ -> + [X, Z, Y]; + _EZ -> + [Z, X, Y] + end; + _ when X == Y -> + keysort_1(I, Y, EY, T, [X]); + _ -> + keysplit_1(I, X, EX, Y, EY, T, [], []) + end; + {EX, EY} -> + case T of + [] -> + [Y, X]; + [Z] -> + case element(I, Z) of + EZ when EX =< EZ -> + [Y, X | T]; + EZ when EY =< EZ -> + [Y, Z, X]; + _EZ -> + [Z, Y, X] + end; + _ -> + keysplit_2(I, X, EX, Y, EY, T, [], []) + end + end + end. + +keysort_1(I, X, EX, [Y | L], R) when X == Y -> + keysort_1(I, Y, EX, L, [X | R]); +keysort_1(I, X, EX, [Y | L], R) -> + case element(I, Y) of + EY when EX =< EY -> + keysplit_1(I, X, EX, Y, EY, L, R, []); + EY -> + keysplit_2(I, X, EX, Y, EY, L, R, []) + end; +keysort_1(_I, X, _EX, [], R) -> + lists:reverse(R, [X]). + +-spec keymerge(pos_integer(), [X], [Y]) -> + [R] when is_subtype(X, tuple()), is_subtype(Y, tuple()), is_subtype(R, tuple()). + +keymerge(Index, T1, L2) when is_integer(Index), Index > 0 -> + case L2 of + [] -> + T1; + [H2 | T2] -> + E2 = element(Index, H2), + M = keymerge2_1(Index, T1, E2, H2, T2, []), + lists:reverse(M, []) + end. + +%% reverse(rkeymerge(I,reverse(A),reverse(B))) is equal to keymerge(I,A,B). + +-spec rkeymerge(pos_integer(), [X], [Y]) -> + [R] when is_subtype(X, tuple()), is_subtype(Y, tuple()), is_subtype(R, tuple()). + +rkeymerge(Index, T1, L2) when is_integer(Index), Index > 0 -> + case L2 of + [] -> + T1; + [H2 | T2] -> + E2 = element(Index, H2), + M = rkeymerge2_1(Index, T1, E2, H2, T2, []), + lists:reverse(M, []) + end. + +-spec ukeysort(pos_integer(), [T]) -> [T] when is_subtype(T, tuple()). + +ukeysort(I, L) when is_integer(I), I > 0 -> + case L of + [] -> L; + [_] -> L; + [X, Y | T] -> + case {element(I, X), element(I, Y)} of + {EX, EY} when EX == EY -> + ukeysort_1(I, X, EX, T); + {EX, EY} when EX < EY -> + case T of + [] -> + L; + [Z] -> + case element(I, Z) of + EZ when EY == EZ -> + [X, Y]; + EZ when EY < EZ -> + [X, Y, Z]; + EZ when EZ == EX -> + [X, Y]; + EZ when EX =< EZ -> + [X, Z, Y]; + _EZ -> + [Z, X, Y] + end; + _ -> + ukeysplit_1(I, X, EX, Y, EY, T, [], []) + end; + {EX, EY} -> + case T of + [] -> + [Y, X]; + [Z] -> + case element(I, Z) of + EZ when EX == EZ -> + [Y, X]; + EZ when EX < EZ -> + [Y, X, Z]; + EZ when EY == EZ -> + [Y, X]; + EZ when EY =< EZ -> + [Y, Z, X]; + _EZ -> + [Z, Y, X] + end; + _ -> + ukeysplit_2(I, Y, EY, T, [X]) + end + end + end. + +ukeysort_1(I, X, EX, [Y | L]) -> + case element(I, Y) of + EY when EX == EY -> + ukeysort_1(I, X, EX, L); + EY when EX < EY -> + ukeysplit_1(I, X, EX, Y, EY, L, [], []); + EY -> + ukeysplit_2(I, Y, EY, L, [X]) + end; +ukeysort_1(_I, X, _EX, []) -> + [X]. + +-spec ukeymerge(pos_integer(), [X], [Y]) -> + [(X | Y)] when is_subtype(X, tuple()), is_subtype(Y, tuple()). + +ukeymerge(Index, L1, T2) when is_integer(Index), Index > 0 -> + case L1 of + [] -> + T2; + [H1 | T1] -> + E1 = element(Index, H1), + M = ukeymerge2_2(Index, T1, E1, H1, T2, []), + lists:reverse(M, []) + end. + +%% reverse(rukeymerge(I,reverse(A),reverse(B))) is equal to ukeymerge(I,A,B). + +-spec rukeymerge(pos_integer(), [X], [Y]) -> + [(X | Y)] when is_subtype(X, tuple()), is_subtype(Y, tuple()). + +rukeymerge(Index, T1, L2) when is_integer(Index), Index > 0 -> + case L2 of + [] -> + T1; + [H2 | T2] -> + E2 = element(Index, H2), + M = rukeymerge2_1(Index, T1, E2, T2, [], H2), + lists:reverse(M, []) + end. + +-spec keymap(fun((_) -> _), pos_integer(), [tuple()]) -> [tuple()]. + +keymap(Fun, Index, [Tup|Tail]) -> + [setelement(Index, Tup, Fun(element(Index, Tup)))|keymap(Fun, Index, Tail)]; +keymap(Fun, Index, []) when is_integer(Index), Index >= 1, + is_function(Fun, 1) -> []. + +%%% Suggestion from OTP-2948: sort and merge with Fun. + +-spec sort(fun((T, T) -> boolean()), [T]) -> [T]. + +sort(Fun, []) when is_function(Fun, 2) -> + []; +sort(Fun, [_] = L) when is_function(Fun, 2) -> + L; +sort(Fun, [X, Y | T]) -> + case Fun(X, Y) of + true -> + fsplit_1(Y, X, Fun, T, [], []); + false -> + fsplit_2(Y, X, Fun, T, [], []) + end. + +-spec merge(fun((X, Y) -> boolean()), [X], [Y]) -> [_]. + +merge(Fun, T1, [H2 | T2]) when is_function(Fun, 2) -> + lists:reverse(fmerge2_1(T1, H2, Fun, T2, []), []); +merge(Fun, T1, []) when is_function(Fun, 2) -> + T1. + +%% reverse(rmerge(F,reverse(A),reverse(B))) is equal to merge(F,A,B). + +-spec rmerge(fun((X, Y) -> boolean()), [X], [Y]) -> [_]. + +rmerge(Fun, T1, [H2 | T2]) when is_function(Fun, 2) -> + lists:reverse(rfmerge2_1(T1, H2, Fun, T2, []), []); +rmerge(Fun, T1, []) when is_function(Fun, 2) -> + T1. + +-spec usort(fun((T, T) -> boolean()), [T]) -> [T]. + +usort(Fun, [_] = L) when is_function(Fun, 2) -> + L; +usort(Fun, [] = L) when is_function(Fun, 2) -> + L; +usort(Fun, [X | L]) when is_function(Fun, 2) -> + usort_1(Fun, X, L). + +usort_1(Fun, X, [Y | L]) -> + case Fun(X, Y) of + true -> + case Fun(Y, X) of + true -> % X equal to Y + case L of + [] -> + [X]; + _ -> + usort_1(Fun, X, L) + end; + false -> + ufsplit_1(Y, X, Fun, L, [], []) + end; + false -> + ufsplit_2(Y, L, Fun, [X]) + end. + +-spec umerge(fun((X, Y) -> boolean()), [X], [Y]) -> [_]. + +umerge(Fun, [], T2) when is_function(Fun, 2) -> + T2; +umerge(Fun, [H1 | T1], T2) when is_function(Fun, 2) -> + lists:reverse(ufmerge2_2(H1, T1, Fun, T2, []), []). + +%% reverse(rumerge(F,reverse(A),reverse(B))) is equal to umerge(F,A,B). + +-spec rumerge(fun((X, Y) -> boolean()), [X], [Y]) -> [_]. + +rumerge(Fun, T1, []) when is_function(Fun, 2) -> + T1; +rumerge(Fun, T1, [H2 | T2]) when is_function(Fun, 2) -> + lists:reverse(rufmerge2_1(T1, H2, Fun, T2, []), []). + +%% usort(List) -> L +%% sorts the list L, removes duplicates + +-spec usort([T]) -> [T]. + +usort([X, Y | L] = L0) when X < Y -> + case L of + [] -> + L0; + [Z] when Y < Z -> + L0; + [Z] when Y == Z -> + [X, Y]; + [Z] when Z < X -> + [Z, X, Y]; + [Z] when Z == X -> + [X, Y]; + [Z] -> + [X, Z, Y]; + _ -> + usplit_1(X, Y, L, [], []) + end; +usort([X, Y | L]) when X > Y -> + case L of + [] -> + [Y, X]; + [Z] when X < Z -> + [Y, X | L]; + [Z] when X == Z -> + [Y, X]; + [Z] when Z < Y -> + [Z, Y, X]; + [Z] when Z == Y -> + [Y, X]; + [Z] -> + [Y, Z, X]; + _ -> + usplit_2(X, Y, L, [], []) + end; +usort([X, _Y | L]) -> + usort_1(X, L); +usort([_] = L) -> + L; +usort([]) -> + []. + +usort_1(X, [Y | L]) when X == Y -> + usort_1(X, L); +usort_1(X, [Y | L]) when X < Y -> + usplit_1(X, Y, L, [], []); +usort_1(X, [Y | L]) -> + usplit_2(X, Y, L, [], []); +usort_1(X, []) -> + [X]. + +%% umerge(List) -> L +%% merges a list of sorted lists without duplicates, removes duplicates + +-spec umerge([T]) -> [T]. + +umerge(L) -> + umergel(L). + +%% umerge3(X, Y, Z) -> L +%% merges three sorted lists X, Y and Z without duplicates, +%% removes duplicates + +-spec umerge3([_], [_], [_]) -> [_]. + +umerge3(L1, [], L3) -> + umerge(L1, L3); +umerge3(L1, L2, []) -> + umerge(L1, L2); +umerge3(L1, [H2 | T2], [H3 | T3]) -> + lists:reverse(umerge3_1(L1, [H2 | H3], T2, H2, [], T3, H3), []). + +%% rumerge3(X, Y, Z) -> L +%% merges three reversed sorted lists X, Y and Z without duplicates, +%% removes duplicates + +-spec rumerge3([_], [_], [_]) -> [_]. + +rumerge3(L1, [], L3) -> + rumerge(L1, L3); +rumerge3(L1, L2, []) -> + rumerge(L1, L2); +rumerge3(L1, [H2 | T2], [H3 | T3]) -> + lists:reverse(rumerge3_1(L1, T2, H2, [], T3, H3),[]). + +%% umerge(X, Y) -> L +%% merges two sorted lists X and Y without duplicates, removes duplicates + +-spec umerge([_], [_]) -> [_]. + +umerge([], T2) -> + T2; +umerge([H1 | T1], T2) -> + lists:reverse(umerge2_2(T1, T2, [], H1), []). + +%% rumerge(X, Y) -> L +%% merges two reversed sorted lists X and Y without duplicates, +%% removes duplicates + +%% reverse(rumerge(reverse(A),reverse(B))) is equal to umerge(I,A,B). + +-spec rumerge([_], [_]) -> [_]. + +rumerge(T1, []) -> + T1; +rumerge(T1, [H2 | T2]) -> + lists:reverse(rumerge2_1(T1, T2, [], H2), []). + +%% all(Predicate, List) +%% any(Predicate, List) +%% map(Function, List) +%% flatmap(Function, List) +%% foldl(Function, First, List) +%% foldr(Function, Last, List) +%% filter(Predicate, List) +%% zf(Function, List) +%% mapfoldl(Function, First, List) +%% mapfoldr(Function, Last, List) +%% foreach(Function, List) +%% takewhile(Predicate, List) +%% dropwhile(Predicate, List) +%% splitwith(Predicate, List) +%% for list programming. Function here is a 'fun'. For backward compatibility, +%% {Module,Function} is still accepted. +%% +%% The name zf is a joke! +%% +%% N.B. Unless where the functions actually needs it only foreach/2/3, +%% which is meant to be used for its side effects, has a defined order +%% of evaluation. +%% +%% There are also versions with an extra argument, ExtraArgs, which is a +%% list of extra arguments to each call. + +-spec all(fun((T) -> boolean()), [T]) -> boolean(). + +all(Pred, [Hd|Tail]) -> + case Pred(Hd) of + true -> all(Pred, Tail); + false -> false + end; +all(Pred, []) when is_function(Pred, 1) -> true. + +-spec any(fun((T) -> boolean()), [T]) -> boolean(). + +any(Pred, [Hd|Tail]) -> + case Pred(Hd) of + true -> true; + false -> any(Pred, Tail) + end; +any(Pred, []) when is_function(Pred, 1) -> false. + +-spec map(fun((D) -> R), [D]) -> [R]. + +map(F, [H|T]) -> + [F(H)|map(F, T)]; +map(F, []) when is_function(F, 1) -> []. + +-spec flatmap(fun((D) -> [R]), [D]) -> [R]. + +flatmap(F, [Hd|Tail]) -> + F(Hd) ++ flatmap(F, Tail); +flatmap(F, []) when is_function(F, 1) -> []. + +-spec foldl(fun((T, _) -> _), _, [T]) -> _. + +foldl(F, Accu, [Hd|Tail]) -> + foldl(F, F(Hd, Accu), Tail); +foldl(F, Accu, []) when is_function(F, 2) -> Accu. + +-spec foldr(fun((T, _) -> _), _, [T]) -> _. + +foldr(F, Accu, [Hd|Tail]) -> + F(Hd, foldr(F, Accu, Tail)); +foldr(F, Accu, []) when is_function(F, 2) -> Accu. + +-spec filter(Pred :: fun((T) -> boolean()), List :: [T]) -> [T]. + +filter(Pred, List) when is_function(Pred, 1) -> + [ E || E <- List, Pred(E) ]. + +%% Equivalent to {filter(F, L), filter(NotF, L)}, if NotF = 'fun(X) -> +%% not F(X) end'. + +-spec partition(Pred :: fun((T) -> boolean()), List :: [T]) -> {[T], [T]}. + +partition(Pred, L) -> + partition(Pred, L, [], []). + +partition(Pred, [H | T], As, Bs) -> + case Pred(H) of + true -> partition(Pred, T, [H | As], Bs); + false -> partition(Pred, T, As, [H | Bs]) + end; +partition(Pred, [], As, Bs) when is_function(Pred, 1) -> + {reverse(As), reverse(Bs)}. + +-spec zf(fun((T) -> boolean() | {'true', X}), [T]) -> [(T | X)]. + +zf(F, [Hd|Tail]) -> + case F(Hd) of + true -> + [Hd|zf(F, Tail)]; + {true,Val} -> + [Val|zf(F, Tail)]; + false -> + zf(F, Tail) + end; +zf(F, []) when is_function(F, 1) -> []. + +-spec foreach(F :: fun((T) -> _), List :: [T]) -> 'ok'. + +foreach(F, [Hd|Tail]) -> + F(Hd), + foreach(F, Tail); +foreach(F, []) when is_function(F, 1) -> ok. + +-spec mapfoldl(fun((T, _) -> {_, _}), _, [T]) -> {[_], _}. + +mapfoldl(F, Accu0, [Hd|Tail]) -> + {R,Accu1} = F(Hd, Accu0), + {Rs,Accu2} = mapfoldl(F, Accu1, Tail), + {[R|Rs],Accu2}; +mapfoldl(F, Accu, []) when is_function(F, 2) -> {[],Accu}. + +-spec mapfoldr(fun((T, _) -> {_, _}), _, [T]) -> {[_], _}. + +mapfoldr(F, Accu0, [Hd|Tail]) -> + {Rs,Accu1} = mapfoldr(F, Accu0, Tail), + {R,Accu2} = F(Hd, Accu1), + {[R|Rs],Accu2}; +mapfoldr(F, Accu, []) when is_function(F, 2) -> {[],Accu}. + +-spec takewhile(fun((T) -> boolean()), [T]) -> [T]. + +takewhile(Pred, [Hd|Tail]) -> + case Pred(Hd) of + true -> [Hd|takewhile(Pred, Tail)]; + false -> [] + end; +takewhile(Pred, []) when is_function(Pred, 1) -> []. + +-spec dropwhile(fun((T) -> boolean()), [T]) -> [T]. + +dropwhile(Pred, [Hd|Tail]=Rest) -> + case Pred(Hd) of + true -> dropwhile(Pred, Tail); + false -> Rest + end; +dropwhile(Pred, []) when is_function(Pred, 1) -> []. + +-spec splitwith(fun((T) -> boolean()), [T]) -> {[T], [T]}. + +splitwith(Pred, List) when is_function(Pred, 1) -> + splitwith(Pred, List, []). + +splitwith(Pred, [Hd|Tail], Taken) -> + case Pred(Hd) of + true -> splitwith(Pred, Tail, [Hd|Taken]); + false -> {reverse(Taken), [Hd|Tail]} + end; +splitwith(Pred, [], Taken) when is_function(Pred, 1) -> + {reverse(Taken),[]}. + +-spec split(non_neg_integer(), [T]) -> {[T], [T]}. + +split(N, List) when is_integer(N), N >= 0, is_list(List) -> + case split(N, List, []) of + {_, _} = Result -> Result; + Fault when is_atom(Fault) -> + erlang:error(Fault, [N,List]) + end; +split(N, List) -> + erlang:error(badarg, [N,List]). + +split(0, L, R) -> + {lists:reverse(R, []), L}; +split(N, [H|T], R) -> + split(N-1, T, [H|R]); +split(_, [], _) -> + badarg. + +%%% ================================================================= +%%% Here follows the implementation of the sort functions. +%%% +%%% These functions used to be in their own module (lists_sort), +%%% but have now been placed here to allow Dialyzer to produce better +%%% type information. +%%% ================================================================= + +-compile({inline, + [{merge3_12,7}, {merge3_21,7}, {rmerge3_12,7}, {rmerge3_21,7}]}). + +-compile({inline, + [{umerge3_12,8}, {umerge3_21,8}, + {rumerge3_12a,7}, {rumerge3_12b,8}]}). + +-compile({inline, + [{keymerge3_12,12}, {keymerge3_21,12}, + {rkeymerge3_12,12}, {rkeymerge3_21,12}]}). + +-compile({inline, + [{ukeymerge3_12,13}, {ukeymerge3_21,13}, + {rukeymerge3_12a,11}, {rukeymerge3_21a,13}, + {rukeymerge3_12b,12}, {rukeymerge3_21b,12}]}). + +%% sort/1 + +%% 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], []). + +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], []). + +%% merge/1 + +mergel([[] | L], Acc) -> + mergel(L, Acc); +mergel([T1, [H2 | T2], [H3 | T3] | L], Acc) -> + mergel(L, [merge3_1(T1, [], H2, T2, H3, T3) | Acc]); +mergel([T1, [H2 | T2]], Acc) -> + rmergel([merge2_1(T1, H2, T2, []) | 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([[H3 | T3], [H2 | T2], T1 | L], Acc) -> + rmergel(L, [rmerge3_1(T1, [], H2, T2, H3, T3) | Acc]); +rmergel([[H2 | T2], T1], Acc) -> + mergel([rmerge2_1(T1, H2, T2, []) | Acc], []); +rmergel([L], Acc) -> + mergel([lists:reverse(L, []) | Acc], []); +rmergel([], Acc) -> + mergel(Acc, []). + +%% merge3/3 + +%% 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([], M, H2, T2, H3, T3) when H2 =< H3 -> + merge2_1(T2, H3, T3, [H2 | M]); +merge3_1([], M, H2, T2, H3, T3) -> + merge2_2(T2, H3, T3, M, H2). + +%% 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, [], H3, T3) when H1 =< H3 -> + merge2_1(T1, H3, T3, [H1 | M]); +merge3_2(T1, H1, M, [], H3, T3) -> + merge2_2(T1, H3, T3, M, H1). + +% H1 =< H2. Inlined. +merge3_12(T1, H1, H2, T2, H3, T3, M) when H1 =< H3 -> + merge3_1(T1, [H1 | M], H2, T2, H3, T3); +merge3_12(T1, H1, H2, T2, H3, T3, M) -> + merge3_12_3(T1, H1, H2, T2, [H3 | M], T3). + +% H1 =< H2, take L3 apart. +merge3_12_3(T1, H1, H2, T2, M, [H3 | T3]) when H1 =< H3 -> + merge3_1(T1, [H1 | M], H2, T2, H3, T3); +merge3_12_3(T1, H1, H2, T2, M, [H3 | T3]) -> + merge3_12_3(T1, H1, H2, T2, [H3 | M], T3); +merge3_12_3(T1, H1, H2, T2, M, []) -> + merge2_1(T1, H2, T2, [H1 | M]). + +% H1 > H2. Inlined. +merge3_21(T1, H1, H2, T2, H3, T3, M) when H2 =< H3 -> + merge3_2(T1, H1, [H2 | M], T2, H3, T3); +merge3_21(T1, H1, H2, T2, H3, T3, M) -> + merge3_21_3(T1, H1, H2, T2, [H3 | M], T3). + +% H1 > H2, take L3 apart. +merge3_21_3(T1, H1, H2, T2, M, [H3 | T3]) when H2 =< H3 -> + merge3_2(T1, H1, [H2 | M], T2, H3, T3); +merge3_21_3(T1, H1, H2, T2, M, [H3 | T3]) -> + merge3_21_3(T1, H1, H2, T2, [H3 | M], T3); +merge3_21_3(T1, H1, H2, T2, M, []) -> + merge2_2(T1, H2, T2, M, H1). + +%% rmerge/3 + +%% 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([], M, H2, T2, H3, T3) when H2 =< H3 -> + rmerge2_2(T2, H3, T3, M, H2); +rmerge3_1([], M, H2, T2, H3, T3) -> + rmerge2_1(T2, H3, T3, [H2 | 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, [], H3, T3) when H1 =< H3 -> + rmerge2_2(T1, H3, T3, M, H1); +rmerge3_2(T1, H1, M, [], H3, T3) -> + rmerge2_1(T1, H3, T3, [H1 | M]). + +% H1 =< H2. Inlined. +rmerge3_12(T1, H1, H2, T2, H3, T3, M) when H2 =< H3 -> + rmerge3_12_3(T1, H1, H2, T2, [H3 | M], T3); +rmerge3_12(T1, H1, H2, T2, H3, T3, M) -> + rmerge3_2(T1, H1, [H2 | M], T2, H3, T3). + +% H1 =< H2, take L3 apart. +rmerge3_12_3(T1, H1, H2, T2, M, [H3 | T3]) when H2 =< H3 -> + rmerge3_12_3(T1, H1, H2, T2, [H3 | M], T3); +rmerge3_12_3(T1, H1, H2, T2, M, [H3 | T3]) -> + rmerge3_2(T1, H1, [H2 | M], T2, H3, T3); +rmerge3_12_3(T1, H1, H2, T2, M, []) -> + rmerge2_2(T1, H2, T2, M, H1). + +% H1 > H2. Inlined. +rmerge3_21(T1, H1, H2, T2, H3, T3, M) when H1 =< H3 -> + rmerge3_21_3(T1, H1, H2, T2, [H3 | M], T3); +rmerge3_21(T1, H1, H2, T2, H3, T3, M) -> + rmerge3_1(T1, [H1 | M], H2, T2, H3, T3). + +% H1 > H2, take L3 apart. +rmerge3_21_3(T1, H1, H2, T2, M, [H3 | T3]) when H1 =< H3 -> + rmerge3_21_3(T1, H1, H2, T2, [H3 | M], T3); +rmerge3_21_3(T1, H1, H2, T2, M, [H3 | T3]) -> + rmerge3_1(T1, [H1 | M], H2, T2, H3, T3); +rmerge3_21_3(T1, H1, H2, T2, M, []) -> + rmerge2_1(T1, H2, T2, [H1 | M]). + +%% merge/2 + +merge2_1([H1 | T1], H2, T2, M) when H1 =< H2 -> + merge2_1(T1, H2, T2, [H1 | M]); +merge2_1([H1 | T1], H2, T2, M) -> + merge2_2(T1, H2, T2, M, H1); +merge2_1([], H2, T2, M) -> + lists:reverse(T2, [H2 | M]). + +merge2_2(T1, HdM, [H2 | T2], M, H1) when H1 =< H2 -> + merge2_1(T1, H2, T2, [H1, HdM | M]); +merge2_2(T1, HdM, [H2 | T2], M, H1) -> + merge2_2(T1, H2, T2, [HdM | M], H1); +merge2_2(T1, HdM, [], M, H1) -> + lists:reverse(T1, [H1, HdM | M]). + +%% rmerge/2 + +rmerge2_1([H1 | T1], H2, T2, M) when H1 =< H2 -> + rmerge2_2(T1, H2, T2, M, H1); +rmerge2_1([H1 | T1], H2, T2, M) -> + rmerge2_1(T1, H2, T2, [H1 | M]); +rmerge2_1([], H2, T2, M) -> + lists:reverse(T2, [H2 | M]). + +rmerge2_2(T1, HdM, [H2 | T2], M, H1) when H1 =< H2 -> + rmerge2_2(T1, H2, T2, [HdM | M], H1); +rmerge2_2(T1, HdM, [H2 | T2], M, H1) -> + rmerge2_1(T1, H2, T2, [H1, HdM | M]); +rmerge2_2(T1, HdM, [], M, H1) -> + lists:reverse(T1, [H1, HdM | M]). + +%% usort/1 + +%% Ascending. +usplit_1(X, Y, [Z | L], R, Rs) when Z > Y -> + usplit_1(Y, Z, L, [X | R], Rs); +usplit_1(X, Y, [Z | L], R, Rs) when Z == Y -> + usplit_1(X, Y, L, R, Rs); +usplit_1(X, Y, [Z | L], R, Rs) when Z > X -> + usplit_1(Z, Y, L, [X | R], Rs); +usplit_1(X, Y, [Z | L], R, Rs) when Z == X -> + usplit_1(X, Y, L, R, Rs); +usplit_1(X, Y, [Z | L], [], Rs) -> + usplit_1(X, Y, L, [Z], Rs); +usplit_1(X, Y, [Z | L], R, Rs) -> + usplit_1_1(X, Y, L, R, Rs, Z); +usplit_1(X, Y, [], R, Rs) -> + rumergel([[Y, X | R] | Rs], [], asc). + +usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z > Y -> + usplit_1_1(Y, Z, L, [X | R], Rs, S); +usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z == Y -> + usplit_1_1(X, Y, L, R, Rs, S); +usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z > X -> + usplit_1_1(Z, Y, L, [X | R], Rs, S); +usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z == X -> + usplit_1_1(X, Y, L, R, Rs, S); +usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z > S -> + usplit_1(S, Z, L, [], [[Y, X | R] | Rs]); +usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z == S -> + usplit_1_1(X, Y, L, R, Rs, S); +usplit_1_1(X, Y, [Z | L], R, Rs, S) -> + usplit_1(Z, S, L, [], [[Y, X | R] | Rs]); +usplit_1_1(X, Y, [], R, Rs, S) -> + rumergel([[S], [Y, X | R] | Rs], [], asc). + +%% Descending. +usplit_2(X, Y, [Z | L], R, Rs) when Z < Y -> + usplit_2(Y, Z, L, [X | R], Rs); +usplit_2(X, Y, [Z | L], R, Rs) when Z == Y -> + usplit_2(X, Y, L, R, Rs); +usplit_2(X, Y, [Z | L], R, Rs) when Z < X -> + usplit_2(Z, Y, L, [X | R], Rs); +usplit_2(X, Y, [Z | L], R, Rs) when Z == X -> + usplit_2(X, Y, L, R, Rs); +usplit_2(X, Y, [Z | L], [], Rs) -> + usplit_2(X, Y, L, [Z], Rs); +usplit_2(X, Y, [Z | L], R, Rs) -> + usplit_2_1(X, Y, L, R, Rs, Z); +usplit_2(X, Y, [], R, Rs) -> + umergel([[Y, X | R] | Rs], [], desc). + +usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z < Y -> + usplit_2_1(Y, Z, L, [X | R], Rs, S); +usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z == Y -> + usplit_2_1(X, Y, L, R, Rs, S); +usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z < X -> + usplit_2_1(Z, Y, L, [X | R], Rs, S); +usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z == X -> + usplit_2_1(X, Y, L, R, Rs, S); +usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z < S -> + usplit_2(S, Z, L, [], [[Y, X | R] | Rs]); +usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z == S -> + usplit_2_1(X, Y, L, R, Rs, S); +usplit_2_1(X, Y, [Z | L], R, Rs, S) -> + usplit_2(Z, S, L, [], [[Y, X | R] | Rs]); +usplit_2_1(X, Y, [], R, Rs, S) -> + umergel([[S], [Y, X | R] | Rs], [], desc). + +%% umerge/1 + +umergel(L) -> + umergel(L, [], asc). + +umergel([[] | L], Acc, O) -> + umergel(L, Acc, O); +umergel([T1, [H2 | T2], [H3 | T3] | L], Acc, asc) -> + umergel(L, [umerge3_1(T1, [H2 | H3], T2, H2, [], T3, H3) | Acc], asc); +umergel([[H3 | T3], [H2 | T2], T1 | L], Acc, desc) -> + umergel(L, [umerge3_1(T1, [H2 | H3], T2, H2, [], T3, H3) | Acc], desc); +umergel([A, [] | L], Acc, O) -> + umergel([A | L], Acc, O); +umergel([A, B, [] | L], Acc, O) -> + umergel([A, B | L], Acc, O); +umergel([[H1 | T1], T2 | L], Acc, asc) -> + umergel(L, [umerge2_2(T1, T2, [], H1) | Acc], asc); +umergel([T2, [H1 | T1] | L], Acc, desc) -> + umergel(L, [umerge2_2(T1, T2, [], H1) | Acc], desc); +umergel([L], [], _O) -> + L; +umergel([L], Acc, O) -> + rumergel([lists:reverse(L, []) | Acc], [], O); +umergel([], [], _O) -> + []; +umergel([], Acc, O) -> + rumergel(Acc, [], O). + +rumergel([[H3 | T3], [H2 | T2], T1 | L], Acc, asc) -> + rumergel(L, [rumerge3_1(T1, T2, H2, [], T3, H3) | Acc], asc); +rumergel([T1, [H2 | T2], [H3 | T3] | L], Acc, desc) -> + rumergel(L, [rumerge3_1(T1, T2, H2, [], T3, H3) | Acc], desc); +rumergel([[H2 | T2], T1 | L], Acc, asc) -> + rumergel(L, [rumerge2_1(T1, T2, [], H2) | Acc], asc); +rumergel([T1, [H2 | T2] | L], Acc, desc) -> + rumergel(L, [rumerge2_1(T1, T2, [], H2) | Acc], desc); +rumergel([L], Acc, O) -> + umergel([lists:reverse(L, []) | Acc], [], O); +rumergel([], Acc, O) -> + umergel(Acc, [], O). + +%% umerge3/3 + +%% Take L1 apart. +umerge3_1([H1 | T1], HdM, T2, H2, M, T3, H3) when H1 =< H2 -> + umerge3_12(T1, H1, T2, H2, M, T3, H3, HdM); +umerge3_1([H1 | T1], HdM, T2, H2, M, T3, H3) when H2 == HdM -> + umerge3_2(T1, H1, T2, H2, M, T3, H3); +umerge3_1([H1 | T1], HdM, T2, H2, M, T3, H3) -> + umerge3_21(T1, H1, T2, H2, M, T3, H3, HdM); +umerge3_1([], HdM, T2, H2, M, T3, H3) when H2 == HdM -> + umerge2_1(T2, T3, M, HdM, H3); +umerge3_1([], _HdM, T2, H2, M, T3, H3) when H2 =< H3 -> + umerge2_1(T2, T3, [H2 | M], H2, H3); +umerge3_1([], HdM, T2, H2, M, T3, H3) when H3 == HdM -> + umerge2_2(T2, T3, M, H2); +umerge3_1([], _HdM, T2, H2, M, T3, H3) -> + umerge2_2(T2, T3, [H3 | M], H2). + +%% Take L2 apart. +umerge3_2(T1, H1, [H2 | T2], HdM, M, T3, H3) when H1 =< H2 -> + umerge3_12(T1, H1, T2, H2, M, T3, H3, HdM); +umerge3_2(T1, H1, [H2 | T2], HdM, M, T3, H3) -> + umerge3_21(T1, H1, T2, H2, M, T3, H3, HdM); +umerge3_2(T1, H1, [], _HdM, M, T3, H3) when H1 =< H3 -> + umerge2_1(T1, T3, [H1 | M], H1, H3); +umerge3_2(T1, H1, [], HdM, M, T3, H3) when H3 == HdM -> + umerge2_2(T1, T3, M, H1); +umerge3_2(T1, H1, [], _HdM, M, T3, H3) -> + umerge2_2(T1, T3, [H3 | M], H1). + +% H1 =< H2. Inlined. +umerge3_12(T1, H1, T2, H2, M, T3, H3, _HdM) when H1 =< H3 -> + umerge3_1(T1, H1, T2, H2, [H1 | M], T3, H3); +umerge3_12(T1, H1, T2, H2, M, T3, H3, HdM) when H3 == HdM -> + umerge3_12_3(T1, H1, T2, H2, M, T3); +umerge3_12(T1, H1, T2, H2, M, T3, H3, _HdM) -> + umerge3_12_3(T1, H1, T2, H2, [H3 | M], T3). + +% H1 =< H2, take L3 apart. +umerge3_12_3(T1, H1, T2, H2, M, [H3 | T3]) when H1 =< H3 -> + umerge3_1(T1, H1, T2, H2, [H1 | M], T3, H3); +umerge3_12_3(T1, H1, T2, H2, M, [H3 | T3]) -> + umerge3_12_3(T1, H1, T2, H2, [H3 | M], T3); +umerge3_12_3(T1, H1, T2, H2, M, []) -> + umerge2_1(T1, T2, [H1 | M], H1, H2). + +% H1 > H2. Inlined. +umerge3_21(T1, H1, T2, H2, M, T3, H3, _HdM) when H2 =< H3 -> + umerge3_2(T1, H1, T2, H2, [H2 | M], T3, H3); +umerge3_21(T1, H1, T2, H2, M, T3, H3, HdM) when H3 == HdM -> + umerge3_21_3(T1, H1, T2, H2, M, T3); +umerge3_21(T1, H1, T2, H2, M, T3, H3, _HdM) -> + umerge3_21_3(T1, H1, T2, H2, [H3 | M], T3). + +% H1 > H2, take L3 apart. +umerge3_21_3(T1, H1, T2, H2, M, [H3 | T3]) when H2 =< H3 -> + umerge3_2(T1, H1, T2, H2, [H2 | M], T3, H3); +umerge3_21_3(T1, H1, T2, H2, M, [H3 | T3]) -> + umerge3_21_3(T1, H1, T2, H2, [H3 | M], T3); +umerge3_21_3(T1, H1, T2, H2, M, []) -> + umerge2_2(T1, T2, [H2 | M], H1). + +%% Take L1 apart. +rumerge3_1([H1 | T1], T2, H2, M, T3, H3) when H1 =< H2 -> + rumerge3_12a(T1, H1, T2, H2, M, T3, H3); +rumerge3_1([H1 | T1], T2, H2, M, T3, H3) when H1 =< H3 -> + rumerge3_21_3(T1, T2, H2, M, T3, H3, H1); +rumerge3_1([H1 | T1], T2, H2, M, T3, H3) -> + rumerge3_1(T1, T2, H2, [H1 | M], T3, H3); +rumerge3_1([], T2, H2, M, T3, H3) when H2 =< H3 -> + rumerge2_2(T2, T3, M, H3, H2); +rumerge3_1([], T2, H2, M, T3, H3) -> + rumerge2_1(T2, T3, [H2 | M], H3). + +% H1 =< H2. Inlined. +rumerge3_12a(T1, H1, T2, H2, M, T3, H3) when H2 =< H3 -> + rumerge3_12_3(T1, T2, H2, M, T3, H3, H1); +rumerge3_12a(T1, H1, T2, H2, M, T3, H3) -> + rumerge3_2(T1, T2, H2, M, T3, H3, H1). + +%% Take L2 apart. H2M > H3. H2M > H2. +rumerge3_2(T1, [H2 | T2], H2M, M, T3, H3, H1) when H1 =< H2 -> + % H2M > H1. + rumerge3_12b(T1, H1, T2, H2, M, T3, H3, H2M); +rumerge3_2(T1, [H2 | T2], H2M, M, T3, H3, H1) when H1 == H2M -> + rumerge3_1(T1, T2, H2, [H1 | M], T3, H3); +rumerge3_2(T1, [H2 | T2], H2M, M, T3, H3, H1) when H1 =< H3 -> + % H2M > H1. + rumerge3_21_3(T1, T2, H2, [H2M | M], T3, H3, H1); +rumerge3_2(T1, [H2 | T2], H2M, M, T3, H3, H1) -> + % H2M > H1. + rumerge3_1(T1, T2, H2, [H1, H2M | M], T3, H3); +rumerge3_2(T1, [], H2M, M, T3, H3, H1) when H1 == H2M -> + rumerge2_1(T1, T3, [H1 | M], H3); +rumerge3_2(T1, [], H2M, M, T3, H3, H1) when H1 =< H3 -> + rumerge2_2(T1, T3, [H2M | M], H3, H1); +rumerge3_2(T1, [], H2M, M, T3, H3, H1) -> + rumerge2_1(T1, T3, [H1, H2M | M], H3). + +% H1 =< H2. Inlined. +rumerge3_12b(T1, H1, T2, H2, M, T3, H3, H2M) when H2 =< H3 -> + rumerge3_12_3(T1, T2, H2, [H2M | M], T3, H3, H1); +rumerge3_12b(T1, H1, T2, H2, M, T3, H3, H2M) -> + rumerge3_2(T1, T2, H2, [H2M | M], T3, H3, H1). + +% H1 =< H2, take L3 apart. +rumerge3_12_3(T1, T2, H2, M, [H3 | T3], H3M, H1) when H2 =< H3 -> + rumerge3_12_3(T1, T2, H2, [H3M | M], T3, H3, H1); +rumerge3_12_3(T1, T2, H2, M, [H3 | T3], H3M, H1) when H2 == H3M -> + rumerge3_2(T1, T2, H2, M, T3, H3, H1); +rumerge3_12_3(T1, T2, H2, M, [H3 | T3], H3M, H1) -> + rumerge3_2(T1, T2, H2, [H3M | M], T3, H3, H1); +rumerge3_12_3(T1, T2, H2, M, [], H3M, H1) when H2 == H3M -> + rumerge2_2(T1, T2, M, H2, H1); +rumerge3_12_3(T1, T2, H2, M, [], H3M, H1) -> + rumerge2_2(T1, T2, [H3M | M], H2, H1). + +% H1 > H2, take L3 apart. +rumerge3_21_3(T1, T2, H2, M, [H3 | T3], H3M, H1) when H1 =< H3 -> + rumerge3_21_3(T1, T2, H2, [H3M | M], T3, H3, H1); +rumerge3_21_3(T1, T2, H2, M, [H3 | T3], H3M, H1) when H1 == H3M -> + rumerge3_1(T1, T2, H2, [H1 | M], T3, H3); +rumerge3_21_3(T1, T2, H2, M, [H3 | T3], H3M, H1) -> + rumerge3_1(T1, T2, H2, [H1, H3M | M], T3, H3); +rumerge3_21_3(T1, T2, H2, M, [], H3M, H1) when H1 == H3M -> + rumerge2_1(T1, T2, [H1 | M], H2); +rumerge3_21_3(T1, T2, H2, M, [], H3M, H1) -> + rumerge2_1(T1, T2, [H1, H3M | M], H2). + +%% umerge/2 + +%% Elements from the first list are kept and prioritized. +umerge2_1([H1 | T1], T2, M, _HdM, H2) when H1 =< H2 -> + umerge2_1(T1, T2, [H1 | M], H1, H2); +umerge2_1([H1 | T1], T2, M, HdM, H2) when H2 == HdM -> + umerge2_2(T1, T2, M, H1); +umerge2_1([H1 | T1], T2, M, _HdM, H2) -> + umerge2_2(T1, T2, [H2 | M], H1); +umerge2_1([], T2, M, HdM, H2) when H2 == HdM -> + lists:reverse(T2, M); +umerge2_1([], T2, M, _HdM, H2) -> + lists:reverse(T2, [H2 | M]). + +umerge2_2(T1, [H2 | T2], M, H1) when H1 =< H2 -> + umerge2_1(T1, T2, [H1 | M], H1, H2); +umerge2_2(T1, [H2 | T2], M, H1) -> + umerge2_2(T1, T2, [H2 | M], H1); +umerge2_2(T1, [], M, H1) -> + lists:reverse(T1, [H1 | M]). + +%% rumerge/2 + +%% Elements from the first list are kept and prioritized. +rumerge2_1([H1 | T1], T2, M, H2) when H1 =< H2 -> + rumerge2_2(T1, T2, M, H2, H1); +rumerge2_1([H1 | T1], T2, M, H2) -> + rumerge2_1(T1, T2, [H1 | M], H2); +rumerge2_1([], T2, M, H2) -> + lists:reverse(T2, [H2 | M]). + +% H1 =< H2M. +rumerge2_2(T1, [H2 | T2], M, H2M, H1) when H1 =< H2 -> + rumerge2_2(T1, T2, [H2M | M], H2, H1); +rumerge2_2(T1, [H2 | T2], M, H2M, H1) when H1 == H2M -> + rumerge2_1(T1, T2, [H1 | M], H2); +rumerge2_2(T1, [H2 | T2], M, H2M, H1) -> + rumerge2_1(T1, T2, [H1, H2M | M], H2); +rumerge2_2(T1, [], M, H2M, H1) when H1 == H2M -> + lists:reverse(T1, [H1 | M]); +rumerge2_2(T1, [], M, H2M, H1) -> + lists:reverse(T1, [H1, H2M | M]). + +%% keysort/2 + +%% Ascending. +keysplit_1(I, X, EX, Y, EY, [Z | L], R, Rs) -> + case element(I, Z) of + EZ when EY =< EZ -> + keysplit_1(I, Y, EY, Z, EZ, L, [X | R], Rs); + EZ when EX =< EZ -> + keysplit_1(I, Z, EZ, Y, EY, L, [X | R], Rs); + _EZ when R == [] -> + keysplit_1(I, X, EX, Y, EY, L, [Z], Rs); + EZ -> + keysplit_1_1(I, X, EX, Y, EY, EZ, R, Rs, Z, L) + end; +keysplit_1(I, X, _EX, Y, _EY, [], R, Rs) -> + rkeymergel(I, [[Y, X | R] | Rs], [], asc). + +keysplit_1_1(I, X, EX, Y, EY, ES, R, Rs, S, [Z | L]) -> + case element(I, Z) of + EZ when EY =< EZ -> + keysplit_1_1(I, Y, EY, Z, EZ, ES, [X | R], Rs, S, L); + EZ when EX =< EZ -> + keysplit_1_1(I, Z, EZ, Y, EY, ES, [X | R], Rs, S, L); + EZ when ES =< EZ -> + keysplit_1(I, S, ES, Z, EZ, L, [], [[Y, X | R] | Rs]); + EZ -> + keysplit_1(I, Z, EZ, S, ES, L, [], [[Y, X | R] | Rs]) + end; +keysplit_1_1(I, X, _EX, Y, _EY, _ES, R, Rs, S, []) -> + rkeymergel(I, [[S], [Y, X | R] | Rs], [], asc). + +%% Descending. +keysplit_2(I, X, EX, Y, EY, [Z | L], R, Rs) -> + case element(I, Z) of + EZ when EY > EZ -> + keysplit_2(I, Y, EY, Z, EZ, L, [X | R], Rs); + EZ when EX > EZ -> + keysplit_2(I, Z, EZ, Y, EY, L, [X | R], Rs); + _EZ when R == [] -> + keysplit_2(I, X, EX, Y, EY, L, [Z], Rs); + EZ -> + keysplit_2_1(I, X, EX, Y, EY, EZ, R, Rs, Z, L) + end; +keysplit_2(I, X, _EX, Y, _EY, [], R, Rs) -> + keymergel(I, [[Y, X | R] | Rs], [], desc). + +keysplit_2_1(I, X, EX, Y, EY, ES, R, Rs, S, [Z | L]) -> + case element(I, Z) of + EZ when EY > EZ -> + keysplit_2_1(I, Y, EY, Z, EZ, ES, [X | R], Rs, S, L); + EZ when EX > EZ -> + keysplit_2_1(I, Z, EZ, Y, EY, ES, [X | R], Rs, S, L); + EZ when ES > EZ -> + keysplit_2(I, S, ES, Z, EZ, L, [], [[Y, X | R] | Rs]); + EZ -> + keysplit_2(I, Z, EZ, S, ES, L, [], [[Y, X | R] | Rs]) + end; +keysplit_2_1(I, X, _EX, Y, _EY, _ES, R, Rs, S, []) -> + keymergel(I, [[S], [Y, X | R] | Rs], [], desc). + +keymergel(I, [T1, [H2 | T2], [H3 | T3] | L], Acc, O) when O == asc -> + M = keymerge3_1(I, T1, [],O,element(I,H2), H2, T2, element(I,H3), H3, T3), + keymergel(I, L, [M | Acc], O); +keymergel(I, [[H3 | T3], [H2 | T2], T1 | L], Acc, O) when O == desc -> + M = keymerge3_1(I, T1, [],O,element(I,H2), H2, T2, element(I,H3), H3, T3), + keymergel(I, L, [M | Acc], O); +keymergel(I, [T1, [H2 | T2] | L], Acc, asc) -> + keymergel(I, L, [keymerge2_1(I, T1, element(I,H2),H2,T2,[]) | Acc], asc); +keymergel(I, [[H2 | T2], T1 | L], Acc, desc) -> + keymergel(I, L, [keymerge2_1(I, T1, element(I,H2),H2,T2,[]) | Acc], desc); +keymergel(_I, [L], [], _O) -> + L; +keymergel(I, [L], Acc, O) -> + rkeymergel(I, [lists:reverse(L, []) | Acc], [], O); +keymergel(I, [], Acc, O) -> + rkeymergel(I, Acc, [], O). + +rkeymergel(I, [[H3 | T3], [H2 | T2], T1 | L], Acc, O) when O == asc -> + M = rkeymerge3_1(I, T1, [],O,element(I,H2), H2, T2, element(I,H3), H3,T3), + rkeymergel(I, L, [M | Acc], O); +rkeymergel(I, [T1, [H2 | T2], [H3 | T3] | L], Acc, O) when O == desc -> + M = rkeymerge3_1(I, T1, [],O,element(I,H2), H2, T2, element(I,H3), H3,T3), + rkeymergel(I, L, [M | Acc], O); +rkeymergel(I, [[H2 | T2], T1 | L], Acc, asc) -> + rkeymergel(I, L, [rkeymerge2_1(I, T1, element(I,H2),H2,T2,[]) | Acc],asc); +rkeymergel(I, [T1, [H2 | T2] | L], Acc, desc) -> + rkeymergel(I, L, [rkeymerge2_1(I,T1, element(I,H2),H2,T2,[]) | Acc],desc); +rkeymergel(I, [L], Acc, O) -> + keymergel(I, [lists:reverse(L, []) | Acc], [], O); +rkeymergel(I, [], Acc, O) -> + keymergel(I, Acc, [], O). + +%%% An extra argument, D, just to avoid some move instructions. + +%% Take L1 apart. +keymerge3_1(I, [H1 | T1], M, D, E2, H2, T2, E3, H3, T3) -> + case element(I, H1) of + E1 when E1 =< E2 -> + keymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D); + E1 -> + keymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, T2) + end; +keymerge3_1(I, [], M, _D, E2, H2, T2, E3, H3, T3) when E2 =< E3 -> + keymerge2_1(I, T2, E3, H3, T3, [H2 | M]); +keymerge3_1(I, [], M, _D, E2, H2, T2, _E3, H3, T3) -> + keymerge2_2(I, T2, E2, H3, T3, M, H2). + +%% Take L2 apart. +keymerge3_2(I, E1, H1, T1, [H2 | T2], M, D, E3, H3, T3) -> + case element(I, H2) of + E2 when E1 =< E2 -> + keymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, T1); + E2 -> + keymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D) + end; +keymerge3_2(I, E1, H1, T1, [], M, _D, E3, H3, T3) when E1 =< E3 -> + keymerge2_1(I, T1, E3, H3, T3, [H1 | M]); +keymerge3_2(I, E1, H1, T1, [], M, _D, _E3, H3, T3) -> + keymerge2_2(I, T1, E1, H3, T3, M, H1). + +% E1 =< E2. Inlined. +keymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D) when E1 =< E3 -> + keymerge3_1(I, T1, [H1 | M], D, E2, H2, T2, E3, H3, T3); +keymerge3_12(I, E1, H1, T1, E2, H2, T2, _E3, H3, T3, M, _D) -> + keymerge3_12_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]). + +% E1 =< E2, take L3 apart. +keymerge3_12_3(I, E1, H1, T1, E2, H2, T2, [H3 | T3], M) -> + case element(I, H3) of + E3 when E1 =< E3 -> + keymerge3_1(I, T1, [H1 | M], T1, E2, H2, T2, E3, H3, T3); + _E3 -> + keymerge3_12_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]) + end; +keymerge3_12_3(I, _E1, H1, T1, E2, H2, T2, [], M) -> + keymerge2_1(I, T1, E2, H2, T2, [H1 | M]). + +% E1 > E2. Inlined. +keymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D) when E2 =< E3 -> + keymerge3_2(I, E1, H1, T1, T2, [H2 | M], D, E3, H3, T3); +keymerge3_21(I, E1, H1, T1, E2, H2, T2, _E3, H3, T3, M, _D) -> + keymerge3_21_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]). + +% E1 > E2, take L3 apart. +keymerge3_21_3(I, E1, H1, T1, E2, H2, T2, [H3 | T3], M) -> + case element(I, H3) of + E3 when E2 =< E3 -> + keymerge3_2(I, E1, H1, T1, T2, [H2 | M], T2, E3, H3, T3); + _E3 -> + keymerge3_21_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]) + end; +keymerge3_21_3(I, E1, H1, T1, _E2, H2, T2, [], M) -> + keymerge2_2(I, T1, E1, H2, T2, M, H1). + +%% Take L1 apart. +rkeymerge3_1(I, [H1 | T1], M, D, E2, H2, T2, E3, H3, T3) -> + case element(I, H1) of + E1 when E1 =< E2 -> + rkeymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, T2); + E1 -> + rkeymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D) + end; +rkeymerge3_1(I, [], M, _D, E2, H2, T2, E3, H3, T3) when E2 =< E3 -> + rkeymerge2_2(I, E2, T2, H3, T3, M, H2); +rkeymerge3_1(I, [], M, _D, _E2, H2, T2, E3, H3, T3) -> + rkeymerge2_1(I, T2, E3, H3, T3, [H2 | M]). + +%% Take L2 apart. +rkeymerge3_2(I, E1, H1, T1, [H2 | T2], M, D, E3, H3, T3) -> + case element(I, H2) of + E2 when E1 =< E2 -> + rkeymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D); + E2 -> + rkeymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, T1) + end; +rkeymerge3_2(I, E1, H1, T1, [], M, _D, E3, H3, T3) when E1 =< E3 -> + rkeymerge2_2(I, E1, T1, H3, T3, M, H1); +rkeymerge3_2(I, _E1, H1, T1, [], M, _D, E3, H3, T3) -> + rkeymerge2_1(I, T1, E3, H3, T3, [H1 | M]). + +% E1 =< E2. Inlined. +rkeymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, _D) when E2 =< E3 -> + rkeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]); +rkeymerge3_12(I, E1, H1, T1, _E2, H2, T2, E3, H3, T3, M, D) -> + rkeymerge3_2(I, E1, H1, T1, T2, [H2 | M], D, E3, H3, T3). + +% E1 =< E2, take L3 apart. +rkeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, [H3 | T3], M) -> + case element(I, H3) of + E3 when E2 =< E3 -> + rkeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]); + E3 -> + rkeymerge3_2(I, E1, H1, T1, T2, [H2 | M], T2, E3, H3, T3) + end; +rkeymerge3_12_3(I, E1, H1, T1, _E2, H2, T2, [], M) -> + rkeymerge2_2(I, E1, T1, H2, T2, M, H1). + +% E1 > E2. Inlined. +rkeymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, _D) when E1 =< E3 -> + rkeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]); +rkeymerge3_21(I, _E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D) -> + rkeymerge3_1(I, T1, [H1 | M], D, E2, H2, T2, E3, H3, T3). + +% E1 > E2, take L3 apart. +rkeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, [H3 | T3], M) -> + case element(I, H3) of + E3 when E1 =< E3 -> + rkeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]); + E3 -> + rkeymerge3_1(I, T1, [H1 | M], T1, E2, H2, T2, E3, H3, T3) + end; +rkeymerge3_21_3(I, _E1, H1, T1, E2, H2, T2, [], M) -> + rkeymerge2_1(I, T1, E2, H2, T2, [H1 | M]). + +%% keymerge/3 + +%% Elements from the first list are prioritized. +keymerge2_1(I, [H1 | T1], E2, H2, T2, M) -> + case element(I, H1) of + E1 when E1 =< E2 -> + keymerge2_1(I, T1, E2, H2, T2, [H1 | M]); + E1 -> + keymerge2_2(I, T1, E1, H2, T2, M, H1) + end; +keymerge2_1(_I, [], _E2, H2, T2, M) -> + lists:reverse(T2, [H2 | M]). + +keymerge2_2(I, T1, E1, HdM, [H2 | T2], M, H1) -> + case element(I, H2) of + E2 when E1 =< E2 -> + keymerge2_1(I, T1, E2, H2, T2, [H1, HdM | M]); + _E2 -> + keymerge2_2(I, T1, E1, H2, T2, [HdM | M], H1) + end; +keymerge2_2(_I, T1, _E1, HdM, [], M, H1) -> + lists:reverse(T1, [H1, HdM | M]). + +%% rkeymerge/3 + +rkeymerge2_1(I, [H1 | T1], E2, H2, T2, M) -> + case element(I, H1) of + E1 when E1 =< E2 -> + rkeymerge2_2(I, E1, T1, H2, T2, M, H1); + _E1 -> + rkeymerge2_1(I, T1, E2, H2, T2, [H1 | M]) + end; +rkeymerge2_1(_I, [], _E2, H2, T2, M) -> + lists:reverse(T2, [H2 | M]). + +rkeymerge2_2(I, E1, T1, HdM, [H2 | T2], M, H1) -> + case element(I, H2) of + E2 when E1 =< E2 -> + rkeymerge2_2(I, E1, T1, H2, T2, [HdM | M], H1); + E2 -> + rkeymerge2_1(I, T1, E2, H2, T2, [H1, HdM | M]) + end; +rkeymerge2_2(_I, _E1, T1, HdM, [], M, H1) -> + lists:reverse(T1, [H1, HdM | M]). + +%% ukeysort/2 + +%% Ascending. +ukeysplit_1(I, X, EX, Y, EY, [Z | L], R, Rs) -> + case element(I, Z) of + EZ when EY == EZ -> + ukeysplit_1(I, X, EX, Y, EY, L, R, Rs); + EZ when EY < EZ -> + ukeysplit_1(I, Y, EY, Z, EZ, L, [X | R], Rs); + EZ when EX == EZ -> + ukeysplit_1(I, X, EX, Y, EY, L, R, Rs); + EZ when EX < EZ -> + ukeysplit_1(I, Z, EZ, Y, EY, L, [X | R], Rs); + _EZ when R == [] -> + ukeysplit_1(I, X, EX, Y, EY, L, [Z], Rs); + EZ -> + ukeysplit_1_1(I, X, EX, Y, EY, L, R, Rs, Z, EZ) + end; +ukeysplit_1(I, X, _EX, Y, _EY, [], R, Rs) -> + rukeymergel(I, [[Y, X | R] | Rs], []). + +ukeysplit_1_1(I, X, EX, Y, EY, [Z | L], R, Rs, S, ES) -> + case element(I, Z) of + EZ when EY == EZ -> + ukeysplit_1_1(I, X, EX, Y, EY, L, R, Rs, S, ES); + EZ when EY < EZ -> + ukeysplit_1_1(I, Y, EY, Z, EZ, L, [X | R], Rs, S, ES); + EZ when EX == EZ -> + ukeysplit_1_1(I, X, EX, Y, EY, L, R, Rs, S, ES); + EZ when EX < EZ -> + ukeysplit_1_1(I, Z, EZ, Y, EY, L, [X | R], Rs, S, ES); + EZ when ES == EZ -> + ukeysplit_1_1(I, X, EX, Y, EY, L, R, Rs, S, ES); + EZ when ES < EZ -> + ukeysplit_1(I, S, ES, Z, EZ, L, [], [[Y, X | R] | Rs]); + EZ -> + ukeysplit_1(I, Z, EZ, S, ES, L, [], [[Y, X | R] | Rs]) + end; +ukeysplit_1_1(I, X, _EX, Y, _EY, [], R, Rs, S, _ES) -> + rukeymergel(I, [[S], [Y, X | R] | Rs], []). + +%% Descending. +ukeysplit_2(I, Y, EY, [Z | L], R) -> + case element(I, Z) of + EZ when EY == EZ -> + ukeysplit_2(I, Y, EY, L, R); + EZ when EY < EZ -> + ukeysplit_1(I, Y, EY, Z, EZ, L, [], [lists:reverse(R, [])]); + EZ -> + ukeysplit_2(I, Z, EZ, L, [Y | R]) + end; +ukeysplit_2(_I, Y, _EY, [], R) -> + [Y | R]. + +ukeymergel(I, [T1, [H2 | T2], [H3 | T3] | L], Acc) -> + %% The fourth argument, [H2 | H3] (=HdM), may confuse type + %% checkers. Its purpose is to ensure that the tests H2 == HdM + %% and H3 == HdM in ukeymerge3_1 will always fail as long as M == []. + M = ukeymerge3_1(I, T1, Acc, [H2 | H3], element(I, H2), H2, T2, [], + element(I, H3), H3, T3), + ukeymergel(I, L, [M | Acc]); +ukeymergel(I, [[H1 | T1], T2 | L], Acc) -> + ukeymergel(I, L, [ukeymerge2_2(I, T1, element(I, H1), H1, T2, []) | Acc]); +ukeymergel(_I, [L], []) -> + L; +ukeymergel(I, [L], Acc) -> + rukeymergel(I, [lists:reverse(L, []) | Acc], []); +ukeymergel(I, [], Acc) -> + rukeymergel(I, Acc, []). + +rukeymergel(I, [[H3 | T3], [H2 | T2], T1 | L], Acc) -> + M = rukeymerge3_1(I, T1, Acc, [], element(I, H2), H2, T2, [], + element(I, H3), H3, T3), + rukeymergel(I, L, [M | Acc]); +rukeymergel(I, [[H2 | T2], T1 | L], Acc) -> + rukeymergel(I, L, [rukeymerge2_1(I, T1, element(I,H2), T2, [], H2)|Acc]); +rukeymergel(I, [L], Acc) -> + ukeymergel(I, [lists:reverse(L, []) | Acc], []); +rukeymergel(I, [], Acc) -> + ukeymergel(I, Acc, []). + +%%% An extra argument, D, just to avoid some move instructions. + +%% Take L1 apart. +ukeymerge3_1(I, [H1 | T1], D, HdM, E2, H2, T2, M, E3, H3, T3) -> + case element(I, H1) of + E1 when E1 =< E2 -> + ukeymerge3_12(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, HdM, D); + E1 when E2 == HdM -> + ukeymerge3_2(I, E1, T1, H1, T2, HdM, T2, M, E3, H3, T3); + E1 -> + ukeymerge3_21(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, HdM, T2) + end; +ukeymerge3_1(I, [], _D, HdM, E2, _H2, T2, M, E3, H3, T3) when E2 == HdM -> + ukeymerge2_1(I, T2, E3, HdM, T3, M, H3); +ukeymerge3_1(I, [], _D, _HdM, E2, H2, T2, M, E3, H3, T3) when E2 =< E3 -> + ukeymerge2_1(I, T2, E3, E2, T3, [H2 | M], H3); +ukeymerge3_1(I, [], _D, HdM, E2, H2, T2, M, E3, _H3, T3) when E3 == HdM -> + ukeymerge2_2(I, T2, E2, H2, T3, M); +ukeymerge3_1(I, [], _D, _HdM, E2, H2, T2, M, _E3, H3, T3) -> + ukeymerge2_2(I, T2, E2, H2, T3, [H3 | M]). + +%% Take L2 apart. +ukeymerge3_2(I, E1, T1, H1, [H2 | T2], HdM, D, M, E3, H3, T3) -> + case element(I, H2) of + E2 when E1 =< E2 -> + ukeymerge3_12(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, HdM, T1); + E2 -> + ukeymerge3_21(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, HdM, D) + end; +ukeymerge3_2(I, E1, T1, H1, [], _HdM, _D, M, E3, H3, T3) when E1 =< E3 -> + ukeymerge2_1(I, T1, E3, E1, T3, [H1 | M], H3); +ukeymerge3_2(I, E1, T1, H1, [], HdM, _D, M, E3, _H3, T3) when E3 == HdM -> + ukeymerge2_2(I, T1, E1, H1, T3, M); +ukeymerge3_2(I, E1, T1, H1, [], _HdM, _D, M, _E3, H3, T3) -> + ukeymerge2_2(I, T1, E1, H1, T3, [H3 | M]). + +% E1 =< E2. Inlined. +ukeymerge3_12(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, _HdM, D) + when E1 =< E3 -> + ukeymerge3_1(I, T1, D, E1, E2, H2, T2, [H1 | M], E3, H3, T3); +ukeymerge3_12(I, E1, T1, H1, E2, H2, T2, E3, _H3, T3, M, HdM, _D) + when E3 == HdM -> + ukeymerge3_12_3(I, E1, T1, H1, E2, H2, T2, M, T3); +ukeymerge3_12(I, E1, T1, H1, E2, H2, T2, _E3, H3, T3, M, _HdM, _D) -> + ukeymerge3_12_3(I, E1, T1, H1, E2, H2, T2, [H3 | M], T3). + +% E1 =< E2, take L3 apart. +ukeymerge3_12_3(I, E1, T1, H1, E2, H2, T2, M, [H3 | T3]) -> + case element(I, H3) of + E3 when E1 =< E3 -> + ukeymerge3_1(I, T1, T1, E1, E2, H2, T2, [H1 | M], E3, H3, T3); + _E3 -> + ukeymerge3_12_3(I, E1, T1, H1, E2, H2, T2, [H3 | M], T3) + end; +ukeymerge3_12_3(I, E1, T1, H1, E2, H2, T2, M, []) -> + ukeymerge2_1(I, T1, E2, E1, T2, [H1 | M], H2). + +% E1 > E2. Inlined. +ukeymerge3_21(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, _HdM, D) + when E2 =< E3 -> + ukeymerge3_2(I, E1, T1, H1, T2, E2, D, [H2 | M], E3, H3, T3); +ukeymerge3_21(I, E1, T1, H1, E2, H2, T2, E3, _H3, T3, M, HdM, _D) + when E3 == HdM -> + ukeymerge3_21_3(I, E1, T1, H1, E2, H2, T2, M, T3); +ukeymerge3_21(I, E1, T1, H1, E2, H2, T2, _E3, H3, T3, M, _HdM, _D) -> + ukeymerge3_21_3(I, E1, T1, H1, E2, H2, T2, [H3 | M], T3). + +% E1 > E2, take L3 apart. +ukeymerge3_21_3(I, E1, T1, H1, E2, H2, T2, M, [H3 | T3]) -> + case element(I, H3) of + E3 when E2 =< E3 -> + ukeymerge3_2(I, E1, T1, H1, T2, E2, T2, [H2 | M], E3, H3, T3); + _E3 -> + ukeymerge3_21_3(I, E1, T1, H1, E2, H2, T2, [H3 | M], T3) + end; +ukeymerge3_21_3(I, E1, T1, H1, _E2, H2, T2, M, []) -> + ukeymerge2_2(I, T1, E1, H1, T2, [H2 | M]). + +%%% Two extra arguments, D1 and D2, just to avoid some move instructions. + +%% Take L1 apart. +rukeymerge3_1(I, [H1 | T1], D1, D2, E2, H2, T2, M, E3, H3, T3) -> + case element(I, H1) of + E1 when E1 =< E2 -> + rukeymerge3_12a(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M); + E1 -> + rukeymerge3_21a(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D1, D2) + end; +rukeymerge3_1(I, [], _D1, _D2, E2, H2, T2, M, E3, H3, T3) when E2 =< E3 -> + rukeymerge2_2(I, T2, E2, T3, M, E3, H3, H2); +rukeymerge3_1(I, [], _D1, _D2, _E2, H2, T2, M, E3, H3, T3) -> + rukeymerge2_1(I, T2, E3, T3, [H2 | M], H3). + +% E1 =< E2. Inlined. +rukeymerge3_12a(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M) when E2 =< E3 -> + rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, M, E3, H3, T3); +rukeymerge3_12a(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M) -> + rukeymerge3_2(I, E1, H1, T1, T2, H2, E2, M, E3, H3, T3). + +% E1 > E2. Inlined +rukeymerge3_21a(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, _D1, _D2) + when E1 =< E3 -> + rukeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, M, E3, H3, T3); +rukeymerge3_21a(I, _E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D1, D2) -> + rukeymerge3_1(I, T1, D1, D2, E2, H2, T2, [H1 | M], E3, H3, T3). + +%% Take L2 apart. E2M > E3. E2M > E2. +rukeymerge3_2(I, E1, H1, T1, [H2 | T2], H2M, E2M, M, E3, H3, T3) -> + case element(I, H2) of + E2 when E1 =< E2 -> + % E2M > E1. + rukeymerge3_12b(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, H2M); + E2 when E1 == E2M -> + rukeymerge3_1(I, T1, H1, T1, E2, H2, T2, [H1 | M], E3, H3, T3); + E2 -> + % E2M > E1. + rukeymerge3_21b(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, H2M) + end; +rukeymerge3_2(I, E1, H1, T1, [], _H2M, E2M, M, E3, H3, T3) when E1 == E2M -> + rukeymerge2_1(I, T1, E3, T3, [H1 | M], H3); +rukeymerge3_2(I, E1, H1, T1, [], H2M, _E2M, M, E3, H3, T3) when E1 =< E3 -> + rukeymerge2_2(I, T1, E1, T3, [H2M | M], E3, H3, H1); +rukeymerge3_2(I, _E1, H1, T1, [], H2M, _E2M, M, E3, H3, T3) -> + rukeymerge2_1(I, T1, E3, T3, [H1, H2M | M], H3). + +% E1 =< E2. Inlined. +rukeymerge3_12b(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, H2M) + when E2 =< E3 -> + rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, [H2M | M], E3, H3, T3); +rukeymerge3_12b(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, H2M) -> + rukeymerge3_2(I, E1, H1, T1, T2, H2, E2, [H2M | M], E3, H3, T3). + +% E1 > E2. Inlined +rukeymerge3_21b(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M,H2M) when E1 =< E3 -> + rukeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, [H2M | M], E3, H3, T3); +rukeymerge3_21b(I, _E1, H1, T1, E2, H2, T2, E3, H3, T3, M, H2M) -> + rukeymerge3_1(I, T1, H1, T1, E2, H2, T2, [H1, H2M | M], E3, H3, T3). + +% E1 =< E2, take L3 apart. +rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, M, E3M, H3M, [H3 | T3]) -> + case element(I, H3) of + E3 when E2 =< E3 -> + rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, [H3M | M], E3, H3, T3); + E3 when E2 == E3M -> + rukeymerge3_2(I, E1, H1, T1, T2, H2, E2, M, E3, H3, T3); + E3 -> + rukeymerge3_2(I, E1, H1, T1, T2, H2, E2, [H3M | M], E3, H3, T3) + end; +rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, M, E3M, _H3M, []) when E2 == E3M -> + rukeymerge2_2(I, T1, E1, T2, M, E2, H2, H1); +rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, M, _E3M, H3M, []) -> + rukeymerge2_2(I, T1, E1, T2, [H3M | M], E2, H2, H1). + +% E1 > E2, take L3 apart. +rukeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, M, E3M, H3M, [H3 | T3]) -> + case element(I, H3) of + E3 when E1 =< E3 -> + rukeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, [H3M | M], E3, H3, T3); + E3 when E1 == E3M -> + rukeymerge3_1(I, T1, H1, T1, E2, H2, T2, [H1 | M], E3, H3, T3); + E3 -> + rukeymerge3_1(I, T1, H1, T1, E2, H2, T2, [H1,H3M | M], E3, H3, T3) + end; +rukeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, M, E3M, _H3M, []) when E1 == E3M -> + rukeymerge2_1(I, T1, E2, T2, [H1 | M], H2); +rukeymerge3_21_3(I, _E1, H1, T1, E2, H2, T2, M, _E3M, H3M, []) -> + rukeymerge2_1(I, T1, E2, T2, [H1, H3M | M], H2). + +%% ukeymerge/3 + +%% Elements from the first list are kept and prioritized. +ukeymerge2_1(I, [H1 | T1], E2, HdM, T2, M, H2) -> + case element(I, H1) of + E1 when E1 =< E2 -> + ukeymerge2_1(I, T1, E2, E1, T2, [H1 | M], H2); + E1 when E2 == HdM -> + ukeymerge2_2(I, T1, E1, H1, T2, M); + E1 -> + ukeymerge2_2(I, T1, E1, H1, T2, [H2 | M]) + end; +ukeymerge2_1(_I, [], E2, HdM, T2, M, _H2) when E2 == HdM -> + lists:reverse(T2, M); +ukeymerge2_1(_I, [], _E2, _HdM, T2, M, H2) -> + lists:reverse(T2, [H2 | M]). + +ukeymerge2_2(I, T1, E1, H1, [H2 | T2], M) -> + case element(I, H2) of + E2 when E1 =< E2 -> + ukeymerge2_1(I, T1, E2, E1, T2, [H1 | M], H2); + _E2 -> + ukeymerge2_2(I, T1, E1, H1, T2, [H2 | M]) + end; +ukeymerge2_2(_I, T1, _E1, H1, [], M) -> + lists:reverse(T1, [H1 | M]). + +%% rukeymerge/3 + +rukeymerge2_1(I, [H1 | T1], E2, T2, M, H2) -> + case element(I, H1) of + E1 when E1 =< E2 -> + rukeymerge2_2(I, T1, E1, T2, M, E2, H2, H1); + _E1 -> + rukeymerge2_1(I, T1, E2, T2, [H1 | M], H2) + end; +rukeymerge2_1(_I, [], _E2, T2, M, H2) -> + lists:reverse(T2, [H2 | M]). + +rukeymerge2_2(I, T1, E1, [H2 | T2], M, E2M, H2M, H1) -> + case element(I, H2) of + E2 when E1 =< E2 -> + rukeymerge2_2(I, T1, E1, T2, [H2M | M], E2, H2, H1); + E2 when E1 == E2M -> + rukeymerge2_1(I, T1, E2, T2, [H1 | M], H2); + E2 -> + rukeymerge2_1(I, T1, E2, T2, [H1, H2M | M], H2) + end; +rukeymerge2_2(_I, T1, E1, [], M, E2M, _H2M, H1) when E1 == E2M -> + lists:reverse(T1, [H1 | M]); +rukeymerge2_2(_I, T1, _E1, [], M, _E2M, H2M, H1) -> + lists:reverse(T1, [H1, H2M | M]). + +%% sort/2 + +%% Ascending. +fsplit_1(Y, X, Fun, [Z | L], R, Rs) -> + case Fun(Y, Z) of + true -> + fsplit_1(Z, Y, Fun, L, [X | R], Rs); + false -> + case Fun(X, Z) of + true -> + fsplit_1(Y, Z, Fun, L, [X | R], Rs); + false when R == [] -> + fsplit_1(Y, X, Fun, L, [Z], Rs); + false -> + fsplit_1_1(Y, X, Fun, L, R, Rs, Z) + end + end; +fsplit_1(Y, X, Fun, [], R, Rs) -> + rfmergel([[Y, X | R] | Rs], [], Fun, asc). + +fsplit_1_1(Y, X, Fun, [Z | L], R, Rs, S) -> + case Fun(Y, Z) of + true -> + fsplit_1_1(Z, Y, Fun, L, [X | R], Rs, S); + false -> + case Fun(X, Z) of + true -> + fsplit_1_1(Y, Z, Fun, L, [X | R], Rs, S); + false -> + case Fun(S, Z) of + true -> + fsplit_1(Z, S, Fun, L, [], [[Y, X | R] | Rs]); + false -> + fsplit_1(S, Z, Fun, L, [], [[Y, X | R] | Rs]) + end + end + end; +fsplit_1_1(Y, X, Fun, [], R, Rs, S) -> + rfmergel([[S], [Y, X | R] | Rs], [], Fun, asc). + +%% Descending. +fsplit_2(Y, X, Fun, [Z | L], R, Rs) -> + case Fun(Y, Z) of + false -> + fsplit_2(Z, Y, Fun, L, [X | R], Rs); + true -> + case Fun(X, Z) of + false -> + fsplit_2(Y, Z, Fun, L, [X | R], Rs); + true when R == [] -> + fsplit_2(Y, X, Fun, L, [Z], Rs); + true -> + fsplit_2_1(Y, X, Fun, L, R, Rs, Z) + end + end; +fsplit_2(Y, X, Fun, [], R, Rs) -> + fmergel([[Y, X | R] | Rs], [], Fun, desc). + +fsplit_2_1(Y, X, Fun, [Z | L], R, Rs, S) -> + case Fun(Y, Z) of + false -> + fsplit_2_1(Z, Y, Fun, L, [X | R], Rs, S); + true -> + case Fun(X, Z) of + false -> + fsplit_2_1(Y, Z, Fun, L, [X | R], Rs, S); + true -> + case Fun(S, Z) of + false -> + fsplit_2(Z, S, Fun, L, [], [[Y, X | R] | Rs]); + true -> + fsplit_2(S, Z, Fun, L, [], [[Y, X | R] | Rs]) + end + end + end; +fsplit_2_1(Y, X, Fun, [], R, Rs, S) -> + fmergel([[S], [Y, X | R] | Rs], [], Fun, desc). + +fmergel([T1, [H2 | T2] | L], Acc, Fun, asc) -> + fmergel(L, [fmerge2_1(T1, H2, Fun, T2, []) | Acc], Fun, asc); +fmergel([[H2 | T2], T1 | L], Acc, Fun, desc) -> + fmergel(L, [fmerge2_1(T1, H2, Fun, T2, []) | Acc], Fun, desc); +fmergel([L], [], _Fun, _O) -> + L; +fmergel([L], Acc, Fun, O) -> + rfmergel([lists:reverse(L, []) | Acc], [], Fun, O); +fmergel([], Acc, Fun, O) -> + rfmergel(Acc, [], Fun, O). + +rfmergel([[H2 | T2], T1 | L], Acc, Fun, asc) -> + rfmergel(L, [rfmerge2_1(T1, H2, Fun, T2, []) | Acc], Fun, asc); +rfmergel([T1, [H2 | T2] | L], Acc, Fun, desc) -> + rfmergel(L, [rfmerge2_1(T1, H2, Fun, T2, []) | Acc], Fun, desc); +rfmergel([L], Acc, Fun, O) -> + fmergel([lists:reverse(L, []) | Acc], [], Fun, O); +rfmergel([], Acc, Fun, O) -> + fmergel(Acc, [], Fun, O). + +%% merge/3 + +%% Elements from the first list are prioritized. +fmerge2_1([H1 | T1], H2, Fun, T2, M) -> + case Fun(H1, H2) of + true -> + fmerge2_1(T1, H2, Fun, T2, [H1 | M]); + false -> + fmerge2_2(H1, T1, Fun, T2, [H2 | M]) + end; +fmerge2_1([], H2, _Fun, T2, M) -> + lists:reverse(T2, [H2 | M]). + +fmerge2_2(H1, T1, Fun, [H2 | T2], M) -> + case Fun(H1, H2) of + true -> + fmerge2_1(T1, H2, Fun, T2, [H1 | M]); + false -> + fmerge2_2(H1, T1, Fun, T2, [H2 | M]) + end; +fmerge2_2(H1, T1, _Fun, [], M) -> + lists:reverse(T1, [H1 | M]). + +%% rmerge/3 + +rfmerge2_1([H1 | T1], H2, Fun, T2, M) -> + case Fun(H1, H2) of + true -> + rfmerge2_2(H1, T1, Fun, T2, [H2 | M]); + false -> + rfmerge2_1(T1, H2, Fun, T2, [H1 | M]) + end; +rfmerge2_1([], H2, _Fun, T2, M) -> + lists:reverse(T2, [H2 | M]). + +rfmerge2_2(H1, T1, Fun, [H2 | T2], M) -> + case Fun(H1, H2) of + true -> + rfmerge2_2(H1, T1, Fun, T2, [H2 | M]); + false -> + rfmerge2_1(T1, H2, Fun, T2, [H1 | M]) + end; +rfmerge2_2(H1, T1, _Fun, [], M) -> + lists:reverse(T1, [H1 | M]). + +%% usort/2 + +%% Ascending. X < Y +ufsplit_1(Y, X, Fun, [Z | L], R, Rs) -> + case Fun(Y, Z) of + true -> + case Fun(Z, Y) of + true -> % Z equal to Y + ufsplit_1(Y, X, Fun, L, R, Rs); + false -> + ufsplit_1(Z, Y, Fun, L, [X | R], Rs) + end; + false -> + case Fun(X, Z) of + true -> + case Fun(Z, X) of + true -> % Z equal to X + ufsplit_1(Y, X, Fun, L, R, Rs); + false -> + ufsplit_1(Y, Z, Fun, L, [X | R], Rs) + end; + false when R == [] -> + ufsplit_1(Y, X, Fun, L, [Z], Rs); + false -> + ufsplit_1_1(Y, X, Fun, L, R, Rs, Z) + end + end; +ufsplit_1(Y, X, Fun, [], R, Rs) -> + rufmergel([[Y, X | R] | Rs], [], Fun). + +%% X < Y +ufsplit_1_1(Y, X, Fun, [Z | L], R, Rs, S) -> + case Fun(Y, Z) of + true -> + case Fun(Z, Y) of + true -> % Z equal to Y + ufsplit_1_1(Y, X, Fun, L, R, Rs, S); + false -> + ufsplit_1_1(Z, Y, Fun, L, [X | R], Rs, S) + end; + false -> + case Fun(X, Z) of + true -> + case Fun(Z, X) of + true -> % Z equal to X + ufsplit_1_1(Y, X, Fun, L, R, Rs, S); + false -> + ufsplit_1_1(Y, Z, Fun, L, [X | R], Rs, S) + end; + false -> + case Fun(S, Z) of + true -> + case Fun(Z, S) of + true -> % Z equal to S + ufsplit_1_1(Y, X, Fun, L, R, Rs, S); + false -> + ufsplit_1(Z, S, Fun, L, [], [[Y, X | R] | Rs]) + end; + false -> + ufsplit_1(S, Z, Fun, L, [], [[Y, X | R] | Rs]) + end + end + end; +ufsplit_1_1(Y, X, Fun, [], R, Rs, S) -> + rufmergel([[S], [Y, X | R] | Rs], [], Fun). + +%% Descending. +ufsplit_2(Y, [Z | L], Fun, R) -> + case Fun(Y, Z) of + true -> + case Fun(Z, Y) of + true -> % Z equal to Y + ufsplit_2(Y, L, Fun, R); + false -> + ufsplit_1(Z, Y, Fun, L, [], [lists:reverse(R, [])]) + end; + false -> + ufsplit_2(Z, L, Fun, [Y | R]) + end; +ufsplit_2(Y, [], _Fun, R) -> + [Y | R]. + +ufmergel([[H1 | T1], T2 | L], Acc, Fun) -> + ufmergel(L, [ufmerge2_2(H1, T1, Fun, T2, []) | Acc], Fun); +ufmergel([L], [], _Fun) -> + L; +ufmergel([L], Acc, Fun) -> + rufmergel([lists:reverse(L, []) | Acc], [], Fun); +ufmergel([], Acc, Fun) -> + rufmergel(Acc, [], Fun). + +rufmergel([[H2 | T2], T1 | L], Acc, Fun) -> + rufmergel(L, [rufmerge2_1(T1, H2, Fun, T2, []) | Acc], Fun); +rufmergel([L], Acc, Fun) -> + ufmergel([lists:reverse(L, []) | Acc], [], Fun); +rufmergel([], Acc, Fun) -> + ufmergel(Acc, [], Fun). + +%% umerge/3 + +%% Elements from the first list are kept and prioritized. +%% HdM before H2. +ufmerge2_1([H1 | T1], H2, Fun, T2, M, HdM) -> + case Fun(H1, H2) of + true -> + ufmerge2_1(T1, H2, Fun, T2, [H1 | M], H1); + false -> + case Fun(H2, HdM) of + true -> % HdM equal to H2 + ufmerge2_2(H1, T1, Fun, T2, M); + false -> + ufmerge2_2(H1, T1, Fun, T2, [H2 | M]) + end + end; +ufmerge2_1([], H2, Fun, T2, M, HdM) -> + case Fun(H2, HdM) of + true -> % HdM equal to H2 + lists:reverse(T2, M); + false -> + lists:reverse(T2, [H2 | M]) + end. + +ufmerge2_2(H1, T1, Fun, [H2 | T2], M) -> + case Fun(H1, H2) of + true -> + ufmerge2_1(T1, H2, Fun, T2, [H1 | M], H1); + false -> + ufmerge2_2(H1, T1, Fun, T2, [H2 | M]) + end; +ufmerge2_2(H1, T1, _Fun, [], M) -> + lists:reverse(T1, [H1 | M]). + +%% rumerge/3 + +rufmerge2_1([H1 | T1], H2, Fun, T2, M) -> + case Fun(H1, H2) of + true -> + rufmerge2_2(H1, T1, Fun, T2, M, H2); + false -> + rufmerge2_1(T1, H2, Fun, T2, [H1 | M]) + end; +rufmerge2_1([], H2, _Fun, T2, M) -> + lists:reverse(T2, [H2 | M]). + +%% H1 before H2M +rufmerge2_2(H1, T1, Fun, [H2 | T2], M, H2M) -> + case Fun(H1, H2) of + true -> + rufmerge2_2(H1, T1, Fun, T2, [H2M | M], H2); + false -> + case Fun(H2M, H1) of + true -> % H2M equal to H1 + rufmerge2_1(T1, H2, Fun, T2, [H1 | M]); + false -> + rufmerge2_1(T1, H2, Fun, T2, [H1, H2M | M]) + end + end; +rufmerge2_2(H1, T1, Fun, [], M, H2M) -> + case Fun(H2M, H1) of + true -> + lists:reverse(T1, [H1 | M]); + false -> + lists:reverse(T1, [H1, H2M | M]) + end. + |