hw-succinct 0.0.0.8 → 0.0.0.9
raw patch · 15 files changed
+40/−934 lines, 15 filesPVP: major bump suggested
API removals or changes: PVP suggests a major version bump
API changes (from Hackage documentation)
- HaskellWorks.Data.Json.Succinct.Cursor: depth :: (BalancedParens u, Rank1 u, Rank0 u) => JsonCursor t v u -> Count
- HaskellWorks.Data.Json.Succinct.Cursor: firstChild :: JsonCursor t v u -> JsonCursor t v u
- HaskellWorks.Data.Json.Succinct.Cursor: nextSibling :: BalancedParens u => JsonCursor t v u -> JsonCursor t v u
- HaskellWorks.Data.Json.Succinct.Cursor: parent :: BalancedParens u => JsonCursor t v u -> JsonCursor t v u
- HaskellWorks.Data.Json.Succinct.Cursor: subtreeSize :: BalancedParens u => JsonCursor t v u -> Count
+ HaskellWorks.Data.Json.Succinct.Cursor.Internal: instance (HaskellWorks.Data.Succinct.BalancedParens.Internal.BalancedParens u, HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1.Rank1 u, HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank0.Rank0 u) => HaskellWorks.Data.TreeCursor.TreeCursor (HaskellWorks.Data.Json.Succinct.Cursor.Internal.JsonCursor t v u)
Files
- hw-succinct.cabal +2/−13
- src/HaskellWorks/Data/Json/Succinct/Cursor.hs +0/−23
- src/HaskellWorks/Data/Json/Succinct/Cursor/Internal.hs +18/−0
- test/HaskellWorks/Data/Bits/BitReadSpec.hs +0/−49
- test/HaskellWorks/Data/Bits/BitWiseSpec.hs +0/−68
- test/HaskellWorks/Data/Json/Succinct/CursorSpec.hs +20/−18
- test/HaskellWorks/Data/Succinct/BalancedParensSpec.hs +0/−98
- test/HaskellWorks/Data/Succinct/RankSelect/Binary/Basic/Rank0Spec.hs +0/−90
- test/HaskellWorks/Data/Succinct/RankSelect/Binary/Basic/Rank1Spec.hs +0/−89
- test/HaskellWorks/Data/Succinct/RankSelect/Binary/Basic/Select0Spec.hs +0/−116
- test/HaskellWorks/Data/Succinct/RankSelect/Binary/Basic/Select1Spec.hs +0/−122
- test/HaskellWorks/Data/Succinct/RankSelect/Binary/BasicGen.hs +0/−31
- test/HaskellWorks/Data/Succinct/RankSelect/Binary/Poppy512Spec.hs +0/−131
- test/HaskellWorks/Data/Succinct/RankSelect/InternalSpec.hs +0/−34
- test/HaskellWorks/Data/Succinct/SimpleSpec.hs +0/−52
hw-succinct.cabal view
@@ -1,5 +1,5 @@ name: hw-succinct-version: 0.0.0.8+version: 0.0.0.9 synopsis: Conduits for tokenizing streams. description: Please see README.md homepage: http://github.com/haskell-works/hw-succinct#readme@@ -66,20 +66,9 @@ type: exitcode-stdio-1.0 hs-source-dirs: test main-is: Spec.hs- other-modules: HaskellWorks.Data.Bits.BitReadSpec- , HaskellWorks.Data.Bits.BitWiseSpec- , HaskellWorks.Data.Json.Final.TokenizeSpec+ other-modules: HaskellWorks.Data.Json.Final.TokenizeSpec , HaskellWorks.Data.Json.Succinct.CursorSpec , HaskellWorks.Data.Json.Succinct.Cursor.InterestBitsSpec- , HaskellWorks.Data.Succinct.BalancedParensSpec- , HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank0Spec- , HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1Spec- , HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Select0Spec- , HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Select1Spec- , HaskellWorks.Data.Succinct.RankSelect.Binary.BasicGen- , HaskellWorks.Data.Succinct.RankSelect.Binary.Poppy512Spec- , HaskellWorks.Data.Succinct.RankSelect.InternalSpec- , HaskellWorks.Data.Succinct.SimpleSpec build-depends: base , attoparsec , bytestring
src/HaskellWorks/Data/Json/Succinct/Cursor.hs view
@@ -6,11 +6,6 @@ module HaskellWorks.Data.Json.Succinct.Cursor ( module X , jsonTokenAt- , firstChild- , nextSibling- , parent- , depth- , subtreeSize ) where import qualified Data.Attoparsec.ByteString.Char8 as ABC@@ -19,8 +14,6 @@ import HaskellWorks.Data.Json.Succinct.Cursor.CursorType as X import HaskellWorks.Data.Json.Succinct.Cursor.Internal as X import HaskellWorks.Data.Positioning-import qualified HaskellWorks.Data.Succinct.BalancedParens as BP-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank0 import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1 import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Select1 import HaskellWorks.Data.Vector.VectorLike@@ -30,19 +23,3 @@ ABC.Fail {} -> error "Failed to parse token in cursor" ABC.Partial _ -> error "Failed to parse token in cursor" ABC.Done _ r -> r--firstChild :: JsonCursor t v u -> JsonCursor t v u-firstChild k = k { cursorRank = BP.firstChild (balancedParens k) (cursorRank k) }--nextSibling :: BP.BalancedParens u => JsonCursor t v u -> JsonCursor t v u-nextSibling k = k { cursorRank = BP.nextSibling (balancedParens k) (cursorRank k) }--parent :: BP.BalancedParens u => JsonCursor t v u -> JsonCursor t v u-parent k = k { cursorRank = BP.parent (balancedParens k) (cursorRank k) }--depth :: (BP.BalancedParens u, Rank1 u, Rank0 u) => JsonCursor t v u -> Count-depth k = BP.depth (balancedParens k) (cursorRank k)--subtreeSize :: BP.BalancedParens u => JsonCursor t v u -> Count-subtreeSize k = BP.subtreeSize (balancedParens k) (cursorRank k)-
src/HaskellWorks/Data/Json/Succinct/Cursor/Internal.hs view
@@ -22,7 +22,10 @@ import HaskellWorks.Data.Json.Succinct.Cursor.InterestBits import HaskellWorks.Data.Positioning import HaskellWorks.Data.Succinct.BalancedParens as BP+import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank0+import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1 import HaskellWorks.Data.Succinct.RankSelect.Binary.Poppy512+import HaskellWorks.Data.TreeCursor data JsonCursor t v w = JsonCursor { cursorText :: !t@@ -84,3 +87,18 @@ instance FromForeignRegion (JsonCursor BS.ByteString Poppy512 (SimpleBalancedParens (DVS.Vector Word64))) where fromForeignRegion (fptr, offset, size) = fromByteString (BSI.fromForeignPtr (castForeignPtr fptr) offset size) +instance (BP.BalancedParens u, Rank1 u, Rank0 u) => TreeCursor (JsonCursor t v u) where+ firstChild :: JsonCursor t v u -> JsonCursor t v u+ firstChild k = k { cursorRank = BP.firstChild (balancedParens k) (cursorRank k) }++ nextSibling :: JsonCursor t v u -> JsonCursor t v u+ nextSibling k = k { cursorRank = BP.nextSibling (balancedParens k) (cursorRank k) }++ parent :: JsonCursor t v u -> JsonCursor t v u+ parent k = k { cursorRank = BP.parent (balancedParens k) (cursorRank k) }++ depth :: JsonCursor t v u -> Count+ depth k = BP.depth (balancedParens k) (cursorRank k)++ subtreeSize :: JsonCursor t v u -> Count+ subtreeSize k = BP.subtreeSize (balancedParens k) (cursorRank k)
− test/HaskellWorks/Data/Bits/BitReadSpec.hs
@@ -1,49 +0,0 @@-{-# OPTIONS_GHC -fno-warn-incomplete-patterns #-}-{-# LANGUAGE ScopedTypeVariables #-}--module HaskellWorks.Data.Bits.BitReadSpec (spec) where--import GHC.Exts-import qualified Data.Vector as DV-import Data.Word-import HaskellWorks.Data.Bits.BitRead-import HaskellWorks.Data.Bits.BitShow-import Test.Hspec--{-# ANN module ("HLint: ignore Redundant do" :: String) #-}--spec :: Spec-spec = describe "HaskellWorks.Data.BitReadSpec" $ do- it "bitRead \"10000000 101\" :: Maybe [Word8]" $- let w = bitRead "10000000 101" :: Maybe [Bool] in- w `shouldBe` Just [True, False, False, False, False, False, False, False, True, False, True]- it "bitRead \"10000000 101\" :: Maybe [Word8]"$- let w = bitRead "10000000 101" :: Maybe [Word8] in- w `shouldBe` Just [1, 5]- it "bitRead \"11100100 10101111 1\" :: Maybe [Word8]" $- let ws = bitRead "11100100 10101111 1" :: Maybe [Word8] in- ws `shouldBe` Just [39, 245, 1]- it "bitRead \"\" :: Maybe [Word8]" $- let ws = bitRead "" :: Maybe [Word8] in- ws `shouldBe` Just []- it "bitRead \"10000000 101\" :: Maybe (DV.Vector Word8)" $- let v = bitRead "10000000 101" :: Maybe (DV.Vector Word8) in- v `shouldBe` Just (fromList [1, 5])- it "bitRead \"11100100 10101111 1\" :: Maybe (DV.Vector Word8)" $- let v = bitRead "11100100 10101111 1" :: Maybe (DV.Vector Word8) in- v `shouldBe` Just (fromList [39, 245, 1])- it "bitRead \"11100100 10101111 1\" :: Maybe (DV.Vector Word16)" $- let v = bitRead "11100100 10101111 1" :: Maybe (DV.Vector Word16) in- v `shouldBe` Just (fromList [39 + 62720, 1])- it "bitRead \"\" :: Maybe (DV.Vector Word8)" $- let v = bitRead "" :: Maybe (DV.Vector Word8) in- v `shouldBe` Just (fromList [])- it "bitShow (8 :: Word8)" $- let bs = bitShow (8 :: Word8) in- bs `shouldBe` "00010000"- it "bitShow (8 :: Word64)" $- let bs = bitShow (8 :: Word64) in- bs `shouldBe` "00010000 00000000 00000000 00000000 00000000 00000000 00000000 00000000"- it "bitShow [0x0102040810204080 :: Word64]" $- let bs = bitShow [0x0102040810204080 :: Word64] in- bs `shouldBe` "00000001 00000010 00000100 00001000 00010000 00100000 01000000 10000000"
− test/HaskellWorks/Data/Bits/BitWiseSpec.hs
@@ -1,68 +0,0 @@-{-# OPTIONS_GHC -fno-warn-incomplete-patterns #-}-{-# LANGUAGE ScopedTypeVariables #-}--module HaskellWorks.Data.Bits.BitWiseSpec (spec) where--import qualified Data.Bits as B-import qualified Data.Vector.Storable as DVS-import Data.Word-import HaskellWorks.Data.Bits.BitLength-import HaskellWorks.Data.Bits.PopCount.PopCount0-import HaskellWorks.Data.Bits.PopCount.PopCount1-import Test.Hspec-import Test.QuickCheck--{-# ANN module ("HLint: ignore Redundant do" :: String) #-}--spec :: Spec-spec = describe "HaskellWorks.Data.SuccinctSpec" $ do- describe "for popCount0" $ do- it "for Word8 matches Data.Bits implementation" $ property $- \(w :: Word8 ) -> popCount0 w == bitLength w - fromIntegral (B.popCount w)- it "for Word16 matches Data.Bits implementation" $ property $- \(w :: Word16) -> popCount0 w == bitLength w - fromIntegral (B.popCount w)- it "for Word32 matches Data.Bits implementation" $ property $- \(w :: Word32) -> popCount0 w == bitLength w - fromIntegral (B.popCount w)- it "for Word64 matches Data.Bits implementation" $ property $- \(w :: Word64) -> popCount0 w == bitLength w - fromIntegral (B.popCount w)- it "for [Word8] matches Data.Bits implementation" $ property $- \(w :: [Word8] ) -> popCount0 w == bitLength w - sum (fmap (fromIntegral . B.popCount) w)- it "for [Word16] matches Data.Bits implementation" $ property $- \(w :: [Word16]) -> popCount0 w == bitLength w - sum (fmap (fromIntegral . B.popCount) w)- it "for [Word32] matches Data.Bits implementation" $ property $- \(w :: [Word32]) -> popCount0 w == bitLength w - sum (fmap (fromIntegral . B.popCount) w)- it "for [Word64] matches Data.Bits implementation" $ property $- \(w :: [Word64]) -> popCount0 w == bitLength w - sum (fmap (fromIntegral . B.popCount) w)- it "for [Word8] matches Data.Bits implementation" $ property $- \(w :: [Word8] ) -> popCount0 w == popCount0 (DVS.fromList w)- it "for [Word16] matches Data.Bits implementation" $ property $- \(w :: [Word16]) -> popCount0 w == popCount0 (DVS.fromList w)- it "for [Word32] matches Data.Bits implementation" $ property $- \(w :: [Word32]) -> popCount0 w == popCount0 (DVS.fromList w)- it "for [Word64] matches Data.Bits implementation" $ property $- \(w :: [Word64]) -> popCount0 w == popCount0 (DVS.fromList w)- describe "for popCount1" $ do- it "for Word8 matches Data.Bits implementation" $ property $- \(w :: Word8 ) -> popCount1 w == fromIntegral (B.popCount w)- it "for Word16 matches Data.Bits implementation" $ property $- \(w :: Word16) -> popCount1 w == fromIntegral (B.popCount w)- it "for Word32 matches Data.Bits implementation" $ property $- \(w :: Word32) -> popCount1 w == fromIntegral (B.popCount w)- it "for Word64 matches Data.Bits implementation" $ property $- \(w :: Word64) -> popCount1 w == fromIntegral (B.popCount w)- it "for [Word8] matches Data.Bits implementation" $ property $- \(w :: [Word8] ) -> popCount1 w == sum (fmap (fromIntegral . B.popCount) w)- it "for [Word16] matches Data.Bits implementation" $ property $- \(w :: [Word16]) -> popCount1 w == sum (fmap (fromIntegral . B.popCount) w)- it "for [Word32] matches Data.Bits implementation" $ property $- \(w :: [Word32]) -> popCount1 w == sum (fmap (fromIntegral . B.popCount) w)- it "for [Word64] matches Data.Bits implementation" $ property $- \(w :: [Word64]) -> popCount1 w == sum (fmap (fromIntegral . B.popCount) w)- it "for [Word8] matches Data.Bits implementation" $ property $- \(w :: [Word8] ) -> popCount1 w == popCount1 (DVS.fromList w)- it "for [Word16] matches Data.Bits implementation" $ property $- \(w :: [Word16]) -> popCount1 w == popCount1 (DVS.fromList w)- it "for [Word32] matches Data.Bits implementation" $ property $- \(w :: [Word32]) -> popCount1 w == popCount1 (DVS.fromList w)- it "for [Word64] matches Data.Bits implementation" $ property $- \(w :: [Word64]) -> popCount1 w == popCount1 (DVS.fromList w)
test/HaskellWorks/Data/Json/Succinct/CursorSpec.hs view
@@ -1,11 +1,14 @@-{-# LANGUAGE ExplicitForAll #-}-{-# LANGUAGE FlexibleContexts #-}-{-# LANGUAGE FlexibleInstances #-}-{-# LANGUAGE InstanceSigs #-}-{-# LANGUAGE MultiParamTypeClasses #-}-{-# LANGUAGE OverloadedStrings #-}-{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE ExplicitForAll #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE InstanceSigs #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE NoMonomorphismRestriction #-}+{-# LANGUAGE OverloadedStrings #-}+{-# LANGUAGE ScopedTypeVariables #-} +{-# OPTIONS_GHC -fno-warn-missing-signatures #-}+ module HaskellWorks.Data.Json.Succinct.CursorSpec(spec) where import qualified Data.ByteString as BS@@ -17,12 +20,13 @@ import HaskellWorks.Data.FromForeignRegion import HaskellWorks.Data.Json.Succinct.Cursor as C import HaskellWorks.Data.Json.Token-import qualified HaskellWorks.Data.Succinct.BalancedParens.Internal as BP+import HaskellWorks.Data.Succinct.BalancedParens.Internal import HaskellWorks.Data.Succinct.BalancedParens.Simple import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank0 import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1 import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Select1 import HaskellWorks.Data.Succinct.RankSelect.Binary.Poppy512+import qualified HaskellWorks.Data.TreeCursor as TC import System.IO.MMap import Test.Hspec @@ -30,11 +34,14 @@ {-# ANN module ("HLint: ignore Reduce duplication" :: String) #-} {-# ANN module ("HLint: redundant bracket" :: String) #-} +fc = TC.firstChild+ns = TC.nextSibling+pn = TC.parent+cd = TC.depth+ss = TC.subtreeSize+ spec :: Spec spec = describe "HaskellWorks.Data.Json.Succinct.CursorSpec" $ do- let fc = C.firstChild- let ns = C.nextSibling- let cd = C.depth describe "Cursor for [Bool]" $ do it "initialises to beginning of empty object" $ do let cursor = "{}" :: JsonCursor String (BitShown [Bool]) (SimpleBalancedParens [Bool])@@ -119,17 +126,12 @@ , Show u , Rank0 u , Rank1 u- , BP.BalancedParens u+ , BalancedParens u , FromForeignRegion (JsonCursor BS.ByteString t u) , IsString (JsonCursor BS.ByteString t u) , HasJsonCursorType (JsonCursor BS.ByteString t u)) => String -> (JsonCursor BS.ByteString t u) -> SpecWith () genSpec t _ = do- let fc = C.firstChild- let ns = C.nextSibling- let pn = C.parent- let cd = C.depth- let ss = C.subtreeSize describe ("Cursor for (" ++ t ++ ")") $ do it "initialises to beginning of empty object" $ do let cursor = "{}" :: JsonCursor BS.ByteString t u@@ -157,7 +159,7 @@ jsonCursorType cursor `shouldBe` JsonCursorNull it "cursor can navigate to first child of array" $ do let cursor = "[null]" :: JsonCursor BS.ByteString t u- jsonCursorType (firstChild cursor) `shouldBe` JsonCursorNull+ jsonCursorType (fc cursor) `shouldBe` JsonCursorNull it "cursor can navigate to second child of array" $ do let cursor = "[null, {\"field\": 1}]" :: JsonCursor BS.ByteString t u jsonCursorType ((ns . fc) cursor) `shouldBe` JsonCursorObject
− test/HaskellWorks/Data/Succinct/BalancedParensSpec.hs
@@ -1,98 +0,0 @@-{-# LANGUAGE ScopedTypeVariables #-}--module HaskellWorks.Data.Succinct.BalancedParensSpec where--import Data.Maybe-import qualified Data.Vector.Storable as DVS-import Data.Word-import HaskellWorks.Data.Bits.BitRead-import HaskellWorks.Data.Succinct.BalancedParens-import Test.Hspec--{-# ANN module ("HLint: ignore Redundant do" :: String) #-}-{-# ANN module ("HLint: ignore Reduce duplication" :: String) #-}--spec :: Spec-spec = describe "HaskellWorks.Data.Succinct.BalancedParensSpec" $ do- describe "For (()(()())) 1101101000" $ do- let bs = SimpleBalancedParens (91 :: Word64)- it "Test 1a" $ findClose bs 1 `shouldBe` 10- it "Test 1b" $ findClose bs 2 `shouldBe` 3- it "Test 2a" $ findOpen bs 10 `shouldBe` 1- it "Test 2b" $ findOpen bs 3 `shouldBe` 2- it "Test 3a" $ enclose bs 2 `shouldBe` 1- it "Test 3b" $ enclose bs 7 `shouldBe` 4- describe "For (()(()())) 1101101000" $ do- let bs = SimpleBalancedParens (fromJust (bitRead "1101101000") :: [Bool])- it "Test 1a" $ findClose bs 1 `shouldBe` 10- it "Test 1b" $ findClose bs 2 `shouldBe` 3- it "Test 1b" $ findClose bs 3 `shouldBe` 3- it "Test 1b" $ findClose bs 4 `shouldBe` 9- it "Test 2a" $ findOpen bs 10 `shouldBe` 1- it "Test 2b" $ findOpen bs 3 `shouldBe` 2- it "Test 3a" $ enclose bs 2 `shouldBe` 1- it "Test 3b" $ enclose bs 7 `shouldBe` 4- it "firstChild 1" $ firstChild bs 1 `shouldBe` 2- it "firstChild 4" $ firstChild bs 4 `shouldBe` 5- it "nextSibling 2" $ nextSibling bs 2 `shouldBe` 4- it "nextSibling 5" $ nextSibling bs 5 `shouldBe` 7- it "parent 2" $ parent bs 2 `shouldBe` 1- it "parent 5" $ parent bs 5 `shouldBe` 4- it "depth 1" $ depth bs 1 `shouldBe` 1- it "depth 2" $ depth bs 2 `shouldBe` 2- it "depth 3" $ depth bs 3 `shouldBe` 2- it "depth 4" $ depth bs 4 `shouldBe` 2- it "depth 5" $ depth bs 5 `shouldBe` 3- it "depth 6" $ depth bs 6 `shouldBe` 3- it "depth 7" $ depth bs 7 `shouldBe` 3- it "depth 8" $ depth bs 8 `shouldBe` 3- it "depth 9" $ depth bs 9 `shouldBe` 2- it "depth 10" $ depth bs 10 `shouldBe` 1- it "subtreeSize 1" $ subtreeSize bs 1 `shouldBe` 5- it "subtreeSize 2" $ subtreeSize bs 2 `shouldBe` 1- it "subtreeSize 3" $ subtreeSize bs 3 `shouldBe` 0- it "subtreeSize 4" $ subtreeSize bs 4 `shouldBe` 3- it "subtreeSize 5" $ subtreeSize bs 5 `shouldBe` 1- it "subtreeSize 6" $ subtreeSize bs 6 `shouldBe` 0- it "subtreeSize 7" $ subtreeSize bs 7 `shouldBe` 1- it "subtreeSize 8" $ subtreeSize bs 8 `shouldBe` 0- it "subtreeSize 9" $ subtreeSize bs 9 `shouldBe` 0- it "subtreeSize 10" $ subtreeSize bs 10 `shouldBe` 0- describe "For (()(()())) 11011010 00000000 :: DVS.Vector Word8" $ do- let bs = SimpleBalancedParens (fromJust (bitRead "11011010 00000000") :: DVS.Vector Word8)- it "Test 1a" $ findClose bs 1 `shouldBe` 10- it "Test 1b" $ findClose bs 2 `shouldBe` 3- it "Test 1b" $ findClose bs 3 `shouldBe` 3- it "Test 1b" $ findClose bs 4 `shouldBe` 9- it "Test 2a" $ findOpen bs 10 `shouldBe` 1- it "Test 2b" $ findOpen bs 3 `shouldBe` 2- it "Test 3a" $ enclose bs 2 `shouldBe` 1- it "Test 3b" $ enclose bs 7 `shouldBe` 4- it "firstChild 1" $ firstChild bs 1 `shouldBe` 2- it "firstChild 4" $ firstChild bs 4 `shouldBe` 5- it "nextSibling 2" $ nextSibling bs 2 `shouldBe` 4- it "nextSibling 5" $ nextSibling bs 5 `shouldBe` 7- it "parent 2" $ parent bs 2 `shouldBe` 1- it "parent 5" $ parent bs 5 `shouldBe` 4- it "depth 1" $ depth bs 1 `shouldBe` 1- it "depth 2" $ depth bs 2 `shouldBe` 2- it "depth 3" $ depth bs 3 `shouldBe` 2- it "depth 4" $ depth bs 4 `shouldBe` 2- it "depth 5" $ depth bs 5 `shouldBe` 3- it "depth 6" $ depth bs 6 `shouldBe` 3- it "depth 7" $ depth bs 7 `shouldBe` 3- it "depth 8" $ depth bs 8 `shouldBe` 3- it "depth 9" $ depth bs 9 `shouldBe` 2- it "depth 10" $ depth bs 10 `shouldBe` 1- it "subtreeSize 1" $ subtreeSize bs 1 `shouldBe` 5- it "subtreeSize 2" $ subtreeSize bs 2 `shouldBe` 1- it "subtreeSize 3" $ subtreeSize bs 3 `shouldBe` 0- it "subtreeSize 4" $ subtreeSize bs 4 `shouldBe` 3- it "subtreeSize 5" $ subtreeSize bs 5 `shouldBe` 1- it "subtreeSize 6" $ subtreeSize bs 6 `shouldBe` 0- it "subtreeSize 7" $ subtreeSize bs 7 `shouldBe` 1- it "subtreeSize 8" $ subtreeSize bs 8 `shouldBe` 0- it "subtreeSize 9" $ subtreeSize bs 9 `shouldBe` 0- it "subtreeSize 10" $ subtreeSize bs 10 `shouldBe` 0---- 11011010 00000000, cursorRank = 2
− test/HaskellWorks/Data/Succinct/RankSelect/Binary/Basic/Rank0Spec.hs
@@ -1,90 +0,0 @@-{-# OPTIONS_GHC -fno-warn-incomplete-patterns #-}-{-# LANGUAGE ScopedTypeVariables #-}--module HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank0Spec- ( genRank0UpTo8Spec- , genRank0UpTo16Spec- , spec- ) where--import Data.Maybe-import Data.Typeable-import qualified Data.Vector as DV-import qualified Data.Vector.Storable as DVS-import Data.Word-import HaskellWorks.Data.Bits.BitRead-import HaskellWorks.Data.Bits.BitWise-import HaskellWorks.Data.Bits.PopCount.PopCount0-import HaskellWorks.Data.Positioning-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank0-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Select0-import Test.Hspec-import Test.QuickCheck--{-# ANN module ("HLint: ignore Redundant do" :: String) #-}-{-# ANN module ("HLint: ignore Reduce duplication" :: String) #-}--genRank0UpTo8Spec :: forall s. (Typeable s, BitRead s, Rank0 s) => s -> Spec-genRank0UpTo8Spec _ = describe ("Generically up to 8 bits for " ++ show (typeOf (undefined :: s))) $ do- it "rank0 10010010 over [0..8] should be 001223445" $ do- let bs = fromJust (bitRead "10010010") :: s- fmap (rank0 bs) [0..8] `shouldBe` [0, 0, 1, 2, 2, 3, 4, 4, 5]--genRank0UpTo16Spec :: forall s. (Typeable s, BitRead s, Rank0 s) => s -> Spec-genRank0UpTo16Spec _ = describe ("Generically up to 16 bits for " ++ show (typeOf (undefined :: s))) $ do- it "rank0 11011010 00000000 over [0..16]" $ do- let bs = fromJust $ bitRead "11011010 00000000" :: s- fmap (rank0 bs) [0..16] `shouldBe` [0, 0, 0, 1, 1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]- it "rank0 11011010 10000000 over [0..16]" $ do- let bs = fromJust $ bitRead "11011010 10000000" :: s- fmap (rank0 bs) [0..16] `shouldBe` [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 9, 10]--spec :: Spec-spec = describe "HaskellWorks.Data.Succinct.RankSelect.InternalSpec" $ do- genRank0UpTo8Spec (undefined :: Word8)- genRank0UpTo8Spec (undefined :: Word16)- genRank0UpTo8Spec (undefined :: Word32)- genRank0UpTo8Spec (undefined :: Word64)- genRank0UpTo8Spec (undefined :: [Word8])- genRank0UpTo16Spec (undefined :: [Word8])- genRank0UpTo8Spec (undefined :: [Word16])- genRank0UpTo16Spec (undefined :: [Word16])- genRank0UpTo8Spec (undefined :: [Word32])- genRank0UpTo16Spec (undefined :: [Word32])- genRank0UpTo8Spec (undefined :: [Word64])- genRank0UpTo16Spec (undefined :: [Word64])- genRank0UpTo8Spec (undefined :: DV.Vector Word8)- genRank0UpTo16Spec (undefined :: DV.Vector Word8)- genRank0UpTo8Spec (undefined :: DV.Vector Word16)- genRank0UpTo16Spec (undefined :: DV.Vector Word16)- genRank0UpTo8Spec (undefined :: DV.Vector Word32)- genRank0UpTo16Spec (undefined :: DV.Vector Word32)- genRank0UpTo8Spec (undefined :: DV.Vector Word64)- genRank0UpTo16Spec (undefined :: DV.Vector Word64)- genRank0UpTo8Spec (undefined :: DVS.Vector Word8)- genRank0UpTo16Spec (undefined :: DVS.Vector Word8)- genRank0UpTo8Spec (undefined :: DVS.Vector Word16)- genRank0UpTo16Spec (undefined :: DVS.Vector Word16)- genRank0UpTo8Spec (undefined :: DVS.Vector Word32)- genRank0UpTo16Spec (undefined :: DVS.Vector Word32)- genRank0UpTo8Spec (undefined :: DVS.Vector Word64)- genRank0UpTo16Spec (undefined :: DVS.Vector Word64)- describe "Different word sizes give the same rank0" $ do- it "when comparing Word16 and Word64 over bits 0-7" $- forAll (choose (0, 8 :: Count)) $ \(i :: Count) (w :: Word8) ->- rank0 w i == rank0 (fromIntegral w :: Word64) i- it "when comparing Word16 and Word64 over bits 0-15" $ property $- forAll (choose (0, 16 :: Count)) $ \(i :: Count) (w :: Word16) ->- rank0 w i == rank0 (fromIntegral w :: Word64) i- it "when comparing Word32 and Word64 over bits 0-31" $ property $- forAll (choose (0, 32 :: Count)) $ \(i :: Count) (w :: Word32) ->- rank0 w i == rank0 (fromIntegral w :: Word64) i- it "when comparing Word32 and Word64 over bits 32-64" $ property $- forAll (choose (0, 32 :: Count)) $ \(i :: Count) (v :: Word32) (w :: Word32) ->- let v64 = fromIntegral v :: Word64 in- let w64 = fromIntegral w :: Word64 in- rank0 v i + popCount0 w == rank0 ((v64 .<. 32) .|. w64) (i + 32)- it "when comparing select1 for Word64 form a galois connection" $ property $- forAll (choose (0, 32 :: Count)) $ \(i :: Count) (w :: Word32) ->- 1 <= i && i <= popCount0 w ==>- rank0 w (select0 w i) == i && select0 w (rank0 w (fromIntegral i)) <= fromIntegral i
− test/HaskellWorks/Data/Succinct/RankSelect/Binary/Basic/Rank1Spec.hs
@@ -1,89 +0,0 @@-{-# OPTIONS_GHC -fno-warn-incomplete-patterns #-}-{-# LANGUAGE ScopedTypeVariables #-}--module HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1Spec- ( genRank1UpTo8Spec- , genRank1UpTo16Spec- , spec- ) where--import Data.Maybe-import Data.Typeable-import qualified Data.Vector as DV-import qualified Data.Vector.Storable as DVS-import Data.Word-import HaskellWorks.Data.Bits.BitRead-import HaskellWorks.Data.Bits.BitWise-import HaskellWorks.Data.Bits.PopCount.PopCount1-import HaskellWorks.Data.Positioning-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Select1-import Test.Hspec-import Test.QuickCheck--{-# ANN module ("HLint: ignore Redundant do" :: String) #-}-{-# ANN module ("HLint: ignore Reduce duplication" :: String) #-}--genRank1UpTo8Spec :: forall s. (Typeable s, BitRead s, Rank1 s) => s -> Spec-genRank1UpTo8Spec _ = describe ("Generically up to 8 bits for " ++ show (typeOf (undefined :: s))) $ do- it "rank1 10010010 over [0..8] should be 011122233" $ do- let bs = fromJust (bitRead "10010010") :: s- fmap (rank1 bs) [0..8] `shouldBe` [0, 1, 1, 1, 2, 2, 2, 3, 3]--genRank1UpTo16Spec :: forall s. (Typeable s, BitRead s, Rank1 s) => s -> Spec-genRank1UpTo16Spec _ = describe ("Generically up to 16 bits for " ++ show (typeOf (undefined :: s))) $ do- it "rank1 11011010 00000000 over [0..9]" $ do- let bs = fromJust $ bitRead "11011010 00000000" :: s- fmap (rank1 bs) [0..16] `shouldBe` [0, 1, 2, 2, 3, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]- it "rank1 11011010 10000000 over [0..9]" $ do- let bs = fromJust $ bitRead "11011010 10000000" :: s- fmap (rank1 bs) [0..16] `shouldBe` [0, 1, 2, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6]--spec :: Spec-spec = describe "HaskellWorks.Data.Succinct.RankSelect.InternalSpec" $ do- genRank1UpTo8Spec (undefined :: Word8)- genRank1UpTo8Spec (undefined :: Word16)- genRank1UpTo8Spec (undefined :: Word32)- genRank1UpTo8Spec (undefined :: Word64)- genRank1UpTo8Spec (undefined :: [Word8])- genRank1UpTo16Spec (undefined :: [Word8])- genRank1UpTo8Spec (undefined :: [Word16])- genRank1UpTo16Spec (undefined :: [Word16])- genRank1UpTo8Spec (undefined :: [Word32])- genRank1UpTo16Spec (undefined :: [Word32])- genRank1UpTo8Spec (undefined :: [Word64])- genRank1UpTo16Spec (undefined :: [Word64])- genRank1UpTo8Spec (undefined :: DV.Vector Word8)- genRank1UpTo16Spec (undefined :: DV.Vector Word8)- genRank1UpTo8Spec (undefined :: DV.Vector Word16)- genRank1UpTo16Spec (undefined :: DV.Vector Word16)- genRank1UpTo8Spec (undefined :: DV.Vector Word32)- genRank1UpTo16Spec (undefined :: DV.Vector Word32)- genRank1UpTo8Spec (undefined :: DV.Vector Word64)- genRank1UpTo16Spec (undefined :: DV.Vector Word64)- genRank1UpTo8Spec (undefined :: DVS.Vector Word8)- genRank1UpTo16Spec (undefined :: DVS.Vector Word8)- genRank1UpTo8Spec (undefined :: DVS.Vector Word16)- genRank1UpTo16Spec (undefined :: DVS.Vector Word16)- genRank1UpTo8Spec (undefined :: DVS.Vector Word32)- genRank1UpTo16Spec (undefined :: DVS.Vector Word32)- genRank1UpTo8Spec (undefined :: DVS.Vector Word64)- genRank1UpTo16Spec (undefined :: DVS.Vector Word64)- describe "For Word8-Word64" $ do- it "rank1 for Word16 and Word64 should give same answer for bits 0-7" $- forAll (choose (0, 8)) $ \(i :: Count) (w :: Word8) ->- rank1 w i == rank1 (fromIntegral w :: Word64) i- it "rank1 for Word16 and Word64 should give same answer for bits 0-15" $- forAll (choose (0, 16)) $ \(i :: Count) (w :: Word16) ->- rank1 w i == rank1 (fromIntegral w :: Word64) i- it "rank1 for Word32 and Word64 should give same answer for bits 0-31" $- forAll (choose (0, 32)) $ \(i :: Count) (w :: Word32) ->- rank1 w i == rank1 (fromIntegral w :: Word64) i- it "rank1 for Word32 and Word64 should give same answer for bits 32-64" $- forAll (choose (0, 32)) $ \(i :: Count) (v :: Word32) (w :: Word32) ->- let v64 = fromIntegral v :: Word64 in- let w64 = fromIntegral w :: Word64 in- rank1 v i + popCount1 w == rank1 ((v64 .<. 32) .|. w64) (i + 32)- it "rank1 and select1 for Word64 form a galois connection" $- forAll (choose (0, 32)) $ \(i :: Count) (w :: Word32) -> 1 <= i && i <= popCount1 w ==>- rank1 w (select1 w i) == i && select1 w (rank1 w (fromIntegral i)) <= fromIntegral i
− test/HaskellWorks/Data/Succinct/RankSelect/Binary/Basic/Select0Spec.hs
@@ -1,116 +0,0 @@-{-# OPTIONS_GHC -fno-warn-incomplete-patterns #-}-{-# LANGUAGE ScopedTypeVariables #-}--module HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Select0Spec- ( genSelect0UpTo8Spec- , genSelect0UpTo16Spec- , genSelect0UpTo32Spec- , spec- ) where--import Data.Maybe-import Data.Typeable-import qualified Data.Vector as DV-import qualified Data.Vector.Storable as DVS-import Data.Word-import HaskellWorks.Data.Bits.BitRead-import HaskellWorks.Data.Bits.BitWise-import HaskellWorks.Data.Bits.PopCount.PopCount0-import HaskellWorks.Data.Positioning-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank0-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Select0-import Test.Hspec-import Test.QuickCheck--{-# ANN module ("HLint: ignore Redundant do" :: String) #-}-{-# ANN module ("HLint: ignore Reduce duplication" :: String) #-}--genSelect0UpTo8Spec :: forall s. (Typeable s, BitRead s, Select0 s) => s -> Spec-genSelect0UpTo8Spec _ = describe ("Generically up to 8 bits for " ++ show (typeOf (undefined :: s))) $ do- it "select0 10010010 over [0..5] should be 023568" $ do- let bs = fromJust $ bitRead "10010010" :: Word8- fmap (select0 bs) [0..5] `shouldBe` [0, 2, 3, 5, 6, 8]--genSelect0UpTo16Spec :: forall s. (Typeable s, BitRead s, Select0 s) => s -> Spec-genSelect0UpTo16Spec _ = describe ("Generically up to 16 bits for " ++ show (typeOf (undefined :: s))) $ do- it "select0 11011010 00 over [0..5]" $- let bs = fromJust $ bitRead "1101101 000" :: [Bool] in- fmap (select0 bs) [0..5] `shouldBe` [0, 3, 6, 8, 9, 10]- it "select0 11011010 00000000 over [0..5]" $ do- let bs = fromJust $ bitRead "11011010 00000000" :: Word32- fmap (select0 bs) [0..11] `shouldBe` [0, 3, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16]--genSelect0UpTo32Spec :: forall s. (Typeable s, BitRead s, Select0 s) => s -> Spec-genSelect0UpTo32Spec _ = describe ("Generically up to 16 bits for " ++ show (typeOf (undefined :: s))) $ do- it "select0 11000001 10000000 01000000 over [0..5] should be 023568" $- let bs = fromJust $ bitRead "11000001 10000000 01000000" :: s in- fmap (select0 bs) [0..19] `shouldBe` [0, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24]--spec :: Spec-spec = describe "HaskellWorks.Data.Succinct.RankSelect.InternalSpec" $ do- genSelect0UpTo8Spec (undefined :: Word8)- genSelect0UpTo8Spec (undefined :: Word16)- genSelect0UpTo8Spec (undefined :: Word32)- genSelect0UpTo8Spec (undefined :: Word64)- genSelect0UpTo16Spec (undefined :: Word16)- genSelect0UpTo16Spec (undefined :: Word32)- genSelect0UpTo16Spec (undefined :: Word64)- genSelect0UpTo32Spec (undefined :: Word32)- genSelect0UpTo32Spec (undefined :: Word64)- genSelect0UpTo8Spec (undefined :: [Bool])- genSelect0UpTo16Spec (undefined :: [Bool])- genSelect0UpTo32Spec (undefined :: [Bool])- genSelect0UpTo8Spec (undefined :: [Word8])- genSelect0UpTo16Spec (undefined :: [Word8])- genSelect0UpTo32Spec (undefined :: [Word8])- genSelect0UpTo8Spec (undefined :: [Word16])- genSelect0UpTo16Spec (undefined :: [Word16])- genSelect0UpTo32Spec (undefined :: [Word16])- genSelect0UpTo8Spec (undefined :: [Word32])- genSelect0UpTo16Spec (undefined :: [Word32])- genSelect0UpTo32Spec (undefined :: [Word32])- genSelect0UpTo8Spec (undefined :: [Word64])- genSelect0UpTo16Spec (undefined :: [Word64])- genSelect0UpTo32Spec (undefined :: [Word64])- genSelect0UpTo8Spec (undefined :: DV.Vector Word8)- genSelect0UpTo16Spec (undefined :: DV.Vector Word8)- genSelect0UpTo32Spec (undefined :: DV.Vector Word8)- genSelect0UpTo8Spec (undefined :: DV.Vector Word16)- genSelect0UpTo16Spec (undefined :: DV.Vector Word16)- genSelect0UpTo32Spec (undefined :: DV.Vector Word16)- genSelect0UpTo8Spec (undefined :: DV.Vector Word32)- genSelect0UpTo16Spec (undefined :: DV.Vector Word32)- genSelect0UpTo32Spec (undefined :: DV.Vector Word32)- genSelect0UpTo8Spec (undefined :: DV.Vector Word64)- genSelect0UpTo16Spec (undefined :: DV.Vector Word64)- genSelect0UpTo32Spec (undefined :: DV.Vector Word64)- genSelect0UpTo8Spec (undefined :: DVS.Vector Word8)- genSelect0UpTo16Spec (undefined :: DVS.Vector Word8)- genSelect0UpTo32Spec (undefined :: DVS.Vector Word8)- genSelect0UpTo8Spec (undefined :: DVS.Vector Word16)- genSelect0UpTo16Spec (undefined :: DVS.Vector Word16)- genSelect0UpTo32Spec (undefined :: DVS.Vector Word16)- genSelect0UpTo8Spec (undefined :: DVS.Vector Word32)- genSelect0UpTo16Spec (undefined :: DVS.Vector Word32)- genSelect0UpTo32Spec (undefined :: DVS.Vector Word32)- genSelect0UpTo8Spec (undefined :: DVS.Vector Word64)- genSelect0UpTo16Spec (undefined :: DVS.Vector Word64)- genSelect0UpTo32Spec (undefined :: DVS.Vector Word64)- describe "For Word8-Word64" $ do- it "rank0 for Word16 and Word64 should give same answer for bits 0-7" $- forAll (choose (0, 8)) $ \(i :: Count) (w :: Word8) ->- rank0 w i == rank0 (fromIntegral w :: Word64) i- it "rank0 for Word16 and Word64 should give same answer for bits 0-15" $- forAll (choose (0, 16)) $ \(i :: Count) (w :: Word16) ->- rank0 w i == rank0 (fromIntegral w :: Word64) i- it "rank0 for Word32 and Word64 should give same answer for bits 0-31" $- forAll (choose (0, 32)) $ \(i :: Count) (w :: Word32) ->- rank0 w i == rank0 (fromIntegral w :: Word64) i- it "rank0 for Word32 and Word64 should give same answer for bits 32-64" $- forAll (choose (0, 32)) $ \(i :: Count) (v :: Word32) (w :: Word32) ->- let v64 = fromIntegral v :: Word64 in- let w64 = fromIntegral w :: Word64 in- rank0 v i + popCount0 w == rank0 ((v64 .<. 32) .|. w64) (i + 32)- it "rank0 and select0 for Word64 form a galois connection" $ property $- forAll (choose (0, 32)) $ \(i :: Count) (w :: Word32) -> 1 <= i && i <= popCount0 w ==>- rank0 w (select0 w i) == i && select0 w (rank0 w (fromIntegral i)) <= fromIntegral i
− test/HaskellWorks/Data/Succinct/RankSelect/Binary/Basic/Select1Spec.hs
@@ -1,122 +0,0 @@-{-# OPTIONS_GHC -fno-warn-incomplete-patterns #-}-{-# LANGUAGE ScopedTypeVariables #-}--module HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Select1Spec- ( genSelect1UpTo8Spec- , genSelect1UpTo16Spec- , genSelect1UpTo32Spec- , spec- ) where--import Data.Maybe-import Data.Typeable-import qualified Data.Vector as DV-import qualified Data.Vector.Storable as DVS-import Data.Word-import HaskellWorks.Data.Bits.BitRead-import HaskellWorks.Data.Bits.BitWise-import HaskellWorks.Data.Bits.PopCount.PopCount1-import HaskellWorks.Data.Positioning-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Select1-import Test.Hspec-import Test.QuickCheck--{-# ANN module ("HLint: ignore Redundant do" :: String) #-}-{-# ANN module ("HLint: ignore Reduce duplication" :: String) #-}--genSelect1UpTo8Spec :: forall s. (Typeable s, BitRead s, Select1 s) => s -> Spec-genSelect1UpTo8Spec _ = describe ("Generically up to 8 bits for " ++ show (typeOf (undefined :: s))) $ do- it "select1 10010010 over [0..3] should be 0147" $ do- let bs = fromJust $ bitRead "10010010" :: s- fmap (select1 bs) [0..3] `shouldBe` [0, 1, 4, 7]--genSelect1UpTo16Spec :: forall s. (Typeable s, BitRead s, Select1 s) => s -> Spec-genSelect1UpTo16Spec _ = describe ("Generically up to 16 bits for " ++ show (typeOf (undefined :: s))) $ do- it "select1 11011010 00 over [0..5]" $- let bs = fromJust $ bitRead "11011010 00" :: s in- fmap (select1 bs) [0..5] `shouldBe` [0, 1, 2, 4, 5, 7]- it "select1 11011010 00000000 over [0..5]" $ do- let bs = fromJust $ bitRead "11011010 00000000" :: s- fmap (select1 bs) [0..5] `shouldBe` [0, 1, 2, 4, 5, 7]- it "select 01000000 00000100 over [0..2]" $ do- let bs = fromJust $ bitRead "01000000 00000100" :: s- fmap (select1 bs) [0..2] `shouldBe` [0, 2, 14]--genSelect1UpTo32Spec :: forall s. (Typeable s, BitRead s, Select1 s) => s -> Spec-genSelect1UpTo32Spec _ = describe ("Generically up to 16 bits for " ++ show (typeOf (undefined :: s))) $ do- it "select1 11000001 10000000 01000000 over [0..5] should be 023568" $- let bs = fromJust $ bitRead "11000001 10000000 01000000" :: s in- fmap (select1 bs) [0..5] `shouldBe` [0, 1, 2, 8, 9, 18]- it "select 10000010 00000000 00100000 00010000 over [0..4]" $ do- let bs = fromJust $ bitRead "10000010 00000000 00100000 00010000" :: s- fmap (select1 bs) [0..4] `shouldBe` [0, 1, 7, 19, 28]--spec :: Spec-spec = describe "HaskellWorks.Data.Succinct.RankSelect.InternalSpec" $ do- genSelect1UpTo8Spec (undefined :: Word8)- genSelect1UpTo8Spec (undefined :: Word16)- genSelect1UpTo8Spec (undefined :: Word32)- genSelect1UpTo8Spec (undefined :: Word64)- genSelect1UpTo16Spec (undefined :: Word16)- genSelect1UpTo16Spec (undefined :: Word32)- genSelect1UpTo16Spec (undefined :: Word64)- genSelect1UpTo32Spec (undefined :: Word32)- genSelect1UpTo32Spec (undefined :: Word64)- genSelect1UpTo8Spec (undefined :: [Bool])- genSelect1UpTo16Spec (undefined :: [Bool])- genSelect1UpTo32Spec (undefined :: [Bool])- genSelect1UpTo8Spec (undefined :: [Word8])- genSelect1UpTo16Spec (undefined :: [Word8])- genSelect1UpTo32Spec (undefined :: [Word8])- genSelect1UpTo8Spec (undefined :: [Word16])- genSelect1UpTo16Spec (undefined :: [Word16])- genSelect1UpTo32Spec (undefined :: [Word16])- genSelect1UpTo8Spec (undefined :: [Word32])- genSelect1UpTo16Spec (undefined :: [Word32])- genSelect1UpTo32Spec (undefined :: [Word32])- genSelect1UpTo8Spec (undefined :: [Word64])- genSelect1UpTo16Spec (undefined :: [Word64])- genSelect1UpTo32Spec (undefined :: [Word64])- genSelect1UpTo8Spec (undefined :: DV.Vector Word8)- genSelect1UpTo16Spec (undefined :: DV.Vector Word8)- genSelect1UpTo32Spec (undefined :: DV.Vector Word8)- genSelect1UpTo8Spec (undefined :: DV.Vector Word16)- genSelect1UpTo16Spec (undefined :: DV.Vector Word16)- genSelect1UpTo32Spec (undefined :: DV.Vector Word16)- genSelect1UpTo8Spec (undefined :: DV.Vector Word32)- genSelect1UpTo16Spec (undefined :: DV.Vector Word32)- genSelect1UpTo32Spec (undefined :: DV.Vector Word32)- genSelect1UpTo8Spec (undefined :: DV.Vector Word64)- genSelect1UpTo16Spec (undefined :: DV.Vector Word64)- genSelect1UpTo32Spec (undefined :: DV.Vector Word64)- genSelect1UpTo8Spec (undefined :: DVS.Vector Word8)- genSelect1UpTo16Spec (undefined :: DVS.Vector Word8)- genSelect1UpTo32Spec (undefined :: DVS.Vector Word8)- genSelect1UpTo8Spec (undefined :: DVS.Vector Word16)- genSelect1UpTo16Spec (undefined :: DVS.Vector Word16)- genSelect1UpTo32Spec (undefined :: DVS.Vector Word16)- genSelect1UpTo8Spec (undefined :: DVS.Vector Word32)- genSelect1UpTo16Spec (undefined :: DVS.Vector Word32)- genSelect1UpTo32Spec (undefined :: DVS.Vector Word32)- genSelect1UpTo8Spec (undefined :: DVS.Vector Word64)- genSelect1UpTo16Spec (undefined :: DVS.Vector Word64)- genSelect1UpTo32Spec (undefined :: DVS.Vector Word64)- describe "For Word64" $ do- it "rank1 for Word16 and Word64 should give same answer for bits 0-7" $ property $- forAll (choose (0, 8)) $ \(i :: Count) (w :: Word8) ->- rank1 w i == rank1 (fromIntegral w :: Word64) i- it "rank1 for Word16 and Word64 should give same answer for bits 0-15" $ property $- forAll (choose (0, 16)) $ \(i :: Count) (w :: Word16) ->- rank1 w i == rank1 (fromIntegral w :: Word64) i- it "rank1 for Word32 and Word64 should give same answer for bits 0-31" $ property $- forAll (choose (0, 32)) $ \(i :: Count) (w :: Word32) ->- rank1 w i == rank1 (fromIntegral w :: Word64) i- it "rank1 for Word32 and Word64 should give same answer for bits 32-64" $ property $- forAll (choose (0, 32)) $ \(i :: Count) (v :: Word32) (w :: Word32) ->- let v64 = fromIntegral v :: Word64 in- let w64 = fromIntegral w :: Word64 in- rank1 v i + popCount1 w == rank1 ((v64 .<. 32) .|. w64) (i + 32)- it "rank1 and select1 for Word64 form a galois connection" $ property $- forAll (choose (0, 32)) $ \(i :: Count) (w :: Word32) -> 1 <= i && i <= popCount1 w ==>- rank1 w (select1 w i) == i && select1 w (rank1 w (fromIntegral i)) <= fromIntegral i
− test/HaskellWorks/Data/Succinct/RankSelect/Binary/BasicGen.hs
@@ -1,31 +0,0 @@-{-# OPTIONS_GHC -fno-warn-incomplete-patterns #-}-{-# LANGUAGE ScopedTypeVariables #-}--module HaskellWorks.Data.Succinct.RankSelect.Binary.BasicGen- ( genBinaryRankSelectSpec- ) where--import Data.Typeable-import HaskellWorks.Data.Bits.BitRead-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank0-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank0Spec hiding (spec)-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1Spec hiding (spec)-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Select0-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Select0Spec hiding (spec)-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Select1-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Select1Spec hiding (spec)-import Test.Hspec--genBinaryRankSelectSpec :: forall s. (Typeable s, BitRead s, Rank0 s, Rank1 s, Select0 s, Select1 s) => s -> Spec-genBinaryRankSelectSpec s = describe "Generically" $ do- genRank0UpTo8Spec s- genRank0UpTo16Spec s- genRank1UpTo8Spec s- genRank1UpTo16Spec s- genSelect0UpTo8Spec s- genSelect0UpTo16Spec s- genSelect0UpTo32Spec s- genSelect1UpTo8Spec s- genSelect1UpTo16Spec s- genSelect1UpTo32Spec s
− test/HaskellWorks/Data/Succinct/RankSelect/Binary/Poppy512Spec.hs
@@ -1,131 +0,0 @@-{-# OPTIONS_GHC -fno-warn-incomplete-patterns #-}-{-# LANGUAGE GeneralizedNewtypeDeriving #-}-{-# LANGUAGE ScopedTypeVariables #-}--module HaskellWorks.Data.Succinct.RankSelect.Binary.Poppy512Spec (spec) where--import GHC.Exts-import qualified Data.Vector.Storable as DVS-import Data.Word-import HaskellWorks.Data.Bits.BitShow-import HaskellWorks.Data.Bits.PopCount.PopCount0-import HaskellWorks.Data.Bits.PopCount.PopCount1-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank0-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Select0-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Select1-import HaskellWorks.Data.Succinct.RankSelect.Binary.BasicGen-import HaskellWorks.Data.Succinct.RankSelect.Binary.Poppy512-import HaskellWorks.Data.Vector.VectorLike-import Test.Hspec-import Test.QuickCheck--{-# ANN module ("HLint: ignore Redundant do" :: String) #-}-{-# ANN module ("HLint: ignore Reduce duplication" :: String) #-}--newtype ShowVector a = ShowVector a deriving (Eq, BitShow)--instance BitShow a => Show (ShowVector a) where- show = bitShow--vectorSizedBetween :: Int -> Int -> Gen (ShowVector (DVS.Vector Word64))-vectorSizedBetween a b = do- n <- choose (a, b)- xs <- sequence [ arbitrary | _ <- [1 .. n] ]- return $ ShowVector (fromList xs)--spec :: Spec-spec = describe "HaskellWorks.Data.Succinct.RankSelect.Binary.Poppy512.Rank1Spec" $ do- genBinaryRankSelectSpec (undefined :: Poppy512)- describe "rank1 for Vector Word64 is equivalent to rank1 for Poppy512" $ do- it "on empty bitvector" $- let v = DVS.empty in- let w = makePoppy512 v in- let i = 0 in- rank1 v i === rank1 w i- it "on one basic block" $- forAll (vectorSizedBetween 1 8) $ \(ShowVector v) ->- forAll (choose (0, vLength v * 8)) $ \i ->- let w = makePoppy512 v in- rank1 v i === rank1 w i- it "on two basic blocks" $- forAll (vectorSizedBetween 9 16) $ \(ShowVector v) ->- forAll (choose (0, vLength v * 8)) $ \i ->- let w = makePoppy512 v in- rank1 v i === rank1 w i- it "on three basic blocks" $- forAll (vectorSizedBetween 17 24) $ \(ShowVector v) ->- forAll (choose (0, vLength v * 8)) $ \i ->- let w = makePoppy512 v in- rank1 v i === rank1 w i- describe "rank0 for Vector Word64 is equivalent to rank0 for Poppy512" $ do- it "on empty bitvector" $- let v = DVS.empty in- let w = makePoppy512 v in- let i = 0 in- rank0 v i === rank0 w i- it "on one basic block" $- forAll (vectorSizedBetween 1 8) $ \(ShowVector v) ->- forAll (choose (0, vLength v * 8)) $ \i ->- let w = makePoppy512 v in- rank0 v i === rank0 w i- it "on two basic blocks" $- forAll (vectorSizedBetween 9 16) $ \(ShowVector v) ->- forAll (choose (0, vLength v * 8)) $ \i ->- let w = makePoppy512 v in- rank0 v i === rank0 w i- it "on three basic blocks" $- forAll (vectorSizedBetween 17 24) $ \(ShowVector v) ->- forAll (choose (0, vLength v * 8)) $ \i ->- let w = makePoppy512 v in- rank0 v i === rank0 w i- describe "select0 for Vector Word64 is equivalent to select0 for Poppy512" $ do- it "on empty bitvector" $- let v = DVS.empty in- let w = makePoppy512 v in- let i = 0 in- select0 v i === select0 w i- it "on one full zero basic block" $- let v = fromList [0, 0, 0, 0, 0, 0, 0, 0] :: DVS.Vector Word64 in- let w = makePoppy512 v in- select0 v 0 === select0 w 0- it "on one basic block" $- forAll (vectorSizedBetween 1 8) $ \(ShowVector v) ->- forAll (choose (0, popCount0 v)) $ \i ->- let w = makePoppy512 v in- select0 v i === select0 w i- it "on two basic blocks" $- forAll (vectorSizedBetween 9 16) $ \(ShowVector v) ->- forAll (choose (0, popCount0 v)) $ \i ->- let w = makePoppy512 v in- select0 v i === select0 w i- it "on three basic blocks" $- forAll (vectorSizedBetween 17 24) $ \(ShowVector v) ->- forAll (choose (0, popCount0 v)) $ \i ->- let w = makePoppy512 v in- select0 v i === select0 w i- describe "select1 for Vector Word64 is equivalent to select1 for Poppy512" $ do- it "on empty bitvector" $- let v = DVS.empty in- let w = makePoppy512 v in- let i = 0 in- select1 v i === select1 w i- it "on one full zero basic block" $- let v = fromList [0, 0, 0, 0, 0, 0, 0, 0] :: DVS.Vector Word64 in- let w = makePoppy512 v in- select1 v 0 === select1 w 0- it "on one basic block" $- forAll (vectorSizedBetween 1 8) $ \(ShowVector v) ->- forAll (choose (0, popCount1 v)) $ \i ->- let w = makePoppy512 v in- select1 v i === select1 w i- it "on two basic blocks" $- forAll (vectorSizedBetween 9 16) $ \(ShowVector v) ->- forAll (choose (0, popCount1 v)) $ \i ->- let w = makePoppy512 v in- select1 v i === select1 w i- it "on three basic blocks" $- forAll (vectorSizedBetween 17 24) $ \(ShowVector v) ->- forAll (choose (0, popCount1 v)) $ \i ->- let w = makePoppy512 v in- select1 v i === select1 w i
− test/HaskellWorks/Data/Succinct/RankSelect/InternalSpec.hs
@@ -1,34 +0,0 @@-{-# OPTIONS_GHC -fno-warn-incomplete-patterns #-}-{-# LANGUAGE ScopedTypeVariables #-}--module HaskellWorks.Data.Succinct.RankSelect.InternalSpec (spec) where--import HaskellWorks.Data.Bits.BitRead-import HaskellWorks.Data.Bits.PopCount.PopCount1-import HaskellWorks.Data.Positioning-import HaskellWorks.Data.Succinct.RankSelect.Internal-import Test.Hspec-import Test.QuickCheck--{-# ANN module ("HLint: ignore Redundant do" :: String) #-}-{-# ANN module ("HLint: ignore Reduce duplication" :: String) #-}--spec :: Spec-spec = describe "HaskellWorks.Data.Succinct.RankSelect.InternalSpec" $ do- describe "For [Bool]" $ do- it "rank True 10010010 over [0..8] should be 011122233" $- let (Just bs) = bitRead "10010010" :: Maybe [Bool] in- fmap (rank True bs) [0..8] `shouldBe` [0, 1, 1, 1, 2, 2, 2, 3, 3]- it "rank True 10010010 over [0..8] should be 001223445" $- let (Just bs) = bitRead "10010010" :: Maybe [Bool] in- fmap (rank False bs) [0..8] `shouldBe` [0, 0, 1, 2, 2, 3, 4, 4, 5]- it "select True 10010010 over [0..3] should be 0147" $- let (Just bs) = bitRead "10010010" :: Maybe [Bool] in- fmap (select True bs) [0..3] `shouldBe` [0, 1, 4, 7]- it "select False 10010010 over [0..5] should be 023568" $- let (Just bs) = bitRead "10010010" :: Maybe [Bool] in- fmap (select False bs) [0..5] `shouldBe` [0, 2, 3, 5, 6, 8]- it "Rank and select form a galois connection" $- property $ \(bs :: [Bool]) ->- forAll (choose (0, popCount1 bs)) $ \(c :: Count) ->- rank True bs (select True bs c) == c
− test/HaskellWorks/Data/Succinct/SimpleSpec.hs
@@ -1,52 +0,0 @@-{-# OPTIONS_GHC -fno-warn-incomplete-patterns #-}-{-# LANGUAGE ScopedTypeVariables #-}--module HaskellWorks.Data.Succinct.SimpleSpec (spec) where--import Data.Vector-import Data.Word-import HaskellWorks.Data.Bits.BitShown-import HaskellWorks.Data.Bits.BitWise-import HaskellWorks.Data.Positioning-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1-import Test.Hspec-import Test.QuickCheck--{-# ANN module ("HLint: ignore Redundant do" :: String) #-}--spec :: Spec-spec = describe "HaskellWorks.Data.SuccinctSpec" $ do- it "rank1 for BitShown (Vector Word8) and BitShown (Vector Word64) should give same answer" $- forAll (choose (0, 64)) $ \(i :: Count) (a :: Word8) (b :: Word8) (c :: Word8) (d :: Word8)- (e :: Word8) (f :: Word8) (g :: Word8) (h :: Word8) ->- let a64 = fromIntegral a :: Word64 in- let b64 = fromIntegral b :: Word64 in- let c64 = fromIntegral c :: Word64 in- let d64 = fromIntegral d :: Word64 in- let e64 = fromIntegral e :: Word64 in- let f64 = fromIntegral f :: Word64 in- let g64 = fromIntegral g :: Word64 in- let h64 = fromIntegral h :: Word64 in- let abcdefgh64 = (h64 .<. 56) .|. (g64 .<. 48) .|. (f64 .<. 40) .|. (e64 .<. 32) .|.- (d64 .<. 24) .|. (c64 .<. 16) .|. (b64 .<. 8 ) .|. a64 in- let vec16 = BitShown (fromList [a, b, c, d, e, f, g, h] :: Vector Word8 ) in- let vec64 = BitShown (fromList [abcdefgh64] :: Vector Word64) in- rank1 vec16 i == rank1 vec64 i- it "rank1 for BitShown (Vector Word16) and BitShown (Vector Word64) should give same answer" $- forAll (choose (0, 64)) $ \(i :: Count) (a :: Word16) (b :: Word16) (c :: Word16) (d :: Word16) ->- let a64 = fromIntegral a :: Word64 in- let b64 = fromIntegral b :: Word64 in- let c64 = fromIntegral c :: Word64 in- let d64 = fromIntegral d :: Word64 in- let abcd64 = (d64 .<. 48) .|. (c64 .<. 32) .|. (b64 .<. 16) .|. a64 in- let vec16 = BitShown (fromList [a, b, c, d] :: Vector Word16) in- let vec64 = BitShown (fromList [abcd64] :: Vector Word64) in- rank1 vec16 i == rank1 vec64 i- it "rank1 for BitShown (Vector Word32) and BitShown (Vector Word64) should give same answer" $- forAll (choose (0, 64)) $ \(i :: Count) (a :: Word32) (b :: Word32) ->- let a64 = fromIntegral a :: Word64 in- let b64 = fromIntegral b :: Word64 in- let ab64 = (b64 .<. 32) .|. a64 in- let vec32 = BitShown (fromList [a, b] :: Vector Word32) in- let vec64 = BitShown (fromList [ab64] :: Vector Word64) in- rank1 vec32 i == rank1 vec64 i