{-# 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      #-}