-module(yog@pathfinding@a_star).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/pathfinding/a_star.gleam").
-export([a_star/7, implicit_a_star/7, implicit_a_star_by/8, a_star_int/4, a_star_float/4]).

-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* (A-Star)](https://en.wikipedia.org/wiki/A*_search_algorithm) search algorithm \n"
    " for optimal pathfinding with heuristic guidance.\n"
    "\n"
    " A* is an informed search algorithm that finds the shortest path from a start node\n"
    " to a goal node using a heuristic function to guide exploration. It combines the\n"
    " completeness of Dijkstra's algorithm with the efficiency of greedy best-first search.\n"
    "\n"
    " ## Algorithm\n"
    "\n"
    " | Algorithm | Function | Complexity | Best For |\n"
    " |-----------|----------|------------|----------|\n"
    " | [A* Search](https://en.wikipedia.org/wiki/A*_search_algorithm) | `a_star/7` | O((V + E) log V) | Pathfinding with good heuristics |\n"
    " | Implicit A* | `implicit_a_star/7` | O((V + E) log V) | Large/infinite graphs generated on-demand |\n"
    "\n"
    " ## Key Concepts\n"
    "\n"
    " - **Evaluation Function**: f(n) = g(n) + h(n)\n"
    "   - g(n): Actual cost from start to node n\n"
    "   - h(n): Heuristic estimate from n to goal\n"
    "   - f(n): Estimated total cost through n\n"
    " - **Admissible Heuristic**: h(n) ≤ actual cost (never overestimates)\n"
    " - **Consistent Heuristic**: h(n) ≤ cost(n→n') + h(n') (triangle inequality)\n"
    "\n"
    " ## When to Use A*\n"
    "\n"
    " **Use A* when:**\n"
    " - You have a specific goal node (not single-source to all)\n"
    " - You can provide a good heuristic estimate\n"
    " - The heuristic is admissible (underestimates)\n"
    "\n"
    " **Use Dijkstra when:**\n"
    " - No good heuristic available (h(n) = 0 reduces A* to Dijkstra)\n"
    " - You need shortest paths to all nodes from a source\n"
    "\n"
    " ## Heuristic Examples\n"
    "\n"
    " | Domain | Heuristic | Admissible? |\n"
    " |--------|-----------|-------------|\n"
    " | Grid (4-way) | Manhattan distance | Yes |\n"
    " | Grid (8-way) | Chebyshev distance | Yes |\n"
    " | Geospatial | Haversine/great-circle | Yes |\n"
    " | Road networks | Precomputed landmarks | Yes |\n"
    "\n"
    " ## Use Cases\n"
    "\n"
    " - **Video games**: NPC pathfinding on game maps\n"
    " - **GPS navigation**: Route planning with distance estimates\n"
    " - **Robotics**: Motion planning with obstacle avoidance\n"
    " - **Puzzle solving**: Sliding puzzles, mazes, labyrinths\n"
    "\n"
    " ## References\n"
    "\n"
    " - [Wikipedia: A* Search Algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm)\n"
    " - [Red Blob Games: A* Implementation](https://www.redblobgames.com/pathfinding/a-star/introduction.html)\n"
    " - [Stanford CS161: A* Lecture](https://web.stanford.edu/class/cs161/lectures/lecture20.pdf)\n"
    " - [CP-Algorithms: A*](https://cp-algorithms.com/graph/A-star.html)\n"
).

-file("src/yog/pathfinding/a_star.gleam", 105).
-spec do_a_star(
    yog@model:graph(any(), SPJ),
    integer(),
    yog@internal@pairing_heap:heap({SMS, SMS, list(integer())}),
    gleam@dict:dict(integer(), SMS),
    fun((SMS, SPJ) -> SMS),
    fun((SMS, SMS) -> gleam@order:order()),
    fun((integer(), integer()) -> SPJ)
) -> gleam@option:option({SMS, list(integer())}).
do_a_star(Graph, Goal, Frontier, Visited, Add, Compare, H) ->
    case yog@internal@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_a_star(
                                Graph,
                                Goal,
                                Rest_frontier,
                                Visited,
                                Add,
                                Compare,
                                H
                            );

                        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(Acc_h, Neighbor) ->
                                        {Next_id, Weight} = Neighbor,
                                        Next_dist = Add(Dist, Weight),
                                        case yog@pathfinding@utils:should_explore_node(
                                            New_visited,
                                            Next_id,
                                            Next_dist,
                                            Compare
                                        ) of
                                            true ->
                                                F_score = Add(
                                                    Next_dist,
                                                    H(Next_id, Goal)
                                                ),
                                                yog@internal@priority_queue:push(
                                                    Acc_h,
                                                    {F_score,
                                                        Next_dist,
                                                        [Next_id | Path]}
                                                );

                                            false ->
                                                Acc_h
                                        end
                                    end
                                )
                            end,
                            do_a_star(
                                Graph,
                                Goal,
                                Next_frontier,
                                New_visited,
                                Add,
                                Compare,
                                H
                            )
                    end
            end;

        _ ->
            none
    end.

-file("src/yog/pathfinding/a_star.gleam", 84).
?DOC(
    " Finds the shortest path using A* search with a heuristic function.\n"
    "\n"
    " A* is more efficient than Dijkstra when you have a good heuristic estimate\n"
    " of the remaining distance to the goal.\n"
    "\n"
    " **Time Complexity:** O((V + E) log V)\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"
    " - `heuristic`: A function that estimates distance from any node to the goal.\n"
    "   Must be admissible (h(n) ≤ actual distance).\n"
).
-spec a_star(
    yog@model:graph(any(), SMG),
    integer(),
    integer(),
    SMG,
    fun((SMG, SMG) -> SMG),
    fun((SMG, SMG) -> gleam@order:order()),
    fun((integer(), integer()) -> SMG)
) -> gleam@option:option(yog@pathfinding@utils:path(SMG)).
a_star(Graph, Start, Goal, Zero, Add, Compare, H) ->
    Initial_f = H(Start, Goal),
    Frontier = begin
        _pipe = yog@internal@priority_queue:new(
            fun(A, B) ->
                yog@pathfinding@utils:compare_a_star_frontier(A, B, Compare)
            end
        ),
        yog@internal@priority_queue:push(_pipe, {Initial_f, Zero, [Start]})
    end,
    _pipe@1 = do_a_star(Graph, Goal, Frontier, maps:new(), Add, Compare, H),
    gleam@option:map(
        _pipe@1,
        fun(Res) ->
            {Dist, Path} = Res,
            {path, lists:reverse(Path), Dist}
        end
    ).

-file("src/yog/pathfinding/a_star.gleam", 201).
-spec do_implicit_a_star(
    yog@internal@pairing_heap:heap({SMZ, SMZ, SNA}),
    gleam@dict:dict(SNA, SMZ),
    fun((SNA) -> list({SNA, SMZ})),
    fun((SNA) -> boolean()),
    fun((SNA) -> SMZ),
    fun((SMZ, SMZ) -> SMZ),
    fun((SMZ, SMZ) -> gleam@order:order())
) -> gleam@option:option(SMZ).
do_implicit_a_star(Frontier, Distances, Successors, Is_goal, H, Add, Compare) ->
    case yog@internal@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_a_star(
                                Rest_frontier,
                                Distances,
                                Successors,
                                Is_goal,
                                H,
                                Add,
                                Compare
                            );

                        true ->
                            New_distances = gleam@dict:insert(
                                Distances,
                                Current,
                                Dist
                            ),
                            Next_frontier = begin
                                _pipe = Successors(Current),
                                gleam@list:fold(
                                    _pipe,
                                    Rest_frontier,
                                    fun(Frontier_acc, Neighbor) ->
                                        {Next_state, Edge_cost} = Neighbor,
                                        Next_dist = Add(Dist, Edge_cost),
                                        case yog@pathfinding@utils:should_explore_node(
                                            New_distances,
                                            Next_state,
                                            Next_dist,
                                            Compare
                                        ) of
                                            true ->
                                                F_score = Add(
                                                    Next_dist,
                                                    H(Next_state)
                                                ),
                                                yog@internal@priority_queue:push(
                                                    Frontier_acc,
                                                    {F_score,
                                                        Next_dist,
                                                        Next_state}
                                                );

                                            false ->
                                                Frontier_acc
                                        end
                                    end
                                )
                            end,
                            do_implicit_a_star(
                                Next_frontier,
                                New_distances,
                                Successors,
                                Is_goal,
                                H,
                                Add,
                                Compare
                            )
                    end
            end
    end.

-file("src/yog/pathfinding/a_star.gleam", 182).
?DOC(
    " Finds the shortest path in an implicit graph using A* search with a heuristic.\n"
    "\n"
    " **Time Complexity:** O((V + E) log V)\n"
    "\n"
    " ## Parameters\n"
    "\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"
    " - `heuristic`: Function that estimates remaining cost from any state to goal.\n"
    "   Must be admissible.\n"
).
-spec implicit_a_star(
    SMV,
    fun((SMV) -> list({SMV, SMW})),
    fun((SMV) -> boolean()),
    fun((SMV) -> SMW),
    SMW,
    fun((SMW, SMW) -> SMW),
    fun((SMW, SMW) -> gleam@order:order())
) -> gleam@option:option(SMW).
implicit_a_star(Start, Successors, Is_goal, H, Zero, Add, Compare) ->
    Initial_f = H(Start),
    Frontier = begin
        _pipe = yog@internal@priority_queue:new(
            fun(A, B) -> Compare(erlang:element(1, A), erlang:element(1, B)) end
        ),
        yog@internal@priority_queue:push(_pipe, {Initial_f, Zero, Start})
    end,
    do_implicit_a_star(
        Frontier,
        maps:new(),
        Successors,
        Is_goal,
        H,
        Add,
        Compare
    ).

-file("src/yog/pathfinding/a_star.gleam", 312).
-spec do_implicit_a_star_by(
    yog@internal@pairing_heap:heap({SNL, SNL, SNM}),
    gleam@dict:dict(SNO, SNL),
    fun((SNM) -> list({SNM, SNL})),
    fun((SNM) -> SNO),
    fun((SNM) -> boolean()),
    fun((SNM) -> SNL),
    fun((SNL, SNL) -> SNL),
    fun((SNL, SNL) -> gleam@order:order())
) -> gleam@option:option(SNL).
do_implicit_a_star_by(
    Frontier,
    Distances,
    Successors,
    Key_fn,
    Is_goal,
    H,
    Add,
    Compare
) ->
    case yog@internal@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_a_star_by(
                                Rest_frontier,
                                Distances,
                                Successors,
                                Key_fn,
                                Is_goal,
                                H,
                                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(Frontier_acc, Neighbor) ->
                                        {Next_state, Edge_cost} = Neighbor,
                                        Next_dist = Add(Dist, Edge_cost),
                                        Next_key = Key_fn(Next_state),
                                        case yog@pathfinding@utils:should_explore_node(
                                            New_distances,
                                            Next_key,
                                            Next_dist,
                                            Compare
                                        ) of
                                            true ->
                                                F_score = Add(
                                                    Next_dist,
                                                    H(Next_state)
                                                ),
                                                yog@internal@priority_queue:push(
                                                    Frontier_acc,
                                                    {F_score,
                                                        Next_dist,
                                                        Next_state}
                                                );

                                            false ->
                                                Frontier_acc
                                        end
                                    end
                                )
                            end,
                            do_implicit_a_star_by(
                                Next_frontier,
                                New_distances,
                                Successors,
                                Key_fn,
                                Is_goal,
                                H,
                                Add,
                                Compare
                            )
                    end
            end
    end.

-file("src/yog/pathfinding/a_star.gleam", 283).
?DOC(
    " Like `implicit_a_star`, 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_a_star_by(
    SNG,
    fun((SNG) -> list({SNG, SNH})),
    fun((SNG) -> any()),
    fun((SNG) -> boolean()),
    fun((SNG) -> SNH),
    SNH,
    fun((SNH, SNH) -> SNH),
    fun((SNH, SNH) -> gleam@order:order())
) -> gleam@option:option(SNH).
implicit_a_star_by(Start, Successors, Key_fn, Is_goal, H, Zero, Add, Compare) ->
    Initial_f = H(Start),
    Frontier = begin
        _pipe = yog@internal@priority_queue:new(
            fun(A, B) -> Compare(erlang:element(1, A), erlang:element(1, B)) end
        ),
        yog@internal@priority_queue:push(_pipe, {Initial_f, Zero, Start})
    end,
    do_implicit_a_star_by(
        Frontier,
        maps:new(),
        Successors,
        Key_fn,
        Is_goal,
        H,
        Add,
        Compare
    ).

-file("src/yog/pathfinding/a_star.gleam", 418).
?DOC(
    " Finds the shortest path using A* with **integer weights**.\n"
    "\n"
    " This is a convenience wrapper around `a_star` that uses:\n"
    " - `0` as the zero element\n"
    " - `int.add` for addition\n"
    " - `int.compare` for comparison\n"
    "\n"
    " You still need to provide a heuristic function.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Grid distance heuristic (Manhattan distance)\n"
    " let heuristic = fn(from, to) {\n"
    "   let dx = int.absolute_value(from.x - to.x)\n"
    "   let dy = int.absolute_value(from.y - to.y)\n"
    "   dx + dy\n"
    " }\n"
    "\n"
    " a_star.a_star_int(graph, from: start, to: goal, with_heuristic: heuristic)\n"
    " ```\n"
).
-spec a_star_int(
    yog@model:graph(any(), integer()),
    integer(),
    integer(),
    fun((integer(), integer()) -> integer())
) -> gleam@option:option(yog@pathfinding@utils:path(integer())).
a_star_int(Graph, Start, Goal, H) ->
    a_star(
        Graph,
        Start,
        Goal,
        0,
        fun gleam@int:add/2,
        fun gleam@int:compare/2,
        H
    ).

-file("src/yog/pathfinding/a_star.gleam", 443).
?DOC(
    " Finds the shortest path using A* with **float weights**.\n"
    "\n"
    " This is a convenience wrapper around `a_star` that uses:\n"
    " - `0.0` as the zero element\n"
    " - `float.add` for addition\n"
    " - `float.compare` for comparison\n"
    "\n"
    " You still need to provide a heuristic function.\n"
).
-spec a_star_float(
    yog@model:graph(any(), float()),
    integer(),
    integer(),
    fun((integer(), integer()) -> float())
) -> gleam@option:option(yog@pathfinding@utils:path(float())).
a_star_float(Graph, Start, Goal, H) ->
    a_star(
        Graph,
        Start,
        Goal,
        +0.0,
        fun gleam@float:add/2,
        fun gleam@float:compare/2,
        H
    ).