hw-balancedparens 0.2.2.2 → 0.3.0.0

raw patch · 12 files changed

+785/−785 lines, 12 filesdep ~hspecPVP ok

version bump matches the API change (PVP)

Dependency ranges changed: hspec

API changes (from Hackage documentation)

Files

• bench/Main.hs +23/−23
• gen/HaskellWorks/Data/BalancedParens/Gen.hs +15/−15
• hw-balancedparens.cabal +5/−5
• src/HaskellWorks/Data/BalancedParens/RangeMin.hs +233/−0
• src/HaskellWorks/Data/BalancedParens/RangeMin2.hs +306/−0
• src/HaskellWorks/Data/BalancedParens/RangeMinMax.hs +0/−233
• src/HaskellWorks/Data/BalancedParens/RangeMinMax2.hs +0/−306
• test/HaskellWorks/Data/BalancedParens/Internal/ParensSeqSpec.hs +9/−9
• test/HaskellWorks/Data/BalancedParens/RangeMin2Spec.hs +135/−0
• test/HaskellWorks/Data/BalancedParens/RangeMinMax2Spec.hs +0/−135
• test/HaskellWorks/Data/BalancedParens/RangeMinMaxSpec.hs +0/−59
• test/HaskellWorks/Data/BalancedParens/RangeMinSpec.hs +59/−0

@@ -11,22 +11,22 @@ import HaskellWorks.Data.Naive import HaskellWorks.Data.Ops -import qualified Data.Vector.Storable                          as DVS-import qualified HaskellWorks.Data.BalancedParens.Gen          as G-import qualified HaskellWorks.Data.BalancedParens.ParensSeq    as PS-import qualified HaskellWorks.Data.BalancedParens.RangeMinMax  as RMM-import qualified HaskellWorks.Data.BalancedParens.RangeMinMax2 as RMM2-import qualified Hedgehog.Gen                                  as G-import qualified Hedgehog.Range                                as R+import qualified Data.Vector.Storable                       as DVS+import qualified HaskellWorks.Data.BalancedParens.Gen       as G+import qualified HaskellWorks.Data.BalancedParens.ParensSeq as PS+import qualified HaskellWorks.Data.BalancedParens.RangeMin  as RM+import qualified HaskellWorks.Data.BalancedParens.RangeMin2 as RM2+import qualified Hedgehog.Gen                               as G+import qualified Hedgehog.Range                             as R  setupEnvVector :: Int -> IO (DVS.Vector Word64) setupEnvVector n = return $ DVS.fromList (take n (cycle [maxBound, 0])) -setupEnvRmmVector :: Int -> IO (RMM.RangeMinMax (DVS.Vector Word64))-setupEnvRmmVector n = return $ RMM.mkRangeMinMax $ DVS.fromList (take n (cycle [maxBound, 0]))+setupEnvRmVector :: Int -> IO (RM.RangeMin (DVS.Vector Word64))+setupEnvRmVector n = return $ RM.mkRangeMin $ DVS.fromList (take n (cycle [maxBound, 0])) -setupEnvRmm2Vector :: Int -> IO (RMM2.RangeMinMax2 (DVS.Vector Word64))-setupEnvRmm2Vector n = return $ RMM2.mkRangeMinMax2 $ DVS.fromList (take n (cycle [maxBound, 0]))+setupEnvRm2Vector :: Int -> IO (RM2.RangeMin2 (DVS.Vector Word64))+setupEnvRm2Vector n = return $ RM2.mkRangeMin2 $ DVS.fromList (take n (cycle [maxBound, 0]))  setupEnvBP2 :: IO Word64 setupEnvBP2 = return $ DVS.head (fromBitTextByteString "10")@@ -79,25 +79,25 @@     ]   ] -benchRmm :: [Benchmark]-benchRmm =-  [ bgroup "Rmm"+benchRm :: [Benchmark]+benchRm =+  [ bgroup "Rm"     [ env (G.sample (G.storableVector (R.singleton 1000) (G.word64 R.constantBounded))) $ \v -> bgroup "Vector64"-      [ bench "mkRangeMinMax"     (nf   RMM.mkRangeMinMax v)+      [ bench "mkRangeMin"        (nf   RM.mkRangeMin v)       ]-    , env (setupEnvRmmVector 1000000) $ \bv -> bgroup "RangeMinMax"+    , env (setupEnvRmVector 1000000) $ \bv -> bgroup "RangeMin"       [ bench "findClose"         (nf   (map (findClose bv)) [0, 1000..10000000])       ]     ]   ] -benchRmm2 :: [Benchmark]-benchRmm2 =-  [ bgroup "Rmm2"+benchRm2 :: [Benchmark]+benchRm2 =+  [ bgroup "Rm2"     [ env (G.sample (G.storableVector (R.singleton 1000) (G.word64 R.constantBounded))) $ \v -> bgroup "Vector64"-      [ bench "mkRangeMinMax2"    (nf   RMM2.mkRangeMinMax2 v)+      [ bench "mkRangeMin2"       (nf   RM2.mkRangeMin2 v)       ]-    , env (setupEnvRmm2Vector 1000000) $ \bv -> bgroup "RangeMinMax2"+    , env (setupEnvRm2Vector 1000000) $ \bv -> bgroup "RangeMin2"       [ bench "findClose"         (nf   (map (findClose bv)) [0, 1000..10000000])       ]     ]@@ -125,6 +125,6 @@ main :: IO () main = defaultMain $ mempty   <> benchVector-  <> benchRmm-  <> benchRmm2+  <> benchRm+  <> benchRm2   <> benchParensSeq

@@ -9,8 +9,8 @@   , bpParensSeq   , vector   , vec2-  , randomRmm-  , randomRmm2+  , randomRm+  , randomRm2   ) where  import Data.Coerce@@ -20,13 +20,13 @@ import HaskellWorks.Data.Positioning import Hedgehog -import qualified Data.Vector                                   as DV-import qualified Data.Vector.Storable                          as DVS-import qualified HaskellWorks.Data.BalancedParens.ParensSeq    as PS-import qualified HaskellWorks.Data.BalancedParens.RangeMinMax  as RMM-import qualified HaskellWorks.Data.BalancedParens.RangeMinMax2 as RMM2-import qualified Hedgehog.Gen                                  as G-import qualified Hedgehog.Range                                as R+import qualified Data.Vector                                as DV+import qualified Data.Vector.Storable                       as DVS+import qualified HaskellWorks.Data.BalancedParens.ParensSeq as PS+import qualified HaskellWorks.Data.BalancedParens.RangeMin  as RM+import qualified HaskellWorks.Data.BalancedParens.RangeMin2 as RM2+import qualified Hedgehog.Gen                               as G+import qualified Hedgehog.Range                             as R  count :: MonadGen m => Range Count -> m Count count r = coerce <$> G.word64 (coerce <$> r)@@ -77,12 +77,12 @@ vec2 :: MonadGen m => m a -> m (a, a) vec2 g = (,) <$> g <*> g -randomRmm :: MonadGen m => Range Int -> m (RMM.RangeMinMax (DVS.Vector Word64))-randomRmm r = do+randomRm :: MonadGen m => Range Int -> m (RM.RangeMin (DVS.Vector Word64))+randomRm r = do   v <- storableVector (fmap (64 *) r) (G.word64 R.constantBounded)-  return (RMM.mkRangeMinMax v)+  return (RM.mkRangeMin v) -randomRmm2 :: MonadGen m => Range Int -> m (RMM2.RangeMinMax2 (DVS.Vector Word64))-randomRmm2 r = do+randomRm2 :: MonadGen m => Range Int -> m (RM2.RangeMin2 (DVS.Vector Word64))+randomRm2 r = do   v <- storableVector (fmap (64 *) r) (G.word64 R.constantBounded)-  return (RMM2.mkRangeMinMax2 v)+  return (RM2.mkRangeMin2 v)

@@ -1,7 +1,7 @@ cabal-version:  2.2  name:           hw-balancedparens-version:        0.2.2.2+version:        0.3.0.0 synopsis:       Balanced parentheses description:    Balanced parentheses. category:       Data, Bit, Succinct Data Structures, Data Structures@@ -68,8 +68,8 @@     HaskellWorks.Data.BalancedParens.OpenAt     HaskellWorks.Data.BalancedParens.ParensSeq     HaskellWorks.Data.BalancedParens.ParensSeq.Types-    HaskellWorks.Data.BalancedParens.RangeMinMax-    HaskellWorks.Data.BalancedParens.RangeMinMax2+    HaskellWorks.Data.BalancedParens.RangeMin+    HaskellWorks.Data.BalancedParens.RangeMin2     HaskellWorks.Data.BalancedParens.Simple   other-modules:      Paths_hw_balancedparens   autogen-modules:    Paths_hw_balancedparens@@ -104,8 +104,8 @@   other-modules:     HaskellWorks.Data.BalancedParens.Internal.BroadwordSpec     HaskellWorks.Data.BalancedParens.Internal.ParensSeqSpec-    HaskellWorks.Data.BalancedParens.RangeMinMax2Spec-    HaskellWorks.Data.BalancedParens.RangeMinMaxSpec+    HaskellWorks.Data.BalancedParens.RangeMin2Spec+    HaskellWorks.Data.BalancedParens.RangeMinSpec     HaskellWorks.Data.BalancedParens.SimpleSpec     Paths_hw_balancedparens   build-depends:      hw-balancedparens

@@ -0,0 +1,233 @@+{-# LANGUAGE BangPatterns          #-}+{-# LANGUAGE DeriveAnyClass        #-}+{-# LANGUAGE DeriveGeneric         #-}+{-# LANGUAGE DuplicateRecordFields #-}+{-# LANGUAGE FlexibleContexts      #-}+{-# LANGUAGE FlexibleInstances     #-}+{-# LANGUAGE InstanceSigs          #-}+{-# LANGUAGE TypeFamilies          #-}++module HaskellWorks.Data.BalancedParens.RangeMin+  ( RangeMin(..)+  , mkRangeMin+  ) where++import Control.DeepSeq+import Data.Int+import GHC.Generics+import HaskellWorks.Data.AtIndex+import HaskellWorks.Data.BalancedParens.BalancedParens+import HaskellWorks.Data.BalancedParens.CloseAt+import HaskellWorks.Data.BalancedParens.Enclose+import HaskellWorks.Data.BalancedParens.FindClose+import HaskellWorks.Data.BalancedParens.FindCloseN+import HaskellWorks.Data.BalancedParens.FindOpen+import HaskellWorks.Data.BalancedParens.FindOpenN+import HaskellWorks.Data.BalancedParens.NewCloseAt+import HaskellWorks.Data.BalancedParens.OpenAt+import HaskellWorks.Data.Bits.AllExcess.AllExcess1+import HaskellWorks.Data.Bits.BitLength+import HaskellWorks.Data.Bits.BitWise+import HaskellWorks.Data.Excess.MinExcess+import HaskellWorks.Data.Excess.MinExcess1+import HaskellWorks.Data.Positioning+import HaskellWorks.Data.RankSelect.Base.Rank0+import HaskellWorks.Data.RankSelect.Base.Rank1+import HaskellWorks.Data.Vector.AsVector64+import Prelude                                         hiding (length)++import qualified Data.Vector.Storable as DVS++data RangeMin a = RangeMin+  { rangeMinBP       :: !a+  , rangeMinL0Min    :: !(DVS.Vector Int8)+  , rangeMinL0Excess :: !(DVS.Vector Int8)+  , rangeMinL1Min    :: !(DVS.Vector Int16)+  , rangeMinL1Excess :: !(DVS.Vector Int16)+  , rangeMinL2Min    :: !(DVS.Vector Int16)+  , rangeMinL2Excess :: !(DVS.Vector Int16)+  } deriving (Eq, Show, NFData, Generic)++factorL0 :: Integral a => a+factorL0 = 1+{-# INLINE factorL0 #-}++factorL1 :: Integral a => a+factorL1 = 32+{-# INLINE factorL1 #-}++factorL2 :: Integral a => a+factorL2 = 32+{-# INLINE factorL2 #-}++pageSizeL0 :: Integral a => a+pageSizeL0 = factorL0+{-# INLINE pageSizeL0 #-}++pageSizeL1 :: Integral a => a+pageSizeL1 = pageSizeL0 * factorL1+{-# INLINE pageSizeL1 #-}++pageSizeL2 :: Integral a => a+pageSizeL2 = pageSizeL1 * factorL2+{-# INLINE pageSizeL2 #-}++mkRangeMin :: AsVector64 a => a -> RangeMin a+mkRangeMin bp = RangeMin+  { rangeMinBP       = bp+  , rangeMinL0Min    = rmL0Min+  , rangeMinL0Excess = dvsReword rmL0Excess+  , rangeMinL1Min    = rmL1Min+  , rangeMinL1Excess = dvsReword rmL1Excess+  , rangeMinL2Min    = rmL2Min+  , rangeMinL2Excess = rmL2Excess+  }+  where bpv           = asVector64 bp+        lenBP         = fromIntegral (length bpv) :: Int+        lenL0         = lenBP+        lenL1         = (DVS.length rmL0Min `div` pageSizeL1) + 1 :: Int+        lenL2         = (DVS.length rmL0Min `div` pageSizeL2) + 1 :: Int+        allMinL0      = dvsConstructNI lenL0 (\i -> if i == lenBP then MinExcess (-64) (-64) else minExcess1 (bpv !!! fromIntegral i))+        allMinL1      = dvsConstructNI lenL1 (\i -> minExcess1 (dropTake (i * pageSizeL1) pageSizeL1 bpv))+        allMinL2      = dvsConstructNI lenL2 (\i -> minExcess1 (dropTake (i * pageSizeL2) pageSizeL2 bpv))+        -- Note: (0xffffffffffffffc0 :: Int64) = -64+        rmL0Excess   = dvsConstructNI lenL0 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL0 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16+        rmL1Excess   = dvsConstructNI lenL1 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL1 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16+        rmL2Excess   = dvsConstructNI lenL2 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL2 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16+        rmL0Min      = dvsConstructNI lenL0 (\i -> let MinExcess minE _ = allMinL0 DVS.! i in fromIntegral minE)+        rmL1Min      = dvsConstructNI lenL1 (\i -> let MinExcess minE _ = allMinL1 DVS.! i in fromIntegral minE)+        rmL2Min      = dvsConstructNI lenL2 (\i -> let MinExcess minE _ = allMinL2 DVS.! i in fromIntegral minE)++dropTake :: DVS.Storable a => Int -> Int -> DVS.Vector a -> DVS.Vector a+dropTake n o = DVS.take o . DVS.drop n+{-# INLINE dropTake #-}++dvsReword :: (DVS.Storable a, Integral a, DVS.Storable b, Num b) => DVS.Vector a -> DVS.Vector b+dvsReword v = dvsConstructNI (DVS.length v) (\i -> fromIntegral (v DVS.! i))+{-# INLINE dvsReword #-}++pageFill :: DVS.Storable a => Int -> Int -> a -> DVS.Vector a -> DVS.Vector a+pageFill n s = dropTakeFill (n * s) s+{-# INLINE pageFill #-}++dropTakeFill :: DVS.Storable a => Int -> Int -> a -> DVS.Vector a -> DVS.Vector a+dropTakeFill n o a v =  let r = DVS.take o (DVS.drop n v) in+                        let len = DVS.length r in+                        if len == o then r else DVS.concat [r, DVS.fromList (replicate (o - len) a)]+{-# INLINE dropTakeFill #-}++dvsConstructNI :: DVS.Storable a => Int -> (Int -> a) -> DVS.Vector a+dvsConstructNI n g = DVS.constructN n (g . DVS.length)+{-# INLINE dvsConstructNI #-}++data FindState = FindBP+  | FindL0 | FindFromL0+  | FindL1 | FindFromL1+  | FindL2 | FindFromL2++rm2FindClose  :: (BitLength a, NewCloseAt a) => RangeMin a -> Int -> Count -> FindState -> Maybe Count+rm2FindClose v s p FindBP = if v `newCloseAt` p+  then if s <= 1+    then Just p+    else rm2FindClose v (s - 1) (p + 1) FindFromL0+  else rm2FindClose v (s + 1) (p + 1) FindFromL0+rm2FindClose v s p FindL0 =+  let i = p `div` 64 in+  let mins = rangeMinL0Min v in+  let minE = fromIntegral (mins !!! fromIntegral i) :: Int in+  if fromIntegral s + minE <= 0+    then rm2FindClose v s p FindBP+    else if v `newCloseAt` p && s <= 1+      then Just p+      else  let excesses  = rangeMinL0Excess v in+            let excess    = fromIntegral (excesses !!! fromIntegral i)  :: Int in+            rm2FindClose v (fromIntegral (excess + fromIntegral s)) (p + 64) FindFromL0+rm2FindClose v s p FindL1 =+  let !i = p `div` (64 * pageSizeL1) in+  let !mins = rangeMinL1Min v in+  let !minE = fromIntegral (mins !!! fromIntegral i) :: Int in+  if fromIntegral s + minE <= 0+    then rm2FindClose v s p FindL0+    else if 0 <= p && p < bitLength v+      then if v `newCloseAt` p && s <= 1+        then Just p+        else  let excesses  = rangeMinL1Excess v in+              let excess    = fromIntegral (excesses !!! fromIntegral i)  :: Int in+              rm2FindClose v (fromIntegral (excess + fromIntegral s)) (p + (64 * pageSizeL1)) FindFromL1+      else Nothing+rm2FindClose v s p FindL2 =+  let !i = p `div` (64 * pageSizeL2) in+  let !mins = rangeMinL2Min v in+  let !minE = fromIntegral (mins !!! fromIntegral i) :: Int in+  if fromIntegral s + minE <= 0+    then rm2FindClose v s p FindL1+    else if 0 <= p && p < bitLength v+      then if v `newCloseAt` p && s <= 1+        then Just p+        else  let excesses  = rangeMinL2Excess v in+              let excess    = fromIntegral (excesses !!! fromIntegral i)  :: Int in+              rm2FindClose v (fromIntegral (excess + fromIntegral s)) (p + (64 * pageSizeL2)) FindFromL2+      else Nothing+rm2FindClose v s p FindFromL0+  | p `mod` 64 == 0             = rm2FindClose v s p FindFromL1+  | 0 <= p && p < bitLength v   = rm2FindClose v s p FindBP+  | otherwise                   = Nothing+rm2FindClose v s p FindFromL1+  | p `mod` (64 * pageSizeL1) == 0  = if 0 <= p && p < bitLength v then rm2FindClose v s p FindFromL2 else Nothing+  | 0 <= p && p < bitLength v       = rm2FindClose v s p FindL0+  | otherwise                       = Nothing+rm2FindClose v s p FindFromL2+  | p `mod` (64 * pageSizeL2) == 0  = if 0 <= p && p < bitLength v then rm2FindClose v s p FindL2 else Nothing+  | 0 <= p && p < bitLength v       = rm2FindClose v s p FindL1+  | otherwise                       = Nothing+{-# INLINE rm2FindClose #-}++instance TestBit a => TestBit (RangeMin a) where+  (.?.) = (.?.) . rangeMinBP+  {-# INLINE (.?.) #-}++instance Rank1 a => Rank1 (RangeMin a) where+  rank1 = rank1 . rangeMinBP+  {-# INLINE rank1 #-}++instance Rank0 a => Rank0 (RangeMin a) where+  rank0 = rank0 . rangeMinBP+  {-# INLINE rank0 #-}++instance BitLength a => BitLength (RangeMin a) where+  bitLength = bitLength . rangeMinBP+  {-# INLINE bitLength #-}++instance OpenAt a => OpenAt (RangeMin a) where+  openAt = openAt . rangeMinBP+  {-# INLINE openAt #-}++instance CloseAt a => CloseAt (RangeMin a) where+  closeAt = closeAt . rangeMinBP+  {-# INLINE closeAt #-}++instance NewCloseAt a => NewCloseAt (RangeMin a) where+  newCloseAt = newCloseAt . rangeMinBP+  {-# INLINE newCloseAt #-}++instance FindOpenN a => FindOpenN (RangeMin a) where+  findOpenN = findOpenN . rangeMinBP+  {-# INLINE findOpenN #-}++instance (BitLength a, NewCloseAt a) => FindCloseN (RangeMin a) where+  findCloseN v s p  = (+ 1) `fmap` rm2FindClose v (fromIntegral s) (p - 1) FindFromL0+  {-# INLINE findCloseN  #-}++instance (BitLength a, CloseAt a, NewCloseAt a, FindCloseN a) => FindClose (RangeMin a) where+  findClose v p = if v `closeAt` p then Just p else findCloseN v 1 (p + 1)+  {-# INLINE findClose #-}++instance (OpenAt a, FindOpenN a) => FindOpen (RangeMin a) where+  findOpen v p = if v `openAt`  p then Just p else findOpenN  v 0 (p - 1)+  {-# INLINE findOpen #-}++instance FindOpenN a => Enclose (RangeMin a) where+  enclose v = findOpenN v 1+  {-# INLINE enclose #-}++instance (BitLength a, NewCloseAt a, CloseAt a, OpenAt a, FindOpenN a, FindCloseN a) => BalancedParens (RangeMin a)

@@ -0,0 +1,306 @@+{-# LANGUAGE BangPatterns      #-}+{-# LANGUAGE DeriveAnyClass    #-}+{-# LANGUAGE DeriveGeneric     #-}+{-# LANGUAGE FlexibleContexts  #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE InstanceSigs      #-}+{-# LANGUAGE TypeFamilies      #-}++module HaskellWorks.Data.BalancedParens.RangeMin2+  ( RangeMin2(..)+  , mkRangeMin2+  ) where++import Control.DeepSeq+import Data.Int+import GHC.Generics+import HaskellWorks.Data.AtIndex+import HaskellWorks.Data.BalancedParens.BalancedParens+import HaskellWorks.Data.BalancedParens.CloseAt+import HaskellWorks.Data.BalancedParens.Enclose+import HaskellWorks.Data.BalancedParens.FindClose+import HaskellWorks.Data.BalancedParens.FindCloseN+import HaskellWorks.Data.BalancedParens.FindOpen+import HaskellWorks.Data.BalancedParens.FindOpenN+import HaskellWorks.Data.BalancedParens.NewCloseAt+import HaskellWorks.Data.BalancedParens.OpenAt+import HaskellWorks.Data.Bits.AllExcess.AllExcess1+import HaskellWorks.Data.Bits.BitLength+import HaskellWorks.Data.Bits.BitWise+import HaskellWorks.Data.Excess.MinExcess+import HaskellWorks.Data.Excess.MinExcess1+import HaskellWorks.Data.Positioning+import HaskellWorks.Data.RankSelect.Base.Rank0+import HaskellWorks.Data.RankSelect.Base.Rank1+import HaskellWorks.Data.Vector.AsVector64+import Prelude                                         hiding (length)++import qualified Data.Vector          as DV+import qualified Data.Vector.Storable as DVS++data RangeMin2 a = RangeMin2+  { rangeMin2BP       :: !a+  , rangeMin2L0Min    :: !(DVS.Vector Int8)+  , rangeMin2L0Excess :: !(DVS.Vector Int8)+  , rangeMin2L1Min    :: !(DVS.Vector Int16)+  , rangeMin2L1Excess :: !(DVS.Vector Int16)+  , rangeMin2L2Min    :: !(DVS.Vector Int16)+  , rangeMin2L2Excess :: !(DVS.Vector Int16)+  , rangeMin2L3Min    :: !(DVS.Vector Int16)+  , rangeMin2L3Excess :: !(DVS.Vector Int16)+  , rangeMin2L4Min    :: !(DVS.Vector Int16)+  , rangeMin2L4Excess :: !(DVS.Vector Int16)+  } deriving (NFData, Generic)++factorL0 :: Integral a => a+factorL0 = 1+{-# INLINE factorL0 #-}++factorL1 :: Integral a => a+factorL1 = 32+{-# INLINE factorL1 #-}++factorL2 :: Integral a => a+factorL2 = 32+{-# INLINE factorL2 #-}++factorL3 :: Integral a => a+factorL3 = 32+{-# INLINE factorL3 #-}++factorL4 :: Integral a => a+factorL4 = 32+{-# INLINE factorL4 #-}++pageSizeL0 :: Integral a => a+pageSizeL0 = factorL0+{-# INLINE pageSizeL0 #-}++pageSizeL1 :: Integral a => a+pageSizeL1 = pageSizeL0 * factorL1+{-# INLINE pageSizeL1 #-}++pageSizeL2 :: Integral a => a+pageSizeL2 = pageSizeL1 * factorL2+{-# INLINE pageSizeL2 #-}++pageSizeL3 :: Integral a => a+pageSizeL3 = pageSizeL2 * factorL3+{-# INLINE pageSizeL3 #-}++pageSizeL4 :: Integral a => a+pageSizeL4 = pageSizeL3 * factorL4+{-# INLINE pageSizeL4 #-}++mkRangeMin2 :: AsVector64 a => a -> RangeMin2 a+mkRangeMin2 bp = RangeMin2+  { rangeMin2BP       = bp+  , rangeMin2L0Min    = dvsReword rmL0Min+  , rangeMin2L0Excess = dvsReword rmL0Excess+  , rangeMin2L1Min    = rmL1Min+  , rangeMin2L1Excess = rmL1Excess+  , rangeMin2L2Min    = rmL2Min+  , rangeMin2L2Excess = rmL2Excess+  , rangeMin2L3Min    = rmL3Min+  , rangeMin2L3Excess = rmL3Excess+  , rangeMin2L4Min    = rmL4Min+  , rangeMin2L4Excess = rmL4Excess+  }+  where bpv           = asVector64 bp+        lenBP         = fromIntegral (length bpv) :: Int+        lenL0         = lenBP+        lenL1         = (DVS.length rmL0Min `div` pageSizeL1) + 1 :: Int+        lenL2         = (DVS.length rmL0Min `div` pageSizeL2) + 1 :: Int+        lenL3         = (DVS.length rmL0Min `div` pageSizeL3) + 1 :: Int+        lenL4         = (DVS.length rmL0Min `div` pageSizeL4) + 1 :: Int+        allMinL0      = dvConstructNI  lenL0 (\i -> if i == lenBP then MinExcess (-64) (-64) else minExcess1 (bpv !!! fromIntegral i))+        -- Note: (0xffffffffffffffc0 :: Int64) = -64+        rmL0Excess   = dvsConstructNI lenL0 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL0 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16+        rmL1Excess   = dvsConstructNI lenL1 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL1 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16+        rmL2Excess   = dvsConstructNI lenL2 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL2 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16+        rmL3Excess   = dvsConstructNI lenL3 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL3 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16+        rmL4Excess   = dvsConstructNI lenL4 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL4 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16+        rmL0Min      = dvsConstructNI lenL0 (\i -> let MinExcess minE _ = allMinL0 DV.! i in fromIntegral minE) :: DVS.Vector Int16+        rmL1Min      = dvsConstructNI lenL1 (\i -> genMin 0 (pageFill i factorL1 0 rmL0Min) (pageFill i factorL1 0 rmL0Excess))+        rmL2Min      = dvsConstructNI lenL2 (\i -> genMin 0 (pageFill i factorL2 0 rmL1Min) (pageFill i factorL2 0 rmL1Excess))+        rmL3Min      = dvsConstructNI lenL3 (\i -> genMin 0 (pageFill i factorL3 0 rmL2Min) (pageFill i factorL3 0 rmL2Excess))+        rmL4Min      = dvsConstructNI lenL4 (\i -> genMin 0 (pageFill i factorL4 0 rmL3Min) (pageFill i factorL4 0 rmL3Excess))++genMin :: (Integral a, DVS.Storable a) => a -> DVS.Vector a -> DVS.Vector a -> a+genMin mL mins excesses = if not (DVS.null mins) || not (DVS.null excesses)+  then genMin (dvsLastOrZero mins `min` (mL + dvsLastOrZero excesses)) (DVS.init mins) (DVS.init excesses)+  else mL++pageFill :: DVS.Storable a => Int -> Int -> a -> DVS.Vector a -> DVS.Vector a+pageFill n s = dropTakeFill (n * s) s+{-# INLINE pageFill #-}++dropTakeFill :: DVS.Storable a => Int -> Int -> a -> DVS.Vector a -> DVS.Vector a+dropTakeFill n s a v =  let r = DVS.take s (DVS.drop n v) in+                        let rLen = DVS.length r in+                        if rLen == s then r else DVS.concat [r, DVS.replicate (s - rLen) a]+{-# INLINE dropTakeFill #-}++dvConstructNI :: Int -> (Int -> a) -> DV.Vector a+dvConstructNI n g = DV.constructN n (g . DV.length)+{-# INLINE dvConstructNI #-}++dvsConstructNI :: DVS.Storable a => Int -> (Int -> a) -> DVS.Vector a+dvsConstructNI n g = DVS.constructN n (g . DVS.length)+{-# INLINE dvsConstructNI #-}++dvsReword :: (DVS.Storable a, Integral a, DVS.Storable b, Num b) => DVS.Vector a -> DVS.Vector b+dvsReword v = dvsConstructNI (DVS.length v) (\i -> fromIntegral (v DVS.! i))+{-# INLINE dvsReword #-}++dvsLastOrZero :: (DVS.Storable a, Integral a) => DVS.Vector a -> a+dvsLastOrZero v = if not (DVS.null v) then DVS.last v else 0+{-# INLINE dvsLastOrZero #-}++data FindState = FindBP+  | FindL0 | FindFromL0+  | FindL1 | FindFromL1+  | FindL2 | FindFromL2+  | FindL3 | FindFromL3+  | FindL4 | FindFromL4++rm2FindClose  :: (BitLength a, NewCloseAt a) => RangeMin2 a -> Int -> Count -> FindState -> Maybe Count+rm2FindClose v s p FindBP = if v `newCloseAt` p+  then if s <= 1+    then Just p+    else rm2FindClose v (s - 1) (p + 1) FindFromL0+  else rm2FindClose v (s + 1) (p + 1) FindFromL0+rm2FindClose v s p FindL0 =+  let i = p `div` 64 in+  let mins = rangeMin2L0Min v in+  let minE = fromIntegral (mins !!! fromIntegral i) :: Int in+  if fromIntegral s + minE <= 0+    then rm2FindClose v s p FindBP+    else if v `newCloseAt` p && s <= 1+      then Just p+      else  let excesses  = rangeMin2L0Excess v in+            let excess    = fromIntegral (excesses !!! fromIntegral i)  :: Int in+            rm2FindClose v (fromIntegral (excess + fromIntegral s)) (p + 64) FindFromL0+rm2FindClose v s p FindL1 =+  let !i = p `div` (64 * pageSizeL1) in+  let !mins = rangeMin2L1Min v in+  let !minE = fromIntegral (mins !!! fromIntegral i) :: Int in+  if fromIntegral s + minE <= 0+    then rm2FindClose v s p FindL0+    else if 0 <= p && p < bitLength v+      then if v `newCloseAt` p && s <= 1+        then Just p+        else  let excesses  = rangeMin2L1Excess v in+              let excess    = fromIntegral (excesses !!! fromIntegral i)  :: Int in+              rm2FindClose v (fromIntegral (excess + fromIntegral s)) (p + (64 * pageSizeL1)) FindFromL1+      else Nothing+rm2FindClose v s p FindL2 =+  let !i = p `div` (64 * pageSizeL2) in+  let !mins = rangeMin2L2Min v in+  let !minE = fromIntegral (mins !!! fromIntegral i) :: Int in+  if fromIntegral s + minE <= 0+    then rm2FindClose v s p FindL1+    else if 0 <= p && p < bitLength v+      then if v `newCloseAt` p && s <= 1+        then Just p+        else  let excesses  = rangeMin2L2Excess v in+              let excess    = fromIntegral (excesses !!! fromIntegral i)  :: Int in+              rm2FindClose v (fromIntegral (excess + fromIntegral s)) (p + (64 * pageSizeL2)) FindFromL2+      else Nothing+rm2FindClose v s p FindL3 =+  let !i = p `div` (64 * pageSizeL3) in+  let !mins = rangeMin2L3Min v in+  let !minE = fromIntegral (mins !!! fromIntegral i) :: Int in+  if fromIntegral s + minE <= 0+    then rm2FindClose v s p FindL2+    else if 0 <= p && p < bitLength v+      then if v `newCloseAt` p && s <= 1+        then Just p+        else  let excesses  = rangeMin2L3Excess v in+              let excess    = fromIntegral (excesses !!! fromIntegral i)  :: Int in+              rm2FindClose v (fromIntegral (excess + fromIntegral s)) (p + (64 * pageSizeL3)) FindFromL3+        else Nothing+rm2FindClose v s p FindL4 =+  let !i = p `div` (64 * pageSizeL4) in+  let !mins = rangeMin2L4Min v in+  let !minE = fromIntegral (mins !!! fromIntegral i) :: Int in+  if fromIntegral s + minE <= 0+    then rm2FindClose v s p FindL3+    else if 0 <= p && p < bitLength v+      then if v `newCloseAt` p && s <= 1+        then Just p+        else  let excesses  = rangeMin2L4Excess v in+              let excess    = fromIntegral (excesses !!! fromIntegral i)  :: Int in+              rm2FindClose v (fromIntegral (excess + fromIntegral s)) (p + (64 * pageSizeL4)) FindFromL4+        else Nothing+rm2FindClose v s p FindFromL0+  | p `mod` 64 == 0             = rm2FindClose v s p FindFromL1+  | 0 <= p && p < bitLength v   = rm2FindClose v s p FindBP+  | otherwise                   = Nothing+rm2FindClose v s p FindFromL1+  | p `mod` (64 * pageSizeL1) == 0  = if 0 <= p && p < bitLength v then rm2FindClose v s p FindFromL2 else Nothing+  | 0 <= p && p < bitLength v       = rm2FindClose v s p FindL0+  | otherwise                       = Nothing+rm2FindClose v s p FindFromL2+  | p `mod` (64 * pageSizeL2) == 0  = if 0 <= p && p < bitLength v then rm2FindClose v s p FindFromL3 else Nothing+  | 0 <= p && p < bitLength v       = rm2FindClose v s p FindL1+  | otherwise                       = Nothing+rm2FindClose v s p FindFromL3+  | p `mod` (64 * pageSizeL3) == 0  = if 0 <= p && p < bitLength v then rm2FindClose v s p FindFromL4 else Nothing+  | 0 <= p && p < bitLength v       = rm2FindClose v s p FindL2+  | otherwise                       = Nothing+rm2FindClose v s p FindFromL4+  | p `mod` (64 * pageSizeL4) == 0  = if 0 <= p && p < bitLength v then rm2FindClose v s p FindL4 else Nothing+  | 0 <= p && p < bitLength v       = rm2FindClose v s p FindL3+  | otherwise                       = Nothing+{-# INLINE rm2FindClose #-}++instance TestBit a => TestBit (RangeMin2 a) where+  (.?.) = (.?.) . rangeMin2BP+  {-# INLINE (.?.) #-}++instance Rank1 a => Rank1 (RangeMin2 a) where+  rank1 = rank1 . rangeMin2BP+  {-# INLINE rank1 #-}++instance Rank0 a => Rank0 (RangeMin2 a) where+  rank0 = rank0 . rangeMin2BP+  {-# INLINE rank0 #-}++instance BitLength a => BitLength (RangeMin2 a) where+  bitLength = bitLength . rangeMin2BP+  {-# INLINE bitLength #-}++instance OpenAt a => OpenAt (RangeMin2 a) where+  openAt = openAt . rangeMin2BP+  {-# INLINE openAt #-}++instance CloseAt a => CloseAt (RangeMin2 a) where+  closeAt = closeAt . rangeMin2BP+  {-# INLINE closeAt #-}++instance NewCloseAt a => NewCloseAt (RangeMin2 a) where+  newCloseAt = newCloseAt . rangeMin2BP+  {-# INLINE newCloseAt #-}++instance FindOpenN a => FindOpenN (RangeMin2 a) where+  findOpenN = findOpenN . rangeMin2BP+  {-# INLINE findOpenN #-}++instance (BitLength a, FindCloseN a, NewCloseAt a) => FindCloseN (RangeMin2 a) where+  findCloseN v s p  = (+ 1) `fmap` rm2FindClose v (fromIntegral s) (p - 1) FindFromL0+  {-# INLINE findCloseN  #-}++instance (BitLength a, NewCloseAt a, CloseAt a, FindCloseN a) => FindClose (RangeMin2 a) where+  findClose v p = if v `closeAt` p then Just p else findCloseN v 1 (p + 1)+  {-# INLINE findClose #-}++instance (OpenAt a, FindOpenN a) => FindOpen (RangeMin2 a) where+  findOpen v p = if v `openAt`  p then Just p else findOpenN  v 0 (p - 1)+  {-# INLINE findOpen #-}++instance FindOpenN a => Enclose (RangeMin2 a) where+  enclose v = findOpenN v 1+  {-# INLINE enclose #-}++instance (BitLength a, NewCloseAt a, CloseAt a, OpenAt a, FindOpenN a, FindCloseN a) => BalancedParens (RangeMin2 a)

@@ -1,233 +0,0 @@-{-# LANGUAGE BangPatterns          #-}-{-# LANGUAGE DeriveAnyClass        #-}-{-# LANGUAGE DeriveGeneric         #-}-{-# LANGUAGE DuplicateRecordFields #-}-{-# LANGUAGE FlexibleContexts      #-}-{-# LANGUAGE FlexibleInstances     #-}-{-# LANGUAGE InstanceSigs          #-}-{-# LANGUAGE TypeFamilies          #-}--module HaskellWorks.Data.BalancedParens.RangeMinMax-  ( RangeMinMax(..)-  , mkRangeMinMax-  ) where--import Control.DeepSeq-import Data.Int-import GHC.Generics-import HaskellWorks.Data.AtIndex-import HaskellWorks.Data.BalancedParens.BalancedParens-import HaskellWorks.Data.BalancedParens.CloseAt-import HaskellWorks.Data.BalancedParens.Enclose-import HaskellWorks.Data.BalancedParens.FindClose-import HaskellWorks.Data.BalancedParens.FindCloseN-import HaskellWorks.Data.BalancedParens.FindOpen-import HaskellWorks.Data.BalancedParens.FindOpenN-import HaskellWorks.Data.BalancedParens.NewCloseAt-import HaskellWorks.Data.BalancedParens.OpenAt-import HaskellWorks.Data.Bits.AllExcess.AllExcess1-import HaskellWorks.Data.Bits.BitLength-import HaskellWorks.Data.Bits.BitWise-import HaskellWorks.Data.Excess.MinExcess-import HaskellWorks.Data.Excess.MinExcess1-import HaskellWorks.Data.Positioning-import HaskellWorks.Data.RankSelect.Base.Rank0-import HaskellWorks.Data.RankSelect.Base.Rank1-import HaskellWorks.Data.Vector.AsVector64-import Prelude                                         hiding (length)--import qualified Data.Vector.Storable as DVS--data RangeMinMax a = RangeMinMax-  { rangeMinMaxBP       :: !a-  , rangeMinMaxL0Min    :: !(DVS.Vector Int8)-  , rangeMinMaxL0Excess :: !(DVS.Vector Int8)-  , rangeMinMaxL1Min    :: !(DVS.Vector Int16)-  , rangeMinMaxL1Excess :: !(DVS.Vector Int16)-  , rangeMinMaxL2Min    :: !(DVS.Vector Int16)-  , rangeMinMaxL2Excess :: !(DVS.Vector Int16)-  } deriving (Eq, Show, NFData, Generic)--factorL0 :: Integral a => a-factorL0 = 1-{-# INLINE factorL0 #-}--factorL1 :: Integral a => a-factorL1 = 32-{-# INLINE factorL1 #-}--factorL2 :: Integral a => a-factorL2 = 32-{-# INLINE factorL2 #-}--pageSizeL0 :: Integral a => a-pageSizeL0 = factorL0-{-# INLINE pageSizeL0 #-}--pageSizeL1 :: Integral a => a-pageSizeL1 = pageSizeL0 * factorL1-{-# INLINE pageSizeL1 #-}--pageSizeL2 :: Integral a => a-pageSizeL2 = pageSizeL1 * factorL2-{-# INLINE pageSizeL2 #-}--mkRangeMinMax :: AsVector64 a => a -> RangeMinMax a-mkRangeMinMax bp = RangeMinMax-  { rangeMinMaxBP       = bp-  , rangeMinMaxL0Min    = rmmL0Min-  , rangeMinMaxL0Excess = dvsReword rmmL0Excess-  , rangeMinMaxL1Min    = rmmL1Min-  , rangeMinMaxL1Excess = dvsReword rmmL1Excess-  , rangeMinMaxL2Min    = rmmL2Min-  , rangeMinMaxL2Excess = rmmL2Excess-  }-  where bpv           = asVector64 bp-        lenBP         = fromIntegral (length bpv) :: Int-        lenL0         = lenBP-        lenL1         = (DVS.length rmmL0Min `div` pageSizeL1) + 1 :: Int-        lenL2         = (DVS.length rmmL0Min `div` pageSizeL2) + 1 :: Int-        allMinMaxL0   = dvsConstructNI lenL0 (\i -> if i == lenBP then MinExcess (-64) (-64) else minExcess1 (bpv !!! fromIntegral i))-        allMinMaxL1   = dvsConstructNI lenL1 (\i -> minExcess1 (dropTake (i * pageSizeL1) pageSizeL1 bpv))-        allMinMaxL2   = dvsConstructNI lenL2 (\i -> minExcess1 (dropTake (i * pageSizeL2) pageSizeL2 bpv))-        -- Note: (0xffffffffffffffc0 :: Int64) = -64-        rmmL0Excess   = dvsConstructNI lenL0 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL0 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16-        rmmL1Excess   = dvsConstructNI lenL1 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL1 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16-        rmmL2Excess   = dvsConstructNI lenL2 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL2 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16-        rmmL0Min      = dvsConstructNI lenL0 (\i -> let MinExcess minE _ = allMinMaxL0 DVS.! i in fromIntegral minE)-        rmmL1Min      = dvsConstructNI lenL1 (\i -> let MinExcess minE _ = allMinMaxL1 DVS.! i in fromIntegral minE)-        rmmL2Min      = dvsConstructNI lenL2 (\i -> let MinExcess minE _ = allMinMaxL2 DVS.! i in fromIntegral minE)--dropTake :: DVS.Storable a => Int -> Int -> DVS.Vector a -> DVS.Vector a-dropTake n o = DVS.take o . DVS.drop n-{-# INLINE dropTake #-}--dvsReword :: (DVS.Storable a, Integral a, DVS.Storable b, Num b) => DVS.Vector a -> DVS.Vector b-dvsReword v = dvsConstructNI (DVS.length v) (\i -> fromIntegral (v DVS.! i))-{-# INLINE dvsReword #-}--pageFill :: DVS.Storable a => Int -> Int -> a -> DVS.Vector a -> DVS.Vector a-pageFill n s = dropTakeFill (n * s) s-{-# INLINE pageFill #-}--dropTakeFill :: DVS.Storable a => Int -> Int -> a -> DVS.Vector a -> DVS.Vector a-dropTakeFill n o a v =  let r = DVS.take o (DVS.drop n v) in-                        let len = DVS.length r in-                        if len == o then r else DVS.concat [r, DVS.fromList (replicate (o - len) a)]-{-# INLINE dropTakeFill #-}--dvsConstructNI :: DVS.Storable a => Int -> (Int -> a) -> DVS.Vector a-dvsConstructNI n g = DVS.constructN n (g . DVS.length)-{-# INLINE dvsConstructNI #-}--data FindState = FindBP-  | FindL0 | FindFromL0-  | FindL1 | FindFromL1-  | FindL2 | FindFromL2--rmm2FindClose  :: (BitLength a, NewCloseAt a) => RangeMinMax a -> Int -> Count -> FindState -> Maybe Count-rmm2FindClose v s p FindBP = if v `newCloseAt` p-  then if s <= 1-    then Just p-    else rmm2FindClose v (s - 1) (p + 1) FindFromL0-  else rmm2FindClose v (s + 1) (p + 1) FindFromL0-rmm2FindClose v s p FindL0 =-  let i = p `div` 64 in-  let mins = rangeMinMaxL0Min v in-  let minE = fromIntegral (mins !!! fromIntegral i) :: Int in-  if fromIntegral s + minE <= 0-    then rmm2FindClose v s p FindBP-    else if v `newCloseAt` p && s <= 1-      then Just p-      else  let excesses  = rangeMinMaxL0Excess v in-            let excess    = fromIntegral (excesses !!! fromIntegral i)  :: Int in-            rmm2FindClose v (fromIntegral (excess + fromIntegral s)) (p + 64) FindFromL0-rmm2FindClose v s p FindL1 =-  let !i = p `div` (64 * pageSizeL1) in-  let !mins = rangeMinMaxL1Min v in-  let !minE = fromIntegral (mins !!! fromIntegral i) :: Int in-  if fromIntegral s + minE <= 0-    then rmm2FindClose v s p FindL0-    else if 0 <= p && p < bitLength v-      then if v `newCloseAt` p && s <= 1-        then Just p-        else  let excesses  = rangeMinMaxL1Excess v in-              let excess    = fromIntegral (excesses !!! fromIntegral i)  :: Int in-              rmm2FindClose v (fromIntegral (excess + fromIntegral s)) (p + (64 * pageSizeL1)) FindFromL1-      else Nothing-rmm2FindClose v s p FindL2 =-  let !i = p `div` (64 * pageSizeL2) in-  let !mins = rangeMinMaxL2Min v in-  let !minE = fromIntegral (mins !!! fromIntegral i) :: Int in-  if fromIntegral s + minE <= 0-    then rmm2FindClose v s p FindL1-    else if 0 <= p && p < bitLength v-      then if v `newCloseAt` p && s <= 1-        then Just p-        else  let excesses  = rangeMinMaxL2Excess v in-              let excess    = fromIntegral (excesses !!! fromIntegral i)  :: Int in-              rmm2FindClose v (fromIntegral (excess + fromIntegral s)) (p + (64 * pageSizeL2)) FindFromL2-      else Nothing-rmm2FindClose v s p FindFromL0-  | p `mod` 64 == 0             = rmm2FindClose v s p FindFromL1-  | 0 <= p && p < bitLength v   = rmm2FindClose v s p FindBP-  | otherwise                   = Nothing-rmm2FindClose v s p FindFromL1-  | p `mod` (64 * pageSizeL1) == 0  = if 0 <= p && p < bitLength v then rmm2FindClose v s p FindFromL2 else Nothing-  | 0 <= p && p < bitLength v       = rmm2FindClose v s p FindL0-  | otherwise                       = Nothing-rmm2FindClose v s p FindFromL2-  | p `mod` (64 * pageSizeL2) == 0  = if 0 <= p && p < bitLength v then rmm2FindClose v s p FindL2 else Nothing-  | 0 <= p && p < bitLength v       = rmm2FindClose v s p FindL1-  | otherwise                       = Nothing-{-# INLINE rmm2FindClose #-}--instance TestBit a => TestBit (RangeMinMax a) where-  (.?.) = (.?.) . rangeMinMaxBP-  {-# INLINE (.?.) #-}--instance Rank1 a => Rank1 (RangeMinMax a) where-  rank1 = rank1 . rangeMinMaxBP-  {-# INLINE rank1 #-}--instance Rank0 a => Rank0 (RangeMinMax a) where-  rank0 = rank0 . rangeMinMaxBP-  {-# INLINE rank0 #-}--instance BitLength a => BitLength (RangeMinMax a) where-  bitLength = bitLength . rangeMinMaxBP-  {-# INLINE bitLength #-}--instance OpenAt a => OpenAt (RangeMinMax a) where-  openAt = openAt . rangeMinMaxBP-  {-# INLINE openAt #-}--instance CloseAt a => CloseAt (RangeMinMax a) where-  closeAt = closeAt . rangeMinMaxBP-  {-# INLINE closeAt #-}--instance NewCloseAt a => NewCloseAt (RangeMinMax a) where-  newCloseAt = newCloseAt . rangeMinMaxBP-  {-# INLINE newCloseAt #-}--instance FindOpenN a => FindOpenN (RangeMinMax a) where-  findOpenN = findOpenN . rangeMinMaxBP-  {-# INLINE findOpenN #-}--instance (BitLength a, NewCloseAt a) => FindCloseN (RangeMinMax a) where-  findCloseN v s p  = (+ 1) `fmap` rmm2FindClose v (fromIntegral s) (p - 1) FindFromL0-  {-# INLINE findCloseN  #-}--instance (BitLength a, CloseAt a, NewCloseAt a, FindCloseN a) => FindClose (RangeMinMax a) where-  findClose v p = if v `closeAt` p then Just p else findCloseN v 1 (p + 1)-  {-# INLINE findClose #-}--instance (OpenAt a, FindOpenN a) => FindOpen (RangeMinMax a) where-  findOpen v p = if v `openAt`  p then Just p else findOpenN  v 0 (p - 1)-  {-# INLINE findOpen #-}--instance FindOpenN a => Enclose (RangeMinMax a) where-  enclose v = findOpenN v 1-  {-# INLINE enclose #-}--instance (BitLength a, NewCloseAt a, CloseAt a, OpenAt a, FindOpenN a, FindCloseN a) => BalancedParens (RangeMinMax a)

@@ -1,306 +0,0 @@-{-# LANGUAGE BangPatterns      #-}-{-# LANGUAGE DeriveAnyClass    #-}-{-# LANGUAGE DeriveGeneric     #-}-{-# LANGUAGE FlexibleContexts  #-}-{-# LANGUAGE FlexibleInstances #-}-{-# LANGUAGE InstanceSigs      #-}-{-# LANGUAGE TypeFamilies      #-}--module HaskellWorks.Data.BalancedParens.RangeMinMax2-  ( RangeMinMax2(..)-  , mkRangeMinMax2-  ) where--import Control.DeepSeq-import Data.Int-import GHC.Generics-import HaskellWorks.Data.AtIndex-import HaskellWorks.Data.BalancedParens.BalancedParens-import HaskellWorks.Data.BalancedParens.CloseAt-import HaskellWorks.Data.BalancedParens.Enclose-import HaskellWorks.Data.BalancedParens.FindClose-import HaskellWorks.Data.BalancedParens.FindCloseN-import HaskellWorks.Data.BalancedParens.FindOpen-import HaskellWorks.Data.BalancedParens.FindOpenN-import HaskellWorks.Data.BalancedParens.NewCloseAt-import HaskellWorks.Data.BalancedParens.OpenAt-import HaskellWorks.Data.Bits.AllExcess.AllExcess1-import HaskellWorks.Data.Bits.BitLength-import HaskellWorks.Data.Bits.BitWise-import HaskellWorks.Data.Excess.MinExcess-import HaskellWorks.Data.Excess.MinExcess1-import HaskellWorks.Data.Positioning-import HaskellWorks.Data.RankSelect.Base.Rank0-import HaskellWorks.Data.RankSelect.Base.Rank1-import HaskellWorks.Data.Vector.AsVector64-import Prelude                                         hiding (length)--import qualified Data.Vector          as DV-import qualified Data.Vector.Storable as DVS--data RangeMinMax2 a = RangeMinMax2-  { rangeMinMax2BP       :: !a-  , rangeMinMax2L0Min    :: !(DVS.Vector Int8)-  , rangeMinMax2L0Excess :: !(DVS.Vector Int8)-  , rangeMinMax2L1Min    :: !(DVS.Vector Int16)-  , rangeMinMax2L1Excess :: !(DVS.Vector Int16)-  , rangeMinMax2L2Min    :: !(DVS.Vector Int16)-  , rangeMinMax2L2Excess :: !(DVS.Vector Int16)-  , rangeMinMax2L3Min    :: !(DVS.Vector Int16)-  , rangeMinMax2L3Excess :: !(DVS.Vector Int16)-  , rangeMinMax2L4Min    :: !(DVS.Vector Int16)-  , rangeMinMax2L4Excess :: !(DVS.Vector Int16)-  } deriving (NFData, Generic)--factorL0 :: Integral a => a-factorL0 = 1-{-# INLINE factorL0 #-}--factorL1 :: Integral a => a-factorL1 = 32-{-# INLINE factorL1 #-}--factorL2 :: Integral a => a-factorL2 = 32-{-# INLINE factorL2 #-}--factorL3 :: Integral a => a-factorL3 = 32-{-# INLINE factorL3 #-}--factorL4 :: Integral a => a-factorL4 = 32-{-# INLINE factorL4 #-}--pageSizeL0 :: Integral a => a-pageSizeL0 = factorL0-{-# INLINE pageSizeL0 #-}--pageSizeL1 :: Integral a => a-pageSizeL1 = pageSizeL0 * factorL1-{-# INLINE pageSizeL1 #-}--pageSizeL2 :: Integral a => a-pageSizeL2 = pageSizeL1 * factorL2-{-# INLINE pageSizeL2 #-}--pageSizeL3 :: Integral a => a-pageSizeL3 = pageSizeL2 * factorL3-{-# INLINE pageSizeL3 #-}--pageSizeL4 :: Integral a => a-pageSizeL4 = pageSizeL3 * factorL4-{-# INLINE pageSizeL4 #-}--mkRangeMinMax2 :: AsVector64 a => a -> RangeMinMax2 a-mkRangeMinMax2 bp = RangeMinMax2-  { rangeMinMax2BP       = bp-  , rangeMinMax2L0Min    = dvsReword rmmL0Min-  , rangeMinMax2L0Excess = dvsReword rmmL0Excess-  , rangeMinMax2L1Min    = rmmL1Min-  , rangeMinMax2L1Excess = rmmL1Excess-  , rangeMinMax2L2Min    = rmmL2Min-  , rangeMinMax2L2Excess = rmmL2Excess-  , rangeMinMax2L3Min    = rmmL3Min-  , rangeMinMax2L3Excess = rmmL3Excess-  , rangeMinMax2L4Min    = rmmL4Min-  , rangeMinMax2L4Excess = rmmL4Excess-  }-  where bpv           = asVector64 bp-        lenBP         = fromIntegral (length bpv) :: Int-        lenL0         = lenBP-        lenL1         = (DVS.length rmmL0Min `div` pageSizeL1) + 1 :: Int-        lenL2         = (DVS.length rmmL0Min `div` pageSizeL2) + 1 :: Int-        lenL3         = (DVS.length rmmL0Min `div` pageSizeL3) + 1 :: Int-        lenL4         = (DVS.length rmmL0Min `div` pageSizeL4) + 1 :: Int-        allMinMaxL0   = dvConstructNI  lenL0 (\i -> if i == lenBP then MinExcess (-64) (-64) else minExcess1 (bpv !!! fromIntegral i))-        -- Note: (0xffffffffffffffc0 :: Int64) = -64-        rmmL0Excess   = dvsConstructNI lenL0 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL0 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16-        rmmL1Excess   = dvsConstructNI lenL1 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL1 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16-        rmmL2Excess   = dvsConstructNI lenL2 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL2 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16-        rmmL3Excess   = dvsConstructNI lenL3 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL3 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16-        rmmL4Excess   = dvsConstructNI lenL4 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL4 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16-        rmmL0Min      = dvsConstructNI lenL0 (\i -> let MinExcess minE _ = allMinMaxL0 DV.! i in fromIntegral minE) :: DVS.Vector Int16-        rmmL1Min      = dvsConstructNI lenL1 (\i -> genMin 0 (pageFill i factorL1 0 rmmL0Min) (pageFill i factorL1 0 rmmL0Excess))-        rmmL2Min      = dvsConstructNI lenL2 (\i -> genMin 0 (pageFill i factorL2 0 rmmL1Min) (pageFill i factorL2 0 rmmL1Excess))-        rmmL3Min      = dvsConstructNI lenL3 (\i -> genMin 0 (pageFill i factorL3 0 rmmL2Min) (pageFill i factorL3 0 rmmL2Excess))-        rmmL4Min      = dvsConstructNI lenL4 (\i -> genMin 0 (pageFill i factorL4 0 rmmL3Min) (pageFill i factorL4 0 rmmL3Excess))--genMin :: (Integral a, DVS.Storable a) => a -> DVS.Vector a -> DVS.Vector a -> a-genMin mL mins excesses = if not (DVS.null mins) || not (DVS.null excesses)-  then genMin (dvsLastOrZero mins `min` (mL + dvsLastOrZero excesses)) (DVS.init mins) (DVS.init excesses)-  else mL--pageFill :: DVS.Storable a => Int -> Int -> a -> DVS.Vector a -> DVS.Vector a-pageFill n s = dropTakeFill (n * s) s-{-# INLINE pageFill #-}--dropTakeFill :: DVS.Storable a => Int -> Int -> a -> DVS.Vector a -> DVS.Vector a-dropTakeFill n s a v =  let r = DVS.take s (DVS.drop n v) in-                        let rLen = DVS.length r in-                        if rLen == s then r else DVS.concat [r, DVS.replicate (s - rLen) a]-{-# INLINE dropTakeFill #-}--dvConstructNI :: Int -> (Int -> a) -> DV.Vector a-dvConstructNI n g = DV.constructN n (g . DV.length)-{-# INLINE dvConstructNI #-}--dvsConstructNI :: DVS.Storable a => Int -> (Int -> a) -> DVS.Vector a-dvsConstructNI n g = DVS.constructN n (g . DVS.length)-{-# INLINE dvsConstructNI #-}--dvsReword :: (DVS.Storable a, Integral a, DVS.Storable b, Num b) => DVS.Vector a -> DVS.Vector b-dvsReword v = dvsConstructNI (DVS.length v) (\i -> fromIntegral (v DVS.! i))-{-# INLINE dvsReword #-}--dvsLastOrZero :: (DVS.Storable a, Integral a) => DVS.Vector a -> a-dvsLastOrZero v = if not (DVS.null v) then DVS.last v else 0-{-# INLINE dvsLastOrZero #-}--data FindState = FindBP-  | FindL0 | FindFromL0-  | FindL1 | FindFromL1-  | FindL2 | FindFromL2-  | FindL3 | FindFromL3-  | FindL4 | FindFromL4--rmm2FindClose  :: (BitLength a, NewCloseAt a) => RangeMinMax2 a -> Int -> Count -> FindState -> Maybe Count-rmm2FindClose v s p FindBP = if v `newCloseAt` p-  then if s <= 1-    then Just p-    else rmm2FindClose v (s - 1) (p + 1) FindFromL0-  else rmm2FindClose v (s + 1) (p + 1) FindFromL0-rmm2FindClose v s p FindL0 =-  let i = p `div` 64 in-  let mins = rangeMinMax2L0Min v in-  let minE = fromIntegral (mins !!! fromIntegral i) :: Int in-  if fromIntegral s + minE <= 0-    then rmm2FindClose v s p FindBP-    else if v `newCloseAt` p && s <= 1-      then Just p-      else  let excesses  = rangeMinMax2L0Excess v in-            let excess    = fromIntegral (excesses !!! fromIntegral i)  :: Int in-            rmm2FindClose v (fromIntegral (excess + fromIntegral s)) (p + 64) FindFromL0-rmm2FindClose v s p FindL1 =-  let !i = p `div` (64 * pageSizeL1) in-  let !mins = rangeMinMax2L1Min v in-  let !minE = fromIntegral (mins !!! fromIntegral i) :: Int in-  if fromIntegral s + minE <= 0-    then rmm2FindClose v s p FindL0-    else if 0 <= p && p < bitLength v-      then if v `newCloseAt` p && s <= 1-        then Just p-        else  let excesses  = rangeMinMax2L1Excess v in-              let excess    = fromIntegral (excesses !!! fromIntegral i)  :: Int in-              rmm2FindClose v (fromIntegral (excess + fromIntegral s)) (p + (64 * pageSizeL1)) FindFromL1-      else Nothing-rmm2FindClose v s p FindL2 =-  let !i = p `div` (64 * pageSizeL2) in-  let !mins = rangeMinMax2L2Min v in-  let !minE = fromIntegral (mins !!! fromIntegral i) :: Int in-  if fromIntegral s + minE <= 0-    then rmm2FindClose v s p FindL1-    else if 0 <= p && p < bitLength v-      then if v `newCloseAt` p && s <= 1-        then Just p-        else  let excesses  = rangeMinMax2L2Excess v in-              let excess    = fromIntegral (excesses !!! fromIntegral i)  :: Int in-              rmm2FindClose v (fromIntegral (excess + fromIntegral s)) (p + (64 * pageSizeL2)) FindFromL2-      else Nothing-rmm2FindClose v s p FindL3 =-  let !i = p `div` (64 * pageSizeL3) in-  let !mins = rangeMinMax2L3Min v in-  let !minE = fromIntegral (mins !!! fromIntegral i) :: Int in-  if fromIntegral s + minE <= 0-    then rmm2FindClose v s p FindL2-    else if 0 <= p && p < bitLength v-      then if v `newCloseAt` p && s <= 1-        then Just p-        else  let excesses  = rangeMinMax2L3Excess v in-              let excess    = fromIntegral (excesses !!! fromIntegral i)  :: Int in-              rmm2FindClose v (fromIntegral (excess + fromIntegral s)) (p + (64 * pageSizeL3)) FindFromL3-        else Nothing-rmm2FindClose v s p FindL4 =-  let !i = p `div` (64 * pageSizeL4) in-  let !mins = rangeMinMax2L4Min v in-  let !minE = fromIntegral (mins !!! fromIntegral i) :: Int in-  if fromIntegral s + minE <= 0-    then rmm2FindClose v s p FindL3-    else if 0 <= p && p < bitLength v-      then if v `newCloseAt` p && s <= 1-        then Just p-        else  let excesses  = rangeMinMax2L4Excess v in-              let excess    = fromIntegral (excesses !!! fromIntegral i)  :: Int in-              rmm2FindClose v (fromIntegral (excess + fromIntegral s)) (p + (64 * pageSizeL4)) FindFromL4-        else Nothing-rmm2FindClose v s p FindFromL0-  | p `mod` 64 == 0             = rmm2FindClose v s p FindFromL1-  | 0 <= p && p < bitLength v   = rmm2FindClose v s p FindBP-  | otherwise                   = Nothing-rmm2FindClose v s p FindFromL1-  | p `mod` (64 * pageSizeL1) == 0  = if 0 <= p && p < bitLength v then rmm2FindClose v s p FindFromL2 else Nothing-  | 0 <= p && p < bitLength v       = rmm2FindClose v s p FindL0-  | otherwise                       = Nothing-rmm2FindClose v s p FindFromL2-  | p `mod` (64 * pageSizeL2) == 0  = if 0 <= p && p < bitLength v then rmm2FindClose v s p FindFromL3 else Nothing-  | 0 <= p && p < bitLength v       = rmm2FindClose v s p FindL1-  | otherwise                       = Nothing-rmm2FindClose v s p FindFromL3-  | p `mod` (64 * pageSizeL3) == 0  = if 0 <= p && p < bitLength v then rmm2FindClose v s p FindFromL4 else Nothing-  | 0 <= p && p < bitLength v       = rmm2FindClose v s p FindL2-  | otherwise                       = Nothing-rmm2FindClose v s p FindFromL4-  | p `mod` (64 * pageSizeL4) == 0  = if 0 <= p && p < bitLength v then rmm2FindClose v s p FindL4 else Nothing-  | 0 <= p && p < bitLength v       = rmm2FindClose v s p FindL3-  | otherwise                       = Nothing-{-# INLINE rmm2FindClose #-}--instance TestBit a => TestBit (RangeMinMax2 a) where-  (.?.) = (.?.) . rangeMinMax2BP-  {-# INLINE (.?.) #-}--instance Rank1 a => Rank1 (RangeMinMax2 a) where-  rank1 = rank1 . rangeMinMax2BP-  {-# INLINE rank1 #-}--instance Rank0 a => Rank0 (RangeMinMax2 a) where-  rank0 = rank0 . rangeMinMax2BP-  {-# INLINE rank0 #-}--instance BitLength a => BitLength (RangeMinMax2 a) where-  bitLength = bitLength . rangeMinMax2BP-  {-# INLINE bitLength #-}--instance OpenAt a => OpenAt (RangeMinMax2 a) where-  openAt = openAt . rangeMinMax2BP-  {-# INLINE openAt #-}--instance CloseAt a => CloseAt (RangeMinMax2 a) where-  closeAt = closeAt . rangeMinMax2BP-  {-# INLINE closeAt #-}--instance NewCloseAt a => NewCloseAt (RangeMinMax2 a) where-  newCloseAt = newCloseAt . rangeMinMax2BP-  {-# INLINE newCloseAt #-}--instance FindOpenN a => FindOpenN (RangeMinMax2 a) where-  findOpenN = findOpenN . rangeMinMax2BP-  {-# INLINE findOpenN #-}--instance (BitLength a, FindCloseN a, NewCloseAt a) => FindCloseN (RangeMinMax2 a) where-  findCloseN v s p  = (+ 1) `fmap` rmm2FindClose v (fromIntegral s) (p - 1) FindFromL0-  {-# INLINE findCloseN  #-}--instance (BitLength a, NewCloseAt a, CloseAt a, FindCloseN a) => FindClose (RangeMinMax2 a) where-  findClose v p = if v `closeAt` p then Just p else findCloseN v 1 (p + 1)-  {-# INLINE findClose #-}--instance (OpenAt a, FindOpenN a) => FindOpen (RangeMinMax2 a) where-  findOpen v p = if v `openAt`  p then Just p else findOpenN  v 0 (p - 1)-  {-# INLINE findOpen #-}--instance FindOpenN a => Enclose (RangeMinMax2 a) where-  enclose v = findOpenN v 1-  {-# INLINE enclose #-}--instance (BitLength a, NewCloseAt a, CloseAt a, OpenAt a, FindOpenN a, FindCloseN a) => BalancedParens (RangeMinMax2 a)

@@ -23,27 +23,27 @@  spec :: Spec spec = describe "HaskellWorks.Data.BalancedParens.Internal.ParensSeqSpec" $ do-  it "fromWord64s should produce Rmm of the right size" $ requireProperty $ do+  it "fromWord64s should produce Rm of the right size" $ requireProperty $ do     ws <- forAll $ G.list (R.linear 0 10) (G.word64 R.constantBounded)      PS.size (PS.fromWord64s ws) === fromIntegral (length ws * 64)-  it "fromWord64s should produce Rmm with the right data" $ requireProperty $ do+  it "fromWord64s should produce Rm with the right data" $ requireProperty $ do     wns <- forAll $ G.list (R.linear 0 10) $ (,)       <$> G.word64 R.constantBounded       <*> G.count (R.linear 1 64)      PS.size (PS.fromPartialWord64s wns) === sum (snd <$> wns)-  it "fromWord64s should produce Rmm with the right data" $ requireProperty $ do+  it "fromWord64s should produce Rm with the right data" $ requireProperty $ do     ws <- forAll $ G.list (R.linear 0 10) (G.word64 R.constantBounded)      PS.toPartialWord64s (PS.fromWord64s ws) === zip ws (repeat 64)-  it "fromPartialWord64s should produce Rmm with the right data" $ requireProperty $ do+  it "fromPartialWord64s should produce Rm with the right data" $ requireProperty $ do     wns <- forAll $ G.list (R.linear 0 10) $ (,)       <$> G.word64 R.constantBounded       <*> G.count (R.linear 1 64)      PS.toPartialWord64s (PS.fromPartialWord64s wns) === wns-  it "fromBools should produce Rmm with the right data" $ requireProperty $ do+  it "fromBools should produce Rm with the right data" $ requireProperty $ do     ws <- forAll $ G.list (R.linear 0 10) (G.word64 R.constantBounded)      PS.toPartialWord64s (PS.fromBools (L.toBools ws)) === zip ws (repeat 64)@@ -98,15 +98,15 @@     nodeCount <- forAll $ pure (fromIntegral (length bs `div` 2))     ranked    <- forAll $ G.count (R.linear 1 nodeCount)     pos       <- forAll $ pure $ select1 bs ranked-    rmm       <- forAll $ pure $ PS.fromBools bs+    rm       <- forAll $ pure $ PS.fromBools bs -    PS.nextSibling rmm pos === BP.nextSibling bs pos+    PS.nextSibling rm pos === BP.nextSibling bs pos   it "nextSibling on ()()" $ requireTest $ do     bs        <- forAll $ pure [True , False , True , False]     pos       <- forAll $ pure 1-    rmm       <- forAll $ pure $ PS.fromBools bs+    rm       <- forAll $ pure $ PS.fromBools bs -    PS.nextSibling rmm pos === BP.nextSibling bs pos+    PS.nextSibling rm pos === BP.nextSibling bs pos   it "(><) should append" $ requireTest $ do     bs1       <- forAll $ G.bpBools (R.linear 1 1000)     bs2       <- forAll $ G.bpBools (R.linear 1 1000)

@@ -0,0 +1,135 @@+{-# LANGUAGE BangPatterns               #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE OverloadedStrings          #-}+{-# LANGUAGE ScopedTypeVariables        #-}++module HaskellWorks.Data.BalancedParens.RangeMin2Spec where++import Data.Word+import HaskellWorks.Data.BalancedParens+import HaskellWorks.Data.BalancedParens.RangeMin+import HaskellWorks.Data.Bits.BitShow+import HaskellWorks.Data.Bits.FromBitTextByteString+import Test.Hspec++import qualified Data.Vector.Storable as DVS++{-# 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++maxVectorSize :: Int+maxVectorSize = 16384+{-# INLINE maxVectorSize #-}++spec :: Spec+spec = describe "HaskellWorks.Data.BalancedParens.RangeMinSpec2" $ do+  -- let maxSuccessDefault = 5+  it "For a simple bit string can find close" $ do+    let v = fromBitTextByteString "11101111 10100101 01111110 10110010 10111011 10111011 00011111 11011100" :: DVS.Vector Word64+    let !rm = mkRangeMin v+    findClose rm 61 `shouldBe` findClose v 61+  -- it "findClose should return the same result" $ do+  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do+  --     forAll (vectorSizedBetween 1 4) $ \(ShowVector v) -> do+  --       let !rm = mkRangeMin v+  --       let len = bitLength v+  --       [findClose rm i | i <- [1..len]] `shouldBe `[findClose v i | i <- [1..len]]+  -- it "findClose should return the same result over all counts" $ do+  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do+  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do+  --       forAll (choose (1, bitLength v)) $ \p -> do+  --         let !rm = mkRangeMin v+  --         findClose rm p `shouldBe` findClose v p+  -- it "nextSibling should return the same result" $ do+  --   forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do+  --     let !rm = mkRangeMin v+  --     nextSibling rm 0 `shouldBe` nextSibling v 0+  -- it "nextSibling should return the same result over all counts" $ do+  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do+  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do+  --       forAll (choose (1, bitLength v)) $ \p -> do+  --         let !rm = mkRangeMin v+  --         nextSibling rm p `shouldBe` nextSibling v p+  -- it "rangeMinBP should match" $ do+  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do+  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do+  --       let !rm1 = mkRangeMin   v+  --       let !rm2 = mkRangeMin2  v+  --       rangeMin2BP rm2 `shouldBe` rangeMinBP rm1+  -- it "rangeMinL0Excess should match" $ do+  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do+  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do+  --       let !rm1 = mkRangeMin   v+  --       let !rm2 = mkRangeMin2  v+  --       rangeMin2L0Excess rm2 `shouldBe` rangeMinL0Excess rm1+  -- it "rangeMinL0Min should match" $ do+  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do+  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do+  --       let !rm1 = mkRangeMin   v+  --       let !rm2 = mkRangeMin2  v+  --       rangeMin2L0Min rm2 `shouldBe` rangeMinL0Min rm1+  -- it "rangeMinL0Max should match" $ do+  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do+  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do+  --       let !rm1 = mkRangeMin   v+  --       let !rm2 = mkRangeMin2  v+  --       rangeMin2L0Max rm2 `shouldBe` rangeMinL0Max rm1+  -- it "rangeMinL1Min should match" $ do+  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do+  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do+  --       let !rm1 = mkRangeMin   v+  --       let !rm2 = mkRangeMin2  v+  --       rangeMin2L1Min rm2 `shouldBe` rangeMinL1Min rm1+  -- it "rangeMinL1Max should match" $ do+  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do+  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do+  --       let !rm1 = mkRangeMin   v+  --       let !rm2 = mkRangeMin2  v+  --       rangeMin2L1Max rm2 `shouldBe` rangeMinL1Max rm1+  -- it "rangeMinL1Excess should match" $ do+  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do+  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do+  --       let !rm1 = mkRangeMin   v+  --       let !rm2 = mkRangeMin2  v+  --       rangeMin2L1Excess rm2 `shouldBe` rangeMinL1Excess rm1+  -- it "rangeMinL2Min should match" $ do+  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do+  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do+  --       let !rm1 = mkRangeMin   v+  --       let !rm2 = mkRangeMin2  v+  --       rangeMin2L2Min rm2 `shouldBe` rangeMinL2Min rm1+  -- it "rangeMinL2Max should match" $ do+  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do+  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do+  --       let !rm1 = mkRangeMin   v+  --       let !rm2 = mkRangeMin2  v+  --       rangeMin2L2Max rm2 `shouldBe` rangeMinL2Max rm1+  -- it "rangeMinL2Excess should match" $ do+  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do+  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do+  --       let !rm1 = mkRangeMin   v+  --       let !rm2 = mkRangeMin2  v+  --       rangeMin2L2Excess rm2 `shouldBe` rangeMinL2Excess rm1+  -- describe "For example long bit string" $ do+  --   let v = fromBitTextByteString " \+  --     \ 01101101 01111100 10011111 01100101 11111100 01101111 00000000 00000000 10001010 11000000 01000010 01010010 01001101 01000101 00000000 00000000 \+  --     \ " :: DVS.Vector Word64+  --   let !rm1 = mkRangeMin   v+  --   let !rm2 = mkRangeMin2  v+  --   it "l0 max matches" $ do+  --     rangeMin2L0Max rm2 `shouldBe` rangeMinL0Max rm1+  --   it "l1 max matches" $ do+  --     rangeMin2L1Max rm2 `shouldBe` rangeMinL1Max rm1+  --   -- it "l2 max matches" $ do+  --   --   rangeMin2L2Max rm2 `shouldBe` rangeMinL2Max rm1+  --   it "l0 min matches" $ do+  --     rangeMin2L0Min rm2 `shouldBe` rangeMinL0Min rm1+  --   it "l1 min matches" $ do+  --     rangeMin2L1Min rm2 `shouldBe` rangeMinL1Min rm1+  --   it "l2 min matches" $ do+  --     rangeMin2L2Min rm2 `shouldBe` rangeMinL2Min rm1

@@ -1,135 +0,0 @@-{-# LANGUAGE BangPatterns               #-}-{-# LANGUAGE GeneralizedNewtypeDeriving #-}-{-# LANGUAGE OverloadedStrings          #-}-{-# LANGUAGE ScopedTypeVariables        #-}--module HaskellWorks.Data.BalancedParens.RangeMinMax2Spec where--import Data.Word-import HaskellWorks.Data.BalancedParens-import HaskellWorks.Data.BalancedParens.RangeMinMax-import HaskellWorks.Data.Bits.BitShow-import HaskellWorks.Data.Bits.FromBitTextByteString-import Test.Hspec--import qualified Data.Vector.Storable as DVS--{-# 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--maxVectorSize :: Int-maxVectorSize = 16384-{-# INLINE maxVectorSize #-}--spec :: Spec-spec = describe "HaskellWorks.Data.BalancedParens.RangeMinMaxSpec2" $ do-  -- let maxSuccessDefault = 5-  it "For a simple bit string can find close" $ do-    let v = fromBitTextByteString "11101111 10100101 01111110 10110010 10111011 10111011 00011111 11011100" :: DVS.Vector Word64-    let !rmm = mkRangeMinMax v-    findClose rmm 61 `shouldBe` findClose v 61-  -- it "findClose should return the same result" $ do-  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do-  --     forAll (vectorSizedBetween 1 4) $ \(ShowVector v) -> do-  --       let !rmm = mkRangeMinMax v-  --       let len = bitLength v-  --       [findClose rmm i | i <- [1..len]] `shouldBe `[findClose v i | i <- [1..len]]-  -- it "findClose should return the same result over all counts" $ do-  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do-  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do-  --       forAll (choose (1, bitLength v)) $ \p -> do-  --         let !rmm = mkRangeMinMax v-  --         findClose rmm p `shouldBe` findClose v p-  -- it "nextSibling should return the same result" $ do-  --   forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do-  --     let !rmm = mkRangeMinMax v-  --     nextSibling rmm 0 `shouldBe` nextSibling v 0-  -- it "nextSibling should return the same result over all counts" $ do-  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do-  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do-  --       forAll (choose (1, bitLength v)) $ \p -> do-  --         let !rmm = mkRangeMinMax v-  --         nextSibling rmm p `shouldBe` nextSibling v p-  -- it "rangeMinMaxBP should match" $ do-  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do-  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do-  --       let !rmm1 = mkRangeMinMax   v-  --       let !rmm2 = mkRangeMinMax2  v-  --       rangeMinMax2BP rmm2 `shouldBe` rangeMinMaxBP rmm1-  -- it "rangeMinMaxL0Excess should match" $ do-  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do-  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do-  --       let !rmm1 = mkRangeMinMax   v-  --       let !rmm2 = mkRangeMinMax2  v-  --       rangeMinMax2L0Excess rmm2 `shouldBe` rangeMinMaxL0Excess rmm1-  -- it "rangeMinMaxL0Min should match" $ do-  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do-  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do-  --       let !rmm1 = mkRangeMinMax   v-  --       let !rmm2 = mkRangeMinMax2  v-  --       rangeMinMax2L0Min rmm2 `shouldBe` rangeMinMaxL0Min rmm1-  -- it "rangeMinMaxL0Max should match" $ do-  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do-  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do-  --       let !rmm1 = mkRangeMinMax   v-  --       let !rmm2 = mkRangeMinMax2  v-  --       rangeMinMax2L0Max rmm2 `shouldBe` rangeMinMaxL0Max rmm1-  -- it "rangeMinMaxL1Min should match" $ do-  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do-  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do-  --       let !rmm1 = mkRangeMinMax   v-  --       let !rmm2 = mkRangeMinMax2  v-  --       rangeMinMax2L1Min rmm2 `shouldBe` rangeMinMaxL1Min rmm1-  -- it "rangeMinMaxL1Max should match" $ do-  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do-  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do-  --       let !rmm1 = mkRangeMinMax   v-  --       let !rmm2 = mkRangeMinMax2  v-  --       rangeMinMax2L1Max rmm2 `shouldBe` rangeMinMaxL1Max rmm1-  -- it "rangeMinMaxL1Excess should match" $ do-  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do-  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do-  --       let !rmm1 = mkRangeMinMax   v-  --       let !rmm2 = mkRangeMinMax2  v-  --       rangeMinMax2L1Excess rmm2 `shouldBe` rangeMinMaxL1Excess rmm1-  -- it "rangeMinMaxL2Min should match" $ do-  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do-  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do-  --       let !rmm1 = mkRangeMinMax   v-  --       let !rmm2 = mkRangeMinMax2  v-  --       rangeMinMax2L2Min rmm2 `shouldBe` rangeMinMaxL2Min rmm1-  -- it "rangeMinMaxL2Max should match" $ do-  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do-  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do-  --       let !rmm1 = mkRangeMinMax   v-  --       let !rmm2 = mkRangeMinMax2  v-  --       rangeMinMax2L2Max rmm2 `shouldBe` rangeMinMaxL2Max rmm1-  -- it "rangeMinMaxL2Excess should match" $ do-  --   quickCheckWith stdArgs { maxSuccess = maxSuccessDefault } $ do-  --     forAll (vectorSizedBetween 1 maxVectorSize) $ \(ShowVector v) -> do-  --       let !rmm1 = mkRangeMinMax   v-  --       let !rmm2 = mkRangeMinMax2  v-  --       rangeMinMax2L2Excess rmm2 `shouldBe` rangeMinMaxL2Excess rmm1-  -- describe "For example long bit string" $ do-  --   let v = fromBitTextByteString " \-  --     \ 01101101 01111100 10011111 01100101 11111100 01101111 00000000 00000000 10001010 11000000 01000010 01010010 01001101 01000101 00000000 00000000 \-  --     \ " :: DVS.Vector Word64-  --   let !rmm1 = mkRangeMinMax   v-  --   let !rmm2 = mkRangeMinMax2  v-  --   it "l0 max matches" $ do-  --     rangeMinMax2L0Max rmm2 `shouldBe` rangeMinMaxL0Max rmm1-  --   it "l1 max matches" $ do-  --     rangeMinMax2L1Max rmm2 `shouldBe` rangeMinMaxL1Max rmm1-  --   -- it "l2 max matches" $ do-  --   --   rangeMinMax2L2Max rmm2 `shouldBe` rangeMinMaxL2Max rmm1-  --   it "l0 min matches" $ do-  --     rangeMinMax2L0Min rmm2 `shouldBe` rangeMinMaxL0Min rmm1-  --   it "l1 min matches" $ do-  --     rangeMinMax2L1Min rmm2 `shouldBe` rangeMinMaxL1Min rmm1-  --   it "l2 min matches" $ do-  --     rangeMinMax2L2Min rmm2 `shouldBe` rangeMinMaxL2Min rmm1

@@ -1,59 +0,0 @@-{-# LANGUAGE BangPatterns               #-}-{-# LANGUAGE GeneralizedNewtypeDeriving #-}-{-# LANGUAGE OverloadedStrings          #-}-{-# LANGUAGE ScopedTypeVariables        #-}--module HaskellWorks.Data.BalancedParens.RangeMinMaxSpec where--import Data.Word-import HaskellWorks.Data.BalancedParens-import HaskellWorks.Data.BalancedParens.RangeMinMax-import HaskellWorks.Data.Bits.BitLength-import HaskellWorks.Data.Bits.BitShow-import HaskellWorks.Data.Bits.FromBitTextByteString-import HaskellWorks.Hspec.Hedgehog-import Hedgehog-import Test.Hspec--import qualified Data.Vector.Storable                 as DVS-import qualified HaskellWorks.Data.BalancedParens.Gen as G-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) #-}--newtype ShowVector a = ShowVector a deriving (Eq, BitShow)--instance BitShow a => Show (ShowVector a) where-  show = bitShow--factor :: Int-factor = 16384-{-# INLINE factor #-}--spec :: Spec-spec = describe "HaskellWorks.Data.BalancedParens.RangeMinMaxSpec" $ do-  it "For a simple bit string can find close" $ requireTest $ do-    let v = fromBitTextByteString "11101111 10100101 01111110 10110010 10111011 10111011 00011111 11011100" :: DVS.Vector Word64-    let !rmm = mkRangeMinMax v-    findClose rmm 61 === findClose v 61-  it "findClose should return the same result" $ requireProperty $ do-    v <- forAll $ G.storableVector (R.linear 1 4) (G.word64 R.constantBounded)-    let !rmm = mkRangeMinMax v-    let len = bitLength v-    [findClose rmm i | i <- [1..len]] === [findClose v i | i <- [1..len]]-  it "findClose should return the same result over all counts" $ requireProperty $ do-    v <- forAll $ G.storableVector (R.linear 1 factor) (G.word64 R.constantBounded)-    p <- forAll $ G.count (R.linear 1 (bitLength v))-    let !rmm = mkRangeMinMax v-    findClose rmm p === findClose v p-  it "nextSibling should return the same result" $ requireProperty $ do-    v <- forAll $ G.storableVector (R.linear 1 factor) (G.word64 R.constantBounded)-    let !rmm = mkRangeMinMax v-    nextSibling rmm 0 === nextSibling v 0-  it "nextSibling should return the same result over all counts" $ requireProperty $ do-    v <- forAll $ G.storableVector (R.linear 1 factor) (G.word64 R.constantBounded)-    p <- forAll $ G.count (R.linear 1 (bitLength v))-    let !rmm = mkRangeMinMax v-    nextSibling rmm p === nextSibling v p

@@ -0,0 +1,59 @@+{-# LANGUAGE BangPatterns               #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE OverloadedStrings          #-}+{-# LANGUAGE ScopedTypeVariables        #-}++module HaskellWorks.Data.BalancedParens.RangeMinSpec where++import Data.Word+import HaskellWorks.Data.BalancedParens+import HaskellWorks.Data.BalancedParens.RangeMin+import HaskellWorks.Data.Bits.BitLength+import HaskellWorks.Data.Bits.BitShow+import HaskellWorks.Data.Bits.FromBitTextByteString+import HaskellWorks.Hspec.Hedgehog+import Hedgehog+import Test.Hspec++import qualified Data.Vector.Storable                 as DVS+import qualified HaskellWorks.Data.BalancedParens.Gen as G+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) #-}++newtype ShowVector a = ShowVector a deriving (Eq, BitShow)++instance BitShow a => Show (ShowVector a) where+  show = bitShow++factor :: Int+factor = 16384+{-# INLINE factor #-}++spec :: Spec+spec = describe "HaskellWorks.Data.BalancedParens.RangeMinSpec" $ do+  it "For a simple bit string can find close" $ requireTest $ do+    let v = fromBitTextByteString "11101111 10100101 01111110 10110010 10111011 10111011 00011111 11011100" :: DVS.Vector Word64+    let !rm = mkRangeMin v+    findClose rm 61 === findClose v 61+  it "findClose should return the same result" $ requireProperty $ do+    v <- forAll $ G.storableVector (R.linear 1 4) (G.word64 R.constantBounded)+    let !rm = mkRangeMin v+    let len = bitLength v+    [findClose rm i | i <- [1..len]] === [findClose v i | i <- [1..len]]+  it "findClose should return the same result over all counts" $ requireProperty $ do+    v <- forAll $ G.storableVector (R.linear 1 factor) (G.word64 R.constantBounded)+    p <- forAll $ G.count (R.linear 1 (bitLength v))+    let !rm = mkRangeMin v+    findClose rm p === findClose v p+  it "nextSibling should return the same result" $ requireProperty $ do+    v <- forAll $ G.storableVector (R.linear 1 factor) (G.word64 R.constantBounded)+    let !rm = mkRangeMin v+    nextSibling rm 0 === nextSibling v 0+  it "nextSibling should return the same result over all counts" $ requireProperty $ do+    v <- forAll $ G.storableVector (R.linear 1 factor) (G.word64 R.constantBounded)+    p <- forAll $ G.count (R.linear 1 (bitLength v))+    let !rm = mkRangeMin v+    nextSibling rm p === nextSibling v p