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

module HaskellWorks.Data.RankSelect.Base.Select1
    ( Select1(..)
    ) 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.Int.Narrow
import HaskellWorks.Data.Positioning
import HaskellWorks.Data.RankSelect.Base.Internal
import Prelude

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

class Select1 v where
  select1 :: v -> Count -> Count

deriving instance Select1 a => Select1 (BitShown a)

-- TODO: Implement NOT interms of select for word-16
instance Select1 Word8 where
  select1 :: Word8 -> Count -> Count
select1 Word8
_ Count
0 = Count
0
  select1 Word8
v Count
p = Word16 -> Count -> Count
forall v. Select1 v => v -> Count -> Count
select1 (Word8 -> Word16
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word8
v :: Word16) Count
p
  {-# INLINE select1 #-}

-- TODO: Remove redundant code to optimise
instance Select1 Word16 where
  select1 :: Word16 -> Count -> Count
select1 Word16
_ Count
0 = Count
0
  select1 Word16
v Count
rn =
    -- Do a normal parallel bit count for a 64-bit integer,
    -- but store all intermediate steps.
    let a :: Word16
a = (Word16
v Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
0x5555) Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
+ ((Word16
v Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>.  Count
1) Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
0x5555)    in
    let b :: Word16
b = (Word16
a Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
0x3333) Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
+ ((Word16
a Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>.  Count
2) Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
0x3333)    in
    let c :: Word16
c = (Word16
b Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
0x0f0f) Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
+ ((Word16
b Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>.  Count
4) Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
0x0f0f)    in
    let d :: Word16
d = (Word16
c Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
0x00ff) Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
+ ((Word16
c Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>.  Count
8) Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
0x00ff)    in
    -- Now do branchless select!
    let r0 :: Word16
r0 = Word16
d Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
+ Word16
1 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Count -> Narrowed16 Count
forall a. Narrow16 a => a -> Narrowed16 a
narrow16 Count
rn                                                in
    let s0 :: Word16
s0 = Word16
64 :: Word16                                                       in
    let t0 :: Word16
t0 = (Word16
d Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Count
32) Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
+ (Word16
d Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Count
48)                                            in
    let s1 :: Word16
s1 = Word16
s0 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- ((Word16
t0 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Word16
r0) Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
256) Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Count
3                                     in
    let r1 :: Word16
r1 = Word16
r0 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- (Word16
t0 Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. ((Word16
t0 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Word16
r0) Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Count
8))                                    in
    let t1 :: Word16
t1 =      (Word16
d Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Word16 -> Count
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word16
s1 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Word16
16)) Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
0xff                       in
    let s2 :: Word16
s2 = Word16
s1 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- ((Word16
t1 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Word16
r1) Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
256) Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Count
4                                     in
    let r2 :: Word16
r2 = Word16
r1 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- (Word16
t1 Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. ((Word16
t1 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Word16
r1) Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Count
8))                                    in
    let t2 :: Word16
t2 =      (Word16
c Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Word16 -> Count
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word16
s2 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Word16
8))  Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
0xf                        in
    let s3 :: Word16
s3 = Word16
s2 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- ((Word16
t2 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Word16
r2) Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
256) Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Count
5                                     in
    let r3 :: Word16
r3 = Word16
r2 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- (Word16
t2 Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. ((Word16
t2 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Word16
r2) Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Count
8))                                    in
    let t3 :: Word16
t3 =      (Word16
b Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Word16 -> Count
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word16
s3 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Word16
4))  Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
0x7                        in
    let s4 :: Word16
s4 = Word16
s3 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- ((Word16
t3 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Word16
r3) Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
256) Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Count
6                                     in
    let r4 :: Word16
r4 = Word16
r3 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- (Word16
t3 Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. ((Word16
t3 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Word16
r3) Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Count
8))                                    in
    let t4 :: Word16
t4 =      (Word16
a Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Word16 -> Count
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word16
s4 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Word16
2))  Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
0x3                        in
    let s5 :: Word16
s5 = Word16
s4 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- ((Word16
t4 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Word16
r4) Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
256) Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Count
7                                     in
    let r5 :: Word16
r5 = Word16
r4 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- (Word16
t4 Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. ((Word16
t4 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Word16
r4) Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Count
8))                                    in
    let t5 :: Word16
t5 =      (Word16
v Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Word16 -> Count
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word16
s5 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Word16
1))  Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
0x1                        in
    let s6 :: Word16
s6 = Word16
s5 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- ((Word16
t5 Word16 -> Word16 -> Word16
forall a. Num a => a -> a -> a
- Word16
r5) Word16 -> Word16 -> Word16
forall a. BitWise a => a -> a -> a
.&. Word16
256) Word16 -> Count -> Word16
forall a. Shift a => a -> Count -> a
.>. Count
8                                     in
    Word16 -> Count
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word16
s6
  {-# INLINE select1 #-}

instance Select1 Word32 where
  select1 :: Word32 -> Count -> Count
select1 = Word32 -> Count -> Count
select1Word32
  {-# INLINE select1 #-}

instance Select1 Word64 where
  select1 :: Count -> Count -> Count
select1 = Count -> Count -> Count
select1Word64
  {-# INLINE select1 #-}

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

instance Select1 [Word8] where
  select1 :: [Word8] -> Count -> Count
select1 [Word8]
v Count
c = [Word8] -> Count -> Count -> Count
go [Word8]
v Count
c Count
0
    where go :: [Word8] -> Count -> Count -> Count
          go :: [Word8] -> Count -> Count -> Count
go [Word8]
_ Count
0  Count
acc = Count
acc
          go [Word8]
u Count
d Count
acc = let w :: Word8
w = [Word8] -> Word8
forall a. [a] -> a
head [Word8]
u in
            case Word8 -> Count
forall v. PopCount1 v => v -> Count
popCount1 Word8
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word8 -> Count -> Count
forall v. Select1 v => v -> Count -> Count
select1 Word8
w Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
acc
              Count
pc -> [Word8] -> Count -> Count -> Count
go ([Word8] -> [Word8]
forall a. [a] -> [a]
tail [Word8]
u) (Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
pc) (Count
acc Count -> Count -> Count
forall a. Num a => a -> a -> a
+ [Word8] -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize [Word8]
u)
  {-# INLINE select1 #-}

instance Select1 [Word16] where
  select1 :: [Word16] -> Count -> Count
select1 [Word16]
v Count
c = [Word16] -> Count -> Count -> Count
go [Word16]
v Count
c Count
0
    where go :: [Word16] -> Count -> Count -> Count
          go :: [Word16] -> Count -> Count -> Count
go [Word16]
_ Count
0  Count
acc = Count
acc
          go [Word16]
u Count
d Count
acc = let w :: Word16
w = [Word16] -> Word16
forall a. [a] -> a
head [Word16]
u in
            case Word16 -> Count
forall v. PopCount1 v => v -> Count
popCount1 Word16
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word16 -> Count -> Count
forall v. Select1 v => v -> Count -> Count
select1 Word16
w Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
acc
              Count
pc -> [Word16] -> Count -> Count -> Count
go ([Word16] -> [Word16]
forall a. [a] -> [a]
tail [Word16]
u) (Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
pc) (Count
acc Count -> Count -> Count
forall a. Num a => a -> a -> a
+ [Word16] -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize [Word16]
u)
  {-# INLINE select1 #-}

instance Select1 [Word32] where
  select1 :: [Word32] -> Count -> Count
select1 [Word32]
v Count
c = [Word32] -> Count -> Count -> Count
go [Word32]
v Count
c Count
0
    where go :: [Word32] -> Count -> Count -> Count
          go :: [Word32] -> Count -> Count -> Count
go [Word32]
_ Count
0  Count
acc = Count
acc
          go [Word32]
u Count
d Count
acc = let w :: Word32
w = [Word32] -> Word32
forall a. [a] -> a
head [Word32]
u in
            case Word32 -> Count
forall v. PopCount1 v => v -> Count
popCount1 Word32
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word32 -> Count -> Count
forall v. Select1 v => v -> Count -> Count
select1 Word32
w Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
acc
              Count
pc -> [Word32] -> Count -> Count -> Count
go ([Word32] -> [Word32]
forall a. [a] -> [a]
tail [Word32]
u) (Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
pc) (Count
acc Count -> Count -> Count
forall a. Num a => a -> a -> a
+ [Word32] -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize [Word32]
u)
  {-# INLINE select1 #-}

instance Select1 [Word64] where
  select1 :: [Count] -> Count -> Count
select1 [Count]
v Count
c = [Count] -> Count -> Count -> Count
go [Count]
v Count
c Count
0
    where go :: [Word64] -> Count -> Count -> Count
          go :: [Count] -> Count -> Count -> Count
go [Count]
_ Count
0  Count
acc = Count
acc
          go [Count]
u Count
d Count
acc = let w :: Count
w = [Count] -> Count
forall a. [a] -> a
head [Count]
u in
            case Count -> Count
forall v. PopCount1 v => v -> Count
popCount1 Count
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Count -> Count -> Count
forall v. Select1 v => v -> Count -> Count
select1 Count
w Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
acc
              Count
pc -> [Count] -> Count -> Count -> Count
go ([Count] -> [Count]
forall a. [a] -> [a]
tail [Count]
u) (Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
pc) (Count
acc Count -> Count -> Count
forall a. Num a => a -> a -> a
+ [Count] -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize [Count]
u)
  {-# INLINE select1 #-}

instance Select1 (DVS.Vector Word8) where
  select1 :: Vector Word8 -> Count -> Count
select1 Vector Word8
v Count
c = Int64 -> Count -> Count -> Count
go Int64
0 Count
c Count
0
    where go :: Int64 -> Count -> Count -> Count
go Int64
_ Count
0  Count
acc = Count
acc
          go Int64
n Count
d Count
acc = let w :: Elem (Vector Word8)
w = (Vector Word8
v Vector Word8 -> Int64 -> Elem (Vector Word8)
forall v. AtIndex v => v -> Int64 -> Elem v
!!! Int64
n) in
            case Word8 -> Count
forall v. PopCount1 v => v -> Count
popCount1 Word8
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word8 -> Count -> Count
forall v. Select1 v => v -> Count -> Count
select1 Word8
w Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
acc
              Count
pc -> Int64 -> Count -> Count -> Count
go (Int64
n Int64 -> Int64 -> Int64
forall a. Num a => a -> a -> a
+ Int64
1) (Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
pc) (Count
acc Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Vector Word8 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word8
v)
  {-# INLINE select1 #-}

instance Select1 (DVS.Vector Word16) where
  select1 :: Vector Word16 -> Count -> Count
select1 Vector Word16
v Count
c = Int64 -> Count -> Count -> Count
go Int64
0 Count
c Count
0
    where go :: Int64 -> Count -> Count -> Count
go Int64
_ Count
0  Count
acc = Count
acc
          go Int64
n Count
d Count
acc = let w :: Elem (Vector Word16)
w = (Vector Word16
v Vector Word16 -> Int64 -> Elem (Vector Word16)
forall v. AtIndex v => v -> Int64 -> Elem v
!!! Int64
n) in
            case Word16 -> Count
forall v. PopCount1 v => v -> Count
popCount1 Word16
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word16 -> Count -> Count
forall v. Select1 v => v -> Count -> Count
select1 Word16
w Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
acc
              Count
pc -> Int64 -> Count -> Count -> Count
go (Int64
n Int64 -> Int64 -> Int64
forall a. Num a => a -> a -> a
+ Int64
1) (Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
pc) (Count
acc Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Vector Word16 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word16
v)
  {-# INLINE select1 #-}

instance Select1 (DVS.Vector Word32) where
  select1 :: Vector Word32 -> Count -> Count
select1 Vector Word32
v Count
c = Int64 -> Count -> Count -> Count
go Int64
0 Count
c Count
0
    where go :: Int64 -> Count -> Count -> Count
go Int64
_ Count
0  Count
acc = Count
acc
          go Int64
n Count
d Count
acc = let w :: Elem (Vector Word32)
w = (Vector Word32
v Vector Word32 -> Int64 -> Elem (Vector Word32)
forall v. AtIndex v => v -> Int64 -> Elem v
!!! Int64
n) in
            case Word32 -> Count
forall v. PopCount1 v => v -> Count
popCount1 Word32
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word32 -> Count -> Count
forall v. Select1 v => v -> Count -> Count
select1 Word32
w Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
acc
              Count
pc -> Int64 -> Count -> Count -> Count
go (Int64
n Int64 -> Int64 -> Int64
forall a. Num a => a -> a -> a
+ Int64
1) (Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
pc) (Count
acc Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Vector Word32 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word32
v)
  {-# INLINE select1 #-}

instance Select1 (DVS.Vector Word64) where
  select1 :: Vector Count -> Count -> Count
select1 Vector Count
v Count
c = Int64 -> Count -> Count -> Count
go Int64
0 Count
c Count
0
    where go :: Int64 -> Count -> Count -> Count
go Int64
_ Count
0  Count
acc = Count
acc
          go Int64
n Count
d Count
acc = let w :: Elem (Vector Count)
w = (Vector Count
v Vector Count -> Int64 -> Elem (Vector Count)
forall v. AtIndex v => v -> Int64 -> Elem v
!!! Int64
n) in
            case Count -> Count
forall v. PopCount1 v => v -> Count
popCount1 Count
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Count -> Count -> Count
forall v. Select1 v => v -> Count -> Count
select1 Count
w Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
acc
              Count
pc -> Int64 -> Count -> Count -> Count
go (Int64
n Int64 -> Int64 -> Int64
forall a. Num a => a -> a -> a
+ Int64
1) (Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
pc) (Count
acc Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Vector Count -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Count
v)
  {-# INLINE select1 #-}

instance Select1 (DV.Vector Word8) where
  select1 :: Vector Word8 -> Count -> Count
select1 Vector Word8
v Count
c = Int64 -> Count -> Count -> Count
go Int64
0 Count
c Count
0
    where go :: Int64 -> Count -> Count -> Count
go Int64
_ Count
0  Count
acc = Count
acc
          go Int64
n Count
d Count
acc = let w :: Elem (Vector Word8)
w = (Vector Word8
v Vector Word8 -> Int64 -> Elem (Vector Word8)
forall v. AtIndex v => v -> Int64 -> Elem v
!!! Int64
n) in
            case Word8 -> Count
forall v. PopCount1 v => v -> Count
popCount1 Word8
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word8 -> Count -> Count
forall v. Select1 v => v -> Count -> Count
select1 Word8
w Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
acc
              Count
pc -> Int64 -> Count -> Count -> Count
go (Int64
n Int64 -> Int64 -> Int64
forall a. Num a => a -> a -> a
+ Int64
1) (Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
pc) (Count
acc Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Vector Word8 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word8
v)
  {-# INLINE select1 #-}

instance Select1 (DV.Vector Word16) where
  select1 :: Vector Word16 -> Count -> Count
select1 Vector Word16
v Count
c = Int64 -> Count -> Count -> Count
go Int64
0 Count
c Count
0
    where go :: Int64 -> Count -> Count -> Count
go Int64
_ Count
0  Count
acc = Count
acc
          go Int64
n Count
d Count
acc = let w :: Elem (Vector Word16)
w = (Vector Word16
v Vector Word16 -> Int64 -> Elem (Vector Word16)
forall v. AtIndex v => v -> Int64 -> Elem v
!!! Int64
n) in
            case Word16 -> Count
forall v. PopCount1 v => v -> Count
popCount1 Word16
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word16 -> Count -> Count
forall v. Select1 v => v -> Count -> Count
select1 Word16
w Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
acc
              Count
pc -> Int64 -> Count -> Count -> Count
go (Int64
n Int64 -> Int64 -> Int64
forall a. Num a => a -> a -> a
+ Int64
1) (Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
pc) (Count
acc Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Vector Word16 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word16
v)
  {-# INLINE select1 #-}

instance Select1 (DV.Vector Word32) where
  select1 :: Vector Word32 -> Count -> Count
select1 Vector Word32
v Count
c = Int64 -> Count -> Count -> Count
go Int64
0 Count
c Count
0
    where go :: Int64 -> Count -> Count -> Count
go Int64
_ Count
0  Count
acc = Count
acc
          go Int64
n Count
d Count
acc = let w :: Elem (Vector Word32)
w = (Vector Word32
v Vector Word32 -> Int64 -> Elem (Vector Word32)
forall v. AtIndex v => v -> Int64 -> Elem v
!!! Int64
n) in
            case Word32 -> Count
forall v. PopCount1 v => v -> Count
popCount1 Word32
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word32 -> Count -> Count
forall v. Select1 v => v -> Count -> Count
select1 Word32
w Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
acc
              Count
pc -> Int64 -> Count -> Count -> Count
go (Int64
n Int64 -> Int64 -> Int64
forall a. Num a => a -> a -> a
+ Int64
1) (Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
pc) (Count
acc Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Vector Word32 -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Word32
v)
  {-# INLINE select1 #-}

instance Select1 (DV.Vector Word64) where
  select1 :: Vector Count -> Count -> Count
select1 Vector Count
v Count
c = Int64 -> Count -> Count -> Count
go Int64
0 Count
c Count
0
    where go :: Int64 -> Count -> Count -> Count
go Int64
_ Count
0  Count
acc = Count
acc
          go Int64
n Count
d Count
acc = let w :: Elem (Vector Count)
w = (Vector Count
v Vector Count -> Int64 -> Elem (Vector Count)
forall v. AtIndex v => v -> Int64 -> Elem v
!!! Int64
n) in
            case Count -> Count
forall v. PopCount1 v => v -> Count
popCount1 Count
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Count -> Count -> Count
forall v. Select1 v => v -> Count -> Count
select1 Count
w Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Count
acc
              Count
pc -> Int64 -> Count -> Count -> Count
go (Int64
n Int64 -> Int64 -> Int64
forall a. Num a => a -> a -> a
+ Int64
1) (Count
d Count -> Count -> Count
forall a. Num a => a -> a -> a
- Count
pc) (Count
acc Count -> Count -> Count
forall a. Num a => a -> a -> a
+ Vector Count -> Count
forall v. ElemFixedBitSize v => v -> Count
elemFixedBitSize Vector Count
v)
  {-# INLINE select1 #-}