-module(yog@pathfinding@bellman_ford).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/pathfinding/bellman_ford.gleam").
-export([relaxation_passes/7, has_negative_cycle/5, reconstruct_path/4, bellman_ford/6, implicit_bellman_ford/6, implicit_bellman_ford_by/7, bellman_ford_int/3, bellman_ford_float/3]).
-export_type([bellman_ford_result/1, implicit_bellman_ford_result/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(" Bellman-Ford algorithm for finding shortest paths in graphs with negative edge weights.\n").

-type bellman_ford_result(QWE) :: {shortest_path,
        yog@pathfinding@utils:path(QWE)} |
    negative_cycle |
    no_path.

-type implicit_bellman_ford_result(QWF) :: {found_goal, QWF} |
    detected_negative_cycle |
    no_goal.

-file("src/yog/pathfinding/bellman_ford.gleam", 84).
-spec relaxation_passes(
    yog@model:graph(any(), QWM),
    list(integer()),
    gleam@dict:dict(integer(), QWM),
    gleam@dict:dict(integer(), integer()),
    integer(),
    fun((QWM, QWM) -> QWM),
    fun((QWM, QWM) -> gleam@order:order())
) -> {gleam@dict:dict(integer(), QWM), gleam@dict:dict(integer(), integer())}.
relaxation_passes(
    Graph,
    Nodes,
    Distances,
    Predecessors,
    Remaining,
    Add,
    Compare
) ->
    case Remaining =< 0 of
        true ->
            {Distances, Predecessors};

        false ->
            {New_distances, New_predecessors} = gleam@list:fold(
                Nodes,
                {Distances, Predecessors},
                fun(Acc, U) ->
                    {Dists, Preds} = Acc,
                    case gleam_stdlib:map_get(Dists, U) of
                        {error, nil} ->
                            Acc;

                        {ok, U_dist} ->
                            Neighbors = yog@model:successors(Graph, U),
                            gleam@list:fold(
                                Neighbors,
                                {Dists, Preds},
                                fun(Inner_acc, Edge) ->
                                    {V, Weight} = Edge,
                                    {Curr_dists, Curr_preds} = Inner_acc,
                                    New_dist = Add(U_dist, Weight),
                                    case gleam_stdlib:map_get(Curr_dists, V) of
                                        {error, nil} ->
                                            {gleam@dict:insert(
                                                    Curr_dists,
                                                    V,
                                                    New_dist
                                                ),
                                                gleam@dict:insert(
                                                    Curr_preds,
                                                    V,
                                                    U
                                                )};

                                        {ok, V_dist} ->
                                            case Compare(New_dist, V_dist) of
                                                lt ->
                                                    {gleam@dict:insert(
                                                            Curr_dists,
                                                            V,
                                                            New_dist
                                                        ),
                                                        gleam@dict:insert(
                                                            Curr_preds,
                                                            V,
                                                            U
                                                        )};

                                                _ ->
                                                    Inner_acc
                                            end
                                    end
                                end
                            )
                    end
                end
            ),
            relaxation_passes(
                Graph,
                Nodes,
                New_distances,
                New_predecessors,
                Remaining - 1,
                Add,
                Compare
            )
    end.

-file("src/yog/pathfinding/bellman_ford.gleam", 142).
-spec has_negative_cycle(
    yog@model:graph(any(), QWZ),
    list(integer()),
    gleam@dict:dict(integer(), QWZ),
    fun((QWZ, QWZ) -> QWZ),
    fun((QWZ, QWZ) -> gleam@order:order())
) -> boolean().
has_negative_cycle(Graph, Nodes, Distances, Add, Compare) ->
    gleam@list:any(Nodes, fun(U) -> case gleam_stdlib:map_get(Distances, U) of
                {error, nil} ->
                    false;

                {ok, U_dist} ->
                    _pipe = yog@model:successors(Graph, U),
                    gleam@list:any(
                        _pipe,
                        fun(Edge) ->
                            {V, Weight} = Edge,
                            New_dist = Add(U_dist, Weight),
                            case gleam_stdlib:map_get(Distances, V) of
                                {error, nil} ->
                                    false;

                                {ok, V_dist} ->
                                    case Compare(New_dist, V_dist) of
                                        lt ->
                                            true;

                                        _ ->
                                            false
                                    end
                            end
                        end
                    )
            end end).

-file("src/yog/pathfinding/bellman_ford.gleam", 172).
-spec reconstruct_path(
    gleam@dict:dict(integer(), integer()),
    integer(),
    integer(),
    list(integer())
) -> {ok, list(integer())} | {error, nil}.
reconstruct_path(Predecessors, Start, Current, Acc) ->
    case Current =:= Start of
        true ->
            {ok, Acc};

        false ->
            case gleam_stdlib:map_get(Predecessors, Current) of
                {error, nil} ->
                    {error, nil};

                {ok, Pred} ->
                    reconstruct_path(Predecessors, Start, Pred, [Pred | Acc])
            end
    end.

-file("src/yog/pathfinding/bellman_ford.gleam", 43).
?DOC(
    " Finds shortest path with support for negative edge weights using Bellman-Ford.\n"
    "\n"
    " **Time Complexity:** O(VE)\n"
    "\n"
    " ## Returns\n"
    "\n"
    " - `ShortestPath(path)`: If a valid shortest path exists\n"
    " - `NegativeCycle`: If a negative cycle is reachable from the start node\n"
    " - `NoPath`: If no path exists from start to goal\n"
).
-spec bellman_ford(
    yog@model:graph(any(), QWH),
    integer(),
    integer(),
    QWH,
    fun((QWH, QWH) -> QWH),
    fun((QWH, QWH) -> gleam@order:order())
) -> bellman_ford_result(QWH).
bellman_ford(Graph, Start, Goal, Zero, Add, Compare) ->
    All_nodes = yog@model:all_nodes(Graph),
    Initial_distances = maps:from_list([{Start, Zero}]),
    Initial_predecessors = maps:new(),
    Node_count = erlang:length(All_nodes),
    {Distances, Predecessors} = relaxation_passes(
        Graph,
        All_nodes,
        Initial_distances,
        Initial_predecessors,
        Node_count - 1,
        Add,
        Compare
    ),
    case has_negative_cycle(Graph, All_nodes, Distances, Add, Compare) of
        true ->
            negative_cycle;

        false ->
            case gleam_stdlib:map_get(Distances, Goal) of
                {error, nil} ->
                    no_path;

                {ok, Dist} ->
                    case reconstruct_path(Predecessors, Start, Goal, [Goal]) of
                        {ok, Path} ->
                            {shortest_path, {path, Path, Dist}};

                        {error, nil} ->
                            no_path
                    end
            end
    end.

-file("src/yog/pathfinding/bellman_ford.gleam", 219).
-spec do_implicit_bellman_ford(
    yog@internal@queue:queue(QXP),
    gleam@dict:dict(QXP, QXR),
    gleam@dict:dict(QXP, integer()),
    gleam@set:set(QXP),
    fun((QXP) -> list({QXP, QXR})),
    fun((QXP) -> boolean()),
    QXR,
    fun((QXR, QXR) -> QXR),
    fun((QXR, QXR) -> gleam@order:order())
) -> implicit_bellman_ford_result(QXR).
do_implicit_bellman_ford(
    Q,
    Distances,
    Relax_counts,
    In_queue,
    Successors,
    Is_goal,
    Zero,
    Add,
    Compare
) ->
    case yog@internal@queue:pop(Q) of
        {error, nil} ->
            _pipe = Distances,
            _pipe@1 = maps:to_list(_pipe),
            _pipe@2 = gleam@list:filter(
                _pipe@1,
                fun(Entry) -> Is_goal(erlang:element(1, Entry)) end
            ),
            _pipe@3 = gleam@list:sort(
                _pipe@2,
                fun(A, B) ->
                    Compare(erlang:element(2, A), erlang:element(2, B))
                end
            ),
            _pipe@4 = gleam@list:first(_pipe@3),
            _pipe@5 = gleam@result:map(
                _pipe@4,
                fun(Entry@1) -> {found_goal, erlang:element(2, Entry@1)} end
            ),
            gleam@result:unwrap(_pipe@5, no_goal);

        {ok, {Current, Rest_queue}} ->
            New_in_queue = gleam@set:delete(In_queue, Current),
            Current_dist = begin
                _pipe@6 = gleam_stdlib:map_get(Distances, Current),
                gleam@result:unwrap(_pipe@6, Zero)
            end,
            {New_distances, New_counts, New_queue, New_in_q} = begin
                _pipe@7 = Successors(Current),
                gleam@list:fold(
                    _pipe@7,
                    {Distances, Relax_counts, Rest_queue, New_in_queue},
                    fun(Acc, Neighbor) ->
                        {Dists, Counts, Q_acc, In_q_acc} = Acc,
                        {Next_state, Edge_cost} = Neighbor,
                        New_dist = Add(Current_dist, Edge_cost),
                        case gleam_stdlib:map_get(Dists, Next_state) of
                            {ok, Prev_dist} ->
                                case Compare(New_dist, Prev_dist) of
                                    lt ->
                                        Updated_dists = gleam@dict:insert(
                                            Dists,
                                            Next_state,
                                            New_dist
                                        ),
                                        Relax_count = begin
                                            _pipe@8 = gleam_stdlib:map_get(
                                                Counts,
                                                Next_state
                                            ),
                                            gleam@result:unwrap(_pipe@8, 0)
                                        end,
                                        New_count = Relax_count + 1,
                                        Updated_counts = gleam@dict:insert(
                                            Counts,
                                            Next_state,
                                            New_count
                                        ),
                                        case New_count > maps:size(Dists) of
                                            true ->
                                                {Updated_dists,
                                                    Updated_counts,
                                                    Q_acc,
                                                    In_q_acc};

                                            false ->
                                                case gleam@set:contains(
                                                    In_q_acc,
                                                    Next_state
                                                ) of
                                                    true ->
                                                        {Updated_dists,
                                                            Updated_counts,
                                                            Q_acc,
                                                            In_q_acc};

                                                    false ->
                                                        {Updated_dists,
                                                            Updated_counts,
                                                            yog@internal@queue:push(
                                                                Q_acc,
                                                                Next_state
                                                            ),
                                                            gleam@set:insert(
                                                                In_q_acc,
                                                                Next_state
                                                            )}
                                                end
                                        end;

                                    _ ->
                                        Acc
                                end;

                            {error, nil} ->
                                Updated_dists@1 = gleam@dict:insert(
                                    Dists,
                                    Next_state,
                                    New_dist
                                ),
                                Updated_counts@1 = gleam@dict:insert(
                                    Counts,
                                    Next_state,
                                    1
                                ),
                                {Updated_dists@1,
                                    Updated_counts@1,
                                    yog@internal@queue:push(Q_acc, Next_state),
                                    gleam@set:insert(In_q_acc, Next_state)}
                        end
                    end
                )
            end,
            Has_negative_cycle = begin
                _pipe@9 = New_counts,
                _pipe@10 = maps:to_list(_pipe@9),
                gleam@list:any(
                    _pipe@10,
                    fun(Entry@2) ->
                        erlang:element(2, Entry@2) > maps:size(New_distances)
                    end
                )
            end,
            case Has_negative_cycle of
                true ->
                    detected_negative_cycle;

                false ->
                    do_implicit_bellman_ford(
                        New_queue,
                        New_distances,
                        New_counts,
                        New_in_q,
                        Successors,
                        Is_goal,
                        Zero,
                        Add,
                        Compare
                    )
            end
    end.

-file("src/yog/pathfinding/bellman_ford.gleam", 198).
?DOC(
    " Finds shortest path in implicit graphs with support for negative edge weights.\n"
    "\n"
    " **Time Complexity:** O(VE) average case\n"
    "\n"
    " ## Returns\n"
    "\n"
    " - `FoundGoal(cost)`: If a valid shortest path to goal exists\n"
    " - `DetectedNegativeCycle`: If a negative cycle is reachable from start\n"
    " - `NoGoal`: If no goal state is reached\n"
).
-spec implicit_bellman_ford(
    QXL,
    fun((QXL) -> list({QXL, QXM})),
    fun((QXL) -> boolean()),
    QXM,
    fun((QXM, QXM) -> QXM),
    fun((QXM, QXM) -> gleam@order:order())
) -> implicit_bellman_ford_result(QXM).
implicit_bellman_ford(Start, Successors, Is_goal, Zero, Add, Compare) ->
    do_implicit_bellman_ford(
        begin
            _pipe = yog@internal@queue:new(),
            yog@internal@queue:push(_pipe, Start)
        end,
        maps:from_list([{Start, Zero}]),
        maps:from_list([{Start, 0}]),
        gleam@set:new(),
        Successors,
        Is_goal,
        Zero,
        Add,
        Compare
    ).

-file("src/yog/pathfinding/bellman_ford.gleam", 348).
-spec do_implicit_bellman_ford_by(
    yog@internal@queue:queue(QYE),
    gleam@dict:dict(QYG, {QYH, QYE}),
    gleam@dict:dict(QYG, integer()),
    gleam@set:set(QYE),
    fun((QYE) -> list({QYE, QYH})),
    fun((QYE) -> QYG),
    fun((QYE) -> boolean()),
    QYH,
    fun((QYH, QYH) -> QYH),
    fun((QYH, QYH) -> gleam@order:order())
) -> implicit_bellman_ford_result(QYH).
do_implicit_bellman_ford_by(
    Q,
    Distances,
    Relax_counts,
    In_queue,
    Successors,
    Key_fn,
    Is_goal,
    Zero,
    Add,
    Compare
) ->
    case yog@internal@queue:pop(Q) of
        {error, nil} ->
            _pipe = Distances,
            _pipe@1 = maps:to_list(_pipe),
            _pipe@2 = gleam@list:filter(
                _pipe@1,
                fun(Entry) ->
                    Is_goal(erlang:element(2, erlang:element(2, Entry)))
                end
            ),
            _pipe@3 = gleam@list:sort(
                _pipe@2,
                fun(A, B) ->
                    Compare(
                        erlang:element(1, erlang:element(2, A)),
                        erlang:element(1, erlang:element(2, B))
                    )
                end
            ),
            _pipe@4 = gleam@list:first(_pipe@3),
            _pipe@5 = gleam@result:map(
                _pipe@4,
                fun(Entry@1) ->
                    {found_goal, erlang:element(1, erlang:element(2, Entry@1))}
                end
            ),
            gleam@result:unwrap(_pipe@5, no_goal);

        {ok, {Current, Rest_queue}} ->
            Current_key = Key_fn(Current),
            New_in_queue = gleam@set:delete(In_queue, Current),
            {Current_dist, _} = begin
                _pipe@6 = gleam_stdlib:map_get(Distances, Current_key),
                gleam@result:unwrap(_pipe@6, {Zero, Current})
            end,
            {New_distances, New_counts, New_queue, New_in_q} = begin
                _pipe@7 = Successors(Current),
                gleam@list:fold(
                    _pipe@7,
                    {Distances, Relax_counts, Rest_queue, New_in_queue},
                    fun(Acc, Neighbor) ->
                        {Dists, Counts, Q_acc, In_q_acc} = Acc,
                        {Next_state, Edge_cost} = Neighbor,
                        Next_key = Key_fn(Next_state),
                        New_dist = Add(Current_dist, Edge_cost),
                        case gleam_stdlib:map_get(Dists, Next_key) of
                            {ok, {Prev_dist, _}} ->
                                case Compare(New_dist, Prev_dist) of
                                    lt ->
                                        Updated_dists = gleam@dict:insert(
                                            Dists,
                                            Next_key,
                                            {New_dist, Next_state}
                                        ),
                                        Relax_count = begin
                                            _pipe@8 = gleam_stdlib:map_get(
                                                Counts,
                                                Next_key
                                            ),
                                            gleam@result:unwrap(_pipe@8, 0)
                                        end,
                                        New_count = Relax_count + 1,
                                        Updated_counts = gleam@dict:insert(
                                            Counts,
                                            Next_key,
                                            New_count
                                        ),
                                        case New_count > maps:size(Dists) of
                                            true ->
                                                {Updated_dists,
                                                    Updated_counts,
                                                    Q_acc,
                                                    In_q_acc};

                                            false ->
                                                case gleam@set:contains(
                                                    In_q_acc,
                                                    Next_state
                                                ) of
                                                    true ->
                                                        {Updated_dists,
                                                            Updated_counts,
                                                            Q_acc,
                                                            In_q_acc};

                                                    false ->
                                                        {Updated_dists,
                                                            Updated_counts,
                                                            yog@internal@queue:push(
                                                                Q_acc,
                                                                Next_state
                                                            ),
                                                            gleam@set:insert(
                                                                In_q_acc,
                                                                Next_state
                                                            )}
                                                end
                                        end;

                                    _ ->
                                        Acc
                                end;

                            {error, nil} ->
                                Updated_dists@1 = gleam@dict:insert(
                                    Dists,
                                    Next_key,
                                    {New_dist, Next_state}
                                ),
                                Updated_counts@1 = gleam@dict:insert(
                                    Counts,
                                    Next_key,
                                    1
                                ),
                                {Updated_dists@1,
                                    Updated_counts@1,
                                    yog@internal@queue:push(Q_acc, Next_state),
                                    gleam@set:insert(In_q_acc, Next_state)}
                        end
                    end
                )
            end,
            Has_negative_cycle = begin
                _pipe@9 = New_counts,
                _pipe@10 = maps:to_list(_pipe@9),
                gleam@list:any(
                    _pipe@10,
                    fun(Entry@2) ->
                        erlang:element(2, Entry@2) > maps:size(New_distances)
                    end
                )
            end,
            case Has_negative_cycle of
                true ->
                    detected_negative_cycle;

                false ->
                    do_implicit_bellman_ford_by(
                        New_queue,
                        New_distances,
                        New_counts,
                        New_in_q,
                        Successors,
                        Key_fn,
                        Is_goal,
                        Zero,
                        Add,
                        Compare
                    )
            end
    end.

-file("src/yog/pathfinding/bellman_ford.gleam", 324).
?DOC(" Like `implicit_bellman_ford`, but deduplicates visited states by a custom key.\n").
-spec implicit_bellman_ford_by(
    QXZ,
    fun((QXZ) -> list({QXZ, QYA})),
    fun((QXZ) -> any()),
    fun((QXZ) -> boolean()),
    QYA,
    fun((QYA, QYA) -> QYA),
    fun((QYA, QYA) -> gleam@order:order())
) -> implicit_bellman_ford_result(QYA).
implicit_bellman_ford_by(Start, Successors, Key_fn, Is_goal, Zero, Add, Compare) ->
    Start_key = Key_fn(Start),
    do_implicit_bellman_ford_by(
        begin
            _pipe = yog@internal@queue:new(),
            yog@internal@queue:push(_pipe, Start)
        end,
        maps:from_list([{Start_key, {Zero, Start}}]),
        maps:from_list([{Start_key, 0}]),
        gleam@set:new(),
        Successors,
        Key_fn,
        Is_goal,
        Zero,
        Add,
        Compare
    ).

-file("src/yog/pathfinding/bellman_ford.gleam", 482).
?DOC(
    " Finds shortest path with **integer weights**, handling negative edges.\n"
    "\n"
    " This is a convenience wrapper around `bellman_ford` that uses:\n"
    " - `0` as the zero element\n"
    " - `int.add` for addition\n"
    " - `int.compare` for comparison\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " bellman_ford.bellman_ford_int(graph, from: 1, to: 5)\n"
    " // => ShortestPath(Path([1, 2, 5], 15))\n"
    " ```\n"
    "\n"
    " ## When to Use\n"
    "\n"
    " Use this for graphs with `Int` edge weights that may be negative (arbitrage\n"
    " detection, time-dependent costs, etc.). For graphs with only non-negative\n"
    " weights, prefer `dijkstra.shortest_path_int` which is faster.\n"
).
-spec bellman_ford_int(yog@model:graph(any(), integer()), integer(), integer()) -> bellman_ford_result(integer()).
bellman_ford_int(Graph, Start, Goal) ->
    bellman_ford(
        Graph,
        Start,
        Goal,
        0,
        fun gleam@int:add/2,
        fun gleam@int:compare/2
    ).

-file("src/yog/pathfinding/bellman_ford.gleam", 509).
?DOC(
    " Finds shortest path with **float weights**, handling negative edges.\n"
    "\n"
    " This is a convenience wrapper around `bellman_ford` that uses:\n"
    " - `0.0` as the zero element\n"
    " - `float.add` for addition\n"
    " - `float.compare` for comparison\n"
    "\n"
    " ## Warning\n"
    "\n"
    " Float arithmetic has precision limitations. Negative cycles might not be\n"
    " detected reliably due to floating-point errors. Prefer `Int` weights for\n"
    " critical calculations.\n"
).
-spec bellman_ford_float(yog@model:graph(any(), float()), integer(), integer()) -> bellman_ford_result(float()).
bellman_ford_float(Graph, Start, Goal) ->
    bellman_ford(
        Graph,
        Start,
        Goal,
        +0.0,
        fun gleam@float:add/2,
        fun gleam@float:compare/2
    ).