Ticket #1762: 1762.txt

File 1762.txt, 3.5 KB (added by dbenbenn, 6 years ago)
Line 
1
2New patches:
3
4[Fix ticket 1762
5David Benbennick <dbenbenn@gmail.com>**20071111201939] {
6hunk ./Data/IntSet.hs 113
7-import QuickCheck
8+import Test.QuickCheck
9hunk ./Data/IntSet.hs 116
10+import qualified Data.Set as Set
11hunk ./Data/IntSet.hs 171
12+-- Invariant: The Mask is a power of 2.  It is the largest bit position at which
13+--            two elements of the set differ.
14+-- Invariant: Prefix is the common high-order bits that all elements share to
15+--            the left of the Mask bit.
16+-- Invariant: In Bin prefix mask left right, left consists of the elements that
17+--            don't have the mask bit set; right is all the elements that do.
18hunk ./Data/IntSet.hs 413
19-  | shorter m2 m1  = subsetCmpLt
20+  | shorter m2 m1  = case subsetCmpLt of
21+                       GT -> GT
22+                       _ -> LT
23hunk ./Data/IntSet.hs 864
24+-- Suppose a is largest such that 2^a divides 2*m.
25+-- Then mask i m is i with the low a bits zeroed out.
26hunk ./Data/IntSet.hs 1031
27+
28+{--------------------------------------------------------------------
29+  Bin invariants
30+--------------------------------------------------------------------}
31+powersOf2 :: IntSet
32+powersOf2 = fromList [2^i | i <- [0..63]]
33+
34+-- Check the invariant that the mask is a power of 2.
35+prop_MaskPow2 :: IntSet -> Bool
36+prop_MaskPow2 (Bin _ msk left right) = member msk powersOf2 && prop_MaskPow2 left && prop_MaskPow2 right
37+prop_MaskPow2 _ = True
38+
39+-- Check that the prefix satisfies its invariant.
40+prop_Prefix :: IntSet -> Bool
41+prop_Prefix s@(Bin prefix msk left right) = all (\elem -> match elem prefix msk) (toList s) && prop_Prefix left && prop_Prefix right
42+prop_Prefix _ = True
43+
44+-- Check that the left elements don't have the mask bit set, and the right
45+-- ones do.
46+prop_LeftRight :: IntSet -> Bool
47+prop_LeftRight (Bin _ msk left right) = and [x .&. msk == 0 | x <- toList left] && and [x .&. msk == msk | x <- toList right]
48+prop_LeftRight _ = True
49+
50+{--------------------------------------------------------------------
51+  IntSet operations are like Set operations
52+--------------------------------------------------------------------}
53+toSet :: IntSet -> Set.Set Int
54+toSet = Set.fromList . toList
55+
56+-- Check that IntSet.isProperSubsetOf is the same as Set.isProperSubsetOf.
57+prop_isProperSubsetOf :: IntSet -> IntSet -> Bool
58+prop_isProperSubsetOf a b = isProperSubsetOf a b == Set.isProperSubsetOf (toSet a) (toSet b)
59+
60+-- In the above test, isProperSubsetOf almost always returns False (since a
61+-- random set is almost never a subset of another random set).  So this second
62+-- test checks the True case.
63+prop_isProperSubsetOf2 :: IntSet -> IntSet -> Bool
64+prop_isProperSubsetOf2 a b = isProperSubsetOf a c == (a /= c) where
65+  c = union a b
66}
67
68[Add tiny regression test
69David Benbennick <dbenbenn@gmail.com>**20071113045358] {
70hunk ./tests/all.T 5
71-
72+test('dataintset001', normal, compile_and_run, ['-package containers'])
73addfile ./tests/dataintset001.hs
74hunk ./tests/dataintset001.hs 1
75+
76+{-
77+Through 6.8.1 this printed False, should be True.
78+-}
79+
80+module Main (main) where
81+
82+import Data.IntSet
83+
84+main :: IO ()
85+main = print $ isProperSubsetOf (fromList [2,3]) $ fromList [2,3,4]
86addfile ./tests/dataintset001.stdout
87hunk ./tests/dataintset001.stdout 1
88+True
89}
90
91Context:
92
93[Specify build-type: Simple
94Duncan Coutts <duncan@haskell.org>**20071018125404]
95[Add a boring file
96Ian Lynagh <igloo@earth.li>**20070913204647]
97[TAG 2007-09-13
98Ian Lynagh <igloo@earth.li>**20070913215901]
99Patch bundle hash:
10014737998e2fca643fc53bcac37a8d9c03b5e7af2