graded

-module(graded@internal@topo).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/graded/internal/topo.gleam").
-export([sort/1]).
-export_type([sort_error/0]).

-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(false).

-type sort_error() :: {cycle, list(binary())}.

-file("src/graded/internal/topo.gleam", 78).
?DOC(false).
-spec prepend_all(list(LTG), list(LTG)) -> list(LTG).
prepend_all(Prefix, Tail) ->
    gleam@list:fold(Prefix, Tail, fun(Acc, Item) -> [Item | Acc] end).

-file("src/graded/internal/topo.gleam", 33).
?DOC(false).
-spec kahn_loop(
    list(binary()),
    gleam@dict:dict(binary(), integer()),
    gleam@dict:dict(binary(), gleam@set:set(binary())),
    list(binary())
) -> {ok, list(binary())} | {error, sort_error()}.
kahn_loop(Queue, In_degrees, Reverse, Acc) ->
    case Queue of
        [] ->
            Remaining = gleam@dict:filter(
                In_degrees,
                fun(_, Degree) -> Degree > 0 end
            ),
            case gleam@dict:is_empty(Remaining) of
                true ->
                    {ok, lists:reverse(Acc)};

                false ->
                    {error, {cycle, maps:keys(Remaining)}}
            end;

        [Node | Rest] ->
            Dependents = case gleam_stdlib:map_get(Reverse, Node) of
                {ok, S} ->
                    gleam@set:to_list(S);

                {error, _} ->
                    []
            end,
            {New_in_degrees, Newly_zero} = gleam@list:fold(
                Dependents,
                {In_degrees, []},
                fun(State, Dependent) ->
                    {Degrees, Zero_acc} = State,
                    Current = case gleam_stdlib:map_get(Degrees, Dependent) of
                        {ok, D} ->
                            D;

                        {error, _} ->
                            0
                    end,
                    Updated = Current - 1,
                    New_degrees = gleam@dict:insert(Degrees, Dependent, Updated),
                    case Updated of
                        0 ->
                            {New_degrees, [Dependent | Zero_acc]};

                        _ ->
                            {New_degrees, Zero_acc}
                    end
                end
            ),
            kahn_loop(
                prepend_all(Newly_zero, Rest),
                New_in_degrees,
                Reverse,
                [Node | Acc]
            )
    end.

-file("src/graded/internal/topo.gleam", 82).
?DOC(false).
-spec build_reverse_graph(gleam@dict:dict(binary(), gleam@set:set(binary()))) -> gleam@dict:dict(binary(), gleam@set:set(binary())).
build_reverse_graph(Graph) ->
    gleam@dict:fold(
        Graph,
        maps:new(),
        fun(Reverse, Node, Deps) ->
            gleam@set:fold(
                Deps,
                Reverse,
                fun(Rev, Dep) ->
                    gleam@dict:upsert(
                        Rev,
                        Dep,
                        fun(Existing) -> case Existing of
                                {some, S} ->
                                    gleam@set:insert(S, Node);

                                none ->
                                    gleam@set:from_list([Node])
                            end end
                    )
                end
            )
        end
    ).

-file("src/graded/internal/topo.gleam", 23).
?DOC(false).
-spec sort(gleam@dict:dict(binary(), gleam@set:set(binary()))) -> {ok,
        list(binary())} |
    {error, sort_error()}.
sort(Graph) ->
    In_degrees = gleam@dict:map_values(
        Graph,
        fun(_, Deps) -> gleam@set:size(Deps) end
    ),
    Reverse = build_reverse_graph(Graph),
    Initial_queue = begin
        _pipe = In_degrees,
        _pipe@1 = gleam@dict:filter(_pipe, fun(_, Degree) -> Degree =:= 0 end),
        maps:keys(_pipe@1)
    end,
    kahn_loop(Initial_queue, In_degrees, Reverse, []).