local geom = require 'geometry'


function progress(fraction)
   local bar = string.rep('=', math.ceil(40*fraction))
   io.write(string.format('[%-40s]\r', bar))
   io.flush()
end

function benchmark(f, N)
   local percent_no = math.floor(N / 100)
   local start = os.time()
   for i=1,100 do
      progress(i/100)
      for j=1,percent_no do
	 f()
      end
   end
   print()
   print(
      string.format(
	 'function %s: %d seconds (%d iterations)',
	 tostring(f), os.difftime(os.time(), start), percent_no * 100
      )
   )
end


function random_point()
   return geom.point(math.random(), math.random())
end

local n_points = 1e5
print(string.format('generating %d points...', n_points))
local tree = geom.quadtree()
local points = {}
for i=1,n_points do
   progress(i/n_points)
   local point = random_point()
   table.insert(points, point)
   tree:insert(point)
end
print()

local find_closest = function(point)
   local dist = math.huge
   local closest
   for _, pt in ipairs(points) do
      if point:distance_to(pt) < dist then
	 dist = point:distance_to(pt)
	 closest = pt
      end
   end
   return closest
end


print('benchmarking brute-force')
benchmark(
   function()
      local point = random_point()
      find_closest(point)
   end, 10000)

print('benchmarking quadtree')
benchmark(
   function()
      local point = random_point()
      tree:get_closest(point)
   end, 10000)