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, scc_order/1]).
-export_type([sort_error/0, tarjan/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())}.

-type tarjan() :: {tarjan,
        integer(),
        gleam@dict:dict(binary(), integer()),
        gleam@dict:dict(binary(), integer()),
        gleam@set:set(binary()),
        list(binary()),
        list(list(binary()))}.

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

-file("src/graded/internal/topo.gleam", 37).
?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", 208).
?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", 25).
?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, []).

-file("src/graded/internal/topo.gleam", 189).
?DOC(false).
-spec pop_component(
    list(binary()),
    gleam@set:set(binary()),
    binary(),
    list(binary())
) -> {list(binary()), list(binary()), gleam@set:set(binary())}.
pop_component(Stack, On_stack, Root, Acc) ->
    case Stack of
        [] ->
            {Acc, [], On_stack};

        [Node | Rest] ->
            On_stack@1 = gleam@set:delete(On_stack, Node),
            Acc@1 = [Node | Acc],
            case Node =:= Root of
                true ->
                    {Acc@1, Rest, On_stack@1};

                false ->
                    pop_component(Rest, On_stack@1, Root, Acc@1)
            end
    end.

-file("src/graded/internal/topo.gleam", 181).
?DOC(false).
-spec lowlink(tarjan(), binary()) -> integer().
lowlink(State, Node) ->
    _pipe = gleam_stdlib:map_get(erlang:element(4, State), Node),
    gleam@result:unwrap(_pipe, 0).

-file("src/graded/internal/topo.gleam", 185).
?DOC(false).
-spec set_lowlink(tarjan(), binary(), integer()) -> tarjan().
set_lowlink(State, Node, Value) ->
    {tarjan,
        erlang:element(2, State),
        erlang:element(3, State),
        gleam@dict:insert(erlang:element(4, State), Node, Value),
        erlang:element(5, State),
        erlang:element(6, State),
        erlang:element(7, State)}.

-file("src/graded/internal/topo.gleam", 132).
?DOC(false).
-spec strong_connect(
    binary(),
    gleam@dict:dict(binary(), gleam@set:set(binary())),
    tarjan()
) -> tarjan().
strong_connect(V, Graph, State) ->
    Index = erlang:element(2, State),
    State@1 = {tarjan,
        Index + 1,
        gleam@dict:insert(erlang:element(3, State), V, Index),
        gleam@dict:insert(erlang:element(4, State), V, Index),
        gleam@set:insert(erlang:element(5, State), V),
        [V | erlang:element(6, State)],
        erlang:element(7, State)},
    Successors = begin
        _pipe = gleam_stdlib:map_get(Graph, V),
        _pipe@1 = gleam@result:unwrap(_pipe, gleam@set:new()),
        gleam@set:to_list(_pipe@1)
    end,
    State@4 = gleam@list:fold(
        Successors,
        State@1,
        fun(State@2, W) ->
            case gleam_stdlib:map_get(erlang:element(3, State@2), W) of
                {error, nil} ->
                    State@3 = strong_connect(W, Graph, State@2),
                    set_lowlink(
                        State@3,
                        V,
                        gleam@int:min(lowlink(State@3, V), lowlink(State@3, W))
                    );

                {ok, Index_w} ->
                    case gleam@set:contains(erlang:element(5, State@2), W) of
                        true ->
                            set_lowlink(
                                State@2,
                                V,
                                gleam@int:min(lowlink(State@2, V), Index_w)
                            );

                        false ->
                            State@2
                    end
            end
        end
    ),
    case lowlink(State@4, V) =:= Index of
        true ->
            {Component, Rest, On_stack} = pop_component(
                erlang:element(6, State@4),
                erlang:element(5, State@4),
                V,
                []
            ),
            {tarjan,
                erlang:element(2, State@4),
                erlang:element(3, State@4),
                erlang:element(4, State@4),
                On_stack,
                Rest,
                [Component | erlang:element(7, State@4)]};

        false ->
            State@4
    end.

-file("src/graded/internal/topo.gleam", 121).
?DOC(false).
-spec new_tarjan() -> tarjan().
new_tarjan() ->
    {tarjan, 0, maps:new(), maps:new(), gleam@set:new(), [], []}.

-file("src/graded/internal/topo.gleam", 96).
?DOC(false).
-spec scc_order(gleam@dict:dict(binary(), gleam@set:set(binary()))) -> list(list(binary())).
scc_order(Graph) ->
    State@1 = gleam@list:fold(
        maps:keys(Graph),
        new_tarjan(),
        fun(State, Node) ->
            case gleam@dict:has_key(erlang:element(3, State), Node) of
                true ->
                    State;

                false ->
                    strong_connect(Node, Graph, State)
            end
        end
    ),
    lists:reverse(erlang:element(7, State@1)).