TestMap.hs 2.81 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

{-


Test instanciations.

: MAPMODULE    :   MAPK      : KEY : EL  :
------------------------------------------
: Data.Map     :   M.Map Int : Int : Int : 
: Data.IntMap  :   M.IntMap  : Int : Int :


-}

-- Module to test the interface of Map-like types.

-- These are all
-- black-box testing: we never check the internal data structures.
-- We are thus independant of the underlying representation.

import qualified MAPMODULE as M

import qualified Data.List as List

import LibTest

import Control.Monad

type MAP = MAPK EL

main = runTests fileName propNames propTests

-------------------
--  Arbitrary maps

instance Arbitrary MAP where
    arbitrary = return M.fromList `ap` arbitrary

prop_Split :: MAP -> KEY -> Bool
prop_Split s k = all (< k) (M.keys l) && all (> k) (M.keys r)
    where (l,r) = M.split k s

prop_SplitUnion :: MAP -> KEY -> Property
prop_SplitUnion s k = not (M.member k s) ==> M.union l r == s
    where (l,r) = M.split k s

prop_SplitLookup :: MAP -> KEY -> Bool
prop_SplitLookup s k = all (< k) (M.keys l) && all (> k) (M.keys r) && found == M.lookup k s
    where (l,found,r) = M.splitLookup k s

prop_Single :: KEY -> EL -> Bool
prop_Single k x
    = (M.insert k x M.empty == M.singleton k x)

prop_InsertDelete :: KEY -> EL -> MAP -> Property
prop_InsertDelete k x t
  = (M.lookup k t == Nothing) ==> M.delete k (M.insert k x t) == t

prop_UnionInsert :: KEY -> EL -> MAP -> Bool
prop_UnionInsert k x t
  = M.union (M.singleton k x) t == M.insert k x t

prop_UnionAssoc :: MAP -> MAP -> MAP -> Bool
prop_UnionAssoc t1 t2 t3
  = M.union t1 (M.union t2 t3) == M.union (M.union t1 t2) t3

prop_UnionComm :: MAP -> MAP -> Bool
prop_UnionComm t1 t2
  = (M.union t1 t2 == M.unionWith (\x y -> y) t2 t1)

prop_UnionWith :: [(KEY,EL)] -> [(KEY,EL)] -> Bool
prop_UnionWith xs ys
  = sum (M.elems (M.unionWith (+) (M.fromListWith (+) xs) (M.fromListWith (+) ys))) 
    == (sum (Prelude.map snd xs) + sum (Prelude.map snd ys))

prop_Diff :: [(KEY,EL)] -> [(KEY,EL)] -> Bool
prop_Diff xs ys
  =  List.sort (M.keys (M.difference (M.fromListWith (+) xs) (M.fromListWith (+) ys))) 
    == List.sort ((List.\\) (List.nub (Prelude.map fst xs))  (List.nub (Prelude.map fst ys)))

prop_Int :: [(KEY,EL)] -> [(KEY,EL)] -> Bool
prop_Int xs ys
  = List.sort (M.keys (M.intersection (M.fromListWith (+) xs) (M.fromListWith (+) ys))) 
    == List.sort (List.nub ((List.intersect) (Prelude.map fst xs)  (Prelude.map fst ys)))

prop_Ordered
  = forAll (choose (5,100)) $ \n ->
    let xs = [(x,()) | x <- [0..n::Int]]
    in M.fromAscList xs == M.fromList xs

prop_toAscList :: [KEY] -> Bool
prop_toAscList xs
  = (List.sort $ List.nub $ xs) == (map fst $ M.toAscList $ M.fromList $ zip xs (repeat ()))


prop_toList :: [KEY] -> Bool
prop_toList xs
  = (List.sort $ List.nub $ xs) == (map fst $ M.toList $ M.fromList $ zip xs (repeat ()))