yog

-module(yog@internal@dsu).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/internal/dsu.gleam").
-export([new/0, add/2, find/2, union/3]).
-export_type([disjoint_set/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(false).

-type disjoint_set(EVI) :: {disjoint_set,
        gleam@dict:dict(EVI, EVI),
        gleam@dict:dict(EVI, integer())}.

-file("src/yog/internal/dsu.gleam", 15).
?DOC(false).
-spec new() -> disjoint_set(any()).
new() ->
    {disjoint_set, maps:new(), maps:new()}.

-file("src/yog/internal/dsu.gleam", 23).
?DOC(false).
-spec add(disjoint_set(EVL), EVL) -> disjoint_set(EVL).
add(Dsu, Element) ->
    case gleam@dict:has_key(erlang:element(2, Dsu), Element) of
        true ->
            Dsu;

        false ->
            {disjoint_set,
                gleam@dict:insert(erlang:element(2, Dsu), Element, Element),
                gleam@dict:insert(erlang:element(3, Dsu), Element, 0)}
    end.

-file("src/yog/internal/dsu.gleam", 40).
?DOC(false).
-spec find(disjoint_set(EVO), EVO) -> {disjoint_set(EVO), EVO}.
find(Dsu, Element) ->
    case gleam_stdlib:map_get(erlang:element(2, Dsu), Element) of
        {error, _} ->
            {add(Dsu, Element), Element};

        {ok, Parent} when Parent =:= Element ->
            {Dsu, Element};

        {ok, Parent@1} ->
            {Updated_dsu, Root} = find(Dsu, Parent@1),
            New_parents = gleam@dict:insert(
                erlang:element(2, Updated_dsu),
                Element,
                Root
            ),
            {{disjoint_set, New_parents, erlang:element(3, Updated_dsu)}, Root}
    end.

-file("src/yog/internal/dsu.gleam", 57).
?DOC(false).
-spec union(disjoint_set(EVR), EVR, EVR) -> disjoint_set(EVR).
union(Dsu, X, Y) ->
    {Dsu1, Root_x} = find(Dsu, X),
    {Dsu2, Root_y} = find(Dsu1, Y),
    case Root_x =:= Root_y of
        true ->
            Dsu2;

        false ->
            Rank_x = begin
                _pipe = gleam_stdlib:map_get(erlang:element(3, Dsu2), Root_x),
                gleam@result:unwrap(_pipe, 0)
            end,
            Rank_y = begin
                _pipe@1 = gleam_stdlib:map_get(erlang:element(3, Dsu2), Root_y),
                gleam@result:unwrap(_pipe@1, 0)
            end,
            case Rank_x < Rank_y of
                true ->
                    {disjoint_set,
                        gleam@dict:insert(
                            erlang:element(2, Dsu2),
                            Root_x,
                            Root_y
                        ),
                        erlang:element(3, Dsu2)};

                false ->
                    Dsu3 = {disjoint_set,
                        gleam@dict:insert(
                            erlang:element(2, Dsu2),
                            Root_y,
                            Root_x
                        ),
                        erlang:element(3, Dsu2)},
                    case Rank_x =:= Rank_y of
                        true ->
                            {disjoint_set,
                                erlang:element(2, Dsu3),
                                gleam@dict:insert(
                                    erlang:element(3, Dsu3),
                                    Root_x,
                                    Rank_x + 1
                                )};

                        false ->
                            Dsu3
                    end
            end
    end.