hw-rankselect 0.0.0.2 → 0.0.0.3

raw patch · 5 files changed

+148/−107 lines, 5 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• bench/Main.hs +0/−22
• hw-rankselect.cabal +1/−1
• src/HaskellWorks/Data/Succinct/BalancedParens/Internal.hs +3/−12
• src/HaskellWorks/Data/Succinct/BalancedParens/Simple.hs +102/−48
• test/HaskellWorks/Data/Succinct/BalancedParensSpec.hs +42/−24

@@ -1,35 +1,13 @@-{-# LANGUAGE BangPatterns        #-}-{-# LANGUAGE ScopedTypeVariables #-}- module Main where  import           Criterion.Main-import qualified Data.ByteString                                     as BS-import qualified Data.ByteString.Internal                            as BSI import qualified Data.Vector.Storable                                as DVS import           Data.Word-import           Foreign import           HaskellWorks.Data.Positioning import           HaskellWorks.Data.Succinct.RankSelect.Binary.Basic-import           System.IO.MMap -setupEnvBs :: Int -> IO BS.ByteString-setupEnvBs n = return $ BS.pack (take n (cycle [maxBound, 0]))--setupEnvBss :: Int -> Int -> IO [BS.ByteString]-setupEnvBss n k = setupEnvBs n >>= \v -> return (replicate k v)- setupEnvVector :: Int -> IO (DVS.Vector Word64) setupEnvVector n = return $ DVS.fromList (take n (cycle [maxBound, 0]))--setupEnvVectors :: Int -> Int -> IO [DVS.Vector Word64]-setupEnvVectors n k = setupEnvVector n >>= \v -> return (replicate k v)--setupEnvJson :: FilePath -> IO BS.ByteString-setupEnvJson filepath = do-  (fptr :: ForeignPtr Word8, offset, size) <- mmapFileForeignPtr filepath ReadOnly Nothing-  let !bs = BSI.fromForeignPtr (castForeignPtr fptr) offset size-  return bs  benchRankSelect :: [Benchmark] benchRankSelect =

@@ -1,5 +1,5 @@ name:                   hw-rankselect-version:                0.0.0.2+version:                0.0.0.3 synopsis:               Conduits for tokenizing streams. description:            Please see README.md homepage:               http://github.com/haskell-works/hw-rankselect#readme

@@ -1,8 +1,5 @@ module HaskellWorks.Data.Succinct.BalancedParens.Internal   ( BalancedParens(..)-  , firstChild-  , nextSibling-  , parent   , depth   , subtreeSize   ) where@@ -15,15 +12,9 @@   findOpen :: v -> Count -> Count   findClose :: v -> Count -> Count   enclose :: v -> Count -> Count--firstChild :: v -> Count -> Count-firstChild _ = (+ 1)--nextSibling :: BalancedParens v => v -> Count -> Count-nextSibling v p = findClose v p + 1--parent :: BalancedParens v => v -> Count -> Count-parent = enclose+  firstChild :: v -> Count -> Maybe Count+  nextSibling :: v -> Count -> Maybe Count+  parent :: v -> Count -> Maybe Count  depth :: (BalancedParens v, Rank0 v, Rank1 v) => v -> Count -> Count depth v p = let q = findOpen v p in rank1 v q - rank0 v q

@@ -66,73 +66,127 @@ {-# INLINABLE findClose' #-}  instance BalancedParens (SimpleBalancedParens [Bool]) where-  findOpen  v p = if v `openAt`  p then p else findOpen'  (Count 0) v (p - 1)-  findClose v p = if v `closeAt` p then p else findClose' (Count 0) v (p + 1)-  enclose       = findOpen' (Count 1)-  {-# INLINABLE findOpen  #-}-  {-# INLINABLE findClose #-}-  {-# INLINABLE enclose   #-}+  findOpen    v p = if v `openAt`  p then p else findOpen'  (Count 0) v (p - 1)+  findClose   v p = if v `closeAt` p then p else findClose' (Count 0) v (p + 1)+  enclose         = findOpen' (Count 1)+  firstChild  v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing+  nextSibling v p = let q = findClose v p in if p == q then Nothing else Just (q + 1)+  parent      v p = Just (enclose v p)+  {-# INLINABLE findOpen    #-}+  {-# INLINABLE findClose   #-}+  {-# INLINABLE enclose     #-}+  {-# INLINABLE firstChild  #-}+  {-# INLINABLE nextSibling #-}+  {-# INLINABLE parent      #-}  instance BalancedParens (SimpleBalancedParens (DVS.Vector Word8)) where-  findOpen  v p = if v `openAt`  p then p else findOpen'  (Count 0) v (p - 1)-  findClose v p = if v `closeAt` p then p else findClose' (Count 0) v (p + 1)-  enclose       = findOpen' (Count 1)-  {-# INLINABLE findOpen  #-}-  {-# INLINABLE findClose #-}-  {-# INLINABLE enclose   #-}+  findOpen    v p = if v `openAt`  p then p else findOpen'  (Count 0) v (p - 1)+  findClose   v p = if v `closeAt` p then p else findClose' (Count 0) v (p + 1)+  enclose         = findOpen' (Count 1)+  firstChild  v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing+  nextSibling v p = let q = findClose v p in if p == q then Nothing else Just (q + 1)+  parent      v p = Just (enclose v p)+  {-# INLINABLE findOpen    #-}+  {-# INLINABLE findClose   #-}+  {-# INLINABLE enclose     #-}+  {-# INLINABLE firstChild  #-}+  {-# INLINABLE nextSibling #-}+  {-# INLINABLE parent      #-}  instance BalancedParens (SimpleBalancedParens (DVS.Vector Word16)) where   findOpen  v p = if v `openAt`  p then p else findOpen'  (Count 0) v (p - 1)   findClose v p = if v `closeAt` p then p else findClose' (Count 0) v (p + 1)   enclose       = findOpen' (Count 1)-  {-# INLINABLE findOpen  #-}-  {-# INLINABLE findClose #-}-  {-# INLINABLE enclose   #-}+  firstChild  v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing+  nextSibling v p = let q = findClose v p in if p == q then Nothing else Just (q + 1)+  parent      v p = Just (enclose v p)+  {-# INLINABLE findOpen    #-}+  {-# INLINABLE findClose   #-}+  {-# INLINABLE enclose     #-}+  {-# INLINABLE firstChild  #-}+  {-# INLINABLE nextSibling #-}+  {-# INLINABLE parent      #-}  instance BalancedParens (SimpleBalancedParens (DVS.Vector Word32)) where   findOpen  v p = if v `openAt`  p then p else findOpen'  (Count 0) v (p - 1)   findClose v p = if v `closeAt` p then p else findClose' (Count 0) v (p + 1)   enclose       = findOpen' (Count 1)-  {-# INLINABLE findOpen  #-}-  {-# INLINABLE findClose #-}-  {-# INLINABLE enclose   #-}+  firstChild  v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing+  nextSibling v p = let q = findClose v p in if p == q then Nothing else Just (q + 1)+  parent      v p = Just (enclose v p)+  {-# INLINABLE findOpen    #-}+  {-# INLINABLE findClose   #-}+  {-# INLINABLE enclose     #-}+  {-# INLINABLE firstChild  #-}+  {-# INLINABLE nextSibling #-}+  {-# INLINABLE parent      #-}  instance BalancedParens (SimpleBalancedParens (DVS.Vector Word64)) where-  findOpen  v p = if v `openAt`  p then p else findOpen'  (Count 0) v (p - 1)-  findClose v p = if v `closeAt` p then p else findClose' (Count 0) v (p + 1)-  enclose       = findOpen' (Count 1)-  {-# INLINABLE findOpen  #-}-  {-# INLINABLE findClose #-}-  {-# INLINABLE enclose   #-}+  findOpen    v p = if v `openAt`  p then p else findOpen'  (Count 0) v (p - 1)+  findClose   v p = if v `closeAt` p then p else findClose' (Count 0) v (p + 1)+  enclose         = findOpen' (Count 1)+  firstChild  v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing+  nextSibling v p = let q = findClose v p in if p == q then Nothing else Just (q + 1)+  parent      v p = Just (enclose v p)+  {-# INLINABLE findOpen    #-}+  {-# INLINABLE findClose   #-}+  {-# INLINABLE enclose     #-}+  {-# INLINABLE firstChild  #-}+  {-# INLINABLE nextSibling #-}+  {-# INLINABLE parent      #-}  instance BalancedParens (SimpleBalancedParens Word8) where-  findOpen  v p = if v `openAt`  p then p else findOpen'  (Count 0) v (p - 1)-  findClose v p = if v `closeAt` p then p else findClose' (Count 0) v (p + 1)-  enclose       = findOpen' (Count 1)-  {-# INLINABLE findOpen  #-}-  {-# INLINABLE findClose #-}-  {-# INLINABLE enclose   #-}+  findOpen    v p = if v `openAt`  p then p else findOpen'  (Count 0) v (p - 1)+  findClose   v p = if v `closeAt` p then p else findClose' (Count 0) v (p + 1)+  enclose         = findOpen' (Count 1)+  firstChild  v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing+  nextSibling v p = let q = findClose v p in if p == q then Nothing else Just (q + 1)+  parent      v p = Just (enclose v p)+  {-# INLINABLE findOpen    #-}+  {-# INLINABLE findClose   #-}+  {-# INLINABLE enclose     #-}+  {-# INLINABLE firstChild  #-}+  {-# INLINABLE nextSibling #-}+  {-# INLINABLE parent      #-}  instance BalancedParens (SimpleBalancedParens Word16) where-  findOpen  v p = if v `openAt`  p then p else findOpen'  (Count 0) v (p - 1)-  findClose v p = if v `closeAt` p then p else findClose' (Count 0) v (p + 1)-  enclose       = findOpen' (Count 1)-  {-# INLINABLE findOpen  #-}-  {-# INLINABLE findClose #-}-  {-# INLINABLE enclose   #-}+  findOpen    v p = if v `openAt`  p then p else findOpen'  (Count 0) v (p - 1)+  findClose   v p = if v `closeAt` p then p else findClose' (Count 0) v (p + 1)+  enclose         = findOpen' (Count 1)+  firstChild  v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing+  nextSibling v p = let q = findClose v p in if p == q then Nothing else Just (q + 1)+  parent      v p = Just (enclose v p)+  {-# INLINABLE findOpen    #-}+  {-# INLINABLE findClose   #-}+  {-# INLINABLE enclose     #-}+  {-# INLINABLE firstChild  #-}+  {-# INLINABLE nextSibling #-}+  {-# INLINABLE parent      #-}  instance BalancedParens (SimpleBalancedParens Word32) where-  findOpen  v p = if v `openAt`  p then p else findOpen'  (Count 0) v (p - 1)-  findClose v p = if v `closeAt` p then p else findClose' (Count 0) v (p + 1)-  enclose       = findOpen' (Count 1)-  {-# INLINABLE findOpen  #-}-  {-# INLINABLE findClose #-}-  {-# INLINABLE enclose   #-}+  findOpen    v p = if v `openAt`  p then p else findOpen'  (Count 0) v (p - 1)+  findClose   v p = if v `closeAt` p then p else findClose' (Count 0) v (p + 1)+  enclose         = findOpen' (Count 1)+  firstChild  v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing+  nextSibling v p = let q = findClose v p in if p == q then Nothing else Just (q + 1)+  parent      v p = Just (enclose v p)+  {-# INLINABLE findOpen    #-}+  {-# INLINABLE findClose   #-}+  {-# INLINABLE enclose     #-}+  {-# INLINABLE firstChild  #-}+  {-# INLINABLE nextSibling #-}+  {-# INLINABLE parent      #-}  instance BalancedParens (SimpleBalancedParens Word64) where-  findOpen  v p = if v `openAt`  p then p else findOpen'  (Count 0) v (p - 1)-  findClose v p = if v `closeAt` p then p else findClose' (Count 0) v (p + 1)-  enclose       = findOpen' (Count 1)-  {-# INLINABLE findOpen  #-}-  {-# INLINABLE findClose #-}-  {-# INLINABLE enclose   #-}+  findOpen    v p = if v `openAt`  p then p else findOpen'  (Count 0) v (p - 1)+  findClose   v p = if v `closeAt` p then p else findClose' (Count 0) v (p + 1)+  enclose         = findOpen' (Count 1)+  firstChild  v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing+  nextSibling v p = let q = findClose v p in if p == q then Nothing else Just (q + 1)+  parent      v p = Just (enclose v p)+  {-# INLINABLE findOpen    #-}+  {-# INLINABLE findClose   #-}+  {-# INLINABLE enclose     #-}+  {-# INLINABLE firstChild  #-}+  {-# INLINABLE nextSibling #-}+  {-# INLINABLE parent      #-}

@@ -18,6 +18,14 @@     let bs = SimpleBalancedParens (91 :: Word64)     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 1b" $ findClose bs  5 `shouldBe`  6+    it "Test 1b" $ findClose bs  6 `shouldBe`  6+    it "Test 1b" $ findClose bs  7 `shouldBe`  8+    it "Test 1b" $ findClose bs  8 `shouldBe`  8+    it "Test 1b" $ findClose bs  9 `shouldBe`  9+    it "Test 1b" $ findClose bs 10 `shouldBe` 10     it "Test 2a" $ findOpen  bs 10 `shouldBe`  1     it "Test 2b" $ findOpen  bs  3 `shouldBe`  2     it "Test 3a" $ enclose   bs  2 `shouldBe`  1@@ -28,26 +36,32 @@     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 1b" $ findClose bs  5 `shouldBe`  6+    it "Test 1b" $ findClose bs  6 `shouldBe`  6+    it "Test 1b" $ findClose bs  7 `shouldBe`  8+    it "Test 1b" $ findClose bs  8 `shouldBe`  8+    it "Test 1b" $ findClose bs  9 `shouldBe`  9+    it "Test 1b" $ findClose bs 10 `shouldBe` 10     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 "firstChild 1"   $ firstChild  bs 1 `shouldBe` Just 2+    it "firstChild 4"   $ firstChild  bs 4 `shouldBe` Just 5+    it "nextSibling 2"  $ nextSibling bs 2 `shouldBe` Just 4+    it "nextSibling 5"  $ nextSibling bs 5 `shouldBe` Just 7+    it "parent 2" $ parent  bs  2 `shouldBe` Just 1+    it "parent 5" $ parent  bs  5 `shouldBe` Just 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@@ -64,16 +78,22 @@     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 1b" $ findClose bs  5 `shouldBe`  6+    it "Test 1b" $ findClose bs  6 `shouldBe`  6+    it "Test 1b" $ findClose bs  7 `shouldBe`  8+    it "Test 1b" $ findClose bs  8 `shouldBe`  8+    it "Test 1b" $ findClose bs  9 `shouldBe`  9+    it "Test 1b" $ findClose bs 10 `shouldBe` 10     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 "firstChild 1"  $ firstChild  bs 1 `shouldBe` Just 2+    it "firstChild 4"  $ firstChild  bs 4 `shouldBe` Just 5+    it "nextSibling 2" $ nextSibling bs 2 `shouldBe` Just 4+    it "nextSibling 5" $ nextSibling bs 5 `shouldBe` Just 7+    it "parent 2" $ parent bs 2 `shouldBe` Just 1+    it "parent 5" $ parent bs 5 `shouldBe` Just 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@@ -94,5 +114,3 @@     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