-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](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) for \n"
    " single-source shortest paths in graphs with non-negative edge weights.\n"
    "\n"
    " Dijkstra's algorithm finds the shortest path from a source node to all other reachable\n"
    " nodes in a graph. It works by maintaining a priority queue of nodes to visit,\n"
    " always expanding the node with the smallest known distance.\n"
    "\n"
    " ## Algorithm\n"
    "\n"
    " | Algorithm | Function | Complexity | Best For |\n"
    " |-----------|----------|------------|----------|\n"
    " | [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) (single-target) | `shortest_path/6` | O((V + E) log V) | One-to-one shortest path |\n"
    " | [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) (single-source) | `single_source_distances/5` | O((V + E) log V) | One-to-all shortest paths |\n"
    " | Implicit Dijkstra | `implicit_dijkstra/6` | O((V + E) log V) | Large/infinite graphs |\n"
    "\n"
    " ## Key Concepts\n"
    "\n"
    " - **Greedy Strategy**: Always expands the node with minimum tentative distance\n"
    " - **Priority Queue**: Min-heap ordered by current best distance\n"
    " - **Relaxation**: Update distances when a shorter path is found\n"
    " - **Non-Negative Weights**: Required for correctness (use Bellman-Ford for negative weights)\n"
    "\n"
    " ## Comparison with Other Algorithms\n"
    "\n"
    " | Algorithm | Handles Negative Weights | Complexity | Use Case |\n"
    " |-----------|-------------------------|------------|----------|\n"
    " | Dijkstra | ❌ No | O((V+E) log V) | General shortest paths |\n"
    " | A* | ❌ No | O((V+E) log V) | When good heuristic available |\n"
    " | Bellman-Ford | ✅ Yes | O(VE) | Negative weights, cycle detection |\n"
    " | Floyd-Warshall | ✅ Yes | O(V³) | All-pairs shortest paths |\n"
    "\n"
    " ## History\n"
    "\n"
    " Edsger W. Dijkstra published this algorithm in 1959. The original paper described\n"
    " it for finding the shortest path between two nodes, but it's commonly used for\n"
    " single-source shortest paths to all nodes.\n"
    "\n"
    " ## Use Cases\n"
    "\n"
    " - **Network routing**: OSPF, IS-IS protocols use Dijkstra\n"
    " - **Map services**: Shortest driving directions\n"
    " - **Social networks**: Degrees of separation\n"
    " - **Game development**: Shortest path on weighted grids\n"
    "\n"
    " ## References\n"
    "\n"
    " - [Wikipedia: Dijkstra's Algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)\n"
    " - [Dijkstra's Original Paper (1959)](https://link.springer.com/article/10.1007/BF01386390)\n"
    " - [Red Blob Games: Dijkstra Introduction](https://www.redblobgames.com/pathfinding/a-star/introduction.html)\n"
    " - [CP-Algorithms: Dijkstra](https://cp-algorithms.com/graph/dijkstra.html)\n"
).

-file("src/yog/pathfinding/dijkstra.gleam", 109).
-spec do_dijkstra(
    yog@model:graph(any(), KCD),
    integer(),
    gleamy@pairing_heap:heap({KCD, list(integer())}),
    gleam@dict:dict(integer(), KCD),
    fun((KCD, KCD) -> KCD),
    fun((KCD, KCD) -> gleam@order:order())
) -> gleam@option:option({KCD, 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", 90).
?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(), KBX),
    integer(),
    integer(),
    KBX,
    fun((KBX, KBX) -> KBX),
    fun((KBX, KBX) -> gleam@order:order())
) -> gleam@option:option(yog@pathfinding@utils:path(KBX)).
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", 178).
-spec do_single_source_dijkstra(
    yog@model:graph(any(), KCT),
    gleamy@pairing_heap:heap({KCT, integer()}),
    gleam@dict:dict(integer(), KCT),
    fun((KCT, KCT) -> KCT),
    fun((KCT, KCT) -> gleam@order:order())
) -> gleam@dict:dict(integer(), KCT).
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", 164).
?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(), KCN),
    integer(),
    KCN,
    fun((KCN, KCN) -> KCN),
    fun((KCN, KCN) -> gleam@order:order())
) -> gleam@dict:dict(integer(), KCN).
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", 257).
-spec do_implicit_dijkstra(
    gleamy@pairing_heap:heap({KDF, KDG}),
    gleam@dict:dict(KDG, KDF),
    fun((KDG) -> list({KDG, KDF})),
    fun((KDG) -> boolean()),
    fun((KDF, KDF) -> KDF),
    fun((KDF, KDF) -> gleam@order:order())
) -> gleam@option:option(KDF).
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", 240).
?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(
    KDB,
    fun((KDB) -> list({KDB, KDC})),
    fun((KDB) -> boolean()),
    KDC,
    fun((KDC, KDC) -> KDC),
    fun((KDC, KDC) -> gleam@order:order())
) -> gleam@option:option(KDC).
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", 342).
-spec do_implicit_dijkstra_by(
    gleamy@pairing_heap:heap({KDR, KDS}),
    gleam@dict:dict(KDU, KDR),
    fun((KDS) -> list({KDS, KDR})),
    fun((KDS) -> KDU),
    fun((KDS) -> boolean()),
    fun((KDR, KDR) -> KDR),
    fun((KDR, KDR) -> gleam@order:order())
) -> gleam@option:option(KDR).
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", 316).
?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(
    KDM,
    fun((KDM) -> list({KDM, KDN})),
    fun((KDM) -> any()),
    fun((KDM) -> boolean()),
    KDN,
    fun((KDN, KDN) -> KDN),
    fun((KDN, KDN) -> gleam@order:order())
) -> gleam@option:option(KDN).
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", 431).
?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", 466).
?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", 484).
?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", 500).
?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
    ).