-- binary_heap-test.lua

require("binary_heap")
local math_random = math.random
local table_sort, table_remove = table.sort, table.remove

-- tests -----------------------------------------------------------------------

local function test_heap_write()
  io.write("Pretty-printing binary heap:\n")
  h = binary_heap.heap:new()
  for i = 1, 20 do
    h:insert(math_random(100))
  end
  h:write()
  io.write("\n")
end

local function test_heap_integrity(runs, insert_count, pop_count, range)
  runs = runs or 200
  insert_count = insert_count or 100
  pop_count = pop_count or 50
  range = range or 10000

  h = binary_heap.heap:new(function(k1, k2) return k1 > k2 end)

  io.write("Testing heap integrity...\n")
  for i = 1,runs do
    for j = 1,math_random(insert_count) do
      h:insert(math_random(range), nil)
      if not h:check() then
        io.write("\n")
        h:write()
        error("Heap check failed aftet insertion")
      end
      io.write("Step: ", i, "/", runs, ": Heap size: ", #h,".     \r")
    end
    for j = 1,math.min(#h, math_random(pop_count)) do
      h:pop()
      if not h:check() then
        io.write("\n")
        h:write()
        error("Heap check failed after pop")
      end
      io.write("Step: ", i, "/", runs, ": Heap size: ", #h,".     \r")
    end
  end
  io.write("\n")
  while #h > 0 do
    h:pop()
      if not h:check() then
        io.write("\n")
        h:write()
        error("Heap check failed while clearing")
      end
    io.write("Clearing: Heap size: ", #h,".     \r")
  end
  io.write("\nDone.\n")
end

local function test_heap_speed(runs, insert_count, pop_count, range)
  runs = runs or 100
  insert_count = insert_count or 10000
  pop_count = pop_count or 7500
  pop_count = math.min(pop_count, insert_count)
  range = range or 10000

  h = binary_heap.heap:new()

  io.write("Testing heap speed...\n")
  local start = os.time()
  for i = 1,runs do
    io.write("Step: ", i, "/", runs..".\r")
    for j = 1,insert_count do
      h:insert(math_random(range), nil)
    end
    for j = 1,pop_count do
      h:pop()
    end
  end
  io.write("\nClearing heap.\n")
  while #h > 0 do
    h:pop()
  end
  
  local elapsed = os.difftime(os.time() - start)
  io.write("Done.  Elapsed time "..elapsed.." seconds (", elapsed / (insert_count * runs), " s/insert+pop).\n")
end

local function test_sort_queue_speed(runs, insert_count, pop_count, range)
  runs = runs or 100
  insert_count = insert_count or 10000
  pop_count = pop_count or 7500
  pop_count = math.min(pop_count, insert_count)
  range = range or 10000

  h = {}

  io.write("Testing sorted queue speed...\n")
  local start = os.time()
  for i = 1,runs do
    io.write("Step: ", i, "/", runs..".\r")
    for j = 1,insert_count do
      h[#h+1] = math_random(range)
    end
    table_sort(h)
    for j = 1,pop_count do
      table_remove(h)
    end
  end
  io.write("\nClearing heap.\n")
  while #h > 0 do
    table_remove(h)
  end
  
  local elapsed = os.difftime(os.time() - start)
  io.write("Done.  Elapsed time "..elapsed.." seconds (", elapsed / (insert_count * runs), " s/insert+pop).\n")
end



-- main -----------------------------------------------------------------------

test_heap_write()
test_heap_integrity()
test_heap_speed()
test_sort_queue_speed()

test_heap_speed(1000, 1000, 750)
test_sort_queue_speed(1000, 1000, 750)

-- EOF -------------------------------------------------------------------------