local test = require('minunit').test
local geom = require 'geometry'
local util = require 'util'


-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
--
-- geom.point tests
--
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

test(
   'create point object',
   function()
      local pt = geom.point(1, 5.5)
      assert(pt.x == 1)
      assert(pt.y == 5.5)
      local mt = getmetatable(pt)
      assert(mt.__index == geom.point)
   end
)

test(
   'point distances',
   function()
      local a = geom.point(1, 3)
      local b = geom.point(4, 7)
      assert(a:distance_to(b) == 5)

      assert(a:distance_to(a) == 0)
   end
)


-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
--
-- geom.square tests
--
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

test(
   'create square object',
   function()
      local s = geom.square(geom.point(2, 5), 1)
      assert(s.center.x == 2)
      assert(s.center.y == 5)
      assert(s.span == 1)

      assert(s.x.min ==  1.5)
      assert(s.x.max ==  2.5)
      assert(s.y.min ==  4.5)
      assert(s.y.max ==  5.5)
   end
)

test(
   'check if point is in square',
   function()
      local center = geom.point(1, 1)
      local square = geom.square(center, 2)

      local interior_points = {
	 geom.point(1, 1),
	 geom.point(2, 2),
	 geom.point(2, 0.1),
	 geom.point(0.1, 0.1),
      }
      for _, point in ipairs(interior_points) do
	 assert(
	    square:contains(point),
	    string.format(
	       'point (%0.2f, %0.2f) was incorrectly outside!',
	       point.x, point.y
	    )
	 )
      end

      local exterior_points = {
	 geom.point(0, 0),
	 geom.point(10, 10),
	 geom.point(0, 1),
	 geom.point(1, 0),
	 geom.point(-2, 1),
	 geom.point(1, -2),
      }
      for _, point in ipairs(exterior_points) do
	 assert(
	    not square:contains(point),
	    string.format(
	       'point (%0.2f, %0.2f) was incorrectly inside!',
	       point.x, point.y
	    )
	 )
      end
   end
)

test(
   'subdivide a square',
   function()
      local center = geom.point(2, 2)
      local square = geom.square(center, 4)

      local children = square:divide()
      assert(
	 #children == 4,
	 string.format(
	    'incorrect number of children: %d',
	    #children
	 )
      )

      local aa = children[1]
      assert(aa.center.x == 1)
      assert(aa.center.y == 1)
      assert(aa.span == 2)

      local ba = children[2]
      assert(ba.center.x == 3)
      assert(ba.center.y == 1)
      assert(ba.span == 2)

      local ab = children[3]
      assert(ab.center.x == 1)
      assert(ab.center.y == 3)
      assert(ab.span == 2)

      local bb = children[4]
      assert(bb.center.x == 3)
      assert(bb.center.y == 3)
      assert(bb.span == 2)
   end
)

test(
   'intersect various squares',
   function()
      local center = geom.point(0, 0)
      local square = geom.square(center, 2)

      -- overlap x/y
      assert(square:intersects(
		geom.square(geom.point(1, 1), 2)))

      -- nest inside
      assert(square:intersects(
		geom.square(geom.point(0, 0), 1)))

      -- nest outside
      assert(square:intersects(
		geom.square(geom.point(0, 0), 5)))

      -------- non-intersections --------

      -- share x on left
      assert(not square:intersects(
		geom.square(geom.point(-2, 0), 2)))

      -- share x on right
      assert(not square:intersects(
		geom.square(geom.point(2, 0), 2)))

      -- share y on top
      assert(not square:intersects(
		geom.square(geom.point(0, -2), 2)))

      -- share y on bottom
      assert(not square:intersects(
		geom.square(geom.point(0, 2), 2)))
   end
)

-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
--
-- geom.qt_node
--
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

test(
   'create qt_node',
   function()
      local center = geom.point(2, 2)
      local node = geom.qt_node(center, 4)

      assert(node.square.center.x == 2)
      assert(node.square.center.y == 2)
      assert(node.square.span == 4)

      assert(node:is_leaf())
      assert(not node.point)
   end
)

test(
   'insert points into qt_node',
   function()
      local center = geom.point(2, 2)
      local node = geom.qt_node(center, 4)

      assert(node:is_leaf())
      assert(not node.point)

      node:insert(geom.point(1, 1))
      assert(node:is_leaf())
      assert(node.point.x == 1)
      assert(node.point.y == 1)

      node:insert(geom.point(3, 3))
      assert(not node:is_leaf())

      assert(node.children[1]:is_leaf())
      assert(node.children[1].point.x == 1)
      assert(node.children[1].point.y == 1)

      assert(node.children[2]:is_leaf())
      assert(not node.children[2].point)

      assert(node.children[3]:is_leaf())
      assert(not node.children[3].point)

      assert(node.children[4]:is_leaf())
      assert(node.children[4].point.x == 3)
      assert(node.children[4].point.y == 3)
   end
)

test(
   'instert four points into qt_node',
   function()
      local center = geom.point(2, 2)
      local node = geom.qt_node(center, 4)

      node:insert(geom.point(1, 1))
      node:insert(geom.point(0.5, 0.5))
      node:insert(geom.point(0.25, 0.25))
      node:insert(geom.point(0.125, 0.125))

      assert(not node:is_leaf())

      assert(node.children[2]:is_leaf())
      assert(not node.children[2].point)
      assert(node.children[3]:is_leaf())
      assert(not node.children[3].point)
      assert(node.children[4]:is_leaf())
      assert(not node.children[4].point)

      node = node.children[1].children[1]
      assert(not node:is_leaf())

      assert(not node.children[1]:is_leaf())
      assert(node.children[2]:is_leaf())
      assert(not node.children[2].point)
      assert(node.children[3]:is_leaf())
      assert(not node.children[3].point)
      assert(node.children[4]:is_leaf())
      assert(node.children[4].point.x == 1)
      assert(node.children[4].point.y == 1)

      node = node.children[1]
      assert(not node:is_leaf())

      assert(node.children[2]:is_leaf())
      assert(not node.children[2].point)
      assert(node.children[3]:is_leaf())
      assert(not node.children[3].point)
      assert(node.children[4]:is_leaf())
      assert(node.children[4].point.x == 0.5)
      assert(node.children[4].point.y == 0.5)

      node = node.children[1]
      assert(not node:is_leaf())

      assert(node.children[2]:is_leaf())
      assert(not node.children[2].point)
      assert(node.children[3]:is_leaf())
      assert(not node.children[3].point)
      assert(node.children[4]:is_leaf())
      assert(node.children[4].point.x == 0.25)
      assert(node.children[4].point.y == 0.25)

      assert(node.children[1]:is_leaf())
      assert(node.children[1].point.x == 0.125)
      assert(node.children[1].point.y == 0.125)
   end
)

test(
   'query qt_node with square',
   function()
      local node = geom.qt_node(geom.point(2, 2), 4)

      local x0 = 0.5
      local y0 = 0.5
      for x = 0,3 do
	 for y = 0,3 do
	    node:insert(geom.point(x0 + x, y0 + y))
	 end
      end

      local query_region = geom.square(geom.point(2, 2), 2)
      local points = {}
      node:query(query_region, points)

      local expected_points = {
	 geom.point(1.5, 1.5),
	 geom.point(2.5, 1.5),
	 geom.point(1.5, 2.5),
	 geom.point(2.5, 2.5),
      }

      local is_expected = function(point)
	 for _, pt in ipairs(expected_points) do
	    if (point.x == pt.x) and (point.y == pt.y) then
	       return true
	    end
	 end
	 return false
      end

      assert(#points == 4)

      for _, point in ipairs(points) do
	 assert(is_expected(point))
      end
   end
)

test(
   'find containing node for points',
   function()
      local node = geom.qt_node(geom.point(2, 2), 4)

      node:insert(geom.point(1, 1))
      node:insert(geom.point(0.5, 0.5))
      node:insert(geom.point(0.25, 0.25))
      node:insert(geom.point(0.125, 0.125))

      local point = geom.point(3, 1)
      local n = node:find_containing(point)
      assert(n:is_leaf())
      assert(n.square.center.x == 3)
      assert(n.square.center.y == 1)

      point = geom.point(1, 3)
      n = node:find_containing(point)
      assert(n:is_leaf())
      assert(n.square.center.x == 1)
      assert(n.square.center.y == 3)

      point = geom.point(3, 3)
      n = node:find_containing(point)
      assert(n:is_leaf())
      assert(n.square.center.x == 3)
      assert(n.square.center.y == 3)

      point = geom.point(0.24, 0.24)
      n = node:find_containing(point)
      assert(n:is_leaf())
      assert(n.point.x == 0.25)
      assert(n.point.y == 0.25)
   end
)