module Data.PrioHeap.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.PrioHeap as P

default (Int)

instance (Arbitrary k, Arbitrary a, Ord k) => Arbitrary (P.PrioHeap k a) where
    arbitrary = fmap P.fromList arbitrary

fromList :: [(Int, ())] -> P.PrioHeap Int ()
fromList = P.fromList

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

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

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

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

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

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

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