treelist

-module(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, fold/3, fold_right/3]).
-export_type([tree_list/1, node_/1]).

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

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

-spec new_node(FYI) -> node_(FYI).
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_(GCV), integer()) -> node_(GCV).
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(FYO), integer()) -> {ok, FYO} | {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(GAQ)) -> {ok, GAQ} | {error, nil}.
first(Tlist) ->
    case size(Tlist) of
        0 ->
            {error, nil};

        _ ->
            get(Tlist, 0)
    end.

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

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

-spec recalculate(node_(GDB)) -> node_(GDB).
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_(GDH)) -> node_(GDH).
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_(GDK)) -> node_(GDK).
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_(GDE)) -> node_(GDE).
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_(GCY), integer(), GCY) -> node_(GCY).
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(GCD) -> tree_list(GCD).
wrap(Val) ->
    {tree_list, insert_node_at(blank_node, 0, Val)}.

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

-spec insert(tree_list(FYX), integer(), FYX) -> {ok, tree_list(FYX)} |
    {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(FYS), FYS) -> {ok, tree_list(FYS)} | {error, nil}.
add(List, Value) ->
    insert(List, size(List), Value).

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

-spec do_to_list(node_(GDT)) -> list(GDT).
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(FZH)) -> list(FZH).
to_list(L) ->
    do_to_list(erlang:element(2, L)).

-spec find_ultimate_left(node_(GEA)) -> node_(GEA).
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 => <<"treelist"/utf8>>,
                    function => <<"find_ultimate_left"/utf8>>,
                    line => 1005})
    end.

-spec remove_node_at(node_(GDW), integer()) -> {node_(GDW),
    gleam@option:option(GDW)}.
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(FZP), integer()) -> {ok, {FZP, tree_list(FZP)}} |
    {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(GAU)) -> {ok, tree_list(GAU)} | {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(GBX), integer()) -> tree_list(GBX).
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(GED, integer(), node_(GED)) -> node_(GED).
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(FZU, integer()) -> {ok, tree_list(FZU)} | {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_(GEQ), list(node_(GEQ))) -> list(node_(GEQ)).
get_left_stack(Node, Acc) ->
    case Node of
        blank_node ->
            Acc;

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

-spec node_iterator(node_(GEG), fun((node_(GEG), GEG, integer()) -> GEJ)) -> gleam@iterator:iterator(GEJ).
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(FZY)) -> gleam@iterator:iterator(FZY).
to_iterator(Tlist) ->
    node_iterator(erlang:element(2, Tlist), fun(_, Value, _) -> Value end).

-spec get_right_stack(node_(GEW), list(node_(GEW))) -> list(node_(GEW)).
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_(GEL),
    fun((node_(GEL), GEL, integer()) -> GEO)
) -> gleam@iterator:iterator(GEO).
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(GAB)) -> gleam@iterator:iterator(GAB).
to_iterator_reverse(Tlist) ->
    node_iterator_reverse(
        erlang:element(2, Tlist),
        fun(_, Value, _) -> Value end
    ).

-spec set_node_at(node_(GFC), integer(), GFC) -> node_(GFC).
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(FZC), integer(), FZC) -> {ok, tree_list(FZC)} | {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_(GFF)), integer(), GFF) -> 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(GAE), GAE) -> integer().
index_of(Tlist, Item) ->
    Stack = get_left_stack(erlang:element(2, Tlist), []),
    do_index_of(Stack, 0, Item).

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

-spec do_last_index_of(list(node_(GFI)), integer(), GFI) -> 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(GAG), GAG) -> 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_(GFL)), node_(GFL), fun((GFL) -> boolean())) -> node_(GFL).
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(GAK), fun((GAK) -> boolean())) -> tree_list(GAK).
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_(GFQ)),
    node_(GFT),
    fun((GFQ) -> {ok, GFT} | {error, any()})
) -> node_(GFT).
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(GBD), fun((GBD) -> {ok, GBF} | {error, any()})) -> tree_list(GBF).
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_(GFZ)), node_(GGC), fun((GFZ) -> GGC)) -> node_(GGC).
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(GBK), fun((GBK) -> GBM)) -> tree_list(GBM).
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_(GGF)) -> node_(GGF).
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(GAN)) -> tree_list(GAN).
reverse(Tlist) ->
    {tree_list, do_reverse(erlang:element(2, Tlist))}.

-spec do_try_map(
    list(node_(GGI)),
    node_(GGL),
    fun((GGI) -> {ok, GGL} | {error, GGN})
) -> {ok, node_(GGL)} | {error, GGN}.
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(GBO), fun((GBO) -> {ok, GBQ} | {error, GBR})) -> {ok,
        tree_list(GBQ)} |
    {error, GBR}.
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_(GGT)), node_(GGT), integer()) -> node_(GGT).
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(GCA), integer()) -> tree_list(GCA).
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_(GGY)), node_(GGY)) -> node_(GGY).
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(GCF), tree_list(GCF)) -> {ok, tree_list(GCF)} |
    {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
    ).

-spec do_fold(list(node_(GHD)), GHG, fun((GHG, GHD) -> GHG)) -> GHG.
do_fold(Node_stack, Acc, Fold_fn) ->
    case Node_stack of
        [{node, Value, _, _, _, Right} | Rest] ->
            do_fold(
                lists:append(get_left_stack(Right, []), Rest),
                Fold_fn(Acc, Value),
                Fold_fn
            );

        _ ->
            Acc
    end.

-spec fold(tree_list(GCL), GCN, fun((GCN, GCL) -> GCN)) -> GCN.
fold(List, Initial, Fun) ->
    do_fold(get_left_stack(erlang:element(2, List), []), Initial, Fun).

-spec do_fold_right(list(node_(GHH)), GHK, fun((GHK, GHH) -> GHK)) -> GHK.
do_fold_right(Node_stack, Acc, Fold_fn) ->
    case Node_stack of
        [{node, Value, _, _, Left, _} | Rest] ->
            do_fold_right(
                lists:append(get_right_stack(Left, []), Rest),
                Fold_fn(Acc, Value),
                Fold_fn
            );

        _ ->
            Acc
    end.

-spec fold_right(tree_list(GCO), GCQ, fun((GCQ, GCO) -> GCQ)) -> GCQ.
fold_right(List, Initial, Fun) ->
    do_fold_right(get_right_stack(erlang:element(2, List), []), Initial, Fun).