-module(yog@pathfinding@unweighted).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/pathfinding/unweighted.gleam").
-export([shortest_path/3, single_source_distances/2, all_pairs_shortest_paths/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(
    " Unweighted pathfinding algorithms for graphs where all edges have equal weight.\n"
    "\n"
    " These algorithms use [Breadth-First Search (BFS)](https://en.wikipedia.org/wiki/Breadth-first_search)\n"
    " to find paths and distances based on the number of hops between nodes.\n"
    "\n"
    " | Algorithm | Function | Complexity | Best For |\n"
    " |-----------|----------|------------|----------|\n"
    " | BFS Path | `shortest_path/3` | O(V + E) | Single-pair unweighted paths |\n"
    " | SSAD | `single_source_distances/2` | O(V + E) | Distances from one node to all others |\n"
    " | Unweighted APSP | `all_pairs_shortest_paths/1` | O(V(V + E)) | All-pairs distances in sparse graphs |\n"
    "\n"
    " ## Why Use Unweighted Algorithms?\n"
    "\n"
    " If your graph doesn't have custom edge weights (or if all weights are identical),\n"
    " Dijkstra and Floyd-Warshall are unnecessarily slow due to their use of priority \n"
    " queues or O(V³) matrices. BFS-based algorithms are the most efficient way to\n"
    " calculate hop-counts.\n"
    "\n"
    " ## Comparison with Weighted Algorithms\n"
    "\n"
    " | Feature | Unweighted (BFS) | Weighted (Dijkstra) |\n"
    " |---------|------------------|---------------------|\n"
    " | point-to-point | O(V + E) | O((V+E) log V) |\n"
    " | SS/APSP | O(V(V + E)) | O(V² log V + VE) |\n"
    " | Overhead | Low (simple queue) | Higher (priority queue) |\n"
    "\n"
).

-file("src/yog/pathfinding/unweighted.gleam", 60).
-spec do_shortest_path(
    yog@model:graph(any(), any()),
    integer(),
    yog@internal@queue:queue({integer(), list(integer())}),
    gleam@dict:dict(integer(), integer())
) -> gleam@option:option(yog@pathfinding@path:path(integer())).
do_shortest_path(Graph, Goal, Q, Visited) ->
    case yog@internal@queue:pop(Q) of
        {error, nil} ->
            none;

        {ok, {{Current, Path}, Rest_q}} ->
            case Current =:= Goal of
                true ->
                    {some, {path, lists:reverse(Path), erlang:length(Path) - 1}};

                false ->
                    Neighbors = yog@model:successor_ids(Graph, Current),
                    {Next_q, Next_visited} = gleam@list:fold(
                        Neighbors,
                        {Rest_q, Visited},
                        fun(Acc, Neighbor) ->
                            {Q_acc, V_acc} = Acc,
                            case gleam@dict:has_key(V_acc, Neighbor) of
                                true ->
                                    Acc;

                                false ->
                                    Dist = begin
                                        _pipe = gleam_stdlib:map_get(
                                            V_acc,
                                            Current
                                        ),
                                        _pipe@1 = gleam@option:from_result(
                                            _pipe
                                        ),
                                        gleam@option:unwrap(_pipe@1, 0)
                                    end,
                                    {yog@internal@queue:push(
                                            Q_acc,
                                            {Neighbor, [Neighbor | Path]}
                                        ),
                                        gleam@dict:insert(
                                            V_acc,
                                            Neighbor,
                                            Dist + 1
                                        )}
                            end
                        end
                    ),
                    do_shortest_path(Graph, Goal, Next_q, Next_visited)
            end
    end.

-file("src/yog/pathfinding/unweighted.gleam", 45).
?DOC(
    " Finds the shortest path (minimum hops) between two nodes in an unweighted graph.\n"
    "\n"
    " **Time Complexity:** O(V + E)\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " unweighted.shortest_path(graph, from: 1, to: 5)\n"
    " // => Some(Path([1, 2, 5], 2))\n"
    " ```\n"
).
-spec shortest_path(yog@model:graph(any(), any()), integer(), integer()) -> gleam@option:option(yog@pathfinding@path:path(integer())).
shortest_path(Graph, Start, Goal) ->
    case Start =:= Goal of
        true ->
            {some, {path, [Start], 0}};

        false ->
            Q = begin
                _pipe = yog@internal@queue:new(),
                yog@internal@queue:push(_pipe, {Start, [Start]})
            end,
            Visited = begin
                _pipe@1 = maps:new(),
                gleam@dict:insert(_pipe@1, Start, 0)
            end,
            do_shortest_path(Graph, Goal, Q, Visited)
    end.

-file("src/yog/pathfinding/unweighted.gleam", 120).
-spec do_single_source(
    yog@model:graph(any(), any()),
    yog@internal@queue:queue(integer()),
    gleam@dict:dict(integer(), integer())
) -> gleam@dict:dict(integer(), integer()).
do_single_source(Graph, Q, Distances) ->
    case yog@internal@queue:pop(Q) of
        {error, nil} ->
            Distances;

        {ok, {Current, Rest_q}} ->
            Current_dist = begin
                _pipe = gleam_stdlib:map_get(Distances, Current),
                _pipe@1 = gleam@option:from_result(_pipe),
                gleam@option:unwrap(_pipe@1, 0)
            end,
            Neighbors = yog@model:successor_ids(Graph, Current),
            {Next_q, Next_distances} = gleam@list:fold(
                Neighbors,
                {Rest_q, Distances},
                fun(Acc, Neighbor) ->
                    {Q_acc, D_acc} = Acc,
                    case gleam@dict:has_key(D_acc, Neighbor) of
                        true ->
                            Acc;

                        false ->
                            {yog@internal@queue:push(Q_acc, Neighbor),
                                gleam@dict:insert(
                                    D_acc,
                                    Neighbor,
                                    Current_dist + 1
                                )}
                    end
                end
            ),
            do_single_source(Graph, Next_q, Next_distances)
    end.

-file("src/yog/pathfinding/unweighted.gleam", 111).
?DOC(
    " Computes the shortest distance (in hops) from a source node to all reachable nodes.\n"
    "\n"
    " **Time Complexity:** O(V + E)\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " unweighted.single_source_distances(graph, source: 1)\n"
    " // => Dict([#(1, 0), #(2, 1), #(5, 2)])\n"
    " ```\n"
).
-spec single_source_distances(yog@model:graph(any(), any()), integer()) -> gleam@dict:dict(integer(), integer()).
single_source_distances(Graph, Start) ->
    Q = begin
        _pipe = yog@internal@queue:new(),
        yog@internal@queue:push(_pipe, Start)
    end,
    Visited = maps:from_list([{Start, 0}]),
    do_single_source(Graph, Q, Visited).

-file("src/yog/pathfinding/unweighted.gleam", 155).
?DOC(
    " Computes hop-count distances between all pairs of nodes in an unweighted graph.\n"
    "\n"
    " This implementation runs a BFS from every node, which is much more efficient than\n"
    " Floyd-Warshall for sparse unweighted graphs.\n"
    "\n"
    " **Time Complexity:** O(V(V + E))\n"
).
-spec all_pairs_shortest_paths(yog@model:graph(any(), any())) -> gleam@dict:dict({integer(),
    integer()}, integer()).
all_pairs_shortest_paths(Graph) ->
    Nodes = maps:keys(erlang:element(3, Graph)),
    gleam@list:fold(
        Nodes,
        maps:new(),
        fun(Acc, Source) ->
            Distances = single_source_distances(Graph, Source),
            gleam@dict:fold(
                Distances,
                Acc,
                fun(Apsp_acc, Target, Dist) ->
                    gleam@dict:insert(Apsp_acc, {Source, Target}, Dist)
                end
            )
        end
    ).