diff options
Diffstat (limited to 'lib/stdlib/src/lists.erl')
-rw-r--r-- | lib/stdlib/src/lists.erl | 534 |
1 files changed, 389 insertions, 145 deletions
diff --git a/lib/stdlib/src/lists.erl b/lib/stdlib/src/lists.erl index d2cb5aab3c..cb1c008ed1 100644 --- a/lib/stdlib/src/lists.erl +++ b/lib/stdlib/src/lists.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 1996-2022. All Rights Reserved. +%% Copyright Ericsson AB 1996-2023. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. @@ -29,7 +29,7 @@ %% arguments. Please keep in alphabetical order. -export([append/1, append/2, concat/1, delete/2, droplast/1, duplicate/2, - enumerate/1, enumerate/2, + enumerate/1, enumerate/2, enumerate/3, flatlength/1, flatten/1, flatten/2, join/2, last/1, min/1, max/1, nth/2, nthtail/2, @@ -37,7 +37,7 @@ split/2, sublist/2, sublist/3, subtract/2, suffix/2, sum/1, uniq/1, unzip/1, unzip3/1, - zip/2, zip3/3]). + zip/2, zip/3, zip3/3, zip3/4]). %% Functions taking a list of tuples and a position within the tuple. -export([keydelete/3, keyreplace/4, keymap/3, @@ -60,7 +60,7 @@ map/2, mapfoldl/3, mapfoldr/3, partition/2, search/2, splitwith/2, takewhile/2, uniq/2, - zipwith/3, zipwith3/4]). + zipwith/3, zipwith/4, zipwith3/4, zipwith3/5]). %% Undocumented, but used within Erlang/OTP. -export([zf/2]). @@ -196,8 +196,12 @@ reverse([A, B | L]) -> T :: term(). nth(1, [H|_]) -> H; -nth(N, [_|T]) when N > 1 -> - nth(N - 1, T). +nth(N, [_|_]=L) when is_integer(N), N > 1 -> + nth_1(N, L). + +nth_1(1, [H|_]) -> H; +nth_1(N, [_|T]) -> + nth_1(N - 1, T). -spec nthtail(N, List) -> Tail when N :: non_neg_integer(), @@ -205,10 +209,15 @@ nth(N, [_|T]) when N > 1 -> Tail :: [T], T :: term(). +nthtail(0, []) -> []; +nthtail(0, [_|_]=L) -> L; nthtail(1, [_|T]) -> T; -nthtail(N, [_|T]) when N > 1 -> - nthtail(N - 1, T); -nthtail(0, L) when is_list(L) -> L. +nthtail(N, [_|_]=L) when is_integer(N), N > 1 -> + nthtail_1(N, L). + +nthtail_1(1, [_|T]) -> T; +nthtail_1(N, [_|T]) -> + nthtail_1(N - 1, T). %% prefix(Prefix, List) -> (true | false) @@ -416,8 +425,35 @@ delete(_, []) -> []. A :: term(), B :: term(). -zip([X | Xs], [Y | Ys]) -> [{X, Y} | zip(Xs, Ys)]; -zip([], []) -> []. +zip(Xs, Ys) -> zip(Xs, Ys, fail). + +-spec zip(List1, List2, How) -> List3 when + List1 :: [A], + List2 :: [B], + List3 :: [{A | DefaultA, B | DefaultB}], + A :: term(), + B :: term(), + How :: 'fail' | 'trim' | {'pad', {DefaultA, DefaultB}}, + DefaultA :: term(), + DefaultB :: term(). + +zip([X | Xs], [Y | Ys], How) -> + [{X, Y} | zip(Xs, Ys, How)]; +zip([], [], fail) -> + []; +zip([], [], trim) -> + []; +zip([], [], {pad, {_, _}}) -> + []; +zip([_ | _], [], trim) -> + []; +zip([], [_ | _], trim) -> + []; +zip([], [_ | _]=Ys, {pad, {X, _}}) -> + [{X, Y} || Y <- Ys]; +zip([_ | _]=Xs, [], {pad, {_, Y}}) -> + [{X, Y} || X <- Xs]. + %% Return {[X0, X1, ..., Xn], [Y0, Y1, ..., Yn]}, for a list [{X0, Y0}, %% {X1, Y1}, ..., {Xn, Yn}]. @@ -446,8 +482,43 @@ unzip([], Xs, Ys) -> {reverse(Xs), reverse(Ys)}. B :: term(), C :: term(). -zip3([X | Xs], [Y | Ys], [Z | Zs]) -> [{X, Y, Z} | zip3(Xs, Ys, Zs)]; -zip3([], [], []) -> []. +zip3(Xs, Ys, Zs) -> zip3(Xs, Ys, Zs, fail). + +-spec zip3(List1, List2, List3, How) -> List4 when + List1 :: [A], + List2 :: [B], + List3 :: [C], + List4 :: [{A | DefaultA, B | DefaultB, C | DefaultC}], + A :: term(), + B :: term(), + C :: term(), + How :: 'fail' | 'trim' | {'pad', {DefaultA, DefaultB, DefaultC}}, + DefaultA :: term(), + DefaultB :: term(), + DefaultC :: term(). + +zip3([X | Xs], [Y | Ys], [Z | Zs], How) -> + [{X, Y, Z} | zip3(Xs, Ys, Zs, How)]; +zip3([], [], [], fail) -> + []; +zip3([], [], [], trim) -> + []; +zip3(Xs, Ys, Zs, trim) when is_list(Xs), is_list(Ys), is_list(Zs) -> + []; +zip3([], [], [], {pad, {_, _, _}}) -> + []; +zip3([], [], [_ |_]=Zs, {pad, {X, Y, _}}) -> + [{X, Y, Z} || Z <- Zs]; +zip3([], [_ | _]=Ys, [], {pad, {X, _, Z}}) -> + [{X, Y, Z} || Y <- Ys]; +zip3([_ | _]=Xs, [], [], {pad, {_, Y, Z}}) -> + [{X, Y, Z} || X <- Xs]; +zip3([], [Y | Ys], [Z | Zs], {pad, {X, _, _}} = How) -> + [{X, Y, Z} | zip3([], Ys, Zs, How)]; +zip3([X | Xs], [], [Z | Zs], {pad, {_, Y, _}} = How) -> + [{X, Y, Z} | zip3(Xs, [], Zs, How)]; +zip3([X | Xs], [Y | Ys], [], {pad, {_, _, Z}} = How) -> + [{X, Y, Z} | zip3(Xs, Ys, [], How)]. %% Return {[X0, X1, ..., Xn], [Y0, Y1, ..., Yn], [Z0, Z1, ..., Zn]}, for %% a list [{X0, Y0, Z0}, {X1, Y1, Z1}, ..., {Xn, Yn, Zn}]. @@ -480,8 +551,36 @@ unzip3([], Xs, Ys, Zs) -> Y :: term(), T :: term(). -zipwith(F, [X | Xs], [Y | Ys]) -> [F(X, Y) | zipwith(F, Xs, Ys)]; -zipwith(F, [], []) when is_function(F, 2) -> []. +zipwith(F, Xs, Ys) -> zipwith(F, Xs, Ys, fail). + +-spec zipwith(Combine, List1, List2, How) -> List3 when + Combine :: fun((X | DefaultX, Y | DefaultY) -> T), + List1 :: [X], + List2 :: [Y], + List3 :: [T], + X :: term(), + Y :: term(), + How :: 'fail' | 'trim' | {'pad', {DefaultX, DefaultY}}, + DefaultX :: term(), + DefaultY :: term(), + T :: term(). + +zipwith(F, [X | Xs], [Y | Ys], How) -> + [F(X, Y) | zipwith(F, Xs, Ys, How)]; +zipwith(F, [], [], fail) when is_function(F, 2) -> + []; +zipwith(F, [], [], trim) when is_function(F, 2) -> + []; +zipwith(F, [], [], {pad, {_, _}}) when is_function(F, 2) -> + []; +zipwith(F, [_ | _], [], trim) when is_function(F, 2) -> + []; +zipwith(F, [], [_ | _], trim) when is_function(F, 2) -> + []; +zipwith(F, [], [_ | _]=Ys, {pad, {X, _}}) -> + [F(X, Y) || Y <- Ys]; +zipwith(F, [_ | _]=Xs, [], {pad, {_, Y}}) -> + [F(X, Y) || X <- Xs]. %% 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]. @@ -497,9 +596,45 @@ zipwith(F, [], []) when is_function(F, 2) -> []. Z :: term(), T :: term(). -zipwith3(F, [X | Xs], [Y | Ys], [Z | Zs]) -> - [F(X, Y, Z) | zipwith3(F, Xs, Ys, Zs)]; -zipwith3(F, [], [], []) when is_function(F, 3) -> []. +zipwith3(F, Xs, Ys, Zs) -> zipwith3(F, Xs, Ys, Zs, fail). + +-spec zipwith3(Combine, List1, List2, List3, How) -> List4 when + Combine :: fun((X | DefaultX, Y | DefaultY, Z | DefaultZ) -> T), + List1 :: [X], + List2 :: [Y], + List3 :: [Z], + List4 :: [T], + X :: term(), + Y :: term(), + Z :: term(), + How :: 'fail' | 'trim' | {'pad', {DefaultX, DefaultY, DefaultZ}}, + DefaultX :: term(), + DefaultY :: term(), + DefaultZ :: term(), + T :: term(). + +zipwith3(F, [X | Xs], [Y | Ys], [Z | Zs], How) -> + [F(X, Y, Z) | zipwith3(F, Xs, Ys, Zs, How)]; +zipwith3(F, [], [], [], fail) when is_function(F, 3) -> + []; +zipwith3(F, [], [], [], trim) when is_function(F, 3) -> + []; +zipwith3(F, Xs, Ys, Zs, trim) when is_function(F, 3), is_list(Xs), is_list(Ys), is_list(Zs) -> + []; +zipwith3(F, [], [], [], {pad, {_, _, _}}) when is_function(F, 3) -> + []; +zipwith3(F, [], [], [_ | _]=Zs, {pad, {X, Y, _}}) -> + [F(X, Y, Z) || Z <- Zs]; +zipwith3(F, [], [_ | _]=Ys, [], {pad, {X, _, Z}}) -> + [F(X, Y, Z) || Y <- Ys]; +zipwith3(F, [_ | _]=Xs, [], [], {pad, {_, Y, Z}}) -> + [F(X, Y, Z) || X <- Xs]; +zipwith3(F, [], [Y | Ys], [Z | Zs], {pad, {X, _, _}} = How) -> + [F(X, Y, Z) | zipwith3(F, [], Ys, Zs, How)]; +zipwith3(F, [X | Xs], [], [Z | Zs], {pad, {_, Y, _}} = How) -> + [F(X, Y, Z) | zipwith3(F, Xs, [], Zs, How)]; +zipwith3(F, [X | Xs], [Y | Ys], [], {pad, {_, _, Z}} = How) -> + [F(X, Y, Z) | zipwith3(F, Xs, Ys, [], How)]. %% sort(List) -> L %% sorts the list L @@ -575,24 +710,44 @@ merge(L) -> Y :: term(), Z :: term(). -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), []). +merge3([_|_]=L1, [H2 | T2], [H3 | T3]) -> + lists:reverse(merge3_1(L1, [], H2, T2, H3, T3), []); +merge3([_|_]=L1, [_|_]=L2, []) -> + merge(L1, L2); +merge3([_|_]=L1, [], [_|_]=L3) -> + merge(L1, L3); +merge3([_|_]=L1, [], []) -> + L1; +merge3([], [_|_]=L2, [_|_]=L3) -> + merge(L2, L3); +merge3([], [_|_]=L2, []) -> + L2; +merge3([], [], [_|_]=L3) -> + L3; +merge3([], [], []) -> + []. %% rmerge3(X, Y, Z) -> L %% merges three reversed sorted lists X, Y and Z -spec rmerge3([X], [Y], [Z]) -> [(X | Y | Z)]. -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), []). +rmerge3([_|_]=L1, [H2 | T2], [H3 | T3]) -> + lists:reverse(rmerge3_1(L1, [], H2, T2, H3, T3), []); +rmerge3([_|_]=L1, [_|_]=L2, []) -> + rmerge(L1, L2); +rmerge3([_|_]=L1, [], [_|_]=L3) -> + rmerge(L1, L3); +rmerge3([_|_]=L1, [], []) -> + L1; +rmerge3([], [_|_]=L2, [_|_]=L3) -> + rmerge(L2, L3); +rmerge3([], [_|_]=L2, []) -> + L2; +rmerge3([], [], [_|_]=L3) -> + L3; +rmerge3([], [], []) -> + []. %% merge(X, Y) -> L %% merges two sorted lists X and Y @@ -604,10 +759,14 @@ rmerge3(L1, [H2 | T2], [H3 | T3]) -> X :: term(), Y :: term(). -merge(T1, []) -> - T1; -merge(T1, [H2 | T2]) -> - lists:reverse(merge2_1(T1, H2, T2, []), []). +merge([_|_]=T1, [H2 | T2]) -> + lists:reverse(merge2_1(T1, H2, T2, []), []); +merge([_|_]=L1, []) -> + L1; +merge([], [_|_]=L2) -> + L2; +merge([], []) -> + []. %% rmerge(X, Y) -> L %% merges two reversed sorted lists X and Y @@ -616,10 +775,14 @@ merge(T1, [H2 | T2]) -> -spec rmerge([X], [Y]) -> [(X | Y)]. -rmerge(T1, []) -> - T1; -rmerge(T1, [H2 | T2]) -> - lists:reverse(rmerge2_1(T1, H2, T2, []), []). +rmerge([_|_]=T1, [H2 | T2]) -> + lists:reverse(rmerge2_1(T1, H2, T2, []), []); +rmerge([_|_]=L1, []) -> + L1; +rmerge([], [_|_]=L2) -> + L2; +rmerge([], []) -> + []. %% concat(L) concatenate the list representation of the elements %% in L - the elements in L can be atoms, numbers of strings. @@ -845,30 +1008,38 @@ keysort_1(_I, X, _EX, [], R) -> T2 :: Tuple, Tuple :: 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. +keymerge(Index, L1, L2) when is_integer(Index), Index > 0 -> + keymerge_1(Index, L1, L2). + +keymerge_1(Index, [_|_]=T1, [H2 | T2]) -> + E2 = element(Index, H2), + M = keymerge2_1(Index, T1, E2, H2, T2, []), + lists:reverse(M, []); +keymerge_1(_Index, [_|_]=L1, []) -> + L1; +keymerge_1(_Index, [], [_|_]=L2) -> + L2; +keymerge_1(_Index, [], []) -> + []. %% reverse(rkeymerge(I,reverse(A),reverse(B))) is equal to keymerge(I,A,B). -spec rkeymerge(pos_integer(), [X], [Y]) -> [R] when X :: tuple(), Y :: tuple(), 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. +rkeymerge(Index, L1, L2) when is_integer(Index), Index > 0 -> + rkeymerge_1(Index, L1, L2). + +rkeymerge_1(Index, [_|_]=T1, [H2 | T2]) -> + E2 = element(Index, H2), + M = rkeymerge2_1(Index, T1, E2, H2, T2, []), + lists:reverse(M, []); +rkeymerge_1(_Index, [_|_]=L1, []) -> + L1; +rkeymerge_1(_Index, [], [_|_]=L2) -> + L2; +rkeymerge_1(_Index, [], []) -> + []. -spec ukeysort(N, TupleList1) -> TupleList2 when N :: pos_integer(), @@ -948,30 +1119,38 @@ ukeysort_1(_I, X, _EX, []) -> T2 :: Tuple, Tuple :: 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. +ukeymerge(Index, L1, L2) when is_integer(Index), Index > 0 -> + ukeymerge_1(Index, L1, L2). + +ukeymerge_1(Index, [H1 | T1], [_|_]=T2) -> + E1 = element(Index, H1), + M = ukeymerge2_2(Index, T1, E1, H1, T2, []), + lists:reverse(M, []); +ukeymerge_1(_Index, [_|_]=L1, []) -> + L1; +ukeymerge_1(_Index, [], [_|_]=L2) -> + L2; +ukeymerge_1(_Index, [], []) -> + []. %% reverse(rukeymerge(I,reverse(A),reverse(B))) is equal to ukeymerge(I,A,B). -spec rukeymerge(pos_integer(), [X], [Y]) -> [(X | Y)] when X :: tuple(), 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. +rukeymerge(Index, L1, L2) when is_integer(Index), Index > 0 -> + rukeymerge_1(Index, L1, L2). + +rukeymerge_1(Index, [_|_]=T1, [H2 | T2]) -> + E2 = element(Index, H2), + M = rukeymerge2_1(Index, T1, E2, T2, [], H2), + lists:reverse(M, []); +rukeymerge_1(_Index, [_|_]=L1, []) -> + L1; +rukeymerge_1(_Index, [], [_|_]=L2) -> + L2; +rukeymerge_1(_Index, [], []) -> + []. -spec keymap(Fun, N, TupleList1) -> TupleList2 when Fun :: fun((Term1 :: term()) -> Term2 :: term()), @@ -990,20 +1169,29 @@ keymap(Fun, Index, []) when is_integer(Index), Index >= 1, List2 :: [{Index, T}], Index :: integer(), T :: term(). -enumerate(List1) when is_list(List1) -> - enumerate_1(1, List1). +enumerate(List1) -> + enumerate(1, 1, List1). -spec enumerate(Index, List1) -> List2 when List1 :: [T], List2 :: [{Index, T}], Index :: integer(), T :: term(). -enumerate(Index, List1) when is_integer(Index), is_list(List1) -> - enumerate_1(Index, List1). +enumerate(Index, List1) -> + enumerate(Index, 1, List1). -enumerate_1(Index, [H|T]) -> - [{Index, H}|enumerate_1(Index + 1, T)]; -enumerate_1(_Index, []) -> +-spec enumerate(Index, Step, List1) -> List2 when + List1 :: [T], + List2 :: [{Index, T}], + Index :: integer(), + Step :: integer(), + T :: term(). +enumerate(Index, Step, List1) when is_integer(Index), is_integer(Step) -> + enumerate_1(Index, Step, List1). + +enumerate_1(Index, Step, [H|T]) -> + [{Index, H}|enumerate_1(Index + Step, Step, T)]; +enumerate_1(_Index, _Step, []) -> []. %%% Suggestion from OTP-2948: sort and merge with Fun. @@ -1034,19 +1222,33 @@ sort(Fun, [X, Y | T]) -> A :: term(), B :: term(). -merge(Fun, T1, [H2 | T2]) when is_function(Fun, 2) -> +merge(Fun, L1, L2) when is_function(Fun, 2) -> + merge_1(Fun, L1, L2). + +merge_1(Fun, [_|_]=T1, [H2 | T2]) -> lists:reverse(fmerge2_1(T1, H2, Fun, T2, []), []); -merge(Fun, T1, []) when is_function(Fun, 2) -> - T1. +merge_1(_Fun, [_|_]=L1, []) -> + L1; +merge_1(_Fun, [], [_|_]=L2) -> + L2; +merge_1(_Fun, [], []) -> + []. %% reverse(rmerge(F,reverse(A),reverse(B))) is equal to merge(F,A,B). -spec rmerge(fun((X, Y) -> boolean()), [X], [Y]) -> [(X | Y)]. -rmerge(Fun, T1, [H2 | T2]) when is_function(Fun, 2) -> +rmerge(Fun, L1, L2) when is_function(Fun, 2) -> + rmerge_1(Fun, L1, L2). + +rmerge_1(Fun, [_|_]=T1, [H2 | T2]) -> lists:reverse(rfmerge2_1(T1, H2, Fun, T2, []), []); -rmerge(Fun, T1, []) when is_function(Fun, 2) -> - T1. +rmerge_1(_Fun, [_|_]=L1, []) -> + L1; +rmerge_1(_Fun, [], [_|_]=L2) -> + L2; +rmerge_1(_Fun, [], []) -> + []. -spec usort(Fun, List1) -> List2 when Fun :: fun((T, T) -> boolean()), @@ -1087,19 +1289,33 @@ usort_1(Fun, X, [Y | L]) -> A :: term(), B :: term(). -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, []), []). +umerge(Fun, L1, L2) when is_function(Fun, 2) -> + umerge_1(Fun, L1, L2). + +umerge_1(Fun, [H1 | T1], [_|_]=T2) -> + lists:reverse(ufmerge2_2(H1, T1, Fun, T2, []), []); +umerge_1(_Fun, [_|_]=L1, []) -> + L1; +umerge_1(_Fun, [], [_|_]=L2) -> + L2; +umerge_1(_Fun, [], []) -> + []. %% reverse(rumerge(F,reverse(A),reverse(B))) is equal to umerge(F,A,B). -spec rumerge(fun((X, Y) -> boolean()), [X], [Y]) -> [(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, []), []). +rumerge(Fun, L1, L2) when is_function(Fun, 2) -> + rumerge_1(Fun, L1, L2). + +rumerge_1(Fun, [_|_]=T1, [H2 | T2]) -> + lists:reverse(rufmerge2_1(T1, H2, Fun, T2, []), []); +rumerge_1(_Fun, [_|_]=L1, []) -> + L1; +rumerge_1(_Fun, [], [_|_]=L2) -> + L2; +rumerge_1(_Fun, [], []) -> + []. %% usort(List) -> L %% sorts the list L, removes duplicates @@ -1184,12 +1400,22 @@ umerge(L) -> Y :: term(), Z :: term(). -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), []). +umerge3([_|_]=L1, [H2 | T2], [H3 | T3]) -> + lists:reverse(umerge3_1(L1, [H2 | H3], T2, H2, [], T3, H3), []); +umerge3([_|_]=L1, [_|_]=L2, []) -> + umerge(L1, L2); +umerge3([_|_]=L1, [], [_|_]=L3) -> + umerge(L1, L3); +umerge3([_|_]=L1, [], []) -> + L1; +umerge3([], [_|_]=L2, [_|_]=L3) -> + umerge(L2, L3); +umerge3([], [_|_]=L2, []) -> + L2; +umerge3([], [], [_|_]=L3) -> + L3; +umerge3([], [], []) -> + []. %% rumerge3(X, Y, Z) -> L %% merges three reversed sorted lists X, Y and Z without duplicates, @@ -1197,12 +1423,22 @@ umerge3(L1, [H2 | T2], [H3 | T3]) -> -spec rumerge3([X], [Y], [Z]) -> [(X | Y | Z)]. -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),[]). +rumerge3([_|_]=L1, [H2 | T2], [H3 | T3]) -> + lists:reverse(rumerge3_1(L1, T2, H2, [], T3, H3),[]); +rumerge3([_|_]=L1, [_|_]=L2, []) -> + rumerge(L1, L2); +rumerge3([_|_]=L1, [], [_|_]=L3) -> + rumerge(L1, L3); +rumerge3([_|_]=L1, [], []) -> + L1; +rumerge3([], [_|_]=L2, [_|_]=L3) -> + rumerge(L2, L3); +rumerge3([], [_|_]=L2, []) -> + L2; +rumerge3([], [], [_|_]=L3) -> + L3; +rumerge3([], [], []) -> + []. %% umerge(X, Y) -> L %% merges two sorted lists X and Y without duplicates, removes duplicates @@ -1214,10 +1450,14 @@ rumerge3(L1, [H2 | T2], [H3 | T3]) -> X :: term(), Y :: term(). -umerge([], T2) -> - T2; -umerge([H1 | T1], T2) -> - lists:reverse(umerge2_2(T1, T2, [], H1), []). +umerge([H1 | T1], [_|_]=T2) -> + lists:reverse(umerge2_2(T1, T2, [], H1), []); +umerge([_|_]=L1, []) -> + L1; +umerge([], [_|_]=L2) -> + L2; +umerge([], []) -> + []. %% rumerge(X, Y) -> L %% merges two reversed sorted lists X and Y without duplicates, @@ -1227,10 +1467,14 @@ umerge([H1 | T1], T2) -> -spec rumerge([X], [Y]) -> [(X | Y)]. -rumerge(T1, []) -> - T1; -rumerge(T1, [H2 | T2]) -> - lists:reverse(rumerge2_1(T1, T2, [], H2), []). +rumerge([_|_]=T1, [H2 | T2]) -> + lists:reverse(rumerge2_1(T1, T2, [], H2), []); +rumerge([_|_]=L1, []) -> + L1; +rumerge([], [_|_]=L2) -> + L2; +rumerge([], []) -> + []. %% all(Predicate, List) %% any(Predicate, List) @@ -1663,24 +1907,24 @@ split_2_1(X, Y, [], R, Rs, S) -> %% 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([[_|_]=L], []) -> + L; mergel([], Acc) -> rmergel(Acc, []); -mergel([A, [] | L], Acc) -> +mergel([[] | L], Acc) -> + mergel(L, Acc); +mergel([[_|_]=L], Acc) -> + rmergel([lists:reverse(L, []) | Acc], []); +mergel([[_|_]=A, [] | L], Acc) -> mergel([A | L], Acc); -mergel([A, B, [] | L], Acc) -> - mergel([A, B | L], Acc). +mergel([[_|_]=A, [_|_]=B, [] | L], Acc) -> + mergel([A, B | 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], []). rmergel([[H3 | T3], [H2 | T2], T1 | L], Acc) -> rmergel(L, [rmerge3_1(T1, [], H2, T2, H3, T3) | Acc]); @@ -1896,28 +2140,28 @@ usplit_2_1(X, Y, [], R, Rs, S) -> umergel(L) -> umergel(L, [], asc). +umergel([], [], _O) -> + []; +umergel([[_|_]=L], [], _O) -> + L; +umergel([], Acc, O) -> + rumergel(Acc, [], O); +umergel([[_|_]=L], Acc, O) -> + rumergel([lists:reverse(L, []) | Acc], [], O); 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 | L], Acc, O); -umergel([A, B, [] | L], Acc, O) -> +umergel([[_|_]=A, [_|_]=B, [] | L], Acc, O) -> umergel([A, B | L], Acc, O); -umergel([[H1 | T1], T2 | L], Acc, asc) -> +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([[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). +umergel([[_|_]=T2, [H1 | T1] | L], Acc, desc) -> + umergel(L, [umerge2_2(T1, T2, [], H1) | Acc], desc). rumergel([[H3 | T3], [H2 | T2], T1 | L], Acc, asc) -> rumergel(L, [rumerge3_1(T1, T2, H2, [], T3, H3) | Acc], asc); |