gauzy

-module(gauzy@bloom_filter).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch]).

-export([new_hash_fn_pair/2, bit_size/1, error_rate/1, hash_fn_count/1, reset/1, try_insert/2, might_contain/2, new/3]).
-export_type([bloom_filter_error/0, hash_function_pair/1, bloom_filter/1]).

-if(?OTP_RELEASE >= 27).
-define(MODULEDOC(Str), -moduledoc(Str)).
-define(DOC(Str), -doc(Str)).
-else.
-define(MODULEDOC(Str), -compile([])).
-define(DOC(Str), -compile([])).
-endif.

?MODULEDOC(
    " This module provides an implementation of a Bloom filter, a space-efficient\n"
    " probabilistic data structure that is used to test whether an element is a\n"
    " member of a set. False positive matches are possible, but false negatives\n"
    " are not – in other words, a query returns either \"possibly in set\" or\n"
    " \"definitely not in set\".\n"
    "\n"
    " Bloom filters are useful in situations where the size of the set would\n"
    " require an impractically large amount of memory to store, or where the\n"
    " cost of a false positive is acceptable compared to the cost of a more\n"
    " precise data structure.\n"
    "\n"
    " The module provides functions for creating, inserting into, querying, and\n"
    " resetting Bloom filters.\n"
    " Optimization step size for finding optimal Bloom filter parameters.\n"
).

-type bloom_filter_error() :: equal_hash_functions |
    insertion_error |
    invalid_capacity |
    invalid_target_error_rate.

-opaque hash_function_pair(JMK) :: {hash_function_pair,
        fun((JMK) -> integer()),
        fun((JMK) -> integer())}.

-opaque bloom_filter(JML) :: {bloom_filter,
        iv:array(integer()),
        integer(),
        float(),
        integer(),
        hash_function_pair(JML)}.

-file("src/gauzy/bloom_filter.gleam", 55).
?DOC(
    " Creates a new pair of hash functions for the `BloomFilter`.\n"
    "\n"
    " The hash functions must not be equal!  For optimal performance,\n"
    " the hash functions should be random, uniform, and independent.\n"
    "\n"
    " * `first_hash_function`: The first hash function.\n"
    " * `second_hash_function`: The second hash function.\n"
).
-spec new_hash_fn_pair(fun((JMM) -> integer()), fun((JMM) -> integer())) -> {ok,
        hash_function_pair(JMM)} |
    {error, bloom_filter_error()}.
new_hash_fn_pair(Hash_fn_1, Hash_fn_2) ->
    case Hash_fn_1 =:= Hash_fn_2 of
        false ->
            {ok, {hash_function_pair, Hash_fn_1, Hash_fn_2}};

        true ->
            {error, equal_hash_functions}
    end.

-file("src/gauzy/bloom_filter.gleam", 142).
?DOC(
    " Returns the size of the `BloomFilter`'s underlying bit array.\n"
    "\n"
    " * `filter`: The `BloomFilter` to get the size from\n"
).
-spec bit_size(bloom_filter(any())) -> integer().
bit_size(Filter) ->
    erlang:element(3, Filter).

-file("src/gauzy/bloom_filter.gleam", 149).
?DOC(
    " Returns the `BloomFilter`'s actual false positive rate\n"
    "\n"
    " * `filter`: The `BloomFilter` to get the error rate from.\n"
).
-spec error_rate(bloom_filter(any())) -> float().
error_rate(Filter) ->
    erlang:element(4, Filter).

-file("src/gauzy/bloom_filter.gleam", 156).
?DOC(
    " Returns the number of hash functions the `BloomFilter` uses.\n"
    "\n"
    " * `filter`: The `BloomFilter` to get the hash function count from\n"
).
-spec hash_fn_count(bloom_filter(any())) -> integer().
hash_fn_count(Filter) ->
    erlang:element(5, Filter).

-file("src/gauzy/bloom_filter.gleam", 163).
?DOC(
    " Returns an empty `BloomFilter` with the same characteristics as the input filter.\n"
    "\n"
    " * `filter`: The `BloomFilter` to reset\n"
).
-spec reset(bloom_filter(JNG)) -> bloom_filter(JNG).
reset(Filter) ->
    {bloom_filter, _, Bit_size, Error_rate, Hash_fn_count, Hash_function_pair} = Filter,
    {bloom_filter,
        iv:repeat(0, Bit_size),
        Bit_size,
        Error_rate,
        Hash_fn_count,
        Hash_function_pair}.

-file("src/gauzy/bloom_filter.gleam", 244).
?DOC(
    " Calculates the false positive rate of a Bloom filter with the properties of the parameters.\n"
    " Used in filter construction.\n"
    "\n"
    " * `bits`: The number of bits that constitute the filter\n"
    " * `capacity`: The number of elements that the filter shall be able to hold\n"
    " * `hash_fns_count`: The number of hash functions the filter uses\n"
    "\n"
    " Returns an `f64` as the expected false positive rate.\n"
).
-spec false_positive_rate(float(), float(), float()) -> float().
false_positive_rate(Bits, Capacity, Hash_fn_count) ->
    _assert_subject = begin
        _pipe = 1.0 - math:exp(case (Bits - 1.0) of
                +0.0 -> +0.0;
                -0.0 -> -0.0;
                Gleam@denominator -> (-1.0 * Hash_fn_count) * (Capacity + 0.5) / Gleam@denominator
            end),
        gleam@float:power(_pipe, Hash_fn_count)
    end,
    {ok, False_positive_rate} = case _assert_subject of
        {ok, _} -> _assert_subject;
        _assert_fail ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        value => _assert_fail,
                        module => <<"gauzy/bloom_filter"/utf8>>,
                        function => <<"false_positive_rate"/utf8>>,
                        line => 245})
    end,
    False_positive_rate.

-file("src/gauzy/bloom_filter.gleam", 260).
?DOC(
    " Calculates the optimal number of hash functions for a Bloom filter.\n"
    " Used in filter construction.\n"
    "\n"
    " * `bits`: The number of bits that constitute the filter\n"
    " * `capacity`: The number of elements that the filter shall be able to hold\n"
).
-spec optimal_hash_fn_count(float(), float()) -> float().
optimal_hash_fn_count(Bits, Capacity) ->
    _assert_subject = gleam@float:logarithm(2.0),
    {ok, Ln_2} = case _assert_subject of
        {ok, _} -> _assert_subject;
        _assert_fail ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        value => _assert_fail,
                        module => <<"gauzy/bloom_filter"/utf8>>,
                        function => <<"optimal_hash_fn_count"/utf8>>,
                        line => 261})
    end,
    (case Capacity of
        +0.0 -> +0.0;
        -0.0 -> -0.0;
        Gleam@denominator -> Bits / Gleam@denominator
    end) * Ln_2.

-file("src/gauzy/bloom_filter.gleam", 270).
?DOC(
    " Returns a list of unique, sorted bit indices for the given `item`\n"
    " using the `BloomFilter`'s hash functions.\n"
    "\n"
    " * `bloom_filter`: The `BloomFilter` to get the bit indices from\n"
    " * `item`: The item to calculate the bit indices for\n"
).
-spec get_bit_indices(bloom_filter(JNN), JNN) -> list(integer()).
get_bit_indices(Bloom_filter, Item) ->
    {bloom_filter, _, Bit_size, _, Hash_fn_count, Hash_function_pair} = Bloom_filter,
    {hash_function_pair, Hash_fn_1, Hash_fn_2} = Hash_function_pair,
    Hash_1@2 = case Hash_fn_1(Item) of
        Hash_1 when Hash_1 < 0 ->
            _pipe = (2 * Hash_1),
            gleam@int:absolute_value(_pipe);

        Hash_1@1 ->
            Hash_1@1
    end,
    Hash_2@2 = case Hash_fn_2(Item) of
        Hash_2 when Hash_2 < 0 ->
            _pipe@1 = (2 * Hash_2),
            gleam@int:absolute_value(_pipe@1);

        Hash_2@1 ->
            Hash_2@1
    end,
    _pipe@2 = gleam@list:range(0, Hash_fn_count - 1),
    _pipe@3 = gleam@list:map(_pipe@2, fun(I) -> case Bit_size of
                0 -> 0;
                Gleam@denominator -> (Hash_1@2 + (I * Hash_2@2)) rem Gleam@denominator
            end end),
    _pipe@4 = gleam@list:unique(_pipe@3),
    gleam@list:sort(_pipe@4, fun gleam@int:compare/2).

-file("src/gauzy/bloom_filter.gleam", 112).
?DOC(
    " Tries to insert an item into the `BloomFilter`.\n"
    "\n"
    " * `filter`: The `BloomFilter` to insert into.\n"
    " * `item`: The item to insert.\n"
).
-spec try_insert(bloom_filter(JMR), JMR) -> {ok, bloom_filter(JMR)} |
    {error, bloom_filter_error()}.
try_insert(Filter, Item) ->
    Indices = get_bit_indices(Filter, Item),
    Array@1 = gleam@list:try_fold(
        Indices,
        erlang:element(2, Filter),
        fun(Array, Idx) -> iv:set(Array, Idx, 1) end
    ),
    case Array@1 of
        {ok, Array@2} ->
            {ok,
                begin
                    _record = Filter,
                    {bloom_filter,
                        Array@2,
                        erlang:element(3, _record),
                        erlang:element(4, _record),
                        erlang:element(5, _record),
                        erlang:element(6, _record)}
                end};

        {error, _} ->
            {error, insertion_error}
    end.

-file("src/gauzy/bloom_filter.gleam", 129).
?DOC(
    " Checks if the `BloomFilter` might contain the given `item`.\n"
    "\n"
    " * `filter`: The `BloomFilter` to check\n"
    " * `item`: The item to check for\n"
).
-spec might_contain(bloom_filter(JMU), JMU) -> boolean().
might_contain(Filter, Item) ->
    _pipe = get_bit_indices(Filter, Item),
    gleam@list:all(
        _pipe,
        fun(Idx) -> case iv:get(erlang:element(2, Filter), Idx) of
                {ok, 1} ->
                    true;

                _ ->
                    false
            end end
    ).

-file("src/gauzy/bloom_filter.gleam", 212).
?DOC(
    " Recursive function to *approximate* optimal Bloom filter properties.\n"
    " Evaluates filter properties for the input parameters and optimizes them if needed.\n"
    " Used in Bloom filter construction.\n"
    "\n"
    " * `capacity`: Intended elements the Bloom filter shall be able to hold\n"
    " * `num_bits`: The number of bits that constitute the filter\n"
    " * `hash_fns_count`: The number of hash functions the filter uses\n"
    " * `target_err_rate`: The Bloom filter's acceptable false positive rate\n"
).
-spec optimize_values(float(), float(), float(), float()) -> {float(),
    float(),
    float()}.
optimize_values(Capacity, Num_bits, Hash_fns_count, Target_error_rate) ->
    Error_rate = false_positive_rate(Num_bits, Capacity, Hash_fns_count),
    Is_acceptable_error_rate = Error_rate < Target_error_rate,
    case Is_acceptable_error_rate of
        false ->
            optimize_values(
                Capacity,
                math:ceil(Num_bits * 1.01),
                optimal_hash_fn_count(math:ceil(Num_bits * 1.01), Capacity),
                Target_error_rate
            );

        true ->
            {Num_bits, math:ceil(Hash_fns_count), Error_rate}
    end.

-file("src/gauzy/bloom_filter.gleam", 188).
?DOC(
    " Proxy function that relays the input to the recursive function `optimize_values`.\n"
    " Used in Bloom filter construction.\n"
    "\n"
    " * `capacity`: Intended elements the Bloom filter shall be able to hold\n"
    " * `target_err_rate`: The Bloom filter's acceptable false positive rate\n"
    "\n"
    " Returns *approximately* optimal (num_bits, hash_fn_count, error_rate).\n"
).
-spec optimize(integer(), float()) -> {integer(), integer(), float()}.
optimize(Capacity, Target_error_rate) ->
    {Num_bits, Hash_fn_count, Error_rate} = optimize_values(
        erlang:float(Capacity),
        4.0 * erlang:float(Capacity),
        2.0,
        Target_error_rate
    ),
    {begin
            _pipe = Num_bits,
            _pipe@1 = math:floor(_pipe),
            erlang:round(_pipe@1)
        end,
        begin
            _pipe@2 = Hash_fn_count,
            _pipe@3 = math:floor(_pipe@2),
            erlang:round(_pipe@3)
        end,
        Error_rate}.

-file("src/gauzy/bloom_filter.gleam", 85).
?DOC(
    " Creates a new `BloomFilter`.\n"
    "\n"
    " * `capacity`: The number of items the `BloomFilter` is expected to hold.\n"
    " * `target_error_rate`: The desired false positive rate (between 0.0 and 1.0).\n"
    " * `hash_function_pair`: The hash functions used to generate indices.\n"
).
-spec new(integer(), float(), hash_function_pair(JMO)) -> {ok,
        bloom_filter(JMO)} |
    {error, bloom_filter_error()}.
new(Capacity, Target_error_rate, Hash_function_pair) ->
    gleam@bool:guard(
        Capacity < 1,
        {error, invalid_capacity},
        fun() ->
            gleam@bool:guard(
                (Target_error_rate =< +0.0) orelse (1.0 =< Target_error_rate),
                {error, invalid_target_error_rate},
                fun() ->
                    {Bit_size, Hash_fn_count, Error_rate} = optimize(
                        Capacity,
                        Target_error_rate
                    ),
                    {ok,
                        {bloom_filter,
                            iv:repeat(0, Bit_size),
                            Bit_size,
                            Error_rate,
                            Hash_fn_count,
                            Hash_function_pair}}
                end
            )
        end
    ).