hw-rankselect-base 0.3.2.4 → 0.3.3.0

raw patch · 9 files changed

+83/−2 lines, 9 filesdep +bitvecdep ~QuickCheckdep ~hw-bitsPVP ok

version bump matches the API change (PVP)

Dependencies added: bitvec

Dependency ranges changed: QuickCheck, hw-bits

API changes (from Hackage documentation)

Files

• hw-rankselect-base.cabal +5/−2
• src/HaskellWorks/Data/RankSelect/Base/Rank0.hs +11/−0
• src/HaskellWorks/Data/RankSelect/Base/Rank1.hs +11/−0
• src/HaskellWorks/Data/RankSelect/Base/Select0.hs +13/−0
• src/HaskellWorks/Data/RankSelect/Base/Select1.hs +13/−0
• test/HaskellWorks/Data/RankSelect/Base/Rank0Spec.hs +7/−0
• test/HaskellWorks/Data/RankSelect/Base/Rank1Spec.hs +5/−0
• test/HaskellWorks/Data/RankSelect/Base/Select0Spec.hs +9/−0
• test/HaskellWorks/Data/RankSelect/Base/Select1Spec.hs +9/−0

@@ -1,7 +1,7 @@ cabal-version: 2.2  name:                   hw-rankselect-base-version:                0.3.2.4+version:                0.3.3.0 synopsis:               Rank-select base description:            Please see README.md category:               Data, Bit, Succinct Data Structures, Data Structures@@ -29,10 +29,11 @@  common QuickCheck                     { build-depends: QuickCheck                     >= 2.10       && < 2.14   } common bits-extra                     { build-depends: bits-extra                     >= 0.0.0.4    && < 0.1    }+common bitvec                         { build-depends: bitvec                         >= 1.0        && < 1.1    } common criterion                      { build-depends: criterion                      >= 1.2        && < 1.6    } common hedgehog                       { build-depends: hedgehog                       >= 0.6        && < 1.1    } common hspec                          { build-depends: hspec                          >= 2.2        && < 3      }-common hw-bits                        { build-depends: hw-bits                        >= 0.7.0.2    && < 0.8    }+common hw-bits                        { build-depends: hw-bits                        >= 0.7.1.0    && < 0.8    } common hw-hedgehog                    { build-depends: hw-hedgehog                    >= 0.1        && < 0.2    } common hw-hspec-hedgehog              { build-depends: hw-hspec-hedgehog              >= 0.1        && < 0.2    } common hw-int                         { build-depends: hw-int                         >= 0.0.0.1    && < 0.1    }@@ -50,6 +51,7 @@ library   import:               base, config                       , bits-extra+                      , bitvec                       , hw-bits                       , hw-int                       , hw-prim@@ -71,6 +73,7 @@   import:               base, config                       , QuickCheck                       , bits-extra+                      , bitvec                       , hedgehog                       , hspec                       , hw-bits

@@ -15,8 +15,11 @@ import HaskellWorks.Data.RankSelect.Base.Rank1   as X import Prelude                                   as P +import qualified Data.Bit             as Bit+import qualified Data.Bit.ThreadSafe  as BitTS import qualified Data.Vector          as DV import qualified Data.Vector.Storable as DVS+import qualified Data.Vector.Unboxed  as DVU  {-# ANN module ("HLint: Ignore Reduce duplication"  :: String) #-} @@ -131,4 +134,12 @@     where (q, r)    = if p < 1 then (0, 0) else ((p - 1) `quot` elemFixedBitSize v, ((p - 1) `rem` elemFixedBitSize v) + 1)           prefix    = DVS.take (fromIntegral q) v           maybeElem = v !!! fromIntegral q+  {-# INLINE rank0 #-}++instance Rank0 (DVU.Vector Bit.Bit) where+  rank0 v p = p - rank1 v p+  {-# INLINE rank0 #-}++instance Rank0 (DVU.Vector BitTS.Bit) where+  rank0 v p = p - rank1 v p   {-# INLINE rank0 #-}

@@ -15,8 +15,11 @@ import HaskellWorks.Data.Bits.PopCount.PopCount1 import HaskellWorks.Data.Positioning +import qualified Data.Bit             as Bit+import qualified Data.Bit.ThreadSafe  as BitTS import qualified Data.Vector          as DV import qualified Data.Vector.Storable as DVS+import qualified Data.Vector.Unboxed  as DVU  {-# ANN module ("HLint: Ignore Reduce duplication"  :: String) #-} @@ -116,3 +119,11 @@           prefix    = DVS.take (fromIntegral q) v           maybeElem = v !!! fromIntegral q   {-# INLINABLE rank1 #-}++instance Rank1 (DVU.Vector Bit.Bit) where+  rank1 v p = fromIntegral (Bit.countBits (DVU.take (fromIntegral p) v))+  {-# INLINE rank1 #-}++instance Rank1 (DVU.Vector BitTS.Bit) where+  rank1 v p = fromIntegral (BitTS.countBits (DVU.take (fromIntegral p) v))+  {-# INLINE rank1 #-}

@@ -15,8 +15,11 @@ import HaskellWorks.Data.Positioning import HaskellWorks.Data.RankSelect.Base.Select1 +import qualified Data.Bit             as Bit+import qualified Data.Bit.ThreadSafe  as BitTS import qualified Data.Vector          as DV import qualified Data.Vector.Storable as DVS+import qualified Data.Vector.Unboxed  as DVU  {-# ANN module ("HLint: ignore Reduce duplication"  :: String) #-} @@ -160,4 +163,14 @@             case popCount0 w of               pc | d <= pc  -> select0 w d + acc               pc -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)+  {-# INLINABLE select0 #-}++instance Select0 (DVU.Vector Bit.Bit) where+  select0 _ 0 = 0+  select0 v p = fromIntegral $ maybe (DVU.length v) (+ 1) $ Bit.nthBitIndex (Bit.Bit False) (fromIntegral p) v+  {-# INLINABLE select0 #-}++instance Select0 (DVU.Vector BitTS.Bit) where+  select0 _ 0 = 0+  select0 v p = fromIntegral $ maybe (DVU.length v) (+ 1) $ BitTS.nthBitIndex (BitTS.Bit False) (fromIntegral p) v   {-# INLINABLE select0 #-}

@@ -19,8 +19,11 @@ import HaskellWorks.Data.RankSelect.Base.Internal import Prelude +import qualified Data.Bit             as Bit+import qualified Data.Bit.ThreadSafe  as BitTS import qualified Data.Vector          as DV import qualified Data.Vector.Storable as DVS+import qualified Data.Vector.Unboxed  as DVU  class Select1 v where   select1 :: v -> Count -> Count@@ -158,4 +161,14 @@                 then select1 w d + acc                 else go ws (d - pc) (acc + bitCount w)             [] -> acc+  {-# INLINE select1 #-}++instance Select1 (DVU.Vector Bit.Bit) where+  select1 _ 0 = 0+  select1 v p = fromIntegral $ maybe (DVU.length v) (+ 1) $ Bit.nthBitIndex (Bit.Bit True) (fromIntegral p) v+  {-# INLINE select1 #-}++instance Select1 (DVU.Vector BitTS.Bit) where+  select1 _ 0 = 0+  select1 v p = fromIntegral $ maybe (DVU.length v) (+ 1) $ BitTS.nthBitIndex (BitTS.Bit True) (fromIntegral p) v   {-# INLINE select1 #-}

@@ -20,8 +20,11 @@ import Hedgehog import Test.Hspec +import qualified Data.Bit             as Bit+import qualified Data.Bit.ThreadSafe  as BitTS import qualified Data.Vector          as DV import qualified Data.Vector.Storable as DVS+import qualified Data.Vector.Unboxed  as DVU import qualified Hedgehog.Gen         as G import qualified Hedgehog.Range       as R @@ -73,6 +76,10 @@   genRank0UpTo16Spec (undefined :: DVS.Vector Word32)   genRank0UpTo8Spec (undefined :: DVS.Vector Word64)   genRank0UpTo16Spec (undefined :: DVS.Vector Word64)+  genRank0UpTo8Spec (undefined :: DVU.Vector Bit.Bit)+  genRank0UpTo16Spec (undefined :: DVU.Vector Bit.Bit)+  genRank0UpTo8Spec (undefined :: DVU.Vector BitTS.Bit)+  genRank0UpTo16Spec (undefined :: DVU.Vector BitTS.Bit)   describe "Different word sizes give the same rank0" $ do     it "when comparing Word16 and Word64 over bits 0-7" $ requireProperty $ do       i <- forAll $ G.word64 (R.linear 0 8)

@@ -20,8 +20,11 @@ import Hedgehog import Test.Hspec +import qualified Data.Bit             as Bit+import qualified Data.Bit.ThreadSafe  as BitTS import qualified Data.Vector          as DV import qualified Data.Vector.Storable as DVS+import qualified Data.Vector.Unboxed  as DVU import qualified Hedgehog.Gen         as G import qualified Hedgehog.Range       as R @@ -65,6 +68,8 @@   genRank1UpTo16Spec (undefined :: DVS.Vector Word32)   genRank1UpTo8Spec (undefined :: DVS.Vector Word64)   genRank1UpTo16Spec (undefined :: DVS.Vector Word64)+  genRank1UpTo16Spec (undefined :: DVU.Vector Bit.Bit)+  genRank1UpTo16Spec (undefined :: DVU.Vector BitTS.Bit)   describe "For Word8-Word64" $ do     it "rank1 for Word16 and Word64 should give same answer for bits 0-7" $ requireProperty $ do       i <- forAll $ G.word64 (R.linear 0 8)

@@ -21,8 +21,11 @@ import Hedgehog import Test.Hspec +import qualified Data.Bit             as Bit+import qualified Data.Bit.ThreadSafe  as BitTS import qualified Data.Vector          as DV import qualified Data.Vector.Storable as DVS+import qualified Data.Vector.Unboxed  as DVU import qualified Hedgehog.Gen         as G import qualified Hedgehog.Range       as R @@ -100,6 +103,12 @@   genSelect0UpTo8Spec  (undefined :: DVS.Vector Word64)   genSelect0UpTo16Spec (undefined :: DVS.Vector Word64)   genSelect0UpTo32Spec (undefined :: DVS.Vector Word64)+  genSelect0UpTo8Spec  (undefined :: DVU.Vector Bit.Bit)+  genSelect0UpTo16Spec (undefined :: DVU.Vector Bit.Bit)+  genSelect0UpTo32Spec (undefined :: DVU.Vector Bit.Bit)+  genSelect0UpTo8Spec  (undefined :: DVU.Vector BitTS.Bit)+  genSelect0UpTo16Spec (undefined :: DVU.Vector BitTS.Bit)+  genSelect0UpTo32Spec (undefined :: DVU.Vector BitTS.Bit)   describe "For Word8-Word64" $ do     it "rank0 for Word16 and Word64 should give same answer for bits 0-7" $ requireProperty $ do       i <- forAll $ G.word64 (R.linear 0 8)

@@ -21,8 +21,11 @@ import Hedgehog import Test.Hspec +import qualified Data.Bit             as Bit+import qualified Data.Bit.ThreadSafe  as BitTS import qualified Data.Vector          as DV import qualified Data.Vector.Storable as DVS+import qualified Data.Vector.Unboxed  as DVU import qualified Hedgehog.Gen         as G import qualified Hedgehog.Range       as R @@ -91,6 +94,12 @@   genSelect1UpTo8Spec  (undefined :: DVS.Vector Word64)   genSelect1UpTo16Spec (undefined :: DVS.Vector Word64)   genSelect1UpTo32Spec (undefined :: DVS.Vector Word64)+  genSelect1UpTo8Spec  (undefined :: DVU.Vector Bit.Bit)+  genSelect1UpTo16Spec (undefined :: DVU.Vector Bit.Bit)+  genSelect1UpTo32Spec (undefined :: DVU.Vector Bit.Bit)+  genSelect1UpTo8Spec  (undefined :: DVU.Vector BitTS.Bit)+  genSelect1UpTo16Spec (undefined :: DVU.Vector BitTS.Bit)+  genSelect1UpTo32Spec (undefined :: DVU.Vector BitTS.Bit)   describe "For Word64" $ do     it "rank1 for Word16 and Word64 should give same answer for bits 0-7" $ requireProperty $ do       i <- forAll $ G.word64 (R.linear 0 8)