glib

-module(glib@treelist).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch]).

-export([new/0, size/1, get/2, first/1, last/1, wrap/1, insert/3, add/2, from_list/1, to_list/1, remove/2, rest/1, drop/2, repeat/2, to_iterator/1, to_iterator_reverse/1, set/3, index_of/2, contains/2, last_index_of/2, filter/2, filter_map/2, map/2, do_reverse/1, reverse/1, try_map/2, take/2, append/2]).
-export_type([tree_list/1, node_/1]).

-opaque tree_list(FYL) :: {tree_list, node_(FYL)}.

-opaque node_(FYM) :: {node, FYM, integer(), integer(), node_(FYM), node_(FYM)} |
    blank_node.

-spec new_node(FYN) -> node_(FYN).
new_node(Value) ->
    {node, Value, 1, 1, blank_node, blank_node}.

-spec new() -> tree_list(any()).
new() ->
    {tree_list, blank_node}.

-spec get_size(node_(any())) -> integer().
get_size(Node) ->
    case Node of
        blank_node ->
            0;

        {node, _, _, Size, _, _} ->
            Size
    end.

-spec size(tree_list(any())) -> integer().
size(List) ->
    get_size(erlang:element(2, List)).

-spec get_height(node_(any())) -> integer().
get_height(Node) ->
    case Node of
        blank_node ->
            0;

        {node, _, Height, _, _, _} ->
            Height
    end.

-spec get_node_at(node_(GCU), integer()) -> node_(GCU).
get_node_at(Node, Index) ->
    case Node of
        {node, _, _, _, Left, Right} ->
            case gleam@int:compare(Index, get_size(Left)) of
                lt ->
                    get_node_at(Left, Index);

                gt ->
                    get_node_at(Right, (Index - get_size(Left)) - 1);

                eq ->
                    Node
            end;

        _ ->
            blank_node
    end.

-spec get(tree_list(FYT), integer()) -> {ok, FYT} | {error, nil}.
get(List, Index) ->
    gleam@bool:guard(
        (Index < 0) orelse (Index >= size(List)),
        {error, nil},
        fun() -> case get_node_at(erlang:element(2, List), Index) of
                {node, Value, _, _, _, _} ->
                    {ok, Value};

                blank_node ->
                    {error, nil}
            end end
    ).

-spec first(tree_list(GAV)) -> {ok, GAV} | {error, nil}.
first(Tlist) ->
    case size(Tlist) of
        0 ->
            {error, nil};

        _ ->
            get(Tlist, 0)
    end.

-spec last(tree_list(GBE)) -> {ok, GBE} | {error, nil}.
last(Tlist) ->
    case size(Tlist) of
        0 ->
            {error, nil};

        Size ->
            get(Tlist, Size - 1)
    end.

-spec recalculate(node_(GDA)) -> node_(GDA).
recalculate(Node) ->
    case Node of
        {node, Value, _, _, Left, Right} ->
            New_height = gleam@int:max(get_height(Left), get_height(Right)) + 1,
            New_size = (get_size(Left) + get_size(Right)) + 1,
            {node, Value, New_height, New_size, Left, Right};

        _ ->
            blank_node
    end.

-spec rotate_left(node_(GDG)) -> node_(GDG).
rotate_left(Node) ->
    case Node of
        {node,
            Value,
            Height,
            Size,
            Left,
            {node,
                Right_value,
                Right_height,
                Right_size,
                Right_left,
                Right_right}} ->
            recalculate(
                {node,
                    Right_value,
                    Right_height,
                    Right_size,
                    recalculate({node, Value, Height, Size, Left, Right_left}),
                    Right_right}
            );

        _ ->
            blank_node
    end.

-spec rotate_right(node_(GDJ)) -> node_(GDJ).
rotate_right(Node) ->
    case Node of
        {node,
            Value,
            Height,
            Size,
            {node, Left_value, Left_height, Left_size, Left_left, Left_right},
            Right} ->
            recalculate(
                {node,
                    Left_value,
                    Left_height,
                    Left_size,
                    Left_left,
                    recalculate({node, Value, Height, Size, Left_right, Right})}
            );

        _ ->
            blank_node
    end.

-spec get_balance(node_(any()), node_(any())) -> integer().
get_balance(Left, Right) ->
    get_height(Right) - get_height(Left).

-spec balance_of(node_(any())) -> integer().
balance_of(Node) ->
    case Node of
        {node, _, _, _, Left, Right} ->
            get_balance(Left, Right);

        _ ->
            9999
    end.

-spec balance(node_(GDD)) -> node_(GDD).
balance(Node) ->
    case Node of
        {node, Value, Height, Size, Left, Right} ->
            case get_balance(Left, Right) of
                -2 ->
                    rotate_right(case balance_of(Left) of
                            1 ->
                                {node,
                                    Value,
                                    Height,
                                    Size,
                                    rotate_left(Left),
                                    Right};

                            _ ->
                                Node
                        end);

                2 ->
                    rotate_left(case balance_of(Right) of
                            -1 ->
                                {node,
                                    Value,
                                    Height,
                                    Size,
                                    Left,
                                    rotate_right(Right)};

                            _ ->
                                Node
                        end);

                _ ->
                    Node
            end;

        _ ->
            blank_node
    end.

-spec insert_node_at(node_(GCX), integer(), GCX) -> node_(GCX).
insert_node_at(Node, Index, New_value) ->
    case Node of
        {node, Value, Height, Size, Left, Right} ->
            Left_size = get_size(Left),
            Res = case gleam@int:compare(Index, Left_size) of
                lt ->
                    {node,
                        Value,
                        Height,
                        Size,
                        insert_node_at(Left, Index, New_value),
                        Right};

                eq ->
                    {node,
                        Value,
                        Height,
                        Size,
                        insert_node_at(Left, Index, New_value),
                        Right};

                gt ->
                    {node,
                        Value,
                        Height,
                        Size,
                        Left,
                        insert_node_at(
                            Right,
                            (Index - Left_size) - 1,
                            New_value
                        )}
            end,
            case recalculate(Res) of
                blank_node ->
                    blank_node;

                Node@1 ->
                    balance(Node@1)
            end;

        _ ->
            new_node(New_value)
    end.

-spec wrap(GCI) -> tree_list(GCI).
wrap(Val) ->
    {tree_list, insert_node_at(blank_node, 0, Val)}.

-spec get_max_int() -> integer().
get_max_int() ->
    999999999999.

-spec insert(tree_list(FZC), integer(), FZC) -> {ok, tree_list(FZC)} |
    {error, nil}.
insert(List, Index, Value) ->
    gleam@bool:guard(
        (Index < 0) orelse (Index > size(List)),
        {error, nil},
        fun() ->
            gleam@bool:guard(
                Index > get_max_int(),
                {error, nil},
                fun() ->
                    {ok,
                        {tree_list,
                            insert_node_at(
                                erlang:element(2, List),
                                Index,
                                Value
                            )}}
                end
            )
        end
    ).

-spec add(tree_list(FYX), FYX) -> {ok, tree_list(FYX)} | {error, nil}.
add(List, Value) ->
    insert(List, size(List), Value).

-spec from_list(list(FZP)) -> {ok, tree_list(FZP)} | {error, nil}.
from_list(List) ->
    gleam@list:try_fold(List, new(), fun(Acc, Val) -> add(Acc, Val) end).

-spec do_to_list(node_(GDS)) -> list(GDS).
do_to_list(Node) ->
    case Node of
        {node, Value, _, _, Left, Right} ->
            Left_list = case Left of
                blank_node ->
                    [];

                _ ->
                    do_to_list(Left)
            end,
            Right_list = case Right of
                blank_node ->
                    [];

                _ ->
                    do_to_list(Right)
            end,
            lists:append(Left_list, [Value | Right_list]);

        _ ->
            []
    end.

-spec to_list(tree_list(FZM)) -> list(FZM).
to_list(L) ->
    do_to_list(erlang:element(2, L)).

-spec find_ultimate_left(node_(GDZ)) -> node_(GDZ).
find_ultimate_left(Node) ->
    case Node of
        {node, _, _, _, Left, _} ->
            case Left of
                blank_node ->
                    Node;

                _ ->
                    find_ultimate_left(Left)
            end;

        blank_node ->
            erlang:error(#{gleam_error => panic,
                    message => <<"panic expression evaluated"/utf8>>,
                    module => <<"glib/treelist"/utf8>>,
                    function => <<"find_ultimate_left"/utf8>>,
                    line => 977})
    end.

-spec remove_node_at(node_(GDV), integer()) -> {node_(GDV),
    gleam@option:option(GDV)}.
remove_node_at(Node, Index) ->
    case Node of
        {node, Value, Height, Size, Left, Right} ->
            {Res, Removed_value, Rebalance} = case gleam@int:compare(
                Index,
                get_size(Left)
            ) of
                lt ->
                    case remove_node_at(Left, Index) of
                        {New_node, {some, Rval}} ->
                            {{node, Value, Height, Size, New_node, Right},
                                {some, Rval},
                                true};

                        _ ->
                            {blank_node, none, false}
                    end;

                gt ->
                    case remove_node_at(Right, (Index - get_size(Left)) - 1) of
                        {New_node@1, {some, Rval@1}} ->
                            {{node, Value, Height, Size, Left, New_node@1},
                                {some, Rval@1},
                                true};

                        _ ->
                            {blank_node, none, false}
                    end;

                eq ->
                    case {Left, Right} of
                        {blank_node, blank_node} ->
                            {blank_node, {some, Value}, false};

                        {_, blank_node} ->
                            {Left, {some, Value}, false};

                        {blank_node, _} ->
                            {Right, {some, Value}, false};

                        {_, _} ->
                            Temp = find_ultimate_left(Right),
                            case {remove_node_at(Right, 0), Temp} of
                                {{New_node@2, _},
                                    {node, Unode_value, _, _, _, _}} ->
                                    {{node,
                                            Unode_value,
                                            Height,
                                            Size,
                                            Left,
                                            New_node@2},
                                        {some, Value},
                                        true};

                                {_, _} ->
                                    {blank_node, none, false}
                            end
                    end
            end,
            case Rebalance of
                false ->
                    {Res, Removed_value};

                true ->
                    case recalculate(Res) of
                        blank_node ->
                            {blank_node, none};

                        Node@1 ->
                            {balance(Node@1), Removed_value}
                    end
            end;

        _ ->
            {blank_node, none}
    end.

-spec remove(tree_list(FZU), integer()) -> {ok, {FZU, tree_list(FZU)}} |
    {error, nil}.
remove(List, Index) ->
    gleam@bool:guard(
        (Index < 0) orelse (Index > size(List)),
        {error, nil},
        fun() -> case remove_node_at(erlang:element(2, List), Index) of
                {New_root, {some, Value}} ->
                    {ok, {Value, {tree_list, New_root}}};

                _ ->
                    {error, nil}
            end end
    ).

-spec rest(tree_list(GAZ)) -> {ok, tree_list(GAZ)} | {error, nil}.
rest(Tlist) ->
    case size(Tlist) of
        0 ->
            {error, nil};

        1 ->
            {ok, new()};

        _ ->
            {ok,
                {tree_list,
                    erlang:element(
                        1,
                        remove_node_at(erlang:element(2, Tlist), 0)
                    )}}
    end.

-spec drop(tree_list(GCC), integer()) -> tree_list(GCC).
drop(Tlist, Up_to_n) ->
    case gleam@int:compare(size(Tlist), Up_to_n) of
        eq ->
            new();

        lt ->
            new();

        gt ->
            {tree_list,
                begin
                    _pipe = gleam@iterator:repeat(0),
                    _pipe@1 = gleam@iterator:take(_pipe, Up_to_n),
                    gleam@iterator:fold(
                        _pipe@1,
                        erlang:element(2, Tlist),
                        fun(Acc, N) ->
                            {New_list, _} = remove_node_at(Acc, N),
                            New_list
                        end
                    )
                end}
    end.

-spec do_repeat(GEC, integer(), node_(GEC)) -> node_(GEC).
do_repeat(A, Times, Acc) ->
    case Times =< 0 of
        true ->
            Acc;

        false ->
            do_repeat(A, Times - 1, insert_node_at(Acc, 0, A))
    end.

-spec repeat(FZZ, integer()) -> {ok, tree_list(FZZ)} | {error, nil}.
repeat(A, Times) ->
    gleam@bool:guard(
        Times > get_max_int(),
        {error, nil},
        fun() -> {ok, {tree_list, do_repeat(A, Times, blank_node)}} end
    ).

-spec get_left_stack(node_(GEP), list(node_(GEP))) -> list(node_(GEP)).
get_left_stack(Node, Acc) ->
    case Node of
        blank_node ->
            Acc;

        {node, _, _, _, Left, _} ->
            get_left_stack(Left, [Node | Acc])
    end.

-spec node_iterator(node_(GEF), fun((node_(GEF), GEF, integer()) -> GEI)) -> gleam@iterator:iterator(GEI).
node_iterator(Tlist, Ret_fn) ->
    Stack = {get_left_stack(Tlist, []), 0},
    Yield = fun(Acc) -> case Acc of
            {[{node, Value, _, _, _, Right} = Node | Rest], Index} ->
                Rest@1 = lists:append(get_left_stack(Right, []), Rest),
                {next, Ret_fn(Node, Value, Index), {Rest@1, Index + 1}};

            _ ->
                done
        end end,
    gleam@iterator:unfold(Stack, Yield).

-spec to_iterator(tree_list(GAD)) -> gleam@iterator:iterator(GAD).
to_iterator(Tlist) ->
    node_iterator(erlang:element(2, Tlist), fun(_, Value, _) -> Value end).

-spec get_right_stack(node_(GEV), list(node_(GEV))) -> list(node_(GEV)).
get_right_stack(Node, Acc) ->
    case Node of
        blank_node ->
            Acc;

        {node, _, _, _, _, Right} ->
            get_right_stack(Right, [Node | Acc])
    end.

-spec node_iterator_reverse(
    node_(GEK),
    fun((node_(GEK), GEK, integer()) -> GEN)
) -> gleam@iterator:iterator(GEN).
node_iterator_reverse(Tlist, Ret_fn) ->
    Stack = {get_right_stack(Tlist, []), 0},
    Yield = fun(Acc) -> case Acc of
            {[{node, Value, _, _, Left, _} = Node | Rest], Index} ->
                Rest@1 = lists:append(get_right_stack(Left, []), Rest),
                {next, Ret_fn(Node, Value, Index), {Rest@1, Index + 1}};

            _ ->
                done
        end end,
    gleam@iterator:unfold(Stack, Yield).

-spec to_iterator_reverse(tree_list(GAG)) -> gleam@iterator:iterator(GAG).
to_iterator_reverse(Tlist) ->
    node_iterator_reverse(
        erlang:element(2, Tlist),
        fun(_, Value, _) -> Value end
    ).

-spec set_node_at(node_(GFB), integer(), GFB) -> node_(GFB).
set_node_at(Node, Index, New_value) ->
    case Node of
        {node, Value, Height, Size, Left, Right} ->
            Left_size = get_size(Left),
            case gleam@int:compare(Index, Left_size) of
                lt ->
                    {node,
                        Value,
                        Height,
                        Size,
                        set_node_at(Left, Index, New_value),
                        Right};

                gt ->
                    {node,
                        Value,
                        Height,
                        Size,
                        Left,
                        set_node_at(Right, (Index - Left_size) - 1, New_value)};

                eq ->
                    {node, New_value, Height, Size, Left, Right}
            end;

        _ ->
            blank_node
    end.

-spec set(tree_list(FZH), integer(), FZH) -> {ok, tree_list(FZH)} | {error, nil}.
set(List, Index, Value) ->
    gleam@bool:guard(
        (Index < 0) orelse (Index >= size(List)),
        {error, nil},
        fun() ->
            {ok,
                {tree_list, set_node_at(erlang:element(2, List), Index, Value)}}
        end
    ).

-spec do_index_of(list(node_(GFE)), integer(), GFE) -> integer().
do_index_of(Node_stack, Index, Search_value) ->
    case Node_stack of
        [{node, Value, _, _, _, Right} | Rest] ->
            case Value =:= Search_value of
                true ->
                    Index;

                false ->
                    do_index_of(
                        lists:append(get_left_stack(Right, []), Rest),
                        Index + 1,
                        Search_value
                    )
            end;

        _ ->
            -1
    end.

-spec index_of(tree_list(GAJ), GAJ) -> integer().
index_of(Tlist, Item) ->
    Stack = get_left_stack(erlang:element(2, Tlist), []),
    do_index_of(Stack, 0, Item).

-spec contains(tree_list(GAN), GAN) -> boolean().
contains(Tlist, Item) ->
    index_of(Tlist, Item) >= 0.

-spec do_last_index_of(list(node_(GFH)), integer(), GFH) -> integer().
do_last_index_of(Node_stack, Index, Search_value) ->
    case Node_stack of
        [{node, Value, _, _, Left, _} | Rest] ->
            case Value =:= Search_value of
                true ->
                    Index;

                false ->
                    do_last_index_of(
                        lists:append(get_right_stack(Left, []), Rest),
                        Index - 1,
                        Search_value
                    )
            end;

        _ ->
            -1
    end.

-spec last_index_of(tree_list(GAL), GAL) -> integer().
last_index_of(Tlist, Item) ->
    Stack = get_right_stack(erlang:element(2, Tlist), []),
    do_last_index_of(Stack, size(Tlist) - 1, Item).

-spec do_filter(list(node_(GFK)), node_(GFK), fun((GFK) -> boolean())) -> node_(GFK).
do_filter(Node_stack, Acc, Filter_fn) ->
    case Node_stack of
        [{node, Value, _, _, _, Right} | Rest] ->
            do_filter(
                lists:append(get_left_stack(Right, []), Rest),
                case Filter_fn(Value) of
                    true ->
                        insert_node_at(Acc, get_size(Acc), Value);

                    false ->
                        Acc
                end,
                Filter_fn
            );

        _ ->
            Acc
    end.

-spec filter(tree_list(GAP), fun((GAP) -> boolean())) -> tree_list(GAP).
filter(Tlist, Filter_fn) ->
    Stack = get_left_stack(erlang:element(2, Tlist), []),
    {tree_list, do_filter(Stack, blank_node, Filter_fn)}.

-spec do_filter_map(
    list(node_(GFP)),
    node_(GFS),
    fun((GFP) -> {ok, GFS} | {error, any()})
) -> node_(GFS).
do_filter_map(Node_stack, Acc, Filter_fn) ->
    case Node_stack of
        [{node, Value, _, _, _, Right} | Rest] ->
            do_filter_map(
                lists:append(get_left_stack(Right, []), Rest),
                case Filter_fn(Value) of
                    {ok, Val} ->
                        insert_node_at(Acc, get_size(Acc), Val);

                    _ ->
                        Acc
                end,
                Filter_fn
            );

        _ ->
            Acc
    end.

-spec filter_map(tree_list(GBI), fun((GBI) -> {ok, GBK} | {error, any()})) -> tree_list(GBK).
filter_map(Tlist, Filter_fn) ->
    Stack = get_left_stack(erlang:element(2, Tlist), []),
    {tree_list, do_filter_map(Stack, blank_node, Filter_fn)}.

-spec do_map(list(node_(GFY)), node_(GGB), fun((GFY) -> GGB)) -> node_(GGB).
do_map(Node_stack, Acc, Filter_fn) ->
    case Node_stack of
        [{node, Value, _, _, _, Right} | Rest] ->
            do_map(
                lists:append(get_left_stack(Right, []), Rest),
                insert_node_at(Acc, get_size(Acc), Filter_fn(Value)),
                Filter_fn
            );

        _ ->
            Acc
    end.

-spec map(tree_list(GBP), fun((GBP) -> GBR)) -> tree_list(GBR).
map(Tlist, Filter_fn) ->
    Stack = get_left_stack(erlang:element(2, Tlist), []),
    {tree_list, do_map(Stack, blank_node, Filter_fn)}.

-spec do_reverse(node_(GGE)) -> node_(GGE).
do_reverse(Node) ->
    case Node of
        {node, Value, Height, Size, Left, Right} ->
            {node, Value, Height, Size, do_reverse(Right), do_reverse(Left)};

        _ ->
            Node
    end.

-spec reverse(tree_list(GAS)) -> tree_list(GAS).
reverse(Tlist) ->
    {tree_list, do_reverse(erlang:element(2, Tlist))}.

-spec do_try_map(
    list(node_(GGH)),
    node_(GGK),
    fun((GGH) -> {ok, GGK} | {error, GGM})
) -> {ok, node_(GGK)} | {error, GGM}.
do_try_map(Node_stack, Acc, Filter_fn) ->
    case Node_stack of
        [{node, Value, _, _, _, Right} | Rest] ->
            case Filter_fn(Value) of
                {error, Err} ->
                    {error, Err};

                {ok, Value@1} ->
                    do_try_map(
                        lists:append(get_left_stack(Right, []), Rest),
                        insert_node_at(Acc, get_size(Acc), Value@1),
                        Filter_fn
                    )
            end;

        _ ->
            {ok, Acc}
    end.

-spec try_map(tree_list(GBT), fun((GBT) -> {ok, GBV} | {error, GBW})) -> {ok,
        tree_list(GBV)} |
    {error, GBW}.
try_map(Tlist, Filter_fn) ->
    Stack = get_left_stack(erlang:element(2, Tlist), []),
    case do_try_map(Stack, blank_node, Filter_fn) of
        {error, Err} ->
            {error, Err};

        {ok, Node} ->
            {ok, {tree_list, Node}}
    end.

-spec do_take(list(node_(GGS)), node_(GGS), integer()) -> node_(GGS).
do_take(Node_stack, Acc, Index) ->
    case Index >= 0 of
        true ->
            case Node_stack of
                [{node, Value, _, _, _, Right} | Rest] ->
                    do_take(
                        lists:append(get_left_stack(Right, []), Rest),
                        insert_node_at(Acc, get_size(Acc), Value),
                        Index - 1
                    );

                _ ->
                    Acc
            end;

        false ->
            Acc
    end.

-spec take(tree_list(GCF), integer()) -> tree_list(GCF).
take(Tlist, Up_to_n) ->
    case gleam@int:compare(size(Tlist), Up_to_n) of
        eq ->
            Tlist;

        lt ->
            Tlist;

        gt ->
            {tree_list,
                do_take(
                    get_left_stack(erlang:element(2, Tlist), []),
                    blank_node,
                    Up_to_n - 1
                )}
    end.

-spec do_append(list(node_(GGX)), node_(GGX)) -> node_(GGX).
do_append(Node_stack, Acc) ->
    case Node_stack of
        [{node, Value, _, _, _, Right} | Rest] ->
            do_append(
                lists:append(get_left_stack(Right, []), Rest),
                insert_node_at(Acc, get_size(Acc), Value)
            );

        _ ->
            Acc
    end.

-spec append(tree_list(GCK), tree_list(GCK)) -> {ok, tree_list(GCK)} |
    {error, nil}.
append(Tlist, Tlist2) ->
    gleam@bool:guard(
        (size(Tlist) + size(Tlist2)) > get_max_int(),
        {error, nil},
        fun() ->
            {ok,
                {tree_list,
                    do_append(
                        get_left_stack(erlang:element(2, Tlist2), []),
                        erlang:element(2, Tlist)
                    )}}
        end
    ).