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, false_positive_rate/1, hash_fn_count/1, new/3, insert/2, might_contain/2, reset/1, estimate_cardinality/1]).
-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"
).

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

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

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

-file("src/gauzy/bloom_filter.gleam", 53).
?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 pairwise 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((JIR) -> integer()), fun((JIR) -> integer())) -> {ok,
        hash_function_pair(JIR)} |
    {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", 151).
?DOC(
    " Returns the size of the `BloomFilter`'s underlying bit array.\n"
    "\n"
    " * `filter`: The `BloomFilter` from which to get the size\n"
).
-spec bit_size(bloom_filter(any())) -> integer().
bit_size(Filter) ->
    erlang:element(3, Filter).

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

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

-file("src/gauzy/bloom_filter.gleam", 204).
?DOC(
    " Calculates the optimal size in bits of a Bloom filter.\n"
    " Used in filter construction.\n"
    "\n"
    " * `capacity`: The number of bits that constitute the filter\n"
    " * `target_err_rate`: The Bloom filter's acceptable false positive rate\n"
).
-spec optimal_bit_size(integer(), float()) -> integer().
optimal_bit_size(Capacity, Target_err_rate) ->
    _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_bit_size"/utf8>>,
                        line => 206})
    end,
    _assert_subject@1 = gleam@float:power(Ln_2, 2.0),
    {ok, Ln_2_squared} = case _assert_subject@1 of
        {ok, _} -> _assert_subject@1;
        _assert_fail@1 ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        value => _assert_fail@1,
                        module => <<"gauzy/bloom_filter"/utf8>>,
                        function => <<"optimal_bit_size"/utf8>>,
                        line => 208})
    end,
    _assert_subject@2 = gleam@float:logarithm(Target_err_rate),
    {ok, Ln_target_err_rate} = case _assert_subject@2 of
        {ok, _} -> _assert_subject@2;
        _assert_fail@2 ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        value => _assert_fail@2,
                        module => <<"gauzy/bloom_filter"/utf8>>,
                        function => <<"optimal_bit_size"/utf8>>,
                        line => 210})
    end,
    _pipe = case Ln_2_squared of
        +0.0 -> +0.0;
        -0.0 -> -0.0;
        Gleam@denominator -> -1.0 * (erlang:float(Capacity) * Ln_target_err_rate)
        / Gleam@denominator
    end,
    _pipe@1 = math:ceil(_pipe),
    erlang:round(_pipe@1).

-file("src/gauzy/bloom_filter.gleam", 223).
?DOC(
    " * `capacity`: The number of elements that the filter shall be able to hold\n"
    " Calculates the optimal number of hash functions for a Bloom filter.\n"
    " Used in filter construction.\n"
    "\n"
    " * `bit_size`: 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(integer(), integer()) -> integer().
optimal_hash_fn_count(Bit_size, 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 => 225})
    end,
    _pipe = (case erlang:float(Capacity) of
        +0.0 -> +0.0;
        -0.0 -> -0.0;
        Gleam@denominator -> erlang:float(Bit_size) / Gleam@denominator
    end) * Ln_2,
    erlang:round(_pipe).

-file("src/gauzy/bloom_filter.gleam", 237).
?DOC(
    " Calculates the actual false positive rate of a `Bloomfilter`.\n"
    " Used in filter construction.\n"
    "\n"
    " * `bit_size`: 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 actual_false_positive_rate(integer(), integer(), integer()) -> float().
actual_false_positive_rate(Bit_size, Capacity, Hash_fn_count) ->
    _assert_subject = gleam@float:power(
        1.0 - math:exp(case (erlang:float(Bit_size)) of
                +0.0 -> +0.0;
                -0.0 -> -0.0;
                Gleam@denominator -> -1.0 * (erlang:float(Hash_fn_count) * erlang:float(
                    Capacity
                ))
                / Gleam@denominator
            end),
        erlang:float(Hash_fn_count)
    ),
    {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 => <<"actual_false_positive_rate"/utf8>>,
                        line => 245})
    end,
    False_positive_rate.

-file("src/gauzy/bloom_filter.gleam", 264).
?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(JJQ), JJQ) -> list(integer()).
get_bit_indices(Filter, Item) ->
    {hash_function_pair, Hash_fn_1, Hash_fn_2} = erlang:element(6, Filter),
    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, erlang:element(4, Filter) - 1),
    gleam@list:map(
        _pipe@2,
        fun(I) ->
            (I * erlang:element(7, Filter)) + (case erlang:element(7, Filter) of
                0 -> 0;
                Gleam@denominator -> (Hash_1@2 + (I * Hash_2@2)) rem Gleam@denominator
            end)
        end
    ).

-file("src/gauzy/bloom_filter.gleam", 83).
?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(JIT)) -> {ok,
        bloom_filter(JIT)} |
    {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() ->
                    Optimal_bit_size = optimal_bit_size(
                        Capacity,
                        Target_error_rate
                    ),
                    Hash_fn_count = optimal_hash_fn_count(
                        Optimal_bit_size,
                        Capacity
                    ),
                    Bit_size = case case Hash_fn_count of
                        0 -> 0;
                        Gleam@denominator -> Optimal_bit_size rem Gleam@denominator
                    end of
                        0 ->
                            Optimal_bit_size;

                        _ ->
                            Optimal_bit_size + (Hash_fn_count - (case Hash_fn_count of
                                0 -> 0;
                                Gleam@denominator@1 -> Optimal_bit_size rem Gleam@denominator@1
                            end))
                    end,
                    False_positive_rate = actual_false_positive_rate(
                        Bit_size,
                        Capacity,
                        Hash_fn_count
                    ),
                    Chunk_size = case Hash_fn_count of
                        0 -> 0;
                        Gleam@denominator@2 -> Bit_size div Gleam@denominator@2
                    end,
                    Word_chunk_count = (case 52 of
                        0 -> 0;
                        Gleam@denominator@3 -> Bit_size div Gleam@denominator@3
                    end) + 1,
                    {ok,
                        {bloom_filter,
                            iv:repeat(0, Word_chunk_count),
                            Bit_size,
                            Hash_fn_count,
                            False_positive_rate,
                            Hash_function_pair,
                            Chunk_size}}
                end
            )
        end
    ).

-file("src/gauzy/bloom_filter.gleam", 119).
?DOC(
    " Inserts an item into the `BloomFilter`.\n"
    "\n"
    " * `filter`: The `BloomFilter` to insert into.\n"
    " * `item`: The item to insert.\n"
).
-spec insert(bloom_filter(JIY), JIY) -> bloom_filter(JIY).
insert(Filter, Item) ->
    Indices = get_bit_indices(Filter, Item),
    Array@1 = gleam@list:fold(
        Indices,
        erlang:element(2, Filter),
        fun(Array, Idx) ->
            Word_idx = case 52 of
                0 -> 0;
                Gleam@denominator -> Idx div Gleam@denominator
            end,
            Mask = erlang:'bsl'(1, (case 52 of
                    0 -> 0;
                    Gleam@denominator@1 -> Idx rem Gleam@denominator@1
                end)),
            iv:try_update(
                Array,
                Word_idx,
                fun(Word) -> erlang:'bor'(Word, Mask) end
            )
        end
    ),
    _record = Filter,
    {bloom_filter,
        Array@1,
        erlang:element(3, _record),
        erlang:element(4, _record),
        erlang:element(5, _record),
        erlang:element(6, _record),
        erlang:element(7, _record)}.

-file("src/gauzy/bloom_filter.gleam", 136).
?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(JJB), JJB) -> boolean().
might_contain(Filter, Item) ->
    _pipe = get_bit_indices(Filter, Item),
    gleam@list:all(
        _pipe,
        fun(Idx) ->
            Word_idx = case 52 of
                0 -> 0;
                Gleam@denominator -> Idx div Gleam@denominator
            end,
            Word = iv:get_or_default(erlang:element(2, Filter), Word_idx, 0),
            Mask = erlang:'bsl'(1, case 52 of
                    0 -> 0;
                    Gleam@denominator@1 -> Idx rem Gleam@denominator@1
                end),
            erlang:'band'(Word, Mask) =:= Mask
        end
    ).

-file("src/gauzy/bloom_filter.gleam", 195).
?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(JJL)) -> bloom_filter(JJL).
reset(Filter) ->
    _record = Filter,
    {bloom_filter, iv:repeat(0, (case 52 of
                0 -> 0;
                Gleam@denominator -> erlang:element(3, Filter) div Gleam@denominator
            end) + 1), erlang:element(3, _record), erlang:element(4, _record), erlang:element(
            5,
            _record
        ), erlang:element(6, _record), erlang:element(7, _record)}.

-file("src/gauzy/bloom_filter.gleam", 286).
?DOC(
    " Counts the number of set bits (population count) in an integer.\n"
    " Used by `estimate_cardinality`.\n"
    "\n"
    " * `word`: The integer (representing a word from the bit array) for which to count set bits.\n"
).
-spec count_set_bits(integer()) -> integer().
count_set_bits(Word) ->
    gleam@list:fold(
        gleam@list:range(0, 52 - 1),
        0,
        fun(Acc, I) ->
            Mask = erlang:'bsl'(1, I),
            case erlang:'band'(Word, Mask) =:= Mask of
                true ->
                    Acc + 1;

                false ->
                    Acc
            end
        end
    ).

-file("src/gauzy/bloom_filter.gleam", 173).
?DOC(
    " Returns an _approximation_ of unique items inserted into the `BloomFilter`.\n"
    " This can differ substantially from reality, especially in smaller filters.\n"
    "\n"
    " * `filter`: The `BloomFilter` for which to estimate\n"
).
-spec estimate_cardinality(bloom_filter(any())) -> integer().
estimate_cardinality(Filter) ->
    Set_bits = iv:fold(
        erlang:element(2, Filter),
        0,
        fun(Total_set_bits, Word) -> Total_set_bits + count_set_bits(Word) end
    ),
    _assert_subject = gleam@float:logarithm(
        1.0 - (case erlang:float(erlang:element(3, Filter)) of
            +0.0 -> +0.0;
            -0.0 -> -0.0;
            Gleam@denominator -> erlang:float(Set_bits) / Gleam@denominator
        end)
    ),
    {ok, Partial_calc} = 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 => <<"estimate_cardinality"/utf8>>,
                        line => 180})
    end,
    _pipe = (case erlang:float(erlang:element(4, Filter)) of
        +0.0 -> +0.0;
        -0.0 -> -0.0;
        Gleam@denominator@1 -> -1.0 * erlang:float(erlang:element(3, Filter)) / Gleam@denominator@1
    end) * Partial_calc,
    erlang:round(_pipe).