{-# LANGUAGE FlexibleInstances          #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE StandaloneDeriving         #-}

module HaskellWorks.Data.RankSelect.Base.Rank1
    ( Rank1(..)
    ) where

import Data.Word
import HaskellWorks.Data.AtIndex
import HaskellWorks.Data.Bits.BitShown
import HaskellWorks.Data.Bits.BitWise
import HaskellWorks.Data.Bits.ElemFixedBitSize
import HaskellWorks.Data.Bits.PopCount.PopCount1
import HaskellWorks.Data.Positioning

import qualified Data.Vector          as DV
import qualified Data.Vector.Storable as DVS

{-# ANN module ("HLint: Ignore Reduce duplication"  :: String) #-}

class Rank1 v where
  rank1 :: v -> Count -> Count

deriving instance Rank1 a => Rank1 (BitShown a)

instance Rank1 Word8 where
  rank1 :: Word8 -> Count -> Count
rank1 Word8
_ Count
0 = Count
0
  rank1 Word8
v Count
i = Word8 -> Count
forall v. PopCount1 v => v -> Count
popCount1 (Word8
v Word8 -> Word8 -> Word8
forall a. BitWise a => a -> a -> a
.&. ((Word8
1 Word8 -> Count -> Word8
forall a. Shift a => a -> Count -> a
.<. Count -> Count
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
i) Word8 -> Word8 -> Word8
forall a. Num a => a -> a -> a
- Word8
1))
  {-# INLINABLE rank1 #-}

instance Rank1 Word16 where
  rank1 :: Word16 -> Count -> Count
rank1 Word16
_ Count
0 = Count
0
  rank1 Word16
v Count
i = Word16 -> Count
forall v. PopCount1 v => v -> Count
popCount1 (Word16
v Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. ((Word16
1 Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.<. Count -> Count
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
i) Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Word16
1))
  {-# INLINABLE rank1 #-}

instance Rank1 Word32 where
  rank1 :: Word32 -> Count -> Count
rank1 Word32
_ Count
0 = Count
0
  rank1 Word32
v Count
i = Word32 -> Count
forall v. PopCount1 v => v -> Count
popCount1 (Word32
v Word32 -> Word32 -> Word32
forall a. BitWise a => a -> a -> a
.&. ((Word32
1 Word32 -> Count -> Word32
forall a. Shift a => a -> Count -> a
.<. Count -> Count
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
i) Word32 -> Word32 -> Word32
forall a. Num a => a -> a -> a
- Word32
1))
  {-# INLINABLE rank1 #-}

instance Rank1 Word64 where
  rank1 :: Count -> Count -> Count
rank1 Count
_ Count
0 = Count
0
  rank1 Count
v Count
i = Count -> Count
forall v. PopCount1 v => v -> Count
popCount1 (Count
v Count -> Count -> Count
forall a. BitWise a => a -> a -> a
.&. ((Count
1 Count -> Count -> Count
forall a. Shift a => a -> Count -> a
.<. Count -> Count
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
i) Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1))
  {-# INLINABLE rank1 #-}

instance Rank1 [Bool] where
  rank1 :: [Bool] -> Count -> Count
rank1 = Count -> [Bool] -> Count -> Count
forall a t. (Eq a, Num a, Num t) => t -> [Bool] -> a -> t
go Count
0
    where go :: t -> [Bool] -> a -> t
go t
r [Bool]
_ a
0          = t
r
          go t
r (Bool
True :[Bool]
bs) a
p = t -> [Bool] -> a -> t
go (t
r t -> t -> t
forall a. Num a => a -> a -> a
+ t
1) [Bool]
bs (a
p a -> a -> a
forall a. Num a => a -> a -> a
- a
1)
          go t
r (Bool
False:[Bool]
bs) a
p = t -> [Bool] -> a -> t
go  t
r      [Bool]
bs (a
p a -> a -> a
forall a. Num a => a -> a -> a
- a
1)
          go t
_ [] a
_         = [Char] -> t
forall a. HasCallStack => [Char] -> a
error [Char]
"Out of range"
  {-# INLINABLE rank1 #-}

instance Rank1 [Word8] where
  rank1 :: [Word8] -> Count -> Count
rank1 [Word8]
v Count
p = [Word8] -> Count
forall v. PopCount1 v => v -> Count
popCount1 [Word8]
prefix Count -> Count -> Count
forall a. Num a => a -> a -> a
+ if Count
r Count -> Count -> Bool
forall a. Eq a => a -> a -> Bool
== Count
0 then Count
0 else (Word8 -> Count -> Count
forall v. Rank1 v => v -> Count -> Count
`rank1` Count
r) Word8
maybeElem
    where (Count
q, Count
r)    = if Count
p Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
< Count
1 then (Count
0, Count
0) else ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`quot` [Word8] -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize [Word8]
v, ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`rem` [Word8] -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize [Word8]
v) Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
1)
          prefix :: [Word8]
prefix    = Int -> [Word8] -> [Word8]
forall a. Int -> [a] -> [a]
take (Count -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q) [Word8]
v
          maybeElem :: Word8
maybeElem = [Word8]
v [Word8] -> Int -> Word8
forall a. [a] -> Int -> a
!! Count -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q
  {-# INLINABLE rank1 #-}

instance Rank1 [Word16] where
  rank1 :: [Word16] -> Count -> Count
rank1 [Word16]
v Count
p = [Word16] -> Count
forall v. PopCount1 v => v -> Count
popCount1 [Word16]
prefix Count -> Count -> Count
forall a. Num a => a -> a -> a
+ if Count
r Count -> Count -> Bool
forall a. Eq a => a -> a -> Bool
== Count
0 then Count
0 else (Word16 -> Count -> Count
forall v. Rank1 v => v -> Count -> Count
`rank1` Count
r) Word16
maybeElem
    where (Count
q, Count
r)    = if Count
p Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
< Count
1 then (Count
0, Count
0) else ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`quot` [Word16] -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize [Word16]
v, ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`rem` [Word16] -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize [Word16]
v) Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
1)
          prefix :: [Word16]
prefix    = Int -> [Word16] -> [Word16]
forall a. Int -> [a] -> [a]
take (Count -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q) [Word16]
v
          maybeElem :: Word16
maybeElem = [Word16]
v [Word16] -> Int -> Word16
forall a. [a] -> Int -> a
!! Count -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q
  {-# INLINABLE rank1 #-}

instance Rank1 [Word32] where
  rank1 :: [Word32] -> Count -> Count
rank1 [Word32]
v Count
p = [Word32] -> Count
forall v. PopCount1 v => v -> Count
popCount1 [Word32]
prefix Count -> Count -> Count
forall a. Num a => a -> a -> a
+ if Count
r Count -> Count -> Bool
forall a. Eq a => a -> a -> Bool
== Count
0 then Count
0 else (Word32 -> Count -> Count
forall v. Rank1 v => v -> Count -> Count
`rank1` Count
r) Word32
maybeElem
    where (Count
q, Count
r)    = if Count
p Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
< Count
1 then (Count
0, Count
0) else ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`quot` [Word32] -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize [Word32]
v, ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`rem` [Word32] -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize [Word32]
v) Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
1)
          prefix :: [Word32]
prefix    = Int -> [Word32] -> [Word32]
forall a. Int -> [a] -> [a]
take (Count -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q) [Word32]
v
          maybeElem :: Word32
maybeElem = [Word32]
v [Word32] -> Int -> Word32
forall a. [a] -> Int -> a
!! Count -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q
  {-# INLINABLE rank1 #-}

instance Rank1 [Word64] where
  rank1 :: [Count] -> Count -> Count
rank1 [Count]
v Count
p = [Count] -> Count
forall v. PopCount1 v => v -> Count
popCount1 [Count]
prefix Count -> Count -> Count
forall a. Num a => a -> a -> a
+ if Count
r Count -> Count -> Bool
forall a. Eq a => a -> a -> Bool
== Count
0 then Count
0 else (Count -> Count -> Count
forall v. Rank1 v => v -> Count -> Count
`rank1` Count
r) Count
maybeElem
    where (Count
q, Count
r)    = if Count
p Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
< Count
1 then (Count
0, Count
0) else ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`quot` [Count] -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize [Count]
v, ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`rem` [Count] -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize [Count]
v) Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
1)
          prefix :: [Count]
prefix    = Int -> [Count] -> [Count]
forall a. Int -> [a] -> [a]
take (Count -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q) [Count]
v
          maybeElem :: Count
maybeElem = [Count]
v [Count] -> Int -> Count
forall a. [a] -> Int -> a
!! Count -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q
  {-# INLINABLE rank1 #-}

instance Rank1 (DV.Vector Word8) where
  rank1 :: Vector Word8 -> Count -> Count
rank1 Vector Word8
v Count
p = Vector Word8 -> Count
forall v. PopCount1 v => v -> Count
popCount1 Vector Word8
prefix Count -> Count -> Count
forall a. Num a => a -> a -> a
+ if Count
r Count -> Count -> Bool
forall a. Eq a => a -> a -> Bool
== Count
0 then Count
0 else (Word8 -> Count -> Count
forall v. Rank1 v => v -> Count -> Count
`rank1` Count
r) Word8
maybeElem
    where (Count
q, Count
r)    = if Count
p Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
< Count
1 then (Count
0, Count
0) else ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`quot` Vector Word8 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word8
v, ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`rem` Vector Word8 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word8
v) Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
1)
          prefix :: Vector Word8
prefix    = Int -> Vector Word8 -> Vector Word8
forall a. Int -> Vector a -> Vector a
DV.take (Count -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q) Vector Word8
v
          maybeElem :: Elem (Vector Word8)
maybeElem = Vector Word8
v Vector Word8 -> Position -> Elem (Vector Word8)
forall v. AtIndex v => v -> Position -> Elem v
!!! Count -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q
  {-# INLINABLE rank1 #-}

instance Rank1 (DV.Vector Word16) where
  rank1 :: Vector Word16 -> Count -> Count
rank1 Vector Word16
v Count
p = Vector Word16 -> Count
forall v. PopCount1 v => v -> Count
popCount1 Vector Word16
prefix Count -> Count -> Count
forall a. Num a => a -> a -> a
+ if Count
r Count -> Count -> Bool
forall a. Eq a => a -> a -> Bool
== Count
0 then Count
0 else (Word16 -> Count -> Count
forall v. Rank1 v => v -> Count -> Count
`rank1` Count
r) Word16
maybeElem
    where (Count
q, Count
r)    = if Count
p Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
< Count
1 then (Count
0, Count
0) else ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`quot` Vector Word16 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word16
v, ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`rem` Vector Word16 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word16
v) Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
1)
          prefix :: Vector Word16
prefix    = Int -> Vector Word16 -> Vector Word16
forall a. Int -> Vector a -> Vector a
DV.take (Count -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q) Vector Word16
v
          maybeElem :: Elem (Vector Word16)
maybeElem = Vector Word16
v Vector Word16 -> Position -> Elem (Vector Word16)
forall v. AtIndex v => v -> Position -> Elem v
!!! Count -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q
  {-# INLINABLE rank1 #-}

instance Rank1 (DV.Vector Word32) where
  rank1 :: Vector Word32 -> Count -> Count
rank1 Vector Word32
v Count
p = Vector Word32 -> Count
forall v. PopCount1 v => v -> Count
popCount1 Vector Word32
prefix Count -> Count -> Count
forall a. Num a => a -> a -> a
+ if Count
r Count -> Count -> Bool
forall a. Eq a => a -> a -> Bool
== Count
0 then Count
0 else (Word32 -> Count -> Count
forall v. Rank1 v => v -> Count -> Count
`rank1` Count
r) Word32
maybeElem
    where (Count
q, Count
r)    = if Count
p Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
< Count
1 then (Count
0, Count
0) else ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`quot` Vector Word32 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word32
v, ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`rem` Vector Word32 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word32
v) Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
1)
          prefix :: Vector Word32
prefix    = Int -> Vector Word32 -> Vector Word32
forall a. Int -> Vector a -> Vector a
DV.take (Count -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q) Vector Word32
v
          maybeElem :: Elem (Vector Word32)
maybeElem = Vector Word32
v Vector Word32 -> Position -> Elem (Vector Word32)
forall v. AtIndex v => v -> Position -> Elem v
!!! Count -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q
  {-# INLINABLE rank1 #-}

instance Rank1 (DV.Vector Word64) where
  rank1 :: Vector Count -> Count -> Count
rank1 Vector Count
v Count
p = Vector Count -> Count
forall v. PopCount1 v => v -> Count
popCount1 Vector Count
prefix Count -> Count -> Count
forall a. Num a => a -> a -> a
+ if Count
r Count -> Count -> Bool
forall a. Eq a => a -> a -> Bool
== Count
0 then Count
0 else (Count -> Count -> Count
forall v. Rank1 v => v -> Count -> Count
`rank1` Count
r) Count
maybeElem
    where (Count
q, Count
r)    = if Count
p Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
< Count
1 then (Count
0, Count
0) else ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`quot` Vector Count -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Count
v, ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`rem` Vector Count -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Count
v) Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
1)
          prefix :: Vector Count
prefix    = Int -> Vector Count -> Vector Count
forall a. Int -> Vector a -> Vector a
DV.take (Count -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q) Vector Count
v
          maybeElem :: Elem (Vector Count)
maybeElem = Vector Count
v Vector Count -> Position -> Elem (Vector Count)
forall v. AtIndex v => v -> Position -> Elem v
!!! Count -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q
  {-# INLINABLE rank1 #-}

instance Rank1 (DVS.Vector Word8) where
  rank1 :: Vector Word8 -> Count -> Count
rank1 Vector Word8
v Count
p = Vector Word8 -> Count
forall v. PopCount1 v => v -> Count
popCount1 Vector Word8
prefix Count -> Count -> Count
forall a. Num a => a -> a -> a
+ if Count
r Count -> Count -> Bool
forall a. Eq a => a -> a -> Bool
== Count
0 then Count
0 else (Word8 -> Count -> Count
forall v. Rank1 v => v -> Count -> Count
`rank1` Count
r) Word8
maybeElem
    where (Count
q, Count
r)    = if Count
p Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
< Count
1 then (Count
0, Count
0) else ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`quot` Vector Word8 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word8
v, ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`rem` Vector Word8 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word8
v) Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
1)
          prefix :: Vector Word8
prefix    = Int -> Vector Word8 -> Vector Word8
forall a. Storable a => Int -> Vector a -> Vector a
DVS.take (Count -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q) Vector Word8
v
          maybeElem :: Elem (Vector Word8)
maybeElem = Vector Word8
v Vector Word8 -> Position -> Elem (Vector Word8)
forall v. AtIndex v => v -> Position -> Elem v
!!! Count -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q
  {-# INLINABLE rank1 #-}

instance Rank1 (DVS.Vector Word16) where
  rank1 :: Vector Word16 -> Count -> Count
rank1 Vector Word16
v Count
p = Vector Word16 -> Count
forall v. PopCount1 v => v -> Count
popCount1 Vector Word16
prefix Count -> Count -> Count
forall a. Num a => a -> a -> a
+ if Count
r Count -> Count -> Bool
forall a. Eq a => a -> a -> Bool
== Count
0 then Count
0 else (Word16 -> Count -> Count
forall v. Rank1 v => v -> Count -> Count
`rank1` Count
r) Word16
maybeElem
    where (Count
q, Count
r)    = if Count
p Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
< Count
1 then (Count
0, Count
0) else ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`quot` Vector Word16 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word16
v, ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`rem` Vector Word16 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word16
v) Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
1)
          prefix :: Vector Word16
prefix    = Int -> Vector Word16 -> Vector Word16
forall a. Storable a => Int -> Vector a -> Vector a
DVS.take (Count -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q) Vector Word16
v
          maybeElem :: Elem (Vector Word16)
maybeElem = Vector Word16
v Vector Word16 -> Position -> Elem (Vector Word16)
forall v. AtIndex v => v -> Position -> Elem v
!!! Count -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q
  {-# INLINABLE rank1 #-}

instance Rank1 (DVS.Vector Word32) where
  rank1 :: Vector Word32 -> Count -> Count
rank1 Vector Word32
v Count
p = Vector Word32 -> Count
forall v. PopCount1 v => v -> Count
popCount1 Vector Word32
prefix Count -> Count -> Count
forall a. Num a => a -> a -> a
+ if Count
r Count -> Count -> Bool
forall a. Eq a => a -> a -> Bool
== Count
0 then Count
0 else (Word32 -> Count -> Count
forall v. Rank1 v => v -> Count -> Count
`rank1` Count
r) Word32
maybeElem
    where (Count
q, Count
r)    = if Count
p Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
< Count
1 then (Count
0, Count
0) else ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`quot` Vector Word32 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word32
v, ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`rem` Vector Word32 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word32
v) Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
1)
          prefix :: Vector Word32
prefix    = Int -> Vector Word32 -> Vector Word32
forall a. Storable a => Int -> Vector a -> Vector a
DVS.take (Count -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q) Vector Word32
v
          maybeElem :: Elem (Vector Word32)
maybeElem = Vector Word32
v Vector Word32 -> Position -> Elem (Vector Word32)
forall v. AtIndex v => v -> Position -> Elem v
!!! Count -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q
  {-# INLINABLE rank1 #-}

instance Rank1 (DVS.Vector Word64) where
  rank1 :: Vector Count -> Count -> Count
rank1 Vector Count
v Count
p = Vector Count -> Count
forall v. PopCount1 v => v -> Count
popCount1 Vector Count
prefix Count -> Count -> Count
forall a. Num a => a -> a -> a
+ if Count
r Count -> Count -> Bool
forall a. Eq a => a -> a -> Bool
== Count
0 then Count
0 else (Count -> Count -> Count
forall v. Rank1 v => v -> Count -> Count
`rank1` Count
r) Count
maybeElem
    where (Count
q, Count
r)    = if Count
p Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
< Count
1 then (Count
0, Count
0) else ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`quot` Vector Count -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Count
v, ((Count
p Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
1) Count -> Count -> Count
forall a. Integral a => a -> a -> a
`rem` Vector Count -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Count
v) Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
1)
          prefix :: Vector Count
prefix    = Int -> Vector Count -> Vector Count
forall a. Storable a => Int -> Vector a -> Vector a
DVS.take (Count -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q) Vector Count
v
          maybeElem :: Elem (Vector Count)
maybeElem = Vector Count
v Vector Count -> Position -> Elem (Vector Count)
forall v. AtIndex v => v -> Position -> Elem v
!!! Count -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Count
q
  {-# INLINABLE rank1 #-}