-
Notifications
You must be signed in to change notification settings - Fork 7
/
Heap.hs
65 lines (55 loc) · 1.46 KB
/
Heap.hs
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
{-# LANGUAGE CPP, TemplateHaskell #-}
module Main where
import qualified Data.List as L
#if METHOD == 1
import Data.Heap.Splay
#elif METHOD == 2
import Data.Heap.Skew
#elif METHOD == 3
import Data.Heap.Binominal
#elif METHOD == 4
import Data.Heap.Leftist
#else
import Data.Heap.Splay
#endif
import Test.Framework.TH.Prime
import Test.Framework.Providers.DocTest.Prime
import Test.Framework.Providers.QuickCheck2
main :: IO ()
main = $(defaultMainGenerator)
doc_test :: DocTests
#if METHOD == 1
doc_test = docTest ["../Data/Heap/Splay.hs"] ["-i.."]
#elif METHOD == 2
doc_test = docTest ["../Data/Heap/Skew.hs"] ["-i.."]
#elif METHOD == 3
doc_test = docTest ["../Data/Heap/Binominal.hs"] ["-i.."]
#elif METHOD == 4
doc_test = docTest ["../Data/Heap/Leftist.hs"] ["-i.."]
#else
doc_test = docTest ["../Data/Heap/Splay.hs"] ["-i.."]
#endif
prop_fromList :: [Int] -> Bool
prop_fromList xs = valid $ fromList xs
prop_toList :: [Int] -> Bool
prop_toList xs = length (toList (fromList xs)) == length xs
prop_deleteMin :: [Int] -> Bool
prop_deleteMin [] = True
prop_deleteMin xs = valid t'
where
t = fromList xs
t' = deleteMin t
prop_deleteMin2 :: [Int] -> Bool
prop_deleteMin2 [] = True
prop_deleteMin2 xs = ys == zs
where
t = fromList xs
t' = deleteMin t
ys = heapSort t'
zs = tail . L.sort $ xs
prop_merge :: [Int] -> Bool
prop_merge [] = True
prop_merge (x:xs) = valid $ merge (fromList ys) (fromList zs)
where
ys = filter (<x) xs
zs = filter (>x) xs