-module(textmetrics@lcs).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/textmetrics/lcs.gleam").
-export([length/2, sequence/2]).
-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(
" Longest Common Subsequence helpers.\n"
"\n"
" Generic over any equality-comparable list type (`List(t)`); pre-split\n"
" strings via `gleam/string.to_graphemes` for grapheme-level results.\n"
" This module performs no Unicode normalization.\n"
).
-file("src/textmetrics/lcs.gleam", 49).
-spec lcs_length_inner(
ERP,
list(ERP),
integer(),
list(integer()),
integer(),
list(integer())
) -> list(integer()).
lcs_length_inner(Ai, Bs, Prev_diag, Prev_rest, Curr_left, Acc) ->
case {Bs, Prev_rest} of
{[], _} ->
lists:reverse(Acc);
{_, []} ->
lists:reverse(Acc);
{[Bj | Bs_rest], [Prev_above | Prev_more]} ->
Curr_j = case Ai =:= Bj of
true ->
Prev_diag + 1;
false ->
gleam@int:max(Prev_above, Curr_left)
end,
lcs_length_inner(
Ai,
Bs_rest,
Prev_above,
Prev_more,
Curr_j,
[Curr_j | Acc]
)
end.
-file("src/textmetrics/lcs.gleam", 32).
-spec lcs_length_outer(list(ERL), list(ERL), list(integer())) -> integer().
lcs_length_outer(Remaining_a, Bs, Prev) ->
case Remaining_a of
[] ->
case gleam@list:last(Prev) of
{ok, V} ->
V;
{error, _} ->
0
end;
[Ai | Rest] ->
Curr = case Prev of
[_ | P_rest] ->
lcs_length_inner(Ai, Bs, 0, P_rest, 0, [0]);
[] ->
[0]
end,
lcs_length_outer(Rest, Bs, Curr)
end.
-file("src/textmetrics/lcs.gleam", 20).
?DOC(
" Length of a longest common subsequence of `a` and `b`.\n"
"\n"
" Time `O(m·n)`, space `O(m + n)`. Returns `0` when either input is\n"
" empty.\n"
"\n"
" Note: this name shadows `gleam/list.length` if both are imported\n"
" unqualified (`import textmetrics/lcs.{length}`). Prefer the\n"
" qualified `lcs.length(...)` form to avoid the conflict.\n"
).
-spec length(list(ERI), list(ERI)) -> integer().
length(A, B) ->
N = erlang:length(B),
case {A, B} of
{[], _} ->
0;
{_, []} ->
0;
{_, _} ->
Initial_prev = gleam@list:repeat(0, N + 1),
lcs_length_outer(A, B, Initial_prev)
end.
-file("src/textmetrics/lcs.gleam", 122).
-spec build_lcs_row(
gleam@dict:dict(integer(), ESO),
gleam@dict:dict(integer(), ESO),
integer(),
integer(),
integer(),
gleam@dict:dict({integer(), integer()}, integer())
) -> gleam@dict:dict({integer(), integer()}, integer()).
build_lcs_row(A_arr, B_arr, N, I, J, D) ->
case J > N of
true ->
D;
false ->
New_d = case {gleam_stdlib:map_get(A_arr, I - 1),
gleam_stdlib:map_get(B_arr, J - 1)} of
{{ok, Ai}, {ok, Bj}} ->
Val = case Ai =:= Bj of
true ->
gleam@result:unwrap(
gleam_stdlib:map_get(D, {I - 1, J - 1}),
0
)
+ 1;
false ->
gleam@int:max(
gleam@result:unwrap(
gleam_stdlib:map_get(D, {I - 1, J}),
0
),
gleam@result:unwrap(
gleam_stdlib:map_get(D, {I, J - 1}),
0
)
)
end,
gleam@dict:insert(D, {I, J}, Val);
{_, _} ->
D
end,
build_lcs_row(A_arr, B_arr, N, I, J + 1, New_d)
end.
-file("src/textmetrics/lcs.gleam", 105).
-spec build_lcs_loop(
gleam@dict:dict(integer(), ESF),
gleam@dict:dict(integer(), ESF),
integer(),
integer(),
integer(),
gleam@dict:dict({integer(), integer()}, integer())
) -> gleam@dict:dict({integer(), integer()}, integer()).
build_lcs_loop(A_arr, B_arr, M, N, I, D) ->
case I > M of
true ->
D;
false ->
New_d = build_lcs_row(A_arr, B_arr, N, I, 1, D),
build_lcs_loop(A_arr, B_arr, M, N, I + 1, New_d)
end.
-file("src/textmetrics/lcs.gleam", 96).
-spec build_lcs_matrix(
gleam@dict:dict(integer(), ERY),
gleam@dict:dict(integer(), ERY),
integer(),
integer()
) -> gleam@dict:dict({integer(), integer()}, integer()).
build_lcs_matrix(A_arr, B_arr, M, N) ->
build_lcs_loop(A_arr, B_arr, M, N, 1, maps:new()).
-file("src/textmetrics/lcs.gleam", 152).
-spec backtrack(
gleam@dict:dict(integer(), ESX),
gleam@dict:dict(integer(), ESX),
gleam@dict:dict({integer(), integer()}, integer()),
integer(),
integer(),
list(ESX)
) -> list(ESX).
backtrack(A_arr, B_arr, Matrix, I, J, Acc) ->
case (I =:= 0) orelse (J =:= 0) of
true ->
Acc;
false ->
case {gleam_stdlib:map_get(A_arr, I - 1),
gleam_stdlib:map_get(B_arr, J - 1)} of
{{ok, Ai}, {ok, Bj}} ->
case Ai =:= Bj of
true ->
backtrack(
A_arr,
B_arr,
Matrix,
I - 1,
J - 1,
[Ai | Acc]
);
false ->
Up = gleam@result:unwrap(
gleam_stdlib:map_get(Matrix, {I - 1, J}),
0
),
Left = gleam@result:unwrap(
gleam_stdlib:map_get(Matrix, {I, J - 1}),
0
),
case Up >= Left of
true ->
backtrack(
A_arr,
B_arr,
Matrix,
I - 1,
J,
Acc
);
false ->
backtrack(
A_arr,
B_arr,
Matrix,
I,
J - 1,
Acc
)
end
end;
{_, _} ->
Acc
end
end.
-file("src/textmetrics/lcs.gleam", 185).
-spec list_to_dict_loop(list(ETK), integer(), gleam@dict:dict(integer(), ETK)) -> gleam@dict:dict(integer(), ETK).
list_to_dict_loop(Items, I, Acc) ->
case Items of
[] ->
Acc;
[X | Rest] ->
list_to_dict_loop(Rest, I + 1, gleam@dict:insert(Acc, I, X))
end.
-file("src/textmetrics/lcs.gleam", 181).
-spec list_to_dict(list(ETG)) -> gleam@dict:dict(integer(), ETG).
list_to_dict(Items) ->
list_to_dict_loop(Items, 0, maps:new()).
-file("src/textmetrics/lcs.gleam", 82).
?DOC(
" One longest common subsequence of `a` and `b`.\n"
"\n"
" When multiple equally-long subsequences exist, this implementation\n"
" returns the one preferring upward backtracking on ties — callers\n"
" should treat the choice as implementation-defined and only rely on\n"
" `length(sequence(a, b)) == length(a, b)`.\n"
"\n"
" Time `O(m·n)`, space `O(m·n)` (full DP matrix retained for\n"
" backtracking).\n"
).
-spec sequence(list(ERU), list(ERU)) -> list(ERU).
sequence(A, B) ->
M = erlang:length(A),
N = erlang:length(B),
case (M =:= 0) orelse (N =:= 0) of
true ->
[];
false ->
A_arr = list_to_dict(A),
B_arr = list_to_dict(B),
Matrix = build_lcs_matrix(A_arr, B_arr, M, N),
backtrack(A_arr, B_arr, Matrix, M, N, [])
end.
