module Data.Heap.Spec
    ( spec
    ) where

import Data.Bifunctor (bimap)
import Data.Foldable (toList)
import Data.List (partition, sort, uncons)

import Test.Hspec
import Test.Hspec.QuickCheck (prop)
import Test.QuickCheck

import qualified Data.Heap as H

default (Int)

instance (Arbitrary a, Ord a) => Arbitrary (H.Heap a) where
    arbitrary = fmap H.fromList arbitrary

spec :: Spec
spec = describe "Data.Heap" $ do
        prop "satisfies `fromList . toList == id`" $ \h -> H.fromList (toList h) === h

        describe "size" $ do
            prop "returns the size" $ \h -> H.size h === length (toList h)
            it "returns 0 for the empty heap" $ H.size H.empty `shouldBe` 0

        describe "union" $ do
            prop "returns the union of two heaps" $ \xs ys -> H.union (H.fromList xs) (H.fromList ys) === H.fromList (xs ++ ys)
            prop "empty heap is neutral element" $ \h -> H.union h H.empty === h .&&. H.union H.empty h === h

        describe "insert" $ do
            prop "inserts an element" $ \xs x -> H.insert x (H.fromList xs) === H.fromList (x : xs)
            prop "works for the empty heap" $ \x -> H.insert x H.empty === H.singleton x

        describe "deleteMin" $ do
            prop "deletes the minimum element" $ \xs -> H.deleteMin (H.fromList xs) === maybe H.empty (H.fromList . snd) (uncons (sort xs))
            it "works for the empty heap" $ H.deleteMin H.empty `shouldBe` H.empty

        describe "filter" $ do
            prop "filters the elements that satisfy the predicate" $ \xs -> H.filter even (H.fromList xs) === H.fromList (filter even xs)

        describe "partition" $ do
            prop "partitions the elements based on the predicate" $ \xs -> H.partition even (H.fromList xs) === bimap H.fromList H.fromList (partition even xs)

        describe "heapsort" $ do
            prop "sorts a list" $ \ls -> H.heapsort ls === sort ls