yog

-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* search algorithm with heuristic guidance.\n").

-file("src/yog/pathfinding/a_star.gleam", 47).
-spec do_a_star(
    yog@model:graph(any(), PRD),
    integer(),
    gleamy@pairing_heap:heap({POP, POP, list(integer())}),
    gleam@dict:dict(integer(), POP),
    fun((POP, PRD) -> POP),
    fun((POP, POP) -> gleam@order:order()),
    fun((integer(), integer()) -> PRD)
) -> gleam@option:option({POP, list(integer())}).
do_a_star(Graph, Goal, Frontier, Visited, Add, Compare, H) ->
    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_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),
                                        F_score = Add(
                                            Next_dist,
                                            H(Next_id, Goal)
                                        ),
                                        gleamy@priority_queue:push(
                                            Acc_h,
                                            {F_score,
                                                Next_dist,
                                                [Next_id | Path]}
                                        )
                                    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", 26).
?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"
    " - `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(), POD),
    integer(),
    integer(),
    POD,
    fun((POD, POD) -> POD),
    fun((POD, POD) -> gleam@order:order()),
    fun((integer(), integer()) -> POD)
) -> gleam@option:option(yog@pathfinding@utils:path(POD)).
a_star(Graph, Start, Goal, Zero, Add, Compare, H) ->
    Initial_f = H(Start, Goal),
    Frontier = begin
        _pipe = gleamy@priority_queue:new(
            fun(A, B) ->
                yog@pathfinding@utils:compare_a_star_frontier(A, B, Compare)
            end
        ),
        gleamy@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", 126).
-spec do_implicit_a_star(
    gleamy@pairing_heap:heap({POW, POW, POX}),
    gleam@dict:dict(POX, POW),
    fun((POX) -> list({POX, POW})),
    fun((POX) -> boolean()),
    fun((POX) -> POW),
    fun((POW, POW) -> POW),
    fun((POW, POW) -> gleam@order:order())
) -> gleam@option:option(POW).
do_implicit_a_star(Frontier, Distances, Successors, Is_goal, H, 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_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),
                                        F_score = Add(Next_dist, H(Next_state)),
                                        gleamy@priority_queue:push(
                                            Frontier_acc,
                                            {F_score, Next_dist, Next_state}
                                        )
                                    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", 107).
?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"
    " - `heuristic`: Function that estimates remaining cost from any state to goal.\n"
    "   Must be admissible.\n"
).
-spec implicit_a_star(
    POS,
    fun((POS) -> list({POS, POT})),
    fun((POS) -> boolean()),
    fun((POS) -> POT),
    POT,
    fun((POT, POT) -> POT),
    fun((POT, POT) -> gleam@order:order())
) -> gleam@option:option(POT).
implicit_a_star(Start, Successors, Is_goal, H, Zero, Add, Compare) ->
    Initial_f = H(Start),
    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, {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", 220).
-spec do_implicit_a_star_by(
    gleamy@pairing_heap:heap({PPI, PPI, PPJ}),
    gleam@dict:dict(PPL, PPI),
    fun((PPJ) -> list({PPJ, PPI})),
    fun((PPJ) -> PPL),
    fun((PPJ) -> boolean()),
    fun((PPJ) -> PPI),
    fun((PPI, PPI) -> PPI),
    fun((PPI, PPI) -> gleam@order:order())
) -> gleam@option:option(PPI).
do_implicit_a_star_by(
    Frontier,
    Distances,
    Successors,
    Key_fn,
    Is_goal,
    H,
    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_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),
                                        F_score = Add(Next_dist, H(Next_state)),
                                        gleamy@priority_queue:push(
                                            Frontier_acc,
                                            {F_score, Next_dist, Next_state}
                                        )
                                    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", 191).
?DOC(
    " Like `implicit_a_star`, but deduplicates visited states by a custom key.\n"
    "\n"
    " **Time Complexity:** O((V + E) log V) where V and E are measured in unique *keys*\n"
).
-spec implicit_a_star_by(
    PPD,
    fun((PPD) -> list({PPD, PPE})),
    fun((PPD) -> any()),
    fun((PPD) -> boolean()),
    fun((PPD) -> PPE),
    PPE,
    fun((PPE, PPE) -> PPE),
    fun((PPE, PPE) -> gleam@order:order())
) -> gleam@option:option(PPE).
implicit_a_star_by(Start, Successors, Key_fn, Is_goal, H, Zero, Add, Compare) ->
    Initial_f = H(Start),
    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, {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", 311).
?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, 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", 336).
?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
    ).