-module(spatial@octree).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/spatial/octree.gleam").
-export([new/2, 'query'/2, query_radius/3, query_all/1, count/1, bounds/1, remove/3, insert/3]).
-export_type([octree/1, octree_children/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(
    " Octree spatial partitioning data structure.\n"
    "\n"
    " An octree divides 3D space into 8 octants recursively, enabling efficient\n"
    " spatial queries for nearby objects.\n"
).

-opaque octree(KXQ) :: {octree_node,
        spatial@collider:internal_collider(),
        integer(),
        list({vec@vec3:vec3(float()), KXQ}),
        gleam@option:option(octree_children(KXQ))}.

-type octree_children(KXR) :: {octree_children,
        octree(KXR),
        octree(KXR),
        octree(KXR),
        octree(KXR),
        octree(KXR),
        octree(KXR),
        octree(KXR),
        octree(KXR)}.

-file("src/spatial/octree.gleam", 54).
?DOC(
    " Create a new empty octree.\n"
    "\n"
    " ## Parameters\n"
    " - `bounds`: The spatial region this octree covers (must be a Box)\n"
    " - `capacity`: Maximum items per node before subdividing (typically 8-16)\n"
    "\n"
    " ## Example\n"
    " ```gleam\n"
    " let bounds = collider.box(\n"
    "   min: vec3.Vec3(-100.0, -100.0, -100.0),\n"
    "   max: vec3.Vec3(100.0, 100.0, 100.0),\n"
    " )\n"
    " let tree = octree.new(bounds, capacity: 8)\n"
    " ```\n"
).
-spec new(spatial@collider:internal_collider(), integer()) -> octree(any()).
new(Bounds, Capacity) ->
    {octree_node, Bounds, Capacity, [], none}.

-file("src/spatial/octree.gleam", 147).
-spec do_query(
    octree(KYG),
    spatial@collider:internal_collider(),
    list({vec@vec3:vec3(float()), KYG})
) -> list({vec@vec3:vec3(float()), KYG}).
do_query(Tree, Query_bounds, Acc) ->
    case Tree of
        {octree_node, Bounds, _, Items, Children} ->
            case spatial@collider:intersects(Bounds, Query_bounds) of
                false ->
                    Acc;

                true ->
                    Acc@1 = 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
                    ),
                    case Children of
                        none ->
                            Acc@1;

                        {some,
                            {octree_children,
                                Bottom_nw,
                                Bottom_ne,
                                Bottom_sw,
                                Bottom_se,
                                Top_nw,
                                Top_ne,
                                Top_sw,
                                Top_se}} ->
                            _pipe = Acc@1,
                            _pipe@1 = do_query(Bottom_nw, Query_bounds, _pipe),
                            _pipe@2 = do_query(Bottom_ne, Query_bounds, _pipe@1),
                            _pipe@3 = do_query(Bottom_sw, Query_bounds, _pipe@2),
                            _pipe@4 = do_query(Bottom_se, Query_bounds, _pipe@3),
                            _pipe@5 = do_query(Top_nw, Query_bounds, _pipe@4),
                            _pipe@6 = do_query(Top_ne, Query_bounds, _pipe@5),
                            _pipe@7 = do_query(Top_sw, Query_bounds, _pipe@6),
                            do_query(Top_se, Query_bounds, _pipe@7)
                    end
            end
    end.

-file("src/spatial/octree.gleam", 143).
?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 tree.\n"
).
-spec 'query'(octree(KYC), spatial@collider:internal_collider()) -> list({vec@vec3:vec3(float()),
    KYC}).
'query'(Tree, Query_bounds) ->
    do_query(Tree, Query_bounds, []).

-file("src/spatial/octree.gleam", 199).
?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(octree(KYM), vec@vec3:vec3(float()), float()) -> list({vec@vec3:vec3(float()),
    KYM}).
query_radius(Tree, Center, Radius) ->
    Half_extents = {vec3, Radius, Radius, Radius},
    Query_bounds = spatial@collider:box_from_center(Center, Half_extents),
    Radius_sq = Radius * Radius,
    _pipe = 'query'(Tree, Query_bounds),
    gleam@list:filter(
        _pipe,
        fun(Item_pair) ->
            {Pos, _} = Item_pair,
            spatial_ffi:distance_squared(Center, Pos) =< Radius_sq
        end
    ).

-file("src/spatial/octree.gleam", 224).
-spec do_query_all(octree(KYV), list({vec@vec3:vec3(float()), KYV})) -> list({vec@vec3:vec3(float()),
    KYV}).
do_query_all(Tree, Acc) ->
    case Tree of
        {octree_node, _, _, Items, Children} ->
            Acc@1 = gleam@list:fold(
                Items,
                Acc,
                fun(Acc_inner, Item) -> [Item | Acc_inner] end
            ),
            case Children of
                none ->
                    Acc@1;

                {some,
                    {octree_children,
                        Bottom_nw,
                        Bottom_ne,
                        Bottom_sw,
                        Bottom_se,
                        Top_nw,
                        Top_ne,
                        Top_sw,
                        Top_se}} ->
                    _pipe = Acc@1,
                    _pipe@1 = do_query_all(Bottom_nw, _pipe),
                    _pipe@2 = do_query_all(Bottom_ne, _pipe@1),
                    _pipe@3 = do_query_all(Bottom_sw, _pipe@2),
                    _pipe@4 = do_query_all(Bottom_se, _pipe@3),
                    _pipe@5 = do_query_all(Top_nw, _pipe@4),
                    _pipe@6 = do_query_all(Top_ne, _pipe@5),
                    _pipe@7 = do_query_all(Top_sw, _pipe@6),
                    do_query_all(Top_se, _pipe@7)
            end
    end.

-file("src/spatial/octree.gleam", 220).
?DOC(
    " Query all items in the octree (useful for iteration).\n"
    "\n"
    " **Time Complexity**: O(n) where n is the total number of items.\n"
).
-spec query_all(octree(KYR)) -> list({vec@vec3:vec3(float()), KYR}).
query_all(Tree) ->
    do_query_all(Tree, []).

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

-file("src/spatial/octree.gleam", 269).
?DOC(" Get the bounds of the octree.\n").
-spec bounds(octree(any())) -> spatial@collider:internal_collider().
bounds(Tree) ->
    case Tree of
        {octree_node, Bounds, _, _, _} ->
            Bounds
    end.

-file("src/spatial/octree.gleam", 277).
-spec subdivide(octree(KZF)) -> octree(KZF).
subdivide(Tree) ->
    case Tree of
        {octree_node, Bounds, Capacity, _, _} ->
            {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/octree"/utf8>>,
                                function => <<"subdivide"/utf8>>,
                                line => 281,
                                value => _assert_fail,
                                start => 8401,
                                'end' => 8443,
                                pattern_start => 8412,
                                pattern_end => 8434})
            end,
            Center = spatial@collider:center(Bounds),
            Bottom_nw = new(
                {box,
                    Min@1,
                    {vec3,
                        erlang:element(2, Center),
                        erlang:element(3, Center),
                        erlang:element(4, Center)}},
                Capacity
            ),
            Bottom_ne = new(
                {box,
                    {vec3,
                        erlang:element(2, Center),
                        erlang:element(3, Min@1),
                        erlang:element(4, Min@1)},
                    {vec3,
                        erlang:element(2, Max@1),
                        erlang:element(3, Center),
                        erlang:element(4, Center)}},
                Capacity
            ),
            Bottom_sw = new(
                {box,
                    {vec3,
                        erlang:element(2, Min@1),
                        erlang:element(3, Min@1),
                        erlang:element(4, Center)},
                    {vec3,
                        erlang:element(2, Center),
                        erlang:element(3, Center),
                        erlang:element(4, Max@1)}},
                Capacity
            ),
            Bottom_se = new(
                {box,
                    {vec3,
                        erlang:element(2, Center),
                        erlang:element(3, Min@1),
                        erlang:element(4, Center)},
                    {vec3,
                        erlang:element(2, Max@1),
                        erlang:element(3, Center),
                        erlang:element(4, Max@1)}},
                Capacity
            ),
            Top_nw = new(
                {box,
                    {vec3,
                        erlang:element(2, Min@1),
                        erlang:element(3, Center),
                        erlang:element(4, Min@1)},
                    {vec3,
                        erlang:element(2, Center),
                        erlang:element(3, Max@1),
                        erlang:element(4, Center)}},
                Capacity
            ),
            Top_ne = new(
                {box,
                    {vec3,
                        erlang:element(2, Center),
                        erlang:element(3, Center),
                        erlang:element(4, Min@1)},
                    {vec3,
                        erlang:element(2, Max@1),
                        erlang:element(3, Max@1),
                        erlang:element(4, Center)}},
                Capacity
            ),
            Top_sw = new(
                {box,
                    {vec3,
                        erlang:element(2, Min@1),
                        erlang:element(3, Center),
                        erlang:element(4, Center)},
                    {vec3,
                        erlang:element(2, Center),
                        erlang:element(3, Max@1),
                        erlang:element(4, Max@1)}},
                Capacity
            ),
            Top_se = new({box, Center, Max@1}, Capacity),
            {octree_node,
                Bounds,
                Capacity,
                [],
                {some,
                    {octree_children,
                        Bottom_nw,
                        Bottom_ne,
                        Bottom_sw,
                        Bottom_se,
                        Top_nw,
                        Top_ne,
                        Top_sw,
                        Top_se}}}
    end.

-file("src/spatial/octree.gleam", 416).
-spec remove_from_child(
    spatial@collider:internal_collider(),
    octree_children(KZM),
    vec@vec3:vec3(float()),
    fun((KZM) -> boolean())
) -> octree_children(KZM).
remove_from_child(_, Children, Position, Predicate) ->
    case Children of
        {octree_children,
            Bottom_nw,
            Bottom_ne,
            Bottom_sw,
            Bottom_se,
            Top_nw,
            Top_ne,
            Top_sw,
            Top_se} ->
            {octree_children,
                remove(Bottom_nw, Position, Predicate),
                remove(Bottom_ne, Position, Predicate),
                remove(Bottom_sw, Position, Predicate),
                remove(Bottom_se, Position, Predicate),
                remove(Top_nw, Position, Predicate),
                remove(Top_ne, Position, Predicate),
                remove(Top_sw, Position, Predicate),
                remove(Top_se, Position, Predicate)}
    end.

-file("src/spatial/octree.gleam", 106).
?DOC(
    " Remove an item from the octree.\n"
    "\n"
    " Removes the first occurrence of an item at the given position.\n"
    "\n"
    " **Time Complexity**: O(n) worst case as it recursively checks all nodes, \n"
    " but typically O(h) where h is the tree height for sparse trees.\n"
).
-spec remove(octree(KXY), vec@vec3:vec3(float()), fun((KXY) -> boolean())) -> octree(KXY).
remove(Tree, Position, Predicate) ->
    case Tree of
        {octree_node, Bounds, _, Items, Children} ->
            case spatial@collider:contains_point(Bounds, Position) of
                false ->
                    Tree;

                true ->
                    New_items = gleam@list:filter(
                        Items,
                        fun(Item_pair) ->
                            {Pos, Item} = Item_pair,
                            Is_at_position = vec@vec3f:distance(Pos, Position) < 0.0001,
                            Matches_predicate = Predicate(Item),
                            not (Is_at_position andalso Matches_predicate)
                        end
                    ),
                    New_children = case Children of
                        none ->
                            none;

                        {some, Octants} ->
                            {some,
                                remove_from_child(
                                    Bounds,
                                    Octants,
                                    Position,
                                    Predicate
                                )}
                    end,
                    {octree_node,
                        erlang:element(2, Tree),
                        erlang:element(3, Tree),
                        New_items,
                        New_children}
            end
    end.

-file("src/spatial/octree.gleam", 359).
-spec insert_into_child(
    spatial@collider:internal_collider(),
    octree_children(KZI),
    vec@vec3:vec3(float()),
    KZI
) -> octree_children(KZI).
insert_into_child(Parent_bounds, Children, Position, Item) ->
    case Children of
        {octree_children,
            Bottom_nw,
            Bottom_ne,
            Bottom_sw,
            Bottom_se,
            Top_nw,
            Top_ne,
            Top_sw,
            Top_se} ->
            Center = spatial@collider:center(Parent_bounds),
            case {erlang:element(2, Position) < erlang:element(2, Center),
                erlang:element(3, Position) < erlang:element(3, Center),
                erlang:element(4, Position) < erlang:element(4, Center)} of
                {true, true, true} ->
                    {octree_children,
                        insert(Bottom_nw, Position, Item),
                        erlang:element(3, Children),
                        erlang:element(4, Children),
                        erlang:element(5, Children),
                        erlang:element(6, Children),
                        erlang:element(7, Children),
                        erlang:element(8, Children),
                        erlang:element(9, Children)};

                {false, true, true} ->
                    {octree_children,
                        erlang:element(2, Children),
                        insert(Bottom_ne, Position, Item),
                        erlang:element(4, Children),
                        erlang:element(5, Children),
                        erlang:element(6, Children),
                        erlang:element(7, Children),
                        erlang:element(8, Children),
                        erlang:element(9, Children)};

                {true, true, false} ->
                    {octree_children,
                        erlang:element(2, Children),
                        erlang:element(3, Children),
                        insert(Bottom_sw, Position, Item),
                        erlang:element(5, Children),
                        erlang:element(6, Children),
                        erlang:element(7, Children),
                        erlang:element(8, Children),
                        erlang:element(9, Children)};

                {false, true, false} ->
                    {octree_children,
                        erlang:element(2, Children),
                        erlang:element(3, Children),
                        erlang:element(4, Children),
                        insert(Bottom_se, Position, Item),
                        erlang:element(6, Children),
                        erlang:element(7, Children),
                        erlang:element(8, Children),
                        erlang:element(9, Children)};

                {true, false, true} ->
                    {octree_children,
                        erlang:element(2, Children),
                        erlang:element(3, Children),
                        erlang:element(4, Children),
                        erlang:element(5, Children),
                        insert(Top_nw, Position, Item),
                        erlang:element(7, Children),
                        erlang:element(8, Children),
                        erlang:element(9, Children)};

                {false, false, true} ->
                    {octree_children,
                        erlang:element(2, Children),
                        erlang:element(3, Children),
                        erlang:element(4, Children),
                        erlang:element(5, Children),
                        erlang:element(6, Children),
                        insert(Top_ne, Position, Item),
                        erlang:element(8, Children),
                        erlang:element(9, Children)};

                {true, false, false} ->
                    {octree_children,
                        erlang:element(2, Children),
                        erlang:element(3, Children),
                        erlang:element(4, Children),
                        erlang:element(5, Children),
                        erlang:element(6, Children),
                        erlang:element(7, Children),
                        insert(Top_sw, Position, Item),
                        erlang:element(9, Children)};

                {false, false, false} ->
                    {octree_children,
                        erlang:element(2, Children),
                        erlang:element(3, Children),
                        erlang:element(4, Children),
                        erlang:element(5, Children),
                        erlang:element(6, Children),
                        erlang:element(7, Children),
                        erlang:element(8, Children),
                        insert(Top_se, Position, Item)}
            end
    end.

-file("src/spatial/octree.gleam", 62).
?DOC(
    " Insert an item at a position into the octree.\n"
    "\n"
    " **Time Complexity**: O(h + c) where h is the tree height (typically O(log n)) \n"
    " and c is the node capacity when subdivision occurs. Average case O(log n).\n"
).
-spec insert(octree(KXU), vec@vec3:vec3(float()), KXU) -> octree(KXU).
insert(Tree, Position, Item) ->
    case Tree of
        {octree_node, Bounds, Capacity, Items, Children} ->
            case spatial@collider:contains_point(Bounds, Position) of
                false ->
                    Tree;

                true ->
                    case Children of
                        none ->
                            New_items = [{Position, Item} | Items],
                            case erlang:length(New_items) > Capacity of
                                false ->
                                    {octree_node,
                                        erlang:element(2, Tree),
                                        erlang:element(3, Tree),
                                        New_items,
                                        erlang:element(5, Tree)};

                                true ->
                                    Subdivided = subdivide(Tree),
                                    gleam@list:fold(
                                        New_items,
                                        Subdivided,
                                        fun(Acc, Item_pair) ->
                                            {Pos, It} = Item_pair,
                                            insert(Acc, Pos, It)
                                        end
                                    )
                            end;

                        {some, Octants} ->
                            New_children = insert_into_child(
                                Bounds,
                                Octants,
                                Position,
                                Item
                            ),
                            {octree_node,
                                erlang:element(2, Tree),
                                erlang:element(3, Tree),
                                erlang:element(4, Tree),
                                {some, New_children}}
                    end
            end
    end.