-module(hyper_test).
-include_lib("proper/include/proper.hrl").
-include_lib("eunit/include/eunit.hrl").

-record(hyper, {p, registers}). % copy of #hyper in hyper.erl

hyper_test_() ->
    {foreach, fun () -> ok end, fun (_) -> ok end,
     [
      ?_test(basic_t()),
      ?_test(serialization_t()),
      {timeout, 30, ?_test(backend_t())},
      ?_test(encoding_t()),
      ?_test(register_sum_t()),
      {timeout, 30, ?_test(error_range_t())},
      ?_test(many_union_t()),
      ?_test(union_t()),
      ?_test(small_big_union_t()),
      ?_test(intersect_card_t()),
      {timeout, 600, fun () -> [] = proper:module(?MODULE) end},
      ?_test(bad_serialization_t())
     ]}.

basic_t() ->
    [?assertEqual(1, trunc(
                       hyper:card(
                         hyper:insert(<<"1">>, hyper:new(4, Mod)))))
     || Mod <- [hyper_bisect, hyper_binary, hyper_gb, hyper_array]].


serialization_t() ->
    Mod = hyper_binary,
    Hyper = hyper:compact(hyper:insert_many(generate_unique(10), hyper:new(5, Mod))),

    {hyper_binary, L} = Hyper#hyper.registers,
    {hyper_binary, R} = (hyper:compact(
                           hyper:from_json(
                             hyper:to_json(Hyper), Mod)))#hyper.registers,

    ?assertEqual(trunc(hyper:card(Hyper)),
                 trunc(
                   hyper:card(
                     hyper:from_json(
                       hyper:to_json(Hyper), Mod)))),
    ?assertEqual(Hyper#hyper.p, (hyper:from_json(
                                   hyper:to_json(Hyper), Mod))#hyper.p),
    ?assertEqual(L, R).


backend_t() ->
    Values = generate_unique(1000000),
    P = 9,
    M = trunc(math:pow(2, P)),

    Gb     = hyper:compact(hyper:insert_many(Values, hyper:new(P, hyper_gb))),
    Array  = hyper:compact(hyper:insert_many(Values, hyper:new(P, hyper_array))),
    Bisect = hyper:compact(hyper:insert_many(Values, hyper:new(P, hyper_bisect))),
    Binary = hyper:compact(hyper:insert_many(Values, hyper:new(P, hyper_binary))),


    {hyper_gb    , GbRegisters}     = Gb#hyper.registers,
    {hyper_array , ArrayRegisters}  = Array#hyper.registers,
    {hyper_bisect, BisectRegisters} = Bisect#hyper.registers,
    {hyper_binary, BinaryRegisters} = Binary#hyper.registers,

    %% error_logger:info_msg("Gb:     ~p~nArray:  ~p~nBisect: ~p~nBinary: ~p~n",
    %%                       [hyper_gb:encode_registers(GbRegisters),
    %%                        hyper_array:encode_registers(ArrayRegisters),
    %%                        hyper_bisect:encode_registers(BisectRegisters),
    %%                        hyper_binary:encode_registers(BinaryRegisters)]),


    ExpectedRegisters = lists:foldl(
                          fun (Value, Registers) ->
                                  Hash = crypto:hash(sha, Value),
                                  <<Index:P, RegisterValue:P/bitstring,
                                    _/bitstring>> = Hash,
                                  ZeroCount = hyper:run_of_zeroes(RegisterValue)
                                      + 1,

                                  case orddict:find(Index, Registers) of
                                      {ok, R} when R > ZeroCount ->
                                          Registers;
                                      _ ->
                                          orddict:store(Index, ZeroCount, Registers)
                                  end
                          end, orddict:new(), Values),
    ExpectedBytes = iolist_to_binary(
                      [begin
                           case orddict:find(I, ExpectedRegisters) of
                               {ok, V} ->
                                   <<V:8/integer>>;
                               error ->
                                   <<0>>
                           end
                       end || I <- lists:seq(0, M-1)]),

    ?assertEqual(ExpectedBytes, hyper_gb:encode_registers(GbRegisters)),
    ?assertEqual(ExpectedBytes, hyper_array:encode_registers(ArrayRegisters)),
    ?assertEqual(ExpectedBytes, hyper_bisect:encode_registers(BisectRegisters)),
    ?assertEqual(ExpectedBytes, hyper_binary:encode_registers(BinaryRegisters)),

    ?assertEqual(hyper:card(Gb),
                 hyper:card(hyper:from_json(hyper:to_json(Array), hyper_gb))),
    ?assertEqual(Array, hyper:from_json(hyper:to_json(Array), hyper_array)),
    ?assertEqual(Array, hyper:from_json(hyper:to_json(Bisect), hyper_array)),
    ?assertEqual(Bisect, hyper:from_json(hyper:to_json(Array), hyper_bisect)),

    ?assertEqual(hyper:to_json(Gb), hyper:to_json(Array)),
    ?assertEqual(hyper:to_json(Gb), hyper:to_json(Bisect)),
    ?assertEqual(hyper:to_json(Gb), hyper:to_json(Binary)),

    ?assertEqual(hyper:card(Gb), hyper:card(Array)),
    ?assertEqual(hyper:card(Gb), hyper:card(Bisect)),
    ?assertEqual(hyper:card(Gb), hyper:card(Binary)).


encoding_t() ->
    [begin
         P = 15,
         M = trunc(math:pow(2, P)),
         Hyper = hyper:insert_many(generate_unique(150000), hyper:new(P, Mod)),
         ?assertEqual(trunc(hyper:card(Hyper)),
                      trunc(hyper:card(hyper:from_json(hyper:to_json(Hyper), Mod)))),

         {Struct} = hyper:to_json(Hyper),
         Serialized = zlib:gunzip(
                        base64:decode(
                          proplists:get_value(<<"registers">>, Struct))),

         WithPadding =  <<Serialized/binary, 0>>,

         B            = Mod:encode_registers(Mod:decode_registers(Serialized, P)),
         BWithPadding = Mod:encode_registers(Mod:decode_registers(WithPadding, P)),
         ?assertEqual(M, byte_size(B)),
         ?assertEqual(M, byte_size(BWithPadding)),
         ?assertEqual(B, BWithPadding)
     end || Mod <- backends()].


register_sum_t() ->
    Mods = [hyper_array, hyper_gb, hyper_bisect, hyper_binary],
    P = 4,
    M = trunc(math:pow(2, P)),

    SetRegisters = [1, 5, 10],
    RegisterValue = 3,

    ExpectedSum =
        (math:pow(2, -0) * M)
        - (math:pow(2, -0) * length(SetRegisters))
        + (math:pow(2, -RegisterValue) * length(SetRegisters)),

    [begin
         Registers = lists:foldl(fun (I, Acc) ->
                                         Mod:set(I, RegisterValue, Acc)
                                 end, Mod:new(P), SetRegisters),
         Compact = Mod:compact(Registers),
         ?assertEqual({Mod, ExpectedSum}, {Mod, Mod:register_sum(Compact)})
     end || Mod <- Mods].


error_range_t() ->
    Mods = [hyper_gb, hyper_array, hyper_bisect, hyper_binary],
    Run = fun (Cardinality, P, Mod) ->
                  lists:foldl(fun (V, H) ->
                                      hyper:insert(V, H)
                              end, hyper:new(P, Mod), generate_unique(Cardinality))
          end,
    ExpectedError = 0.02,
    P = 14,
    random:seed(1, 2, 3),

    [begin
         Estimate = trunc(hyper:card(Run(Card, P, Mod))),
         ?assert(abs(Estimate - Card) < Card * ExpectedError)
     end || Card <- lists:seq(1000, 50000, 5000),
            Mod <- Mods].

many_union_t() ->
    random:seed(1, 2, 3),
    Card = 1000,
    NumSets = 3,

    [begin
         M = trunc(math:pow(2, P)),
         Error = 1.04 / math:sqrt(M),

         Sets = [sets:from_list(generate_unique(Card))
                 || _ <- lists:seq(1, NumSets)],
         Filters = [hyper:insert_many(sets:to_list(S), hyper:new(P, Mod))
                    || S <- Sets],

         ExpectedFilter = hyper:compact(
                            hyper:insert_many(
                              lists:flatten([sets:to_list(S) || S <- Sets]),
                              hyper:new(P, Mod))),
         H = hyper:union(Filters),

         {Mod, ExpectedRegisters} = ExpectedFilter#hyper.registers,
         {Mod, ActualRegisters} = H#hyper.registers,

         ?assertEqual(Mod:encode_registers(ExpectedRegisters),
                      Mod:encode_registers(ActualRegisters)),

         Delta = abs(sets:size(sets:union(Sets)) - hyper:card(hyper:union(Filters))),
         case Delta < (Card * NumSets * Error) of
             true ->
                 ok;
             false ->
                 error_logger:info_msg("too high error, expected ~.2f%, actual ~.2f%~n"
                                       "~p, p = ~p, card = ~p",
                                       [Error, Delta / (Card * NumSets), Mod, P, Card]),
                 ?assert(false)
         end
     end || Mod <- backends(),
            P <- [15]].


union_t() ->
    random:seed(1, 2, 3),

    LeftDistinct = sets:from_list(generate_unique(10000)),

    RightDistinct = sets:from_list(generate_unique(5000)
                                   ++ lists:sublist(sets:to_list(LeftDistinct),
                                                    5000)),

    LeftHyper = hyper:insert_many(sets:to_list(LeftDistinct), hyper:new(13)),
    RightHyper = hyper:insert_many(sets:to_list(RightDistinct), hyper:new(13)),

    UnionHyper = hyper:union([LeftHyper, RightHyper]),
    Intersection = hyper:card(LeftHyper)
        + hyper:card(RightHyper) - hyper:card(UnionHyper),

    ?assert(abs(hyper:card(UnionHyper) -
                    sets:size(sets:union(LeftDistinct, RightDistinct)))
            < 200),
    ?assert(abs(Intersection - sets:size(
                                 sets:intersection(LeftDistinct, RightDistinct)))
            < 200).

small_big_union_t() ->
    random:seed(1, 2, 3),
    SmallCard = 100,
    BigCard   = 15000, % switches to dense at 10922 items

    SmallSet = sets:from_list(generate_unique(SmallCard)),
    BigSet   = sets:from_list(generate_unique(BigCard)),

    SmallHyper = hyper:insert_many(sets:to_list(SmallSet),
                                   hyper:new(15, hyper_bisect)),
    BigHyper   = hyper:insert_many(sets:to_list(BigSet),
                                   hyper:new(15, hyper_bisect)),
    ?assertMatch({hyper_bisect, {sparse, _, _, _}}, SmallHyper#hyper.registers),
    ?assertMatch({hyper_bisect, {dense, _}}, BigHyper#hyper.registers),

    UnionHyper = hyper:union(SmallHyper, BigHyper),
    TrueUnion = sets:size(sets:union(SmallSet, BigSet)),
    ?assert(abs(hyper:card(UnionHyper) - TrueUnion) < TrueUnion * 0.01).


intersect_card_t() ->
    random:seed(1, 2, 3),

    LeftDistinct = sets:from_list(generate_unique(10000)),

    RightDistinct = sets:from_list(generate_unique(5000)
                                   ++ lists:sublist(sets:to_list(LeftDistinct),
                                                    5000)),

    LeftHyper = hyper:insert_many(sets:to_list(LeftDistinct), hyper:new(13)),
    RightHyper = hyper:insert_many(sets:to_list(RightDistinct), hyper:new(13)),

    IntersectCard = hyper:intersect_card(LeftHyper, RightHyper),

    ?assert(IntersectCard =< hyper:card(hyper:union(LeftHyper, RightHyper))),

    %% NOTE: we can't really say much about the error here,
    %% so just pick something and see if the intersection makes sense
    Error = 0.05,
    ?assert((abs(5000 - IntersectCard) / 5000) =< Error).


bad_serialization_t() ->
    [begin
         P = 15,
         M = trunc(math:pow(2, P)),
         {ok, WithNewlines} = file:read_file("../test/filter.txt"),
         Raw = case zlib:gunzip(
                      base64:decode(
                        binary:replace(WithNewlines, <<"\n">>, <<>>))) of
                   <<RawBytes:M/binary>> ->
                       RawBytes;
                   <<RawBytes:M/binary, 0>> ->
                       %% TODO: test padding
                       RawBytes
               end,

         H = hyper:from_json({[{<<"p">>, 15},
                               {<<"registers">>, base64:encode(zlib:gzip(Raw))}]},
                             Mod),
         {Mod, Registers} = H#hyper.registers,
         Encoded = Mod:encode_registers(Registers),

         ?assertEqual(size(Raw), size(Encoded)),
         lists:foreach(fun (I) ->
                               ?assertEqual(binary:at(Raw, I),
                                            binary:at(Encoded, I))
                       end, lists:seq(0, size(Encoded) - 1)),

         ?assertEqual(Raw, Mod:encode_registers(Registers)),

         ?assertEqual({[{<<"p">>, 15},
                        {<<"registers">>, base64:encode(zlib:gzip(Raw))}]},
                      hyper:to_json(H))
     end || Mod <- backends()].

%%
%% PROPERTIES
%%

backends() ->
    [hyper_gb, hyper_array, hyper_bisect, hyper_binary].

gen_values() ->
    %% ?LET(S, oneof(lists:seq(1, 100000, 10)), generate_unique(S)).
    ?SIZED(Size, generate_unique(Size*4)).

expected_bytes(P, Values) ->
    M = trunc(math:pow(2, P)),
    ExpectedRegisters = lists:foldl(
                          fun (Value, Registers) ->
                                  Hash = crypto:hash(sha, Value),
                                  <<Index:P, RegisterValue:P/bitstring,
                                    _/bitstring>> = Hash,
                                  ZeroCount = hyper:run_of_zeroes(RegisterValue)
                                      + 1,

                                  case orddict:find(Index, Registers) of
                                      {ok, R} when R > ZeroCount ->
                                          Registers;
                                      _ ->
                                          orddict:store(Index, ZeroCount, Registers)
                                  end
                          end, orddict:new(), Values),
    iolist_to_binary(
      [begin
           case orddict:find(I, ExpectedRegisters) of
               {ok, V} ->
                   <<V:8/integer>>;
               error ->
                   <<0>>
           end
       end || I <- lists:seq(0, M-1)]).


prop_getset() ->
    ?FORALL({Mod, P, Values}, {oneof(backends()), range(4, 16), gen_values()},
            begin
                L = lists:map(
                      fun (Value) ->
                              Hash = crypto:hash(sha, Value),
                              <<Index:P, RegisterValue:P/bitstring,
                                _/bitstring>> = Hash,
                              ZeroCount = hyper:run_of_zeroes(RegisterValue)
                                  + 1,
                              {Index, ZeroCount}
                      end, Values),

                R = lists:foldl(
                      fun ({Index, ZeroCount}, Register) ->
                              Mod:set(Index, ZeroCount, Register)
                      end, Mod:new(P), L),
                case Mod:encode_registers(Mod:compact(R))
                    =:= expected_bytes(P, Values) of
                    true ->
                        true;
                    false ->
                        error_logger:info_msg("values~n~p~n"
                                              "encoded~n~p~n"
                                              "expected~n~p~n",
                                              [L,
                                               Mod:encode_registers(R),
                                               expected_bytes(P, Values)]),
                        false
                end
            end).

prop_serialize() ->
    ?FORALL({Mod, P, Values}, {oneof(backends()), range(4, 16), gen_values()},
            begin
                H = hyper:compact(hyper:insert_many(Values, hyper:new(P, Mod))),
                H =:= hyper:compact(
                        hyper:from_json(
                          hyper:to_json(H), Mod))
            end).

%%
%% HELPERS
%%


generate_unique(N) ->
    generate_unique(lists:usort(random_bytes(N)), N).


generate_unique(L, N) ->
    case length(L) of
        N ->
            L;
        Less ->
            generate_unique(lists:usort(random_bytes(N - Less) ++ L), N)
    end.


random_bytes(N) ->
    random_bytes([], N).

random_bytes(Acc, 0) -> Acc;
random_bytes(Acc, N) ->
    Int = random:uniform(100000000000000),
    random_bytes([<<Int:64/integer>> | Acc], N-1).