-module(yog@pathfinding@dijkstra).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/pathfinding/dijkstra.gleam").
-export([do_dijkstra/6, shortest_path/6, single_source_distances/5, implicit_dijkstra/6, implicit_dijkstra_by/7, shortest_path_int/3, shortest_path_float/3, single_source_distances_int/2, single_source_distances_float/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(" Dijkstra's algorithm for finding shortest paths in graphs with non-negative edge weights.\n").

-file("src/yog/pathfinding/dijkstra.gleam", 60).
-spec do_dijkstra(
    yog@model:graph(any(), NJR),
    integer(),
    gleamy@pairing_heap:heap({NJR, list(integer())}),
    gleam@dict:dict(integer(), NJR),
    fun((NJR, NJR) -> NJR),
    fun((NJR, NJR) -> gleam@order:order())
) -> gleam@option:option({NJR, list(integer())}).
do_dijkstra(Graph, Goal, Frontier, Visited, Add, Compare) ->
    case gleamy@priority_queue:pop(Frontier) of
        {error, nil} ->
            none;

        {ok, {{Dist, [Current | _] = Path}, Rest_frontier}} ->
            case Current =:= Goal of
                true ->
                    {some, {Dist, Path}};

                false ->
                    Should_explore = yog@pathfinding@utils:should_explore_node(
                        Visited,
                        Current,
                        Dist,
                        Compare
                    ),
                    case Should_explore of
                        false ->
                            do_dijkstra(
                                Graph,
                                Goal,
                                Rest_frontier,
                                Visited,
                                Add,
                                Compare
                            );

                        true ->
                            New_visited = gleam@dict:insert(
                                Visited,
                                Current,
                                Dist
                            ),
                            Next_frontier = begin
                                _pipe = yog@model:successors(Graph, Current),
                                gleam@list:fold(
                                    _pipe,
                                    Rest_frontier,
                                    fun(H, Neighbor) ->
                                        {Next_id, Weight} = Neighbor,
                                        gleamy@priority_queue:push(
                                            H,
                                            {Add(Dist, Weight),
                                                [Next_id | Path]}
                                        )
                                    end
                                )
                            end,
                            do_dijkstra(
                                Graph,
                                Goal,
                                Next_frontier,
                                New_visited,
                                Add,
                                Compare
                            )
                    end
            end;

        {ok, _} ->
            none
    end.

-file("src/yog/pathfinding/dijkstra.gleam", 41).
?DOC(
    " Finds the shortest path between two nodes using Dijkstra's algorithm.\n"
    "\n"
    " Works with non-negative edge weights only.\n"
    "\n"
    " **Time Complexity:** O((V + E) log V) with heap\n"
    "\n"
    " ## Parameters\n"
    "\n"
    " - `zero`: The identity element for addition (e.g., 0 for integers)\n"
    " - `add`: Function to add two weights\n"
    " - `compare`: Function to compare two weights\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " dijkstra.shortest_path(\n"
    "   in: graph,\n"
    "   from: 1,\n"
    "   to: 5,\n"
    "   with_zero: 0,\n"
    "   with_add: int.add,\n"
    "   with_compare: int.compare\n"
    " )\n"
    " // => Some(Path([1, 2, 5], 15))\n"
    " ```\n"
).
-spec shortest_path(
    yog@model:graph(any(), NJL),
    integer(),
    integer(),
    NJL,
    fun((NJL, NJL) -> NJL),
    fun((NJL, NJL) -> gleam@order:order())
) -> gleam@option:option(yog@pathfinding@utils:path(NJL)).
shortest_path(Graph, Start, Goal, Zero, Add, Compare) ->
    Frontier = begin
        _pipe = gleamy@priority_queue:new(
            fun(A, B) ->
                yog@pathfinding@utils:compare_frontier(A, B, Compare)
            end
        ),
        gleamy@priority_queue:push(_pipe, {Zero, [Start]})
    end,
    _pipe@1 = do_dijkstra(Graph, Goal, Frontier, maps:new(), Add, Compare),
    gleam@option:map(
        _pipe@1,
        fun(Res) ->
            {Dist, Path} = Res,
            {path, lists:reverse(Path), Dist}
        end
    ).

-file("src/yog/pathfinding/dijkstra.gleam", 129).
-spec do_single_source_dijkstra(
    yog@model:graph(any(), NKH),
    gleamy@pairing_heap:heap({NKH, integer()}),
    gleam@dict:dict(integer(), NKH),
    fun((NKH, NKH) -> NKH),
    fun((NKH, NKH) -> gleam@order:order())
) -> gleam@dict:dict(integer(), NKH).
do_single_source_dijkstra(Graph, Frontier, Distances, Add, Compare) ->
    case gleamy@priority_queue:pop(Frontier) of
        {error, nil} ->
            Distances;

        {ok, {{Dist, Current}, Rest_frontier}} ->
            Should_explore = yog@pathfinding@utils:should_explore_node(
                Distances,
                Current,
                Dist,
                Compare
            ),
            case Should_explore of
                false ->
                    do_single_source_dijkstra(
                        Graph,
                        Rest_frontier,
                        Distances,
                        Add,
                        Compare
                    );

                true ->
                    New_distances = gleam@dict:insert(Distances, Current, Dist),
                    Next_frontier = begin
                        _pipe = yog@model:successors(Graph, Current),
                        gleam@list:fold(
                            _pipe,
                            Rest_frontier,
                            fun(H, Neighbor) ->
                                {Next_id, Weight} = Neighbor,
                                gleamy@priority_queue:push(
                                    H,
                                    {Add(Dist, Weight), Next_id}
                                )
                            end
                        )
                    end,
                    do_single_source_dijkstra(
                        Graph,
                        Next_frontier,
                        New_distances,
                        Add,
                        Compare
                    )
            end
    end.

-file("src/yog/pathfinding/dijkstra.gleam", 115).
?DOC(
    " Computes shortest distances from a source node to all reachable nodes.\n"
    "\n"
    " Returns a dictionary mapping each reachable node to its shortest distance\n"
    " from the source. Unreachable nodes are not included in the result.\n"
    "\n"
    " **Time Complexity:** O((V + E) log V) with heap\n"
    "\n"
    " ## Parameters\n"
    "\n"
    " - `zero`: The identity element for addition (e.g., 0 for integers)\n"
    " - `add`: Function to add two weights\n"
    " - `compare`: Function to compare two weights\n"
).
-spec single_source_distances(
    yog@model:graph(any(), NKB),
    integer(),
    NKB,
    fun((NKB, NKB) -> NKB),
    fun((NKB, NKB) -> gleam@order:order())
) -> gleam@dict:dict(integer(), NKB).
single_source_distances(Graph, Source, Zero, Add, Compare) ->
    Frontier = begin
        _pipe = gleamy@priority_queue:new(
            fun(A, B) ->
                yog@pathfinding@utils:compare_distance_frontier(A, B, Compare)
            end
        ),
        gleamy@priority_queue:push(_pipe, {Zero, Source})
    end,
    do_single_source_dijkstra(Graph, Frontier, maps:new(), Add, Compare).

-file("src/yog/pathfinding/dijkstra.gleam", 208).
-spec do_implicit_dijkstra(
    gleamy@pairing_heap:heap({NKT, NKU}),
    gleam@dict:dict(NKU, NKT),
    fun((NKU) -> list({NKU, NKT})),
    fun((NKU) -> boolean()),
    fun((NKT, NKT) -> NKT),
    fun((NKT, NKT) -> gleam@order:order())
) -> gleam@option:option(NKT).
do_implicit_dijkstra(Frontier, Distances, Successors, Is_goal, Add, Compare) ->
    case gleamy@priority_queue:pop(Frontier) of
        {error, nil} ->
            none;

        {ok, {{Dist, Current}, Rest_frontier}} ->
            case Is_goal(Current) of
                true ->
                    {some, Dist};

                false ->
                    Should_explore = yog@pathfinding@utils:should_explore_node(
                        Distances,
                        Current,
                        Dist,
                        Compare
                    ),
                    case Should_explore of
                        false ->
                            do_implicit_dijkstra(
                                Rest_frontier,
                                Distances,
                                Successors,
                                Is_goal,
                                Add,
                                Compare
                            );

                        true ->
                            New_distances = gleam@dict:insert(
                                Distances,
                                Current,
                                Dist
                            ),
                            Next_frontier = begin
                                _pipe = Successors(Current),
                                gleam@list:fold(
                                    _pipe,
                                    Rest_frontier,
                                    fun(H, Neighbor) ->
                                        {Next_state, Cost} = Neighbor,
                                        gleamy@priority_queue:push(
                                            H,
                                            {Add(Dist, Cost), Next_state}
                                        )
                                    end
                                )
                            end,
                            do_implicit_dijkstra(
                                Next_frontier,
                                New_distances,
                                Successors,
                                Is_goal,
                                Add,
                                Compare
                            )
                    end
            end
    end.

-file("src/yog/pathfinding/dijkstra.gleam", 191).
?DOC(
    " Finds the shortest path in an implicit graph using Dijkstra's algorithm.\n"
    "\n"
    " Instead of a materialized `Graph`, this uses a `successors_with_cost` function\n"
    " to compute weighted neighbors on demand.\n"
    "\n"
    " Returns the shortest distance to any state satisfying `is_goal`, or `None`\n"
    " if no goal state is reachable.\n"
    "\n"
    " **Time Complexity:** O((V + E) log V) where V is visited states and E is explored transitions\n"
    "\n"
    " ## Parameters\n"
    "\n"
    " - `successors_with_cost`: Function that generates weighted successors for a state\n"
    " - `is_goal`: Predicate that identifies goal states\n"
    " - `zero`: The identity element for addition (e.g., 0 for integers)\n"
    " - `add`: Function to add two costs\n"
    " - `compare`: Function to compare two costs\n"
).
-spec implicit_dijkstra(
    NKP,
    fun((NKP) -> list({NKP, NKQ})),
    fun((NKP) -> boolean()),
    NKQ,
    fun((NKQ, NKQ) -> NKQ),
    fun((NKQ, NKQ) -> gleam@order:order())
) -> gleam@option:option(NKQ).
implicit_dijkstra(Start, Successors, Is_goal, Zero, Add, Compare) ->
    Frontier = begin
        _pipe = gleamy@priority_queue:new(
            fun(A, B) -> Compare(erlang:element(1, A), erlang:element(1, B)) end
        ),
        gleamy@priority_queue:push(_pipe, {Zero, Start})
    end,
    do_implicit_dijkstra(
        Frontier,
        maps:new(),
        Successors,
        Is_goal,
        Add,
        Compare
    ).

-file("src/yog/pathfinding/dijkstra.gleam", 293).
-spec do_implicit_dijkstra_by(
    gleamy@pairing_heap:heap({NLF, NLG}),
    gleam@dict:dict(NLI, NLF),
    fun((NLG) -> list({NLG, NLF})),
    fun((NLG) -> NLI),
    fun((NLG) -> boolean()),
    fun((NLF, NLF) -> NLF),
    fun((NLF, NLF) -> gleam@order:order())
) -> gleam@option:option(NLF).
do_implicit_dijkstra_by(
    Frontier,
    Distances,
    Successors,
    Key_fn,
    Is_goal,
    Add,
    Compare
) ->
    case gleamy@priority_queue:pop(Frontier) of
        {error, nil} ->
            none;

        {ok, {{Dist, Current}, Rest_frontier}} ->
            case Is_goal(Current) of
                true ->
                    {some, Dist};

                false ->
                    Current_key = Key_fn(Current),
                    Should_explore = yog@pathfinding@utils:should_explore_node(
                        Distances,
                        Current_key,
                        Dist,
                        Compare
                    ),
                    case Should_explore of
                        false ->
                            do_implicit_dijkstra_by(
                                Rest_frontier,
                                Distances,
                                Successors,
                                Key_fn,
                                Is_goal,
                                Add,
                                Compare
                            );

                        true ->
                            New_distances = gleam@dict:insert(
                                Distances,
                                Current_key,
                                Dist
                            ),
                            Next_frontier = begin
                                _pipe = Successors(Current),
                                gleam@list:fold(
                                    _pipe,
                                    Rest_frontier,
                                    fun(H, Neighbor) ->
                                        {Next_state, Cost} = Neighbor,
                                        gleamy@priority_queue:push(
                                            H,
                                            {Add(Dist, Cost), Next_state}
                                        )
                                    end
                                )
                            end,
                            do_implicit_dijkstra_by(
                                Next_frontier,
                                New_distances,
                                Successors,
                                Key_fn,
                                Is_goal,
                                Add,
                                Compare
                            )
                    end
            end
    end.

-file("src/yog/pathfinding/dijkstra.gleam", 267).
?DOC(
    " Like `implicit_dijkstra`, but deduplicates visited states by a custom key.\n"
    "\n"
    " Essential when your state carries extra data beyond what defines identity.\n"
    " The `visited_by` function extracts the deduplication key from each state.\n"
    "\n"
    " **Time Complexity:** O((V + E) log V) where V and E are measured in unique *keys*\n"
).
-spec implicit_dijkstra_by(
    NLA,
    fun((NLA) -> list({NLA, NLB})),
    fun((NLA) -> any()),
    fun((NLA) -> boolean()),
    NLB,
    fun((NLB, NLB) -> NLB),
    fun((NLB, NLB) -> gleam@order:order())
) -> gleam@option:option(NLB).
implicit_dijkstra_by(Start, Successors, Key_fn, Is_goal, Zero, Add, Compare) ->
    Frontier = begin
        _pipe = gleamy@priority_queue:new(
            fun(A, B) -> Compare(erlang:element(1, A), erlang:element(1, B)) end
        ),
        gleamy@priority_queue:push(_pipe, {Zero, Start})
    end,
    do_implicit_dijkstra_by(
        Frontier,
        maps:new(),
        Successors,
        Key_fn,
        Is_goal,
        Add,
        Compare
    ).

-file("src/yog/pathfinding/dijkstra.gleam", 382).
?DOC(
    " Finds the shortest path using **integer weights**.\n"
    "\n"
    " This is a convenience wrapper around `shortest_path` 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"
    " // Much cleaner than the full explicit version\n"
    " dijkstra.shortest_path_int(graph, from: 1, to: 5)\n"
    " // => Some(Path([1, 2, 5], 15))\n"
    "\n"
    " // Equivalent explicit call:\n"
    " // dijkstra.shortest_path(\n"
    " //   graph, from: 1, to: 5,\n"
    " //   with_zero: 0,\n"
    " //   with_add: int.add,\n"
    " //   with_compare: int.compare\n"
    " // )\n"
    " ```\n"
    "\n"
    " ## When to Use\n"
    "\n"
    " Use this for graphs with `Int` edge weights (hop counts, distances in meters,\n"
    " costs in cents, etc.). For custom weight types (Money, Distance, etc.), use\n"
    " the full `shortest_path` function with your own semiring operations.\n"
).
-spec shortest_path_int(yog@model:graph(any(), integer()), integer(), integer()) -> gleam@option:option(yog@pathfinding@utils:path(integer())).
shortest_path_int(Graph, Start, Goal) ->
    shortest_path(
        Graph,
        Start,
        Goal,
        0,
        fun gleam@int:add/2,
        fun gleam@int:compare/2
    ).

-file("src/yog/pathfinding/dijkstra.gleam", 417).
?DOC(
    " Finds the shortest path using **float weights**.\n"
    "\n"
    " This is a convenience wrapper around `shortest_path` that uses:\n"
    " - `0.0` as the zero element\n"
    " - `float.add` for addition\n"
    " - `float.compare` for comparison\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " dijkstra.shortest_path_float(graph, from: 1, to: 5)\n"
    " // => Some(Path([1, 2, 5], 15.5))\n"
    " ```\n"
    "\n"
    " ## When to Use\n"
    "\n"
    " Use this for graphs with `Float` edge weights (probabilities, distances in\n"
    " kilometers with decimal precision, continuous costs, etc.). Note that float\n"
    " arithmetic has precision limitations - for exact calculations, prefer `Int`\n"
    " weights (e.g., store cents instead of dollars).\n"
).
-spec shortest_path_float(yog@model:graph(any(), float()), integer(), integer()) -> gleam@option:option(yog@pathfinding@utils:path(float())).
shortest_path_float(Graph, Start, Goal) ->
    shortest_path(
        Graph,
        Start,
        Goal,
        +0.0,
        fun gleam@float:add/2,
        fun gleam@float:compare/2
    ).

-file("src/yog/pathfinding/dijkstra.gleam", 435).
?DOC(
    " Computes shortest distances using **integer weights**.\n"
    "\n"
    " Convenience wrapper for `single_source_distances` with `Int` weights.\n"
).
-spec single_source_distances_int(yog@model:graph(any(), integer()), integer()) -> gleam@dict:dict(integer(), integer()).
single_source_distances_int(Graph, Source) ->
    single_source_distances(
        Graph,
        Source,
        0,
        fun gleam@int:add/2,
        fun gleam@int:compare/2
    ).

-file("src/yog/pathfinding/dijkstra.gleam", 451).
?DOC(
    " Computes shortest distances using **float weights**.\n"
    "\n"
    " Convenience wrapper for `single_source_distances` with `Float` weights.\n"
).
-spec single_source_distances_float(yog@model:graph(any(), float()), integer()) -> gleam@dict:dict(integer(), float()).
single_source_distances_float(Graph, Source) ->
    single_source_distances(
        Graph,
        Source,
        +0.0,
        fun gleam@float:add/2,
        fun gleam@float:compare/2
    ).