add multi-recursion insert test

4 files changed, 174 insertions, 4 deletions

diff --git a/city/.#geometry-test.lua b/city/.#geometry-test.lua
deleted file mode 120000
index 4290946..0000000
--- a/city/.#geometry-test.lua
+++ /dev/null
@@ -1 +0,0 @@
-kate@amalthea.2265651:1645662843
\ No newline at end of file
diff --git a/city/geometry-test.lua b/city/geometry-test.lua
index 3227cd1..758ce95 100644
--- a/city/geometry-test.lua
+++ b/city/geometry-test.lua
@@ -1,5 +1,6 @@
 local test = require('minunit').test
 local geom = require 'geometry'
+local util = require 'util'
 
 
 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
@@ -148,7 +149,100 @@ test(
       assert(node.square.center.y == 2)
       assert(node.square.span == 4)
 
-      assert(not node:is_leaf())
+      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
 )
diff --git a/city/geometry.lua b/city/geometry.lua
index 78c2aa7..5893731 100644
--- a/city/geometry.lua
+++ b/city/geometry.lua
@@ -96,9 +96,49 @@ geom.qt_node = class{
    end,
 
    is_leaf = function(self)
-      if self.children then return true end
-      return false
+      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
 }
 
 return geom
diff --git a/city/util.lua b/city/util.lua
new file mode 100644
index 0000000..49ead55
--- /dev/null
+++ b/city/util.lua
@@ -0,0 +1,37 @@
+local util = {}
+
+util.table_str = function(tbl, recursive, indent)
+   local tab = '\t'
+   
+   local recursive = recursive or false
+   local indent = indent or ''
+
+   local str = '{'
+
+   for key, value in pairs(tbl) do
+      local key_str, value_str
+      if type(key) == 'table' and recursive then
+	 key_str = util.table_str(key, recursive, indent..tab)
+      else
+	 key_str = tostring(key)
+      end
+
+      if type(value) == 'table' and recursive then
+	 value_str = util.table_str(value, recursive, indent..tab)
+      else
+	 value_str = tostring(value)
+      end
+
+      str = str .. string.format(
+	 '\n%s%s = %s', indent..tab,
+	 key_str, value_str)
+   end
+
+   if string.len(str) > 1 then
+      str = str .. '\n' .. indent
+   end
+   str = str .. '}'
+   return str
+end
+
+return util