module HaskellWorks.Data.Succinct.BalancedParens.Internal
( BalancedParens(..)
, subtreeSize
) where
import Control.Monad
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
class BalancedParens v where
openAt :: v -> Count -> Bool
closeAt :: v -> Count -> Bool
findCloseN :: v -> Count -> Count -> Maybe Count
firstChild :: v -> Count -> Maybe Count
nextSibling :: v -> Count -> Maybe Count
findClose :: v -> Count -> Maybe Count
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))
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))
openAt' :: TestBit a => a -> Count -> Bool
openAt' v c = v .?. toPosition (c 1)
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' v (c 1) (p + 1)
else findClose' v (c + 1) (p + 1)
else Nothing
instance (BalancedParens a, TestBit a, BitLength a) => BalancedParens (BitShown a) where
openAt = openAt' . bitShown
closeAt = closeAt' . bitShown
findCloseN = findClose' . bitShown
instance BalancedParens [Bool] where
openAt = openAt'
closeAt = closeAt'
findCloseN = findClose'
instance BalancedParens (DVS.Vector Word8) where
openAt = openAt'
closeAt = closeAt'
findCloseN = findClose'
instance BalancedParens (DVS.Vector Word16) where
openAt = openAt'
closeAt = closeAt'
findCloseN = findClose'
instance BalancedParens (DVS.Vector Word32) where
openAt = openAt'
closeAt = closeAt'
findCloseN = findClose'
instance BalancedParens (DVS.Vector Word64) where
openAt = openAt'
closeAt = closeAt'
findCloseN = findClose'
instance BalancedParens Word8 where
openAt = openAt'
closeAt = closeAt'
findCloseN = findClose'
instance BalancedParens Word16 where
openAt = openAt'
closeAt = closeAt'
findCloseN = findClose'
instance BalancedParens Word32 where
openAt = openAt'
closeAt = closeAt'
findCloseN = findClose'
instance BalancedParens Word64 where
openAt = openAt'
closeAt = closeAt'
findCloseN = findClose'