lists.erl

来自「OTP是开放电信平台的简称」· ERL 代码 · 共 2,008 行 · 第 1/5 页

keydelete3(_, _, []) -> [].

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(_, _, [], _) -> [].

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]).

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).
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.

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].

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).
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.

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) -> [].

keymap(Fun, ExtraArgs, Index, [Tup|Tail]) ->
   [setelement(Index, Tup, apply(Fun, [element(Index, Tup)|ExtraArgs]))|
    keymap(Fun, ExtraArgs, Index, Tail)];
keymap(Fun, _ , _, []) when is_function(Fun) -> [].


%%% Suggestion from OTP-2948: sort and merge with Fun.
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.

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).
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.

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.
                    
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).
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

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

umerge(L) ->
    umergel(L).

%% umerge3(X, Y, Z) -> L
%%  merges three sorted lists X, Y and Z without duplicates, 
%%  removes duplicates

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

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

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).
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.

all(Pred, [Hd|Tail]) ->
    case Pred(Hd) of
	true -> all(Pred, Tail);
	false -> false
    end;
all(Pred, []) when is_function(Pred, 1) -> true. 

any(Pred, [Hd|Tail]) ->
    case Pred(Hd) of
	true -> true;
	false -> any(Pred, Tail)
    end;
any(Pred, []) when is_function(Pred, 1) -> false. 

map(F, [H|T]) ->
    [F(H)|map(F, T)];
map(F, []) when is_function(F, 1) -> [].

flatmap(F, [Hd|Tail]) ->
    F(Hd) ++ flatmap(F, Tail);
flatmap(F, []) when is_function(F, 1) -> [].

foldl(F, Accu, [Hd|Tail]) ->
    foldl(F, F(Hd, Accu), Tail);
foldl(F, Accu, []) when is_function(F, 2) -> Accu.

foldr(F, Accu, [Hd|Tail]) ->
    F(Hd, foldr(F, Accu, Tail));
foldr(F, Accu, []) when is_function(F, 2) -> Accu.

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'.