balanced_tree_gleam

-module(balanced_tree).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/balanced_tree.gleam").
-export([balance/1, delete/2, from_dict/1, from_list/1, get/2, get_larger/2, get_smaller/2, has_key/2, insert/3, is_empty/1, get_max/1, get_min/1, iterate/1, iterate_right/1, keys/1, map_values/2, new/0, pop_max/1, pop_min/1, size/1, to_list/1, each/2, filter/2, drop/2, fold/3, fold_right/3, to_dict/1, merge/2, upsert/3, combine/3, values/1]).
-export_type([balanced_tree/2, iter/2, order/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(
    " BalancedTree is a Gleam friendly wrapper around erlang's gb_trees module\n"
    " It implements the same functions as gleam/dict, a few from gleam/list, and some additional that are unique to gb_trees\n"
    " \n"
    " Build Target is Erlang-only. I may consider writing a javascript implementation in the future\n"
    "\n"
).

-type balanced_tree(FMJ, FMK) :: any() | {gleam_phantom, FMJ, FMK}.

-type iter(FML, FMM) :: any() | {gleam_phantom, FML, FMM}.

-type order() :: ordered | reversed.

-file("src/balanced_tree.gleam", 90).
?DOC(" Notice that this is rarely necessary, but can be motivated when many nodes have been deleted from the tree without further insertions. Rebalancing can then be forced to minimize lookup times, as deletion does not rebalance the tree.\n").
-spec balance(balanced_tree(FOY, FOZ)) -> balanced_tree(FOY, FOZ).
balance(Tree) ->
    gb_trees:balance(Tree).

-file("src/balanced_tree.gleam", 114).
?DOC(" Creates a new tree from a given tree with all the same entries except for the one with a given key, if it exists.\n").
-spec delete(balanced_tree(FPM, FPN), FPM) -> balanced_tree(FPM, FPN).
delete(Tree, Key) ->
    gb_trees:delete_any(Key, Tree).

-file("src/balanced_tree.gleam", 173).
?DOC(" Converts a `Dict(k, v)` into a `BalancedTree(k, v)`\n").
-spec from_dict(gleam@dict:dict(FQU, FQV)) -> balanced_tree(FQU, FQV).
from_dict(Dict) ->
    _pipe = Dict,
    _pipe@1 = maps:to_list(_pipe),
    gb_trees:from_orddict(_pipe@1).

-file("src/balanced_tree.gleam", 180).
?DOC(
    " Converts a list of 2-element tuples `#(key, value)` to a tree.\n"
    "\n"
    " If two tuples have the same key the last one in the list will be the one that is present in the tree.\n"
).
-spec from_list(list({FRA, FRB})) -> balanced_tree(FRA, FRB).
from_list(List) ->
    _pipe = List,
    _pipe@1 = maps:from_list(_pipe),
    from_dict(_pipe@1).

-file("src/balanced_tree.gleam", 190).
?DOC(
    " Fetches a value from a tree for a given key.\n"
    "\n"
    " The tree may not have a value for the key, so the value is wrapped in a Result.\n"
).
-spec get(balanced_tree(FRF, FRG), FRF) -> {ok, FRG} | {error, nil}.
get(Gb_tree, Key) ->
    gb_trees_shim:lookup_shim(Gb_tree, Key).

-file("src/balanced_tree.gleam", 196).
?DOC(
    " Gets the 2-element tuple `#(key, value)` of the next larger key in the Tree.\n"
    " \n"
    " The tree may not have a larger key, so the tuple is wrapped in a `Result`.\n"
).
-spec get_larger(balanced_tree(FRL, FRM), FRL) -> {ok, {FRL, FRM}} |
    {error, nil}.
get_larger(Tree, Key) ->
    gb_trees_shim:larger_shim(Tree, Key).

-file("src/balanced_tree.gleam", 222).
?DOC(
    " Gets the 2-element tuple `#(key, value)` of the next smaller key in the Tree.\n"
    " \n"
    " The tree may not have a smaller key, so the tuple is wrapped in a `Result`.\n"
).
-spec get_smaller(balanced_tree(FSD, FSE), FSD) -> {ok, {FSD, FSE}} |
    {error, nil}.
get_smaller(Tree, Key) ->
    gb_trees_shim:smaller_shim(Tree, Key).

-file("src/balanced_tree.gleam", 225).
?DOC(" Determines whether or not a value is present in the tree for a given key.\n").
-spec has_key(balanced_tree(FSJ, any()), FSJ) -> boolean().
has_key(Tree, Key) ->
    gb_trees:is_defined(Key, Tree).

-file("src/balanced_tree.gleam", 229).
-spec insert(balanced_tree(FSN, FSO), FSN, FSO) -> balanced_tree(FSN, FSO).
insert(Tree, Key, Value) ->
    gb_trees:enter(Key, Value, Tree).

-file("src/balanced_tree.gleam", 239).
?DOC(" Determines whether or not the tree is empty.\n").
-spec is_empty(balanced_tree(any(), any())) -> boolean().
is_empty(Tree) ->
    gb_trees:is_empty(Tree).

-file("src/balanced_tree.gleam", 201).
?DOC(
    " Fetches the key-value pair for the largest key in the tree.\n"
    "\n"
    " Returns `Error(Nil)` when the tree is empty, otherwise `Ok(#(k, v))`\n"
).
-spec get_max(balanced_tree(FRR, FRS)) -> {ok, {FRR, FRS}} | {error, nil}.
get_max(Tree) ->
    case gb_trees:is_empty(Tree) of
        true ->
            {error, nil};

        false ->
            _pipe = Tree,
            _pipe@1 = gb_trees:largest(_pipe),
            {ok, _pipe@1}
    end.

-file("src/balanced_tree.gleam", 211).
?DOC(
    " Fetches the key-value pair for the smallest key in the tree.\n"
    "\n"
    " Returns `Error(Nil)` when the tree is empty, otherwise `Ok(#(k, v))`\n"
).
-spec get_min(balanced_tree(FRX, FRY)) -> {ok, {FRX, FRY}} | {error, nil}.
get_min(Tree) ->
    case gb_trees:is_empty(Tree) of
        true ->
            {error, nil};

        false ->
            _pipe = Tree,
            _pipe@1 = gb_trees:smallest(_pipe),
            {ok, _pipe@1}
    end.

-file("src/balanced_tree.gleam", 241).
-spec iterate_internal(balanced_tree(FSX, FSY), order()) -> gleam@yielder:yielder({FSX,
    FSY}).
iterate_internal(Tree, Order) ->
    Iter = gb_trees:iterator(Tree, Order),
    gleam@yielder:unfold(Iter, fun(Acc) -> case gb_trees_shim:next_shim(Acc) of
                {error, nil} ->
                    done;

                {ok, {Key, Value, Next_acc}} ->
                    {next, {Key, Value}, Next_acc}
            end end).

-file("src/balanced_tree.gleam", 252).
?DOC(" Generate a `Yielder` that traverses in the tree in min-to-max order\n").
-spec iterate(balanced_tree(FTC, FTD)) -> gleam@yielder:yielder({FTC, FTD}).
iterate(Tree) ->
    iterate_internal(Tree, ordered).

-file("src/balanced_tree.gleam", 257).
?DOC(" Generate a `Yielder` that traverses in the tree in max-to-min order\n").
-spec iterate_right(balanced_tree(FTH, FTI)) -> gleam@yielder:yielder({FTH, FTI}).
iterate_right(Tree) ->
    iterate_internal(Tree, reversed).

-file("src/balanced_tree.gleam", 265).
?DOC(
    " Gets a list of all keys in a given dict.\n"
    "\n"
    " BalancedTrees are ordered. Keys are returned ordered min-to-max.\n"
).
-spec keys(balanced_tree(FTM, any())) -> list(FTM).
keys(Tree) ->
    gb_trees:keys(Tree).

-file("src/balanced_tree.gleam", 268).
?DOC(" Updates all values in a given tree by calling a given function on each key and value.\n").
-spec map_values(balanced_tree(FTR, FTS), fun((FTR, FTS) -> FTV)) -> balanced_tree(FTR, FTV).
map_values(Tree, Fun) ->
    gb_trees:map(Fun, Tree).

-file("src/balanced_tree.gleam", 291).
?DOC(" Creates a fresh tree that contains no values.\n").
-spec new() -> balanced_tree(any(), any()).
new() ->
    gb_trees:empty().

-file("src/balanced_tree.gleam", 294).
?DOC(" Gets the max key-value pair in the tree, returning the pair and a new tree without that pair.\n").
-spec pop_max(balanced_tree(FUK, FUL)) -> {ok,
        {{FUK, FUL}, balanced_tree(FUK, FUL)}} |
    {error, nil}.
pop_max(Tree) ->
    case gb_trees:is_empty(Tree) of
        true ->
            {error, nil};

        false ->
            _pipe = Tree,
            _pipe@1 = gb_trees:take_largest(_pipe),
            _pipe@2 = (fun(T) ->
                {{erlang:element(1, T), erlang:element(2, T)},
                    erlang:element(3, T)}
            end)(_pipe@1),
            {ok, _pipe@2}
    end.

-file("src/balanced_tree.gleam", 305).
?DOC(" Gets the min key-value pair in the tree, returning the pair and a new tree without that pair.\n").
-spec pop_min(balanced_tree(FUS, FUT)) -> {ok,
        {{FUS, FUT}, balanced_tree(FUS, FUT)}} |
    {error, nil}.
pop_min(Tree) ->
    case gb_trees:is_empty(Tree) of
        true ->
            {error, nil};

        false ->
            _pipe = Tree,
            _pipe@1 = gb_trees:take_smallest(_pipe),
            _pipe@2 = (fun(T) ->
                {{erlang:element(1, T), erlang:element(2, T)},
                    erlang:element(3, T)}
            end)(_pipe@1),
            {ok, _pipe@2}
    end.

-file("src/balanced_tree.gleam", 319).
?DOC(
    " Determines the number of key-value pairs in the dict.\n"
    " \n"
    " Unlike gleam/dict, this function must iterate over the tree and runs in linear time time\n"
).
-spec size(balanced_tree(any(), any())) -> integer().
size(Tree) ->
    gb_trees:size(Tree).

-file("src/balanced_tree.gleam", 325).
?DOC(
    " Converts the dict to a list of 2-element tuples #(key, value), one for each key-value pair in the dict.\n"
    "\n"
    " The tuples in the list are ordered by Key\n"
).
-spec to_list(balanced_tree(FVE, FVF)) -> list({FVE, FVF}).
to_list(Tree) ->
    gb_trees:to_list(Tree).

-file("src/balanced_tree.gleam", 133).
?DOC(
    " Calls a function for each key and value in a tree, discarding the return value.\n"
    "\n"
    " Useful for producing a side effect for every item of a tree.\n"
).
-spec each(balanced_tree(FPZ, FQA), fun((FPZ, FQA) -> any())) -> nil.
each(Tree, Fun) ->
    _pipe = gb_trees:to_list(Tree),
    gleam@list:each(
        _pipe,
        fun(Kvp) -> Fun(erlang:element(1, Kvp), erlang:element(2, Kvp)) end
    ).

-file("src/balanced_tree.gleam", 138).
-spec filter(balanced_tree(FQE, FQF), fun((FQE, FQF) -> boolean())) -> balanced_tree(FQE, FQF).
filter(Tree, Predicate) ->
    _pipe = gb_trees:to_list(Tree),
    _pipe@1 = gleam@list:filter(
        _pipe,
        fun(Kvp) ->
            Predicate(erlang:element(1, Kvp), erlang:element(2, Kvp))
        end
    ),
    _pipe@2 = from_list(_pipe@1),
    gb_trees:balance(_pipe@2).

-file("src/balanced_tree.gleam", 122).
-spec drop(balanced_tree(FPS, FPT), list(FPS)) -> balanced_tree(FPS, FPT).
drop(Tree, Disallowed_keys) ->
    As_set = gleam@set:from_list(Disallowed_keys),
    filter(Tree, fun(K, _) -> gleam@set:contains(As_set, K) end).

-file("src/balanced_tree.gleam", 151).
?DOC(
    " Reduces a list of elements into a single value by calling a given function on each element, in order from min-key to max-key\n"
    "\n"
    " This function runs in linear time.\n"
).
-spec fold(balanced_tree(FQK, FQL), FQO, fun((FQO, FQK, FQL) -> FQO)) -> FQO.
fold(Tree, Initial, Fun) ->
    _pipe = gb_trees:to_list(Tree),
    gleam@list:fold(
        _pipe,
        Initial,
        fun(Acc, Kvp) ->
            Fun(Acc, erlang:element(1, Kvp), erlang:element(2, Kvp))
        end
    ).

-file("src/balanced_tree.gleam", 162).
?DOC(
    " Reduces a list of elements into a single value by calling a given function on each element, in order from max-key to min-key\n"
    "\n"
    " This function runs in linear time.\n"
).
-spec fold_right(balanced_tree(FQP, FQQ), FQT, fun((FQT, FQP, FQQ) -> FQT)) -> FQT.
fold_right(Tree, Initial, Fun) ->
    _pipe = gb_trees:to_list(Tree),
    _pipe@1 = lists:reverse(_pipe),
    gleam@list:fold(
        _pipe@1,
        Initial,
        fun(Acc, Kvp) ->
            Fun(Acc, erlang:element(1, Kvp), erlang:element(2, Kvp))
        end
    ).

-file("src/balanced_tree.gleam", 327).
-spec to_dict(balanced_tree(FVJ, FVK)) -> gleam@dict:dict(FVJ, FVK).
to_dict(Tree) ->
    _pipe = Tree,
    _pipe@1 = gb_trees:to_list(_pipe),
    maps:from_list(_pipe@1).

-file("src/balanced_tree.gleam", 278).
?DOC(
    " Creates a new tree from a pair of given trees by combining their entries.\n"
    "\n"
    " If there are entries with the same keys in both trees the entry from the second tree takes precedence.\n"
).
-spec merge(balanced_tree(FTY, FTZ), balanced_tree(FTY, FTZ)) -> balanced_tree(FTY, FTZ).
merge(Tree, New_entries) ->
    Tree_as_dict = to_dict(Tree),
    New_entries_as_dict = to_dict(New_entries),
    Merged = maps:merge(Tree_as_dict, New_entries_as_dict),
    from_dict(Merged).

-file("src/balanced_tree.gleam", 334).
?DOC(
    " Creates a new tree with one entry inserted or updated using a given function.\n"
    "\n"
    " If there was not an entry in the tree for the given key then the function gets None as its argument, otherwise it gets Some(value).\n"
).
-spec upsert(
    balanced_tree(FVP, FVQ),
    FVP,
    fun((gleam@option:option(FVQ)) -> FVQ)
) -> balanced_tree(FVP, FVQ).
upsert(Tree, Key, Fun) ->
    _pipe = gb_trees_shim:lookup_shim(Tree, Key),
    _pipe@1 = gleam@option:from_result(_pipe),
    _pipe@2 = Fun(_pipe@1),
    gb_trees:enter(Key, _pipe@2, Tree).

-file("src/balanced_tree.gleam", 95).
?DOC(
    " Creates a new tree from a pair of given frees by combining their entries.\n"
    "\n"
    " If there are entries with the same keys in both trees the given function is used to determine the new value to use in the resulting dict.\n"
).
-spec combine(
    balanced_tree(FPE, FPF),
    balanced_tree(FPE, FPF),
    fun((FPF, FPF) -> FPF)
) -> balanced_tree(FPE, FPF).
combine(Tree, Other, Fun) ->
    _pipe = Other,
    _pipe@1 = gb_trees:to_list(_pipe),
    gleam@list:fold(
        _pipe@1,
        Tree,
        fun(Acc, Kvp) ->
            upsert(
                Acc,
                erlang:element(1, Kvp),
                fun(Opt_value) -> case Opt_value of
                        none ->
                            erlang:element(2, Kvp);

                        {some, V} ->
                            Fun(V, erlang:element(2, Kvp))
                    end end
            )
        end
    ).

-file("src/balanced_tree.gleam", 349).
?DOC(
    " Gets a list of all values in a given tree.\n"
    " \n"
    " BalancedTrees are ordered. Values are guaranteed to be in min-to-max order based on their associated Keys.\n"
).
-spec values(balanced_tree(any(), FVX)) -> list(FVX).
values(Tree) ->
    gb_trees:values(Tree).