starfuzz

-module(starfuzz@distance).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/starfuzz/distance.gleam").
-export([levenshtein/2, optimal_string_alignment/2, longest_common_subsequence/2, hamming/2]).
-export_type([hamming_error/0]).

-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(
    " A module providing distance calculation metrics.\n"
    " Distance calculations compute the number of operational edits (lower values are closer)\n"
    " required to transform one string into another.\n"
).

-type hamming_error() :: different_lengths.

-file("src/starfuzz/distance.gleam", 14).
-spec min3(integer(), integer(), integer()) -> integer().
min3(X, Y, Z) ->
    Temp = case X < Y of
        true ->
            X;

        false ->
            Y
    end,
    case Temp < Z of
        true ->
            Temp;

        false ->
            Z
    end.

-file("src/starfuzz/distance.gleam", 29).
-spec do_range(integer(), integer(), list(integer())) -> list(integer()).
do_range(Start, End, Acc) ->
    case Start > End of
        true ->
            lists:reverse(Acc);

        false ->
            do_range(Start + 1, End, [Start | Acc])
    end.

-file("src/starfuzz/distance.gleam", 25).
-spec range(integer(), integer()) -> list(integer()).
range(Start, End) ->
    do_range(Start, End, []).

-file("src/starfuzz/distance.gleam", 64).
-spec compute_next_row(
    list(integer()),
    list(binary()),
    binary(),
    integer(),
    list(integer())
) -> list(integer()).
compute_next_row(Old_row, B_chars, A_char, Curr_val, Acc) ->
    case {Old_row, B_chars} of
        {[Old_head | Old_tail], [B_head | B_tail]} ->
            Old_next@1 = case gleam@list:first(Old_tail) of
                {ok, Old_next} -> Old_next;
                _assert_fail ->
                    erlang:error(#{gleam_error => let_assert,
                                message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                file => <<?FILEPATH/utf8>>,
                                module => <<"starfuzz/distance"/utf8>>,
                                function => <<"compute_next_row"/utf8>>,
                                line => 73,
                                value => _assert_fail,
                                start => 1963,
                                'end' => 2009,
                                pattern_start => 1974,
                                pattern_end => 1986})
            end,
            Cost = case A_char =:= B_head of
                true ->
                    0;

                false ->
                    1
            end,
            Next_val = min3(Curr_val + 1, Old_next@1 + 1, Old_head + Cost),
            compute_next_row(
                Old_tail,
                B_tail,
                A_char,
                Next_val,
                [Next_val | Acc]
            );

        {_, _} ->
            lists:reverse(Acc)
    end.

-file("src/starfuzz/distance.gleam", 39).
?DOC(
    " Computes the Levenshtein distance between two strings (minimum insertion, deletion, or substitution edits).\n"
    "\n"
    " Implemented using a tail-recursive row-state optimization requiring $O(m)$ auxiliary space.\n"
).
-spec levenshtein(binary(), binary()) -> integer().
levenshtein(A, B) ->
    A_chars = gleam@string:to_graphemes(A),
    B_chars = gleam@string:to_graphemes(B),
    B_len = erlang:length(B_chars),
    case erlang:length(A_chars) of
        0 ->
            B_len;

        _ ->
            case B_len of
                0 ->
                    erlang:length(A_chars);

                _ ->
                    Initial_row = range(0, B_len),
                    {_, Final_row} = gleam@list:fold(
                        A_chars,
                        {0, Initial_row},
                        fun(Acc_state, A_char) ->
                            {I, Prev_row} = Acc_state,
                            Next_row = compute_next_row(
                                Prev_row,
                                B_chars,
                                A_char,
                                I + 1,
                                [I + 1]
                            ),
                            {I + 1, Next_row}
                        end
                    ),
                    Last@1 = case gleam@list:last(Final_row) of
                        {ok, Last} -> Last;
                        _assert_fail ->
                            erlang:error(#{gleam_error => let_assert,
                                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                        file => <<?FILEPATH/utf8>>,
                                        module => <<"starfuzz/distance"/utf8>>,
                                        function => <<"levenshtein"/utf8>>,
                                        line => 56,
                                        value => _assert_fail,
                                        start => 1653,
                                        'end' => 1695,
                                        pattern_start => 1664,
                                        pattern_end => 1672})
                    end,
                    Last@1
            end
    end.

-file("src/starfuzz/distance.gleam", 133).
-spec osa_step(
    list(integer()),
    list(integer()),
    list(binary()),
    binary(),
    binary(),
    binary(),
    integer(),
    integer(),
    integer(),
    integer(),
    list(integer())
) -> list(integer()).
osa_step(
    Row_i_minus_2,
    Row_i_minus_1,
    B_chars,
    A_char,
    Prev_a_char,
    Prev_b_char,
    Curr_val,
    I,
    J,
    R2_prev,
    Acc
) ->
    case {Row_i_minus_2, Row_i_minus_1, B_chars} of
        {[R2_head | R2_tail], [R1_head | R1_tail], [B_head | B_tail]} ->
            R1_next@1 = case gleam@list:first(R1_tail) of
                {ok, R1_next} -> R1_next;
                _assert_fail ->
                    erlang:error(#{gleam_error => let_assert,
                                message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                file => <<?FILEPATH/utf8>>,
                                module => <<"starfuzz/distance"/utf8>>,
                                function => <<"osa_step"/utf8>>,
                                line => 148,
                                value => _assert_fail,
                                start => 4064,
                                'end' => 4108,
                                pattern_start => 4075,
                                pattern_end => 4086})
            end,
            Cost = case A_char =:= B_head of
                true ->
                    0;

                false ->
                    1
            end,
            Standard_val = min3(Curr_val + 1, R1_next@1 + 1, R1_head + Cost),
            Next_val = case ((((I > 0) andalso (J > 0)) andalso (A_char /= B_head))
            andalso (A_char =:= Prev_b_char))
            andalso (B_head =:= Prev_a_char) of
                true ->
                    Trans_val = R2_prev + 1,
                    case Trans_val < Standard_val of
                        true ->
                            Trans_val;

                        false ->
                            Standard_val
                    end;

                false ->
                    Standard_val
            end,
            osa_step(
                R2_tail,
                R1_tail,
                B_tail,
                A_char,
                Prev_a_char,
                B_head,
                Next_val,
                I,
                J + 1,
                R2_head,
                [Next_val | Acc]
            );

        {_, _, _} ->
            lists:reverse(Acc)
    end.

-file("src/starfuzz/distance.gleam", 93).
?DOC(
    " Computes the Optimal String Alignment (OSA / Restricted Damerau-Levenshtein) distance.\n"
    "\n"
    " OSA computes insertions, deletions, substitutions, and adjacent transpositions,\n"
    " but restricts transposition edits to prevent substrings from being edited twice.\n"
    "\n"
    " Implemented using a tail-recursive double-row carrying optimization requiring $O(m)$ auxiliary space.\n"
).
-spec optimal_string_alignment(binary(), binary()) -> integer().
optimal_string_alignment(A, B) ->
    A_chars = gleam@string:to_graphemes(A),
    B_chars = gleam@string:to_graphemes(B),
    B_len = erlang:length(B_chars),
    case erlang:length(A_chars) of
        0 ->
            B_len;

        _ ->
            case B_len of
                0 ->
                    erlang:length(A_chars);

                _ ->
                    Row_i_minus_2 = range(0, B_len),
                    Row_i_minus_1 = range(0, B_len),
                    {_, _, _, Final_row} = gleam@list:fold(
                        A_chars,
                        {0, <<""/utf8>>, Row_i_minus_2, Row_i_minus_1},
                        fun(Acc_state, A_char) ->
                            {I, Prev_a_char, R2, R1} = Acc_state,
                            Next_row = osa_step(
                                R2,
                                R1,
                                B_chars,
                                A_char,
                                Prev_a_char,
                                <<""/utf8>>,
                                I + 1,
                                I,
                                0,
                                0,
                                [I + 1]
                            ),
                            {I + 1, A_char, R1, Next_row}
                        end
                    ),
                    Last@1 = case gleam@list:last(Final_row) of
                        {ok, Last} -> Last;
                        _assert_fail ->
                            erlang:error(#{gleam_error => let_assert,
                                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                        file => <<?FILEPATH/utf8>>,
                                        module => <<"starfuzz/distance"/utf8>>,
                                        function => <<"optimal_string_alignment"/utf8>>,
                                        line => 125,
                                        value => _assert_fail,
                                        start => 3605,
                                        'end' => 3647,
                                        pattern_start => 3616,
                                        pattern_end => 3624})
                    end,
                    Last@1
            end
    end.

-file("src/starfuzz/distance.gleam", 212).
-spec lcs_step(
    list(integer()),
    list(binary()),
    binary(),
    integer(),
    list(integer())
) -> list(integer()).
lcs_step(Old_row, B_chars, A_char, Curr_val, Acc) ->
    case {Old_row, B_chars} of
        {[Old_head | Old_tail], [B_head | B_tail]} ->
            Old_next@1 = case gleam@list:first(Old_tail) of
                {ok, Old_next} -> Old_next;
                _assert_fail ->
                    erlang:error(#{gleam_error => let_assert,
                                message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                file => <<?FILEPATH/utf8>>,
                                module => <<"starfuzz/distance"/utf8>>,
                                function => <<"lcs_step"/utf8>>,
                                line => 221,
                                value => _assert_fail,
                                start => 5867,
                                'end' => 5913,
                                pattern_start => 5878,
                                pattern_end => 5890})
            end,
            Next_val = case A_char =:= B_head of
                true ->
                    Old_head + 1;

                false ->
                    case Old_next@1 > Curr_val of
                        true ->
                            Old_next@1;

                        false ->
                            Curr_val
                    end
            end,
            lcs_step(Old_tail, B_tail, A_char, Next_val, [Next_val | Acc]);

        {_, _} ->
            lists:reverse(Acc)
    end.

-file("src/starfuzz/distance.gleam", 189).
?DOC(
    " Computes the Longest Common Subsequence length (LCS) between two strings.\n"
    "\n"
    " Implemented using a tail-recursive row-state optimization requiring $O(m)$ auxiliary space.\n"
).
-spec longest_common_subsequence(binary(), binary()) -> integer().
longest_common_subsequence(A, B) ->
    A_chars = gleam@string:to_graphemes(A),
    B_chars = gleam@string:to_graphemes(B),
    B_len = erlang:length(B_chars),
    case erlang:length(A_chars) of
        0 ->
            0;

        _ ->
            case B_len of
                0 ->
                    0;

                _ ->
                    Initial_row = gleam@list:repeat(0, B_len + 1),
                    Final_row = gleam@list:fold(
                        A_chars,
                        Initial_row,
                        fun(Prev_row, A_char) ->
                            lcs_step(Prev_row, B_chars, A_char, 0, [0])
                        end
                    ),
                    Last@1 = case gleam@list:last(Final_row) of
                        {ok, Last} -> Last;
                        _assert_fail ->
                            erlang:error(#{gleam_error => let_assert,
                                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                        file => <<?FILEPATH/utf8>>,
                                        module => <<"starfuzz/distance"/utf8>>,
                                        function => <<"longest_common_subsequence"/utf8>>,
                                        line => 204,
                                        value => _assert_fail,
                                        start => 5565,
                                        'end' => 5607,
                                        pattern_start => 5576,
                                        pattern_end => 5584})
                    end,
                    Last@1
            end
    end.

-file("src/starfuzz/distance.gleam", 241).
?DOC(
    " Computes the Hamming distance between two strings of equal length.\n"
    " Returns an error if lengths differ.\n"
).
-spec hamming(binary(), binary()) -> {ok, integer()} | {error, hamming_error()}.
hamming(A, B) ->
    A_chars = gleam@string:to_graphemes(A),
    B_chars = gleam@string:to_graphemes(B),
    case erlang:length(A_chars) =:= erlang:length(B_chars) of
        false ->
            {error, different_lengths};

        true ->
            Diffs = begin
                _pipe = gleam@list:zip(A_chars, B_chars),
                _pipe@1 = gleam@list:filter(
                    _pipe,
                    fun(P) -> erlang:element(1, P) /= erlang:element(2, P) end
                ),
                erlang:length(_pipe@1)
            end,
            {ok, Diffs}
    end.