dijkstra

-module(dijkstra).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch]).

-export([dijkstra/2, has_path_to/2, shortest_path/2, dijkstra_all/2, shortest_paths/2]).
-export_type([shortest_paths/1, all_shortest_paths/1]).

-type shortest_paths(IJW) :: {shortest_paths,
        gleam@dict:dict(IJW, integer()),
        gleam@dict:dict(IJW, IJW)}.

-type all_shortest_paths(IJX) :: {all_shortest_paths,
        gleam@dict:dict(IJX, integer()),
        gleam@dict:dict(IJX, list(IJX))}.

-file("/Users/liteyear/Programming/gleam-dijkstra/src/dijkstra.gleam", 68).
-spec do_dijkstra(
    fun((IKO) -> gleam@dict:dict(IKO, integer())),
    gleam@dict:dict(IKO, integer()),
    gleam@dict:dict(IKO, IKO),
    gleamy@pairing_heap:heap({IKO, integer()})
) -> shortest_paths(IKO).
do_dijkstra(Edges_from, Dist, Pred, Q) ->
    case gleamy@priority_queue:is_empty(Q) of
        true ->
            {shortest_paths, Dist, Pred};

        false ->
            _assert_subject = gleamy@priority_queue:pop(Q),
            {ok, {{U, _}, Q@1}} = case _assert_subject of
                {ok, {{_, _}, _}} -> _assert_subject;
                _assert_fail ->
                    erlang:error(#{gleam_error => let_assert,
                                message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                value => _assert_fail,
                                module => <<"dijkstra"/utf8>>,
                                function => <<"do_dijkstra"/utf8>>,
                                line => 75})
            end,
            {Dist@2, Pred@2, Q@3} = gleam@dict:fold(
                Edges_from(U),
                {Dist, Pred, Q@1},
                fun(Acc, V, Uv_dist) ->
                    {Dist@1, Pred@1, Q@2} = Acc,
                    _assert_subject@1 = gleam_stdlib:map_get(Dist@1, U),
                    {ok, U_dist} = case _assert_subject@1 of
                        {ok, _} -> _assert_subject@1;
                        _assert_fail@1 ->
                            erlang:error(#{gleam_error => let_assert,
                                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                        value => _assert_fail@1,
                                        module => <<"dijkstra"/utf8>>,
                                        function => <<"do_dijkstra"/utf8>>,
                                        line => 78})
                    end,
                    Alt = U_dist + Uv_dist,
                    case gleam_stdlib:map_get(Dist@1, V) of
                        {ok, V_dist} when Alt >= V_dist ->
                            Acc;

                        _ ->
                            {gleam@dict:insert(Dist@1, V, Alt),
                                gleam@dict:insert(Pred@1, V, U),
                                gleamy@priority_queue:push(Q@2, {V, Alt})}
                    end
                end
            ),
            do_dijkstra(Edges_from, Dist@2, Pred@2, Q@3)
    end.

-file("/Users/liteyear/Programming/gleam-dijkstra/src/dijkstra.gleam", 59).
-spec dijkstra(fun((IKL) -> gleam@dict:dict(IKL, integer())), IKL) -> shortest_paths(IKL).
dijkstra(Edges_from, Start) ->
    Dist = maps:from_list([{Start, 0}]),
    Q = gleamy@priority_queue:from_list(
        [{Start, 0}],
        fun(A, B) ->
            gleam@int:compare(erlang:element(2, A), erlang:element(2, B))
        end
    ),
    do_dijkstra(Edges_from, Dist, maps:new(), Q).

-file("/Users/liteyear/Programming/gleam-dijkstra/src/dijkstra.gleam", 98).
-spec has_path_to(shortest_paths(IKU), IKU) -> boolean().
has_path_to(Paths, Dest) ->
    gleam@dict:has_key(erlang:element(2, Paths), Dest).

-file("/Users/liteyear/Programming/gleam-dijkstra/src/dijkstra.gleam", 113).
-spec do_shortest_path(gleam@dict:dict(ILC, ILC), ILC) -> list(ILC).
do_shortest_path(Predecessors, Curr) ->
    case gleam_stdlib:map_get(Predecessors, Curr) of
        {error, _} ->
            [Curr];

        {ok, Pred} ->
            [Curr | do_shortest_path(Predecessors, Pred)]
    end.

-file("/Users/liteyear/Programming/gleam-dijkstra/src/dijkstra.gleam", 106).
-spec shortest_path(shortest_paths(IKX), IKX) -> {list(IKX), integer()}.
shortest_path(Paths, Dest) ->
    Path = do_shortest_path(erlang:element(3, Paths), Dest),
    _assert_subject = gleam_stdlib:map_get(erlang:element(2, Paths), Dest),
    {ok, Dist} = case _assert_subject of
        {ok, _} -> _assert_subject;
        _assert_fail ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        value => _assert_fail,
                        module => <<"dijkstra"/utf8>>,
                        function => <<"shortest_path"/utf8>>,
                        line => 109})
    end,
    {lists:reverse(Path), Dist}.

-file("/Users/liteyear/Programming/gleam-dijkstra/src/dijkstra.gleam", 135).
-spec do_dijkstra_all(
    fun((ILH) -> gleam@dict:dict(ILH, integer())),
    gleam@dict:dict(ILH, integer()),
    gleam@dict:dict(ILH, list(ILH)),
    gleamy@pairing_heap:heap({ILH, integer()})
) -> all_shortest_paths(ILH).
do_dijkstra_all(Edges_from, Dist, Pred, Q) ->
    case gleamy@priority_queue:is_empty(Q) of
        true ->
            {all_shortest_paths, Dist, Pred};

        false ->
            _assert_subject = gleamy@priority_queue:pop(Q),
            {ok, {{U, _}, Q@1}} = case _assert_subject of
                {ok, {{_, _}, _}} -> _assert_subject;
                _assert_fail ->
                    erlang:error(#{gleam_error => let_assert,
                                message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                value => _assert_fail,
                                module => <<"dijkstra"/utf8>>,
                                function => <<"do_dijkstra_all"/utf8>>,
                                line => 142})
            end,
            {Dist@2, Pred@2, Q@3} = gleam@dict:fold(
                Edges_from(U),
                {Dist, Pred, Q@1},
                fun(Acc, V, Uv_dist) ->
                    {Dist@1, Pred@1, Q@2} = Acc,
                    _assert_subject@1 = gleam_stdlib:map_get(Dist@1, U),
                    {ok, U_dist} = case _assert_subject@1 of
                        {ok, _} -> _assert_subject@1;
                        _assert_fail@1 ->
                            erlang:error(#{gleam_error => let_assert,
                                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                        value => _assert_fail@1,
                                        module => <<"dijkstra"/utf8>>,
                                        function => <<"do_dijkstra_all"/utf8>>,
                                        line => 145})
                    end,
                    Alt = U_dist + Uv_dist,
                    case gleam_stdlib:map_get(Dist@1, V) of
                        {ok, V_dist} when Alt > V_dist ->
                            Acc;

                        {ok, V_dist@1} when Alt =:= V_dist@1 ->
                            {Dist@1,
                                gleam@dict:upsert(Pred@1, V, fun(X) -> case X of
                                            {some, I} ->
                                                [U | I];

                                            _ ->
                                                erlang:error(
                                                    #{gleam_error => panic,
                                                        message => <<"BUG"/utf8>>,
                                                        module => <<"dijkstra"/utf8>>,
                                                        function => <<"do_dijkstra_all"/utf8>>,
                                                        line => 153}
                                                )
                                        end end),
                                Q@2};

                        _ ->
                            {gleam@dict:insert(Dist@1, V, Alt),
                                gleam@dict:insert(Pred@1, V, [U]),
                                gleamy@priority_queue:push(Q@2, {V, Alt})}
                    end
                end
            ),
            do_dijkstra_all(Edges_from, Dist@2, Pred@2, Q@3)
    end.

-file("/Users/liteyear/Programming/gleam-dijkstra/src/dijkstra.gleam", 126).
-spec dijkstra_all(fun((ILE) -> gleam@dict:dict(ILE, integer())), ILE) -> all_shortest_paths(ILE).
dijkstra_all(Edges_from, Start) ->
    Dist = maps:from_list([{Start, 0}]),
    Q = gleamy@priority_queue:from_list(
        [{Start, 0}],
        fun(A, B) ->
            gleam@int:compare(erlang:element(2, A), erlang:element(2, B))
        end
    ),
    do_dijkstra_all(Edges_from, Dist, maps:new(), Q).

-file("/Users/liteyear/Programming/gleam-dijkstra/src/dijkstra.gleam", 174).
-spec do_shortest_paths(gleam@dict:dict(ILR, list(ILR)), list(ILR), ILR) -> list(list(ILR)).
do_shortest_paths(Predecessors, Path, Curr) ->
    New_path = [Curr | Path],
    case gleam_stdlib:map_get(Predecessors, Curr) of
        {error, _} ->
            [New_path];

        {ok, Preds} ->
            gleam@list:flat_map(
                Preds,
                fun(_capture) ->
                    do_shortest_paths(Predecessors, New_path, _capture)
                end
            )
    end.

-file("/Users/liteyear/Programming/gleam-dijkstra/src/dijkstra.gleam", 167).
-spec shortest_paths(all_shortest_paths(ILN), ILN) -> {list(list(ILN)),
    integer()}.
shortest_paths(All_paths, Dest) ->
    Paths = do_shortest_paths(erlang:element(3, All_paths), [], Dest),
    _assert_subject = gleam_stdlib:map_get(erlang:element(2, All_paths), Dest),
    {ok, Dist} = case _assert_subject of
        {ok, _} -> _assert_subject;
        _assert_fail ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        value => _assert_fail,
                        module => <<"dijkstra"/utf8>>,
                        function => <<"shortest_paths"/utf8>>,
                        line => 170})
    end,
    {Paths, Dist}.