local geom = {}

local function class(tbl)
   setmetatable(tbl, tbl)
   return tbl
end

-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
--
-- point
--
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

geom.point = class{
   __call = function(this, x, y)
      local pt = {}
      pt.x = x
      pt.y = y
      setmetatable(pt, {__index=this})
      return pt
   end,

   distance_to = function(self, pt)
      local d_x = self.x - pt.x
      local d_y = self.y - pt.y
      return math.sqrt(d_x*d_x + d_y*d_y)
   end,
}


-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
--
-- square
--
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

geom.square = class{
   __call = function(this, center, span)
      local square = {}
      square.center = center
      square.span = span
      square.x = this.axis_range(center.x, span/2)
      square.y = this.axis_range(center.y, span/2)
      setmetatable(square, {__index=this})
      return square
   end,

   axis_range = function(c, r) return {min=c-r, max=c+r} end,

   -- returns true if a point is inside of the square
   -- and false otherwise
   -- (x/y mininum exclusive, maximum inclusive)
   contains = function(self, point)
      local x_overlap =
	 (point.x > self.x.min) and (point.x <= self.x.max)
      local y_overlap =
	 (point.y > self.y.min) and (point.y <= self.y.max)

      if x_overlap and y_overlap then
	 return true
      end
      return false
   end,

   -- check if the square intersects the given square
   intersects = function(self, square)
      local overlap = function(a, b)
	 return math.max(a.min, b.min) < math.min(a.max, b.max)
      end
      local x_overlap = overlap(self.x, square.x)
      local y_overlap = overlap(self.y, square.y)

      if x_overlap and y_overlap then return true end
      return false
   end,

   -- return an array of four squares covering the same
   -- area as their parent
   divide = function(self)
      local this = getmetatable(self).__index

      local x = self.center.x
      local y = self.center.y
      local d = self.span / 4

      return {
	 this(geom.point(x-d, y-d), d*2),
	 this(geom.point(x+d, y-d), d*2),
	 this(geom.point(x-d, y+d), d*2),
	 this(geom.point(x+d, y+d), d*2),
      }
   end,
}


-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
--
-- qt_node
--
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

geom.qt_node = class{
   __call = function(this, center, span)
      local node = {}
      node.square = geom.square(center, span)
      setmetatable(node, {__index=this})
      return node
   end,

   is_leaf = function(self)
      if self.children then return false end
      return true
   end,

   insert = function(self, point)
      if not self.square:contains(point) then
	 -- point isn't even in this region
	 return false
      end

      if self:is_leaf() and not self.point then
	 -- no preexisting point, just store it
	 self.point = point
	 return true
      end

      if self:is_leaf() then
	 -- subdivide and re-insert original point
	 -- and then insert new point again
	 local self_point = self.point
	 self.point = nil
	 self.children = {}
	 local this = getmetatable(self).__index
	 local child_regions = self.square:divide()
	 for _, region in ipairs(child_regions) do
	    table.insert(
	       self.children,
	       this(region.center, region.span)
	    )
	 end
	 self:insert(self_point)
	 self:insert(point)
	 return true
      end

      -- not a leaf node
      for _, child in ipairs(self.children) do
	 if child:insert(point) then return true end
      end

      -- should never get here
      return false
   end,

   -- append any points within the supplied region under
   -- the current node to the supplied array
   query = function(self, region, points)
      -- don't do anything if there's no intersection
      if not self.square:intersects(region) then return end

      if self:is_leaf() then
	 if self.point and region:contains(self.point) then
	    table.insert(points, self.point)
	 end
	 return
      end

      -- not a leaf node, recursively query children
      for _, child in ipairs(self.children) do
	 child:query(region, points)
      end
   end,

   -- return the leaf node containing the given point
   -- returns nil if no such node exists (i.e. the point
   -- is out of bounds)
   find_containing = function(self, point)
      if not self.square:contains(point) then return end

      if self:is_leaf() then return self end

      for _, child in ipairs(self.children) do
	 local result = child:find_containing(point)
	 if result then return result end
      end
   end
}

return geom