{-# LANGUAGE CPP, GeneralizedNewtypeDeriving #-}
-- | Tests for the 'Data.HashSet' module. We test functions by
-- comparing them to a simpler model, a list.
module Main (main) where
import qualified Data.Foldable as Foldable
import Data.Hashable (Hashable(hashWithSalt))
import qualified Data.List as L
import qualified Data.HashSet as S
import qualified Data.Set as Set
import Test.QuickCheck (Arbitrary)
import Test.Framework (Test, defaultMain, testGroup)
import Test.Framework.Providers.QuickCheck2 (testProperty)
-- Key type that generates more hash collisions.
newtype Key = K { unK :: Int }
deriving (Arbitrary, Enum, Eq, Integral, Num, Ord, Show, Real)
instance Hashable Key where
hashWithSalt salt k = hashWithSalt salt (unK k) `mod` 20
------------------------------------------------------------------------
-- * Properties
------------------------------------------------------------------------
-- ** Instances
pEq :: [Key] -> [Key] -> Bool
pEq xs = (Set.fromList xs ==) `eq` (S.fromList xs ==)
pNeq :: [Key] -> [Key] -> Bool
pNeq xs = (Set.fromList xs /=) `eq` (S.fromList xs /=)
pFoldable :: [Int] -> Bool
pFoldable = (L.sort . Foldable.foldr (:) []) `eq`
(L.sort . Foldable.foldr (:) [])
------------------------------------------------------------------------
-- ** Basic interface
pSize :: [Key] -> Bool
pSize = Set.size `eq` S.size
pMember :: Key -> [Key] -> Bool
pMember k = Set.member k `eq` S.member k
pInsert :: Key -> [Key] -> Bool
pInsert a = Set.insert a `eq_` S.insert a
pDelete :: Key -> [Key] -> Bool
pDelete a = Set.delete a `eq_` S.delete a
------------------------------------------------------------------------
-- ** Combine
pUnion :: [Key] -> [Key] -> Bool
pUnion xs ys = Set.union (Set.fromList xs) `eq_`
S.union (S.fromList xs) $ ys
------------------------------------------------------------------------
-- ** Transformations
pMap :: [Key] -> Bool
pMap = Set.map (+ 1) `eq_` S.map (+ 1)
------------------------------------------------------------------------
-- ** Folds
pFoldr :: [Int] -> Bool
pFoldr = (L.sort . foldrSet (:) []) `eq`
(L.sort . S.foldr (:) [])
foldrSet :: (a -> b -> b) -> b -> Set.Set a -> b
#if MIN_VERSION_containers(0,4,2)
foldrSet = Set.foldr
#else
foldrSet = Foldable.foldr
#endif
pFoldl' :: Int -> [Int] -> Bool
pFoldl' z0 = foldl'Set (+) z0 `eq` S.foldl' (+) z0
foldl'Set :: (a -> b -> a) -> a -> Set.Set b -> a
#if MIN_VERSION_containers(0,4,2)
foldl'Set = Set.foldl'
#else
foldl'Set = Foldable.foldl'
#endif
------------------------------------------------------------------------
-- ** Filter
pFilter :: [Key] -> Bool
pFilter = Set.filter odd `eq_` S.filter odd
------------------------------------------------------------------------
-- ** Conversions
pToList :: [Key] -> Bool
pToList = Set.toAscList `eq` toAscList
------------------------------------------------------------------------
-- * Test list
tests :: [Test]
tests =
[
-- Instances
testGroup "instances"
[ testProperty "==" pEq
, testProperty "/=" pNeq
, testProperty "Foldable" pFoldable
]
-- Basic interface
, testGroup "basic interface"
[ testProperty "size" pSize
, testProperty "member" pMember
, testProperty "insert" pInsert
, testProperty "delete" pDelete
]
-- Combine
, testProperty "union" pUnion
-- Transformations
, testProperty "map" pMap
-- Folds
, testGroup "folds"
[ testProperty "foldr" pFoldr
, testProperty "foldl'" pFoldl'
]
-- Filter
, testGroup "filter"
[ testProperty "filter" pFilter
]
-- Conversions
, testGroup "conversions"
[ testProperty "toList" pToList
]
]
------------------------------------------------------------------------
-- * Model
-- Invariant: the list is sorted in ascending order, by key.
type Model a = Set.Set a
-- | Check that a function operating on a 'HashMap' is equivalent to
-- one operating on a 'Model'.
eq :: (Eq a, Hashable a, Ord a, Eq b)
=> (Model a -> b) -- ^ Function that modifies a 'Model' in the same
-- way
-> (S.HashSet a -> b) -- ^ Function that modified a 'HashSet'
-> [a] -- ^ Initial content of the 'HashSet' and 'Model'
-> Bool -- ^ True if the functions are equivalent
eq f g xs = g (S.fromList xs) == f (Set.fromList xs)
eq_ :: (Eq a, Hashable a, Ord a)
=> (Model a -> Model a) -- ^ Function that modifies a 'Model'
-> (S.HashSet a -> S.HashSet a) -- ^ Function that modified a
-- 'HashSet' in the same way
-> [a] -- ^ Initial content of the 'HashSet'
-- and 'Model'
-> Bool -- ^ True if the functions are
-- equivalent
eq_ f g = (Set.toAscList . f) `eq` (toAscList . g)
------------------------------------------------------------------------
-- * Test harness
main :: IO ()
main = defaultMain tests
------------------------------------------------------------------------
-- * Helpers
toAscList :: Ord a => S.HashSet a -> [a]
toAscList = L.sort . S.toList