-- ---------------------------------------------------------------------------
-- siftDown
-- Purpose:
--   Restore the max-heap property below root in the 1-based range 1..last.
-- Parameters:
--   values - list to mutate; root - subtree root; last - inclusive heap end.
-- Returns:
--   None.
-- Variables used:
--   child - selected child index.
-- ---------------------------------------------------------------------------
local function siftDown(values, root, last)
  while root * 2 <= last do
    local child = root * 2
    if child + 1 <= last and values[child] < values[child + 1] then child = child + 1 end
    if values[root] >= values[child] then return end
    values[root], values[child] = values[child], values[root];
    root = child;
  end
end

-- ---------------------------------------------------------------------------
-- loadFile
-- Purpose:
--   Read non-blank lines from a file and convert them to numbers.
-- Parameters:
--   fileSpec - input file path.
-- Returns:
--   A list table; raises on I/O or number-conversion errors.
-- Variables used:
--   inputFile, values, line - file handle, accumulated data, current line.
-- ---------------------------------------------------------------------------
local function loadFile(fileSpec)
  print("READING INPUT FILE...")
  local inputFile = assert(io.open(fileSpec, "r"))
  local values = {}
  for line in inputFile:lines() do
    if line:match("%S") then table.insert(values, assert(tonumber(line))) end
  end
  inputFile:close()
  print("DONE.")
  return values
end

-- ---------------------------------------------------------------------------
-- saveFile
-- Purpose:
--   Write each value to a file on its own line.
-- Parameters:
--   values - list table; fileSpec - output file path.
-- Returns:
--   None.
-- Variables used:
--   outputFile, value - file handle and current item.
-- ---------------------------------------------------------------------------
local function saveFile(values, fileSpec)
  print("SAVING OUTPUT FILE...")
  local outputFile = assert(io.open(fileSpec, "w"))
  for _, value in ipairs(values) do outputFile:write(value, "\n") end
  outputFile:close()
  print("DONE.")
end

-- ---------------------------------------------------------------------------
-- performSort
-- Purpose:
--   Sort values in place using heap sort and measure CPU time.
-- Parameters:
--   values - list table to sort.
-- Returns:
--   Elapsed CPU time in seconds.
-- Variables used:
--   startTime, endTime - timer snapshots; start, last - heap bounds.
-- ---------------------------------------------------------------------------
local function performSort(values)
  print("SORTING ELEMENTS...")
  local startTime = os.clock()
  for start = math.floor(#values / 2), 1, -1 do siftDown(values, start, #values) end
  for last = #values, 2, -1 do
    values[1], values[last] = values[last], values[1]
    siftDown(values, 1, last - 1)
  end
  local endTime = os.clock()
  print("DONE.")
  return endTime - startTime;
end

print("***HEAPSORT LUA***")
local values = loadFile("D:/Sorting/Sorting_Input.txt")
local elapsed = performSort(values)
saveFile(values, "D:/Sorting/Output_LUA.txt")
print("***RUN COMPLETE***")
print(string.format("HEAPSORT TOOK %.6f SECONDS.", elapsed))