Fix power of 2 validity check. (#505)
authorMatt Renaud <matt@m-renaud.com>
Mon, 22 Jan 2018 17:31:29 +0000 (09:31 -0800)
committerDavid Feuer <David.Feuer@gmail.com>
Mon, 22 Jan 2018 17:31:29 +0000 (12:31 -0500)
Previously an incorrect check of divisible by 2 was being performed, this fixes
the behaviour.

Data/IntMap/Internal.hs
tests/IntMapValidity.hs
tests/IntSetValidity.hs

index a2ff125..2ec52fb 100644 (file)
@@ -359,6 +359,8 @@ data IntMap a = Bin {-# UNPACK #-} !Prefix
 --   mask: The switching bit to determine if a key should follow the left
 --         or right subtree of a 'Bin'.
 -- Invariant: Nil is never found as a child of Bin.
+-- Invariant: The Mask is a power of 2. It is the largest bit position at which
+--            two keys of the map differ.
 -- Invariant: Prefix is the common high-order bits that all elements share to
 --            the left of the Mask bit.
 -- Invariant: In Bin prefix mask left right, left consists of the elements that
index f33e128..a831779 100644 (file)
@@ -3,6 +3,7 @@ module IntMapValidity (valid) where
 import Data.Bits (xor, (.&.))
 import Data.IntMap.Internal
 import Test.QuickCheck (Property, counterexample, property, (.&&.))
+import Utils.Containers.Internal.BitUtil (bitcount)
 
 {--------------------------------------------------------------------
   Assertions
@@ -28,6 +29,16 @@ nilNeverChildOfBin t =
         Tip _ _ -> True
         Bin _ _ l' r' -> noNilInSet l' && noNilInSet r'
 
+-- Invariant: The Mask is a power of 2. It is the largest bit position at which
+--            two keys of the map differ.
+maskPowerOfTwo :: IntMap a -> Bool
+maskPowerOfTwo t =
+  case t of
+    Nil -> True
+    Tip _ _ -> True
+    Bin _ m l r ->
+      bitcount 0 (fromIntegral m) == 1 && maskPowerOfTwo l && maskPowerOfTwo r
+
 -- Invariant: Prefix is the common high-order bits that all elements share to
 --            the left of the Mask bit.
 commonPrefix :: IntMap a -> Bool
index 3f8c2c2..d228e7c 100644 (file)
@@ -4,6 +4,7 @@ module IntSetValidity (valid) where
 import Data.Bits (xor, (.&.))
 import Data.IntSet.Internal
 import Test.QuickCheck (Property, counterexample, property, (.&&.))
+import Utils.Containers.Internal.BitUtil (bitcount)
 
 {--------------------------------------------------------------------
   Assertions
@@ -39,7 +40,7 @@ maskPowerOfTwo t =
     Nil -> True
     Tip _ _ -> True
     Bin _ m l r ->
-      (m `mod` 2 == 0) && maskPowerOfTwo l && maskPowerOfTwo r
+      bitcount 0 (fromIntegral m) == 1 && maskPowerOfTwo l && maskPowerOfTwo r
 
 -- Invariant: Prefix is the common high-order bits that all elements share to
 --            the left of the Mask bit.