packages feed

hw-balancedparens 0.3.0.4 → 0.3.0.5

raw patch · 14 files changed

+208/−288 lines, 14 filesdep ~hw-bitsPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: hw-bits

API changes (from Hackage documentation)

- HaskellWorks.Data.BalancedParens.CloseAt: instance HaskellWorks.Data.BalancedParens.CloseAt.CloseAt (HaskellWorks.Data.Bits.Broadword.Broadword GHC.Word.Word64)
- HaskellWorks.Data.BalancedParens.FindClose: instance HaskellWorks.Data.BalancedParens.FindClose.FindClose (HaskellWorks.Data.Bits.Broadword.Broadword GHC.Word.Word64)
- HaskellWorks.Data.BalancedParens.OpenAt: instance HaskellWorks.Data.BalancedParens.OpenAt.OpenAt (HaskellWorks.Data.Bits.Broadword.Broadword GHC.Word.Word64)
+ HaskellWorks.Data.BalancedParens.CloseAt: instance HaskellWorks.Data.BalancedParens.CloseAt.CloseAt (HaskellWorks.Data.Bits.Broadword.Type.Broadword GHC.Word.Word64)
+ HaskellWorks.Data.BalancedParens.FindClose: instance HaskellWorks.Data.BalancedParens.FindClose.FindClose (HaskellWorks.Data.Bits.Broadword.Type.Broadword GHC.Word.Word64)
+ HaskellWorks.Data.BalancedParens.FindCloseN: findClose' :: (BitLength a, CloseAt a, TestBit a) => a -> Count -> Count -> Maybe Count
+ HaskellWorks.Data.BalancedParens.Internal.Trace: traceW :: Show a => String -> a -> a
+ HaskellWorks.Data.BalancedParens.Internal.Vector.Storable: dropTake :: Storable a => Int -> Int -> Vector a -> Vector a
+ HaskellWorks.Data.BalancedParens.Internal.Vector.Storable: dropTakeFill :: Storable a => Int -> Int -> a -> Vector a -> Vector a
+ HaskellWorks.Data.BalancedParens.Internal.Vector.Storable: lastOrZero :: (Storable a, Integral a) => Vector a -> a
+ HaskellWorks.Data.BalancedParens.Internal.Vector.Storable: pageFill :: Storable a => Int -> Int -> a -> Vector a -> Vector a
+ HaskellWorks.Data.BalancedParens.Internal.Vector.Storable: reword :: (Storable a, Integral a, Storable b, Num b) => Vector a -> Vector b
+ HaskellWorks.Data.BalancedParens.OpenAt: instance HaskellWorks.Data.BalancedParens.OpenAt.OpenAt (HaskellWorks.Data.Bits.Broadword.Type.Broadword GHC.Word.Word64)

Files

bench/Main.hs view
@@ -6,7 +6,7 @@ import Data.Semigroup                               ((<>)) import Data.Word import HaskellWorks.Data.BalancedParens.FindClose-import HaskellWorks.Data.Bits.Broadword+import HaskellWorks.Data.Bits.Broadword.Type import HaskellWorks.Data.Bits.FromBitTextByteString import HaskellWorks.Data.Naive import HaskellWorks.Data.Ops
hw-balancedparens.cabal view
@@ -1,7 +1,7 @@ cabal-version:  2.2  name:                   hw-balancedparens-version:                0.3.0.4+version:                0.3.0.5 synopsis:               Balanced parentheses description:            Balanced parentheses. category:               Data, Bit, Succinct Data Structures, Data Structures@@ -29,7 +29,7 @@ common hedgehog                 { build-depends: hedgehog                 >= 1.0        && < 1.1    } common hspec                    { build-depends: hspec                    >= 2.2        && < 3.0    } common hw-hspec-hedgehog        { build-depends: hw-hspec-hedgehog        >= 0.1        && < 0.2    }-common hw-bits                  { build-depends: hw-bits                  >= 0.4.0.0    && < 0.8    }+common hw-bits                  { build-depends: hw-bits                  >= 0.7.1.2    && < 0.8    } common hw-excess                { build-depends: hw-excess                >= 0.2.2.0    && < 0.3    } common hw-fingertree            { build-depends: hw-fingertree            >= 0.1.1.0    && < 0.2    } common hw-prim                  { build-depends: hw-prim                  >= 0.6.2.25   && < 0.7    }@@ -68,6 +68,8 @@                         HaskellWorks.Data.BalancedParens.Internal.List                         HaskellWorks.Data.BalancedParens.Internal.ParensSeq                         HaskellWorks.Data.BalancedParens.Internal.RoseTree+                        HaskellWorks.Data.BalancedParens.Internal.Trace+                        HaskellWorks.Data.BalancedParens.Internal.Vector.Storable                         HaskellWorks.Data.BalancedParens.Internal.Word                         HaskellWorks.Data.BalancedParens.NewCloseAt                         HaskellWorks.Data.BalancedParens.NewOpenAt@@ -108,6 +110,7 @@   main-is:              Spec.hs   other-modules:        HaskellWorks.Data.BalancedParens.Internal.BroadwordSpec                         HaskellWorks.Data.BalancedParens.Internal.ParensSeqSpec+                        HaskellWorks.Data.BalancedParens.FindCloseNSpec                         HaskellWorks.Data.BalancedParens.RangeMin2Spec                         HaskellWorks.Data.BalancedParens.RangeMinSpec                         HaskellWorks.Data.BalancedParens.SimpleSpec
src/HaskellWorks/Data/BalancedParens/Broadword.hs view
@@ -16,10 +16,16 @@ import Data.Int import Data.Word import HaskellWorks.Data.Bits.BitWise-import HaskellWorks.Data.Bits.Broadword+import HaskellWorks.Data.Bits.Broadword.Word64+import HaskellWorks.Data.Bits.Word64  import qualified Data.Bits as DB +-- Source:+--    Broadword Implementation of Parenthesis Queries+--    Sebastiano Vigna+--    Dipartimento di Scienze dell’Informazione+--    Università degli Studi di Milano, Italy findCloseW64 :: Word64 -> Word64 findCloseW64 x =                                                                                     -- let !_ = traceW "x00" x   in   let !b00 = x - ((x .&. 0xaaaaaaaaaaaaaaaa) .>. 1)                                               in -- let !_ = traceW "b00" b00 in@@ -29,17 +35,17 @@   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
src/HaskellWorks/Data/BalancedParens/CloseAt.hs view
@@ -4,12 +4,12 @@   ( CloseAt(..)   ) where -import Data.Vector.Storable             as DVS+import Data.Vector.Storable                  as DVS import Data.Word import HaskellWorks.Data.Bits.BitLength import HaskellWorks.Data.Bits.BitShown import HaskellWorks.Data.Bits.BitWise-import HaskellWorks.Data.Bits.Broadword+import HaskellWorks.Data.Bits.Broadword.Type import HaskellWorks.Data.Naive import HaskellWorks.Data.Positioning
src/HaskellWorks/Data/BalancedParens/FindClose.hs view
@@ -10,7 +10,7 @@ import HaskellWorks.Data.BalancedParens.FindCloseN import HaskellWorks.Data.Bits.BitShown import HaskellWorks.Data.Bits.BitWise-import HaskellWorks.Data.Bits.Broadword+import HaskellWorks.Data.Bits.Broadword.Type import HaskellWorks.Data.Naive import HaskellWorks.Data.Positioning
src/HaskellWorks/Data/BalancedParens/FindCloseN.hs view
@@ -2,6 +2,7 @@  module HaskellWorks.Data.BalancedParens.FindCloseN   ( FindCloseN(..)+  , findClose'   ) where  import Data.Word
+ src/HaskellWorks/Data/BalancedParens/Internal/Trace.hs view
@@ -0,0 +1,9 @@+module HaskellWorks.Data.BalancedParens.Internal.Trace+  ( traceW+  ) where++import Data.Semigroup ((<>))+import Debug.Trace++traceW :: Show a => String -> a -> a+traceW s a = trace (s <> " = " <> show a) a
+ src/HaskellWorks/Data/BalancedParens/Internal/Vector/Storable.hs view
@@ -0,0 +1,39 @@+module HaskellWorks.Data.BalancedParens.Internal.Vector.Storable+  ( lastOrZero+  , reword+  , dropTake+  , dropTakeFill+  , pageFill+  ) where++import qualified Data.Vector.Storable as DVS++lastOrZero :: (DVS.Storable a, Integral a) => DVS.Vector a -> a+lastOrZero v = if not (DVS.null v) then DVS.last v else 0+{-# INLINE lastOrZero #-}++reword :: (DVS.Storable a, Integral a, DVS.Storable b, Num b) => DVS.Vector a -> DVS.Vector b+reword v = DVS.generate (DVS.length v) (\i -> fromIntegral (v DVS.! i))+{-# INLINE reword #-}++dropTake :: DVS.Storable a => Int -> Int -> DVS.Vector a -> DVS.Vector a+dropTake n o = DVS.take o . DVS.drop n+{-# INLINE dropTake #-}++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 #-}++-- | Return the n-th page of size s from the input vector.  In the case where there isn't+-- sufficient data to fill the page from the input vector, then the remainder of the page+-- is filled with a.+pageFill :: DVS.Storable a+  => Int          -- ^ The n-th page to retrieve+  -> Int          -- ^ The page size+  -> a            -- ^ The element value to fill the page when input vector has insufficient values+  -> DVS.Vector a -- ^ The input vector+  -> DVS.Vector a -- ^ The page+pageFill n s = dropTakeFill (n * s) s+{-# INLINE pageFill #-}
src/HaskellWorks/Data/BalancedParens/OpenAt.hs view
@@ -8,7 +8,7 @@ import HaskellWorks.Data.Bits.BitLength import HaskellWorks.Data.Bits.BitShown import HaskellWorks.Data.Bits.BitWise-import HaskellWorks.Data.Bits.Broadword+import HaskellWorks.Data.Bits.Broadword.Type import HaskellWorks.Data.Naive import HaskellWorks.Data.Positioning
src/HaskellWorks/Data/BalancedParens/RangeMin.hs view
@@ -36,7 +36,8 @@ import HaskellWorks.Data.Vector.AsVector64 import Prelude                                         hiding (length) -import qualified Data.Vector.Storable as DVS+import qualified Data.Vector.Storable                                      as DVS+import qualified HaskellWorks.Data.BalancedParens.Internal.Vector.Storable as DVS  data RangeMin a = RangeMin   { rangeMinBP       :: !a@@ -76,9 +77,9 @@ mkRangeMin bp = RangeMin   { rangeMinBP       = bp   , rangeMinL0Min    = rmL0Min-  , rangeMinL0Excess = dvsReword rmL0Excess+  , rangeMinL0Excess = DVS.reword rmL0Excess   , rangeMinL1Min    = rmL1Min-  , rangeMinL1Excess = dvsReword rmL1Excess+  , rangeMinL1Excess = DVS.reword rmL1Excess   , rangeMinL2Min    = rmL2Min   , rangeMinL2Excess = rmL2Excess   }@@ -88,33 +89,15 @@         lenL1         = (DVS.length rmL0Min `div` pageSizeL1) + 1 :: Int         lenL2         = (DVS.length rmL0Min `div` pageSizeL2) + 1 :: Int         allMinL0      = DVS.generate lenL0 (\i -> if i == lenBP then MinExcess (-64) (-64) else minExcess1 (bpv !!! fromIntegral i))-        allMinL1      = DVS.generate lenL1 (\i -> minExcess1 (dropTake (i * pageSizeL1) pageSizeL1 bpv))-        allMinL2      = DVS.generate lenL2 (\i -> minExcess1 (dropTake (i * pageSizeL2) pageSizeL2 bpv))+        allMinL1      = DVS.generate lenL1 (\i -> minExcess1 (DVS.dropTake (i * pageSizeL1) pageSizeL1 bpv))+        allMinL2      = DVS.generate lenL2 (\i -> minExcess1 (DVS.dropTake (i * pageSizeL2) pageSizeL2 bpv))         -- Note: (0xffffffffffffffc0 :: Int64) = -64-        rmL0Excess    = DVS.generate lenL0 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL0 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16-        rmL1Excess    = DVS.generate lenL1 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL1 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16-        rmL2Excess    = DVS.generate lenL2 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL2 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16+        rmL0Excess    = DVS.generate lenL0 (\i -> fromIntegral (allExcess1 (DVS.pageFill i pageSizeL0 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16+        rmL1Excess    = DVS.generate lenL1 (\i -> fromIntegral (allExcess1 (DVS.pageFill i pageSizeL1 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16+        rmL2Excess    = DVS.generate lenL2 (\i -> fromIntegral (allExcess1 (DVS.pageFill i pageSizeL2 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16         rmL0Min       = DVS.generate lenL0 (\i -> let MinExcess minE _ = allMinL0 DVS.! i in fromIntegral minE)         rmL1Min       = DVS.generate lenL1 (\i -> let MinExcess minE _ = allMinL1 DVS.! i in fromIntegral minE)         rmL2Min       = DVS.generate 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 = DVS.generate (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 #-}  data FindState = FindBP   | FindL0 | FindFromL0
src/HaskellWorks/Data/BalancedParens/RangeMin2.hs view
@@ -35,8 +35,9 @@ import HaskellWorks.Data.Vector.AsVector64 import Prelude                                         hiding (length) -import qualified Data.Vector          as DV-import qualified Data.Vector.Storable as DVS+import qualified Data.Vector                                               as DV+import qualified Data.Vector.Storable                                      as DVS+import qualified HaskellWorks.Data.BalancedParens.Internal.Vector.Storable as DVS  data RangeMin2 a = RangeMin2   { rangeMin2BP       :: !a@@ -95,8 +96,8 @@ mkRangeMin2 :: AsVector64 a => a -> RangeMin2 a mkRangeMin2 bp = RangeMin2   { rangeMin2BP       = bp-  , rangeMin2L0Min    = dvsReword rmL0Min-  , rangeMin2L0Excess = dvsReword rmL0Excess+  , rangeMin2L0Min    = DVS.reword rmL0Min+  , rangeMin2L0Excess = DVS.reword rmL0Excess   , rangeMin2L1Min    = rmL1Min   , rangeMin2L1Excess = rmL1Excess   , rangeMin2L2Min    = rmL2Min@@ -115,39 +116,21 @@         lenL4         = (DVS.length rmL0Min `div` pageSizeL4) + 1 :: Int         allMinL0      = DV.generate  lenL0 (\i -> if i == lenBP then MinExcess (-64) (-64) else minExcess1 (bpv !!! fromIntegral i))         -- Note: (0xffffffffffffffc0 :: Int64) = -64-        rmL0Excess    = DVS.generate lenL0 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL0 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16-        rmL1Excess    = DVS.generate lenL1 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL1 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16-        rmL2Excess    = DVS.generate lenL2 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL2 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16-        rmL3Excess    = DVS.generate lenL3 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL3 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16-        rmL4Excess    = DVS.generate lenL4 (\i -> fromIntegral (allExcess1 (pageFill i pageSizeL4 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16+        rmL0Excess    = DVS.generate lenL0 (\i -> fromIntegral (allExcess1 (DVS.pageFill i pageSizeL0 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16+        rmL1Excess    = DVS.generate lenL1 (\i -> fromIntegral (allExcess1 (DVS.pageFill i pageSizeL1 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16+        rmL2Excess    = DVS.generate lenL2 (\i -> fromIntegral (allExcess1 (DVS.pageFill i pageSizeL2 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16+        rmL3Excess    = DVS.generate lenL3 (\i -> fromIntegral (allExcess1 (DVS.pageFill i pageSizeL3 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16+        rmL4Excess    = DVS.generate lenL4 (\i -> fromIntegral (allExcess1 (DVS.pageFill i pageSizeL4 0xffffffffffffffc0 bpv))) :: DVS.Vector Int16         rmL0Min       = DVS.generate lenL0 (\i -> let MinExcess minE _ = allMinL0 DV.! i in fromIntegral minE) :: DVS.Vector Int16-        rmL1Min       = DVS.generate lenL1 (\i -> genMin 0 (pageFill i factorL1 0 rmL0Min) (pageFill i factorL1 0 rmL0Excess))-        rmL2Min       = DVS.generate lenL2 (\i -> genMin 0 (pageFill i factorL2 0 rmL1Min) (pageFill i factorL2 0 rmL1Excess))-        rmL3Min       = DVS.generate lenL3 (\i -> genMin 0 (pageFill i factorL3 0 rmL2Min) (pageFill i factorL3 0 rmL2Excess))-        rmL4Min       = DVS.generate lenL4 (\i -> genMin 0 (pageFill i factorL4 0 rmL3Min) (pageFill i factorL4 0 rmL3Excess))+        rmL1Min       = DVS.generate lenL1 (\i -> genMin 0 (DVS.pageFill i factorL1 0 rmL0Min) (DVS.pageFill i factorL1 0 rmL0Excess))+        rmL2Min       = DVS.generate lenL2 (\i -> genMin 0 (DVS.pageFill i factorL2 0 rmL1Min) (DVS.pageFill i factorL2 0 rmL1Excess))+        rmL3Min       = DVS.generate lenL3 (\i -> genMin 0 (DVS.pageFill i factorL3 0 rmL2Min) (DVS.pageFill i factorL3 0 rmL2Excess))+        rmL4Min       = DVS.generate lenL4 (\i -> genMin 0 (DVS.pageFill i factorL4 0 rmL3Min) (DVS.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)+  then genMin (DVS.lastOrZero mins `min` (mL + DVS.lastOrZero 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 #-}--dvsReword :: (DVS.Storable a, Integral a, DVS.Storable b, Num b) => DVS.Vector a -> DVS.Vector b-dvsReword v = DVS.generate (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
+ test/HaskellWorks/Data/BalancedParens/FindCloseNSpec.hs view
@@ -0,0 +1,23 @@+{-# LANGUAGE OverloadedStrings   #-}+{-# LANGUAGE ScopedTypeVariables #-}++module HaskellWorks.Data.BalancedParens.FindCloseNSpec where++import HaskellWorks.Data.BalancedParens+import HaskellWorks.Data.Bits.Broadword.Type+import HaskellWorks.Hspec.Hedgehog+import Hedgehog+import Test.Hspec++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) #-}++spec :: Spec+spec = describe "HaskellWorks.Data.BalancedParens.FindCloseNSpec" $ do+  it "returns same result as broadword" $ requireProperty $ do+    w <- forAll $ G.word64 R.constantBounded+    p <- forAll $ G.word64 (R.linear 1 64)+    findClose w p === findClose (Broadword w) p
test/HaskellWorks/Data/BalancedParens/Internal/BroadwordSpec.hs view
@@ -9,7 +9,7 @@ import GHC.Generics import HaskellWorks.Data.BalancedParens.FindClose import HaskellWorks.Data.Bits.BitShow-import HaskellWorks.Data.Bits.Broadword+import HaskellWorks.Data.Bits.Broadword.Type import HaskellWorks.Data.Bits.FromBitTextByteString import HaskellWorks.Hspec.Hedgehog import Hedgehog@@ -32,108 +32,66 @@ spec = describe "HaskellWorks.Data.BalancedParens.BroadwordSpec" $ do   describe "For (()(()())) 1101101000" $ do     let bs = Broadword (91 :: Word64)-    it "Test 1a" $ findClose bs  1 `shouldBe` Just 10-    it "Test 1b" $ findClose bs  2 `shouldBe` Just  3-    it "Test 1b" $ findClose bs  3 `shouldBe` Just  3-    it "Test 1b" $ findClose bs  4 `shouldBe` Just  9-    it "Test 1b" $ findClose bs  5 `shouldBe` Just  6-    it "Test 1b" $ findClose bs  6 `shouldBe` Just  6-    it "Test 1b" $ findClose bs  7 `shouldBe` Just  8-    it "Test 1b" $ findClose bs  8 `shouldBe` Just  8-    it "Test 1b" $ findClose bs  9 `shouldBe` Just  9-    it "Test 1b" $ findClose bs 10 `shouldBe` Just 10-    -- it "Test 2a" $ findOpen  bs 10 `shouldBe` Just  1-    -- it "Test 2b" $ findOpen  bs  3 `shouldBe` Just  2-    -- it "Test 3a" $ enclose   bs  2 `shouldBe` Just  1-    -- it "Test 3b" $ enclose   bs  7 `shouldBe` Just  4-  -- describe "For (()(()())) 1101101000" $ do-  --   let bs = Broadword (fromJust (bitRead "1101101000") :: [Bool])-  --   it "Test 1a" $ findClose bs  1 `shouldBe` Just 10-  --   it "Test 1b" $ findClose bs  2 `shouldBe` Just  3-  --   it "Test 1b" $ findClose bs  3 `shouldBe` Just  3-  --   it "Test 1b" $ findClose bs  4 `shouldBe` Just  9-  --   it "Test 1b" $ findClose bs  5 `shouldBe` Just  6-  --   it "Test 1b" $ findClose bs  6 `shouldBe` Just  6-  --   it "Test 1b" $ findClose bs  7 `shouldBe` Just  8-  --   it "Test 1b" $ findClose bs  8 `shouldBe` Just  8-  --   it "Test 1b" $ findClose bs  9 `shouldBe` Just  9-  --   it "Test 1b" $ findClose bs 10 `shouldBe` Just 10-    -- it "Test 2a" $ findOpen  bs 10 `shouldBe` Just  1-    -- it "Test 2b" $ findOpen  bs  3 `shouldBe` Just  2-    -- it "Test 3a" $ enclose   bs  2 `shouldBe` Just  1-    -- it "Test 3b" $ enclose   bs  7 `shouldBe` Just  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` Just 1-    -- it "depth  2" $ depth   bs  2 `shouldBe` Just 2-    -- it "depth  3" $ depth   bs  3 `shouldBe` Just 2-    -- it "depth  4" $ depth   bs  4 `shouldBe` Just 2-    -- it "depth  5" $ depth   bs  5 `shouldBe` Just 3-    -- it "depth  6" $ depth   bs  6 `shouldBe` Just 3-    -- it "depth  7" $ depth   bs  7 `shouldBe` Just 3-    -- it "depth  8" $ depth   bs  8 `shouldBe` Just 3-    -- it "depth  9" $ depth   bs  9 `shouldBe` Just 2-    -- it "depth 10" $ depth   bs 10 `shouldBe` Just 1-    -- it "subtreeSize  1" $ subtreeSize bs  1 `shouldBe` Just 5-    -- it "subtreeSize  2" $ subtreeSize bs  2 `shouldBe` Just 1-    -- it "subtreeSize  3" $ subtreeSize bs  3 `shouldBe` Just 0-    -- it "subtreeSize  4" $ subtreeSize bs  4 `shouldBe` Just 3-    -- it "subtreeSize  5" $ subtreeSize bs  5 `shouldBe` Just 1-    -- it "subtreeSize  6" $ subtreeSize bs  6 `shouldBe` Just 0-    -- it "subtreeSize  7" $ subtreeSize bs  7 `shouldBe` Just 1-    -- it "subtreeSize  8" $ subtreeSize bs  8 `shouldBe` Just 0-    -- it "subtreeSize  9" $ subtreeSize bs  9 `shouldBe` Just 0-    -- it "subtreeSize 10" $ subtreeSize bs 10 `shouldBe` Just 0+    it "Test 1a" $ requireTest $ findClose bs  1 === Just 10+    it "Test 1b" $ requireTest $ findClose bs  2 === Just  3+    it "Test 1b" $ requireTest $ findClose bs  3 === Just  3+    it "Test 1b" $ requireTest $ findClose bs  4 === Just  9+    it "Test 1b" $ requireTest $ findClose bs  5 === Just  6+    it "Test 1b" $ requireTest $ findClose bs  6 === Just  6+    it "Test 1b" $ requireTest $ findClose bs  7 === Just  8+    it "Test 1b" $ requireTest $ findClose bs  8 === Just  8+    it "Test 1b" $ requireTest $ findClose bs  9 === Just  9+    it "Test 1b" $ requireTest $ findClose bs 10 === Just 10+    -- it "Test 2a" $ requireTest $ findOpen  bs 10 === Just  1+    -- it "Test 2b" $ requireTest $ findOpen  bs  3 === Just  2+    -- it "Test 3a" $ requireTest $ enclose   bs  2 === Just  1+    -- it "Test 3b" $ requireTest $ enclose   bs  7 === Just  4   describe "For (()(()())) 11011010 00000000 :: DVS.Vector Word8" $ do     let bs = Broadword (DVS.head (fromBitTextByteString "11011010 00000000") :: Word64)-    it "Test 1a" $ findClose bs  1 `shouldBe` Just 10-    it "Test 1b" $ findClose bs  2 `shouldBe` Just  3-    it "Test 1b" $ findClose bs  3 `shouldBe` Just  3-    it "Test 1b" $ findClose bs  4 `shouldBe` Just  9-    it "Test 1b" $ findClose bs  5 `shouldBe` Just  6-    it "Test 1b" $ findClose bs  6 `shouldBe` Just  6-    it "Test 1b" $ findClose bs  7 `shouldBe` Just  8-    it "Test 1b" $ findClose bs  8 `shouldBe` Just  8-    it "Test 1b" $ findClose bs  9 `shouldBe` Just  9-    it "Test 1b" $ findClose bs 10 `shouldBe` Just 10-    -- it "Test 2a" $ findOpen  bs 10 `shouldBe` Just  1-    -- it "Test 2b" $ findOpen  bs  3 `shouldBe` Just  2-    -- it "Test 3a" $ enclose   bs  2 `shouldBe` Just  1-    -- it "Test 3b" $ enclose   bs  7 `shouldBe` Just  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` Just 1-    -- it "depth  2" $ depth bs  2 `shouldBe` Just 2-    -- it "depth  3" $ depth bs  3 `shouldBe` Just 2-    -- it "depth  4" $ depth bs  4 `shouldBe` Just 2-    -- it "depth  5" $ depth bs  5 `shouldBe` Just 3-    -- it "depth  6" $ depth bs  6 `shouldBe` Just 3-    -- it "depth  7" $ depth bs  7 `shouldBe` Just 3-    -- it "depth  8" $ depth bs  8 `shouldBe` Just 3-    -- it "depth  9" $ depth bs  9 `shouldBe` Just 2-    -- it "depth 10" $ depth bs 10 `shouldBe` Just 1-    -- it "subtreeSize  1" $ subtreeSize bs  1 `shouldBe` Just 5-    -- it "subtreeSize  2" $ subtreeSize bs  2 `shouldBe` Just 1-    -- it "subtreeSize  3" $ subtreeSize bs  3 `shouldBe` Just 0-    -- it "subtreeSize  4" $ subtreeSize bs  4 `shouldBe` Just 3-    -- it "subtreeSize  5" $ subtreeSize bs  5 `shouldBe` Just 1-    -- it "subtreeSize  6" $ subtreeSize bs  6 `shouldBe` Just 0-    -- it "subtreeSize  7" $ subtreeSize bs  7 `shouldBe` Just 1-    -- it "subtreeSize  8" $ subtreeSize bs  8 `shouldBe` Just 0-    -- it "subtreeSize  9" $ subtreeSize bs  9 `shouldBe` Just 0-    -- it "subtreeSize 10" $ subtreeSize bs 10 `shouldBe` Just 0+    it "Test 1a" $ requireTest $ findClose bs  1 === Just 10+    it "Test 1b" $ requireTest $ findClose bs  2 === Just  3+    it "Test 1b" $ requireTest $ findClose bs  3 === Just  3+    it "Test 1b" $ requireTest $ findClose bs  4 === Just  9+    it "Test 1b" $ requireTest $ findClose bs  5 === Just  6+    it "Test 1b" $ requireTest $ findClose bs  6 === Just  6+    it "Test 1b" $ requireTest $ findClose bs  7 === Just  8+    it "Test 1b" $ requireTest $ findClose bs  8 === Just  8+    it "Test 1b" $ requireTest $ findClose bs  9 === Just  9+    it "Test 1b" $ requireTest $ findClose bs 10 === Just 10+    -- it "Test 2a" $ requireTest $ findOpen  bs 10 === Just  1+    -- it "Test 2b" $ requireTest $ findOpen  bs  3 === Just  2+    -- it "Test 3a" $ requireTest $ enclose   bs  2 === Just  1+    -- it "Test 3b" $ requireTest $ enclose   bs  7 === Just  4+    -- it "firstChild 1"  $ requireTest $ firstChild  bs 1 === Just 2+    -- it "firstChild 4"  $ requireTest $ firstChild  bs 4 === Just 5+    -- it "nextSibling 2" $ requireTest $ nextSibling bs 2 === Just 4+    -- it "nextSibling 5" $ requireTest $ nextSibling bs 5 === Just 7+    -- it "parent 2" $ requireTest $ parent bs 2 === Just 1+    -- it "parent 5" $ requireTest $ parent bs 5 === Just 4+    -- it "depth  1" $ requireTest $ depth bs  1 === Just 1+    -- it "depth  2" $ requireTest $ depth bs  2 === Just 2+    -- it "depth  3" $ requireTest $ depth bs  3 === Just 2+    -- it "depth  4" $ requireTest $ depth bs  4 === Just 2+    -- it "depth  5" $ requireTest $ depth bs  5 === Just 3+    -- it "depth  6" $ requireTest $ depth bs  6 === Just 3+    -- it "depth  7" $ requireTest $ depth bs  7 === Just 3+    -- it "depth  8" $ requireTest $ depth bs  8 === Just 3+    -- it "depth  9" $ requireTest $ depth bs  9 === Just 2+    -- it "depth 10" $ requireTest $ depth bs 10 === Just 1+    -- it "subtreeSize  1" $ requireTest $ subtreeSize bs  1 === Just 5+    -- it "subtreeSize  2" $ requireTest $ subtreeSize bs  2 === Just 1+    -- it "subtreeSize  3" $ requireTest $ subtreeSize bs  3 === Just 0+    -- it "subtreeSize  4" $ requireTest $ subtreeSize bs  4 === Just 3+    -- it "subtreeSize  5" $ requireTest $ subtreeSize bs  5 === Just 1+    -- it "subtreeSize  6" $ requireTest $ subtreeSize bs  6 === Just 0+    -- it "subtreeSize  7" $ requireTest $ subtreeSize bs  7 === Just 1+    -- it "subtreeSize  8" $ requireTest $ subtreeSize bs  8 === Just 0+    -- it "subtreeSize  9" $ requireTest $ subtreeSize bs  9 === Just 0+    -- it "subtreeSize 10" $ requireTest $ subtreeSize bs 10 === Just 0   -- describe "Does not suffer exceptions" $ do   --   it "when calling nextSibling from valid locations" $ do   --     forAll (vectorSizedBetween 1 64) $ \(ShowVector v) -> do-  --       [nextSibling v p | p <- [1..bitLength v]] `shouldBe` [nextSibling v p | p <- [1..bitLength v]]+  --       [nextSibling v p | p <- [1..bitLength v]] === [nextSibling v p | p <- [1..bitLength v]]   it "Broadword findClose should behave the same as Naive findClose" $ requireProperty $ do     w <- forAll $ G.word64 R.constantBounded     p <- forAll $ G.count (R.linear 1 64)
test/HaskellWorks/Data/BalancedParens/RangeMin2Spec.hs view
@@ -1,137 +1,52 @@-{-# LANGUAGE BangPatterns               #-}-{-# LANGUAGE DeriveGeneric              #-}-{-# LANGUAGE GeneralizedNewtypeDeriving #-}-{-# LANGUAGE OverloadedStrings          #-}-{-# LANGUAGE ScopedTypeVariables        #-}+{-# LANGUAGE BangPatterns        #-}+{-# LANGUAGE OverloadedStrings   #-}+{-# LANGUAGE ScopedTypeVariables #-}  module HaskellWorks.Data.BalancedParens.RangeMin2Spec where  import Data.Word-import GHC.Generics import HaskellWorks.Data.BalancedParens-import HaskellWorks.Data.BalancedParens.RangeMin-import HaskellWorks.Data.Bits.BitShow+import HaskellWorks.Data.BalancedParens.RangeMin2+import HaskellWorks.Data.Bits.BitLength import HaskellWorks.Data.Bits.FromBitTextByteString+import HaskellWorks.Hspec.Hedgehog+import Hedgehog import Test.Hspec -import qualified Data.Vector.Storable as DVS+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, Generic)--instance BitShow a => Show (ShowVector a) where-  show = bitShow--maxVectorSize :: Int-maxVectorSize = 16384-{-# INLINE maxVectorSize #-}+factor :: Int+factor = 16384+{-# INLINE factor #-}  spec :: Spec spec = describe "HaskellWorks.Data.BalancedParens.RangeMinSpec2" $ do-  -- let maxSuccessDefault = 5-  it "For a simple bit string can find close" $ 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 `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+    let !rm = mkRangeMin2 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 = mkRangeMin2 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 = mkRangeMin2 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 = mkRangeMin2 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 = mkRangeMin2 v+    nextSibling rm p === nextSibling v p