efuse_filter

%%-----------------------------------------------------------------------------
%% @copyright (C) 2021, Matthew Pope
%% @author Matthew Pope
%% @doc Interface for the fuse8 filter.
%%
%% For a full set of examples, see the GitHub README at 
%%  https://github.com/mpope9/efuse_filter/blob/main/README.md
%%
%% Example usage:
%% ```
%% Filter = fuse8:new(["cat", "dog", "mouse"]),
%% true   = fuse8:contain(Filter, "cat"),
%% false  = fuse8:contain(Filter, "goose").
%% '''
%% @end
%%-----------------------------------------------------------------------------
-module(fuse8).

-export([
    new/1,
    new/2,
    new_empty/0,
    new_empty/1,
    contain/2,
    contain/3,
    contain/4,
    add/2,
    finalize/1,
    to_bin/1,
    from_bin/1,
    from_bin/2
]).

-record(fuse8, {
    reference :: reference() | undefined,
    hashing_method :: default | none,
    elements :: set:set() | undefined
}).

-type fuse8() :: #fuse8{}.

-export_type([fuse8/0]).

%%-----------------------------------------------------------------------------
%% @doc Initializes the fuse filter
%%
%% Initializes a fuse8 filter frim the passed values. Each value is hashed
%% using the `erlang:phash2/1' function.
%%
%% Returns a fuse8 type, which is a filter to be used in `contain'
%% If a predefined set of hashes is desired, pass `none' as the second
%% argument.
%%
%% Otherwise, an `{error, reason}' tuple will be returned.
%%
%% Do not modify the return value of this function.
%% @end
%%-----------------------------------------------------------------------------
-spec new(List::[term()]) -> fuse8:fuse8() | {error, atom()}.

new(List) when is_list(List) ->

    HashedSet = lists:foldl(
        fun (Element, Set) ->
            sets:add_element(erlang:phash2(Element), Set)
        end, sets:new([{version, 2}]), List),

    HashedList = sets:to_list(HashedSet),

    FilterFun = case over_100k(HashedList) of
        true -> fun efuse_filter:fuse8_initialize_nif_dirty/1;
        false -> fun efuse_filter:fuse8_initialize_nif/1
    end,
    #fuse8{
        reference = FilterFun(HashedList), 
        hashing_method = default,
        elements = undefined}.


-spec new(List::[term()], atom()) -> fuse8:fuse8() | {error, atom()}.

new(List, none) when is_list(List) ->

    Set = lists:foldl(
        fun (Element, Set) ->
            sets:add_element(Element, Set)
        end, sets:new([{version, 2}]), List),

    DedupedList = sets:to_list(Set),

    AllInts = lists:any(fun(Val) -> is_integer(Val) end, DedupedList),

    case AllInts of

        false ->
            {error, pre_hashed_values_should_be_ints};

        true ->

            FilterFun = case over_100k(List) of
                true -> fun efuse_filter:fuse8_initialize_nif_dirty/1;
                false -> fun efuse_filter:fuse8_initialize_nif/1
            end,
            #fuse8{
                reference = FilterFun(DedupedList),
                hashing_method = none,
                elements = undefined}
    end;

new(_List, _Method) ->
    {error, invalid_hash_method}.


%%-----------------------------------------------------------------------------
%% @doc Initializes an empty filter. This should be filled incrementally.
%% Do not modify the reutrn value of this function.
%% @end
%%-----------------------------------------------------------------------------
-spec new_empty() -> fuse8:fuse8().

new_empty() ->
    #fuse8{
        reference = undefined,
        hashing_method = default,
        elements = sets:new([{version, 2}])
    }.


%%-----------------------------------------------------------------------------
%% @doc Initializes an empty filter. This should be filled incrementally.
%% If a value other than `none' is passed, then `{error, invalid_hash_method}'
%% will be returned. Values passed to `fuse8:add/2' need to be pre-hashed as
%% integers before adding to a filter returned by this function.
%% Do not modify the return value of this function.
%% @end
%%-----------------------------------------------------------------------------
-spec new_empty(atom()) -> fuse8:fuse8() | {error, atom()}.

new_empty(none) ->
    #fuse8{
        reference = undefined,
        hashing_method = none,
        elements = sets:new([{version, 2}])
    };

new_empty(_) ->
    {error, invalid_hash_method}.


%%-----------------------------------------------------------------------------
%% @doc Tests to see if the passed argument is in the filter.  The first
%% argument must be the pre-initialized filter. Returns `false' if the
%% argument is not found.
%%
%% A filter previously serialized by `to_bin' is allowed
%% @end
%%-----------------------------------------------------------------------------
-spec contain(Filter::fuse8:fuse8() | binary(), Key::term()) -> term().

contain(Filter, Key) ->
    contain(Filter, Key, false).


%%-----------------------------------------------------------------------------
%% @doc Tests to see if the passed argument is in the filter.  The first
%% argument must be the pre-initialized filter. If the value is not found,
%% the third arguement is returned instead of `false'.
%%
%% A filter previously serialized by `to_bin' is allowed
%%
%% If an invalid filter is passed or if the key is not an integer and the 
%% hashing method is set to `none' then false will be returned.
%%
%% @end
%%-----------------------------------------------------------------------------
-spec contain(Filter::fuse8:fuse8() | binary(), Key::term(), Default::term()) 
    -> true | term().

contain(<<Filter/binary>>, Key, Default) ->
    case efuse_filter:fuse8_contain_nif(Filter, erlang:phash2(Key)) of
        true -> true;
        false -> Default
    end;

contain(#fuse8{hashing_method = none}, Key, _Default)
    when not is_integer(Key) ->

    _Default;

contain(#fuse8{reference = Filter}, _Key, _Default)
    when Filter == undefined ->

    _Default;

contain(#fuse8{reference = Filter, hashing_method = none}, Key, Default)
    when is_integer(Key) ->

    case efuse_filter:fuse8_contain_nif(Filter, Key) of
        true -> true;
        false -> Default
    end;

contain(#fuse8{reference = Filter, hashing_method = default}, Key, Default) ->

    case efuse_filter:fuse8_contain_nif(Filter, erlang:phash2(Key)) of
        true -> true;
        false -> Default
    end;

contain(_Filter, _Key, _Default) ->
    _Default.


%%-----------------------------------------------------------------------------
%% @doc This function exists for testing if an element exists in a
%% serialized filter with custom hashing.
%% The first argument should be the pre-initialized and seralized filter.
%% The second argument is the key that will be tested.
%% The third arguement is returned instead of `false'.
%% The fourth argument should be `none'.
%%
%% If an invalid filter is passed or if the key is not an integer and the 
%% hashing method is set to `none' then false will be returned.
%%
%% @end
%%-----------------------------------------------------------------------------
-spec contain(Filter::binary(), Key::integer(), Default::term(), none)
    -> term().

contain(_Filter, Key, Default, none) when not is_integer(Key) ->
    Default;

contain(<<Filter/binary>>, Key, Default, none) ->
    case efuse_filter:fuse8_contain_nif(Filter, Key) of
        true -> true;
        false -> Default
    end;

contain(_Filter, _Key, Default, _HashingMethod) ->
    Default.

%%-----------------------------------------------------------------------------
%% @doc Adds elements to filter, and applys the default hashing mechanism if
%% `none' wasn't specified in the `fuse8:new_empty/1' function. This function
%% attempts to catch issues early, before they reach the NIF code. So if
%% any elements that are passed when custom hashing was specified this 
%% function will return `{error, pre_hashed_values_should_be_ints}'.
%%
%% This function accepts both a list of elements and a single element.
%% @end
%%-----------------------------------------------------------------------------
-spec add(Filter::fuse8:fuse8(), Element::term()) -> fuse8:fuse8() | {error, atom()}.

add(#fuse8{reference = Reference}, _Elements) when Reference /= undefined ->
    {error, already_initialized_filter};

add(#fuse8{elements = undefined}, _Elements) ->
    {error, uninitialized_filter};

add(#fuse8{hashing_method = default, elements = Elements} = Filter, ElementsInput) 
    when is_list(ElementsInput) ->

    ElementsNew = lists:foldl(
        fun(Element, Acc) ->
            sets:add_element(erlang:phash2(Element), Acc)
        end, Elements, ElementsInput),

    Filter#fuse8{elements = ElementsNew};

add(#fuse8{hashing_method = default, elements = Elements} = Filter, Element) ->
    Filter#fuse8{elements = sets:add_element(erlang:phash2(Element), Elements)};

add(#fuse8{hashing_method = none, elements = Elements} = Filter, ElementsInput) 
    when is_list(ElementsInput) ->

    case lists:any(fun(Val) -> is_integer(Val) end, ElementsInput) of

        false ->
            {error, pre_hashed_values_should_be_ints};

        true ->

            ElementsNew = lists:foldl(
                fun(Element, Acc) ->
                    sets:add_element(Element, Acc)
                end, Elements, ElementsInput),
            Filter#fuse8{elements = ElementsNew}

    end;

add(#fuse8{hashing_method = none, elements = Elements} = Filter, Element) ->

    case is_integer(Element) of

        false ->
            {error, pre_hashed_values_should_be_ints};

        true ->
            Filter#fuse8{elements = sets:add_element(Element, Elements)}
    end.

%%-----------------------------------------------------------------------------
%% @doc Initializes filter internally. Equivalent to calling `fuse8:new'.
%% Elements are deduplicated at this point, so this function should only fail
%% if an already intiialized filter is passed to it.
%%
%% If more than 100K elements have been added, then the dirty version of the 
%% NIF is called. This is based around some simple benchmarking, and 
%% 100K elements initialized in under 1ms.
%% @end
%%-----------------------------------------------------------------------------
finalize(#fuse8{reference = Reference}) when Reference /= undefined ->
    {error, already_initialized_filter};

finalize(#fuse8{elements = undefined}) ->
    {error, invalid_state_error};

finalize(#fuse8{elements = Elements} = Filter) ->

    List = sets:to_list(Elements),
    FilterFun = case over_100k(List) of
        true -> fun efuse_filter:fuse8_initialize_nif_dirty/1;
        false -> fun efuse_filter:fuse8_initialize_nif/1
    end,
    Filter#fuse8{
        reference = FilterFun(List),
        elements = undefined
    }.


%%-----------------------------------------------------------------------------
%% @doc Serialize the filter to a binary
%%
%% Returns `binary()'.
%% @end
%%-----------------------------------------------------------------------------
to_bin(#fuse8{reference = undefined}) ->
    {error, uninitialized_filter};

to_bin(#fuse8{reference = Reference}) ->
    efuse_filter:fuse8_to_bin_nif(Reference).


%%-----------------------------------------------------------------------------
%% @doc Deserialize the filter from a previous `fuse8_to_bin' call. This
%% will defines the filter to use the default hashing method.
%%
%% Returns `fuse8:fuse8'.
%% @end
%%-----------------------------------------------------------------------------
from_bin(<<Binary/binary>>) ->
    #fuse8{
        reference = efuse_filter:fuse8_from_bin_nif(Binary),
        hashing_method = default}.


%%-----------------------------------------------------------------------------
%% @doc Deserialize the filter from a previous `fuse8_to_bin' call. This
%% will defines the filter to use custom hashing.
%%
%% Returns `fuse8:fuse8'.
%% @end
%%-----------------------------------------------------------------------------
from_bin(<<Binary/binary>>, none) ->
    #fuse8{
        reference = efuse_filter:fuse8_from_bin_nif(Binary),
        hashing_method = none};

from_bin(_Binary, _) ->
    {error, invalid_hash_method}.


-spec over_100k(List::[term()]) -> boolean().

over_100k(List) ->
    over_100k(List, 0).


-spec over_100k(List::[term()], Count::non_neg_integer()) -> boolean().

over_100k(_List, 10_001) -> true;
over_100k([], Count) when Count < 100_001 -> false;
over_100k([_|L], Count) -> over_100k(L, Count + 1).