topological

-module(topological).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/topological.gleam").
-export([describe_reason/1, sort/1]).
-export_type([reason/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.

-type reason(DKT) :: {dependency_cycle, list(DKT)} | {missing_node, DKT}.

-file("src/topological.gleam", 21).
-spec describe_reason(reason(any())) -> binary().
describe_reason(Reason) ->
    case Reason of
        {dependency_cycle, Cycle} ->
            <<"cycle detected: "/utf8,
                (begin
                    _pipe = Cycle,
                    _pipe@1 = gleam@list:map(_pipe, fun gleam@string:inspect/1),
                    gleam@string:join(_pipe@1, <<" -> "/utf8>>)
                end)/binary>>;

        {missing_node, Node} ->
            <<"missing node: "/utf8, (gleam@string:inspect(Node))/binary>>
    end.

-file("src/topological.gleam", 30).
-spec dfs(DLZ, list(DLZ), list(DLZ), list({DLZ, list(DLZ)}), list(DLZ)) -> {ok,
        list(DLZ)} |
    {error, reason(DLZ)}.
dfs(Node, Children, Path, Graph, Output) ->
    {Path@1, Check} = gleam@list:split_while(Path, fun(X) -> X /= Node end),
    case Check of
        [] ->
            Path@2 = [Node | Path@1],
            Result = gleam@list:try_fold(
                Children,
                Output,
                fun(Output@1, Child) ->
                    case gleam@list:contains(Output@1, Child) of
                        true ->
                            {ok, Output@1};

                        false ->
                            case gleam@list:key_find(Graph, Child) of
                                {ok, Children@1} ->
                                    dfs(
                                        Child,
                                        Children@1,
                                        Path@2,
                                        Graph,
                                        Output@1
                                    );

                                {error, nil} ->
                                    {error, {missing_node, Child}}
                            end
                    end
                end
            ),
            case Result of
                {ok, Output@2} ->
                    {ok, [Node | Output@2]};

                {error, Reason} ->
                    {error, Reason}
            end;

        _ ->
            {error,
                {dependency_cycle,
                    begin
                        _pipe = [Node | lists:reverse(Path@1)],
                        lists:append(_pipe, [Node])
                    end}}
    end.

-file("src/topological.gleam", 5).
?DOC(" topological sort of list of items\n").
-spec sort(list({DKU, list(DKU)})) -> {ok, list(DKU)} | {error, reason(DKU)}.
sort(Graph) ->
    gleam@list:try_fold(
        Graph,
        [],
        fun(Output, El) ->
            {Node, Children} = El,
            case gleam@list:contains(Output, Node) of
                true ->
                    {ok, Output};

                false ->
                    dfs(Node, Children, [], Graph, Output)
            end
        end
    ).