{-# OPTIONS_GHC-funbox-strict-fields #-} {-# LANGUAGE DeriveAnyClass #-} {-# LANGUAGE DeriveGeneric #-} {-# LANGUAGE TypeFamilies #-} module HaskellWorks.Data.RankSelect.Poppy512 ( Poppy512(..) , Rank1(..) , makePoppy512 ) where import Control.DeepSeq import Data.Word import GHC.Generics import HaskellWorks.Data.AtIndex import HaskellWorks.Data.BalancedParens.BalancedParens import HaskellWorks.Data.BalancedParens.CloseAt import HaskellWorks.Data.BalancedParens.Enclose import HaskellWorks.Data.BalancedParens.FindClose import HaskellWorks.Data.BalancedParens.FindCloseN import HaskellWorks.Data.BalancedParens.FindOpen import HaskellWorks.Data.BalancedParens.FindOpenN import HaskellWorks.Data.BalancedParens.NewCloseAt import HaskellWorks.Data.BalancedParens.OpenAt import HaskellWorks.Data.Bits.BitLength import HaskellWorks.Data.Bits.BitRead import HaskellWorks.Data.Bits.BitWise import HaskellWorks.Data.Bits.PopCount.PopCount0 import HaskellWorks.Data.Bits.PopCount.PopCount1 import HaskellWorks.Data.FromForeignRegion import HaskellWorks.Data.Positioning import HaskellWorks.Data.RankSelect.Base.Rank0 import HaskellWorks.Data.RankSelect.Base.Rank1 import HaskellWorks.Data.RankSelect.Base.Select0 import HaskellWorks.Data.RankSelect.Base.Select1 import HaskellWorks.Data.Search import HaskellWorks.Data.Vector.AsVector64 import Prelude hiding (length) import qualified Data.Vector.Storable as DVS data Poppy512 = Poppy512 { Poppy512 -> Vector Word64 poppy512Bits :: !(DVS.Vector Word64) , Poppy512 -> Vector Word64 poppy512Index :: !(DVS.Vector Word64) } deriving (Poppy512 -> Poppy512 -> Bool (Poppy512 -> Poppy512 -> Bool) -> (Poppy512 -> Poppy512 -> Bool) -> Eq Poppy512 forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a /= :: Poppy512 -> Poppy512 -> Bool $c/= :: Poppy512 -> Poppy512 -> Bool == :: Poppy512 -> Poppy512 -> Bool $c== :: Poppy512 -> Poppy512 -> Bool Eq, Int -> Poppy512 -> ShowS [Poppy512] -> ShowS Poppy512 -> String (Int -> Poppy512 -> ShowS) -> (Poppy512 -> String) -> ([Poppy512] -> ShowS) -> Show Poppy512 forall a. (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a showList :: [Poppy512] -> ShowS $cshowList :: [Poppy512] -> ShowS show :: Poppy512 -> String $cshow :: Poppy512 -> String showsPrec :: Int -> Poppy512 -> ShowS $cshowsPrec :: Int -> Poppy512 -> ShowS Show, Poppy512 -> () (Poppy512 -> ()) -> NFData Poppy512 forall a. (a -> ()) -> NFData a rnf :: Poppy512 -> () $crnf :: Poppy512 -> () NFData, (forall x. Poppy512 -> Rep Poppy512 x) -> (forall x. Rep Poppy512 x -> Poppy512) -> Generic Poppy512 forall x. Rep Poppy512 x -> Poppy512 forall x. Poppy512 -> Rep Poppy512 x forall a. (forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a $cto :: forall x. Rep Poppy512 x -> Poppy512 $cfrom :: forall x. Poppy512 -> Rep Poppy512 x Generic) instance FromForeignRegion Poppy512 where fromForeignRegion :: ForeignRegion -> Poppy512 fromForeignRegion = Vector Word64 -> Poppy512 makePoppy512 (Vector Word64 -> Poppy512) -> (ForeignRegion -> Vector Word64) -> ForeignRegion -> Poppy512 forall b c a. (b -> c) -> (a -> b) -> a -> c . ForeignRegion -> Vector Word64 forall a. FromForeignRegion a => ForeignRegion -> a fromForeignRegion instance PopCount0 Poppy512 where popCount0 :: Poppy512 -> Word64 popCount0 = Vector Word64 -> Word64 forall v. PopCount0 v => v -> Word64 popCount0 (Vector Word64 -> Word64) -> (Poppy512 -> Vector Word64) -> Poppy512 -> Word64 forall b c a. (b -> c) -> (a -> b) -> a -> c . Poppy512 -> Vector Word64 poppy512Bits {-# INLINE popCount0 #-} instance PopCount1 Poppy512 where popCount1 :: Poppy512 -> Word64 popCount1 = Vector Word64 -> Word64 forall v. PopCount1 v => v -> Word64 popCount1 (Vector Word64 -> Word64) -> (Poppy512 -> Vector Word64) -> Poppy512 -> Word64 forall b c a. (b -> c) -> (a -> b) -> a -> c . Poppy512 -> Vector Word64 poppy512Bits {-# INLINE popCount1 #-} instance AsVector64 Poppy512 where asVector64 :: Poppy512 -> Vector Word64 asVector64 = Vector Word64 -> Vector Word64 forall a. AsVector64 a => a -> Vector Word64 asVector64 (Vector Word64 -> Vector Word64) -> (Poppy512 -> Vector Word64) -> Poppy512 -> Vector Word64 forall b c a. (b -> c) -> (a -> b) -> a -> c . Poppy512 -> Vector Word64 poppy512Bits {-# INLINE asVector64 #-} makePoppy512 :: DVS.Vector Word64 -> Poppy512 makePoppy512 :: Vector Word64 -> Poppy512 makePoppy512 Vector Word64 v = Poppy512 :: Vector Word64 -> Vector Word64 -> Poppy512 Poppy512 { poppy512Bits :: Vector Word64 poppy512Bits = Vector Word64 v , poppy512Index :: Vector Word64 poppy512Index = Int -> (Vector Word64 -> Word64) -> Vector Word64 forall a. Storable a => Int -> (Vector a -> a) -> Vector a DVS.constructN (((Vector Word64 -> Int forall a. Storable a => Vector a -> Int DVS.length Vector Word64 v Int -> Int -> Int forall a. Num a => a -> a -> a + Int 7) Int -> Int -> Int forall a. Integral a => a -> a -> a `div` Int 8) Int -> Int -> Int forall a. Num a => a -> a -> a + Int 1) Vector Word64 -> Word64 gen512Index } where gen512Index :: DVS.Vector Word64 -> Word64 gen512Index :: Vector Word64 -> Word64 gen512Index Vector Word64 u = let indexN :: Int indexN = Vector Word64 -> Int forall a. Storable a => Vector a -> Int DVS.length Vector Word64 u Int -> Int -> Int forall a. Num a => a -> a -> a - Int 1 in if Int indexN Int -> Int -> Bool forall a. Eq a => a -> a -> Bool == -Int 1 then Word64 0 else Vector Word64 -> Word64 forall v. PopCount1 v => v -> Word64 popCount1 (Int -> Vector Word64 -> Vector Word64 forall a. Storable a => Int -> Vector a -> Vector a DVS.take Int 8 (Int -> Vector Word64 -> Vector Word64 forall a. Storable a => Int -> Vector a -> Vector a DVS.drop (Int indexN Int -> Int -> Int forall a. Num a => a -> a -> a * Int 8) Vector Word64 v)) Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a + Vector Word64 -> Word64 forall a. Storable a => Vector a -> a DVS.last Vector Word64 u instance BitLength Poppy512 where bitLength :: Poppy512 -> Word64 bitLength Poppy512 v = Vector Word64 -> Word64 forall v. Length v => v -> Word64 length (Poppy512 -> Vector Word64 poppy512Bits Poppy512 v) Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a * Word64 -> Word64 forall v. BitLength v => v -> Word64 bitLength (Poppy512 -> Vector Word64 poppy512Bits Poppy512 v Vector Word64 -> Position -> Elem (Vector Word64) forall v. AtIndex v => v -> Position -> Elem v !!! Position 0) {-# INLINE bitLength #-} instance TestBit Poppy512 where .?. :: Poppy512 -> Position -> Bool (.?.) = Vector Word64 -> Position -> Bool forall a. TestBit a => a -> Position -> Bool (.?.) (Vector Word64 -> Position -> Bool) -> (Poppy512 -> Vector Word64) -> Poppy512 -> Position -> Bool forall b c a. (b -> c) -> (a -> b) -> a -> c . Poppy512 -> Vector Word64 poppy512Bits {-# INLINE (.?.) #-} instance BitRead Poppy512 where bitRead :: String -> Maybe Poppy512 bitRead = (Vector Word64 -> Poppy512) -> Maybe (Vector Word64) -> Maybe Poppy512 forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b fmap Vector Word64 -> Poppy512 makePoppy512 (Maybe (Vector Word64) -> Maybe Poppy512) -> (String -> Maybe (Vector Word64)) -> String -> Maybe Poppy512 forall b c a. (b -> c) -> (a -> b) -> a -> c . String -> Maybe (Vector Word64) forall a. BitRead a => String -> Maybe a bitRead instance Rank1 Poppy512 where rank1 :: Poppy512 -> Word64 -> Word64 rank1 (Poppy512 Vector Word64 v Vector Word64 i) Word64 p = (Vector Word64 i Vector Word64 -> Position -> Elem (Vector Word64) forall v. AtIndex v => v -> Position -> Elem v !!! Word64 -> Position forall a. ToPosition a => a -> Position toPosition (Word64 p Word64 -> Word64 -> Word64 forall a. Integral a => a -> a -> a `div` Word64 512)) Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a + Vector Word64 -> Word64 -> Word64 forall v. Rank1 v => v -> Word64 -> Word64 rank1 (Int -> Vector Word64 -> Vector Word64 forall a. Storable a => Int -> Vector a -> Vector a DVS.drop ((Word64 -> Int forall a b. (Integral a, Num b) => a -> b fromIntegral Word64 p Int -> Int -> Int forall a. Integral a => a -> a -> a `div` Int 512) Int -> Int -> Int forall a. Num a => a -> a -> a * Int 8) Vector Word64 v) (Word64 p Word64 -> Word64 -> Word64 forall a. Integral a => a -> a -> a `mod` Word64 512) instance Rank0 Poppy512 where rank0 :: Poppy512 -> Word64 -> Word64 rank0 (Poppy512 Vector Word64 v Vector Word64 i) Word64 p = Word64 p Word64 -> Word64 -> Word64 forall a. Integral a => a -> a -> a `div` Word64 512 Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a * Word64 512 Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a - (Vector Word64 i Vector Word64 -> Position -> Elem (Vector Word64) forall v. AtIndex v => v -> Position -> Elem v !!! Word64 -> Position forall a. ToPosition a => a -> Position toPosition (Word64 p Word64 -> Word64 -> Word64 forall a. Integral a => a -> a -> a `div` Word64 512)) Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a + Vector Word64 -> Word64 -> Word64 forall v. Rank0 v => v -> Word64 -> Word64 rank0 (Int -> Vector Word64 -> Vector Word64 forall a. Storable a => Int -> Vector a -> Vector a DVS.drop ((Word64 -> Int forall a b. (Integral a, Num b) => a -> b fromIntegral Word64 p Int -> Int -> Int forall a. Integral a => a -> a -> a `div` Int 512) Int -> Int -> Int forall a. Num a => a -> a -> a * Int 8) Vector Word64 v) (Word64 p Word64 -> Word64 -> Word64 forall a. Integral a => a -> a -> a `mod` Word64 512) instance Select1 Poppy512 where select1 :: Poppy512 -> Word64 -> Word64 select1 (Poppy512 Vector Word64 v Vector Word64 i) Word64 p = Position -> Word64 forall a. ToCount a => a -> Word64 toCount Position q Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a * Word64 512 Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a + Vector Word64 -> Word64 -> Word64 forall v. Select1 v => v -> Word64 -> Word64 select1 (Int -> Vector Word64 -> Vector Word64 forall a. Storable a => Int -> Vector a -> Vector a DVS.drop (Position -> Int forall a b. (Integral a, Num b) => a -> b fromIntegral Position q Int -> Int -> Int forall a. Num a => a -> a -> a * Int 8) Vector Word64 v) (Word64 p Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a - Word64 s) where q :: Position q = Word64 -> (Position -> Word64) -> Position -> Position -> Position forall a n. (Ord a, Integral n) => a -> (n -> a) -> n -> n -> n binarySearch (Word64 -> Word64 forall a b. (Integral a, Num b) => a -> b fromIntegral Word64 p) Position -> Word64 Position -> Elem (Vector Word64) wordAt Position 0 (Int -> Position forall a b. (Integral a, Num b) => a -> b fromIntegral (Int -> Position) -> Int -> Position forall a b. (a -> b) -> a -> b $ Vector Word64 -> Int forall a. Storable a => Vector a -> Int DVS.length Vector Word64 i Int -> Int -> Int forall a. Num a => a -> a -> a - Int 1) s :: Word64 s = (Vector Word64 i Vector Word64 -> Position -> Elem (Vector Word64) forall v. AtIndex v => v -> Position -> Elem v !!! Position q) :: Count wordAt :: Position -> Elem (Vector Word64) wordAt = (Vector Word64 i Vector Word64 -> Position -> Elem (Vector Word64) forall v. AtIndex v => v -> Position -> Elem v !!!) instance Select0 Poppy512 where select0 :: Poppy512 -> Word64 -> Word64 select0 (Poppy512 Vector Word64 v Vector Word64 i) Word64 p = Position -> Word64 forall a. ToCount a => a -> Word64 toCount Position q Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a * Word64 512 Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a + Vector Word64 -> Word64 -> Word64 forall v. Select0 v => v -> Word64 -> Word64 select0 (Int -> Vector Word64 -> Vector Word64 forall a. Storable a => Int -> Vector a -> Vector a DVS.drop (Position -> Int forall a b. (Integral a, Num b) => a -> b fromIntegral Position q Int -> Int -> Int forall a. Num a => a -> a -> a * Int 8) Vector Word64 v) (Word64 p Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a - Word64 s) where q :: Position q = Word64 -> (Position -> Word64) -> Position -> Position -> Position forall a n. (Ord a, Integral n) => a -> (n -> a) -> n -> n -> n binarySearch (Word64 -> Word64 forall a b. (Integral a, Num b) => a -> b fromIntegral Word64 p) Position -> Word64 wordAt Position 0 (Int -> Position forall a b. (Integral a, Num b) => a -> b fromIntegral (Int -> Position) -> Int -> Position forall a b. (a -> b) -> a -> b $ Vector Word64 -> Int forall a. Storable a => Vector a -> Int DVS.length Vector Word64 i Int -> Int -> Int forall a. Num a => a -> a -> a - Int 1) s :: Word64 s = (Position -> Word64 forall a b. (Integral a, Num b) => a -> b fromIntegral Position q Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a * Word64 512 Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a - (Vector Word64 i Vector Word64 -> Position -> Elem (Vector Word64) forall v. AtIndex v => v -> Position -> Elem v !!! Position q)) :: Count wordAt :: Position -> Word64 wordAt Position o = Position -> Word64 forall a b. (Integral a, Num b) => a -> b fromIntegral Position o Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a * Word64 512 Word64 -> Word64 -> Word64 forall a. Num a => a -> a -> a - (Vector Word64 i Vector Word64 -> Position -> Elem (Vector Word64) forall v. AtIndex v => v -> Position -> Elem v !!! Position o) instance OpenAt Poppy512 where openAt :: Poppy512 -> Word64 -> Bool openAt = Vector Word64 -> Word64 -> Bool forall v. OpenAt v => v -> Word64 -> Bool openAt (Vector Word64 -> Word64 -> Bool) -> (Poppy512 -> Vector Word64) -> Poppy512 -> Word64 -> Bool forall b c a. (b -> c) -> (a -> b) -> a -> c . Poppy512 -> Vector Word64 poppy512Bits {-# INLINE openAt #-} instance CloseAt Poppy512 where closeAt :: Poppy512 -> Word64 -> Bool closeAt = Vector Word64 -> Word64 -> Bool forall v. CloseAt v => v -> Word64 -> Bool closeAt (Vector Word64 -> Word64 -> Bool) -> (Poppy512 -> Vector Word64) -> Poppy512 -> Word64 -> Bool forall b c a. (b -> c) -> (a -> b) -> a -> c . Poppy512 -> Vector Word64 poppy512Bits {-# INLINE closeAt #-} instance FindOpenN Poppy512 where findOpenN :: Poppy512 -> Word64 -> Word64 -> Maybe Word64 findOpenN = Vector Word64 -> Word64 -> Word64 -> Maybe Word64 forall v. FindOpenN v => v -> Word64 -> Word64 -> Maybe Word64 findOpenN (Vector Word64 -> Word64 -> Word64 -> Maybe Word64) -> (Poppy512 -> Vector Word64) -> Poppy512 -> Word64 -> Word64 -> Maybe Word64 forall b c a. (b -> c) -> (a -> b) -> a -> c . Poppy512 -> Vector Word64 poppy512Bits {-# INLINE findOpenN #-} instance FindCloseN Poppy512 where findCloseN :: Poppy512 -> Word64 -> Word64 -> Maybe Word64 findCloseN = Vector Word64 -> Word64 -> Word64 -> Maybe Word64 forall v. FindCloseN v => v -> Word64 -> Word64 -> Maybe Word64 findCloseN (Vector Word64 -> Word64 -> Word64 -> Maybe Word64) -> (Poppy512 -> Vector Word64) -> Poppy512 -> Word64 -> Word64 -> Maybe Word64 forall b c a. (b -> c) -> (a -> b) -> a -> c . Poppy512 -> Vector Word64 poppy512Bits {-# INLINE findCloseN #-} instance FindOpen Poppy512 where findOpen :: Poppy512 -> Word64 -> Maybe Word64 findOpen = Vector Word64 -> Word64 -> Maybe Word64 forall v. FindOpen v => v -> Word64 -> Maybe Word64 findOpen (Vector Word64 -> Word64 -> Maybe Word64) -> (Poppy512 -> Vector Word64) -> Poppy512 -> Word64 -> Maybe Word64 forall b c a. (b -> c) -> (a -> b) -> a -> c . Poppy512 -> Vector Word64 poppy512Bits {-# INLINE findOpen #-} instance FindClose Poppy512 where findClose :: Poppy512 -> Word64 -> Maybe Word64 findClose = Vector Word64 -> Word64 -> Maybe Word64 forall v. FindClose v => v -> Word64 -> Maybe Word64 findClose (Vector Word64 -> Word64 -> Maybe Word64) -> (Poppy512 -> Vector Word64) -> Poppy512 -> Word64 -> Maybe Word64 forall b c a. (b -> c) -> (a -> b) -> a -> c . Poppy512 -> Vector Word64 poppy512Bits {-# INLINE findClose #-} instance NewCloseAt Poppy512 where newCloseAt :: Poppy512 -> Word64 -> Bool newCloseAt = Vector Word64 -> Word64 -> Bool forall v. NewCloseAt v => v -> Word64 -> Bool newCloseAt (Vector Word64 -> Word64 -> Bool) -> (Poppy512 -> Vector Word64) -> Poppy512 -> Word64 -> Bool forall b c a. (b -> c) -> (a -> b) -> a -> c . Poppy512 -> Vector Word64 poppy512Bits {-# INLINE newCloseAt #-} instance Enclose Poppy512 where enclose :: Poppy512 -> Word64 -> Maybe Word64 enclose = Vector Word64 -> Word64 -> Maybe Word64 forall v. Enclose v => v -> Word64 -> Maybe Word64 enclose (Vector Word64 -> Word64 -> Maybe Word64) -> (Poppy512 -> Vector Word64) -> Poppy512 -> Word64 -> Maybe Word64 forall b c a. (b -> c) -> (a -> b) -> a -> c . Poppy512 -> Vector Word64 poppy512Bits {-# INLINE enclose #-} instance BalancedParens Poppy512 where firstChild :: Poppy512 -> Word64 -> Maybe Word64 firstChild = Vector Word64 -> Word64 -> Maybe Word64 forall v. BalancedParens v => v -> Word64 -> Maybe Word64 firstChild (Vector Word64 -> Word64 -> Maybe Word64) -> (Poppy512 -> Vector Word64) -> Poppy512 -> Word64 -> Maybe Word64 forall b c a. (b -> c) -> (a -> b) -> a -> c . Poppy512 -> Vector Word64 poppy512Bits nextSibling :: Poppy512 -> Word64 -> Maybe Word64 nextSibling = Vector Word64 -> Word64 -> Maybe Word64 forall v. BalancedParens v => v -> Word64 -> Maybe Word64 nextSibling (Vector Word64 -> Word64 -> Maybe Word64) -> (Poppy512 -> Vector Word64) -> Poppy512 -> Word64 -> Maybe Word64 forall b c a. (b -> c) -> (a -> b) -> a -> c . Poppy512 -> Vector Word64 poppy512Bits parent :: Poppy512 -> Word64 -> Maybe Word64 parent = Vector Word64 -> Word64 -> Maybe Word64 forall v. BalancedParens v => v -> Word64 -> Maybe Word64 parent (Vector Word64 -> Word64 -> Maybe Word64) -> (Poppy512 -> Vector Word64) -> Poppy512 -> Word64 -> Maybe Word64 forall b c a. (b -> c) -> (a -> b) -> a -> c . Poppy512 -> Vector Word64 poppy512Bits {-# INLINE firstChild #-} {-# INLINE nextSibling #-} {-# INLINE parent #-}