# Ticket #1762: 1762.txt

File 1762.txt, 3.5 KB (added by dbenbenn, 8 years ago)
Line
1
2New patches:
3
4[Fix ticket 1762
5David Benbennick <[email protected]>**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.
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
69David Benbennick <[email protected]>**20071113045358] {
70hunk ./tests/all.T 5
71-
72+test('dataintset001', normal, compile_and_run, ['-package containers'])
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]
87hunk ./tests/dataintset001.stdout 1
88+True
89}
90
91Context:
92
93[Specify build-type: Simple
94Duncan Coutts <[email protected]>**20071018125404]