{-# LANGUAGE FlexibleInstances #-}
module HaskellWorks.Data.BalancedParens.BalancedParens
( BalancedParens(..)
, depth
, subtreeSize
) where
import Control.Monad
import Data.Word
import HaskellWorks.Data.BalancedParens.CloseAt
import HaskellWorks.Data.BalancedParens.Enclose
import HaskellWorks.Data.BalancedParens.FindClose
import HaskellWorks.Data.BalancedParens.FindOpen
import HaskellWorks.Data.BalancedParens.OpenAt
import HaskellWorks.Data.Naive
import HaskellWorks.Data.Positioning
import HaskellWorks.Data.RankSelect.Base.Rank0
import HaskellWorks.Data.RankSelect.Base.Rank1
import qualified Data.Vector.Storable as DVS
class (OpenAt v, CloseAt v, FindOpen v, FindClose v, Enclose v) => BalancedParens v where
firstChild :: v -> Count -> Maybe Count
firstChild v
v Word64
p = if forall v. OpenAt v => v -> Word64 -> Bool
openAt v
v Word64
p Bool -> Bool -> Bool
&& forall v. OpenAt v => v -> Word64 -> Bool
openAt v
v (Word64
p forall a. Num a => a -> a -> a
+ Word64
1) then forall a. a -> Maybe a
Just (Word64
p forall a. Num a => a -> a -> a
+ Word64
1) else forall a. Maybe a
Nothing
{-# INLINE firstChild #-}
nextSibling :: v -> Count -> Maybe Count
nextSibling v
v Word64
p = if forall v. CloseAt v => v -> Word64 -> Bool
closeAt v
v Word64
p
then forall a. Maybe a
Nothing
else forall v. OpenAt v => v -> Word64 -> Bool
openAt v
v forall (m :: * -> *) a. MonadPlus m => (a -> Bool) -> m a -> m a
`mfilter` (forall v. FindClose v => v -> Word64 -> Maybe Word64
findClose v
v Word64
p forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (\Word64
q ->
if Word64
p forall a. Eq a => a -> a -> Bool
/= Word64
q
then forall (m :: * -> *) a. Monad m => a -> m a
return (Word64
q forall a. Num a => a -> a -> a
+ Word64
1)
else forall a. Maybe a
Nothing))
{-# INLINE nextSibling #-}
parent :: v -> Count -> Maybe Count
parent v
v Word64
p = forall v. Enclose v => v -> Word64 -> Maybe Word64
enclose v
v Word64
p forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (\Word64
r -> if Word64
r forall a. Ord a => a -> a -> Bool
>= Word64
1 then forall (m :: * -> *) a. Monad m => a -> m a
return Word64
r else forall a. Maybe a
Nothing)
{-# INLINE parent #-}
depth :: (BalancedParens v, Rank0 v, Rank1 v) => v -> Count -> Maybe Count
depth :: forall v.
(BalancedParens v, Rank0 v, Rank1 v) =>
v -> Word64 -> Maybe Word64
depth v
v Word64
p = (\Word64
q -> forall v. Rank1 v => v -> Word64 -> Word64
rank1 v
v Word64
q forall a. Num a => a -> a -> a
- forall v. Rank0 v => v -> Word64 -> Word64
rank0 v
v Word64
q) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall v. FindOpen v => v -> Word64 -> Maybe Word64
findOpen v
v Word64
p
{-# INLINE depth #-}
subtreeSize :: BalancedParens v => v -> Count -> Maybe Count
subtreeSize :: forall v. BalancedParens v => v -> Word64 -> Maybe Word64
subtreeSize v
v Word64
p = (\Word64
q -> (Word64
q forall a. Num a => a -> a -> a
- Word64
p forall a. Num a => a -> a -> a
+ Word64
1) forall a. Integral a => a -> a -> a
`quot` Word64
2) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall v. FindClose v => v -> Word64 -> Maybe Word64
findClose v
v Word64
p
{-# INLINE subtreeSize #-}
instance BalancedParens [Bool]
instance BalancedParens (DVS.Vector Word8)
instance BalancedParens (DVS.Vector Word16)
instance BalancedParens (DVS.Vector Word32)
instance BalancedParens (DVS.Vector Word64)
instance BalancedParens Word8
instance BalancedParens Word16
instance BalancedParens Word32
instance BalancedParens Word64
instance BalancedParens (Naive Word64)