hw-rankselect 0.1.0.1 → 0.2.0.0
raw patch · 15 files changed
+970/−278 lines, 15 files
Files
- hw-rankselect.cabal +11/−2
- src/HaskellWorks/Data/Succinct/BalancedParens/Internal.hs +133/−142
- src/HaskellWorks/Data/Succinct/BalancedParens/RangeMinMax.hs +93/−0
- src/HaskellWorks/Data/Succinct/Excess.hs +6/−0
- src/HaskellWorks/Data/Succinct/Excess/Excess0.hs +46/−0
- src/HaskellWorks/Data/Succinct/Excess/Excess1.hs +46/−0
- src/HaskellWorks/Data/Succinct/Excess/MinMaxExcess0.hs +73/−0
- src/HaskellWorks/Data/Succinct/Excess/MinMaxExcess1.hs +73/−0
- src/HaskellWorks/Data/Succinct/RankSelect/Binary/Poppy512.hs +10/−6
- src/HaskellWorks/Data/Succinct/RankSelect/Binary/Poppy512S.hs +8/−12
- test/HaskellWorks/Data/Succinct/BalancedParens/RangeMinMaxSpec.hs +57/−0
- test/HaskellWorks/Data/Succinct/BalancedParens/SimpleSpec.hs +116/−0
- test/HaskellWorks/Data/Succinct/BalancedParensSpec.hs +0/−116
- test/HaskellWorks/Data/Succinct/Excess/MinMaxExcess0Spec.hs +149/−0
- test/HaskellWorks/Data/Succinct/Excess/MinMaxExcess1Spec.hs +149/−0
hw-rankselect.cabal view
@@ -1,5 +1,5 @@ name: hw-rankselect-version: 0.1.0.1+version: 0.2.0.0 synopsis: Conduits for tokenizing streams. description: Please see README.md homepage: http://github.com/haskell-works/hw-rankselect#readme@@ -25,7 +25,13 @@ hs-source-dirs: src exposed-modules: HaskellWorks.Data.Succinct.BalancedParens , HaskellWorks.Data.Succinct.BalancedParens.Internal+ , HaskellWorks.Data.Succinct.BalancedParens.RangeMinMax , HaskellWorks.Data.Succinct.BalancedParens.Simple+ , HaskellWorks.Data.Succinct.Excess+ , HaskellWorks.Data.Succinct.Excess.Excess0+ , HaskellWorks.Data.Succinct.Excess.Excess1+ , HaskellWorks.Data.Succinct.Excess.MinMaxExcess0+ , HaskellWorks.Data.Succinct.Excess.MinMaxExcess1 , HaskellWorks.Data.Succinct.NearestNeighbour , HaskellWorks.Data.Succinct.RankSelect , HaskellWorks.Data.Succinct.RankSelect.Binary@@ -51,7 +57,10 @@ type: exitcode-stdio-1.0 hs-source-dirs: test main-is: Spec.hs- other-modules: HaskellWorks.Data.Succinct.BalancedParensSpec+ other-modules: HaskellWorks.Data.Succinct.BalancedParens.RangeMinMaxSpec+ , HaskellWorks.Data.Succinct.BalancedParens.SimpleSpec+ , HaskellWorks.Data.Succinct.Excess.MinMaxExcess0Spec+ , HaskellWorks.Data.Succinct.Excess.MinMaxExcess1Spec , HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank0Spec , HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1Spec , HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Select0Spec
src/HaskellWorks/Data/Succinct/BalancedParens/Internal.hs view
@@ -2,9 +2,7 @@ module HaskellWorks.Data.Succinct.BalancedParens.Internal ( BalancedParens(..)- , closeAt- , depth- , openAt+ -- , depth , subtreeSize ) where @@ -12,177 +10,170 @@ import qualified 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.Positioning-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank0-import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1+-- import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank0+-- import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1 class BalancedParens v where- findOpen :: v -> Count -> Maybe Count- findClose :: v -> Count -> Maybe Count- enclose :: v -> Count -> Maybe Count- firstChild :: v -> Count -> Maybe Count+ openAt :: v -> Count -> Bool+ closeAt :: v -> Count -> Bool+ -- TODO Second argument should be Int+ -- findOpenN :: v -> Count -> Count -> Maybe Count+ findCloseN :: v -> Count -> Count -> Maybe Count++ -- enclose :: v -> Count -> Maybe Count+ firstChild :: v -> Count -> Maybe Count nextSibling :: v -> Count -> Maybe Count- parent :: v -> Count -> Maybe Count+ -- parent :: v -> Count -> Maybe Count+ -- findOpen :: v -> Count -> Maybe Count+ findClose :: v -> Count -> Maybe Count+ -- findOpen v p = if v `openAt` p then Just p else findOpenN v (Count 1) (p - 1)+ findClose v p = if v `closeAt` p then Just p else findCloseN v (Count 1) (p + 1)+ firstChild v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing+ nextSibling v p = if closeAt v p then Nothing else openAt v `mfilter` (findClose v p >>= (\q -> if p /= q then return (q + 1) else Nothing))+ -- parent v p = enclose v p >>= (\r -> if r >= 1 then return r else Nothing)+ -- enclose v = findOpenN v (Count 1)+ -- {-# INLINE findOpen #-}+ {-# INLINE findClose #-}+ {-# INLINE firstChild #-}+ {-# INLINE nextSibling #-}+ -- {-# INLINE parent #-}+ -- {-# INLINE enclose #-} -depth :: (BalancedParens v, Rank0 v, Rank1 v) => v -> Count -> Maybe Count-depth v p = (\q -> rank1 v q - rank0 v q) <$> findOpen v p+-- depth :: (BalancedParens v, Rank0 v, Rank1 v) => v -> Count -> Maybe Count+-- depth v p = (\q -> rank1 v q - rank0 v q) <$> findOpen v p subtreeSize :: BalancedParens v => v -> Count -> Maybe Count subtreeSize v p = (\q -> (q - p + 1) `quot` 2) <$> findClose v p -closeAt :: TestBit a => a -> Count -> Bool-closeAt v c = not (v .?. toPosition (c - 1))-{-# INLINABLE closeAt #-}+closeAt' :: TestBit a => a -> Count -> Bool+closeAt' v c = not (v .?. toPosition (c - 1))+{-# INLINE closeAt' #-} -openAt :: TestBit a => a -> Count -> Bool-openAt v c = v .?. toPosition (c - 1)-{-# INLINABLE openAt #-}+openAt' :: TestBit a => a -> Count -> Bool+openAt' v c = v .?. toPosition (c - 1)+{-# INLINE openAt' #-} ----- -findOpen' :: (BitLength a, TestBit a) => Count -> a -> Count -> Maybe Count-findOpen' c v p = if 0 < p && p <= bitLength v- then if v `openAt` p- then if c == 0- then Just p- else findOpen' (c - 1) v (p - 1)- else findOpen' (c + 1) v (p - 1)- else Nothing-{-# INLINABLE findOpen' #-}+-- findOpen' :: (BitLength a, TestBit a) => a -> Count -> Count -> Maybe Count+-- findOpen' v c p = if 0 < p && p <= bitLength v+-- then if v `openAt'` p+-- then if c == 0+-- then Just p+-- else findOpen' v (c - 1) (p - 1)+-- else findOpen' v (c + 1) (p - 1)+-- else Nothing+-- {-# INLINE findOpen' #-} -findClose' :: (BitLength a, TestBit a) => Count -> a -> Count -> Maybe Count-findClose' c v p = if 1 < p && p <= bitLength v- then if v `closeAt` p- then if c == 0+findClose' :: (BitLength a, TestBit a) => a -> Count -> Count -> Maybe Count+findClose' v c p = if 0 < p && p <= bitLength v+ then if v `closeAt'` p+ then if c <= 1 then Just p- else findClose' (c + 1) v (p + 1)- else findClose' (c - 1) v (p + 1)+ else findClose' v (c - 1) (p + 1)+ else findClose' v (c + 1) (p + 1) else Nothing-{-# INLINABLE findClose' #-}+{-# INLINE findClose' #-} +instance (BalancedParens a, TestBit a, BitLength a) => BalancedParens (BitShown a) where+ openAt = openAt' . bitShown+ closeAt = closeAt' . bitShown+ -- findOpenN = findOpen' . bitShown+ findCloseN = findClose' . bitShown+ {-# INLINE openAt #-}+ {-# INLINE closeAt #-}+ -- {-# INLINE findOpenN #-}+ {-# INLINE findCloseN #-}+ instance BalancedParens [Bool] where- findOpen v p = if v `openAt` p then Just p else findOpen' (Count 0) v (p - 1)- findClose v p = if v `closeAt` p then Just p else findClose' (Count 0) v (p + 1)- enclose = findOpen' (Count 1)- firstChild v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing- nextSibling v p = if closeAt v p then Nothing else openAt v `mfilter` (findClose v p >>= (\q -> if p /= q then return (q + 1) else Nothing))- parent v p = enclose v p >>= (\r -> if r >= 1 then return r else Nothing)- {-# INLINABLE findOpen #-}- {-# INLINABLE findClose #-}- {-# INLINABLE enclose #-}- {-# INLINABLE firstChild #-}- {-# INLINABLE nextSibling #-}- {-# INLINABLE parent #-}+ openAt = openAt'+ closeAt = closeAt'+ -- findOpenN = findOpen'+ findCloseN = findClose'+ {-# INLINE openAt #-}+ {-# INLINE closeAt #-}+ -- {-# INLINE findOpenN #-}+ {-# INLINE findCloseN #-} instance BalancedParens (DVS.Vector Word8) where- findOpen v p = if v `openAt` p then Just p else findOpen' (Count 0) v (p - 1)- findClose v p = if v `closeAt` p then Just p else findClose' (Count 0) v (p + 1)- enclose = findOpen' (Count 1)- firstChild v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing- nextSibling v p = if closeAt v p then Nothing else openAt v `mfilter` (findClose v p >>= (\q -> if p /= q then return (q + 1) else Nothing))- parent v p = enclose v p >>= (\r -> if r >= 1 then return r else Nothing)- {-# INLINABLE findOpen #-}- {-# INLINABLE findClose #-}- {-# INLINABLE enclose #-}- {-# INLINABLE firstChild #-}- {-# INLINABLE nextSibling #-}- {-# INLINABLE parent #-}+ openAt = openAt'+ closeAt = closeAt'+ -- findOpenN = findOpen'+ findCloseN = findClose'+ {-# INLINE openAt #-}+ {-# INLINE closeAt #-}+ -- {-# INLINE findOpenN #-}+ {-# INLINE findCloseN #-} instance BalancedParens (DVS.Vector Word16) where- findOpen v p = if v `openAt` p then Just p else findOpen' (Count 0) v (p - 1)- findClose v p = if v `closeAt` p then Just p else findClose' (Count 0) v (p + 1)- enclose = findOpen' (Count 1)- firstChild v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing- nextSibling v p = if closeAt v p then Nothing else openAt v `mfilter` (findClose v p >>= (\q -> if p /= q then return (q + 1) else Nothing))- parent v p = enclose v p >>= (\r -> if r >= 1 then return r else Nothing)- {-# INLINABLE findOpen #-}- {-# INLINABLE findClose #-}- {-# INLINABLE enclose #-}- {-# INLINABLE firstChild #-}- {-# INLINABLE nextSibling #-}- {-# INLINABLE parent #-}+ openAt = openAt'+ closeAt = closeAt'+ -- findOpenN = findOpen'+ findCloseN = findClose'+ {-# INLINE openAt #-}+ {-# INLINE closeAt #-}+ -- {-# INLINE findOpenN #-}+ {-# INLINE findCloseN #-} instance BalancedParens (DVS.Vector Word32) where- findOpen v p = if v `openAt` p then Just p else findOpen' (Count 0) v (p - 1)- findClose v p = if v `closeAt` p then Just p else findClose' (Count 0) v (p + 1)- enclose = findOpen' (Count 1)- firstChild v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing- nextSibling v p = if closeAt v p then Nothing else openAt v `mfilter` (findClose v p >>= (\q -> if p /= q then return (q + 1) else Nothing))- parent v p = enclose v p >>= (\r -> if r >= 1 then return r else Nothing)- {-# INLINABLE findOpen #-}- {-# INLINABLE findClose #-}- {-# INLINABLE enclose #-}- {-# INLINABLE firstChild #-}- {-# INLINABLE nextSibling #-}- {-# INLINABLE parent #-}+ openAt = openAt'+ closeAt = closeAt'+ -- findOpenN = findOpen'+ findCloseN = findClose'+ {-# INLINE openAt #-}+ {-# INLINE closeAt #-}+ -- {-# INLINE findOpenN #-}+ {-# INLINE findCloseN #-} instance BalancedParens (DVS.Vector Word64) where- findOpen v p = if v `openAt` p then Just p else findOpen' (Count 0) v (p - 1)- findClose v p = if v `closeAt` p then Just p else findClose' (Count 0) v (p + 1)- enclose = findOpen' (Count 1)- firstChild v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing- nextSibling v p = if closeAt v p then Nothing else openAt v `mfilter` (findClose v p >>= (\q -> if p /= q then return (q + 1) else Nothing))- parent v p = enclose v p >>= (\r -> if r >= 1 then return r else Nothing)- {-# INLINABLE findOpen #-}- {-# INLINABLE findClose #-}- {-# INLINABLE enclose #-}- {-# INLINABLE firstChild #-}- {-# INLINABLE nextSibling #-}- {-# INLINABLE parent #-}+ openAt = openAt'+ closeAt = closeAt'+ -- findOpenN = findOpen'+ findCloseN = findClose'+ {-# INLINE openAt #-}+ {-# INLINE closeAt #-}+ -- {-# INLINE findOpenN #-}+ {-# INLINE findCloseN #-} instance BalancedParens Word8 where- findOpen v p = if v `openAt` p then Just p else findOpen' (Count 0) v (p - 1)- findClose v p = if v `closeAt` p then Just p else findClose' (Count 0) v (p + 1)- enclose = findOpen' (Count 1)- firstChild v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing- nextSibling v p = if closeAt v p then Nothing else openAt v `mfilter` (findClose v p >>= (\q -> if p /= q then return (q + 1) else Nothing))- parent v p = enclose v p >>= (\r -> if r >= 1 then return r else Nothing)- {-# INLINABLE findOpen #-}- {-# INLINABLE findClose #-}- {-# INLINABLE enclose #-}- {-# INLINABLE firstChild #-}- {-# INLINABLE nextSibling #-}- {-# INLINABLE parent #-}+ openAt = openAt'+ closeAt = closeAt'+ -- findOpenN = findOpen'+ findCloseN = findClose'+ {-# INLINE openAt #-}+ {-# INLINE closeAt #-}+ -- {-# INLINE findOpenN #-}+ {-# INLINE findCloseN #-} instance BalancedParens Word16 where- findOpen v p = if v `openAt` p then Just p else findOpen' (Count 0) v (p - 1)- findClose v p = if v `closeAt` p then Just p else findClose' (Count 0) v (p + 1)- enclose = findOpen' (Count 1)- firstChild v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing- nextSibling v p = if closeAt v p then Nothing else openAt v `mfilter` (findClose v p >>= (\q -> if p /= q then return (q + 1) else Nothing))- parent v p = enclose v p >>= (\r -> if r >= 1 then return r else Nothing)- {-# INLINABLE findOpen #-}- {-# INLINABLE findClose #-}- {-# INLINABLE enclose #-}- {-# INLINABLE firstChild #-}- {-# INLINABLE nextSibling #-}- {-# INLINABLE parent #-}+ openAt = openAt'+ closeAt = closeAt'+ -- findOpenN = findOpen'+ findCloseN = findClose'+ {-# INLINE openAt #-}+ {-# INLINE closeAt #-}+ -- {-# INLINE findOpenN #-}+ {-# INLINE findCloseN #-} instance BalancedParens Word32 where- findOpen v p = if v `openAt` p then Just p else findOpen' (Count 0) v (p - 1)- findClose v p = if v `closeAt` p then Just p else findClose' (Count 0) v (p + 1)- enclose = findOpen' (Count 1)- firstChild v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing- nextSibling v p = if closeAt v p then Nothing else openAt v `mfilter` (findClose v p >>= (\q -> if p /= q then return (q + 1) else Nothing))- parent v p = enclose v p >>= (\r -> if r >= 1 then return r else Nothing)- {-# INLINABLE findOpen #-}- {-# INLINABLE findClose #-}- {-# INLINABLE enclose #-}- {-# INLINABLE firstChild #-}- {-# INLINABLE nextSibling #-}- {-# INLINABLE parent #-}+ openAt = openAt'+ closeAt = closeAt'+ -- findOpenN = findOpen'+ findCloseN = findClose'+ {-# INLINE openAt #-}+ {-# INLINE closeAt #-}+ -- {-# INLINE findOpenN #-}+ {-# INLINE findCloseN #-} instance BalancedParens Word64 where- findOpen v p = if v `openAt` p then Just p else findOpen' (Count 0) v (p - 1)- findClose v p = if v `closeAt` p then Just p else findClose' (Count 0) v (p + 1)- enclose = findOpen' (Count 1)- firstChild v p = if openAt v p && openAt v (p + 1) then Just (p + 1) else Nothing- nextSibling v p = if closeAt v p then Nothing else openAt v `mfilter` (findClose v p >>= (\q -> if p /= q then return (q + 1) else Nothing))- parent v p = enclose v p >>= (\r -> if r >= 1 then return r else Nothing)- {-# INLINABLE findOpen #-}- {-# INLINABLE findClose #-}- {-# INLINABLE enclose #-}- {-# INLINABLE firstChild #-}- {-# INLINABLE nextSibling #-}- {-# INLINABLE parent #-}+ openAt = openAt'+ closeAt = closeAt'+ -- findOpenN = findOpen'+ findCloseN = findClose'+ {-# INLINE openAt #-}+ {-# INLINE closeAt #-}+ -- {-# INLINE findOpenN #-}+ {-# INLINE findCloseN #-}
+ src/HaskellWorks/Data/Succinct/BalancedParens/RangeMinMax.hs view
@@ -0,0 +1,93 @@+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE InstanceSigs #-}++module HaskellWorks.Data.Succinct.BalancedParens.RangeMinMax+ ( RangeMinMaxL0(..)+ , mkRangeMinMaxL0+ ) where++import Data.Int+import qualified Data.Vector as DV+import qualified Data.Vector.Storable as DVS+import Data.Word+import HaskellWorks.Data.Bits.BitLength+import HaskellWorks.Data.Bits.BitWise+import HaskellWorks.Data.Positioning+import HaskellWorks.Data.Succinct.BalancedParens.Internal+import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank0+import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1+import HaskellWorks.Data.Succinct.Excess.MinMaxExcess1+import HaskellWorks.Data.Vector.VectorLike++data RangeMinMaxL0 v = RangeMinMaxL0+ { rangeMinMaxBP :: v+ , rangeMinMaxL0Min :: DVS.Vector Int8+ , rangeMinMaxL0Max :: DVS.Vector Int8+ , rangeMinMaxL0Excess :: DVS.Vector Int8+ }++mkRangeMinMaxL0 :: (VectorLike v, MinMaxExcess1 (Elem v)) => v -> RangeMinMaxL0 v+mkRangeMinMaxL0 bp = RangeMinMaxL0+ { rangeMinMaxBP = bp+ , rangeMinMaxL0Min = DVS.constructN (len0 + 1) (\v -> let (minE, _, _) = allMinMax DV.! DVS.length v in fromIntegral minE)+ , rangeMinMaxL0Max = DVS.constructN (len0 + 1) (\v -> let (_, _, maxE) = allMinMax DV.! DVS.length v in fromIntegral maxE)+ , rangeMinMaxL0Excess = DVS.constructN (len0 + 1) (\v -> let (_, e, _) = allMinMax DV.! DVS.length v in fromIntegral e)+ }+ where len0 = fromIntegral (vLength bp) :: Int+ allMinMax = DV.constructN (len0 + 1) genMinMax+ genMinMax v = let len = DV.length v in+ if len == len0+ then (0, 0, 0)+ else minMaxExcess1 (bp !!! fromIntegral len)++instance TestBit (RangeMinMaxL0 (DVS.Vector Word64)) where+ (.?.) = (.?.) . rangeMinMaxBP+ {-# INLINE (.?.) #-}++instance Rank1 (RangeMinMaxL0 (DVS.Vector Word64)) where+ rank1 = rank1 . rangeMinMaxBP+ {-# INLINE rank1 #-}++instance Rank0 (RangeMinMaxL0 (DVS.Vector Word64)) where+ rank0 = rank0 . rangeMinMaxBP+ {-# INLINE rank0 #-}++instance BitLength (RangeMinMaxL0 (DVS.Vector Word64)) where+ bitLength = bitLength . rangeMinMaxBP+ {-# INLINE bitLength #-}++rangeMinMaxFindCloseN :: RangeMinMaxL0 (DVS.Vector Word64) -> Int -> Count -> Maybe Count+rangeMinMaxFindCloseN v s p = result+ where bp = rangeMinMaxBP v+ mins = rangeMinMaxL0Min v+ excesses = rangeMinMaxL0Excess v+ findCloseN' = if v `closeAt` p+ then if s <= 1+ then Just p+ else rangeMinMaxFindCloseN v (s - 1) (p + 1)+ else rangeMinMaxFindCloseN v (s + 1) (p + 1)+ result = if 0 < p && p <= bitLength v+ then if (p - 1) `mod` elemBitLength bp == 0+ then let i = (p - 1) `div` elemBitLength bp in+ let minE = fromIntegral (mins !!! fromIntegral i) :: Int in+ if fromIntegral s + minE <= 0+ then findCloseN'+ else if v `closeAt` p && s <= 1+ then Just p+ else let excess = fromIntegral (excesses !!! fromIntegral i) :: Int in+ rangeMinMaxFindCloseN v (fromIntegral (excess + fromIntegral s)) (p + 64)+ else findCloseN'+ else Nothing+{-# INLINE rangeMinMaxFindCloseN #-}++instance BalancedParens (RangeMinMaxL0 (DVS.Vector Word64)) where+ openAt = openAt . rangeMinMaxBP+ closeAt = closeAt . rangeMinMaxBP+ -- findOpenN = findOpenN . rangeMinMaxBP+ findCloseN v s = rangeMinMaxFindCloseN v (fromIntegral s)++ {-# INLINE openAt #-}+ {-# INLINE closeAt #-}+ -- {-# INLINE findOpenN #-}+ {-# INLINE findCloseN #-}
+ src/HaskellWorks/Data/Succinct/Excess.hs view
@@ -0,0 +1,6 @@+module HaskellWorks.Data.Succinct.Excess+ ( module X+ ) where++import HaskellWorks.Data.Succinct.Excess.Excess0 as X+import HaskellWorks.Data.Succinct.Excess.Excess1 as X
+ src/HaskellWorks/Data/Succinct/Excess/Excess0.hs view
@@ -0,0 +1,46 @@+{-# LANGUAGE FlexibleInstances #-}++module HaskellWorks.Data.Succinct.Excess.Excess0+ ( Excess0(..)+ ) where++import Data.Word+import qualified Data.Vector.Storable as DVS+import HaskellWorks.Data.Positioning+import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank0+import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1++class Excess0 v where+ excess0 :: v -> Count -> Int++instance Excess0 Word8 where+ excess0 v c = fromIntegral (rank0 v c) - fromIntegral (rank1 v c)+ {-# INLINE excess0 #-}++instance Excess0 Word16 where+ excess0 v c = fromIntegral (rank0 v c) - fromIntegral (rank1 v c)+ {-# INLINE excess0 #-}++instance Excess0 Word32 where+ excess0 v c = fromIntegral (rank0 v c) - fromIntegral (rank1 v c)+ {-# INLINE excess0 #-}++instance Excess0 Word64 where+ excess0 v c = fromIntegral (rank0 v c) - fromIntegral (rank1 v c)+ {-# INLINE excess0 #-}++instance Excess0 (DVS.Vector Word8) where+ excess0 v c = fromIntegral (rank0 v c) - fromIntegral (rank1 v c)+ {-# INLINE excess0 #-}++instance Excess0 (DVS.Vector Word16) where+ excess0 v c = fromIntegral (rank0 v c) - fromIntegral (rank1 v c)+ {-# INLINE excess0 #-}++instance Excess0 (DVS.Vector Word32) where+ excess0 v c = fromIntegral (rank0 v c) - fromIntegral (rank1 v c)+ {-# INLINE excess0 #-}++instance Excess0 (DVS.Vector Word64) where+ excess0 v c = fromIntegral (rank0 v c) - fromIntegral (rank1 v c)+ {-# INLINE excess0 #-}
+ src/HaskellWorks/Data/Succinct/Excess/Excess1.hs view
@@ -0,0 +1,46 @@+{-# LANGUAGE FlexibleInstances #-}++module HaskellWorks.Data.Succinct.Excess.Excess1+ ( Excess1(..)+ ) where++import Data.Word+import qualified Data.Vector.Storable as DVS+import HaskellWorks.Data.Positioning+import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank0+import HaskellWorks.Data.Succinct.RankSelect.Binary.Basic.Rank1++class Excess1 v where+ excess1 :: v -> Count -> Int++instance Excess1 Word8 where+ excess1 v c = fromIntegral (rank1 v c) - fromIntegral (rank0 v c)+ {-# INLINE excess1 #-}++instance Excess1 Word16 where+ excess1 v c = fromIntegral (rank1 v c) - fromIntegral (rank0 v c)+ {-# INLINE excess1 #-}++instance Excess1 Word32 where+ excess1 v c = fromIntegral (rank1 v c) - fromIntegral (rank0 v c)+ {-# INLINE excess1 #-}++instance Excess1 Word64 where+ excess1 v c = fromIntegral (rank1 v c) - fromIntegral (rank0 v c)+ {-# INLINE excess1 #-}++instance Excess1 (DVS.Vector Word8) where+ excess1 v c = fromIntegral (rank1 v c) - fromIntegral (rank0 v c)+ {-# INLINE excess1 #-}++instance Excess1 (DVS.Vector Word16) where+ excess1 v c = fromIntegral (rank1 v c) - fromIntegral (rank0 v c)+ {-# INLINE excess1 #-}++instance Excess1 (DVS.Vector Word32) where+ excess1 v c = fromIntegral (rank1 v c) - fromIntegral (rank0 v c)+ {-# INLINE excess1 #-}++instance Excess1 (DVS.Vector Word64) where+ excess1 v c = fromIntegral (rank1 v c) - fromIntegral (rank0 v c)+ {-# INLINE excess1 #-}
+ src/HaskellWorks/Data/Succinct/Excess/MinMaxExcess0.hs view
@@ -0,0 +1,73 @@+{-# LANGUAGE FlexibleInstances #-}++module HaskellWorks.Data.Succinct.Excess.MinMaxExcess0+ ( MinMaxExcess0(..)+ , MaxExcess+ , MinExcess+ ) where++import qualified Data.Vector.Storable as DVS+import Data.Word+import HaskellWorks.Data.Bits.BitWise+import HaskellWorks.Data.Bits.FixedBitSize++type MinExcess = Int+type MaxExcess = Int+type Excess = Int++class MinMaxExcess0 a where+ minMaxExcess0 :: a -> (MinExcess, Excess, MaxExcess)++instance MinMaxExcess0 [Bool] where+ minMaxExcess0 = go 0 0 0+ where go minE maxE e (x:xs) = let ne = if x then e - 1 else e + 1 in+ go (minE `min` ne) (maxE `max` ne) ne xs+ go minE maxE e _ = (minE, e, maxE)++instance MinMaxExcess0 Word8 where+ minMaxExcess0 = go 0 0 0 0+ where go minE maxE e n w | n < fixedBitSize w = let ne = if w .?. fromIntegral n then e - 1 else e + 1 in+ go (minE `min` ne) (maxE `max` ne) ne (n + 1) w+ go minE maxE e _ _ = (minE, e, maxE)++instance MinMaxExcess0 Word16 where+ minMaxExcess0 = go 0 0 0 0+ where go minE maxE e n w | n < fixedBitSize w = let ne = if w .?. fromIntegral n then e - 1 else e + 1 in+ go (minE `min` ne) (maxE `max` ne) ne (n + 1) w+ go minE maxE e _ _ = (minE, e, maxE)++instance MinMaxExcess0 Word32 where+ minMaxExcess0 = go 0 0 0 0+ where go minE maxE e n w | n < fixedBitSize w = let ne = if w .?. fromIntegral n then e - 1 else e + 1 in+ go (minE `min` ne) (maxE `max` ne) ne (n + 1) w+ go minE maxE e _ _ = (minE, e, maxE)++instance MinMaxExcess0 Word64 where+ minMaxExcess0 = go 0 0 0 0+ where go minE maxE e n w | n < fixedBitSize w = let ne = if w .?. fromIntegral n then e - 1 else e + 1 in+ go (minE `min` ne) (maxE `max` ne) ne (n + 1) w+ go minE maxE e _ _ = (minE, e, maxE)++instance MinMaxExcess0 (DVS.Vector Word8) where+ minMaxExcess0 = DVS.foldl gen (0, 0, 0)+ where gen :: (MinExcess, Excess, MaxExcess) -> Word8 -> (MinExcess, Excess, MaxExcess)+ gen (minE, e, maxE) w = let (wMinE, wE, wMaxE) = minMaxExcess0 w in+ (minE `min` (wMinE + e), e + wE, maxE `max` (wMaxE + e))++instance MinMaxExcess0 (DVS.Vector Word16) where+ minMaxExcess0 = DVS.foldl gen (0, 0, 0)+ where gen :: (MinExcess, Excess, MaxExcess) -> Word16 -> (MinExcess, Excess, MaxExcess)+ gen (minE, e, maxE) w = let (wMinE, wE, wMaxE) = minMaxExcess0 w in+ (minE `min` (wMinE + e), e + wE, maxE `max` (wMaxE + e))++instance MinMaxExcess0 (DVS.Vector Word32) where+ minMaxExcess0 = DVS.foldl gen (0, 0, 0)+ where gen :: (MinExcess, Excess, MaxExcess) -> Word32 -> (MinExcess, Excess, MaxExcess)+ gen (minE, e, maxE) w = let (wMinE, wE, wMaxE) = minMaxExcess0 w in+ (minE `min` (wMinE + e), e + wE, maxE `max` (wMaxE + e))++instance MinMaxExcess0 (DVS.Vector Word64) where+ minMaxExcess0 = DVS.foldl gen (0, 0, 0)+ where gen :: (MinExcess, Excess, MaxExcess) -> Word64 -> (MinExcess, Excess, MaxExcess)+ gen (minE, e, maxE) w = let (wMinE, wE, wMaxE) = minMaxExcess0 w in+ (minE `min` (wMinE + e), e + wE, maxE `max` (wMaxE + e))
+ src/HaskellWorks/Data/Succinct/Excess/MinMaxExcess1.hs view
@@ -0,0 +1,73 @@+{-# LANGUAGE FlexibleInstances #-}++module HaskellWorks.Data.Succinct.Excess.MinMaxExcess1+ ( MinMaxExcess1(..)+ , MaxExcess+ , MinExcess+ ) where++import qualified Data.Vector.Storable as DVS+import Data.Word+import HaskellWorks.Data.Bits.BitWise+import HaskellWorks.Data.Bits.FixedBitSize++type MinExcess = Int+type MaxExcess = Int+type Excess = Int++class MinMaxExcess1 a where+ minMaxExcess1 :: a -> (MinExcess, Excess, MaxExcess)++instance MinMaxExcess1 [Bool] where+ minMaxExcess1 = go 0 0 0+ where go minE maxE e (x:xs) = let ne = if x then e + 1 else e - 1 in+ go (minE `min` ne) (maxE `max` ne) ne xs+ go minE maxE e _ = (minE, e, maxE)++instance MinMaxExcess1 Word8 where+ minMaxExcess1 = go 0 0 0 0+ where go minE maxE e n w | n < fixedBitSize w = let ne = if w .?. fromIntegral n then e + 1 else e - 1 in+ go (minE `min` ne) (maxE `max` ne) ne (n + 1) w+ go minE maxE e _ _ = (minE, e, maxE)++instance MinMaxExcess1 Word16 where+ minMaxExcess1 = go 0 0 0 0+ where go minE maxE e n w | n < fixedBitSize w = let ne = if w .?. fromIntegral n then e + 1 else e - 1 in+ go (minE `min` ne) (maxE `max` ne) ne (n + 1) w+ go minE maxE e _ _ = (minE, e, maxE)++instance MinMaxExcess1 Word32 where+ minMaxExcess1 = go 0 0 0 0+ where go minE maxE e n w | n < fixedBitSize w = let ne = if w .?. fromIntegral n then e + 1 else e - 1 in+ go (minE `min` ne) (maxE `max` ne) ne (n + 1) w+ go minE maxE e _ _ = (minE, e, maxE)++instance MinMaxExcess1 Word64 where+ minMaxExcess1 = go 0 0 0 0+ where go minE maxE e n w | n < fixedBitSize w = let ne = if w .?. fromIntegral n then e + 1 else e - 1 in+ go (minE `min` ne) (maxE `max` ne) ne (n + 1) w+ go minE maxE e _ _ = (minE, e, maxE)++instance MinMaxExcess1 (DVS.Vector Word8) where+ minMaxExcess1 = DVS.foldl gen (0, 0, 0)+ where gen :: (MinExcess, Excess, MaxExcess) -> Word8 -> (MinExcess, Excess, MaxExcess)+ gen (minE, e, maxE) w = let (wMinE, wE, wMaxE) = minMaxExcess1 w in+ (minE `min` (wMinE + e), e + wE, maxE `max` (wMaxE + e))++instance MinMaxExcess1 (DVS.Vector Word16) where+ minMaxExcess1 = DVS.foldl gen (0, 0, 0)+ where gen :: (MinExcess, Excess, MaxExcess) -> Word16 -> (MinExcess, Excess, MaxExcess)+ gen (minE, e, maxE) w = let (wMinE, wE, wMaxE) = minMaxExcess1 w in+ (minE `min` (wMinE + e), e + wE, maxE `max` (wMaxE + e))++instance MinMaxExcess1 (DVS.Vector Word32) where+ minMaxExcess1 = DVS.foldl gen (0, 0, 0)+ where gen :: (MinExcess, Excess, MaxExcess) -> Word32 -> (MinExcess, Excess, MaxExcess)+ gen (minE, e, maxE) w = let (wMinE, wE, wMaxE) = minMaxExcess1 w in+ (minE `min` (wMinE + e), e + wE, maxE `max` (wMaxE + e))++instance MinMaxExcess1 (DVS.Vector Word64) where+ minMaxExcess1 = DVS.foldl gen (0, 0, 0)+ where gen :: (MinExcess, Excess, MaxExcess) -> Word64 -> (MinExcess, Excess, MaxExcess)+ gen (minE, e, maxE) w = let (wMinE, wE, wMaxE) = minMaxExcess1 w in+ (minE `min` (wMinE + e), e + wE, maxE `max` (wMaxE + e))
src/HaskellWorks/Data/Succinct/RankSelect/Binary/Poppy512.hs view
@@ -68,15 +68,19 @@ wordAt o = fromIntegral o * 512 - (i !!! o) instance BalancedParens Poppy512 where- findOpen = findOpen . poppy512Bits+ openAt = openAt . poppy512Bits+ closeAt = closeAt . poppy512Bits+ -- findOpenN = findOpenN . poppy512Bits+ findCloseN = findCloseN . poppy512Bits+ -- findOpen = findOpen . poppy512Bits findClose = findClose . poppy512Bits- enclose = enclose . poppy512Bits+ -- enclose = enclose . poppy512Bits firstChild = firstChild . poppy512Bits nextSibling = nextSibling . poppy512Bits- parent = parent . poppy512Bits- {-# INLINABLE findOpen #-}+ -- parent = parent . poppy512Bits+ -- {-# INLINABLE findOpen #-} {-# INLINABLE findClose #-}- {-# INLINABLE enclose #-}+ -- {-# INLINABLE enclose #-} {-# INLINABLE firstChild #-} {-# INLINABLE nextSibling #-}- {-# INLINABLE parent #-}+ -- {-# INLINABLE parent #-}
src/HaskellWorks/Data/Succinct/RankSelect/Binary/Poppy512S.hs view
@@ -89,15 +89,11 @@ iMax = fromIntegral $ ((sampleMax - 1) `div` 512) + 1 :: Position instance BalancedParens Poppy512S where- findOpen = findOpen . poppy512SBits- findClose = findClose . poppy512SBits- enclose = enclose . poppy512SBits- firstChild = firstChild . poppy512SBits- nextSibling = nextSibling . poppy512SBits- parent = parent . poppy512SBits- {-# INLINABLE findOpen #-}- {-# INLINABLE findClose #-}- {-# INLINABLE enclose #-}- {-# INLINABLE firstChild #-}- {-# INLINABLE nextSibling #-}- {-# INLINABLE parent #-}+ openAt = openAt . poppy512SBits+ closeAt = closeAt . poppy512SBits+ -- findOpenN = findOpenN . poppy512SBits+ findCloseN = findCloseN . poppy512SBits+ {-# INLINABLE openAt #-}+ {-# INLINABLE closeAt #-}+ -- {-# INLINABLE findOpenN #-}+ {-# INLINABLE findCloseN #-}
+ test/HaskellWorks/Data/Succinct/BalancedParens/RangeMinMaxSpec.hs view
@@ -0,0 +1,57 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE OverloadedStrings #-}+{-# LANGUAGE ScopedTypeVariables #-}++module HaskellWorks.Data.Succinct.BalancedParens.RangeMinMaxSpec where++import qualified Data.Vector.Storable as DVS+import Data.Word+import HaskellWorks.Data.Bits.BitLength+import HaskellWorks.Data.Bits.BitShow+-- import HaskellWorks.Data.Bits.BitShown+import HaskellWorks.Data.Bits.FromBitTextByteString+import HaskellWorks.Data.Succinct.BalancedParens+import HaskellWorks.Data.Succinct.BalancedParens.RangeMinMax+import Test.Hspec+import Test.QuickCheck++{-# ANN module ("HLint: Ignore Redundant do" :: String) #-}+{-# ANN module ("HLint: Ignore Reduce duplication" :: String) #-}++newtype ShowVector a = ShowVector a deriving (Eq, BitShow)++instance BitShow a => Show (ShowVector a) where+ show = bitShow++vectorSizedBetween :: Int -> Int -> Gen (ShowVector (DVS.Vector Word64))+vectorSizedBetween a b = do+ n <- choose (a, b)+ xs <- sequence [ arbitrary | _ <- [1 .. n] ]+ return $ ShowVector (DVS.fromList xs)++spec :: Spec+spec = describe "HaskellWorks.Data.Succinct.BalancedParens.RangeMinMaxSpec" $ do+ it "XXX" $ do+ let v = fromBitTextByteString "11101111 10100101 01111110 10110010 10111011 10111011 00011111 11011100" :: DVS.Vector Word64+ let !rmm = mkRangeMinMaxL0 v+ findClose rmm 61 `shouldBe` findClose v 61+ it "findClose should return the same result" $ do+ forAll (vectorSizedBetween 1 4) $ \(ShowVector v) -> do+ let !rmm = mkRangeMinMaxL0 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+ forAll (vectorSizedBetween 1 512) $ \(ShowVector v) -> do+ forAll (choose (1, bitLength v)) $ \p -> do+ let !rmm = mkRangeMinMaxL0 v+ findClose rmm p `shouldBe` findClose v p+ it "nextSibling should return the same result" $ do+ forAll (vectorSizedBetween 1 512) $ \(ShowVector v) -> do+ let !rmm = mkRangeMinMaxL0 v+ nextSibling rmm 0 `shouldBe` nextSibling v 0+ it "nextSibling should return the same result over all counts" $ do+ forAll (vectorSizedBetween 1 512) $ \(ShowVector v) -> do+ forAll (choose (1, bitLength v)) $ \p -> do+ let !rmm = mkRangeMinMaxL0 v+ nextSibling rmm p `shouldBe` nextSibling v p
+ test/HaskellWorks/Data/Succinct/BalancedParens/SimpleSpec.hs view
@@ -0,0 +1,116 @@+{-# LANGUAGE ScopedTypeVariables #-}++module HaskellWorks.Data.Succinct.BalancedParens.SimpleSpec where++import Data.Maybe+import qualified Data.Vector.Storable as DVS+import Data.Word+import HaskellWorks.Data.Bits.BitRead+import HaskellWorks.Data.Succinct.BalancedParens+import Test.Hspec++{-# ANN module ("HLint: Ignore Redundant do" :: String) #-}+{-# ANN module ("HLint: Ignore Reduce duplication" :: String) #-}++spec :: Spec+spec = describe "HaskellWorks.Data.Succinct.BalancedParens.SimpleSpec" $ do+ describe "For (()(()())) 1101101000" $ do+ let bs = SimpleBalancedParens (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 = SimpleBalancedParens (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+ describe "For (()(()())) 11011010 00000000 :: DVS.Vector Word8" $ do+ let bs = SimpleBalancedParens (fromJust (bitRead "11011010 00000000") :: DVS.Vector Word8)+ it "Test 1a" $ findClose bs 1 `shouldBe` 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
− test/HaskellWorks/Data/Succinct/BalancedParensSpec.hs
@@ -1,116 +0,0 @@-{-# LANGUAGE ScopedTypeVariables #-}--module HaskellWorks.Data.Succinct.BalancedParensSpec where--import Data.Maybe-import qualified Data.Vector.Storable as DVS-import Data.Word-import HaskellWorks.Data.Bits.BitRead-import HaskellWorks.Data.Succinct.BalancedParens-import Test.Hspec--{-# ANN module ("HLint: ignore Redundant do" :: String) #-}-{-# ANN module ("HLint: ignore Reduce duplication" :: String) #-}--spec :: Spec-spec = describe "HaskellWorks.Data.Succinct.BalancedParensSpec" $ do- describe "For (()(()())) 1101101000" $ do- let bs = SimpleBalancedParens (91 :: Word64)- it "Test 1a" $ findClose bs 1 `shouldBe` 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 = SimpleBalancedParens (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- describe "For (()(()())) 11011010 00000000 :: DVS.Vector Word8" $ do- let bs = SimpleBalancedParens (fromJust (bitRead "11011010 00000000") :: DVS.Vector Word8)- it "Test 1a" $ findClose bs 1 `shouldBe` 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
+ test/HaskellWorks/Data/Succinct/Excess/MinMaxExcess0Spec.hs view
@@ -0,0 +1,149 @@+{-# OPTIONS_GHC -fno-warn-incomplete-patterns #-}+{-# LANGUAGE ScopedTypeVariables #-}++module HaskellWorks.Data.Succinct.Excess.MinMaxExcess0Spec (spec) where++import qualified Data.Vector.Storable as DVS+import Data.Word+import HaskellWorks.Data.Bits.Word+import HaskellWorks.Data.Succinct.Excess.MinMaxExcess0+import Test.Hspec+import Test.QuickCheck++{-# ANN module ("HLint: Ignore Redundant do" :: String) #-}+{-# ANN module ("HLint: Ignore Reduce duplication" :: String) #-}++spec :: Spec+spec = describe "HaskellWorks.Data.Succinct.Excess.MinMaxExcess0Spec" $ do+ describe "For Word8" $ do+ it "Excess should be between min excess and max excess" $+ forAll (choose (0, 255 :: Word8)) $ \w ->+ let (minE, e, maxE) = minMaxExcess0 w in+ minE <= e && e <= maxE+ it "minE2 == minE0 `min` (minE1 + e0)" $+ forAll (choose (0, 255 :: Word8)) $ \w0 ->+ forAll (choose (0, 255 :: Word8)) $ \w1 ->+ let w2 = leConcat w0 w1 in+ let (minE0, e0, _) = minMaxExcess0 w0 in+ let (minE1, _ , _) = minMaxExcess0 w1 in+ let (minE2, _ , _) = minMaxExcess0 w2 in+ minE2 == minE0 `min` (minE1 + e0)+ it "maxE2 == maxE0 `max` (maxE1 + e0)" $+ forAll (choose (0, 255 :: Word8)) $ \w0 ->+ forAll (choose (0, 255 :: Word8)) $ \w1 ->+ let w2 = leConcat w0 w1 in+ let (_, e0, maxE0) = minMaxExcess0 w0 in+ let (_, _ , maxE1) = minMaxExcess0 w1 in+ let (_, _ , maxE2) = minMaxExcess0 w2 in+ maxE2 == maxE0 `max` (maxE1 + e0)+ it "minE2 == minE0 `min` (minE1 + e0) via vector" $+ forAll (choose (0, 255 :: Word8)) $ \w0 ->+ forAll (choose (0, 255 :: Word8)) $ \w1 ->+ let w2 = DVS.fromList [w0, w1] in+ let (minE0, e0, _) = minMaxExcess0 w0 in+ let (minE1, _ , _) = minMaxExcess0 w1 in+ let (minE2, _ , _) = minMaxExcess0 w2 in+ minE2 == minE0 `min` (minE1 + e0)+ it "maxE2 == maxE0 `max` (maxE1 + e0) via vector" $+ forAll (choose (0, 255 :: Word8)) $ \w0 ->+ forAll (choose (0, 255 :: Word8)) $ \w1 ->+ let w2 = DVS.fromList [w0, w1] in+ let (_, e0, maxE0) = minMaxExcess0 w0 in+ let (_, _ , maxE1) = minMaxExcess0 w1 in+ let (_, _ , maxE2) = minMaxExcess0 w2 in+ maxE2 == maxE0 `max` (maxE1 + e0)+ describe "For Word16" $ do+ it "Excess should be between min excess and max excess" $+ forAll (choose (0, 255 :: Word16)) $ \w ->+ let (minE, e, maxE) = minMaxExcess0 w in+ minE <= e && e <= maxE+ it "minE2 == minE0 `min` (minE1 + e0)" $+ forAll (choose (0, 255 :: Word16)) $ \w0 ->+ forAll (choose (0, 255 :: Word16)) $ \w1 ->+ let w2 = leConcat w0 w1 in+ let (minE0, e0, _) = minMaxExcess0 w0 in+ let (minE1, _ , _) = minMaxExcess0 w1 in+ let (minE2, _ , _) = minMaxExcess0 w2 in+ minE2 == minE0 `min` (minE1 + e0)+ it "maxE2 == maxE0 `max` (maxE1 + e0)" $+ forAll (choose (0, 255 :: Word16)) $ \w0 ->+ forAll (choose (0, 255 :: Word16)) $ \w1 ->+ let w2 = leConcat w0 w1 in+ let (_, e0, maxE0) = minMaxExcess0 w0 in+ let (_, _ , maxE1) = minMaxExcess0 w1 in+ let (_, _ , maxE2) = minMaxExcess0 w2 in+ maxE2 == maxE0 `max` (maxE1 + e0)+ it "minE2 == minE0 `min` (minE1 + e0) via vector" $+ forAll (choose (0, 255 :: Word16)) $ \w0 ->+ forAll (choose (0, 255 :: Word16)) $ \w1 ->+ let w2 = DVS.fromList [w0, w1] in+ let (minE0, e0, _) = minMaxExcess0 w0 in+ let (minE1, _ , _) = minMaxExcess0 w1 in+ let (minE2, _ , _) = minMaxExcess0 w2 in+ minE2 == minE0 `min` (minE1 + e0)+ it "maxE2 == maxE0 `max` (maxE1 + e0) via vector" $+ forAll (choose (0, 255 :: Word16)) $ \w0 ->+ forAll (choose (0, 255 :: Word16)) $ \w1 ->+ let w2 = DVS.fromList [w0, w1] in+ let (_, e0, maxE0) = minMaxExcess0 w0 in+ let (_, _ , maxE1) = minMaxExcess0 w1 in+ let (_, _ , maxE2) = minMaxExcess0 w2 in+ maxE2 == maxE0 `max` (maxE1 + e0)+ describe "For Word32" $ do+ it "Excess should be between min excess and max excess" $+ forAll (choose (0, 255 :: Word32)) $ \w ->+ let (minE, e, maxE) = minMaxExcess0 w in+ minE <= e && e <= maxE+ it "minE2 == minE0 `min` (minE1 + e0)" $+ forAll (choose (0, 255 :: Word32)) $ \w0 ->+ forAll (choose (0, 255 :: Word32)) $ \w1 ->+ let w2 = leConcat w0 w1 in+ let (minE0, e0, _) = minMaxExcess0 w0 in+ let (minE1, _ , _) = minMaxExcess0 w1 in+ let (minE2, _ , _) = minMaxExcess0 w2 in+ minE2 == minE0 `min` (minE1 + e0)+ it "maxE2 == maxE0 `max` (maxE1 + e0)" $+ forAll (choose (0, 255 :: Word32)) $ \w0 ->+ forAll (choose (0, 255 :: Word32)) $ \w1 ->+ let w2 = leConcat w0 w1 in+ let (_, e0, maxE0) = minMaxExcess0 w0 in+ let (_, _ , maxE1) = minMaxExcess0 w1 in+ let (_, _ , maxE2) = minMaxExcess0 w2 in+ maxE2 == maxE0 `max` (maxE1 + e0)+ it "minE2 == minE0 `min` (minE1 + e0) via vector" $+ forAll (choose (0, 255 :: Word32)) $ \w0 ->+ forAll (choose (0, 255 :: Word32)) $ \w1 ->+ let w2 = DVS.fromList [w0, w1] in+ let (minE0, e0, _) = minMaxExcess0 w0 in+ let (minE1, _ , _) = minMaxExcess0 w1 in+ let (minE2, _ , _) = minMaxExcess0 w2 in+ minE2 == minE0 `min` (minE1 + e0)+ it "maxE2 == maxE0 `max` (maxE1 + e0) via vector" $+ forAll (choose (0, 255 :: Word32)) $ \w0 ->+ forAll (choose (0, 255 :: Word32)) $ \w1 ->+ let w2 = DVS.fromList [w0, w1] in+ let (_, e0, maxE0) = minMaxExcess0 w0 in+ let (_, _ , maxE1) = minMaxExcess0 w1 in+ let (_, _ , maxE2) = minMaxExcess0 w2 in+ maxE2 == maxE0 `max` (maxE1 + e0)+ describe "For Word64" $ do+ it "Excess should be between min excess and max excess" $+ forAll (choose (0, 255 :: Word64)) $ \w ->+ let (minE, e, maxE) = minMaxExcess0 w in+ minE <= e && e <= maxE+ it "minE2 == minE0 `min` (minE1 + e0) via vector" $+ forAll (choose (0, 255 :: Word64)) $ \w0 ->+ forAll (choose (0, 255 :: Word64)) $ \w1 ->+ let w2 = DVS.fromList [w0, w1] in+ let (minE0, e0, _) = minMaxExcess0 w0 in+ let (minE1, _ , _) = minMaxExcess0 w1 in+ let (minE2, _ , _) = minMaxExcess0 w2 in+ minE2 == minE0 `min` (minE1 + e0)+ it "maxE2 == maxE0 `max` (maxE1 + e0) via vector" $+ forAll (choose (0, 255 :: Word64)) $ \w0 ->+ forAll (choose (0, 255 :: Word64)) $ \w1 ->+ let w2 = DVS.fromList [w0, w1] in+ let (_, e0, maxE0) = minMaxExcess0 w0 in+ let (_, _ , maxE1) = minMaxExcess0 w1 in+ let (_, _ , maxE2) = minMaxExcess0 w2 in+ maxE2 == maxE0 `max` (maxE1 + e0)
+ test/HaskellWorks/Data/Succinct/Excess/MinMaxExcess1Spec.hs view
@@ -0,0 +1,149 @@+{-# OPTIONS_GHC -fno-warn-incomplete-patterns #-}+{-# LANGUAGE ScopedTypeVariables #-}++module HaskellWorks.Data.Succinct.Excess.MinMaxExcess1Spec (spec) where++import qualified Data.Vector.Storable as DVS+import Data.Word+import HaskellWorks.Data.Bits.Word+import HaskellWorks.Data.Succinct.Excess.MinMaxExcess1+import Test.Hspec+import Test.QuickCheck++{-# ANN module ("HLint: Ignore Redundant do" :: String) #-}+{-# ANN module ("HLint: Ignore Reduce duplication" :: String) #-}++spec :: Spec+spec = describe "HaskellWorks.Data.Succinct.Excess.MinMaxExcess1Spec" $ do+ describe "For Word8" $ do+ it "Excess should be between min excess and max excess" $+ forAll (choose (0, 255 :: Word8)) $ \w ->+ let (minE, e, maxE) = minMaxExcess1 w in+ minE <= e && e <= maxE+ it "minE2 == minE0 `min` (minE1 + e0)" $+ forAll (choose (0, 255 :: Word8)) $ \w0 ->+ forAll (choose (0, 255 :: Word8)) $ \w1 ->+ let w2 = leConcat w0 w1 in+ let (minE0, e0, _) = minMaxExcess1 w0 in+ let (minE1, _ , _) = minMaxExcess1 w1 in+ let (minE2, _ , _) = minMaxExcess1 w2 in+ minE2 == minE0 `min` (minE1 + e0)+ it "maxE2 == maxE0 `max` (maxE1 + e0)" $+ forAll (choose (0, 255 :: Word8)) $ \w0 ->+ forAll (choose (0, 255 :: Word8)) $ \w1 ->+ let w2 = leConcat w0 w1 in+ let (_, e0, maxE0) = minMaxExcess1 w0 in+ let (_, _ , maxE1) = minMaxExcess1 w1 in+ let (_, _ , maxE2) = minMaxExcess1 w2 in+ maxE2 == maxE0 `max` (maxE1 + e0)+ it "minE2 == minE0 `min` (minE1 + e0) via vector" $+ forAll (choose (0, 255 :: Word8)) $ \w0 ->+ forAll (choose (0, 255 :: Word8)) $ \w1 ->+ let w2 = DVS.fromList [w0, w1] in+ let (minE0, e0, _) = minMaxExcess1 w0 in+ let (minE1, _ , _) = minMaxExcess1 w1 in+ let (minE2, _ , _) = minMaxExcess1 w2 in+ minE2 == minE0 `min` (minE1 + e0)+ it "maxE2 == maxE0 `max` (maxE1 + e0) via vector" $+ forAll (choose (0, 255 :: Word8)) $ \w0 ->+ forAll (choose (0, 255 :: Word8)) $ \w1 ->+ let w2 = DVS.fromList [w0, w1] in+ let (_, e0, maxE0) = minMaxExcess1 w0 in+ let (_, _ , maxE1) = minMaxExcess1 w1 in+ let (_, _ , maxE2) = minMaxExcess1 w2 in+ maxE2 == maxE0 `max` (maxE1 + e0)+ describe "For Word16" $ do+ it "Excess should be between min excess and max excess" $+ forAll (choose (0, 255 :: Word16)) $ \w ->+ let (minE, e, maxE) = minMaxExcess1 w in+ minE <= e && e <= maxE+ it "minE2 == minE0 `min` (minE1 + e0)" $+ forAll (choose (0, 255 :: Word16)) $ \w0 ->+ forAll (choose (0, 255 :: Word16)) $ \w1 ->+ let w2 = leConcat w0 w1 in+ let (minE0, e0, _) = minMaxExcess1 w0 in+ let (minE1, _ , _) = minMaxExcess1 w1 in+ let (minE2, _ , _) = minMaxExcess1 w2 in+ minE2 == minE0 `min` (minE1 + e0)+ it "maxE2 == maxE0 `max` (maxE1 + e0)" $+ forAll (choose (0, 255 :: Word16)) $ \w0 ->+ forAll (choose (0, 255 :: Word16)) $ \w1 ->+ let w2 = leConcat w0 w1 in+ let (_, e0, maxE0) = minMaxExcess1 w0 in+ let (_, _ , maxE1) = minMaxExcess1 w1 in+ let (_, _ , maxE2) = minMaxExcess1 w2 in+ maxE2 == maxE0 `max` (maxE1 + e0)+ it "minE2 == minE0 `min` (minE1 + e0) via vector" $+ forAll (choose (0, 255 :: Word16)) $ \w0 ->+ forAll (choose (0, 255 :: Word16)) $ \w1 ->+ let w2 = DVS.fromList [w0, w1] in+ let (minE0, e0, _) = minMaxExcess1 w0 in+ let (minE1, _ , _) = minMaxExcess1 w1 in+ let (minE2, _ , _) = minMaxExcess1 w2 in+ minE2 == minE0 `min` (minE1 + e0)+ it "maxE2 == maxE0 `max` (maxE1 + e0) via vector" $+ forAll (choose (0, 255 :: Word16)) $ \w0 ->+ forAll (choose (0, 255 :: Word16)) $ \w1 ->+ let w2 = DVS.fromList [w0, w1] in+ let (_, e0, maxE0) = minMaxExcess1 w0 in+ let (_, _ , maxE1) = minMaxExcess1 w1 in+ let (_, _ , maxE2) = minMaxExcess1 w2 in+ maxE2 == maxE0 `max` (maxE1 + e0)+ describe "For Word32" $ do+ it "Excess should be between min excess and max excess" $+ forAll (choose (0, 255 :: Word32)) $ \w ->+ let (minE, e, maxE) = minMaxExcess1 w in+ minE <= e && e <= maxE+ it "minE2 == minE0 `min` (minE1 + e0)" $+ forAll (choose (0, 255 :: Word32)) $ \w0 ->+ forAll (choose (0, 255 :: Word32)) $ \w1 ->+ let w2 = leConcat w0 w1 in+ let (minE0, e0, _) = minMaxExcess1 w0 in+ let (minE1, _ , _) = minMaxExcess1 w1 in+ let (minE2, _ , _) = minMaxExcess1 w2 in+ minE2 == minE0 `min` (minE1 + e0)+ it "maxE2 == maxE0 `max` (maxE1 + e0)" $+ forAll (choose (0, 255 :: Word32)) $ \w0 ->+ forAll (choose (0, 255 :: Word32)) $ \w1 ->+ let w2 = leConcat w0 w1 in+ let (_, e0, maxE0) = minMaxExcess1 w0 in+ let (_, _ , maxE1) = minMaxExcess1 w1 in+ let (_, _ , maxE2) = minMaxExcess1 w2 in+ maxE2 == maxE0 `max` (maxE1 + e0)+ it "minE2 == minE0 `min` (minE1 + e0) via vector" $+ forAll (choose (0, 255 :: Word32)) $ \w0 ->+ forAll (choose (0, 255 :: Word32)) $ \w1 ->+ let w2 = DVS.fromList [w0, w1] in+ let (minE0, e0, _) = minMaxExcess1 w0 in+ let (minE1, _ , _) = minMaxExcess1 w1 in+ let (minE2, _ , _) = minMaxExcess1 w2 in+ minE2 == minE0 `min` (minE1 + e0)+ it "maxE2 == maxE0 `max` (maxE1 + e0) via vector" $+ forAll (choose (0, 255 :: Word32)) $ \w0 ->+ forAll (choose (0, 255 :: Word32)) $ \w1 ->+ let w2 = DVS.fromList [w0, w1] in+ let (_, e0, maxE0) = minMaxExcess1 w0 in+ let (_, _ , maxE1) = minMaxExcess1 w1 in+ let (_, _ , maxE2) = minMaxExcess1 w2 in+ maxE2 == maxE0 `max` (maxE1 + e0)+ describe "For Word64" $ do+ it "Excess should be between min excess and max excess" $+ forAll (choose (0, 255 :: Word64)) $ \w ->+ let (minE, e, maxE) = minMaxExcess1 w in+ minE <= e && e <= maxE+ it "minE2 == minE0 `min` (minE1 + e0) via vector" $+ forAll (choose (0, 255 :: Word64)) $ \w0 ->+ forAll (choose (0, 255 :: Word64)) $ \w1 ->+ let w2 = DVS.fromList [w0, w1] in+ let (minE0, e0, _) = minMaxExcess1 w0 in+ let (minE1, _ , _) = minMaxExcess1 w1 in+ let (minE2, _ , _) = minMaxExcess1 w2 in+ minE2 == minE0 `min` (minE1 + e0)+ it "maxE2 == maxE0 `max` (maxE1 + e0) via vector" $+ forAll (choose (0, 255 :: Word64)) $ \w0 ->+ forAll (choose (0, 255 :: Word64)) $ \w1 ->+ let w2 = DVS.fromList [w0, w1] in+ let (_, e0, maxE0) = minMaxExcess1 w0 in+ let (_, _ , maxE1) = minMaxExcess1 w1 in+ let (_, _ , maxE2) = minMaxExcess1 w2 in+ maxE2 == maxE0 `max` (maxE1 + e0)