{-# LANGUAGE BangPatterns          #-}
{-# LANGUAGE DeriveAnyClass        #-}
{-# LANGUAGE DeriveGeneric         #-}
{-# LANGUAGE DuplicateRecordFields #-}
{-# LANGUAGE FlexibleContexts      #-}
{-# LANGUAGE FlexibleInstances     #-}
{-# LANGUAGE InstanceSigs          #-}
{-# LANGUAGE TypeFamilies          #-}

module HaskellWorks.Data.BalancedParens.RangeMin
  ( RangeMin(..)
  , mkRangeMin
  ) where

import Control.DeepSeq
import Data.Int
import GHC.Generics
import HaskellWorks.Data.AtIndex
import HaskellWorks.Data.BalancedParens.BalancedParens
import HaskellWorks.Data.BalancedParens.CloseAt
import HaskellWorks.Data.BalancedParens.Enclose
import HaskellWorks.Data.BalancedParens.FindClose
import HaskellWorks.Data.BalancedParens.FindCloseN
import HaskellWorks.Data.BalancedParens.FindOpen
import HaskellWorks.Data.BalancedParens.FindOpenN
import HaskellWorks.Data.BalancedParens.NewCloseAt
import HaskellWorks.Data.BalancedParens.OpenAt
import HaskellWorks.Data.Bits.AllExcess.AllExcess1
import HaskellWorks.Data.Bits.BitLength
import HaskellWorks.Data.Bits.BitWise
import HaskellWorks.Data.Excess.MinExcess
import HaskellWorks.Data.Excess.MinExcess1
import HaskellWorks.Data.Positioning
import HaskellWorks.Data.RankSelect.Base.Rank0
import HaskellWorks.Data.RankSelect.Base.Rank1
import HaskellWorks.Data.Vector.AsVector64
import Prelude                                         hiding (length)

import qualified Data.Vector.Storable                                      as DVS
import qualified HaskellWorks.Data.BalancedParens.Internal.Vector.Storable as DVS

data RangeMin a = RangeMin
  { RangeMin a -> a
rangeMinBP       :: !a
  , RangeMin a -> Vector Int8
rangeMinL0Min    :: !(DVS.Vector Int8)
  , RangeMin a -> Vector Int8
rangeMinL0Excess :: !(DVS.Vector Int8)
  , RangeMin a -> Vector Int16
rangeMinL1Min    :: !(DVS.Vector Int16)
  , RangeMin a -> Vector Int16
rangeMinL1Excess :: !(DVS.Vector Int16)
  , RangeMin a -> Vector Int16
rangeMinL2Min    :: !(DVS.Vector Int16)
  , RangeMin a -> Vector Int16
rangeMinL2Excess :: !(DVS.Vector Int16)
  } deriving (RangeMin a -> RangeMin a -> Bool
(RangeMin a -> RangeMin a -> Bool)
-> (RangeMin a -> RangeMin a -> Bool) -> Eq (RangeMin a)
forall a. Eq a => RangeMin a -> RangeMin a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: RangeMin a -> RangeMin a -> Bool
$c/= :: forall a. Eq a => RangeMin a -> RangeMin a -> Bool
== :: RangeMin a -> RangeMin a -> Bool
$c== :: forall a. Eq a => RangeMin a -> RangeMin a -> Bool
Eq, Int -> RangeMin a -> ShowS
[RangeMin a] -> ShowS
RangeMin a -> String
(Int -> RangeMin a -> ShowS)
-> (RangeMin a -> String)
-> ([RangeMin a] -> ShowS)
-> Show (RangeMin a)
forall a. Show a => Int -> RangeMin a -> ShowS
forall a. Show a => [RangeMin a] -> ShowS
forall a. Show a => RangeMin a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [RangeMin a] -> ShowS
$cshowList :: forall a. Show a => [RangeMin a] -> ShowS
show :: RangeMin a -> String
$cshow :: forall a. Show a => RangeMin a -> String
showsPrec :: Int -> RangeMin a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> RangeMin a -> ShowS
Show, RangeMin a -> ()
(RangeMin a -> ()) -> NFData (RangeMin a)
forall a. NFData a => RangeMin a -> ()
forall a. (a -> ()) -> NFData a
rnf :: RangeMin a -> ()
$crnf :: forall a. NFData a => RangeMin a -> ()
NFData, (forall x. RangeMin a -> Rep (RangeMin a) x)
-> (forall x. Rep (RangeMin a) x -> RangeMin a)
-> Generic (RangeMin a)
forall x. Rep (RangeMin a) x -> RangeMin a
forall x. RangeMin a -> Rep (RangeMin a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (RangeMin a) x -> RangeMin a
forall a x. RangeMin a -> Rep (RangeMin a) x
$cto :: forall a x. Rep (RangeMin a) x -> RangeMin a
$cfrom :: forall a x. RangeMin a -> Rep (RangeMin a) x
Generic)

factorL0 :: Integral a => a
factorL0 :: a
factorL0 = a
1
{-# INLINE factorL0 #-}

factorL1 :: Integral a => a
factorL1 :: a
factorL1 = a
32
{-# INLINE factorL1 #-}

factorL2 :: Integral a => a
factorL2 :: a
factorL2 = a
32
{-# INLINE factorL2 #-}

pageSizeL0 :: Integral a => a
pageSizeL0 :: a
pageSizeL0 = a
forall a. Integral a => a
factorL0
{-# INLINE pageSizeL0 #-}

pageSizeL1 :: Integral a => a
pageSizeL1 :: a
pageSizeL1 = a
forall a. Integral a => a
pageSizeL0 a -> a -> a
forall a. Num a => a -> a -> a
* a
forall a. Integral a => a
factorL1
{-# INLINE pageSizeL1 #-}

pageSizeL2 :: Integral a => a
pageSizeL2 :: a
pageSizeL2 = a
forall a. Integral a => a
pageSizeL1 a -> a -> a
forall a. Num a => a -> a -> a
* a
forall a. Integral a => a
factorL2
{-# INLINE pageSizeL2 #-}

mkRangeMin :: AsVector64 a => a -> RangeMin a
mkRangeMin :: a -> RangeMin a
mkRangeMin a
bp = RangeMin :: forall a.
a
-> Vector Int8
-> Vector Int8
-> Vector Int16
-> Vector Int16
-> Vector Int16
-> Vector Int16
-> RangeMin a
RangeMin
  { $sel:rangeMinBP:RangeMin :: a
rangeMinBP       = a
bp
  , $sel:rangeMinL0Min:RangeMin :: Vector Int8
rangeMinL0Min    = Vector Int8
rmL0Min
  , $sel:rangeMinL0Excess:RangeMin :: Vector Int8
rangeMinL0Excess = Vector Int16 -> Vector Int8
forall a b.
(Storable a, Integral a, Storable b, Num b) =>
Vector a -> Vector b
DVS.reword Vector Int16
rmL0Excess
  , $sel:rangeMinL1Min:RangeMin :: Vector Int16
rangeMinL1Min    = Vector Int16
rmL1Min
  , $sel:rangeMinL1Excess:RangeMin :: Vector Int16
rangeMinL1Excess = Vector Int16 -> Vector Int16
forall a b.
(Storable a, Integral a, Storable b, Num b) =>
Vector a -> Vector b
DVS.reword Vector Int16
rmL1Excess
  , $sel:rangeMinL2Min:RangeMin :: Vector Int16
rangeMinL2Min    = Vector Int16
rmL2Min
  , $sel:rangeMinL2Excess:RangeMin :: Vector Int16
rangeMinL2Excess = Vector Int16
rmL2Excess
  }
  where bpv :: Vector Word64
bpv           = a -> Vector Word64
forall a. AsVector64 a => a -> Vector Word64
asVector64 a
bp
        lenBP :: Int
lenBP         = Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Word64 -> Word64
forall v. Length v => v -> Word64
length Vector Word64
bpv) :: Int
        lenL0 :: Int
lenL0         = Int
lenBP
        lenL1 :: Int
lenL1         = (Vector Int8 -> Int
forall a. Storable a => Vector a -> Int
DVS.length Vector Int8
rmL0Min Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
forall a. Integral a => a
pageSizeL1) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 :: Int
        lenL2 :: Int
lenL2         = (Vector Int8 -> Int
forall a. Storable a => Vector a -> Int
DVS.length Vector Int8
rmL0Min Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
forall a. Integral a => a
pageSizeL2) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 :: Int
        allMinL0 :: Vector MinExcess
allMinL0      = Int -> (Int -> MinExcess) -> Vector MinExcess
forall a. Storable a => Int -> (Int -> a) -> Vector a
DVS.generate Int
lenL0 (\Int
i -> if Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
lenBP then Int -> Int -> MinExcess
MinExcess (-Int
64) (-Int
64) else Word64 -> MinExcess
forall a. MinExcess1 a => a -> MinExcess
minExcess1 (Vector Word64
bpv Vector Word64 -> Position -> Elem (Vector Word64)
forall v. AtIndex v => v -> Position -> Elem v
!!! Int -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
i))
        allMinL1 :: Vector MinExcess
allMinL1      = Int -> (Int -> MinExcess) -> Vector MinExcess
forall a. Storable a => Int -> (Int -> a) -> Vector a
DVS.generate Int
lenL1 (\Int
i -> Vector Word64 -> MinExcess
forall a. MinExcess1 a => a -> MinExcess
minExcess1 (Int -> Int -> Vector Word64 -> Vector Word64
forall a. Storable a => Int -> Int -> Vector a -> Vector a
DVS.dropTake (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
forall a. Integral a => a
pageSizeL1) Int
forall a. Integral a => a
pageSizeL1 Vector Word64
bpv))
        allMinL2 :: Vector MinExcess
allMinL2      = Int -> (Int -> MinExcess) -> Vector MinExcess
forall a. Storable a => Int -> (Int -> a) -> Vector a
DVS.generate Int
lenL2 (\Int
i -> Vector Word64 -> MinExcess
forall a. MinExcess1 a => a -> MinExcess
minExcess1 (Int -> Int -> Vector Word64 -> Vector Word64
forall a. Storable a => Int -> Int -> Vector a -> Vector a
DVS.dropTake (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
forall a. Integral a => a
pageSizeL2) Int
forall a. Integral a => a
pageSizeL2 Vector Word64
bpv))
        -- Note: (0xffffffffffffffc0 :: Int64) = -64
        rmL0Excess :: Vector Int16
rmL0Excess    = Int -> (Int -> Int16) -> Vector Int16
forall a. Storable a => Int -> (Int -> a) -> Vector a
DVS.generate Int
lenL0 (\Int
i -> Int -> Int16
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Word64 -> Int
forall a. AllExcess1 a => a -> Int
allExcess1 (Int -> Int -> Word64 -> Vector Word64 -> Vector Word64
forall a. Storable a => Int -> Int -> a -> Vector a -> Vector a
DVS.pageFill Int
i Int
forall a. Integral a => a
pageSizeL0 Word64
0xffffffffffffffc0 Vector Word64
bpv))) :: DVS.Vector Int16
        rmL1Excess :: Vector Int16
rmL1Excess    = Int -> (Int -> Int16) -> Vector Int16
forall a. Storable a => Int -> (Int -> a) -> Vector a
DVS.generate Int
lenL1 (\Int
i -> Int -> Int16
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Word64 -> Int
forall a. AllExcess1 a => a -> Int
allExcess1 (Int -> Int -> Word64 -> Vector Word64 -> Vector Word64
forall a. Storable a => Int -> Int -> a -> Vector a -> Vector a
DVS.pageFill Int
i Int
forall a. Integral a => a
pageSizeL1 Word64
0xffffffffffffffc0 Vector Word64
bpv))) :: DVS.Vector Int16
        rmL2Excess :: Vector Int16
rmL2Excess    = Int -> (Int -> Int16) -> Vector Int16
forall a. Storable a => Int -> (Int -> a) -> Vector a
DVS.generate Int
lenL2 (\Int
i -> Int -> Int16
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Word64 -> Int
forall a. AllExcess1 a => a -> Int
allExcess1 (Int -> Int -> Word64 -> Vector Word64 -> Vector Word64
forall a. Storable a => Int -> Int -> a -> Vector a -> Vector a
DVS.pageFill Int
i Int
forall a. Integral a => a
pageSizeL2 Word64
0xffffffffffffffc0 Vector Word64
bpv))) :: DVS.Vector Int16
        rmL0Min :: Vector Int8
rmL0Min       = Int -> (Int -> Int8) -> Vector Int8
forall a. Storable a => Int -> (Int -> a) -> Vector a
DVS.generate Int
lenL0 (\Int
i -> let MinExcess Int
minE Int
_ = Vector MinExcess
allMinL0 Vector MinExcess -> Int -> MinExcess
forall a. Storable a => Vector a -> Int -> a
DVS.! Int
i in Int -> Int8
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
minE)
        rmL1Min :: Vector Int16
rmL1Min       = Int -> (Int -> Int16) -> Vector Int16
forall a. Storable a => Int -> (Int -> a) -> Vector a
DVS.generate Int
lenL1 (\Int
i -> let MinExcess Int
minE Int
_ = Vector MinExcess
allMinL1 Vector MinExcess -> Int -> MinExcess
forall a. Storable a => Vector a -> Int -> a
DVS.! Int
i in Int -> Int16
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
minE)
        rmL2Min :: Vector Int16
rmL2Min       = Int -> (Int -> Int16) -> Vector Int16
forall a. Storable a => Int -> (Int -> a) -> Vector a
DVS.generate Int
lenL2 (\Int
i -> let MinExcess Int
minE Int
_ = Vector MinExcess
allMinL2 Vector MinExcess -> Int -> MinExcess
forall a. Storable a => Vector a -> Int -> a
DVS.! Int
i in Int -> Int16
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
minE)

data FindState = FindBP
  | FindL0 | FindFromL0
  | FindL1 | FindFromL1
  | FindL2 | FindFromL2

rm2FindClose  :: (BitLength a, NewCloseAt a) => RangeMin a -> Int -> Count -> FindState -> Maybe Count
rm2FindClose :: RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
rm2FindClose RangeMin a
v Int
s Word64
p FindState
FindBP = if RangeMin a
v RangeMin a -> Word64 -> Bool
forall v. NewCloseAt v => v -> Word64 -> Bool
`newCloseAt` Word64
p
  then if Int
s Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
1
    then Word64 -> Maybe Word64
forall a. a -> Maybe a
Just Word64
p
    else RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
forall a.
(BitLength a, NewCloseAt a) =>
RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
rm2FindClose RangeMin a
v (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) (Word64
p Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
1) FindState
FindFromL0
  else RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
forall a.
(BitLength a, NewCloseAt a) =>
RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
rm2FindClose RangeMin a
v (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (Word64
p Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
1) FindState
FindFromL0
rm2FindClose RangeMin a
v Int
s Word64
p FindState
FindL0 =
  let i :: Word64
i = Word64
p Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`div` Word64
64 in
  let mins :: Vector Int8
mins = RangeMin a -> Vector Int8
forall a. RangeMin a -> Vector Int8
rangeMinL0Min RangeMin a
v in
  let minE :: Int
minE = Int8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Int8
mins Vector Int8 -> Position -> Elem (Vector Int8)
forall v. AtIndex v => v -> Position -> Elem v
!!! Word64 -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
i) :: Int in
  if Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
minE Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0
    then RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
forall a.
(BitLength a, NewCloseAt a) =>
RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
rm2FindClose RangeMin a
v Int
s Word64
p FindState
FindBP
    else if RangeMin a
v RangeMin a -> Word64 -> Bool
forall v. NewCloseAt v => v -> Word64 -> Bool
`newCloseAt` Word64
p Bool -> Bool -> Bool
&& Int
s Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
1
      then Word64 -> Maybe Word64
forall a. a -> Maybe a
Just Word64
p
      else  let excesses :: Vector Int8
excesses  = RangeMin a -> Vector Int8
forall a. RangeMin a -> Vector Int8
rangeMinL0Excess RangeMin a
v in
            let excess :: Int
excess    = Int8 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Int8
excesses Vector Int8 -> Position -> Elem (Vector Int8)
forall v. AtIndex v => v -> Position -> Elem v
!!! Word64 -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
i)  :: Int in
            RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
forall a.
(BitLength a, NewCloseAt a) =>
RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
rm2FindClose RangeMin a
v (Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
excess Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
s)) (Word64
p Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
64) FindState
FindFromL0
rm2FindClose RangeMin a
v Int
s Word64
p FindState
FindL1 =
  let !i :: Word64
i = Word64
p Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`div` (Word64
64 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
forall a. Integral a => a
pageSizeL1) in
  let !mins :: Vector Int16
mins = RangeMin a -> Vector Int16
forall a. RangeMin a -> Vector Int16
rangeMinL1Min RangeMin a
v in
  let !minE :: Int
minE = Int16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Int16
mins Vector Int16 -> Position -> Elem (Vector Int16)
forall v. AtIndex v => v -> Position -> Elem v
!!! Word64 -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
i) :: Int in
  if Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
minE Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0
    then RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
forall a.
(BitLength a, NewCloseAt a) =>
RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
rm2FindClose RangeMin a
v Int
s Word64
p FindState
FindL0
    else if Word64
0 Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word64
p Bool -> Bool -> Bool
&& Word64
p Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
< RangeMin a -> Word64
forall v. BitLength v => v -> Word64
bitLength RangeMin a
v
      then if RangeMin a
v RangeMin a -> Word64 -> Bool
forall v. NewCloseAt v => v -> Word64 -> Bool
`newCloseAt` Word64
p Bool -> Bool -> Bool
&& Int
s Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
1
        then Word64 -> Maybe Word64
forall a. a -> Maybe a
Just Word64
p
        else  let excesses :: Vector Int16
excesses  = RangeMin a -> Vector Int16
forall a. RangeMin a -> Vector Int16
rangeMinL1Excess RangeMin a
v in
              let excess :: Int
excess    = Int16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Int16
excesses Vector Int16 -> Position -> Elem (Vector Int16)
forall v. AtIndex v => v -> Position -> Elem v
!!! Word64 -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
i)  :: Int in
              RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
forall a.
(BitLength a, NewCloseAt a) =>
RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
rm2FindClose RangeMin a
v (Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
excess Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
s)) (Word64
p Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ (Word64
64 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
forall a. Integral a => a
pageSizeL1)) FindState
FindFromL1
      else Maybe Word64
forall a. Maybe a
Nothing
rm2FindClose RangeMin a
v Int
s Word64
p FindState
FindL2 =
  let !i :: Word64
i = Word64
p Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`div` (Word64
64 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
forall a. Integral a => a
pageSizeL2) in
  let !mins :: Vector Int16
mins = RangeMin a -> Vector Int16
forall a. RangeMin a -> Vector Int16
rangeMinL2Min RangeMin a
v in
  let !minE :: Int
minE = Int16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Int16
mins Vector Int16 -> Position -> Elem (Vector Int16)
forall v. AtIndex v => v -> Position -> Elem v
!!! Word64 -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
i) :: Int in
  if Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
minE Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0
    then RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
forall a.
(BitLength a, NewCloseAt a) =>
RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
rm2FindClose RangeMin a
v Int
s Word64
p FindState
FindL1
    else if Word64
0 Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word64
p Bool -> Bool -> Bool
&& Word64
p Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
< RangeMin a -> Word64
forall v. BitLength v => v -> Word64
bitLength RangeMin a
v
      then if RangeMin a
v RangeMin a -> Word64 -> Bool
forall v. NewCloseAt v => v -> Word64 -> Bool
`newCloseAt` Word64
p Bool -> Bool -> Bool
&& Int
s Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
1
        then Word64 -> Maybe Word64
forall a. a -> Maybe a
Just Word64
p
        else  let excesses :: Vector Int16
excesses  = RangeMin a -> Vector Int16
forall a. RangeMin a -> Vector Int16
rangeMinL2Excess RangeMin a
v in
              let excess :: Int
excess    = Int16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Int16
excesses Vector Int16 -> Position -> Elem (Vector Int16)
forall v. AtIndex v => v -> Position -> Elem v
!!! Word64 -> Position
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
i)  :: Int in
              RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
forall a.
(BitLength a, NewCloseAt a) =>
RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
rm2FindClose RangeMin a
v (Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
excess Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
s)) (Word64
p Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ (Word64
64 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
forall a. Integral a => a
pageSizeL2)) FindState
FindFromL2
      else Maybe Word64
forall a. Maybe a
Nothing
rm2FindClose RangeMin a
v Int
s Word64
p FindState
FindFromL0
  | Word64
p Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`mod` Word64
64 Word64 -> Word64 -> Bool
forall a. Eq a => a -> a -> Bool
== Word64
0             = RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
forall a.
(BitLength a, NewCloseAt a) =>
RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
rm2FindClose RangeMin a
v Int
s Word64
p FindState
FindFromL1
  | Word64
0 Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word64
p Bool -> Bool -> Bool
&& Word64
p Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
< RangeMin a -> Word64
forall v. BitLength v => v -> Word64
bitLength RangeMin a
v   = RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
forall a.
(BitLength a, NewCloseAt a) =>
RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
rm2FindClose RangeMin a
v Int
s Word64
p FindState
FindBP
  | Bool
otherwise                   = Maybe Word64
forall a. Maybe a
Nothing
rm2FindClose RangeMin a
v Int
s Word64
p FindState
FindFromL1
  | Word64
p Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`mod` (Word64
64 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
forall a. Integral a => a
pageSizeL1) Word64 -> Word64 -> Bool
forall a. Eq a => a -> a -> Bool
== Word64
0  = if Word64
0 Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word64
p Bool -> Bool -> Bool
&& Word64
p Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
< RangeMin a -> Word64
forall v. BitLength v => v -> Word64
bitLength RangeMin a
v then RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
forall a.
(BitLength a, NewCloseAt a) =>
RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
rm2FindClose RangeMin a
v Int
s Word64
p FindState
FindFromL2 else Maybe Word64
forall a. Maybe a
Nothing
  | Word64
0 Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word64
p Bool -> Bool -> Bool
&& Word64
p Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
< RangeMin a -> Word64
forall v. BitLength v => v -> Word64
bitLength RangeMin a
v       = RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
forall a.
(BitLength a, NewCloseAt a) =>
RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
rm2FindClose RangeMin a
v Int
s Word64
p FindState
FindL0
  | Bool
otherwise                       = Maybe Word64
forall a. Maybe a
Nothing
rm2FindClose RangeMin a
v Int
s Word64
p FindState
FindFromL2
  | Word64
p Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
`mod` (Word64
64 Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
* Word64
forall a. Integral a => a
pageSizeL2) Word64 -> Word64 -> Bool
forall a. Eq a => a -> a -> Bool
== Word64
0  = if Word64
0 Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word64
p Bool -> Bool -> Bool
&& Word64
p Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
< RangeMin a -> Word64
forall v. BitLength v => v -> Word64
bitLength RangeMin a
v then RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
forall a.
(BitLength a, NewCloseAt a) =>
RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
rm2FindClose RangeMin a
v Int
s Word64
p FindState
FindL2 else Maybe Word64
forall a. Maybe a
Nothing
  | Word64
0 Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word64
p Bool -> Bool -> Bool
&& Word64
p Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
< RangeMin a -> Word64
forall v. BitLength v => v -> Word64
bitLength RangeMin a
v       = RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
forall a.
(BitLength a, NewCloseAt a) =>
RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
rm2FindClose RangeMin a
v Int
s Word64
p FindState
FindL1
  | Bool
otherwise                       = Maybe Word64
forall a. Maybe a
Nothing
{-# INLINE rm2FindClose #-}

instance TestBit a => TestBit (RangeMin a) where
  .?. :: RangeMin a -> Position -> Bool
(.?.) = a -> Position -> Bool
forall a. TestBit a => a -> Position -> Bool
(.?.) (a -> Position -> Bool)
-> (RangeMin a -> a) -> RangeMin a -> Position -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RangeMin a -> a
forall a. RangeMin a -> a
rangeMinBP
  {-# INLINE (.?.) #-}

instance Rank1 a => Rank1 (RangeMin a) where
  rank1 :: RangeMin a -> Word64 -> Word64
rank1 = a -> Word64 -> Word64
forall v. Rank1 v => v -> Word64 -> Word64
rank1 (a -> Word64 -> Word64)
-> (RangeMin a -> a) -> RangeMin a -> Word64 -> Word64
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RangeMin a -> a
forall a. RangeMin a -> a
rangeMinBP
  {-# INLINE rank1 #-}

instance Rank0 a => Rank0 (RangeMin a) where
  rank0 :: RangeMin a -> Word64 -> Word64
rank0 = a -> Word64 -> Word64
forall v. Rank0 v => v -> Word64 -> Word64
rank0 (a -> Word64 -> Word64)
-> (RangeMin a -> a) -> RangeMin a -> Word64 -> Word64
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RangeMin a -> a
forall a. RangeMin a -> a
rangeMinBP
  {-# INLINE rank0 #-}

instance BitLength a => BitLength (RangeMin a) where
  bitLength :: RangeMin a -> Word64
bitLength = a -> Word64
forall v. BitLength v => v -> Word64
bitLength (a -> Word64) -> (RangeMin a -> a) -> RangeMin a -> Word64
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RangeMin a -> a
forall a. RangeMin a -> a
rangeMinBP
  {-# INLINE bitLength #-}

instance OpenAt a => OpenAt (RangeMin a) where
  openAt :: RangeMin a -> Word64 -> Bool
openAt = a -> Word64 -> Bool
forall v. OpenAt v => v -> Word64 -> Bool
openAt (a -> Word64 -> Bool)
-> (RangeMin a -> a) -> RangeMin a -> Word64 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RangeMin a -> a
forall a. RangeMin a -> a
rangeMinBP
  {-# INLINE openAt #-}

instance CloseAt a => CloseAt (RangeMin a) where
  closeAt :: RangeMin a -> Word64 -> Bool
closeAt = a -> Word64 -> Bool
forall v. CloseAt v => v -> Word64 -> Bool
closeAt (a -> Word64 -> Bool)
-> (RangeMin a -> a) -> RangeMin a -> Word64 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RangeMin a -> a
forall a. RangeMin a -> a
rangeMinBP
  {-# INLINE closeAt #-}

instance NewCloseAt a => NewCloseAt (RangeMin a) where
  newCloseAt :: RangeMin a -> Word64 -> Bool
newCloseAt = a -> Word64 -> Bool
forall v. NewCloseAt v => v -> Word64 -> Bool
newCloseAt (a -> Word64 -> Bool)
-> (RangeMin a -> a) -> RangeMin a -> Word64 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RangeMin a -> a
forall a. RangeMin a -> a
rangeMinBP
  {-# INLINE newCloseAt #-}

instance FindOpenN a => FindOpenN (RangeMin a) where
  findOpenN :: RangeMin a -> Word64 -> Word64 -> Maybe Word64
findOpenN = a -> Word64 -> Word64 -> Maybe Word64
forall v. FindOpenN v => v -> Word64 -> Word64 -> Maybe Word64
findOpenN (a -> Word64 -> Word64 -> Maybe Word64)
-> (RangeMin a -> a)
-> RangeMin a
-> Word64
-> Word64
-> Maybe Word64
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RangeMin a -> a
forall a. RangeMin a -> a
rangeMinBP
  {-# INLINE findOpenN #-}

instance (BitLength a, NewCloseAt a) => FindCloseN (RangeMin a) where
  findCloseN :: RangeMin a -> Word64 -> Word64 -> Maybe Word64
findCloseN RangeMin a
v Word64
s Word64
p  = (Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
1) (Word64 -> Word64) -> Maybe Word64 -> Maybe Word64
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
forall a.
(BitLength a, NewCloseAt a) =>
RangeMin a -> Int -> Word64 -> FindState -> Maybe Word64
rm2FindClose RangeMin a
v (Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
s) (Word64
p Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
- Word64
1) FindState
FindFromL0
  {-# INLINE findCloseN  #-}

instance (BitLength a, CloseAt a, NewCloseAt a, FindCloseN a) => FindClose (RangeMin a) where
  findClose :: RangeMin a -> Word64 -> Maybe Word64
findClose RangeMin a
v Word64
p = if RangeMin a
v RangeMin a -> Word64 -> Bool
forall v. CloseAt v => v -> Word64 -> Bool
`closeAt` Word64
p then Word64 -> Maybe Word64
forall a. a -> Maybe a
Just Word64
p else RangeMin a -> Word64 -> Word64 -> Maybe Word64
forall v. FindCloseN v => v -> Word64 -> Word64 -> Maybe Word64
findCloseN RangeMin a
v Word64
1 (Word64
p Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
+ Word64
1)
  {-# INLINE findClose #-}

instance (OpenAt a, FindOpenN a) => FindOpen (RangeMin a) where
  findOpen :: RangeMin a -> Word64 -> Maybe Word64
findOpen RangeMin a
v Word64
p = if RangeMin a
v RangeMin a -> Word64 -> Bool
forall v. OpenAt v => v -> Word64 -> Bool
`openAt`  Word64
p then Word64 -> Maybe Word64
forall a. a -> Maybe a
Just Word64
p else RangeMin a -> Word64 -> Word64 -> Maybe Word64
forall v. FindOpenN v => v -> Word64 -> Word64 -> Maybe Word64
findOpenN  RangeMin a
v Word64
0 (Word64
p Word64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
- Word64
1)
  {-# INLINE findOpen #-}

instance FindOpenN a => Enclose (RangeMin a) where
  enclose :: RangeMin a -> Word64 -> Maybe Word64
enclose RangeMin a
v = RangeMin a -> Word64 -> Word64 -> Maybe Word64
forall v. FindOpenN v => v -> Word64 -> Word64 -> Maybe Word64
findOpenN RangeMin a
v Word64
1
  {-# INLINE enclose #-}

instance (BitLength a, NewCloseAt a, CloseAt a, OpenAt a, FindOpenN a, FindCloseN a) => BalancedParens (RangeMin a)