# Ticket #1762: 1762.txt

File 1762.txt, 3.5 KB (added by , 10 years ago) |
---|

Line | |
---|---|

1 | |

2 | New patches: |

3 | |

4 | [Fix ticket 1762 |

5 | David Benbennick <dbenbenn@gmail.com>**20071111201939] { |

6 | hunk ./Data/IntSet.hs 113 |

7 | -import QuickCheck |

8 | +import Test.QuickCheck |

9 | hunk ./Data/IntSet.hs 116 |

10 | +import qualified Data.Set as Set |

11 | hunk ./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. |

18 | hunk ./Data/IntSet.hs 413 |

19 | - | shorter m2 m1 = subsetCmpLt |

20 | + | shorter m2 m1 = case subsetCmpLt of |

21 | + GT -> GT |

22 | + _ -> LT |

23 | hunk ./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. |

26 | hunk ./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 |

69 | David Benbennick <dbenbenn@gmail.com>**20071113045358] { |

70 | hunk ./tests/all.T 5 |

71 | - |

72 | +test('dataintset001', normal, compile_and_run, ['-package containers']) |

73 | addfile ./tests/dataintset001.hs |

74 | hunk ./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] |

86 | addfile ./tests/dataintset001.stdout |

87 | hunk ./tests/dataintset001.stdout 1 |

88 | +True |

89 | } |

90 | |

91 | Context: |

92 | |

93 | [Specify build-type: Simple |

94 | Duncan Coutts <duncan@haskell.org>**20071018125404] |

95 | [Add a boring file |

96 | Ian Lynagh <igloo@earth.li>**20070913204647] |

97 | [TAG 2007-09-13 |

98 | Ian Lynagh <igloo@earth.li>**20070913215901] |

99 | Patch bundle hash: |

100 | 14737998e2fca643fc53bcac37a8d9c03b5e7af2 |