module Tests.Internal.MinHeap (tests) where

import AtCoder.Internal.MinHeap qualified as ACIMH
import Control.Monad
import Control.Monad.ST (runST)
import Data.List qualified as L
import Data.Maybe
import Test.Tasty
import Test.Tasty.QuickCheck qualified as QC

prop_ordered :: TestTree
prop_ordered =
  testGroup
    "Ordering"
    [ QC.testProperty "max heap ordering" $ do
        n <- QC.chooseInt (1, 16)
        xs <- QC.vectorOf n (QC.chooseInt (-10, 10))
        let result = runST $ do
              heap <- ACIMH.new n
              forM_ xs (ACIMH.push heap)
              replicateM n (fromJust <$> ACIMH.pop heap)
        let expected = L.sort xs
        pure . QC.counterexample (show xs) $ result QC.=== expected
    ]

tests :: [TestTree]
tests = [testGroup "AtCoder.Internal.Heap" [prop_ordered]]