otp/lib/stdlib/src/sofs.erl at master · googol-lab/otp

Repository navigation

%% %CopyrightBegin%
%% Copyright Ericsson AB 2001-2017. 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.
%% You may obtain a copy of the License at
%%     http://www.apache.org/licenses/LICENSE-2.0
%% Unless required by applicable law or agreed to in writing, software
%% distributed under the License is distributed on an "AS IS" BASIS,
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%% See the License for the specific language governing permissions and
%% limitations under the License.
%% %CopyrightEnd%
-module(sofs).
-export([from_term/1, from_term/2, from_external/2, empty_set/0,
         is_type/1, set/1, set/2, from_sets/1, relation/1, relation/2,
         a_function/1, a_function/2, family/1, family/2,
         to_external/1, type/1, to_sets/1, no_elements/1,
         specification/2, union/2, intersection/2, difference/2,
         symdiff/2, symmetric_partition/2, product/1, product/2,
         constant_function/2, is_equal/2, is_subset/2, is_sofs_set/1,
         is_set/1, is_empty_set/1, is_disjoint/2]).
-export([union/1, intersection/1, canonical_relation/1]).
-export([relation_to_family/1, domain/1, range/1, field/1,
	 relative_product/1, relative_product/2, relative_product1/2,
	 converse/1, image/2, inverse_image/2, strict_relation/1,
	 weak_relation/1, extension/3, is_a_function/1]).
-export([composite/2, inverse/1]).
-export([restriction/2, restriction/3, drestriction/2, drestriction/3,
         substitution/2, projection/2, partition/1, partition/2,
         partition/3, multiple_relative_product/2, join/4]).
-export([family_to_relation/1, family_specification/2,
         union_of_family/1, intersection_of_family/1,
         family_union/1, family_intersection/1,
         family_domain/1, family_range/1, family_field/1,
         family_union/2, family_intersection/2, family_difference/2,
         partition_family/2, family_projection/2]).
-export([family_to_digraph/1, family_to_digraph/2,
         digraph_to_family/1, digraph_to_family/2]).
%% Shorter names of some functions.
-export([fam2rel/1, rel2fam/1]).
-import(lists,
        [any/2, append/1, flatten/1, foreach/2,
         keysort/2, last/1, map/2, mapfoldl/3, member/2, merge/2,
         reverse/1, reverse/2, sort/1, umerge/1, umerge/2, usort/1]).
-compile({inline, [{family_to_relation,1}, {relation_to_family,1}]}).
-compile({inline, [{rel,2},{a_func,2},{fam,2},{term2set,2}]}).
-compile({inline, [{external_fun,1},{element_type,1}]}).
-compile({inline,
          [{unify_types,2}, {match_types,2},
           {test_rel,3}, {symdiff,3},
           {subst,3}]}).
-compile({inline, [{fam_binop,3}]}).
%% Nope, no is_member, del_member or add_member.
%% See also "Naive Set Theory" by Paul R. Halmos.
%% By convention, erlang:error/1 is called from exported functions.
-define(TAG, 'Set').
-define(ORDTAG, 'OrdSet').
-record(?TAG, {data = [] :: list(), type = type :: term()}).
-record(?ORDTAG, {orddata = {} :: tuple() | atom(),
                  ordtype = type :: term()}).
-define(LIST(S), (S)#?TAG.data).
-define(TYPE(S), (S)#?TAG.type).
-define(SET(L, T), #?TAG{data = L, type = T}).
-define(IS_SET(S), is_record(S, ?TAG)).
-define(IS_UNTYPED_SET(S), ?TYPE(S) =:= ?ANYTYPE).
%% Ordered sets and atoms:
-define(ORDDATA(S), (S)#?ORDTAG.orddata).
-define(ORDTYPE(S), (S)#?ORDTAG.ordtype).
-define(ORDSET(L, T), #?ORDTAG{orddata = L, ordtype = T}).
-define(IS_ORDSET(S), is_record(S, ?ORDTAG)).
-define(ATOM_TYPE, atom).
-define(IS_ATOM_TYPE(T), is_atom(T)). % true for ?ANYTYPE...
%% When IS_SET is true:
-define(ANYTYPE, '_').
-define(BINREL(X, Y), {X, Y}).
-define(IS_RELATION(R), is_tuple(R)).
-define(REL_ARITY(R), tuple_size(R)).
-define(REL_TYPE(I, R), element(I, R)).
-define(SET_OF(X), [X]).
-define(IS_SET_OF(X), is_list(X)).
-define(FAMILY(X, Y), ?BINREL(X, ?SET_OF(Y))).
-export_type([anyset/0, binary_relation/0, external_set/0, a_function/0,
              family/0, relation/0, set_of_sets/0, set_fun/0, spec_fun/0,
              type/0]).
-export_type([ordset/0, a_set/0]).
-type(anyset() :: ordset() | a_set()).
-type(binary_relation() :: relation()).
-type(external_set() :: term()).
-type(a_function() :: relation()).
-type(family() :: a_function()).
-opaque(ordset() :: #?ORDTAG{}).
-type(relation() :: a_set()).
-opaque(a_set() :: #?TAG{}).
-type(set_of_sets() :: a_set()).
-type(set_fun() :: pos_integer()
                 | {external, fun((external_set()) -> external_set())}
                 | fun((anyset()) -> anyset())).
-type(spec_fun() :: {external, fun((external_set()) -> boolean())}
                  | fun((anyset()) -> boolean())).
-type(type() :: term()).
-type(tuple_of(_T) :: tuple()).
%%  Exported functions
%%% Create sets
-spec(from_term(Term) -> AnySet when
      AnySet :: anyset(),
      Term :: term()).
from_term(T) ->
    Type = case T of
               _ when is_list(T) -> [?ANYTYPE];
               _ -> ?ANYTYPE
           end,
    try setify(T, Type)
    catch _:_ -> erlang:error(badarg)
-spec(from_term(Term, Type) -> AnySet when
      AnySet :: anyset(),
      Term :: term(),
      Type :: type()).
from_term(L, T) ->
    case is_type(T) of
        true ->
            try setify(L, T)
            catch _:_ -> erlang:error(badarg)
            end;
        false  ->
            erlang:error(badarg)
-spec(from_external(ExternalSet, Type) -> AnySet when
      ExternalSet :: external_set(),
      AnySet :: anyset(),
      Type :: type()).
from_external(L, ?SET_OF(Type)) ->
    ?SET(L, Type);
from_external(T, Type) ->
    ?ORDSET(T, Type).
-spec(empty_set() -> Set when
      Set :: a_set()).
empty_set() ->
    ?SET([], ?ANYTYPE).
-spec(is_type(Term) -> Bool when
      Bool :: boolean(),
      Term :: term()).
is_type(Atom) when ?IS_ATOM_TYPE(Atom), Atom =/= ?ANYTYPE ->
is_type(?SET_OF(T)) ->
    is_element_type(T);
is_type(T) when tuple_size(T) > 0 ->
    is_types(tuple_size(T), T);
is_type(_T) ->
-spec(set(Terms) -> Set when
      Set :: a_set(),
      Terms :: [term()]).
    try usort(L) of
        SL -> ?SET(SL, ?ATOM_TYPE)
    catch _:_ -> erlang:error(badarg)
-spec(set(Terms, Type) -> Set when
      Set :: a_set(),
      Terms :: [term()],
      Type :: type()).
set(L, ?SET_OF(Type)) when ?IS_ATOM_TYPE(Type), Type =/= ?ANYTYPE ->
    try usort(L) of
        SL -> ?SET(SL, Type)
    catch _:_ -> erlang:error(badarg)
set(L, ?SET_OF(_) = T) ->
    try setify(L, T)
    catch _:_ -> erlang:error(badarg)
set(_, _) ->
    erlang:error(badarg).
-spec(from_sets(ListOfSets) -> Set when
      Set :: a_set(),
      ListOfSets :: [anyset()];
               (TupleOfSets) -> Ordset when
      Ordset :: ordset(),
      TupleOfSets :: tuple_of(anyset())).
from_sets(Ss) when is_list(Ss) ->
    case set_of_sets(Ss, [], ?ANYTYPE) of
        {error, Error} ->
            erlang:error(Error);
        Set ->
from_sets(Tuple) when is_tuple(Tuple) ->
    case ordset_of_sets(tuple_to_list(Tuple), [], []) of
        error ->
            erlang:error(badarg);
        Set ->
from_sets(_) ->
    erlang:error(badarg).
-spec(relation(Tuples) -> Relation when
      Relation :: relation(),
      Tuples :: [tuple()]).
relation([]) ->
    ?SET([], ?BINREL(?ATOM_TYPE, ?ATOM_TYPE));
relation(Ts = [T | _]) when is_tuple(T) ->
    try rel(Ts, tuple_size(T))
    catch _:_ -> erlang:error(badarg)
relation(_) ->
    erlang:error(badarg).
-spec(relation(Tuples, Type) -> Relation when
      N :: integer(),
      Type :: N | type(),
      Relation :: relation(),
      Tuples :: [tuple()]).
relation(Ts, TS) ->
    try rel(Ts, TS)
    catch _:_ -> erlang:error(badarg)
-spec(a_function(Tuples) -> Function when
      Function :: a_function(),
      Tuples :: [tuple()]).
a_function(Ts) ->
    try func(Ts, ?BINREL(?ATOM_TYPE, ?ATOM_TYPE)) of
        Bad when is_atom(Bad) ->
            erlang:error(Bad);
        Set ->
    catch _:_ -> erlang:error(badarg)
-spec(a_function(Tuples, Type) -> Function when
      Function :: a_function(),
      Tuples :: [tuple()],
      Type :: type()).
a_function(Ts, T) ->
    try a_func(Ts, T) of
	Bad when is_atom(Bad) ->
	    erlang:error(Bad);
    catch _:_ -> erlang:error(badarg)
-spec(family(Tuples) -> Family when
      Family :: family(),
      Tuples :: [tuple()]).
family(Ts) ->
    try fam2(Ts, ?FAMILY(?ATOM_TYPE, ?ATOM_TYPE)) of
        Bad when is_atom(Bad) ->
            erlang:error(Bad);
        Set ->
    catch _:_ -> erlang:error(badarg)
-spec(family(Tuples, Type) -> Family when
      Family :: family(),
      Tuples :: [tuple()],
      Type :: type()).
family(Ts, T) ->
    try fam(Ts, T) of
	Bad when is_atom(Bad) ->
	    erlang:error(Bad);
    catch _:_ -> erlang:error(badarg)
%%% Functions on sets.
-spec(to_external(AnySet) -> ExternalSet when
      ExternalSet :: external_set(),
      AnySet :: anyset()).
to_external(S) when ?IS_SET(S) ->
    ?LIST(S);
to_external(S) when ?IS_ORDSET(S) ->
    ?ORDDATA(S).
-spec(type(AnySet) -> Type when
      AnySet :: anyset(),
      Type :: type()).
type(S) when ?IS_SET(S) ->
    ?SET_OF(?TYPE(S));
type(S) when ?IS_ORDSET(S) ->
    ?ORDTYPE(S).
-spec(to_sets(ASet) -> Sets when
      ASet :: a_set() | ordset(),
      Sets :: tuple_of(AnySet) | [AnySet],
      AnySet :: anyset()).
to_sets(S) when ?IS_SET(S) ->
    case ?TYPE(S) of
        ?SET_OF(Type) -> list_of_sets(?LIST(S), Type, []);
        Type -> list_of_ordsets(?LIST(S), Type, [])
to_sets(S) when ?IS_ORDSET(S), is_tuple(?ORDTYPE(S)) ->
    tuple_of_sets(tuple_to_list(?ORDDATA(S)), tuple_to_list(?ORDTYPE(S)), []);
to_sets(S) when ?IS_ORDSET(S) ->
    erlang:error(badarg).
-spec(no_elements(ASet) -> NoElements when
      ASet :: a_set() | ordset(),
      NoElements :: non_neg_integer()).
no_elements(S) when ?IS_SET(S) ->
    length(?LIST(S));
no_elements(S) when ?IS_ORDSET(S), is_tuple(?ORDTYPE(S)) ->
    tuple_size(?ORDDATA(S));
no_elements(S) when ?IS_ORDSET(S) ->
    erlang:error(badarg).
-spec(specification(Fun, Set1) -> Set2 when
      Fun :: spec_fun(),
      Set1 :: a_set(),
      Set2 :: a_set()).
specification(Fun, S) when ?IS_SET(S) ->
    Type = ?TYPE(S),
    R = case external_fun(Fun) of
	    false ->
		spec(?LIST(S), Fun, element_type(Type), []);
	    XFun ->
		specification(?LIST(S), XFun, [])
    case R of
	SL when is_list(SL) ->
	    ?SET(SL, Type);
	    erlang:error(Bad)
-spec(union(Set1, Set2) -> Set3 when
      Set1 :: a_set(),
      Set2 :: a_set(),
      Set3 :: a_set()).
union(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) ->
    case unify_types(?TYPE(S1), ?TYPE(S2)) of
        [] -> erlang:error(type_mismatch);
        Type ->  ?SET(umerge(?LIST(S1), ?LIST(S2)), Type)
-spec(intersection(Set1, Set2) -> Set3 when
      Set1 :: a_set(),
      Set2 :: a_set(),
      Set3 :: a_set()).
intersection(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) ->
    case unify_types(?TYPE(S1), ?TYPE(S2)) of
        [] -> erlang:error(type_mismatch);
        Type ->  ?SET(intersection(?LIST(S1), ?LIST(S2), []), Type)
-spec(difference(Set1, Set2) -> Set3 when
      Set1 :: a_set(),
      Set2 :: a_set(),
      Set3 :: a_set()).
difference(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) ->
    case unify_types(?TYPE(S1), ?TYPE(S2)) of
        [] -> erlang:error(type_mismatch);
        Type ->  ?SET(difference(?LIST(S1), ?LIST(S2), []), Type)
-spec(symdiff(Set1, Set2) -> Set3 when
      Set1 :: a_set(),
      Set2 :: a_set(),
      Set3 :: a_set()).
symdiff(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) ->
    case unify_types(?TYPE(S1), ?TYPE(S2)) of
        [] -> erlang:error(type_mismatch);
        Type ->  ?SET(symdiff(?LIST(S1), ?LIST(S2), []), Type)
-spec(symmetric_partition(Set1, Set2) -> {Set3, Set4, Set5} when
      Set1 :: a_set(),
      Set2 :: a_set(),
      Set3 :: a_set(),
      Set4 :: a_set(),
      Set5 :: a_set()).
symmetric_partition(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) ->
    case unify_types(?TYPE(S1), ?TYPE(S2)) of
        [] -> erlang:error(type_mismatch);
        Type ->  sympart(?LIST(S1), ?LIST(S2), [], [], [], Type)
-spec(product(Set1, Set2) -> BinRel when
      BinRel :: binary_relation(),
      Set1 :: a_set(),
      Set2 :: a_set()).
product(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) ->
        ?TYPE(S1) =:= ?ANYTYPE -> S1;
        ?TYPE(S2) =:= ?ANYTYPE -> S2;
        true ->
	    F = fun(E) -> {0, E} end,
	    T = ?BINREL(?TYPE(S1), ?TYPE(S2)),
	    ?SET(relprod(map(F, ?LIST(S1)), map(F, ?LIST(S2))), T)
-spec(product(TupleOfSets) -> Relation when
      Relation :: relation(),
      TupleOfSets :: tuple_of(a_set())).
product({S1, S2}) ->
    product(S1, S2);
product(T) when is_tuple(T) ->
    Ss = tuple_to_list(T),
    try sets_to_list(Ss) of
        [] ->
            erlang:error(badarg);
        L ->
            Type = types(Ss, []),
            case member([], L) of
                true ->
		    empty_set();
                false ->
                    ?SET(reverse(prod(L, [], [])), Type)
    catch _:_ -> erlang:error(badarg)
-spec(constant_function(Set, AnySet) -> Function when
      AnySet :: anyset(),
      Function :: a_function(),
      Set :: a_set()).
constant_function(S, E) when ?IS_SET(S) ->
    case {?TYPE(S), is_sofs_set(E)} of
	{?ANYTYPE, true} -> S;
	{Type, true} ->
	    NType = ?BINREL(Type, type(E)),
	    ?SET(constant_function(?LIST(S), to_external(E), []), NType);
	_ -> erlang:error(badarg)
constant_function(S, _) when ?IS_ORDSET(S) ->
    erlang:error(badarg).
-spec(is_equal(AnySet1, AnySet2) -> Bool when
      AnySet1 :: anyset(),
      AnySet2 :: anyset(),
      Bool :: boolean()).
is_equal(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) ->
    case match_types(?TYPE(S1), ?TYPE(S2)) of
        true  -> ?LIST(S1) == ?LIST(S2);
        false -> erlang:error(type_mismatch)
is_equal(S1, S2) when ?IS_ORDSET(S1), ?IS_ORDSET(S2) ->
    case match_types(?ORDTYPE(S1), ?ORDTYPE(S2)) of
        true  -> ?ORDDATA(S1) == ?ORDDATA(S2);
        false -> erlang:error(type_mismatch)
is_equal(S1, S2) when ?IS_SET(S1), ?IS_ORDSET(S2) ->
    erlang:error(type_mismatch);
is_equal(S1, S2) when ?IS_ORDSET(S1), ?IS_SET(S2) ->
    erlang:error(type_mismatch).
-spec(is_subset(Set1, Set2) -> Bool when
      Bool :: boolean(),
      Set1 :: a_set(),
      Set2 :: a_set()).
is_subset(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) ->
    case match_types(?TYPE(S1), ?TYPE(S2)) of
        true  -> subset(?LIST(S1), ?LIST(S2));
        false -> erlang:error(type_mismatch)
-spec(is_sofs_set(Term) -> Bool when
      Bool :: boolean(),
      Term :: term()).
is_sofs_set(S) when ?IS_SET(S) ->
is_sofs_set(S) when ?IS_ORDSET(S) ->
is_sofs_set(_S) ->
-spec(is_set(AnySet) -> Bool when
      AnySet :: anyset(),
      Bool :: boolean()).
is_set(S) when ?IS_SET(S) ->
is_set(S) when ?IS_ORDSET(S) ->
-spec(is_empty_set(AnySet) -> Bool when
      AnySet :: anyset(),
      Bool :: boolean()).
is_empty_set(S) when ?IS_SET(S) ->
    ?LIST(S) =:= [];
is_empty_set(S) when ?IS_ORDSET(S) ->
-spec(is_disjoint(Set1, Set2) -> Bool when
      Bool :: boolean(),
      Set1 :: a_set(),
      Set2 :: a_set()).
is_disjoint(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) ->
    case match_types(?TYPE(S1), ?TYPE(S2)) of
        true ->
            case ?LIST(S1) of
                [] -> true;
                [A | As] -> disjoint(?LIST(S2), A, As)
            end;
        false -> erlang:error(type_mismatch)
%%% Functions on set-of-sets.
-spec(union(SetOfSets) -> Set when
      Set :: a_set(),
      SetOfSets :: set_of_sets()).
union(Sets) when ?IS_SET(Sets) ->
    case ?TYPE(Sets) of
        ?SET_OF(Type) -> ?SET(lunion(?LIST(Sets)), Type);
        ?ANYTYPE -> Sets;
        _ -> erlang:error(badarg)
-spec(intersection(SetOfSets) -> Set when
      Set :: a_set(),
      SetOfSets :: set_of_sets()).
intersection(Sets) when ?IS_SET(Sets) ->
    case ?LIST(Sets) of
        [] -> erlang:error(badarg);
        [L | Ls] ->
            case ?TYPE(Sets) of
                ?SET_OF(Type) ->
                    ?SET(lintersection(Ls, L), Type);
                _ -> erlang:error(badarg)
-spec(canonical_relation(SetOfSets) -> BinRel when
      BinRel :: binary_relation(),
      SetOfSets :: set_of_sets()).
canonical_relation(Sets) when ?IS_SET(Sets) ->
    ST = ?TYPE(Sets),
    case ST of
        ?SET_OF(?ANYTYPE) -> empty_set();
        ?SET_OF(Type) ->
            ?SET(can_rel(?LIST(Sets), []), ?BINREL(Type, ST));
        ?ANYTYPE -> Sets;
        _ -> erlang:error(badarg)
%%% Functions on binary relations only.
-spec(rel2fam(BinRel) -> Family when
      Family :: family(),
      BinRel :: binary_relation()).
rel2fam(R) ->
    relation_to_family(R).
-spec(relation_to_family(BinRel) -> Family when
      Family :: family(),
      BinRel :: binary_relation()).
%% Inlined.
relation_to_family(R) when ?IS_SET(R) ->
    case ?TYPE(R) of
        ?BINREL(DT, RT) ->
            ?SET(rel2family(?LIST(R)), ?FAMILY(DT, RT));
        ?ANYTYPE -> R;
        _Else    -> erlang:error(badarg)
-spec(domain(BinRel) -> Set when
      BinRel :: binary_relation(),
      Set :: a_set()).
domain(R) when ?IS_SET(R) ->
    case ?TYPE(R) of
        ?BINREL(DT, _)  -> ?SET(dom(?LIST(R)), DT);
        ?ANYTYPE -> R;
        _Else    -> erlang:error(badarg)
-spec(range(BinRel) -> Set when
      BinRel :: binary_relation(),
      Set :: a_set()).
range(R) when ?IS_SET(R) ->
    case ?TYPE(R) of
        ?BINREL(_, RT)  -> ?SET(ran(?LIST(R),  []), RT);
        ?ANYTYPE -> R;
        _ -> erlang:error(badarg)
-spec(field(BinRel) -> Set when
      BinRel :: binary_relation(),
      Set :: a_set()).
%% In "Introduction to LOGIC", Suppes defines the field of a binary
%% relation to be the union of the domain and the range (or
%% counterdomain).
field(R) ->
    union(domain(R), range(R)).
-spec(relative_product(ListOfBinRels) -> BinRel2 when
      ListOfBinRels :: [BinRel, ...],
      BinRel :: binary_relation(),
      BinRel2 :: binary_relation()).
%% The following clause is kept for backward compatibility.
%% The list is due to Dialyzer's specs.
relative_product(RT) when is_tuple(RT) ->
    relative_product(tuple_to_list(RT));
relative_product(RL) when is_list(RL) ->
    case relprod_n(RL, foo, false, false) of
        {error, Reason} ->
            erlang:error(Reason);
        Reply ->
            Reply
-spec(relative_product(ListOfBinRels, BinRel1) -> BinRel2 when
      ListOfBinRels :: [BinRel, ...],
      BinRel :: binary_relation(),
      BinRel1 :: binary_relation(),
      BinRel2 :: binary_relation();
                      (BinRel1, BinRel2) -> BinRel3 when
      BinRel1 :: binary_relation(),
      BinRel2 :: binary_relation(),
      BinRel3 :: binary_relation()).
relative_product(R1, R2) when ?IS_SET(R1), ?IS_SET(R2) ->
    relative_product1(converse(R1), R2);
%% The following clause is kept for backward compatibility.
%% The list is due to Dialyzer's specs.
relative_product(RT, R) when is_tuple(RT), ?IS_SET(R) ->
    relative_product(tuple_to_list(RT), R);
relative_product(RL, R) when is_list(RL), ?IS_SET(R) ->
    EmptyR = case ?TYPE(R) of
                 ?BINREL(_, _) -> ?LIST(R) =:= [];
                 ?ANYTYPE -> true;
                 _ -> erlang:error(badarg)
             end,
    case relprod_n(RL, R, EmptyR, true) of
        {error, Reason} ->
            erlang:error(Reason);
        Reply ->
            Reply
-spec(relative_product1(BinRel1, BinRel2) -> BinRel3 when
      BinRel1 :: binary_relation(),
      BinRel2 :: binary_relation(),
      BinRel3 :: binary_relation()).
relative_product1(R1, R2) when ?IS_SET(R1), ?IS_SET(R2) ->
    {DTR1, RTR1} = case ?TYPE(R1) of
                     ?BINREL(_, _) = R1T -> R1T;
                     ?ANYTYPE -> {?ANYTYPE, ?ANYTYPE};
                     _ -> erlang:error(badarg)
    {DTR2, RTR2} = case ?TYPE(R2) of
                     ?BINREL(_, _) = R2T -> R2T;
                     ?ANYTYPE -> {?ANYTYPE, ?ANYTYPE};
                     _ -> erlang:error(badarg)
    case match_types(DTR1, DTR2) of
        true when DTR1 =:= ?ANYTYPE -> R1;
        true when DTR2 =:= ?ANYTYPE -> R2;
        true -> ?SET(relprod(?LIST(R1), ?LIST(R2)), ?BINREL(RTR1, RTR2));
        false -> erlang:error(type_mismatch)
-spec(converse(BinRel1) -> BinRel2 when
      BinRel1 :: binary_relation(),
      BinRel2 :: binary_relation()).
converse(R) when ?IS_SET(R) ->
    case ?TYPE(R) of
        ?BINREL(DT, RT) -> ?SET(converse(?LIST(R), []), ?BINREL(RT, DT));
        ?ANYTYPE -> R;
        _ -> erlang:error(badarg)
-spec(image(BinRel, Set1) -> Set2 when
      BinRel :: binary_relation(),
      Set1 :: a_set(),
      Set2 :: a_set()).
image(R, S) when ?IS_SET(R), ?IS_SET(S) ->
    case ?TYPE(R) of
        ?BINREL(DT, RT) ->
	    case match_types(DT, ?TYPE(S)) of
		    ?SET(usort(restrict(?LIST(S), ?LIST(R))), RT);
		    erlang:error(type_mismatch)
        ?ANYTYPE -> R;
        _ -> erlang:error(badarg)
-spec(inverse_image(BinRel, Set1) -> Set2 when
      BinRel :: binary_relation(),
      Set1 :: a_set(),
      Set2 :: a_set()).
inverse_image(R, S) when ?IS_SET(R), ?IS_SET(S) ->
    case ?TYPE(R) of
        ?BINREL(DT, RT) ->
	    case match_types(RT, ?TYPE(S)) of
		    NL = restrict(?LIST(S), converse(?LIST(R), [])),
		    ?SET(usort(NL), DT);
		    erlang:error(type_mismatch)
        ?ANYTYPE -> R;
        _ -> erlang:error(badarg)
-spec(strict_relation(BinRel1) -> BinRel2 when
      BinRel1 :: binary_relation(),
      BinRel2 :: binary_relation()).
strict_relation(R) when ?IS_SET(R) ->
    case ?TYPE(R) of
        Type = ?BINREL(_, _) ->
            ?SET(strict(?LIST(R), []), Type);
        ?ANYTYPE -> R;
        _ -> erlang:error(badarg)
-spec(weak_relation(BinRel1) -> BinRel2 when
      BinRel1 :: binary_relation(),
      BinRel2 :: binary_relation()).
weak_relation(R) when ?IS_SET(R) ->
    case ?TYPE(R) of
        ?BINREL(DT, RT) ->
            case unify_types(DT, RT) of
                    erlang:error(badarg);
                Type ->
                    ?SET(weak(?LIST(R)), ?BINREL(Type, Type))
            end;
        ?ANYTYPE -> R;
        _ -> erlang:error(badarg)
-spec(extension(BinRel1, Set, AnySet) -> BinRel2 when
      AnySet :: anyset(),
      BinRel1 :: binary_relation(),
      BinRel2 :: binary_relation(),
      Set :: a_set()).
extension(R, S, E) when ?IS_SET(R), ?IS_SET(S) ->
    case {?TYPE(R), ?TYPE(S), is_sofs_set(E)} of
	{T=?BINREL(DT, RT), ST, true} ->
	    case match_types(DT, ST) and match_types(RT, type(E)) of
		    erlang:error(type_mismatch);
		    RL = ?LIST(R),
		    case extc([], ?LIST(S), to_external(E), RL) of
			    ?SET(merge(RL, reverse(L)), T)
	{?ANYTYPE, ?ANYTYPE, true} ->
	{?ANYTYPE, ST, true} ->
	    case type(E) of
		?SET_OF(?ANYTYPE) ->
		    ?SET([], ?BINREL(ST, ET))
	{_, _, true} ->
	    erlang:error(badarg)
-spec(is_a_function(BinRel) -> Bool when
      Bool :: boolean(),
      BinRel :: binary_relation()).
is_a_function(R) when ?IS_SET(R) ->
    case ?TYPE(R) of
        ?BINREL(_, _) ->
            case ?LIST(R) of
                [] -> true;
                [{V,_} | Es] -> is_a_func(Es, V)
            end;
        ?ANYTYPE -> true;
        _ -> erlang:error(badarg)
-spec(restriction(BinRel1, Set) -> BinRel2 when
      BinRel1 :: binary_relation(),
      BinRel2 :: binary_relation(),
      Set :: a_set()).
restriction(Relation, Set) ->
    restriction(1, Relation, Set).
-spec(drestriction(BinRel1, Set) -> BinRel2 when
      BinRel1 :: binary_relation(),
      BinRel2 :: binary_relation(),
      Set :: a_set()).
drestriction(Relation, Set) ->
    drestriction(1, Relation, Set).
%%% Functions on functions only.
-spec(composite(Function1, Function2) -> Function3 when
      Function1 :: a_function(),
      Function2 :: a_function(),
      Function3 :: a_function()).
composite(Fn1, Fn2) when ?IS_SET(Fn1), ?IS_SET(Fn2) ->
    ?BINREL(DTF1, RTF1) = case ?TYPE(Fn1)of
			      ?BINREL(_, _) = F1T -> F1T;
			      ?ANYTYPE -> {?ANYTYPE, ?ANYTYPE};
			      _ -> erlang:error(badarg)
    ?BINREL(DTF2, RTF2) = case ?TYPE(Fn2) of
			      ?BINREL(_, _) = F2T -> F2T;
			      ?ANYTYPE -> {?ANYTYPE, ?ANYTYPE};
			      _ -> erlang:error(badarg)
    case match_types(RTF1, DTF2) of
        true when DTF1 =:= ?ANYTYPE -> Fn1;
        true when DTF2 =:= ?ANYTYPE -> Fn2;
        true ->
	    case comp(?LIST(Fn1), ?LIST(Fn2)) of
		SL when is_list(SL) ->
		    ?SET(sort(SL), ?BINREL(DTF1, RTF2));
		    erlang:error(Bad)
        false -> erlang:error(type_mismatch)
-spec(inverse(Function1) -> Function2 when
      Function1 :: a_function(),
      Function2 :: a_function()).
inverse(Fn) when ?IS_SET(Fn) ->
    case ?TYPE(Fn) of
        ?BINREL(DT, RT) ->
	    case inverse1(?LIST(Fn)) of
		SL when is_list(SL) ->
		    ?SET(SL, ?BINREL(RT, DT));
		    erlang:error(Bad)
        ?ANYTYPE -> Fn;
        _ -> erlang:error(badarg)
%%% Functions on relations (binary or other).
-spec(restriction(SetFun, Set1, Set2) -> Set3 when
      SetFun :: set_fun(),
      Set1 :: a_set(),
      Set2 :: a_set(),
      Set3 :: a_set()).
%% Equivalent to range(restriction(inverse(substitution(Fun, S1)), S2)).
restriction(I, R, S) when is_integer(I), ?IS_SET(R), ?IS_SET(S) ->
    RT = ?TYPE(R),
    ST = ?TYPE(S),
    case check_for_sort(RT, I) of
	    erlang:error(badarg);
	    RL = ?LIST(R),
	    case {match_types(?REL_TYPE(I, RT), ST), ?LIST(S)} of
		{true, _SL} when RL =:= [] ->
		{true, []} ->
                    ?SET([], RT);
		{true, [E | Es]} when Sort =:= false -> % I =:= 1
		    ?SET(reverse(restrict_n(I, RL, E, Es, [])), RT);
		{true, [E | Es]} ->
		    ?SET(sort(restrict_n(I, keysort(I, RL), E, Es, [])), RT);
		{false, _SL} ->
		    erlang:error(type_mismatch)
restriction(SetFun, S1, S2) when ?IS_SET(S1), ?IS_SET(S2) ->
    Type1 = ?TYPE(S1),
    Type2 = ?TYPE(S2),
    SL1 = ?LIST(S1),
    case external_fun(SetFun) of
	false when Type2 =:= ?ANYTYPE ->
	    case subst(SL1, SetFun, element_type(Type1)) of
		{NSL, NewType} -> % NewType can be ?ANYTYPE
		    case match_types(NewType, Type2) of
			    NL = sort(restrict(?LIST(S2), converse(NSL, []))),
			    ?SET(NL, Type1);
			false ->
			    erlang:error(type_mismatch)
		    erlang:error(Bad)
	_ when Type1 =:= ?ANYTYPE ->
	_XFun when ?IS_SET_OF(Type1) ->
            erlang:error(badarg);
	    FunT = XFun(Type1),
	    try check_fun(Type1, XFun, FunT) of
		    case match_types(FunT, Type2) of
			    R1 = inverse_substitution(SL1, XFun, Sort),
			    ?SET(sort(Sort, restrict(?LIST(S2), R1)), Type1);
			false ->
			    erlang:error(type_mismatch)
            catch _:_ -> erlang:error(badarg)
-spec(drestriction(SetFun, Set1, Set2) -> Set3 when
      SetFun :: set_fun(),
      Set1 :: a_set(),
      Set2 :: a_set(),
      Set3 :: a_set()).
drestriction(I, R, S) when is_integer(I), ?IS_SET(R), ?IS_SET(S) ->
    RT = ?TYPE(R),
    ST = ?TYPE(S),
    case check_for_sort(RT, I) of
	    erlang:error(badarg);
	    RL = ?LIST(R),
	    case {match_types(?REL_TYPE(I, RT), ST), ?LIST(S)} of
		{true, []} ->
		{true, _SL} when RL =:= [] ->
		{true, [E | Es]} when Sort =:= false -> % I =:= 1
		    ?SET(diff_restrict_n(I, RL, E, Es, []), RT);
		{true, [E | Es]} ->
		    ?SET(diff_restrict_n(I, keysort(I, RL), E, Es, []), RT);
		{false, _SL} ->
		    erlang:error(type_mismatch)
drestriction(SetFun, S1, S2) when ?IS_SET(S1), ?IS_SET(S2) ->
    Type1 = ?TYPE(S1),
    Type2 = ?TYPE(S2),
    SL1 = ?LIST(S1),
    case external_fun(SetFun) of
	false when Type2 =:= ?ANYTYPE ->
	    case subst(SL1, SetFun, element_type(Type1)) of
		{NSL, NewType} -> % NewType can be ?ANYTYPE
		    case match_types(NewType, Type2) of
			    SL2 = ?LIST(S2),
View remainder of file in raw view
FilesExpand file tree

sofs.erl

Latest commit

History

sofs.erl

File metadata and controls
