packages feed

hw-rankselect-base 0.3.4.0 → 0.3.4.1

raw patch · 13 files changed

+135/−49 lines, 13 filesdep ~bitvecdep ~criteriondep ~doctestPVP ok

version bump matches the API change (PVP)

Dependency ranges changed: bitvec, criterion, doctest, hedgehog, hw-int, vector

API changes (from Hackage documentation)

Files

hw-rankselect-base.cabal view
@@ -1,7 +1,7 @@ cabal-version: 2.2  name:                   hw-rankselect-base-version:                0.3.4.0+version:                0.3.4.1 synopsis:               Rank-select base description:            Please see README.md category:               Data, Bit, Succinct Data Structures, Data Structures@@ -116,7 +116,7 @@                       , doctest-discover                       , hw-rankselect-base   type:                 exitcode-stdio-1.0-  ghc-options:          -threaded+  ghc-options:          -threaded -rtsopts -with-rtsopts=-N   main-is:              DoctestDriver.hs   HS-Source-Dirs:       doctest   build-tool-depends:   doctest-discover:doctest-discover
src/HaskellWorks/Data/RankSelect/Base.hs view
@@ -2,7 +2,7 @@     ( module X     ) where -import           HaskellWorks.Data.RankSelect.Base.Rank0   as X-import           HaskellWorks.Data.RankSelect.Base.Rank1   as X-import           HaskellWorks.Data.RankSelect.Base.Select0 as X-import           HaskellWorks.Data.RankSelect.Base.Select1 as X+import HaskellWorks.Data.RankSelect.Base.Rank0   as X+import HaskellWorks.Data.RankSelect.Base.Rank1   as X+import HaskellWorks.Data.RankSelect.Base.Select0 as X+import HaskellWorks.Data.RankSelect.Base.Select1 as X
src/HaskellWorks/Data/RankSelect/Base/Rank.hs view
@@ -11,7 +11,12 @@ import HaskellWorks.Data.RankSelect.Base.Rank1  class Eq a => Rank v a where-  rank :: a -> v -> Count -> Count+  -- | Find the number of occurences of the given symbol in the prefix of the supplied bitstring of the given length+  rank+    :: a      -- ^ The symbol+    -> v      -- ^ The bitstring+    -> Count  -- ^ The prefix length+    -> Count  instance Rank [Bool] Bool where   rank a = if a then rank1 else rank0
src/HaskellWorks/Data/RankSelect/Base/Rank0.hs view
@@ -21,10 +21,28 @@ import qualified Data.Vector.Storable as DVS import qualified Data.Vector.Unboxed  as DVU -{-# ANN module ("HLint: ignore Reduce duplication"  :: String) #-}+{- HLINT ignore "Reduce duplication"  -}  class Rank0 v where-  rank0 :: v -> Count -> Count+  -- | Find the number of occurences of the bit @0@ in the prefix of the supplied bitstring of the given length+  --+  -- >>> import HaskellWorks.Data.Bits.BitRead+  -- >>> :set -XTypeApplications+  --+  -- >>> rank0 (unsafeBitRead @Word8 "11111111") 4+  -- 0+  -- >>> rank0 (unsafeBitRead @Word8 "00111111") 4+  -- 2+  -- >>> rank0 (unsafeBitRead @Word8 "10011111") 4+  -- 2+  -- >>> rank0 (unsafeBitRead @Word8 "10011001") 4+  -- 2+  -- >>> rank0 (unsafeBitRead @Word8 "10011001") 6+  -- 3+  rank0+    :: v      -- ^ The bitstring+    -> Count  -- ^ The prefix length+    -> Count  deriving instance Rank0 a => Rank0 (BitShown a)
src/HaskellWorks/Data/RankSelect/Base/Rank1.hs view
@@ -21,10 +21,28 @@ import qualified Data.Vector.Storable as DVS import qualified Data.Vector.Unboxed  as DVU -{-# ANN module ("HLint: ignore Reduce duplication"  :: String) #-}+{- HLINT ignore "Reduce duplication"  -}  class Rank1 v where-  rank1 :: v -> Count -> Count+  -- | Find the number of occurences of the bit @1@ in the prefix of the supplied bitstring of the given length+  --+  -- >>> import HaskellWorks.Data.Bits.BitRead+  -- >>> :set -XTypeApplications+  --+  -- >>> rank1 (unsafeBitRead @Word8 "00000000") 4+  -- 0+  -- >>> rank1 (unsafeBitRead @Word8 "11000000") 4+  -- 2+  -- >>> rank1 (unsafeBitRead @Word8 "01100000") 4+  -- 2+  -- >>> rank1 (unsafeBitRead @Word8 "01100110") 4+  -- 2+  -- >>> rank1 (unsafeBitRead @Word8 "01100110") 6+  -- 3+  rank1+    :: v      -- ^ The bitstring+    -> Count  -- ^ The prefix length+    -> Count  deriving instance Rank1 a => Rank1 (BitShown a)
src/HaskellWorks/Data/RankSelect/Base/Select.hs view
@@ -11,7 +11,12 @@ import HaskellWorks.Data.RankSelect.Base.Select1  class Eq a => Select v a where-  select :: a -> v -> Count -> Count+  -- | Find length of the shortest prefix of the given prefix that contains specified number of occurences of the given symbol+  select+    :: a      -- ^ The symbol+    -> v      -- ^ The bitstring+    -> Count  -- ^ The number of occurences+    -> Count  instance Select [Bool] Bool where   select a = if a then select1 else select0
src/HaskellWorks/Data/RankSelect/Base/Select0.hs view
@@ -21,10 +21,30 @@ import qualified Data.Vector.Storable as DVS import qualified Data.Vector.Unboxed  as DVU -{-# ANN module ("HLint: ignore Reduce duplication"  :: String) #-}+{- HLINT ignore "Reduce duplication"  -}  class Select0 v where-  select0 :: v -> Count -> Count+  -- | Find length of the shortest prefix of the given prefix that contains specified number of occurences of the bit @1@+  --+  -- If the bitstring does not have enough occurences of bit @0@ is insufficient to satisfy the query the result is undefined.+  --+  -- >>> import HaskellWorks.Data.Bits.BitRead+  -- >>> :set -XTypeApplications+  --+  -- >>> select0 (unsafeBitRead @Word8 "11111111") 0+  -- 0+  -- >>> select0 (unsafeBitRead @Word8 "11110111") 1+  -- 5+  -- >>> select0 (unsafeBitRead @Word8 "00000000") 4+  -- 4+  -- >>> select0 (unsafeBitRead @Word8 "11000000") 4+  -- 6+  -- >>> select0 (unsafeBitRead @Word8 "01100000") 4+  -- 6+  select0+    :: v      -- ^ The bitstring+    -> Count  -- ^ The number of zeros+    -> Count  deriving instance Select0 a => Select0 (BitShown a) @@ -59,8 +79,8 @@           go _ 0  acc = acc           go u d acc = let w = head u in             case popCount0 w of-              pc | d <= pc  -> select0 w d + acc-              pc -> go (tail u) (d - pc) (acc + elemFixedBitSize u)+              pc | d <= pc -> select0 w d + acc+              pc           -> go (tail u) (d - pc) (acc + elemFixedBitSize u)   {-# INLINABLE select0 #-}  instance Select0 [Word16] where@@ -69,8 +89,8 @@           go _ 0  acc = acc           go u d acc = let w = head u in             case popCount0 w of-              pc | d <= pc  -> select0 w d + acc-              pc -> go (tail u) (d - pc) (acc + elemFixedBitSize u)+              pc | d <= pc -> select0 w d + acc+              pc           -> go (tail u) (d - pc) (acc + elemFixedBitSize u)   {-# INLINABLE select0 #-}  instance Select0 [Word32] where@@ -79,8 +99,8 @@           go _ 0  acc = acc           go u d acc = let w = head u in             case popCount0 w of-              pc | d <= pc  -> select0 w d + acc-              pc -> go (tail u) (d - pc) (acc + elemFixedBitSize u)+              pc | d <= pc -> select0 w d + acc+              pc           -> go (tail u) (d - pc) (acc + elemFixedBitSize u)   {-# INLINABLE select0 #-}  instance Select0 [Word64] where@@ -89,8 +109,8 @@           go _ 0  acc = acc           go u d acc = let w = head u in             case popCount0 w of-              pc | d <= pc  -> select0 w d + acc-              pc -> go (tail u) (d - pc) (acc + elemFixedBitSize u)+              pc | d <= pc -> select0 w d + acc+              pc           -> go (tail u) (d - pc) (acc + elemFixedBitSize u)   {-# INLINABLE select0 #-}  instance Select0 (DV.Vector Word8) where@@ -98,8 +118,8 @@     where go _ 0  acc = acc           go n d acc = let w = (v !!! n) in             case popCount0 w of-              pc | d <= pc  -> select0 w d + acc-              pc -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)+              pc | d <= pc -> select0 w d + acc+              pc           -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)   {-# INLINABLE select0 #-}  instance Select0 (DV.Vector Word16) where@@ -107,8 +127,8 @@     where go _ 0  acc = acc           go n d acc = let w = (v !!! n) in             case popCount0 w of-              pc | d <= pc  -> select0 w d + acc-              pc -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)+              pc | d <= pc -> select0 w d + acc+              pc           -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)   {-# INLINABLE select0 #-}  instance Select0 (DV.Vector Word32) where@@ -116,8 +136,8 @@     where go _ 0  acc = acc           go n d acc = let w = (v !!! n) in             case popCount0 w of-              pc | d <= pc  -> select0 w d + acc-              pc -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)+              pc | d <= pc -> select0 w d + acc+              pc           -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)   {-# INLINABLE select0 #-}  instance Select0 (DV.Vector Word64) where@@ -125,8 +145,8 @@     where go _ 0  acc = acc           go n d acc = let w = (v !!! n) in             case popCount0 w of-              pc | d <= pc  -> select0 w d + acc-              pc -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)+              pc | d <= pc -> select0 w d + acc+              pc           -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)   {-# INLINABLE select0 #-}  instance Select0 (DVS.Vector Word8) where@@ -134,8 +154,8 @@     where go _ 0  acc = acc           go n d acc = let w = (v !!! n) in             case popCount0 w of-              pc | d <= pc  -> select0 w d + acc-              pc -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)+              pc | d <= pc -> select0 w d + acc+              pc           -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)   {-# INLINABLE select0 #-}  instance Select0 (DVS.Vector Word16) where@@ -143,8 +163,8 @@     where go _ 0  acc = acc           go n d acc = let w = (v !!! n) in             case popCount0 w of-              pc | d <= pc  -> select0 w d + acc-              pc -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)+              pc | d <= pc -> select0 w d + acc+              pc           -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)   {-# INLINABLE select0 #-}  instance Select0 (DVS.Vector Word32) where@@ -152,8 +172,8 @@     where go _ 0  acc = acc           go n d acc = let w = (v !!! n) in             case popCount0 w of-              pc | d <= pc  -> select0 w d + acc-              pc -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)+              pc | d <= pc -> select0 w d + acc+              pc           -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)   {-# INLINABLE select0 #-}  instance Select0 (DVS.Vector Word64) where@@ -161,8 +181,8 @@     where go _ 0  acc = acc           go n d acc = let w = (v !!! n) in             case popCount0 w of-              pc | d <= pc  -> select0 w d + acc-              pc -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)+              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
src/HaskellWorks/Data/RankSelect/Base/Select1.hs view
@@ -26,7 +26,27 @@ import qualified Data.Vector.Unboxed  as DVU  class Select1 v where-  select1 :: v -> Count -> Count+  -- | Find length of the shortest prefix of the given prefix that contains specified number of occurences of the bit @1@+  --+  -- If the bitstring does not have enough occurences of bit @1@ is insufficient to satisfy the query the result is undefined.+  --+  -- >>> import HaskellWorks.Data.Bits.BitRead+  -- >>> :set -XTypeApplications+  --+  -- >>> select1 (unsafeBitRead @Word8 "00000000") 0+  -- 0+  -- >>> select1 (unsafeBitRead @Word8 "00001000") 1+  -- 5+  -- >>> select1 (unsafeBitRead @Word8 "11111111") 4+  -- 4+  -- >>> select1 (unsafeBitRead @Word8 "00111111") 4+  -- 6+  -- >>> select1 (unsafeBitRead @Word8 "10011111") 4+  -- 6+  select1+    :: v      -- ^ The bitstring+    -> Count  -- ^ The number of ones+    -> Count  deriving instance Select1 a => Select1 (BitShown a)
test/HaskellWorks/Data/RankSelect/Base/InternalSpec.hs view
@@ -12,8 +12,8 @@ import qualified Hedgehog.Gen   as G import qualified Hedgehog.Range as R -{-# ANN module ("HLint: ignore Redundant do"        :: String) #-}-{-# ANN module ("HLint: ignore Reduce duplication"  :: String) #-}+{- HLINT ignore "Redundant do"        -}+{- HLINT ignore "Reduce duplication"  -}  spec :: Spec spec = describe "HaskellWorks.Data.RankSelect.Base.InternalSpec" $ do
test/HaskellWorks/Data/RankSelect/Base/Rank0Spec.hs view
@@ -28,8 +28,8 @@ import qualified Hedgehog.Gen         as G import qualified Hedgehog.Range       as R -{-# ANN module ("HLint: ignore Redundant do"        :: String) #-}-{-# ANN module ("HLint: ignore Reduce duplication"  :: String) #-}+{- HLINT ignore "Redundant do"        -}+{- HLINT ignore "Reduce duplication"  -}  genRank0UpTo8Spec :: forall s. (Typeable s, BitRead s, Rank0 s) => s -> Spec genRank0UpTo8Spec _ = describe ("Generically up to 8 bits for " ++ show (typeOf (undefined :: s))) $ do
test/HaskellWorks/Data/RankSelect/Base/Rank1Spec.hs view
@@ -28,8 +28,8 @@ import qualified Hedgehog.Gen         as G import qualified Hedgehog.Range       as R -{-# ANN module ("HLint: ignore Redundant do"        :: String) #-}-{-# ANN module ("HLint: ignore Reduce duplication"  :: String) #-}+{- HLINT ignore "Redundant do"        -}+{- HLINT ignore "Reduce duplication"  -}  genRank1UpTo8Spec :: forall s. (Typeable s, BitRead s, Rank1 s) => s -> Spec genRank1UpTo8Spec _ = describe ("Generically up to 8 bits for " ++ show (typeOf (undefined :: s))) $ do
test/HaskellWorks/Data/RankSelect/Base/Select0Spec.hs view
@@ -29,8 +29,8 @@ import qualified Hedgehog.Gen         as G import qualified Hedgehog.Range       as R -{-# ANN module ("HLint: ignore Redundant do"        :: String) #-}-{-# ANN module ("HLint: ignore Reduce duplication"  :: String) #-}+{- HLINT ignore "Redundant do"        -}+{- HLINT ignore "Reduce duplication"  -}  genSelect0UpTo8Spec :: forall s. (Typeable s, BitRead s, Select0 s) => s -> Spec genSelect0UpTo8Spec _ = describe ("Generically up to 8 bits for " ++ show (typeOf (undefined :: s))) $ do
test/HaskellWorks/Data/RankSelect/Base/Select1Spec.hs view
@@ -29,8 +29,8 @@ import qualified Hedgehog.Gen         as G import qualified Hedgehog.Range       as R -{-# ANN module ("HLint: ignore Redundant do"        :: String) #-}-{-# ANN module ("HLint: ignore Reduce duplication"  :: String) #-}+{- HLINT ignore "Redundant do"        -}+{- HLINT ignore "Reduce duplication"  -}  genSelect1UpTo8Spec :: forall s. (Typeable s, BitRead s, Select1 s) => s -> Spec genSelect1UpTo8Spec _ = describe ("Generically up to 8 bits for " ++ show (typeOf (undefined :: s))) $ do