iset.erl

-module(iset).

-include_lib("eqc/include/eqc.hrl").

-export([empty/0,
         singleton/1,
         union/2,
         member/2,
         to_list/1]).
-compile(export_all).

empty() ->
    [].

singleton(N) ->
    [{N, N}].

union([], B) ->
    B;
union(A, []) ->
    A;
union(A, [H | T]) ->
    union(add_pair(A, H), T).

%% @private
add_pair([], B) ->
    [B];
%% completely less but contiguous
add_pair([{_LowA, HighA} | T], {LowB, _HighB})
        when _HighB + 1 =:= _LowA ->
    [{LowB, HighA} | T];
%% completely less not contiguous
add_pair(A=[{_LowA, _HighA} | _T], B={_LowB, _HighB})
        when _HighB < _LowA ->
    [B | A];
%% completely greater but contiguous
add_pair([{LowA, _HighA} | T], {_LowB, HighB})
        when _HighA + 1 =:= _LowB ->
    add_pair(T, {LowA, HighB});
%% completely covered
add_pair([{_LowA, _HighA} | T], B={_LowB, _HighB})
        when _LowB =< _LowA, _HighB >= _HighA ->
    add_pair(T, B);
%% completely greater
add_pair([H={_LowA, _HighA} | T], B={_LowB, _HighB})
        when _LowB > _HighA ->
    [H] ++ add_pair(T, B);
%% completely inside
add_pair(A=[{_LowA, _HighA} | _T], {_LowB, _HighB})
        when _LowB >= _LowA, _HighB =< _HighA->
    A;
%% overlap
add_pair([{LowA, HighA} | T], {LowB, HighB}) ->
    add_pair(T, {erlang:min(LowA, LowB), erlang:max(HighA, HighB)}).

member(_N, []) ->
    false;
member(N, [H | T]) ->
    in_head(N, H) orelse member(N, T).

%% @private
in_head(_N, {Low, High}) when _N >= Low, _N =< High ->
    true;
in_head(_N, _H) ->
    false.

to_list([]) ->
    [];
to_list([{Low, High} | T]) ->
    lists:seq(Low, High) ++ to_list(T).

%% EQC

valid([]) ->
    true;
valid([A]) ->
    valid_tuple(A);
valid([A={_LowA, HighA}, B={LowB, _HighB} | T]) ->
    valid_tuple(A) andalso
    HighA + 1 < LowB andalso
    valid([B | T]).

%% @private
valid_tuple({Low, High}) ->
    Low =< High.

from_list(L) ->
    lists:foldr(fun union/2,empty(),
                [singleton(X) || X <- L]).

%% Generators

list_nat_tuple() ->
    list({nat(), nat()}).

iset_gen() ->
    ?LET(X, list_nat_tuple(), create_ranges(X, 1)).

create_ranges([], _Min) ->
    [];
create_ranges([A | B], Min) ->
    A2={_Low, High} = create_tuple(A, Min),
    [A2 | create_ranges(B, High+2)].

create_tuple({Low, High}, Min) ->
    Low2 = erlang:min(Min, Low + Min),
    {Low2, Low2 + High}.

%% properies

prop_valid_generator() ->
    ?FORALL(L, iset_gen(),
            valid(L)).

prop_valid_to_list() ->
    ?FORALL(L, iset_gen(),
            lists:usort(to_list(L)) =:=
            to_list(L)).

prop_valid_right_identity() ->
    ?FORALL(L, iset_gen(),
            L =:= union(L, empty())).

prop_valid_left_identity() ->
    ?FORALL(L, iset_gen(),
            L =:= union(empty(), L)).

prop_valid_union() ->
    ?FORALL({A, B}, {iset_gen(), iset_gen()},
            valid(union(A, B))).

prop_correct_union() ->
    ?FORALL({A, B}, {iset_gen(), iset_gen()},
            lists:umerge(to_list(A), to_list(B)) =:=
            to_list(union(A, B))).

prop_list_roundtrip() ->
    ?FORALL(L, iset_gen(),
            L =:=
            from_list(to_list(L))).