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