partisan

%% =============================================================================
%%  partisan_interval_sets -
%%
%%  Copyright (c) 2022 Alejandro M. Ramallo. 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.
%% =============================================================================
%% -----------------------------------------------------------------------------
%% @doc An implementation of a set of bounded open intervals.
%% @end
%% -----------------------------------------------------------------------------
-module(partisan_interval_sets).

-type interval()    ::  {integer(), integer()}.
-type element()     ::  integer() | interval().
-type t()           ::  [element()].

-export_type([interval/0]).
-export_type([t/0]).


-export([add_element/2]).
-export([del_element/2]).
-export([filter/2]).
-export([fold/3]).
-export([from_list/1]).
-export([intersection/1]).
-export([intersection/2]).
-export([is_disjoint/2]).
-export([is_element/2]).
-export([is_empty/1]).
-export([is_subset/2]).
-export([is_type/1]).
-export([new/0]).
-export([size/1]).
-export([flat_size/1]).
-export([subtract/2]).
-export([to_list/1]).
-export([to_flat_list/1]).
-export([union/1]).
-export([union/2]).
-export([min/1]).
-export([max/1]).


-ifdef(TEST).

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

-export([element_union/2]).
-export([element_intersection/2]).
-export([element_overlaps/2]).
-export([element_starts_before/2]).
-export([element_meets/2]).
-export([element_merges/2]).
-export([element_begins/2]).
-export([element_ends/2]).
-export([element_succeeds/2]).
-export([element_precedes/2]).
-export([element_includes/2]).
-export([element_included/2]).
-export([element_subtract/2]).

-endif.




%% =============================================================================
%% API
%% =============================================================================



%% -----------------------------------------------------------------------------
%% @doc Return a new empty offset.
%% -----------------------------------------------------------------------------
-spec new() -> [].

new() ->
    [].


%% -----------------------------------------------------------------------------
%% @doc Return 'true' if Set is an ordered set of elements, else 'false'.
%% -----------------------------------------------------------------------------
-spec is_type(t()) -> boolean().

is_type([E|Es]) ->
    is_element_type(E) andalso is_type(Es, E);

is_type([]) ->
    true;

is_type(_) ->
    false.


%% -----------------------------------------------------------------------------
%% @doc Return the number of elements in OrdSet.
%% -----------------------------------------------------------------------------
-spec size(t()) -> non_neg_integer().

size(S) ->
    length(S).


%% -----------------------------------------------------------------------------
%% @doc Return the number of points in the Ordset.
%% -----------------------------------------------------------------------------
-spec flat_size(t()) -> non_neg_integer().

flat_size(S) ->
    lists:foldl(
        fun
            ({H, T}, Cnt) -> Cnt + 1 + T - H;
            (_, Cnt) -> Cnt + 1
        end,
        0,
        S
    ).


%% -----------------------------------------------------------------------------
%% @doc Return 'true' if OrdSet is an empty set, otherwise 'false'.
%% -----------------------------------------------------------------------------
-spec is_empty(t()) -> boolean().

is_empty(S) ->
    S =:= [].


%% -----------------------------------------------------------------------------
%% @doc Returns the minimum integer value contained in the set.
%% -----------------------------------------------------------------------------
-spec min(t()) -> integer().

min([{H, _}|_]) ->
    H;

min([N|_]) ->
    N.


%% -----------------------------------------------------------------------------
%% @doc Returns the maximum integer value contained in the set.
%% -----------------------------------------------------------------------------
-spec max(t()) -> integer().

max(S) ->
    case lists:last(S) of
        {_, T} -> T;
        N -> N
    end.


%% -----------------------------------------------------------------------------
%% @doc Return the elements in OrdSet as a list.
%% -----------------------------------------------------------------------------
-spec to_list(t()) -> [element()].

to_list(S) ->
    S.


%% -----------------------------------------------------------------------------
%% @doc Return the points in OrdSet as a list.
%% -----------------------------------------------------------------------------
-spec to_flat_list(t()) -> [integer()].

to_flat_list(Set) ->
    List = lists:foldl(
        fun
            ({H, T}, Acc) ->
                [lists:seq(H, T)|Acc];
            (N, Acc) ->
                [N|Acc]
        end,
        [],
        Set
    ),
    lists:flatten(lists:reverse(List)).



%% -----------------------------------------------------------------------------
%% @doc Build an ordered set from the elements in List.
%% -----------------------------------------------------------------------------
-spec from_list(List :: [element()]) -> Sets :: t().

from_list(L0) ->
    L1 = lists:usort(
        fun
            ({V1, V2} = E1, {V3, _} = E2) ->
                ok = validate_element(E1),
                ok = validate_element(E2),
                V2 =< V3 orelse V1 =< V3;

            ({V1, _} = E1, E2) when is_integer(E2) ->
                ok = validate_element(E1),
                V1 =< E2;

            (E1, {V1, _} = E2) when is_integer(E1) ->
                ok = validate_element(E2),
                E1 =< V1;

            (E1, E2) when is_integer(E1), is_integer(E2), E1 < E2 ->
                true;

            (E1, E2) ->
                ok = validate_element(E1),
                ok = validate_element(E2),
                false

        end,
        L0
    ),
    compact(L1).


%% -----------------------------------------------------------------------------
%% @doc Return 'true' if Element is an element of Sets, else 'false'.
%% -----------------------------------------------------------------------------
-spec is_element(Element :: element(), Sets :: t()) -> boolean().

is_element(Element, Sets) ->
    ok = validate_element(Element),
    do_is_element(Element, Sets).


%% @private
do_is_element(A, [B|Es]) ->
    (not element_starts_before(A, B) andalso not element_precedes(A, B))
    andalso (
        element_included(A, B)
        orelse (
            element_succeeds(A, B) andalso do_is_element(A, Es)
        )
    );

do_is_element(_, []) ->
    false.



%% -----------------------------------------------------------------------------
%% @doc Return OrdSet with Element inserted in it.
%% -----------------------------------------------------------------------------
-spec add_element(Element :: element(), Set1 :: t()) -> Set2 :: t().

add_element(A, [B|Es] = Set) ->
    ok = validate_element(A),

    case equal(A, B) of
        true ->
            Set;
        false ->
            case element_meets(A, B) of
                true ->
                    E = unsafe_element_union(A, B),
                    add_element(E, Es);
                false ->
                    case element_precedes(A, B) of
                        true ->
                            [simplify(A)|Set];
                        false ->
                            case element_succeeds(A, B) of
                                true ->
                                    [B|add_element(A, Es)];
                                false ->
                                    case element_overlaps(A, B) of
                                        true ->
                                            E = unsafe_element_union(A, B),
                                            add_element(E, Es);
                                        false ->
                                            error(badarg)
                                    end
                            end
                    end
            end
    end;

add_element(E, []) ->
    ok = validate_element(E),
    [E].



%% -----------------------------------------------------------------------------
%% @doc Return OrdSet but with Element removed.
%% -----------------------------------------------------------------------------
-spec del_element(Element :: element(), Set1 :: t()) -> Set2 :: t().

del_element(A, [B|Es] = Set) ->
    ok = validate_element(A),

    case equal(A, B) of
        true ->
            Es;
        false ->
            case element_precedes(A, B) of
                true ->
                    Set;
                false ->
                    case element_succeeds(A, B) of
                        true ->
                            [B|del_element(A, Es)];
                        false ->
                            case element_overlaps(A, B) of
                                true ->
                                    I = element_intersection(A, B),
                                    New = [
                                        simplify(X)
                                        || X <- element_subtract(B, I)
                                    ],
                                    R = element_subtract(A, I),
                                    New ++ del_element(R, Es);
                                false ->
                                    error(badarg)
                            end
                    end
            end
    end;

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


%% -----------------------------------------------------------------------------
%% @doc Return the union of IntervalSet1 and IntervalSet2.
%% -----------------------------------------------------------------------------
-spec union(Set1 :: t(), Set2 :: t()) -> Set3 :: t().

union(Set1, Set2) ->
    compact(ordsets:union(to_flat_list(Set1), to_flat_list(Set2))).

% union([E1|Es1], [E2|_]=Set2) when E1 < E2 ->
%     [E1|union(Es1, Set2)];
% union([E1|_]=Set1, [E2|Es2]) when E1 > E2 ->
%     [E2|union(Es2, Set1)];            % switch arguments!
% union([E1|Es1], [_E2|Es2]) ->         %E1 == E2
%     [E1|union(Es1, Es2)];
% union([], Es2) -> Es2;
% union(Es1, []) -> Es1.


%% -----------------------------------------------------------------------------
%% @doc Return the union of the list of interval sets.
%% -----------------------------------------------------------------------------
-spec union(SetsList :: [t()]) -> Set :: t().

union(SetsList) ->
    compact(lists:umerge([to_flat_list(Set) || Set <- SetsList])).


%% -----------------------------------------------------------------------------
%% @doc Return the intersection of IntervalSet1 and IntervalSet2.
%% -----------------------------------------------------------------------------
-spec intersection(Set1 :: t(), Set2 :: t()) -> Set3 :: t().

intersection(Set1, Set2) ->
    compact(ordsets:intersection(to_flat_list(Set1), to_flat_list(Set2))).


% intersection([E1|Es1], [E2|_]=Set2) when E1 < E2 ->
%     intersection(Es1, Set2);
% intersection([E1|_]=Set1, [E2|Es2]) when E1 > E2 ->
%     intersection(Es2, Set1);          % switch arguments!
% intersection([E1|Es1], [_E2|Es2]) ->      %E1 == E2
%     [E1|intersection(Es1, Es2)];
% intersection([], _) ->
%     [];
% intersection(_, []) ->
%     [].


%% -----------------------------------------------------------------------------
%% @doc Return the intersection of the list of interval sets.
%% -----------------------------------------------------------------------------
-spec intersection(SetsList :: [t()]) -> Set :: t().

intersection([S1,S2|Ss]) ->
    intersection1(intersection(S1, S2), Ss);

intersection([S]) ->
    S.

intersection1(S1, [S2|Ss]) ->
    intersection1(intersection(S1, S2), Ss);

intersection1(S1, []) ->
    S1.


%% -----------------------------------------------------------------------------
%% @doc Check whether IntervalSet1 and IntervalSet2 are disjoint.
%% -----------------------------------------------------------------------------
-spec is_disjoint(Set1 :: t(), Set2 :: t()) -> boolean().

is_disjoint(Set1, Set2) ->
    ordsets:is_disjoint(to_flat_list(Set1), to_flat_list(Set2)).

% is_disjoint([E1|Es1], [E2|_]=Set2) when E1 < E2 ->
%     is_disjoint(Es1, Set2);
% is_disjoint([E1|_]=Set1, [E2|Es2]) when E1 > E2 ->
%     is_disjoint(Es2, Set1);           % switch arguments!
% is_disjoint([_E1|_Es1], [_E2|_Es2]) ->        %E1 == E2
%     false;
% is_disjoint([], _) ->
%     true;
% is_disjoint(_, []) ->
%     true.


%% -----------------------------------------------------------------------------
%% @doc Return all and only the elements of IntervalSet1 which are not also in
%% IntervalSet2.
%% -----------------------------------------------------------------------------
-spec subtract(Set1 :: t(), Set2 :: t()) -> Set3 :: t().

subtract(Set1, Set2) ->
    compact(ordsets:subtract(to_flat_list(Set1), to_flat_list(Set2))).

% subtract([E1|Es1], [E2|_]=Set2) when E1 < E2 ->
%     [E1|subtract(Es1, Set2)];

% subtract([E1|_]=Set1, [E2|Es2]) when E1 > E2 ->
%     subtract(Set1, Es2);

% subtract([_E1|Es1], [_E2|Es2]) ->     %E1 == E2
%     subtract(Es1, Es2);

% subtract([], _) ->
%     [];

% subtract(Es1, []) ->
%     Es1.


%% -----------------------------------------------------------------------------
%% @doc Return 'true' when every element of IntervalSet1 is also a member of
%%  IntervalSet2, else 'false'.
%% -----------------------------------------------------------------------------
-spec is_subset(Set1 :: t(), Set2 :: t()) -> boolean().

is_subset(Set1, Set2) ->
    ordsets:is_subset(to_flat_list(Set1), to_flat_list(Set2)).

% is_subset([E1|_], [E2|_]) when E1 < E2 -> %E1 not in Set2
%     false;
% is_subset([E1|_]=Set1, [E2|Es2]) when E1 > E2 ->
%     is_subset(Set1, Es2);
% is_subset([_E1|Es1], [_E2|Es2]) ->        %E1 == E2
%     is_subset(Es1, Es2);
% is_subset([], _) -> true;
% is_subset(_, []) -> false.


%% -----------------------------------------------------------------------------
%% @doc Fold function Fun over all elements in OrdSet and return Accumulator.
%% -----------------------------------------------------------------------------
-spec fold(Function, Acc0, Sets) -> Acc1 when
      Function :: fun((Element :: element(), AccIn :: term()) -> AccOut :: term()),
      Sets :: t(),
      Acc0 :: term(),
      Acc1 :: term().

fold(F, Acc, Set) ->
    lists:foldl(F, Acc, Set).


%% -----------------------------------------------------------------------------
%% @doc Filter OrdSet with Fun.
%% -----------------------------------------------------------------------------
-spec filter(Pred, Set1) -> Set2 when
      Pred :: fun((Element :: element()) -> boolean()),
      Set1 :: t(),
      Set2 :: t().

filter(F, Set) ->
    lists:filter(F, Set).



%% =============================================================================
%% PRIVATE
%% =============================================================================



%% @private
interval({_, _} = E) ->
    E;

interval(N) ->
    {N, N}.


%% @private
simplify({N, N}) ->
    N;

simplify(E) ->
    E.


%% @private
equal({_, _} = A, A) ->
    true;

equal(N, {N, N}) ->
    true;

equal({N, N}, N) ->
    true;

equal(N, N) ->
    true;

equal(_, _) ->
    false.


%% @private
is_type([{E3, _} = E|Es], {_, E2}) when E2 =< E3 ->
    is_type(Es, E);

is_type([{_, _}|_], {_, _}) ->
    false;

is_type([{E2, _} = E|Es], E1) when E1 =< E2 ->
    is_type(Es, E);

is_type([{_, _}|_], _) ->
    false;

is_type([E3|Es], {_, E2}) when is_integer(E3), E2 =< E3 ->
    is_type(Es, E2);

is_type([_|_], {_, _}) ->
    false;

is_type([E2|Es], E1) when E1 < E2 ->
    is_type(Es, E2);

is_type([_|_], _) ->
    false;

is_type([], _) ->
    true.


%% @private
is_element_type(X) when is_integer(X) ->
    true;

is_element_type({X, Y}) when is_integer(X), is_integer(Y), X =< Y ->
    true;

is_element_type(_) ->
    false.


%% @private
validate_element(E) ->
    is_element_type(E) orelse error({badarg, E}),
    ok.


%% @private
compact(L) ->
    compact(L, []).


%% @private
compact([], _Acc) ->
    [];
compact([E1|Es], Acc) ->
    compact(Es, Acc, E1).


%% @private
compact([E|Es], Acc, E) ->
    compact(Es, Acc, E);

compact([{V3, V4}|Es], Acc, {V1, V2}) when V2 + 1 >= V3, V2 =< V4 ->
    E = {V1, V4},
    compact(Es, Acc, E);

compact([{V3, V4}|Es], Acc, {V1, V2}) when V2 + 1 >= V3, V2 > V4 ->
    E = {V1, V2},
    compact(Es, Acc, E);

compact([{_, _} = E2|Es], Acc, {_, _} = E1) ->
    %% There is a gap between E1 and E2
    compact(Es, [simplify(E1)|Acc], E2);

compact([{V1, V2}|Es], Acc, E1) when E1 + 1 >= V1, E1 =< V2 ->
    E = {E1, V2},
    compact(Es, Acc, E);

compact([{_, _} = E2|Es], Acc, E1) ->
    %% There is a gap between E1 and E2
    compact(Es, [simplify(E1)|Acc], E2);

compact([E2|Es], Acc, {V1, V2}) when E2 - 1 =< V2 ->
    %% E2 is covered by the interval or is next(V2)
    E = {V1, max(E2, V2)},
    compact(Es, Acc, E);

compact([E2|Es], Acc, {_, V2} = E1) when E2 =< V2 ->
    %% There is a gap between E1 and E2
    compact(Es, [simplify(E1)|Acc], E2);

compact([E2|Es], Acc, E1) when E1 + 1 == E2 ->
    E = {E1, E2},
    compact(Es, Acc, E);

compact([E2|Es], Acc, E1) ->
    %% There is a gap between E1 and E2
    compact(Es, [simplify(E1)|Acc], E2);

compact([], Acc, E) ->
    lists:reverse([simplify(E)|Acc]).


%% @private
element_includes({H1, T1}, {H2, T2}) ->
    H1 =< H2 andalso T1 >= T2;

element_includes({H, T}, N) ->
    H =< N andalso T >= N;

element_includes(N, {N, N}) ->
    true;

element_includes(_, {_, _}) ->
    false;

element_includes(N, M) ->
    N =:= M.


%% @private
element_included(A, B) ->
    element_includes(B, A).


%% @private
element_precedes({_, T1}, {H2, _}) ->
    T1 < H2;

element_precedes({_, T}, N) ->
    T < N;

element_precedes(N, {H, _}) ->
    N < H;

element_precedes(N, M) ->
    N < M.


%% @private
element_succeeds(A, B) ->
    element_precedes(B, A).


%% @private
element_starts_before({H1, _}, {H2, _}) ->
    H1 < H2;

element_starts_before({H, _}, N) ->
    H < N;

element_starts_before(N, {H, _}) ->
    N < H;

element_starts_before(N, M) ->
    N < M.


%% @private
element_overlaps({H1, T1}, {H2, T2}) ->
    H1 =< T2 andalso H2 =< T1;

element_overlaps({_, _} = A, N) ->
    element_overlaps(A, interval(N));

element_overlaps(N, {_, _} = B) ->
    element_overlaps(interval(N), B);

element_overlaps(A, B) ->
    A =:= B.


%% @private
element_meets({H1, T1} = A, {H2, T2} = B) ->
    (element_precedes(A, B) andalso H2 =:= T1 + 1)
        orelse (element_precedes(B, A) andalso H1 =:= T2 + 1);

element_meets({_, _} = A, N) ->
    element_meets(A, interval(N));

element_meets(N, {_, _} = B) ->
    element_meets(interval(N), B);

element_meets(A, B) ->
    abs(A - B) == 1.


%% private
unsafe_element_union({H1, T1}, {H2, T2}) ->
    {min(H1, H2), max(T1, T2)};

unsafe_element_union({_, _} = A, N) ->
    unsafe_element_union(A, interval(N));

unsafe_element_union(N, {_, _} = B) ->
    unsafe_element_union(interval(N), B);

unsafe_element_union(N, B) ->
    unsafe_element_union(interval(N), B).


%% private
element_intersection({_, _} = A, {_, _} = B) ->
    case element_overlaps(A, B) of
        true ->
            unsafe_element_intersection(A, B);
        false ->
            error(badarg)
    end;

element_intersection({_, _} = A, N) ->
    element_intersection(A, interval(N));

element_intersection(N, {_, _} = B) ->
    element_intersection(interval(N), B);

element_intersection(N, B) ->
    element_intersection(interval(N), B).


%% private
unsafe_element_intersection({H1, T1}, {H2, T2}) ->
    {max(H1, H2), min(T1, T2)};

unsafe_element_intersection({_, _} = A, N) ->
    unsafe_element_intersection(A, interval(N));

unsafe_element_intersection(N, {_, _} = B) ->
    unsafe_element_intersection(interval(N), B);

unsafe_element_intersection(N, B) ->
    unsafe_element_intersection(interval(N), B).


%% private
element_subtract(A, B) ->
    Empty =
        element_precedes(A, B)
        orelse element_included(A, B)
        orelse element_succeeds(A, B),

    case Empty of
        true ->
            [];
        false ->
            do_element_subtract(A, B)
    end.

do_element_subtract({H1, T1}, {H2, T2}) when H1 >= H2, T1 > T2 ->
    [{max(T2 + 1, H1), T1}];

do_element_subtract({H1, T1}, {H2, T2}) when H1 < H2, T1 =< T2 ->
    [{H1, min(H2 - 1, T1)}];

do_element_subtract({H1, T1}, {H2, T2}) when H1 < H2, T1 > T2 ->
    %% A includes B
    [{H1, H2 - 1}, {T2 + 1, T1}];

do_element_subtract({_, _} = A, N) when is_integer(N) ->
    do_element_subtract(A, interval(N));

do_element_subtract(N, {_, _} = B) when is_integer(N) ->
    do_element_subtract(interval(N), B);

do_element_subtract(_, _) ->
    error(badarg).



-ifdef(TEST).
%% DISABLED FOR NOW

%% @private
element_merges(A, B) ->
    element_overlaps(A, B) orelse element_meets(A, B).

%% @private
element_begins({H1, T1}, {H2, _} = B) ->
    H1 =:= H2 andalso is_element(T1, [B]);

element_begins({_, _} = A, N) ->
    element_begins(A, interval(N));

element_begins(N, {_, _} = B) ->
    element_begins(interval(N), B);

element_begins(_, _) ->
    false.


%% @private
element_ends({H1, T1}, {_, T2} = B) ->
    T1 =:= T2 andalso is_element(H1, [B]);

element_ends({_, _} = A, N) ->
    element_ends(A, interval(N));

element_ends(N, {_, _} = B) ->
    element_ends(interval(N), B);

element_ends(_, _) ->
    false.


%% private
element_union({_, _} = A, {_, _} = B) ->
    case element_merges(A, B) of
        true ->
            unsafe_element_union(A, B);
        false ->
            error(badarg)
    end;

element_union({_, _} = A, N) ->
    element_union(A, interval(N));

element_union(N, {_, _} = B) ->
    element_union(interval(N), B);

element_union(N, B) ->
    element_union(interval(N), B).

-endif.

%% =============================================================================
%% EUNIT
%% =============================================================================

-ifdef(TEST).


%% @private
element_merges(A, B) ->
    element_overlaps(A, B) orelse element_meets(A, B).

%% @private
element_begins({H1, T1}, {H2, _} = B) ->
    H1 =:= H2 andalso is_element(T1, [B]);

element_begins({_, _} = A, N) ->
    element_begins(A, interval(N));

element_begins(N, {_, _} = B) ->
    element_begins(interval(N), B);

element_begins(_, _) ->
    false.


%% @private
element_ends({H1, T1}, {_, T2} = B) ->
    T1 =:= T2 andalso is_element(H1, [B]);

element_ends({_, _} = A, N) ->
    element_ends(A, interval(N));

element_ends(N, {_, _} = B) ->
    element_ends(interval(N), B);

element_ends(_, _) ->
    false.


%% private
element_union({_, _} = A, {_, _} = B) ->
    case element_merges(A, B) of
        true ->
            unsafe_element_union(A, B);
        false ->
            error(badarg)
    end;

element_union({_, _} = A, N) ->
    element_union(A, interval(N));

element_union(N, {_, _} = B) ->
    element_union(interval(N), B);

element_union(N, B) ->
    element_union(interval(N), B).



from_list_test_() ->
    Expected = [{1, 2}, 4, {6, 10}],
    [
        ?_assertEqual(Expected, from_list([1, 2, 4, 6, 7, 8, 9, 10])),
        ?_assertEqual(Expected, from_list([{1, 2}, 4, 6, 7, 8, 9, 10])),
        ?_assertEqual(Expected, from_list([{1, 2}, 4, {6, 7}, 8, 9, 10])),
        ?_assertEqual(Expected, from_list([{1, 2}, 4, {6, 7}, 8, {9, 10}])),
        ?_assertEqual(Expected, from_list(Expected))
    ].


to_flat_list_test_() ->
    Expected = [1, 2, 4, 6, 7, 8, 9, 10],
    [
        ?_assertEqual(Expected, to_flat_list(Expected)),
        ?_assertEqual(Expected, to_flat_list([{1, 2}, 4, 6, 7, 8, 9, 10])),
        ?_assertEqual(Expected, to_flat_list([{1, 2}, 4, {6, 7}, 8, 9, 10])),
        ?_assertEqual(Expected, to_flat_list([{1, 2}, 4, {6, 10}]))
    ].


is_type_test_() ->
    [
        ?_assert(true =:= is_type([1, 2, 4, 6, 7, 8, 9, 10])),
        ?_assert(true =:= is_type([{1, 2}, 4, 6, 7, 8, 9, 10])),
        ?_assert(true =:= is_type([{1, 2}, 4, {6, 7}, 8, 9, 10])),
        ?_assert(true =:= is_type([{1, 2}, 4, {6, 7}, 8, {9, 10}])),
        ?_assert(true =:= is_type([{1, 2}, 4, {6, 10}])),
        ?_assert(false =:= is_type([0.23])),
        ?_assert(false =:= is_type([atom])),
        ?_assert(false =:= is_type([<<>>]))
    ].


is_element_test_() ->
    [
        ?_assert(true =:= is_element(1, [{1, 2}, 4, {6, 10}])),
        ?_assert(true =:= is_element(2, [{1, 2}, 4, {6, 10}])),
        ?_assert(false =:= is_element(3, [{1, 2}, 4, {6, 10}])),
        ?_assert(true =:= is_element(4, [{1, 2}, 4, {6, 10}])),
        ?_assert(false =:= is_element(5, [{1, 2}, 4, {6, 10}])),
        ?_assert(true =:= is_element(6, [{1, 2}, 4, {6, 10}])),
        ?_assert(true =:= is_element(7, [{1, 2}, 4, {6, 10}])),
        ?_assert(true =:= is_element(8, [{1, 2}, 4, {6, 10}])),
        ?_assert(true =:= is_element(9, [{1, 2}, 4, {6, 10}])),
        ?_assert(true =:= is_element(10, [{1, 2}, 4, {6, 10}])),
        ?_assert(false =:= is_element(11, [{1, 2}, 4, {6, 10}])),
        ?_assert(false =:= is_element({1,6}, [{1, 2}, 4, {6, 10}])),
        ?_assert(true =:= is_element({6,7}, [{1, 2}, 4, {6, 10}])),
        ?_assert(true =:= is_element({7,10}, [{1, 2}, 4, {6, 10}])),
        ?_assert(false =:= is_element({8,11}, [{1, 2}, 4, {6, 10}]))
    ].


flat_size_test_() ->
    [
        ?_assert(8 =:= flat_size([1, 2, 4, 6, 7, 8, 9, 10])),
        ?_assert(8 =:= flat_size([{1, 2}, 4, 6, 7, 8, 9, 10])),
        ?_assert(8 =:= flat_size([{1, 2}, 4, {6, 7}, 8, 9, 10])),
        ?_assert(8 =:= flat_size([{1, 2}, 4, {6, 7}, 8, {9, 10}])),
        ?_assert(8 =:= flat_size([{1, 2}, 4, {6, 10}]))
    ].

min_test_() ->
    [
        ?_assert(1 =:= min([1, 2, 4, 6, 7, 8, 9, 10])),
        ?_assert(1 =:= min([{1, 2}, 4, 6, 7, 8, 9, 10])),
        ?_assert(1 =:= min([{1, 2}, 4, {6, 7}, 8, 9, 10])),
        ?_assert(1 =:= min([{1, 2}, 4, {6, 7}, 8, {9, 10}])),
        ?_assert(1 =:= min([{1, 2}, 4, {6, 10}]))
    ].

max_test_() ->
    [
        ?_assert(10 =:= max([1, 2, 4, 6, 7, 8, 9, 10])),
        ?_assert(10 =:= max([{1, 2}, 4, 6, 7, 8, 9, 10])),
        ?_assert(10 =:= max([{1, 2}, 4, {6, 7}, 8, 9, 10])),
        ?_assert(10 =:= max([{1, 2}, 4, {6, 7}, 8, {9, 10}])),
        ?_assert(10 =:= max([{1, 2}, 4, {6, 10}]))
    ].

element_precedes_test_() ->
    [
        ?_assert(element_precedes(0, {2, 3})),
        ?_assert(element_precedes(1, {2, 3})),
        ?_assert(element_precedes({0, 1}, {2, 3})),
        ?_assert(false =:= element_precedes({1, 1}, 1)),
        ?_assert(false =:= element_precedes({0, 1}, {0, 1})),
        ?_assert(false =:= element_precedes({0, 3}, {2, 3})),
        ?_assert(false =:= element_precedes({3, 4}, {2, 3})),
        ?_assert(false =:= element_precedes({4, 5}, {2, 3}))
    ].

element_meets_test_() ->
    [
        ?_assert(false =:= element_meets({1, 1}, 1)),
        ?_assert(false =:= element_meets({0, 1}, {0, 1})),
        ?_assert(false =:= element_meets({0, 3}, {2, 3})),
        ?_assert(false =:= element_meets({3, 4}, {2, 3})),
        ?_assert(element_meets({0, 1}, {2, 3})),
        ?_assert(element_meets({4, 5}, {2, 3}))
    ].

element_subtract_test_() ->
    [
        ?_assertEqual([], element_subtract(16, 16)),
        ?_assertEqual([], element_subtract({0, 16}, {0, 16})),
        ?_assertEqual([], element_subtract({4, 16}, {0, 16})),
        ?_assertEqual([], element_subtract({0, 5}, {0, 10})),
        ?_assertEqual([], element_subtract({5, 10}, {3, 20})),

        ?_assertEqual([{0, 1}], element_subtract({0, 16}, {2, 16})),
        ?_assertEqual([{9, 16}], element_subtract({0, 16}, {0, 8})),
        ?_assertEqual([{9, 16}], element_subtract({4, 16}, {4, 8})),
        ?_assertEqual([{9, 16}], element_subtract({4, 16}, {4, 8})),
        ?_assertEqual([{11, 20}], element_subtract({3, 20}, {0, 10})),
        ?_assertEqual([{0, 7}], element_subtract({0, 16}, {8, 20})),

        ?_assertEqual([{0, 1}, {9, 16}], element_subtract({0, 16}, {2, 8})),
        ?_assertEqual([{0, 3}, {9, 16}], element_subtract({0, 16}, {4, 8})),
        ?_assertEqual([{3, 4}, {11, 20}], element_subtract({3, 20}, {5, 10}))
    ].

add_element_test_() ->
    Cases = [
        % {Expected, Element, Set}
        {[{0, 1}, {3, 4}], {0, 1}, [{3, 4}]},
        {[0, {3, 4}], 0, [{3, 4}]},
        {[1, {3, 4}], 1, [{3, 4}]},
        {[{0, 3}], {0, 1}, [{2, 3}]},
        {[{0, 3}], {0, 2}, [{2, 3}]},
        {[{0, 3}], {0, 3}, [{2, 3}]},
        {[{0, 4}], {0, 4}, [{2, 3}]},
        {[{0, 4}], {0, 4}, [{0, 3}]},
        {[{0, 4}], {0, 4}, [{0, 4}]},
        {[{2, 10}], {3, 10}, [{2, 3}]},
        {[{2, 3}, {20, 30}], {20, 30}, [{2, 3}]}
    ],
    lists:append([
        [
            ?_assertEqual(Expected, add_element(Element, Set)),
            ?_assertEqual(
                ordsets:union(to_flat_list([Element]), to_flat_list(Set)),
                to_flat_list(add_element(Element, Set))
            )
        ]
        || {Expected, Element, Set} <- Cases
    ]).


del_element_test_() ->
    Cases = [
        {[2], 1, [2]},
        {[{2, 3}], 1, [{2, 3}]},
        {[], 1, [1]},
        {[], 1, [{1, 1}]},
        {[], {1, 2}, [{1, 2}]},
        {[{3, 4}], {0, 1}, [{3, 4}]},
        {[{2, 4}], {0, 1}, [{0, 4}]},
        {[{0, 2}, {15, 16}], {3, 14}, [{0, 16}]}
    ],
    lists:append([
        [
            ?_assertEqual(Expected, del_element(Element, Set)),
            ?_assertEqual(
                ordsets:subtract(to_flat_list(Set), to_flat_list([Element])),
                to_flat_list(del_element(Element, Set))
            )
        ]
        || {Expected, Element, Set} <- Cases
    ]).


-endif.