{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MultiWayIf   #-}

module HaskellWorks.Data.RankSelect.CsPoppy.Internal.Lookup where

import Data.Word
import HaskellWorks.Data.AtIndex
import HaskellWorks.Data.Bits.BitWise
import Prelude                        hiding (drop, length, pi, take)

import qualified Data.Vector.Storable as DVS

binarySearchPBounds :: (Word64 -> Bool) -> DVS.Vector Word64 -> Word64 -> Word64 -> Word64
binarySearchPBounds :: (Word64 -> Bool) -> Vector Word64 -> Word64 -> Word64 -> Word64
binarySearchPBounds Word64 -> Bool
p Vector Word64
v = Word64 -> Word64 -> Word64
loop
  where loop :: Word64 -> Word64 -> Word64
        loop :: Word64 -> Word64 -> Word64
loop !Word64
l !Word64
u
          | Word64
u Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word64
l    = Word64
l
          | Bool
otherwise = let e :: Elem (Vector Word64)
e = Vector Word64
v Vector Word64 -> Position -> Elem (Vector Word64)
forall v. AtIndex v => v -> Position -> Elem v
!!! Word64 -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
k in if Word64 -> Bool
p Word64
e then Word64 -> Word64 -> Word64
loop Word64
l Word64
k else Word64 -> Word64 -> Word64
loop (Word64
k Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
1) Word64
u
          where k :: Word64
k = (Word64
u Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
l) Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>. Word64
1
{-# INLINE binarySearchPBounds #-}

lookupLayerMXFrom :: Word64 -> Word64 -> Word64 -> DVS.Vector Word64 -> Word64
lookupLayerMXFrom :: Word64 -> Word64 -> Word64 -> Vector Word64 -> Word64
lookupLayerMXFrom Word64
prev Word64
i Word64
r Vector Word64
v | Word64
i Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
< Vector Word64 -> Word64
forall v. Length v => v -> Word64
length Vector Word64
v =
  let mw :: Word64
mw  = Vector Word64
v Vector Word64 -> Position -> Elem (Vector Word64)
forall v. AtIndex v => v -> Position -> Elem v
!!! Word64 -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
i                      :: Word64
      mx :: Word64
mx  =      ( Word64
mw Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x00000000ffffffff        ) :: Word64
  in if Word64
r Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word64
mx
    then Word64
prev
    else Word64 -> Word64 -> Word64 -> Vector Word64 -> Word64
lookupLayerMXFrom Word64
i (Word64
i Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
1) Word64
r Vector Word64
v
lookupLayerMXFrom Word64
prev Word64
_ Word64
_ Vector Word64
_ = Word64
prev
{-# INLINE lookupLayerMXFrom #-}

lookupLayerMFrom1 :: Word64 -> Word64 -> Word64 -> DVS.Vector Word64 -> (Word64, Word64)
lookupLayerMFrom1 :: Word64 -> Word64 -> Word64 -> Vector Word64 -> (Word64, Word64)
lookupLayerMFrom1 Word64
i Word64
_ Word64
r Vector Word64
v
  | Word64
r Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word64
mx   = [Char] -> (Word64, Word64)
forall a. HasCallStack => [Char] -> a
error [Char]
"This shouldn't happen"
  | Word64
r Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word64
ma   = (Word64
mx, Word64
j Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
4    )
  | Word64
r Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word64
mb   = (Word64
ma, Word64
j Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
4 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
1)
  | Word64
r Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word64
mc   = (Word64
mb, Word64
j Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
4 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
2)
  | Bool
otherwise = (Word64
mc, Word64
j Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
4 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
3)
  where j :: Word64
j   = Word64 -> Word64 -> Word64 -> Vector Word64 -> Word64
lookupLayerMXFrom Word64
0 Word64
i Word64
r Vector Word64
v
        mw :: Word64
mw  = Vector Word64
v Vector Word64 -> Position -> Elem (Vector Word64)
forall v. AtIndex v => v -> Position -> Elem v
!!! Word64 -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
j                      :: Word64
        mx :: Word64
mx  =      ( Word64
mw Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x00000000ffffffff        ) :: Word64
        ma :: Word64
ma  = Word64
mx Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ ((Word64
mw Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x000003ff00000000) Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>. Word64
32) :: Word64
        mb :: Word64
mb  = Word64
ma Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ ((Word64
mw Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x000ffc0000000000) Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>. Word64
42) :: Word64
        mc :: Word64
mc  = Word64
mb Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ ((Word64
mw Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x3ff0000000000000) Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>. Word64
52) :: Word64
{-# INLINE lookupLayerMFrom1 #-}

lookupLayerMFrom2 :: Word64 -> Word64 -> Word64 -> DVS.Vector Word64 -> (Word64, Word64)
lookupLayerMFrom2 :: Word64 -> Word64 -> Word64 -> Vector Word64 -> (Word64, Word64)
lookupLayerMFrom2 Word64
i Word64
j Word64
r Vector Word64
v =
  let cmp :: Word64 -> Bool
cmp Word64
w = (Word64
r Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
- Word64
1) Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
< (Word64
w Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0xffffffff)
      !k :: Word64
k  = ((Word64 -> Bool) -> Vector Word64 -> Word64 -> Word64 -> Word64
binarySearchPBounds Word64 -> Bool
cmp Vector Word64
v Word64
i Word64
j Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
- Word64
1) Word64 -> Word64 -> Word64
forall a. Ord a => a -> a -> a
`max` Word64
0
      !mw :: Word64
mw = Vector Word64
v Vector Word64 -> Position -> Elem (Vector Word64)
forall v. AtIndex v => v -> Position -> Elem v
!!! Word64 -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
k                      :: Word64
      !mx :: Word64
mx =      ( Word64
mw Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x00000000ffffffff        ) :: Word64
      !ma :: Word64
ma = Word64
mx Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ ((Word64
mw Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x000003ff00000000) Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>. Word64
32) :: Word64
      !mb :: Word64
mb = Word64
ma Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ ((Word64
mw Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x000ffc0000000000) Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>. Word64
42) :: Word64
      !mc :: Word64
mc = Word64
mb Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ ((Word64
mw Word64 -> Word64 -> Word64
forall a. BitWise a => a -> a -> a
.&. Word64
0x3ff0000000000000) Word64 -> Word64 -> Word64
forall a. Shift a => a -> Word64 -> a
.>. Word64
52) :: Word64
  in if
    | Word64
r Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word64
mx   -> (Word64
0 , Word64
0        )
    | Word64
r Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word64
ma   -> (Word64
mx, Word64
k Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
4    )
    | Word64
r Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word64
mb   -> (Word64
ma, Word64
k Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
4 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
1)
    | Word64
r Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word64
mc   -> (Word64
mb, Word64
k Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
4 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
2)
    | Bool
otherwise -> (Word64
mc, Word64
k Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
4 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
3)
{-# INLINE lookupLayerMFrom2 #-}