quadtree

--[[    class/quadtree.lua - Jericho Quadtree Interface

---     This module contains an implementation for a Quadtree datastructure.
--- This Quadtree is mostly used to support low complexity inventory collision
-- detection.

--]]

local dirs = enum {
    "northwest";
    "northeast";
    "southwest";
    "southeast";
    "none";
}

local node = class.define {
    --- \brief Array of four child nodes.
    children = {};

    --- \brief The size and width of this node.
    --- NOTE: This should always x, where x > 0 and f(x) = 2^n
    dimension = 2;

    --- \brief The value pointed to at this node.
    value = nil;

    --- \brief If this node has been subdivided or not
    split = false;

    --- \brief ctor.
    --- \p dim - This node's dimensions.
    --- \p val = The initial value for this node.
    __init = function(self, dim, x, y, val)
        self.dimension  = dim
        self.x          = x
        self.y          = y
        self.value      = val
    end;

    direction = function(self, x, y)
        local hs = self.dimension / 2

        if x >= self.x and x < self.x + hs then
            if y >= self.y and y < self.y + hs then
                return dirs.northwest
            elseif y >= self.y + hs and y <= self.y + self.dimension then
                return dirs.southwest
            end
        elseif x >= self.x + hs and x <= self.x + self.dimension then
            if y >= self.y and y < self.y + hs then
                return dirs.northeast
            elseif y >= self.y + hs and y <= self.y + self.dimension then
                return dirs.southeast
            end
        else
            return dirs.none
        end
    end;

    --- \brief Subdivides this node
    subdivide = function(self)
        assert(self.dimension ~= 1, "Cannot subdivide 1x1 node.")

        local hs = self.dimension / 2

        self.children[dirs.northwest] = self.__class(self.dimension / 2, self.x     , self.y)
        self.children[dirs.northeast] = self.__class(self.dimension / 2, self.x + hs, self.y)
        self.children[dirs.southwest] = self.__class(self.dimension / 2, self.x + hs, self.y + hs)
        self.children[dirs.southeast] = self.__class(self.dimension / 2, self.x     , self.y + hs)

        self.split = true
    end;

    insert = function(self, size, x, y, v)
        if self.dimension ~= size then
            local dir = self:direction(x, y)

            if not self.split then
                self:subdivide()
            end

            self.children[self:direction(x, y)]:insert(size, x, y, v)
        else
            self.value = v
        end
    end;

    get = function(self, x, y)
        if self.split then
            local dir = self:direction(x, y)
            return self.children[dir]:get(x, y)
        end

        return self.value
    end
}

local quadtree = class.define {
    __init = function(self, size)
        assert(type(size) == "number", "Expected size to be a number, got '" .. type(size) .. "'.")

        self.root = node(size, 0, 0)
    end;

    insert = function(self, size, x, y, v)
        assert(type(size) == "number", "Expected size to be a number, got '" .. type(size) .. "'.")
        assert(type(x) == "number", "Expected x to be a number, got '" .. type(x) .. "'.")
        assert(type(y) == "number", "Expected y to be a number, got '" .. type(y) .. "'.")

        self.root:insert(size, x, y, v)
    end;

    get = function(self, x, y)
        assert(type(x) == "number", "Expected x to be a number, got '" .. type(x) .. "'.")
        assert(type(y) == "number", "Expected y to be a number, got '" .. type(y) .. "'.")

        return self.root:get(x, y)
    end
}

class.quadtree = quadtree
return quadtree