trove

-module(trove@internal@btree@range).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/trove/internal/btree/range.gleam").
-export(['query'/8]).

-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).

-file("src/trove/internal/btree/range.gleam", 51).
?DOC(false).
-spec fetch_or_panic(trove@internal@store:store(), integer(), binary()) -> bitstring().
fetch_or_panic(Store, Location, Label) ->
    case trove@internal@store:get_node(Store, Location) of
        {ok, D} ->
            D;

        {error, Reason} ->
            erlang:error(#{gleam_error => panic,
                    message => (<<<<<<<<<<"range query: "/utf8, Label/binary>>/binary,
                                    " read failed at offset "/utf8>>/binary,
                                (erlang:integer_to_binary(Location))/binary>>/binary,
                            ": "/utf8>>/binary,
                        (trove@internal@store:error_to_string(Reason))/binary>>),
                    file => <<?FILEPATH/utf8>>,
                    module => <<"trove/internal/btree/range"/utf8>>,
                    function => <<"fetch_or_panic"/utf8>>,
                    line => 55})
    end.

-file("src/trove/internal/btree/range.gleam", 156).
?DOC(false).
-spec order_children(list({JMZ, integer()}), trove@range:direction()) -> list({JMZ,
    integer()}).
order_children(Children, Direction) ->
    case Direction of
        forward ->
            Children;

        reverse ->
            lists:reverse(Children)
    end.

-file("src/trove/internal/btree/range.gleam", 177).
?DOC(false).
-spec do_prune_below_min(
    list({JNH, integer()}),
    trove@range:bound(JNH),
    fun((JNH, JNH) -> gleam@order:order())
) -> list({JNH, integer()}).
do_prune_below_min(Children, Min, Compare) ->
    Bound_key = case Min of
        {inclusive, K} ->
            K;

        {exclusive, K@1} ->
            K@1
    end,
    case Children of
        [] ->
            [];

        [_] ->
            Children;

        [_, Next | Rest] ->
            case Compare(erlang:element(1, Next), Bound_key) of
                gt ->
                    Children;

                lt ->
                    do_prune_below_min([Next | Rest], Min, Compare);

                eq ->
                    do_prune_below_min([Next | Rest], Min, Compare)
            end
    end.

-file("src/trove/internal/btree/range.gleam", 166).
?DOC(false).
-spec prune_below_min(
    list({JNC, integer()}),
    gleam@option:option(trove@range:bound(JNC)),
    fun((JNC, JNC) -> gleam@order:order())
) -> list({JNC, integer()}).
prune_below_min(Children, Min, Compare) ->
    case Min of
        none ->
            Children;

        {some, Bound} ->
            do_prune_below_min(Children, Bound, Compare)
    end.

-file("src/trove/internal/btree/range.gleam", 197).
?DOC(false).
-spec beyond_max(
    JNL,
    gleam@option:option(trove@range:bound(JNL)),
    fun((JNL, JNL) -> gleam@order:order())
) -> boolean().
beyond_max(Key, Max, Compare) ->
    case Max of
        none ->
            false;

        {some, {inclusive, Bound}} ->
            Compare(Key, Bound) =:= gt;

        {some, {exclusive, Bound@1}} ->
            Compare(Key, Bound@1) /= lt
    end.

-file("src/trove/internal/btree/range.gleam", 209).
?DOC(false).
-spec in_range(
    JNO,
    gleam@option:option(trove@range:bound(JNO)),
    gleam@option:option(trove@range:bound(JNO)),
    fun((JNO, JNO) -> gleam@order:order())
) -> boolean().
in_range(Key, Min, Max, Compare) ->
    Above_min = case Min of
        none ->
            true;

        {some, {inclusive, Bound_key}} ->
            Compare(Key, Bound_key) /= lt;

        {some, {exclusive, Bound_key@1}} ->
            Compare(Key, Bound_key@1) =:= gt
    end,
    Below_max = case Max of
        none ->
            true;

        {some, {inclusive, Bound_key@2}} ->
            Compare(Key, Bound_key@2) /= gt;

        {some, {exclusive, Bound_key@3}} ->
            Compare(Key, Bound_key@3) =:= lt
    end,
    Above_min andalso Below_max.

-file("src/trove/internal/btree/range.gleam", 99).
?DOC(false).
-spec traverse_leaf(
    trove@internal@store:store(),
    non_empty_list:non_empty_list({JMG, integer()}),
    trove@codec:codec(JMI),
    fun((JMG, JMG) -> gleam@order:order()),
    gleam@option:option(trove@range:bound(JMG)),
    gleam@option:option(trove@range:bound(JMG)),
    trove@range:direction()
) -> gleam@yielder:yielder({JMG, JMI}).
traverse_leaf(Store, Children, Value_codec, Compare, Min, Max, Direction) ->
    Ordered = order_children(non_empty_list:to_list(Children), Direction),
    _pipe = gleam@yielder:from_list(Ordered),
    _pipe@1 = gleam@yielder:filter(
        _pipe,
        fun(Entry) -> in_range(erlang:element(1, Entry), Min, Max, Compare) end
    ),
    gleam@yielder:filter_map(
        _pipe@1,
        fun(Entry@1) ->
            {Key, Data_loc} = Entry@1,
            Data = fetch_or_panic(Store, Data_loc, <<"data node"/utf8>>),
            case trove@internal@btree@node:decode_data_node(Data, Value_codec) of
                {ok, {value, Value}} ->
                    {ok, {Key, Value}};

                {ok, deleted} ->
                    {error, nil};

                {error, nil} ->
                    erlang:error(#{gleam_error => panic,
                            message => (<<"failed to decode data node during range query at offset "/utf8,
                                (erlang:integer_to_binary(Data_loc))/binary>>),
                            file => <<?FILEPATH/utf8>>,
                            module => <<"trove/internal/btree/range"/utf8>>,
                            function => <<"traverse_leaf"/utf8>>,
                            line => 118})
            end
        end
    ).

-file("src/trove/internal/btree/range.gleam", 234).
?DOC(false).
-spec bounds_are_empty(
    gleam@option:option(trove@range:bound(JNT)),
    gleam@option:option(trove@range:bound(JNT)),
    fun((JNT, JNT) -> gleam@order:order())
) -> boolean().
bounds_are_empty(Min, Max, Compare) ->
    case {Min, Max} of
        {{some, Min_bound}, {some, Max_bound}} ->
            Lo = case Min_bound of
                {inclusive, K} ->
                    K;

                {exclusive, K} ->
                    K
            end,
            Hi = case Max_bound of
                {inclusive, K@1} ->
                    K@1;

                {exclusive, K@1} ->
                    K@1
            end,
            case {Min_bound, Max_bound} of
                {{inclusive, _}, {inclusive, _}} ->
                    Compare(Lo, Hi) =:= gt;

                {_, _} ->
                    Compare(Lo, Hi) /= lt
            end;

        {none, _} ->
            false;

        {_, none} ->
            false
    end.

-file("src/trove/internal/btree/range.gleam", 126).
?DOC(false).
-spec traverse_branch(
    trove@internal@store:store(),
    non_empty_list:non_empty_list({JMP, integer()}),
    trove@codec:codec(JMP),
    trove@codec:codec(JMS),
    fun((JMP, JMP) -> gleam@order:order()),
    gleam@option:option(trove@range:bound(JMP)),
    gleam@option:option(trove@range:bound(JMP)),
    trove@range:direction()
) -> gleam@yielder:yielder({JMP, JMS}).
traverse_branch(
    Store,
    Children,
    Key_codec,
    Value_codec,
    Compare,
    Min,
    Max,
    Direction
) ->
    Pruned = begin
        _pipe = non_empty_list:to_list(Children),
        _pipe@1 = prune_below_min(_pipe, Min, Compare),
        gleam@list:take_while(
            _pipe@1,
            fun(Entry) ->
                not beyond_max(erlang:element(1, Entry), Max, Compare)
            end
        )
    end,
    Ordered = order_children(Pruned, Direction),
    _pipe@2 = gleam@yielder:from_list(Ordered),
    gleam@yielder:flat_map(
        _pipe@2,
        fun(Entry@1) ->
            traverse_node(
                Store,
                erlang:element(2, Entry@1),
                Key_codec,
                Value_codec,
                Compare,
                Min,
                Max,
                Direction
            )
        end
    ).

-file("src/trove/internal/btree/range.gleam", 66).
?DOC(false).
-spec traverse_node(
    trove@internal@store:store(),
    integer(),
    trove@codec:codec(JLX),
    trove@codec:codec(JLZ),
    fun((JLX, JLX) -> gleam@order:order()),
    gleam@option:option(trove@range:bound(JLX)),
    gleam@option:option(trove@range:bound(JLX)),
    trove@range:direction()
) -> gleam@yielder:yielder({JLX, JLZ}).
traverse_node(
    Store,
    Location,
    Key_codec,
    Value_codec,
    Compare,
    Min,
    Max,
    Direction
) ->
    Data = fetch_or_panic(Store, Location, <<"tree node"/utf8>>),
    case trove@internal@btree@node:decode_tree_node(Data, Key_codec) of
        {ok, {leaf, Children}} ->
            traverse_leaf(
                Store,
                Children,
                Value_codec,
                Compare,
                Min,
                Max,
                Direction
            );

        {ok, {branch, Children@1}} ->
            traverse_branch(
                Store,
                Children@1,
                Key_codec,
                Value_codec,
                Compare,
                Min,
                Max,
                Direction
            );

        {error, nil} ->
            erlang:error(#{gleam_error => panic,
                    message => (<<"failed to decode tree node during range query at offset "/utf8,
                        (erlang:integer_to_binary(Location))/binary>>),
                    file => <<?FILEPATH/utf8>>,
                    module => <<"trove/internal/btree/range"/utf8>>,
                    function => <<"traverse_node"/utf8>>,
                    line => 92})
    end.

-file("src/trove/internal/btree/range.gleam", 21).
?DOC(false).
-spec 'query'(
    trove@internal@btree:btree(JLM, JLN),
    trove@internal@store:store(),
    gleam@option:option(trove@range:bound(JLM)),
    gleam@option:option(trove@range:bound(JLM)),
    trove@range:direction(),
    trove@codec:codec(JLM),
    trove@codec:codec(JLN),
    fun((JLM, JLM) -> gleam@order:order())
) -> gleam@yielder:yielder({JLM, JLN}).
'query'(Tree, Store, Min, Max, Direction, Key_codec, Value_codec, Compare) ->
    gleam@bool:guard(
        bounds_are_empty(Min, Max, Compare),
        gleam@yielder:empty(),
        fun() -> case trove@internal@btree:root(Tree) of
                none ->
                    gleam@yielder:empty();

                {some, Location} ->
                    traverse_node(
                        Store,
                        Location,
                        Key_codec,
                        Value_codec,
                        Compare,
                        Min,
                        Max,
                        Direction
                    )
            end end
    ).