module Main where

import Data.Time.Clock

data Heap = Empty | Node Int Heap Heap

-- ---------------------------------------------------------------------------
-- readSortingInput
-- Purpose:
--   Read a file as one integer per non-empty line.
-- Parameters:
--   filePath - input file path.
-- Returns:
--   IO action producing the parsed values; invalid integer text fails at read.
-- Variables used:
--   None beyond the filePath argument; processing is composed functionally.
-- ---------------------------------------------------------------------------
readSortingInput :: FilePath -> IO [Int]
readSortingInput filePath = map read . filter (not . null) . lines <$> readFile filePath

-- ---------------------------------------------------------------------------
-- merge
-- Purpose:
--   Meld two max-heaps while retaining the larger root.
-- Parameters:
--   Two Heap values to combine.
-- Returns:
--   A max-heap containing the values from both inputs.
-- Variables used:
--   firstValue/secondValue and their subheaps are matched from Node values.
-- ---------------------------------------------------------------------------
merge :: Heap -> Heap -> Heap
merge Empty heap = heap
merge heap Empty = heap
merge first@(Node firstValue firstLeft firstRight) second@(Node secondValue secondLeft secondRight)
    | firstValue >= secondValue = Node firstValue (merge firstRight second) firstLeft
    | otherwise = Node secondValue (merge secondRight first) secondLeft

-- ---------------------------------------------------------------------------
-- insert
-- Purpose:
--   Insert one integer into a max-heap.
-- Parameters:
--   value - integer to insert; heap - existing max-heap.
-- Returns:
--   Updated max-heap.
-- Variables used:
--   None; delegates heap combination to merge.
-- ---------------------------------------------------------------------------
insert :: Int -> Heap -> Heap
insert value heap = merge (Node value Empty Empty) heap

-- ---------------------------------------------------------------------------
-- removeMaximum
-- Purpose:
--   Remove the maximum value from a heap.
-- Parameters:
--   heap - heap to remove from.
-- Returns:
--   Nothing for Empty; otherwise Just (maximum, remaining heap).
-- Variables used:
--   value, left, right - root item and its subheaps.
-- ---------------------------------------------------------------------------
removeMaximum :: Heap -> Maybe (Int, Heap)
removeMaximum Empty = Nothing
removeMaximum (Node value left right) = Just (value, merge left right)

-- ---------------------------------------------------------------------------
-- heapsort
-- Purpose:
--   Sort integers in ascending order by building and draining a max-heap.
-- Parameters:
--   values - input integer list.
-- Returns:
--   A new sorted list; the input list is unchanged.
-- Variables used:
--   heap - local binding used by drainHeap; value, remaining - drain state.
-- ---------------------------------------------------------------------------
heapsort :: [Int] -> [Int]
heapsort values = reverse (drainHeap (foldr insert Empty values))
    where
        drainHeap heap = case removeMaximum heap of
            Nothing -> []
            Just (value, remaining) -> value : drainHeap remaining


-- ---------------------------------------------------------------------------
-- main
-- Purpose:
--   Load, sort, save, and report the configured input file.
-- Parameters:
--   None.
-- Returns:
--   IO action with no result value.
-- Variables used:
--   values, startTime, sortedValues, endTime - input, timing, and sort result.
-- ---------------------------------------------------------------------------
main :: IO ()
main = do
     putStrLn "***HEAPSORT HASKELL***"
     putStr "READING INPUT FILE..."
     values <- readSortingInput "D:/Sorting/Sorting_Input.txt"
     putStrLn "DONE."
     putStr "SORTING ELEMENTS..."
     startTime <- getCurrentTime
     let sortedValues = heapsort values
     endTime <- getCurrentTime
     putStrLn "DONE."
     putStr "WRITING OUTPUT FILE..."
     writeFile "D:/Sorting/Output_Haskell.txt" (unlines (map show sortedValues))
     putStrLn "DONE."
     putStrLn "***RUN COMPLETE***"
     putStrLn ("HEAPSORT TOOK " ++ show (diffUTCTime endTime startTime) ++ " SECONDS.")