local X=game:GetService("\082\101\112\108\105\099\097\116\101\100\083\116\111\114\097\103\101")local function I(X,I,d)return(X-I).Magnitude<=d end local d={Vector3.new(-1000000.0,-1000000.0,-1000000.0);Vector3.new(1000000.0,1000000.0,1000000.0)}return function()local T=require(X.Objects.Shared.Octree)local Q={Vector3.new(0,0,0);Vector3.new(1,1,1),Vector3.new(1,2,1),Vector3.new(1,1,3),Vector3.new(1.5,11,1);Vector3.new(1,-200,1)}describe("\105\110\115\101\114\116",function()it("\115\104\111\117\108\100 \105\110\115\101\114\116 \099\111\111\114\100\115",function()local X=T.new(unpack(d))for I,d in ipairs(Q)do X:Insert(d,d);(expect(X:GetSize())).to.equal(I);(expect(X._dataToLeaf[d])).to.be.ok()end end)it("\115\104\111\117\108\100 \098\101 \097\098\108\101 \116\111 \102\105\110\100 \099\111\111\114\100\115",function()local X=T.new(unpack(d))for I,d in ipairs(Q)do X:Insert(d,d)local T,Q=X:GetNearestNeighbor(d);(expect(T)).to.equal(d)end end)end)describe("\100\101\108\101\116\101",function()it("\115\104\111\117\108\100 \100\101\108\101\116\101 \099\111\111\114\100\115",function()local X=T.new(unpack(d))for I,d in ipairs(Q)do X:Insert(d,d);(expect(X:GetSize())).to.equal(1)X:Remove(d);(expect(X:GetSize())).to.equal(0);(expect(X._dataToLeaf[d])).to.never.be.ok()end end)it("\115\104\111\117\108\100 \100\101\108\101\116\101 \109\117\108\116\105\112\108\101 \099\111\111\114\100\115",function()local X=T.new(unpack(d))for I,d in ipairs(Q)do X:Insert(d,d)end for I,d in ipairs(Q)do X:Remove(d)local T,Q=X:GetNearestNeighbor(d,1);(expect(T)).never.to.be.ok()end;(expect(X:GetSize())).to.equal(0)end)end)describe("\110\101\097\114\101\115\116-\110\101\105\103\104\098\111\114",function()it("\115\104\111\117\108\100 \115\101\097\114\099\104 \102\111\114 \110\101\097\114\101\115\116 \110\101\105\103\104\098\111\114\115",function()local X=.5 local v=T.new(unpack(d))for X,I in ipairs(Q)do v:Insert(I,I)end local D=Vector3.new(.1,.1,.1)local M,J=v:GetNearestNeighbor(D);(expect(I(J,D,X))).to.equal(true)for d,T in pairs(Q)do local Q=Vector3.new(math.random(),math.random(),math.random())/1000+T;(expect(I(Q,T,X))).to.equal(true)local D,M=v:GetNearestNeighbor(Q);(expect(I(M,Q,X))).to.equal(true);(expect(I(T,M,X))).to.equal(true)end end)it("\115\104\111\117\108\100\110\'\116 \114\101\116\117\114\110 \116\111\111 \102\097\114 \114\101\115\117\108\116\115",function()local X=T.new(unpack(d))for I,d in ipairs(Q)do X:Insert(d,d)end local I=Vector3.new(1,1,1)*1000 local v,D=X:GetNearestNeighbor(I,10);(expect(v)).never.to.be.ok()end)end)end
local ReplicatedStorage = game:GetService("ReplicatedStorage")

local function isClose(a, b, eps)
    return (a-b).Magnitude <= eps
end

local DEFAULT_BOUNDS = {Vector3.new(-1E6, -1E6, -1E6), Vector3.new(1E6, 1E6, 1E6)}
return function()
    local Octree = require(ReplicatedStorage.Objects.Shared.Octree)

    local COORDS = {
        Vector3.new(0, 0, 0),
        Vector3.new(1, 1, 1),
        Vector3.new(1, 2, 1),
        Vector3.new(1, 1, 3),
        Vector3.new(1.5, 11, 1),
        Vector3.new(1, -200, 1),
    }
    describe(
        "insert",
        function()
            it(
                "should insert coords",
                function()
                    local tree = Octree.new(unpack(DEFAULT_BOUNDS))
                    for i, coord in ipairs(COORDS) do
                        tree:Insert(coord, coord)
                        expect(tree:GetSize()).to.equal(i)
                        expect(tree._dataToLeaf[coord]).to.be.ok()
                    end
                end
            )
            it(
                "should be able to find coords",
                function()
                    local tree = Octree.new(unpack(DEFAULT_BOUNDS))
                    for i, coord in ipairs(COORDS) do
                        tree:Insert(coord, coord)
                        local data, coordinate = tree:GetNearestNeighbor(coord)
                        expect(data).to.equal(coord)
                    end
                end
            )
        end
    )

    describe(
        "delete",
        function()
            it(
                "should delete coords",
                function()
                    local tree = Octree.new(unpack(DEFAULT_BOUNDS))
                    for i, coord in ipairs(COORDS) do
                        tree:Insert(coord, coord)
                        expect(tree:GetSize()).to.equal(1)
                        tree:Remove(coord)
                        expect(tree:GetSize()).to.equal(0)
                        expect(tree._dataToLeaf[coord]).to.never.be.ok()
                    end
                end
            )

            it(
                "should delete multiple coords",
                function()
                    local tree = Octree.new(unpack(DEFAULT_BOUNDS))
                    for i, coord in ipairs(COORDS) do
                        tree:Insert(coord, coord)
                    end
                    for i, coord in ipairs(COORDS) do
                        tree:Remove(coord)
                        local data, coordinate = tree:GetNearestNeighbor(coord, 1)
                        expect(data).never.to.be.ok()
                    end
                    expect(tree:GetSize()).to.equal(0)
                end
            )
        end
    )

    describe(
        "nearest-neighbor",
        function()
            it(
                "should search for nearest neighbors",
                function()
                    local eps = .5
                    local tree = Octree.new(unpack(DEFAULT_BOUNDS))
                    for i, coord in ipairs(COORDS) do
                        tree:Insert(coord, coord)
                    end
                    local test_coord = Vector3.new(.1, .1, .1)
                    local data, returned_coord = tree:GetNearestNeighbor(test_coord)
                    expect(isClose(returned_coord, test_coord, eps)).to.equal(true)

                    for _,v in pairs(COORDS) do
                        local test_coord = Vector3.new(math.random(), math.random(), math.random())/1000 + v
                        expect(isClose(test_coord, v, eps)).to.equal(true)
                        local data, returned_coord = tree:GetNearestNeighbor(test_coord)
                        expect(isClose(returned_coord, test_coord, eps)).to.equal(true)
                        expect(isClose(v, returned_coord, eps)).to.equal(true)
                    end
                end
            )
            it(
                "shouldn't return too far results",
                function()
                    local tree = Octree.new(unpack(DEFAULT_BOUNDS))
                    for i, coord in ipairs(COORDS) do
                        tree:Insert(coord, coord)
                    end
                    local test_coord = Vector3.new(1, 1, 1) * 1000
                    local data, returned_coord = tree:GetNearestNeighbor(test_coord, 10)
                    expect(data).never.to.be.ok()
                end
            )
        end
    )
end
