hw-balancedparens 0.3.0.1 → 0.3.0.2
raw patch · 3 files changed
+139/−144 lines, 3 filesdep ~basePVP ok
version bump matches the API change (PVP)
Dependency ranges changed: base
API changes (from Hackage documentation)
Files
- hw-balancedparens.cabal +97/−101
- src/HaskellWorks/Data/BalancedParens/Broadword.hs +39/−40
- src/HaskellWorks/Data/BalancedParens/CloseAt.hs +3/−3
hw-balancedparens.cabal view
@@ -1,27 +1,26 @@ cabal-version: 2.2 -name: hw-balancedparens-version: 0.3.0.1-synopsis: Balanced parentheses-description: Balanced parentheses.-category: Data, Bit, Succinct Data Structures, Data Structures-homepage: http://github.com/haskell-works/hw-balancedparens#readme-bug-reports: https://github.com/haskell-works/hw-balancedparens/issues-author: John Ky-maintainer: newhoggy@gmail.com-copyright: 2016-2019 John Ky-license: BSD-3-Clause-license-file: LICENSE-tested-with: GHC == 8.6.5, GHC == 8.4.4, GHC == 8.2.2-build-type: Simple-extra-source-files:- README.md+name: hw-balancedparens+version: 0.3.0.2+synopsis: Balanced parentheses+description: Balanced parentheses.+category: Data, Bit, Succinct Data Structures, Data Structures+homepage: http://github.com/haskell-works/hw-balancedparens#readme+bug-reports: https://github.com/haskell-works/hw-balancedparens/issues+author: John Ky+maintainer: newhoggy@gmail.com+copyright: 2016-2019 John Ky+license: BSD-3-Clause+license-file: LICENSE+tested-with: GHC == 8.8.1, GHC == 8.6.5, GHC == 8.4.4, GHC == 8.2.2+build-type: Simple+extra-source-files: README.md source-repository head type: git location: https://github.com/haskell-works/hw-balancedparens -common base { build-depends: base >= 4 && < 5 }+common base { build-depends: base >= 4.10 && < 5 } common criterion { build-depends: criterion >= 1.2 && < 1.6 } common deepseq { build-depends: deepseq >= 1.4.2.0 && < 1.5 }@@ -37,95 +36,92 @@ common vector { build-depends: vector >= 0.12 && < 0.13 } common config- default-language: Haskell2010- ghc-options: -Wall -O2 -msse4.2+ default-language: Haskell2010+ ghc-options: -Wall -O2 -msse4.2 library- import: base, config- , deepseq- , hw-bits- , hw-excess- , hw-fingertree- , hw-prim- , hw-rankselect-base- , vector- exposed-modules:- HaskellWorks.Data.BalancedParens- HaskellWorks.Data.BalancedParens.BalancedParens- HaskellWorks.Data.BalancedParens.Broadword- HaskellWorks.Data.BalancedParens.CloseAt- HaskellWorks.Data.BalancedParens.Enclose- HaskellWorks.Data.BalancedParens.FindClose- HaskellWorks.Data.BalancedParens.FindCloseN- HaskellWorks.Data.BalancedParens.FindOpen- HaskellWorks.Data.BalancedParens.FindOpenN- HaskellWorks.Data.BalancedParens.Internal.List- HaskellWorks.Data.BalancedParens.Internal.ParensSeq- HaskellWorks.Data.BalancedParens.Internal.RoseTree- HaskellWorks.Data.BalancedParens.Internal.Word- HaskellWorks.Data.BalancedParens.NewCloseAt- HaskellWorks.Data.BalancedParens.NewOpenAt- HaskellWorks.Data.BalancedParens.OpenAt- HaskellWorks.Data.BalancedParens.ParensSeq- HaskellWorks.Data.BalancedParens.ParensSeq.Types- HaskellWorks.Data.BalancedParens.RangeMin- HaskellWorks.Data.BalancedParens.RangeMin2- HaskellWorks.Data.BalancedParens.Simple- other-modules: Paths_hw_balancedparens- autogen-modules: Paths_hw_balancedparens- hs-source-dirs: src+ import: base, config+ , deepseq+ , hw-bits+ , hw-excess+ , hw-fingertree+ , hw-prim+ , hw-rankselect-base+ , vector+ exposed-modules: HaskellWorks.Data.BalancedParens+ HaskellWorks.Data.BalancedParens.BalancedParens+ HaskellWorks.Data.BalancedParens.Broadword+ HaskellWorks.Data.BalancedParens.CloseAt+ HaskellWorks.Data.BalancedParens.Enclose+ HaskellWorks.Data.BalancedParens.FindClose+ HaskellWorks.Data.BalancedParens.FindCloseN+ HaskellWorks.Data.BalancedParens.FindOpen+ HaskellWorks.Data.BalancedParens.FindOpenN+ HaskellWorks.Data.BalancedParens.Internal.List+ HaskellWorks.Data.BalancedParens.Internal.ParensSeq+ HaskellWorks.Data.BalancedParens.Internal.RoseTree+ HaskellWorks.Data.BalancedParens.Internal.Word+ HaskellWorks.Data.BalancedParens.NewCloseAt+ HaskellWorks.Data.BalancedParens.NewOpenAt+ HaskellWorks.Data.BalancedParens.OpenAt+ HaskellWorks.Data.BalancedParens.ParensSeq+ HaskellWorks.Data.BalancedParens.ParensSeq.Types+ HaskellWorks.Data.BalancedParens.RangeMin+ HaskellWorks.Data.BalancedParens.RangeMin2+ HaskellWorks.Data.BalancedParens.Simple+ other-modules: Paths_hw_balancedparens+ autogen-modules: Paths_hw_balancedparens+ hs-source-dirs: src library hw-balancedparens-gen- import: base, config- , deepseq- , hedgehog- , hspec- , hw-prim- , vector- exposed-modules:- HaskellWorks.Data.BalancedParens.Gen- Paths_hw_balancedparens- build-depends: hw-balancedparens- hs-source-dirs: gen- autogen-modules: Paths_hw_balancedparens+ import: base, config+ , deepseq+ , hedgehog+ , hspec+ , hw-prim+ , vector+ exposed-modules: HaskellWorks.Data.BalancedParens.Gen+ Paths_hw_balancedparens+ build-depends: hw-balancedparens+ hs-source-dirs: gen+ autogen-modules: Paths_hw_balancedparens test-suite hw-balancedparens-test- import: base, config- , hedgehog- , hspec- , hw-bits- , hw-hspec-hedgehog- , hw-prim- , hw-rankselect-base- , transformers- , vector- type: exitcode-stdio-1.0- main-is: Spec.hs- other-modules:- HaskellWorks.Data.BalancedParens.Internal.BroadwordSpec- HaskellWorks.Data.BalancedParens.Internal.ParensSeqSpec- HaskellWorks.Data.BalancedParens.RangeMin2Spec- HaskellWorks.Data.BalancedParens.RangeMinSpec- HaskellWorks.Data.BalancedParens.SimpleSpec- Paths_hw_balancedparens- build-depends: hw-balancedparens- , hw-balancedparens-gen- hs-source-dirs: test- ghc-options: -threaded -rtsopts -with-rtsopts=-N- autogen-modules: Paths_hw_balancedparens- build-tool-depends: hspec-discover:hspec-discover+ import: base, config+ , hedgehog+ , hspec+ , hw-bits+ , hw-hspec-hedgehog+ , hw-prim+ , hw-rankselect-base+ , transformers+ , vector+ type: exitcode-stdio-1.0+ main-is: Spec.hs+ other-modules: HaskellWorks.Data.BalancedParens.Internal.BroadwordSpec+ HaskellWorks.Data.BalancedParens.Internal.ParensSeqSpec+ HaskellWorks.Data.BalancedParens.RangeMin2Spec+ HaskellWorks.Data.BalancedParens.RangeMinSpec+ HaskellWorks.Data.BalancedParens.SimpleSpec+ Paths_hw_balancedparens+ build-depends: hw-balancedparens+ , hw-balancedparens-gen+ hs-source-dirs: test+ ghc-options: -threaded -rtsopts -with-rtsopts=-N+ autogen-modules: Paths_hw_balancedparens+ build-tool-depends: hspec-discover:hspec-discover benchmark bench- import: base, config- , criterion- , hedgehog- , hw-bits- , hw-prim- , vector- type: exitcode-stdio-1.0- main-is: Main.hs- other-modules: Paths_hw_balancedparens- autogen-modules: Paths_hw_balancedparens- hs-source-dirs: bench- build-depends: hw-balancedparens- , hw-balancedparens-gen+ import: base, config+ , criterion+ , hedgehog+ , hw-bits+ , hw-prim+ , vector+ type: exitcode-stdio-1.0+ main-is: Main.hs+ other-modules: Paths_hw_balancedparens+ autogen-modules: Paths_hw_balancedparens+ hs-source-dirs: bench+ build-depends: hw-balancedparens+ , hw-balancedparens-gen
src/HaskellWorks/Data/BalancedParens/Broadword.hs view
@@ -1,8 +1,8 @@-{-# LANGUAGE BangPatterns #-}-{-# LANGUAGE FlexibleContexts #-}-{-# LANGUAGE FlexibleInstances #-}-{-# LANGUAGE InstanceSigs #-}-{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE InstanceSigs #-}+{-# LANGUAGE ScopedTypeVariables #-} module HaskellWorks.Data.BalancedParens.Broadword ( findCloseW64@@ -16,7 +16,6 @@ import Data.Int import Data.Word-import Debug.Trace import HaskellWorks.Data.Bits.BitShown import HaskellWorks.Data.Bits.BitWise import HaskellWorks.Data.Bits.Broadword@@ -24,35 +23,35 @@ import qualified Data.Bits as DB traceW :: String -> Word64 -> Word64-traceW s w = trace (s ++ ": " ++ show (BitShown w) ++ " : " ++ show w ++ ", " ++ show (fromIntegral w :: Int64)) w+traceW s w = w -- trace (s ++ ": " ++ show (BitShown w) ++ " : " ++ show w ++ ", " ++ show (fromIntegral w :: Int64)) w findCloseW64 :: Word64 -> Word64-findCloseW64 x = -- let !_ = traceW "x00" x in- let !b00 = x - ((x .&. 0xaaaaaaaaaaaaaaaa) .>. 1) in -- let !_ = traceW "b00" b00 in- let !b01 = (b00 .&. 0x3333333333333333) + ((b00 .>. 2) .&. 0x3333333333333333) in -- let !_ = traceW "b01" b01 in- let !b02 = (b01 + (b01 .>. 4)) .&. 0x0f0f0f0f0f0f0f0f in -- let !_ = traceW "b02" b02 in- let !b03 = (b02 * 0x0101010101010101) .<. 1 in -- let !_ = traceW "b03" b03 in- let !b04 = kBitDiffUnsafe 8 (h 8 .|. 0x4038302820181008) b03 in -- let !_ = traceW "b04" b04 in- let !u00 = (((((b04 .|. h 8) - l 8) .>. 7) .&. l 8) .|. h 8) - l 8 in -- let !_ = traceW "u00" u00 in- let !z00 = ((h 8 .>. 1) .|. (l 8 * 7)) .&. u00 in -- let !_ = traceW "z00" z00 in- -- let !_ = trace "" False in- let !d10 = (l 8 * 2 - (((x .>. 6) .&. (l 8 .<. 1)) + ((x .>. 5) .&. (l 8 .<. 1)))) in -- let !_ = traceW "d10" d10 in- let !b10 = b04 - d10 in -- let !_ = traceW "b10" b10 in- let !u10 = (((((b10 .|. h 8) - l 8) .>. 7) .&. l 8) .|. h 8) - l 8 in -- let !_ = traceW "u10" u10 in- let !z10 = (z00 .&. comp u10) .|. (((h 8 .>. 1) .|. (l 8 * 5)) .&. u10) in -- let !_ = traceW "z10" z10 in- -- let !_ = trace "" False in- let !d20 = (l 8 * 2 - (((x .>. 4) .&. (l 8 .<. 1)) + ((x .>. 3) .&. (l 8 .<. 1)))) in -- let !_ = traceW "d20" d20 in- let !b20 = b10 - d20 in -- let !_ = traceW "b20" b20 in- let !u20 = (((((b20 .|. h 8) - l 8) .>. 7) .&. l 8) .|. h 8) - l 8 in -- let !_ = traceW "u20" u20 in- let !z20 = (z10 .&. comp u20) .|. (((h 8 .>. 1) .|. (l 8 * 3)) .&. u20) in -- let !_ = traceW "z20" z20 in- -- let !_ = trace "" False in- let !d30 = (l 8 * 2 - (((x .>. 2) .&. (l 8 .<. 1)) + ((x .>. 1) .&. (l 8 .<. 1)))) in -- let !_ = traceW "d30" d30 in- let !b30 = b20 - d30 in -- let !_ = traceW "b30" b30 in- let !u30 = (((((b30 .|. h 8) - l 8) .>. 7) .&. l 8) .|. h 8) - l 8 in -- let !_ = traceW "u30" u30 in- let !z30 = (z20 .&. comp u30) .|. (((h 8 .>. 1) .|. l 8 ) .&. u30) in -- let !_ = traceW "z30" z30 in+findCloseW64 x = -- let !_ = traceW "x00" x in+ let !b00 = x - ((x .&. 0xaaaaaaaaaaaaaaaa) .>. 1) in -- let !_ = traceW "b00" b00 in+ let !b01 = (b00 .&. 0x3333333333333333) + ((b00 .>. 2) .&. 0x3333333333333333) in -- let !_ = traceW "b01" b01 in+ let !b02 = (b01 + (b01 .>. 4)) .&. 0x0f0f0f0f0f0f0f0f in -- let !_ = traceW "b02" b02 in+ let !b03 = (b02 * 0x0101010101010101) .<. 1 in -- let !_ = traceW "b03" b03 in+ let !b04 = kBitDiffUnsafe 8 (h 8 .|. 0x4038302820181008) b03 in -- let !_ = traceW "b04" b04 in+ let !u00 = (((((b04 .|. h 8) - l 8) .>. 7) .&. l 8) .|. h 8) - l 8 in -- let !_ = traceW "u00" u00 in+ let !z00 = ((h 8 .>. 1) .|. (l 8 * 7)) .&. u00 in -- let !_ = traceW "z00" z00 in+ -- let !_ = trace "" False in+ let !d10 = (l 8 * 2 - (((x .>. 6) .&. (l 8 .<. 1)) + ((x .>. 5) .&. (l 8 .<. 1)))) in -- let !_ = traceW "d10" d10 in+ let !b10 = b04 - d10 in -- let !_ = traceW "b10" b10 in+ let !u10 = (((((b10 .|. h 8) - l 8) .>. 7) .&. l 8) .|. h 8) - l 8 in -- let !_ = traceW "u10" u10 in+ let !z10 = (z00 .&. comp u10) .|. (((h 8 .>. 1) .|. (l 8 * 5)) .&. u10) in -- let !_ = traceW "z10" z10 in+ -- let !_ = trace "" False in+ let !d20 = (l 8 * 2 - (((x .>. 4) .&. (l 8 .<. 1)) + ((x .>. 3) .&. (l 8 .<. 1)))) in -- let !_ = traceW "d20" d20 in+ let !b20 = b10 - d20 in -- let !_ = traceW "b20" b20 in+ let !u20 = (((((b20 .|. h 8) - l 8) .>. 7) .&. l 8) .|. h 8) - l 8 in -- let !_ = traceW "u20" u20 in+ let !z20 = (z10 .&. comp u20) .|. (((h 8 .>. 1) .|. (l 8 * 3)) .&. u20) in -- let !_ = traceW "z20" z20 in+ -- let !_ = trace "" False in+ let !d30 = (l 8 * 2 - (((x .>. 2) .&. (l 8 .<. 1)) + ((x .>. 1) .&. (l 8 .<. 1)))) in -- let !_ = traceW "d30" d30 in+ let !b30 = b20 - d30 in -- let !_ = traceW "b30" b30 in+ let !u30 = (((((b30 .|. h 8) - l 8) .>. 7) .&. l 8) .|. h 8) - l 8 in -- let !_ = traceW "u30" u30 in+ let !z30 = (z20 .&. comp u30) .|. (((h 8 .>. 1) .|. l 8 ) .&. u30) in -- let !_ = traceW "z30" z30 in - let !p00 = lsb (z30 .>. 6 .&. l 8) in -- let !_ = traceW "p00" p00 in- let !r00 = ((p00 + ((z30 .>. fromIntegral p00) .&. 0x3f)) .|. (p00 .>. 8)) .&. 0x7f in -- let !_ = traceW "r00" r00 in+ let !p00 = lsb (z30 .>. 6 .&. l 8) in -- let !_ = traceW "p00" p00 in+ let !r00 = ((p00 + ((z30 .>. fromIntegral (p00 .&. 0x3f)) .&. 0x3f)) .|. (p00 .>. 8)) .&. 0x7f in -- let !_ = traceW "r00" r00 in r00 {-# INLINE findCloseW64 #-} @@ -119,13 +118,13 @@ µµ2 = 0x0F hh :: Int -> Word8-hh 2 = 0xaa-hh 4 = 0x88-hh 8 = 0x80-hh 16 = 0x80-hh 32 = 0x80-hh 64 = 0x80-hh k = error ("Invalid h k where k = " ++ show k)+hh 2 = 0xaa+hh 4 = 0x88+hh 8 = 0x80+hh 16 = 0x80+hh 32 = 0x80+hh 64 = 0x80+hh k = error ("Invalid h k where k = " ++ show k) {-# INLINE hh #-} kkBitDiff :: Int -> Word8 -> Word8 -> Word8@@ -144,7 +143,7 @@ showPadded n a = reverse (take n (reverse (show a) ++ [' ', ' ' ..])) traceWW :: String -> Word8 -> Word8-traceWW s w = trace (s ++ ": " ++ show (BitShown w) ++ " : " ++ showPadded 3 w ++ ", " ++ showPadded 3 (fromIntegral w :: Int8)) w+traceWW s w = w -- trace (s ++ ": " ++ show (BitShown w) ++ " : " ++ showPadded 3 w ++ ", " ++ showPadded 3 (fromIntegral w :: Int8)) w (.>+.) :: Word8 -> Int -> Word8 (.>+.) w n = fromIntegral ((fromIntegral w :: Int8) `DB.shift` (-n))
src/HaskellWorks/Data/BalancedParens/CloseAt.hs view
@@ -7,14 +7,14 @@ import Data.Vector.Storable as DVS import Data.Word import HaskellWorks.Data.Bits.BitLength-import HaskellWorks.Data.Bits.BitWise import HaskellWorks.Data.Bits.BitShown+import HaskellWorks.Data.Bits.BitWise import HaskellWorks.Data.Bits.Broadword-import HaskellWorks.Data.Positioning import HaskellWorks.Data.Naive+import HaskellWorks.Data.Positioning closeAt' :: TestBit a => a -> Count -> Bool-closeAt' v c = not (v .?. toPosition (c - 1))+closeAt' v c = c > 0 && not (v .?. toPosition (c - 1)) {-# INLINE closeAt' #-} class CloseAt v where