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

module HaskellWorks.Data.RankSelect.Base.Select0
    ( Select0(..)
    ) 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.PopCount0
import HaskellWorks.Data.Positioning
import HaskellWorks.Data.RankSelect.Base.Select1

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

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

class Select0 v where
  select0 :: v -> Count -> Count

deriving instance Select0 a => Select0 (BitShown a)

-- TODO: Implement NOT in terms of select for word-16
instance Select0 Word8 where
  select0 :: Word8 -> Count -> Count
select0 Word8
v = Word8 -> Count -> Count
forall v. Select1 v => v -> Count -> Count
select1 (Word8 -> Word8
forall a. BitWise a => a -> a
comp Word8
v)
  {-# INLINABLE select0 #-}

instance Select0 Word16 where
  select0 :: Word16 -> Count -> Count
select0 Word16
v = Word16 -> Count -> Count
forall v. Select1 v => v -> Count -> Count
select1 (Word16 -> Word16
forall a. BitWise a => a -> a
comp Word16
v)
  {-# INLINABLE select0 #-}

instance Select0 Word32 where
  select0 :: Word32 -> Count -> Count
select0 Word32
v = Word32 -> Count -> Count
forall v. Select1 v => v -> Count -> Count
select1 (Word32 -> Word32
forall a. BitWise a => a -> a
comp Word32
v)
  {-# INLINABLE select0 #-}

instance Select0 Word64 where
  select0 :: Count -> Count -> Count
select0 Count
v = Count -> Count -> Count
forall v. Select1 v => v -> Count -> Count
select1 (Count -> Count
forall a. BitWise a => a -> a
comp Count
v)
  {-# INLINABLE select0 #-}

instance Select0 [Bool] where
  select0 :: [Bool] -> Count -> Count
select0 = 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
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 t -> t -> t
forall a. Num a => a -> a -> a
- t
1)
          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
          go a
_ []         t
_ = [Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"Out of range"
  {-# INLINABLE select0 #-}

instance Select0 [Word8] where
  select0 :: [Word8] -> Count -> Count
select0 [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. PopCount0 v => v -> Count
popCount0 Word8
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word8 -> Count -> Count
forall v. Select0 v => v -> Count -> Count
select0 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)
  {-# INLINABLE select0 #-}

instance Select0 [Word16] where
  select0 :: [Word16] -> Count -> Count
select0 [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. PopCount0 v => v -> Count
popCount0 Word16
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word16 -> Count -> Count
forall v. Select0 v => v -> Count -> Count
select0 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)
  {-# INLINABLE select0 #-}

instance Select0 [Word32] where
  select0 :: [Word32] -> Count -> Count
select0 [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. PopCount0 v => v -> Count
popCount0 Word32
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word32 -> Count -> Count
forall v. Select0 v => v -> Count -> Count
select0 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)
  {-# INLINABLE select0 #-}

instance Select0 [Word64] where
  select0 :: [Count] -> Count -> Count
select0 [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. PopCount0 v => v -> Count
popCount0 Count
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Count -> Count -> Count
forall v. Select0 v => v -> Count -> Count
select0 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)
  {-# INLINABLE select0 #-}

instance Select0 (DV.Vector Word8) where
  select0 :: Vector Word8 -> Count -> Count
select0 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. PopCount0 v => v -> Count
popCount0 Word8
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word8 -> Count -> Count
forall v. Select0 v => v -> Count -> Count
select0 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)
  {-# INLINABLE select0 #-}

instance Select0 (DV.Vector Word16) where
  select0 :: Vector Word16 -> Count -> Count
select0 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. PopCount0 v => v -> Count
popCount0 Word16
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word16 -> Count -> Count
forall v. Select0 v => v -> Count -> Count
select0 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)
  {-# INLINABLE select0 #-}

instance Select0 (DV.Vector Word32) where
  select0 :: Vector Word32 -> Count -> Count
select0 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. PopCount0 v => v -> Count
popCount0 Word32
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word32 -> Count -> Count
forall v. Select0 v => v -> Count -> Count
select0 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)
  {-# INLINABLE select0 #-}

instance Select0 (DV.Vector Word64) where
  select0 :: Vector Count -> Count -> Count
select0 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. PopCount0 v => v -> Count
popCount0 Count
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Count -> Count -> Count
forall v. Select0 v => v -> Count -> Count
select0 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)
  {-# INLINABLE select0 #-}

instance Select0 (DVS.Vector Word8) where
  select0 :: Vector Word8 -> Count -> Count
select0 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. PopCount0 v => v -> Count
popCount0 Word8
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word8 -> Count -> Count
forall v. Select0 v => v -> Count -> Count
select0 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)
  {-# INLINABLE select0 #-}

instance Select0 (DVS.Vector Word16) where
  select0 :: Vector Word16 -> Count -> Count
select0 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. PopCount0 v => v -> Count
popCount0 Word16
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word16 -> Count -> Count
forall v. Select0 v => v -> Count -> Count
select0 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)
  {-# INLINABLE select0 #-}

instance Select0 (DVS.Vector Word32) where
  select0 :: Vector Word32 -> Count -> Count
select0 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. PopCount0 v => v -> Count
popCount0 Word32
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Word32 -> Count -> Count
forall v. Select0 v => v -> Count -> Count
select0 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)
  {-# INLINABLE select0 #-}

instance Select0 (DVS.Vector Word64) where
  select0 :: Vector Count -> Count -> Count
select0 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. PopCount0 v => v -> Count
popCount0 Count
w of
              Count
pc | Count
d Count -> Count -> Bool
forall a. Ord a => a -> a -> Bool
<= Count
pc  -> Count -> Count -> Count
forall v. Select0 v => v -> Count -> Count
select0 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)
  {-# INLINABLE select0 #-}