spatial

-module(spatial@bvh).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/spatial/bvh.gleam").
-export(['query'/2, query_radius/3, query_all/1, count/1, bounds/1, remove/2, refit/1, from_items/2, insert/4, update/5]).
-export_type([b_v_h/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(
    " Bounding Volume Hierarchy (BVH) for efficient spatial queries.\n"
    "\n"
    " BVH is a tree structure where each node contains a bounding box that\n"
    " encompasses all its children. Excellent for dynamic scenes and collision detection.\n"
).

-opaque b_v_h(KGJ) :: {b_v_h_leaf,
        spatial@collider:internal_collider(),
        list({vec@vec3:vec3(float()), KGJ})} |
    {b_v_h_node, spatial@collider:internal_collider(), b_v_h(KGJ), b_v_h(KGJ)}.

-file("src/spatial/bvh.gleam", 51).
-spec do_query(
    b_v_h(KGU),
    spatial@collider:internal_collider(),
    list({vec@vec3:vec3(float()), KGU})
) -> list({vec@vec3:vec3(float()), KGU}).
do_query(Bvh, Query_bounds, Acc) ->
    case Bvh of
        {b_v_h_leaf, Bounds, Items} ->
            case spatial@collider:intersects(Bounds, Query_bounds) of
                false ->
                    Acc;

                true ->
                    gleam@list:fold(
                        Items,
                        Acc,
                        fun(Acc_inner, Item_pair) ->
                            {Pos, _} = Item_pair,
                            case spatial@collider:contains_point(
                                Query_bounds,
                                Pos
                            ) of
                                true ->
                                    [Item_pair | Acc_inner];

                                false ->
                                    Acc_inner
                            end
                        end
                    )
            end;

        {b_v_h_node, Bounds@1, Left, Right} ->
            case spatial@collider:intersects(Bounds@1, Query_bounds) of
                false ->
                    Acc;

                true ->
                    _pipe = Acc,
                    _pipe@1 = do_query(Left, Query_bounds, _pipe),
                    do_query(Right, Query_bounds, _pipe@1)
            end
    end.

-file("src/spatial/bvh.gleam", 47).
?DOC(
    " Query all items within a collider region.\n"
    "\n"
    " **Time Complexity**: O(log n + k) average case where k is the number of results.\n"
    " Worst case O(n) if query region covers entire BVH.\n"
).
-spec 'query'(b_v_h(KGQ), spatial@collider:internal_collider()) -> list({vec@vec3:vec3(float()),
    KGQ}).
'query'(Bvh, Query_bounds) ->
    do_query(Bvh, Query_bounds, []).

-file("src/spatial/bvh.gleam", 88).
?DOC(
    " Query all items within a radius of a point.\n"
    "\n"
    " **Time Complexity**: O(log n + k) average case where k is the number of results.\n"
).
-spec query_radius(b_v_h(KHA), vec@vec3:vec3(float()), float()) -> list({vec@vec3:vec3(float()),
    KHA}).
query_radius(Bvh, Center, Radius) ->
    Half_extents = {vec3, Radius, Radius, Radius},
    Query_bounds = spatial@collider:box_from_center(Center, Half_extents),
    Radius_sq = Radius * Radius,
    _pipe = 'query'(Bvh, Query_bounds),
    gleam@list:filter(
        _pipe,
        fun(Item_pair) ->
            {Pos, _} = Item_pair,
            spatial_ffi:distance_squared(Center, Pos) =< Radius_sq
        end
    ).

-file("src/spatial/bvh.gleam", 112).
-spec do_query_all(b_v_h(KHJ), list({vec@vec3:vec3(float()), KHJ})) -> list({vec@vec3:vec3(float()),
    KHJ}).
do_query_all(Bvh, Acc) ->
    case Bvh of
        {b_v_h_leaf, _, Items} ->
            gleam@list:fold(
                Items,
                Acc,
                fun(Acc_inner, Item) -> [Item | Acc_inner] end
            );

        {b_v_h_node, _, Left, Right} ->
            _pipe = Acc,
            _pipe@1 = do_query_all(Left, _pipe),
            do_query_all(Right, _pipe@1)
    end.

-file("src/spatial/bvh.gleam", 108).
?DOC(
    " Query all items in the BVH.\n"
    "\n"
    " **Time Complexity**: O(n) where n is the total number of items.\n"
).
-spec query_all(b_v_h(KHF)) -> list({vec@vec3:vec3(float()), KHF}).
query_all(Bvh) ->
    do_query_all(Bvh, []).

-file("src/spatial/bvh.gleam", 132).
?DOC(
    " Count total items in the BVH.\n"
    "\n"
    " **Time Complexity**: O(n) where n is the total number of items.\n"
).
-spec count(b_v_h(any())) -> integer().
count(Bvh) ->
    _pipe = query_all(Bvh),
    erlang:length(_pipe).

-file("src/spatial/bvh.gleam", 138).
?DOC(" Get the root bounds of the BVH.\n").
-spec bounds(b_v_h(any())) -> spatial@collider:internal_collider().
bounds(Bvh) ->
    case Bvh of
        {b_v_h_leaf, Bounds, _} ->
            Bounds;

        {b_v_h_node, Bounds@1, _, _} ->
            Bounds@1
    end.

-file("src/spatial/bvh.gleam", 350).
-spec compute_bounds(list({vec@vec3:vec3(float()), any()})) -> spatial@collider:internal_collider().
compute_bounds(Items) ->
    Positions = gleam@list:map(Items, fun(Item) -> erlang:element(1, Item) end),
    {Min, Max} = spatial_ffi:compute_bounds(Positions),
    Padding = 0.01,
    spatial@collider:box(
        {vec3,
            erlang:element(2, Min) - Padding,
            erlang:element(3, Min) - Padding,
            erlang:element(4, Min) - Padding},
        {vec3,
            erlang:element(2, Max) + Padding,
            erlang:element(3, Max) + Padding,
            erlang:element(4, Max) + Padding}
    ).

-file("src/spatial/bvh.gleam", 364).
-spec merge_bounds(
    spatial@collider:internal_collider(),
    spatial@collider:internal_collider()
) -> spatial@collider:internal_collider().
merge_bounds(A, B) ->
    {Min_a@1, Max_a@1} = case A of
        {box, Min_a, Max_a} -> {Min_a, Max_a};
        _assert_fail ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        file => <<?FILEPATH/utf8>>,
                        module => <<"spatial/bvh"/utf8>>,
                        function => <<"merge_bounds"/utf8>>,
                        line => 365,
                        value => _assert_fail,
                        start => 10892,
                        'end' => 10933,
                        pattern_start => 10903,
                        pattern_end => 10929})
    end,
    {Min_b@1, Max_b@1} = case B of
        {box, Min_b, Max_b} -> {Min_b, Max_b};
        _assert_fail@1 ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        file => <<?FILEPATH/utf8>>,
                        module => <<"spatial/bvh"/utf8>>,
                        function => <<"merge_bounds"/utf8>>,
                        line => 366,
                        value => _assert_fail@1,
                        start => 10936,
                        'end' => 10977,
                        pattern_start => 10947,
                        pattern_end => 10973})
    end,
    {Min, Max} = spatial_ffi:merge_bounds(Min_a@1, Max_a@1, Min_b@1, Max_b@1),
    spatial@collider:box(Min, Max).

-file("src/spatial/bvh.gleam", 228).
-spec do_remove(b_v_h(KIG), fun((KIG) -> boolean())) -> {ok, b_v_h(KIG)} |
    {error, nil}.
do_remove(Bvh, Predicate) ->
    case Bvh of
        {b_v_h_leaf, _, Items} ->
            New_items = gleam@list:filter(
                Items,
                fun(Item_pair) ->
                    {_, Item} = Item_pair,
                    not Predicate(Item)
                end
            ),
            case New_items of
                [] ->
                    {error, nil};

                _ ->
                    case erlang:length(New_items) =:= erlang:length(Items) of
                        true ->
                            {error, nil};

                        false ->
                            New_bounds = compute_bounds(New_items),
                            {ok, {b_v_h_leaf, New_bounds, New_items}}
                    end
            end;

        {b_v_h_node, _, Left, Right} ->
            case do_remove(Left, Predicate) of
                {ok, New_left} ->
                    New_bounds@1 = merge_bounds(bounds(New_left), bounds(Right)),
                    {ok, {b_v_h_node, New_bounds@1, New_left, Right}};

                {error, nil} ->
                    case do_remove(Right, Predicate) of
                        {ok, New_right} ->
                            New_bounds@2 = merge_bounds(
                                bounds(Left),
                                bounds(New_right)
                            ),
                            {ok, {b_v_h_node, New_bounds@2, Left, New_right}};

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

-file("src/spatial/bvh.gleam", 224).
?DOC(
    " Remove an item from the BVH by comparing values using equality.\n"
    "\n"
    " Returns a new BVH with the item removed, or the original BVH if not found.\n"
    "\n"
    " **Time Complexity**: O(n) worst case (must search all leaves).\n"
    "\n"
    " ## Example\n"
    " ```gleam\n"
    " let bvh = bvh.from_items([...], max_leaf_size: 4)\n"
    " let updated_bvh = bvh.remove(bvh, fn(item) { item == \"item_to_remove\" })\n"
    " ```\n"
).
-spec remove(b_v_h(KIB), fun((KIB) -> boolean())) -> {ok, b_v_h(KIB)} |
    {error, nil}.
remove(Bvh, Predicate) ->
    do_remove(Bvh, Predicate).

-file("src/spatial/bvh.gleam", 317).
?DOC(
    " Refit the BVH bounds after items have been modified.\n"
    "\n"
    " This is cheaper than rebuilding but doesn't optimize the tree structure.\n"
    " Use this when items haven't moved much, or rebuild when structure degrades.\n"
    "\n"
    " **Time Complexity**: O(n) where n is the number of nodes.\n"
    "\n"
    " ## Example\n"
    " ```gleam\n"
    " let refitted_bvh = bvh.refit(bvh)\n"
    " ```\n"
).
-spec refit(b_v_h(KIR)) -> b_v_h(KIR).
refit(Bvh) ->
    case Bvh of
        {b_v_h_leaf, _, Items} ->
            New_bounds = compute_bounds(Items),
            {b_v_h_leaf, New_bounds, Items};

        {b_v_h_node, _, Left, Right} ->
            New_left = refit(Left),
            New_right = refit(Right),
            New_bounds@1 = merge_bounds(bounds(New_left), bounds(New_right)),
            {b_v_h_node, New_bounds@1, New_left, New_right}
    end.

-file("src/spatial/bvh.gleam", 373).
-spec split_items(list({vec@vec3:vec3(float()), KJC})) -> {list({vec@vec3:vec3(float()),
        KJC}),
    list({vec@vec3:vec3(float()), KJC})}.
split_items(Items) ->
    Bounds = compute_bounds(Items),
    Center = spatial@collider:center(Bounds),
    Size = spatial@collider:size(Bounds),
    Axis = case (erlang:element(2, Size) >= erlang:element(3, Size)) andalso (erlang:element(
        2,
        Size
    )
    >= erlang:element(4, Size)) of
        true ->
            0;

        false ->
            case erlang:element(3, Size) >= erlang:element(4, Size) of
                true ->
                    1;

                false ->
                    2
            end
    end,
    {Left, Right} = gleam@list:partition(
        Items,
        fun(Item) ->
            {Pos, _} = Item,
            case Axis of
                0 ->
                    erlang:element(2, Pos) < erlang:element(2, Center);

                1 ->
                    erlang:element(3, Pos) < erlang:element(3, Center);

                _ ->
                    erlang:element(4, Pos) < erlang:element(4, Center)
            end
        end
    ),
    case {Left, Right} of
        {[], _} ->
            Mid = erlang:length(Items) div 2,
            {gleam@list:take(Items, Mid), gleam@list:drop(Items, Mid)};

        {_, []} ->
            Mid = erlang:length(Items) div 2,
            {gleam@list:take(Items, Mid), gleam@list:drop(Items, Mid)};

        {_, _} ->
            {Left, Right}
    end.

-file("src/spatial/bvh.gleam", 334).
-spec build_bvh(list({vec@vec3:vec3(float()), KIV}), integer()) -> b_v_h(KIV).
build_bvh(Items, Max_leaf_size) ->
    case erlang:length(Items) =< Max_leaf_size of
        true ->
            Bounds = compute_bounds(Items),
            {b_v_h_leaf, Bounds, Items};

        false ->
            {Left_items, Right_items} = split_items(Items),
            Left = build_bvh(Left_items, Max_leaf_size),
            Right = build_bvh(Right_items, Max_leaf_size),
            Bounds@1 = merge_bounds(bounds(Left), bounds(Right)),
            {b_v_h_node, Bounds@1, Left, Right}
    end.

-file("src/spatial/bvh.gleam", 33).
?DOC(
    " Create a new BVH from a list of positioned items.\n"
    "\n"
    " Uses Surface Area Heuristic (SAH) for optimal splits.\n"
    "\n"
    " **Time Complexity**: O(n log n) where n is the number of items.\n"
    "\n"
    " ## Example\n"
    " ```gleam\n"
    " let items = [\n"
    "   #(vec3.Vec3(0.0, 0.0, 0.0), \"item1\"),\n"
    "   #(vec3.Vec3(10.0, 0.0, 0.0), \"item2\"),\n"
    " ]\n"
    " let bvh = bvh.from_items(items, max_leaf_size: 4)\n"
    " ```\n"
).
-spec from_items(list({vec@vec3:vec3(float()), KGL}), integer()) -> {ok,
        b_v_h(KGL)} |
    {error, nil}.
from_items(Items, Max_leaf_size) ->
    case Items of
        [] ->
            {error, nil};

        _ ->
            {ok, build_bvh(Items, Max_leaf_size)}
    end.

-file("src/spatial/bvh.gleam", 411).
-spec expand_bounds(
    spatial@collider:internal_collider(),
    vec@vec3:vec3(float())
) -> spatial@collider:internal_collider().
expand_bounds(Bounds, Point) ->
    {Min@1, Max@1} = case Bounds of
        {box, Min, Max} -> {Min, Max};
        _assert_fail ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        file => <<?FILEPATH/utf8>>,
                        module => <<"spatial/bvh"/utf8>>,
                        function => <<"expand_bounds"/utf8>>,
                        line => 412,
                        value => _assert_fail,
                        start => 12100,
                        'end' => 12142,
                        pattern_start => 12111,
                        pattern_end => 12133})
    end,
    New_min = {vec3, case erlang:element(2, Point) < erlang:element(2, Min@1) of
            true ->
                erlang:element(2, Point);

            false ->
                erlang:element(2, Min@1)
        end, case erlang:element(3, Point) < erlang:element(3, Min@1) of
            true ->
                erlang:element(3, Point);

            false ->
                erlang:element(3, Min@1)
        end, case erlang:element(4, Point) < erlang:element(4, Min@1) of
            true ->
                erlang:element(4, Point);

            false ->
                erlang:element(4, Min@1)
        end},
    New_max = {vec3, case erlang:element(2, Point) > erlang:element(2, Max@1) of
            true ->
                erlang:element(2, Point);

            false ->
                erlang:element(2, Max@1)
        end, case erlang:element(3, Point) > erlang:element(3, Max@1) of
            true ->
                erlang:element(3, Point);

            false ->
                erlang:element(3, Max@1)
        end, case erlang:element(4, Point) > erlang:element(4, Max@1) of
            true ->
                erlang:element(4, Point);

            false ->
                erlang:element(4, Max@1)
        end},
    Padding = 0.01,
    spatial@collider:box(
        {vec3,
            erlang:element(2, New_min) - Padding,
            erlang:element(3, New_min) - Padding,
            erlang:element(4, New_min) - Padding},
        {vec3,
            erlang:element(2, New_max) + Padding,
            erlang:element(3, New_max) + Padding,
            erlang:element(4, New_max) + Padding}
    ).

-file("src/spatial/bvh.gleam", 462).
-spec surface_area(spatial@collider:internal_collider()) -> float().
surface_area(Bounds) ->
    Size = spatial@collider:size(Bounds),
    2.0 * (((erlang:element(2, Size) * erlang:element(3, Size)) + (erlang:element(
        2,
        Size
    )
    * erlang:element(4, Size)))
    + (erlang:element(3, Size) * erlang:element(4, Size))).

-file("src/spatial/bvh.gleam", 166).
-spec do_insert(b_v_h(KHX), {vec@vec3:vec3(float()), KHX}, integer()) -> b_v_h(KHX).
do_insert(Bvh, Item, Max_leaf_size) ->
    case Bvh of
        {b_v_h_leaf, Leaf_bounds, Items} ->
            New_items = [Item | Items],
            case erlang:length(New_items) =< Max_leaf_size of
                true ->
                    New_bounds = expand_bounds(
                        Leaf_bounds,
                        erlang:element(1, Item)
                    ),
                    {b_v_h_leaf, New_bounds, New_items};

                false ->
                    {Left_items, Right_items} = split_items(New_items),
                    Left = build_bvh(Left_items, Max_leaf_size),
                    Right = build_bvh(Right_items, Max_leaf_size),
                    New_bounds@1 = merge_bounds(bounds(Left), bounds(Right)),
                    {b_v_h_node, New_bounds@1, Left, Right}
            end;

        {b_v_h_node, _, Left@1, Right@1} ->
            Left_bounds = bounds(Left@1),
            Right_bounds = bounds(Right@1),
            Left_expanded = expand_bounds(Left_bounds, erlang:element(1, Item)),
            Right_expanded = expand_bounds(
                Right_bounds,
                erlang:element(1, Item)
            ),
            Left_cost = surface_area(Left_expanded),
            Right_cost = surface_area(Right_expanded),
            case Left_cost =< Right_cost of
                true ->
                    New_left = do_insert(Left@1, Item, Max_leaf_size),
                    New_bounds@2 = merge_bounds(bounds(New_left), Right_bounds),
                    {b_v_h_node, New_bounds@2, New_left, Right@1};

                false ->
                    New_right = do_insert(Right@1, Item, Max_leaf_size),
                    New_bounds@3 = merge_bounds(Left_bounds, bounds(New_right)),
                    {b_v_h_node, New_bounds@3, Left@1, New_right}
            end
    end.

-file("src/spatial/bvh.gleam", 157).
?DOC(
    " Insert a new item into the BVH.\n"
    "\n"
    " Uses Surface Area Heuristic (SAH) to find the best insertion point.\n"
    " Returns a new BVH with the item inserted.\n"
    "\n"
    " **Time Complexity**: O(log n) average case.\n"
    "\n"
    " ## Example\n"
    " ```gleam\n"
    " let bvh = bvh.from_items([#(vec3.Vec3(0.0, 0.0, 0.0), \"item1\")], max_leaf_size: 4)\n"
    " let updated_bvh = bvh.insert(bvh, vec3.Vec3(1.0, 0.0, 0.0), \"item2\", max_leaf_size: 4)\n"
    " ```\n"
).
-spec insert(b_v_h(KHT), vec@vec3:vec3(float()), KHT, integer()) -> b_v_h(KHT).
insert(Bvh, Position, Item, Max_leaf_size) ->
    do_insert(Bvh, {Position, Item}, Max_leaf_size).

-file("src/spatial/bvh.gleam", 292).
?DOC(
    " Update an item's position in the BVH.\n"
    "\n"
    " This is equivalent to removing the old item and inserting it at the new position.\n"
    "\n"
    " **Time Complexity**: O(n + log n) = O(n) due to removal requiring search.\n"
    "\n"
    " ## Example\n"
    " ```gleam\n"
    " let bvh = bvh.from_items([...], max_leaf_size: 4)\n"
    " let updated_bvh = bvh.update(\n"
    "   bvh,\n"
    "   fn(item) { item.id == target_id },\n"
    "   new_position,\n"
    "   updated_item,\n"
    "   max_leaf_size: 4\n"
    " )\n"
    " ```\n"
).
-spec update(
    b_v_h(KIL),
    fun((KIL) -> boolean()),
    vec@vec3:vec3(float()),
    KIL,
    integer()
) -> {ok, b_v_h(KIL)} | {error, nil}.
update(Bvh, Predicate, New_position, New_item, Max_leaf_size) ->
    case remove(Bvh, Predicate) of
        {ok, Bvh_after_remove} ->
            {ok,
                insert(Bvh_after_remove, New_position, New_item, Max_leaf_size)};

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