-module(yog@pathfinding@bidirectional).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/pathfinding/bidirectional.gleam").
-export([shortest_path_unweighted/3, shortest_path/6, shortest_path_int/3, shortest_path_float/3]).
-export_type([bi_search_state/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(
    " [Bidirectional search](https://en.wikipedia.org/wiki/Bidirectional_search) algorithms\n"
    " that meet in the middle for dramatic speedup.\n"
    "\n"
    " These algorithms start two simultaneous searches - one from the source\n"
    " and one from the target - that meet in the middle. This can dramatically\n"
    " reduce the search space compared to single-direction search.\n"
    "\n"
    " ## Performance Benefits\n"
    "\n"
    " For a graph with branching factor b and depth d:\n"
    " - **Standard BFS**: O(b^d) nodes explored\n"
    " - **Bidirectional BFS**: O(2 × b^(d/2)) nodes explored\n"
    "\n"
    " **Example** with b=10, d=6:\n"
    " - Standard: 10^6 = 1,000,000 nodes\n"
    " - Bidirectional: 2 × 10^3 = 2,000 nodes (500× faster!)\n"
    "\n"
    " ## Algorithms\n"
    "\n"
    " | Algorithm | Function | Complexity | Best For |\n"
    " |-----------|----------|------------|----------|\n"
    " | Bidirectional BFS | `shortest_path_unweighted/3` | O(b^(d/2)) | Unweighted graphs |\n"
    " | Bidirectional Dijkstra | `shortest_path/6` | O(b^(d/2) log b) | Weighted graphs |\n"
    "\n"
    " ## Requirements\n"
    "\n"
    " - Graph must be connected (otherwise no path exists)\n"
    " - For directed graphs: needs efficient reverse edge lookup (yog's `in_edges` structure is perfect!)\n"
    " - Target node must be known in advance\n"
    "\n"
    " ## Termination\n"
    "\n"
    " The tricky part of bidirectional search is knowing when to stop:\n"
    " - **BFS**: Can stop as soon as frontiers touch\n"
    " - **Dijkstra**: Must continue until minimum distances from both sides exceed best path found\n"
    "\n"
    " ## References\n"
    "\n"
    " - [Wikipedia: Bidirectional Search](https://en.wikipedia.org/wiki/Bidirectional_search)\n"
    " - [Red Blob Games: Meeting in the Middle](https://www.redblobgames.com/pathfinding/a-star/introduction.html#bidirectional-search)\n"
    " - [Ira Pohl (1971): Bi-directional Search](https://api.semanticscholar.org/CorpusID:60374980)\n"
).

-type bi_search_state(XOK) :: {bi_search_state,
        gleam@dict:dict(integer(), XOK),
        gleam@dict:dict(integer(), integer()),
        gleam@dict:dict(integer(), XOK),
        gleam@dict:dict(integer(), integer()),
        gleam@option:option(integer()),
        gleam@option:option(XOK)}.

-file("src/yog/pathfinding/bidirectional.gleam", 137).
-spec get_queue_min_dist(
    yog@internal@queue:queue(integer()),
    gleam@dict:dict(integer(), integer())
) -> gleam@option:option(integer()).
get_queue_min_dist(Q, Dists) ->
    case yog@internal@queue:peek(Q) of
        {ok, Node} ->
            _pipe = gleam_stdlib:map_get(Dists, Node),
            gleam@option:from_result(_pipe);

        {error, nil} ->
            none
    end.

-file("src/yog/pathfinding/bidirectional.gleam", 149).
-spec do_bidirectional_bfs(
    yog@model:graph(any(), any()),
    yog@internal@queue:queue(integer()),
    yog@internal@queue:queue(integer()),
    bi_search_state(integer())
) -> gleam@option:option(bi_search_state(integer())).
do_bidirectional_bfs(Graph, Forward_queue, Backward_queue, State) ->
    Can_terminate = case erlang:element(7, State) of
        {some, Best} ->
            F_min = get_queue_min_dist(Forward_queue, erlang:element(2, State)),
            B_min = get_queue_min_dist(Backward_queue, erlang:element(4, State)),
            case {F_min, B_min} of
                {{some, F}, {some, B}} ->
                    ((F + B) + 1) >= Best;

                {_, _} ->
                    false
            end;

        none ->
            false
    end,
    case Can_terminate of
        true ->
            {some, State};

        false ->
            F_empty = begin
                _pipe = yog@internal@queue:pop(Forward_queue),
                gleam@result:is_error(_pipe)
            end,
            B_empty = begin
                _pipe@1 = yog@internal@queue:pop(Backward_queue),
                gleam@result:is_error(_pipe@1)
            end,
            case {F_empty, B_empty} of
                {true, true} ->
                    case erlang:element(6, State) of
                        {some, _} ->
                            {some, State};

                        none ->
                            none
                    end;

                {_, _} ->
                    Forward_size = maps:size(erlang:element(2, State)),
                    Backward_size = maps:size(erlang:element(4, State)),
                    case ((Forward_size =< Backward_size) andalso not F_empty)
                    orelse B_empty of
                        true ->
                            case yog@internal@queue:pop(Forward_queue) of
                                {error, nil} ->
                                    none;

                                {ok, {Current, Rest_queue}} ->
                                    Current_dist = begin
                                        _pipe@2 = gleam_stdlib:map_get(
                                            erlang:element(2, State),
                                            Current
                                        ),
                                        _pipe@3 = gleam@option:from_result(
                                            _pipe@2
                                        ),
                                        gleam@option:unwrap(_pipe@3, 0)
                                    end,
                                    New_state = case gleam@dict:has_key(
                                        erlang:element(4, State),
                                        Current
                                    ) of
                                        true ->
                                            Back_dist = begin
                                                _pipe@4 = gleam_stdlib:map_get(
                                                    erlang:element(4, State),
                                                    Current
                                                ),
                                                _pipe@5 = gleam@option:from_result(
                                                    _pipe@4
                                                ),
                                                gleam@option:unwrap(_pipe@5, 0)
                                            end,
                                            Total = Current_dist + Back_dist,
                                            case erlang:element(7, State) of
                                                {some, Best@1} when Total >= Best@1 ->
                                                    State;

                                                _ ->
                                                    {bi_search_state,
                                                        erlang:element(2, State),
                                                        erlang:element(3, State),
                                                        erlang:element(4, State),
                                                        erlang:element(5, State),
                                                        {some, Current},
                                                        {some, Total}}
                                            end;

                                        false ->
                                            State
                                    end,
                                    Neighbors = yog@model:successor_ids(
                                        Graph,
                                        Current
                                    ),
                                    {Next_state, Next_queue} = gleam@list:fold(
                                        Neighbors,
                                        {New_state, Rest_queue},
                                        fun(Acc, Neighbor) ->
                                            {S, Q} = Acc,
                                            case gleam@dict:has_key(
                                                erlang:element(2, S),
                                                Neighbor
                                            ) of
                                                true ->
                                                    {S, Q};

                                                false ->
                                                    Updated_state = {bi_search_state,
                                                        gleam@dict:insert(
                                                            erlang:element(2, S),
                                                            Neighbor,
                                                            Current_dist + 1
                                                        ),
                                                        gleam@dict:insert(
                                                            erlang:element(3, S),
                                                            Neighbor,
                                                            Current
                                                        ),
                                                        erlang:element(4, S),
                                                        erlang:element(5, S),
                                                        erlang:element(6, S),
                                                        erlang:element(7, S)},
                                                    Updated_queue = yog@internal@queue:push(
                                                        Q,
                                                        Neighbor
                                                    ),
                                                    case gleam@dict:has_key(
                                                        erlang:element(4, S),
                                                        Neighbor
                                                    ) of
                                                        true ->
                                                            Back_dist@1 = begin
                                                                _pipe@6 = gleam_stdlib:map_get(
                                                                    erlang:element(
                                                                        4,
                                                                        S
                                                                    ),
                                                                    Neighbor
                                                                ),
                                                                _pipe@7 = gleam@option:from_result(
                                                                    _pipe@6
                                                                ),
                                                                gleam@option:unwrap(
                                                                    _pipe@7,
                                                                    0
                                                                )
                                                            end,
                                                            Total@1 = (Current_dist
                                                            + 1)
                                                            + Back_dist@1,
                                                            case erlang:element(
                                                                7,
                                                                S
                                                            ) of
                                                                {some, Best@2} when Total@1 >= Best@2 ->
                                                                    {Updated_state,
                                                                        Updated_queue};

                                                                _ ->
                                                                    {{bi_search_state,
                                                                            erlang:element(
                                                                                2,
                                                                                Updated_state
                                                                            ),
                                                                            erlang:element(
                                                                                3,
                                                                                Updated_state
                                                                            ),
                                                                            erlang:element(
                                                                                4,
                                                                                Updated_state
                                                                            ),
                                                                            erlang:element(
                                                                                5,
                                                                                Updated_state
                                                                            ),
                                                                            {some,
                                                                                Neighbor},
                                                                            {some,
                                                                                Total@1}},
                                                                        Updated_queue}
                                                            end;

                                                        false ->
                                                            {Updated_state,
                                                                Updated_queue}
                                                    end
                                            end
                                        end
                                    ),
                                    do_bidirectional_bfs(
                                        Graph,
                                        Next_queue,
                                        Backward_queue,
                                        Next_state
                                    )
                            end;

                        false ->
                            case yog@internal@queue:pop(Backward_queue) of
                                {error, nil} ->
                                    none;

                                {ok, {Current@1, Rest_queue@1}} ->
                                    Current_dist@1 = begin
                                        _pipe@8 = gleam_stdlib:map_get(
                                            erlang:element(4, State),
                                            Current@1
                                        ),
                                        _pipe@9 = gleam@option:from_result(
                                            _pipe@8
                                        ),
                                        gleam@option:unwrap(_pipe@9, 0)
                                    end,
                                    New_state@1 = case gleam@dict:has_key(
                                        erlang:element(2, State),
                                        Current@1
                                    ) of
                                        true ->
                                            Fwd_dist = begin
                                                _pipe@10 = gleam_stdlib:map_get(
                                                    erlang:element(2, State),
                                                    Current@1
                                                ),
                                                _pipe@11 = gleam@option:from_result(
                                                    _pipe@10
                                                ),
                                                gleam@option:unwrap(_pipe@11, 0)
                                            end,
                                            Total@2 = Fwd_dist + Current_dist@1,
                                            case erlang:element(7, State) of
                                                {some, Best@3} when Total@2 >= Best@3 ->
                                                    State;

                                                _ ->
                                                    {bi_search_state,
                                                        erlang:element(2, State),
                                                        erlang:element(3, State),
                                                        erlang:element(4, State),
                                                        erlang:element(5, State),
                                                        {some, Current@1},
                                                        {some, Total@2}}
                                            end;

                                        false ->
                                            State
                                    end,
                                    Predecessors = begin
                                        _pipe@12 = yog@model:predecessors(
                                            Graph,
                                            Current@1
                                        ),
                                        gleam@list:map(
                                            _pipe@12,
                                            fun(P) -> erlang:element(1, P) end
                                        )
                                    end,
                                    {Next_state@1, Next_queue@1} = gleam@list:fold(
                                        Predecessors,
                                        {New_state@1, Rest_queue@1},
                                        fun(Acc@1, Pred) ->
                                            {S@1, Q@1} = Acc@1,
                                            case gleam@dict:has_key(
                                                erlang:element(4, S@1),
                                                Pred
                                            ) of
                                                true ->
                                                    {S@1, Q@1};

                                                false ->
                                                    Updated_state@1 = {bi_search_state,
                                                        erlang:element(2, S@1),
                                                        erlang:element(3, S@1),
                                                        gleam@dict:insert(
                                                            erlang:element(
                                                                4,
                                                                S@1
                                                            ),
                                                            Pred,
                                                            Current_dist@1 + 1
                                                        ),
                                                        gleam@dict:insert(
                                                            erlang:element(
                                                                5,
                                                                S@1
                                                            ),
                                                            Pred,
                                                            Current@1
                                                        ),
                                                        erlang:element(6, S@1),
                                                        erlang:element(7, S@1)},
                                                    Updated_queue@1 = yog@internal@queue:push(
                                                        Q@1,
                                                        Pred
                                                    ),
                                                    case gleam@dict:has_key(
                                                        erlang:element(2, S@1),
                                                        Pred
                                                    ) of
                                                        true ->
                                                            Fwd_dist@1 = begin
                                                                _pipe@13 = gleam_stdlib:map_get(
                                                                    erlang:element(
                                                                        2,
                                                                        S@1
                                                                    ),
                                                                    Pred
                                                                ),
                                                                _pipe@14 = gleam@option:from_result(
                                                                    _pipe@13
                                                                ),
                                                                gleam@option:unwrap(
                                                                    _pipe@14,
                                                                    0
                                                                )
                                                            end,
                                                            Total@3 = (Fwd_dist@1
                                                            + Current_dist@1)
                                                            + 1,
                                                            case erlang:element(
                                                                7,
                                                                S@1
                                                            ) of
                                                                {some, Best@4} when Total@3 >= Best@4 ->
                                                                    {Updated_state@1,
                                                                        Updated_queue@1};

                                                                _ ->
                                                                    {{bi_search_state,
                                                                            erlang:element(
                                                                                2,
                                                                                Updated_state@1
                                                                            ),
                                                                            erlang:element(
                                                                                3,
                                                                                Updated_state@1
                                                                            ),
                                                                            erlang:element(
                                                                                4,
                                                                                Updated_state@1
                                                                            ),
                                                                            erlang:element(
                                                                                5,
                                                                                Updated_state@1
                                                                            ),
                                                                            {some,
                                                                                Pred},
                                                                            {some,
                                                                                Total@3}},
                                                                        Updated_queue@1}
                                                            end;

                                                        false ->
                                                            {Updated_state@1,
                                                                Updated_queue@1}
                                                    end
                                            end
                                        end
                                    ),
                                    do_bidirectional_bfs(
                                        Graph,
                                        Forward_queue,
                                        Next_queue@1,
                                        Next_state@1
                                    )
                            end
                    end
            end
    end.

-file("src/yog/pathfinding/bidirectional.gleam", 412).
-spec build_path_to_meeting(
    gleam@dict:dict(integer(), integer()),
    integer(),
    integer(),
    list(integer())
) -> list(integer()).
build_path_to_meeting(Parent_map, Start, Current, Acc) ->
    case Current =:= Start of
        true ->
            [Start | Acc];

        false ->
            case gleam_stdlib:map_get(Parent_map, Current) of
                {ok, Parent} ->
                    build_path_to_meeting(
                        Parent_map,
                        Start,
                        Parent,
                        [Current | Acc]
                    );

                {error, nil} ->
                    [Current | Acc]
            end
    end.

-file("src/yog/pathfinding/bidirectional.gleam", 430).
-spec build_path_from_meeting(
    gleam@dict:dict(integer(), integer()),
    integer(),
    integer(),
    list(integer())
) -> list(integer()).
build_path_from_meeting(Parent_map, Current, Goal, Acc) ->
    case Current =:= Goal of
        true ->
            lists:reverse(Acc);

        false ->
            case gleam_stdlib:map_get(Parent_map, Current) of
                {ok, Child} ->
                    build_path_from_meeting(
                        Parent_map,
                        Child,
                        Goal,
                        [Child | Acc]
                    );

                {error, nil} ->
                    lists:reverse(Acc)
            end
    end.

-file("src/yog/pathfinding/bidirectional.gleam", 394).
?DOC(" Reconstructs the path from bidirectional search by combining forward and backward paths\n").
-spec reconstruct_bidirectional_path(
    gleam@dict:dict(integer(), integer()),
    gleam@dict:dict(integer(), integer()),
    integer(),
    integer(),
    integer()
) -> list(integer()).
reconstruct_bidirectional_path(
    Forward_parent,
    Backward_parent,
    Start,
    Goal,
    Meeting
) ->
    Forward_path = build_path_to_meeting(Forward_parent, Start, Meeting, []),
    Backward_path = build_path_from_meeting(Backward_parent, Meeting, Goal, []),
    lists:append(Forward_path, Backward_path).

-file("src/yog/pathfinding/bidirectional.gleam", 90).
?DOC(
    " Finds the shortest path in an unweighted graph using bidirectional BFS.\n"
    "\n"
    " This runs BFS from both source and target simultaneously, stopping when\n"
    " the frontiers meet. Much faster than single-direction BFS for long paths.\n"
    "\n"
    " **Time Complexity:** O(b^(d/2)) where b is branching factor and d is depth\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " bidirectional.shortest_path_unweighted(\n"
    "   in: graph,\n"
    "   from: 1,\n"
    "   to: 100\n"
    " )\n"
    " // => Some(Path([1, 5, 20, 100], 3))\n"
    " ```\n"
).
-spec shortest_path_unweighted(
    yog@model:graph(any(), any()),
    integer(),
    integer()
) -> gleam@option:option(yog@pathfinding@path:path(integer())).
shortest_path_unweighted(Graph, Start, Goal) ->
    case Start =:= Goal of
        true ->
            {some, {path, [Start], 0}};

        false ->
            Initial_state = {bi_search_state,
                begin
                    _pipe = maps:new(),
                    gleam@dict:insert(_pipe, Start, 0)
                end,
                maps:new(),
                begin
                    _pipe@1 = maps:new(),
                    gleam@dict:insert(_pipe@1, Goal, 0)
                end,
                maps:new(),
                none,
                none},
            Forward_queue = begin
                _pipe@2 = yog@internal@queue:new(),
                yog@internal@queue:push(_pipe@2, Start)
            end,
            Backward_queue = begin
                _pipe@3 = yog@internal@queue:new(),
                yog@internal@queue:push(_pipe@3, Goal)
            end,
            _pipe@4 = do_bidirectional_bfs(
                Graph,
                Forward_queue,
                Backward_queue,
                Initial_state
            ),
            gleam@option:map(
                _pipe@4,
                fun(State) -> case erlang:element(6, State) of
                        {some, Meeting} ->
                            Path = reconstruct_bidirectional_path(
                                erlang:element(3, State),
                                erlang:element(5, State),
                                Start,
                                Goal,
                                Meeting
                            ),
                            Length = case erlang:element(7, State) of
                                {some, Len} ->
                                    Len;

                                none ->
                                    erlang:length(Path) - 1
                            end,
                            {path, Path, Length};

                        none ->
                            {path, [], 0}
                    end end
            )
    end.

-file("src/yog/pathfinding/bidirectional.gleam", 697).
-spec expand_forward(
    yog@model:graph(any(), XQU),
    yog@internal@pairing_heap:heap({XQU, integer()}),
    yog@internal@pairing_heap:heap({XQU, integer()}),
    gleam@set:set(integer()),
    gleam@set:set(integer()),
    bi_search_state(XQU),
    XQU,
    fun((XQU, XQU) -> XQU),
    fun((XQU, XQU) -> gleam@order:order())
) -> gleam@option:option(bi_search_state(XQU)).
expand_forward(
    Graph,
    Forward_frontier,
    Backward_frontier,
    Forward_settled,
    Backward_settled,
    State,
    Zero,
    Add,
    Compare
) ->
    case yog@internal@priority_queue:pop(Forward_frontier) of
        {error, nil} ->
            do_bidirectional_dijkstra(
                Graph,
                Forward_frontier,
                Backward_frontier,
                Forward_settled,
                Backward_settled,
                State,
                Zero,
                Add,
                Compare
            );

        {ok, {{Dist, Current}, Rest_frontier}} ->
            case gleam@set:contains(Forward_settled, Current) of
                true ->
                    do_bidirectional_dijkstra(
                        Graph,
                        Rest_frontier,
                        Backward_frontier,
                        Forward_settled,
                        Backward_settled,
                        State,
                        Zero,
                        Add,
                        Compare
                    );

                false ->
                    New_settled = gleam@set:insert(Forward_settled, Current),
                    Updated_state = case gleam_stdlib:map_get(
                        erlang:element(4, State),
                        Current
                    ) of
                        {ok, Back_dist} ->
                            Total = Add(Dist, Back_dist),
                            case erlang:element(7, State) of
                                {some, Best} ->
                                    case Compare(Total, Best) of
                                        lt ->
                                            {bi_search_state,
                                                erlang:element(2, State),
                                                erlang:element(3, State),
                                                erlang:element(4, State),
                                                erlang:element(5, State),
                                                {some, Current},
                                                {some, Total}};

                                        _ ->
                                            State
                                    end;

                                none ->
                                    {bi_search_state,
                                        erlang:element(2, State),
                                        erlang:element(3, State),
                                        erlang:element(4, State),
                                        erlang:element(5, State),
                                        {some, Current},
                                        {some, Total}}
                            end;

                        {error, nil} ->
                            State
                    end,
                    Neighbors = yog@model:successors(Graph, Current),
                    {Next_state, Next_frontier} = gleam@list:fold(
                        Neighbors,
                        {Updated_state, Rest_frontier},
                        fun(Acc, Neighbor) ->
                            {S, Frontier} = Acc,
                            {Next_id, Weight} = Neighbor,
                            New_dist = Add(Dist, Weight),
                            case yog@internal@util:should_explore_node(
                                erlang:element(2, S),
                                Next_id,
                                New_dist,
                                Compare
                            ) of
                                true ->
                                    New_s = {bi_search_state,
                                        gleam@dict:insert(
                                            erlang:element(2, S),
                                            Next_id,
                                            New_dist
                                        ),
                                        gleam@dict:insert(
                                            erlang:element(3, S),
                                            Next_id,
                                            Current
                                        ),
                                        erlang:element(4, S),
                                        erlang:element(5, S),
                                        erlang:element(6, S),
                                        erlang:element(7, S)},
                                    New_frontier = yog@internal@priority_queue:push(
                                        Frontier,
                                        {New_dist, Next_id}
                                    ),
                                    {New_s, New_frontier};

                                false ->
                                    {S, Frontier}
                            end
                        end
                    ),
                    do_bidirectional_dijkstra(
                        Graph,
                        Next_frontier,
                        Backward_frontier,
                        New_settled,
                        Backward_settled,
                        Next_state,
                        Zero,
                        Add,
                        Compare
                    )
            end
    end.

-file("src/yog/pathfinding/bidirectional.gleam", 538).
-spec do_bidirectional_dijkstra(
    yog@model:graph(any(), XPY),
    yog@internal@pairing_heap:heap({XPY, integer()}),
    yog@internal@pairing_heap:heap({XPY, integer()}),
    gleam@set:set(integer()),
    gleam@set:set(integer()),
    bi_search_state(XPY),
    XPY,
    fun((XPY, XPY) -> XPY),
    fun((XPY, XPY) -> gleam@order:order())
) -> gleam@option:option(bi_search_state(XPY)).
do_bidirectional_dijkstra(
    Graph,
    Forward_frontier,
    Backward_frontier,
    Forward_settled,
    Backward_settled,
    State,
    Zero,
    Add,
    Compare
) ->
    case {yog@internal@priority_queue:is_empty(Forward_frontier),
        yog@internal@priority_queue:is_empty(Backward_frontier)} of
        {true, true} ->
            case erlang:element(6, State) of
                {some, _} ->
                    {some, State};

                none ->
                    none
            end;

        {_, _} ->
            case erlang:element(7, State) of
                {some, Best} ->
                    Fwd_min = yog@internal@priority_queue:peek(Forward_frontier),
                    Back_min = yog@internal@priority_queue:peek(
                        Backward_frontier
                    ),
                    case {Fwd_min, Back_min} of
                        {{ok, {Fd, _}}, {ok, {Bd, _}}} ->
                            Sum = Add(Fd, Bd),
                            case Compare(Sum, Best) of
                                lt ->
                                    expand_bidirectional(
                                        Graph,
                                        Forward_frontier,
                                        Backward_frontier,
                                        Forward_settled,
                                        Backward_settled,
                                        State,
                                        Zero,
                                        Add,
                                        Compare
                                    );

                                eq ->
                                    expand_bidirectional(
                                        Graph,
                                        Forward_frontier,
                                        Backward_frontier,
                                        Forward_settled,
                                        Backward_settled,
                                        State,
                                        Zero,
                                        Add,
                                        Compare
                                    );

                                gt ->
                                    {some, State}
                            end;

                        {_, _} ->
                            expand_bidirectional(
                                Graph,
                                Forward_frontier,
                                Backward_frontier,
                                Forward_settled,
                                Backward_settled,
                                State,
                                Zero,
                                Add,
                                Compare
                            )
                    end;

                none ->
                    expand_bidirectional(
                        Graph,
                        Forward_frontier,
                        Backward_frontier,
                        Forward_settled,
                        Backward_settled,
                        State,
                        Zero,
                        Add,
                        Compare
                    )
            end
    end.

-file("src/yog/pathfinding/bidirectional.gleam", 619).
-spec expand_bidirectional(
    yog@model:graph(any(), XQJ),
    yog@internal@pairing_heap:heap({XQJ, integer()}),
    yog@internal@pairing_heap:heap({XQJ, integer()}),
    gleam@set:set(integer()),
    gleam@set:set(integer()),
    bi_search_state(XQJ),
    XQJ,
    fun((XQJ, XQJ) -> XQJ),
    fun((XQJ, XQJ) -> gleam@order:order())
) -> gleam@option:option(bi_search_state(XQJ)).
expand_bidirectional(
    Graph,
    Forward_frontier,
    Backward_frontier,
    Forward_settled,
    Backward_settled,
    State,
    Zero,
    Add,
    Compare
) ->
    case {yog@internal@priority_queue:peek(Forward_frontier),
        yog@internal@priority_queue:peek(Backward_frontier)} of
        {{ok, {Fwd_dist, _}}, {ok, {Back_dist, _}}} ->
            case Compare(Fwd_dist, Back_dist) of
                lt ->
                    expand_forward(
                        Graph,
                        Forward_frontier,
                        Backward_frontier,
                        Forward_settled,
                        Backward_settled,
                        State,
                        Zero,
                        Add,
                        Compare
                    );

                eq ->
                    expand_forward(
                        Graph,
                        Forward_frontier,
                        Backward_frontier,
                        Forward_settled,
                        Backward_settled,
                        State,
                        Zero,
                        Add,
                        Compare
                    );

                gt ->
                    expand_backward(
                        Graph,
                        Forward_frontier,
                        Backward_frontier,
                        Forward_settled,
                        Backward_settled,
                        State,
                        Zero,
                        Add,
                        Compare
                    )
            end;

        {{ok, _}, {error, nil}} ->
            expand_forward(
                Graph,
                Forward_frontier,
                Backward_frontier,
                Forward_settled,
                Backward_settled,
                State,
                Zero,
                Add,
                Compare
            );

        {{error, nil}, {ok, _}} ->
            expand_backward(
                Graph,
                Forward_frontier,
                Backward_frontier,
                Forward_settled,
                Backward_settled,
                State,
                Zero,
                Add,
                Compare
            );

        {{error, nil}, {error, nil}} ->
            case erlang:element(6, State) of
                {some, _} ->
                    {some, State};

                none ->
                    none
            end
    end.

-file("src/yog/pathfinding/bidirectional.gleam", 474).
?DOC(
    " Finds the shortest path in a weighted graph using bidirectional Dijkstra.\n"
    "\n"
    " This is trickier than bidirectional BFS because we can't stop as soon\n"
    " as the frontiers meet - we must continue until we can prove optimality.\n"
    "\n"
    " **Time Complexity:** O((V + E) log V / 2) - approximately 2x faster than standard Dijkstra\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"
    " bidirectional.shortest_path(\n"
    "   in: graph,\n"
    "   from: 1,\n"
    "   to: 100,\n"
    "   with_zero: 0,\n"
    "   with_add: int.add,\n"
    "   with_compare: int.compare\n"
    " )\n"
    " // => Some(Path([1, 5, 20, 100], 42))\n"
    " ```\n"
).
-spec shortest_path(
    yog@model:graph(any(), XPS),
    integer(),
    integer(),
    XPS,
    fun((XPS, XPS) -> XPS),
    fun((XPS, XPS) -> gleam@order:order())
) -> gleam@option:option(yog@pathfinding@path:path(XPS)).
shortest_path(Graph, Start, Goal, Zero, Add, Compare) ->
    case Start =:= Goal of
        true ->
            {some, {path, [Start], Zero}};

        false ->
            Initial_state = {bi_search_state,
                begin
                    _pipe = maps:new(),
                    gleam@dict:insert(_pipe, Start, Zero)
                end,
                maps:new(),
                begin
                    _pipe@1 = maps:new(),
                    gleam@dict:insert(_pipe@1, Goal, Zero)
                end,
                maps:new(),
                none,
                none},
            Forward_frontier = begin
                _pipe@2 = yog@internal@priority_queue:new(
                    fun(A, B) ->
                        Compare(erlang:element(1, A), erlang:element(1, B))
                    end
                ),
                yog@internal@priority_queue:push(_pipe@2, {Zero, Start})
            end,
            Backward_frontier = begin
                _pipe@3 = yog@internal@priority_queue:new(
                    fun(A@1, B@1) ->
                        Compare(erlang:element(1, A@1), erlang:element(1, B@1))
                    end
                ),
                yog@internal@priority_queue:push(_pipe@3, {Zero, Goal})
            end,
            _pipe@4 = do_bidirectional_dijkstra(
                Graph,
                Forward_frontier,
                Backward_frontier,
                gleam@set:new(),
                gleam@set:new(),
                Initial_state,
                Zero,
                Add,
                Compare
            ),
            gleam@option:map(
                _pipe@4,
                fun(State) ->
                    case {erlang:element(6, State), erlang:element(7, State)} of
                        {{some, Meeting}, {some, Length}} ->
                            Path = reconstruct_bidirectional_path(
                                erlang:element(3, State),
                                erlang:element(5, State),
                                Start,
                                Goal,
                                Meeting
                            ),
                            {path, Path, Length};

                        {_, _} ->
                            {path, [], Zero}
                    end
                end
            )
    end.

-file("src/yog/pathfinding/bidirectional.gleam", 824).
-spec expand_backward(
    yog@model:graph(any(), XRF),
    yog@internal@pairing_heap:heap({XRF, integer()}),
    yog@internal@pairing_heap:heap({XRF, integer()}),
    gleam@set:set(integer()),
    gleam@set:set(integer()),
    bi_search_state(XRF),
    XRF,
    fun((XRF, XRF) -> XRF),
    fun((XRF, XRF) -> gleam@order:order())
) -> gleam@option:option(bi_search_state(XRF)).
expand_backward(
    Graph,
    Forward_frontier,
    Backward_frontier,
    Forward_settled,
    Backward_settled,
    State,
    Zero,
    Add,
    Compare
) ->
    case yog@internal@priority_queue:pop(Backward_frontier) of
        {error, nil} ->
            do_bidirectional_dijkstra(
                Graph,
                Forward_frontier,
                Backward_frontier,
                Forward_settled,
                Backward_settled,
                State,
                Zero,
                Add,
                Compare
            );

        {ok, {{Dist, Current}, Rest_frontier}} ->
            case gleam@set:contains(Backward_settled, Current) of
                true ->
                    do_bidirectional_dijkstra(
                        Graph,
                        Forward_frontier,
                        Rest_frontier,
                        Forward_settled,
                        Backward_settled,
                        State,
                        Zero,
                        Add,
                        Compare
                    );

                false ->
                    New_settled = gleam@set:insert(Backward_settled, Current),
                    Updated_state = case gleam_stdlib:map_get(
                        erlang:element(2, State),
                        Current
                    ) of
                        {ok, Fwd_dist} ->
                            Total = Add(Fwd_dist, Dist),
                            case erlang:element(7, State) of
                                {some, Best} ->
                                    case Compare(Total, Best) of
                                        lt ->
                                            {bi_search_state,
                                                erlang:element(2, State),
                                                erlang:element(3, State),
                                                erlang:element(4, State),
                                                erlang:element(5, State),
                                                {some, Current},
                                                {some, Total}};

                                        _ ->
                                            State
                                    end;

                                none ->
                                    {bi_search_state,
                                        erlang:element(2, State),
                                        erlang:element(3, State),
                                        erlang:element(4, State),
                                        erlang:element(5, State),
                                        {some, Current},
                                        {some, Total}}
                            end;

                        {error, nil} ->
                            State
                    end,
                    Predecessors = yog@model:predecessors(Graph, Current),
                    {Next_state, Next_frontier} = gleam@list:fold(
                        Predecessors,
                        {Updated_state, Rest_frontier},
                        fun(Acc, Pred) ->
                            {S, Frontier} = Acc,
                            {Pred_id, Weight} = Pred,
                            New_dist = Add(Dist, Weight),
                            case yog@internal@util:should_explore_node(
                                erlang:element(4, S),
                                Pred_id,
                                New_dist,
                                Compare
                            ) of
                                true ->
                                    New_s = {bi_search_state,
                                        erlang:element(2, S),
                                        erlang:element(3, S),
                                        gleam@dict:insert(
                                            erlang:element(4, S),
                                            Pred_id,
                                            New_dist
                                        ),
                                        gleam@dict:insert(
                                            erlang:element(5, S),
                                            Pred_id,
                                            Current
                                        ),
                                        erlang:element(6, S),
                                        erlang:element(7, S)},
                                    New_frontier = yog@internal@priority_queue:push(
                                        Frontier,
                                        {New_dist, Pred_id}
                                    ),
                                    {New_s, New_frontier};

                                false ->
                                    {S, Frontier}
                            end
                        end
                    ),
                    do_bidirectional_dijkstra(
                        Graph,
                        Forward_frontier,
                        Next_frontier,
                        Forward_settled,
                        New_settled,
                        Next_state,
                        Zero,
                        Add,
                        Compare
                    )
            end
    end.

-file("src/yog/pathfinding/bidirectional.gleam", 961).
?DOC(
    " Finds the shortest path using bidirectional Dijkstra with **integer weights**.\n"
    "\n"
    " Convenience wrapper that uses:\n"
    " - `0` as the zero element\n"
    " - `int.add` for addition\n"
    " - `int.compare` for comparison\n"
).
-spec shortest_path_int(yog@model:graph(any(), integer()), integer(), integer()) -> gleam@option:option(yog@pathfinding@path: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/bidirectional.gleam", 982).
?DOC(
    " Finds the shortest path using bidirectional Dijkstra with **float weights**.\n"
    "\n"
    " Convenience wrapper that uses:\n"
    " - `0.0` as the zero element\n"
    " - `float.add` for addition\n"
    " - `float.compare` for comparison\n"
).
-spec shortest_path_float(yog@model:graph(any(), float()), integer(), integer()) -> gleam@option:option(yog@pathfinding@path: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
    ).