sofs.erl

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

    reverse(L).

weak1([E={X,Y} | Es], Ys, L, X0) when X > Y, X == X0 ->
    weak1(Es, Ys, [E | L], X);
weak1([E={X,Y} | Es], Ys, L, X0) when X == Y, X == X0 ->
    weak2(Es, Ys, [E | L], X);
weak1([E={X,_Y} | Es], Ys, L, X0) when X == X0 -> % when X < Y
    weak2(Es, Ys, [E, {X,X} | L], X);
weak1(Es, Ys, L, X) ->
    weak(Es, Ys, [{X,X} | L]).

weak2([E={X,_Y} | Es], Ys, L, X0) when X == X0 -> % when X < _Y 
    weak2(Es, Ys, [E | L], X);
weak2(Es, Ys, L, _X) ->
    weak(Es, Ys, L).

extc(L, [D | Ds], C, Ts) ->
    extc(L, Ds, C, Ts, D);
extc(L, [], _C, _Ts) ->
    L.

extc(L, Ds, C, [{X,_Y} | Ts], D) when X < D ->
    extc(L, Ds, C, Ts, D);
extc(L, Ds, C, [{X,_Y} | Ts], D) when X == D ->
    extc(L, Ds, C, Ts);
extc(L, Ds, C, [{X,_Y} | Ts], D) ->
    extc2([{D,C} | L], Ds, C, Ts, X);
extc(L, Ds, C, [], D) ->
    extc_tail([{D,C} | L], Ds, C).

extc2(L, [D | Ds], C, Ts, X) when X > D ->
    extc2([{D,C} | L], Ds, C, Ts, X);
extc2(L, [D | Ds], C, Ts, X) when X == D ->
    extc(L, Ds, C, Ts);
extc2(L, [D | Ds], C, Ts, _X) ->
    extc(L, Ds, C, Ts, D);
extc2(L, [], _C, _Ts, _X) ->
    L.

extc_tail(L, [D | Ds], C) ->
    extc_tail([{D,C} | L], Ds, C);
extc_tail(L, [], _C) ->
    L.

is_a_func([{E,_} | Es], E0) when E /= E0 ->
    is_a_func(Es, E);
is_a_func(L, _E) ->
    L =:= [].

restrict_n(I, [T | Ts], Key, Keys, L) ->
    case element(I, T) of
	K when K < Key ->
	    restrict_n(I, Ts, Key, Keys, L);
	K when K == Key ->
	    restrict_n(I, Ts, Key, Keys, [T | L]);
	K ->
	    restrict_n(I, K, Ts, Keys, L, T)
    end;
restrict_n(_I, _Ts, _Key, _Keys, L) ->
    L.
    
restrict_n(I, K, Ts, [Key | Keys], L, E) when K > Key ->
    restrict_n(I, K, Ts, Keys, L, E);
restrict_n(I, K, Ts, [Key | Keys], L, E) when K == Key ->
    restrict_n(I, Ts, Key, Keys, [E | L]);
restrict_n(I, _K, Ts, [Key | Keys], L, _E) ->
    restrict_n(I, Ts, Key, Keys, L);
restrict_n(_I, _K, _Ts, _Keys, L, _E) ->
    L.

restrict([Key | Keys], Tuples) ->
    restrict(Tuples, Key, Keys, []);
restrict(_Keys, _Tuples) ->
    [].

restrict([{K,_E} | Ts], Key, Keys, L) when K < Key ->
    restrict(Ts, Key, Keys, L);
restrict([{K,E} | Ts], Key, Keys, L) when K == Key ->
    restrict(Ts, Key, Keys, [E | L]);
restrict([{K,E} | Ts], _Key, Keys, L) ->
    restrict(Ts, K, Keys, L, E);
restrict(_Ts, _Key, _Keys, L) ->
    L.
    
restrict(Ts, K, [Key | Keys], L, E) when K > Key ->
    restrict(Ts, K, Keys, L, E);
restrict(Ts, K, [Key | Keys], L, E) when K == Key ->
    restrict(Ts, Key, Keys, [E | L]);
restrict(Ts, _K, [Key | Keys], L, _E) ->
    restrict(Ts, Key, Keys, L);
restrict(_Ts, _K, _Keys, L, _E) ->
    L.

diff_restrict_n(I, [T | Ts], Key, Keys, L) ->
    case element(I, T) of
	K when K < Key ->
	    diff_restrict_n(I, Ts, Key, Keys, [T | L]);
	K when K == Key ->
	    diff_restrict_n(I, Ts, Key, Keys, L);
	K ->
	    diff_restrict_n(I, K, Ts, Keys, L, T)
    end;
diff_restrict_n(I, _Ts, _Key, _Keys, L) when I =:= 1 ->
    reverse(L);
diff_restrict_n(_I, _Ts, _Key, _Keys, L) ->
    sort(L).
    
diff_restrict_n(I, K, Ts, [Key | Keys], L, T) when K > Key ->
    diff_restrict_n(I, K, Ts, Keys, L, T);
diff_restrict_n(I, K, Ts, [Key | Keys], L, _T) when K == Key ->
    diff_restrict_n(I, Ts, Key, Keys, L);
diff_restrict_n(I, _K, Ts, [Key | Keys], L, T) ->
    diff_restrict_n(I, Ts, Key, Keys, [T | L]);
diff_restrict_n(I, _K, Ts, _Keys, L, T) when I =:= 1 ->
    reverse(L, [T | Ts]);
diff_restrict_n(_I, _K, Ts, _Keys, L, T) ->
    sort([T | Ts ++ L]).

diff_restrict([Key | Keys], Tuples) ->
    diff_restrict(Tuples, Key, Keys, []);
diff_restrict(_Keys, Tuples) ->
    diff_restrict_tail(Tuples, []).

diff_restrict([{K,E} | Ts], Key, Keys, L) when K < Key ->
    diff_restrict(Ts, Key, Keys, [E | L]);
diff_restrict([{K,_E} | Ts], Key, Keys, L) when K == Key ->
    diff_restrict(Ts, Key, Keys, L);
diff_restrict([{K,E} | Ts], _Key, Keys, L) ->
    diff_restrict(Ts, K, Keys, L, E);
diff_restrict(_Ts, _Key, _Keys, L) ->
    L.
    
diff_restrict(Ts, K, [Key | Keys], L, E) when K > Key ->
    diff_restrict(Ts, K, Keys, L, E);
diff_restrict(Ts, K, [Key | Keys], L, _E) when K == Key ->
    diff_restrict(Ts, Key, Keys, L);
diff_restrict(Ts, _K, [Key | Keys], L, E) ->
    diff_restrict(Ts, Key, Keys, [E | L]);
diff_restrict(Ts, _K, _Keys, L, E) ->
    diff_restrict_tail(Ts, [E | L]).

diff_restrict_tail([{_K,E} | Ts], L) ->
    diff_restrict_tail(Ts, [E | L]);
diff_restrict_tail(_Ts, L) ->
    L.

comp([], B) ->
    check_function(B, []);
comp(_A, []) ->
    bad_function;
comp(A0, [{Bx,By} | B]) ->
    A = converse(A0, []),
    check_function(A0, comp1(A, B, [], Bx, By)).

comp1([{Ay,Ax} | A], B, L, Bx, By) when Ay == Bx ->
    comp1(A, B, [{Ax,By} | L], Bx, By);
comp1([{Ay,Ax} | A], B, L, Bx, _By) when Ay > Bx ->
    comp2(A, B, L, Bx, Ay, Ax);
comp1([{Ay,_Ax} | _A], _B, _L, Bx, _By) when Ay < Bx ->
    bad_function;
comp1([], B, L, Bx, _By) ->
    check_function(Bx, B, L).

comp2(A, [{Bx,_By} | B], L, Bx0, Ay, Ax) when Ay > Bx, Bx /= Bx0 ->
    comp2(A, B, L, Bx, Ay, Ax);
comp2(A, [{Bx,By} | B], L, _Bx0, Ay, Ax) when Ay == Bx ->
    comp1(A, B, [{Ax,By} | L], Bx, By);
comp2(_A, _B, _L, _Bx0, _Ay, _Ax) ->
    bad_function.

inverse1([{A,B} | X]) ->
    inverse(X, A, [{B,A}]);
inverse1([]) ->
    [].

inverse([{A,B} | X], A0, L) when A0 /= A ->
    inverse(X, A, [{B,A} | L]);
inverse([{A,_B} | _X], A0, _L) when A0 == A ->
    bad_function;
inverse([], _A0, L) ->
    SL = [{V,_} | Es] = sort(L),
    case is_a_func(Es, V) of
	true -> SL;
	false -> bad_function
    end.

%% Inlined.
external_fun({external, Function}) when is_atom(Function) ->
    false;
external_fun({external, Fun}) ->
    Fun;
external_fun(_) -> 
    false.

%% Inlined.
element_type(?SET_OF(Type)) -> Type;
element_type(Type) -> Type.

subst(Ts, Fun, Type) ->
    subst(Ts, Fun, Type, ?ANYTYPE, []).

subst([T | Ts], Fun, Type, NType, L) ->
    case setfun(T, Fun, Type, NType) of
	{SD, ST} -> subst(Ts, Fun, Type, ST, [{T, SD} | L]);
	Bad -> Bad
    end;
subst([], _Fun, _Type, NType, L) ->
    {L, NType}.

projection1([E | Es]) ->
    projection1([], element(1, E), Es);
projection1([] = L) ->
    L.

projection1(L, X, [E | Es]) ->
    case element(1, E) of
	X1 when X == X1 -> projection1(L, X, Es);
	X1 -> projection1([X | L], X1, Es)
    end;
projection1(L, X, []) ->
    reverse(L, [X]).

projection_n([E | Es], I, L) ->
    projection_n(Es, I, [element(I, E) | L]);
projection_n([], _I, L) ->
    usort(L).

substitute_element([T | Ts], I, L) ->
    substitute_element(Ts, I, [{T, element(I, T)} | L]);
substitute_element(_, _I, L) ->
    reverse(L).

substitute([T | Ts], Fun, L) ->
    substitute(Ts, Fun, [{T, Fun(T)} | L]);
substitute(_, _Fun, L) ->
    reverse(L).

partition_n(I, [E | Ts]) ->
    partition_n(I, Ts, element(I, E), [E], []);
partition_n(_I, []) ->
    [].

partition_n(I, [E | Ts], K, Es, P) ->
    case {element(I, E), Es} of
	{K1, _} when K == K1 ->
	    partition_n(I, Ts, K, [E | Es], P);
	{K1, [_]} -> % optimization
	    partition_n(I, Ts, K1, [E], [Es | P]);
	{K1, _} ->
	    partition_n(I, Ts, K1, [E], [reverse(Es) | P])
    end;
partition_n(I, [], _K, Es, P) when I > 1 ->
    sort([reverse(Es) | P]);
partition_n(_I, [], _K, [_] = Es, P) -> % optimization
    reverse(P, [Es]);
partition_n(_I, [], _K, Es, P) ->
    reverse(P, [reverse(Es)]).

partition3_n(I, [T | Ts], Key, Keys, L1, L2)  ->
    case element(I, T) of
	K when K < Key ->
	    partition3_n(I, Ts, Key, Keys, L1, [T | L2]);
	K when K == Key ->
	    partition3_n(I, Ts, Key, Keys, [T | L1], L2);
	K ->
	    partition3_n(I, K, Ts, Keys, L1, L2, T)
    end;
partition3_n(I, _Ts, _Key, _Keys, L1, L2) when I =:= 1 ->
    [reverse(L1) | reverse(L2)];
partition3_n(_I, _Ts, _Key, _Keys, L1, L2) ->
    [sort(L1) | sort(L2)].
    
partition3_n(I, K, Ts, [Key | Keys], L1, L2, T) when K > Key ->
    partition3_n(I, K, Ts, Keys, L1, L2, T);
partition3_n(I, K, Ts, [Key | Keys], L1, L2, T) when K == Key ->
    partition3_n(I, Ts, Key, Keys, [T | L1], L2);
partition3_n(I, _K, Ts, [Key | Keys], L1, L2, T) ->
    partition3_n(I, Ts, Key, Keys, L1, [T | L2]);
partition3_n(I, _K, Ts, _Keys, L1, L2, T) when I =:= 1 ->
    [reverse(L1) | reverse(L2, [T | Ts])];
partition3_n(_I, _K, Ts, _Keys, L1, L2, T) ->
    [sort(L1) | sort([T | Ts ++ L2])].

partition3([Key | Keys], Tuples) ->
    partition3(Tuples, Key, Keys, [], []);
partition3(_Keys, Tuples) ->
    partition3_tail(Tuples, [], []).

partition3([{K,E} | Ts], Key, Keys, L1, L2) when K < Key ->
    partition3(Ts, Key, Keys, L1, [E | L2]);
partition3([{K,E} | Ts], Key, Keys, L1, L2) when K == Key ->
    partition3(Ts, Key, Keys, [E | L1], L2);
partition3([{K,E} | Ts], _Key, Keys, L1, L2) ->
    partition3(Ts, K, Keys, L1, L2, E);
partition3(_Ts, _Key, _Keys, L1, L2) ->
    [L1 | L2].
    
partition3(Ts, K, [Key | Keys], L1, L2, E) when K > Key ->
    partition3(Ts, K, Keys, L1, L2, E);
partition3(Ts, K, [Key | Keys], L1, L2, E) when K == Key ->
    partition3(Ts, Key, Keys, [E | L1], L2);
partition3(Ts, _K, [Key | Keys], L1, L2, E) ->
    partition3(Ts, Key, Keys, L1, [E | L2]);
partition3(Ts, _K, _Keys, L1, L2, E) ->
    partition3_tail(Ts, L1, [E | L2]).

partition3_tail([{_K,E} | Ts], L1, L2) ->
    partition3_tail(Ts, L1, [E | L2]);
partition3_tail(_Ts, L1, L2) ->
    [L1 | L2].

replace([E | Es], F, L) ->
    replace(Es, F, [F(E) | L]);
replace(_, _F, L) ->
    sort(L).

mul_relprod([T | Ts], I, R) when ?IS_SET(T) ->
    P = raise_element(R, I),
    F = relative_product1(P, T),
    [F | mul_relprod(Ts, I+1, R)];
mul_relprod([], _I, _R) ->
    [].

raise_element(R, I) ->
    L = sort(I =/= 1, rearr(?LIST(R), I, [])),
    Type = ?TYPE(R),
    ?SET(L, ?BINREL(?REL_TYPE(I, Type), Type)).

rearr([E | Es], I, L) ->
    rearr(Es, I, [{element(I, E), E} | L]);
rearr([], _I, L) ->
    L.

join_element(E1, E2) ->
    [_ | L2] = tuple_to_list(E2),
    list_to_tuple(tuple_to_list(E1) ++ L2).

join_element(E1, E2, I2) ->
    tuple_to_list(E1) ++ join_element2(tuple_to_list(E2), 1, I2).

join_element2([B | Bs], C, I2) when C =/= I2 ->
    [B | join_element2(Bs, C+1, I2)];
join_element2([_ | Bs], _C, _I2) -> 
    Bs.

family2rel([{X,S} | F], L) ->
    fam2rel(F, L, X, S);
family2rel([], L) ->
    reverse(L).

fam2rel(F, L, X, [Y | Ys]) ->
    fam2rel(F, [{X,Y} | L], X, Ys);
fam2rel(F, L, _X, _) ->
    family2rel(F, L).

fam_spec([{_,S}=E | F], Fun, Type, L) ->
    case Fun(?SET(S, Type)) of
        true ->
            fam_spec(F, Fun, Type, [E | L]);
        false ->
            fam_spec(F, Fun, Type, L);
	_ ->
	    badarg
    end;
fam_spec([], _Fun, _Type, L) ->
    reverse(L).

fam_specification([{_,S}=E | F], Fun, L) ->
    case Fun(S) of
        true ->
            fam_specification(F, Fun, [E | L]);
        false ->
            fam_specification(F, Fun, L);
	_ ->
	    badarg
    end;
fam_specification([], _Fun, L) ->
    reverse(L).

un_of_fam([{_X,S} | F], L) ->
    un_of_fam(F, [S | L]);
un_of_fam([], L) ->
    lunion(sort(L)).

int_of_fam([{_,S} | F]) ->
    int_of_fam(F, [S]);
int_of_fam([]) ->
    badarg.

int_of_fam([{_,S} | F], L) ->
    int_of_fam(F, [S | L]);
int_of_fam([], [L | Ls]) ->
    lintersection(Ls, L).

fam_un([{X,S} | F], L) ->
    fam_un(F, [{X, lunion(S)} | L]);
fam_un([], L) ->
    reverse(L).

fam_int([{X, [S | Ss]} | F], L) ->
    fam_int(F, [{X, lintersection(Ss, S)} | L]);
fam_int([{_X,[]} | _F], _L) ->
    badarg;
fam_int([], L) ->
    reverse(L).

fam_dom([{X,S} | F], L) ->
    fam_dom(F, [{X, dom(S)} | L]);
fam_dom([], L) ->
    reverse(L).

fam_ran([{X,S} | F], L) ->
    fam_ran(F, [{X, ran(S, [])} | L]);
fam_ran([], L) ->
    reverse(L).

fam_union(F1 = [{A,_AS} | _AL], [B1={B,_BS} | BL], L) when A > B ->
    fam_union(F1, BL, [B1 | L]);
fam_union([{A,AS} | AL], [{B,BS} | BL], L) when A == B ->
    fam_union(AL, BL, [{A, umerge(AS, BS)} | L]);
fam_union([A1 | AL], F2, L) ->
    fam_union(AL, F2, [A1 | L]);
fam_union(_, F2, L) ->
    reverse(L, F2).

fam_intersect(F1 = [{A,_AS} | _AL], [{B,_BS} | BL], L) when A > B ->
    fam_intersect(F1, BL, L);
fam_intersect([{A,AS} | AL], [{B,BS} | BL], L) when A == B ->
    fam_intersect(AL, BL, [{A, intersection(AS, BS, [])} | L]);
fam_intersect([_A1 | AL], F2, L) ->
    fam_intersect(AL, F2, L);
fam_intersect(_, _, L) ->
    reverse(L).

fam_difference(F1 = [{A,_AS} | _AL], [{B,_BS} | BL], L) when A > B ->
    fam_difference(F1, BL, L);
fam_difference([{A,AS} | AL], [{B,BS} | BL], L) when A == B ->
    fam_difference(AL, BL, [{A, difference(AS, BS, [])} | L]);
fam_difference([A1 | AL], F2, L) ->
    fam_difference(AL, F2, [A1 | L]);
fam_difference(F1, _, L) ->
    reverse(L, F1).

check_function([{X,_} | XL], R) ->
    check_function(X, XL, R);
check_function([], R) ->
    R.
    
check_function(X0, [{X,_} | XL], R) when X0 /= X ->
    check_function(X, XL, R);
check_function(X0, [{X,_} | _XL], _R) when X0 == X ->
    bad_function;
check_function(_X0, [], R) ->
    R.

fam_partition_n(I, [E | Ts]) ->
    fam_partition_n(I, Ts, element(I, E), [E], []);
fam_partition_n(_I, []) ->
    [].

fam_partition_n(I, [E | Ts], K, Es, P) ->
    case {element(I, E), Es} of
	{K1, _} when K == K1 ->