{-# LANGUAGE DerivingVia #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE TypeFamilies #-}
{-# OPTIONS_HADDOCK hide #-}

-- | Base module for implementing dynamic sequences. It internaly uses a splay tree and user has to
-- track the root node change.
--
-- @since 1.2.0.0
module AtCoder.Extra.Seq.Raw
  ( -- * Seq
    Seq (..),

    -- * Constructors
    newST,
    resetST,
    newNodeST,
    newSeqST,
    freeNodeST,
    freeSubtreeST,

    -- * Metadata
    capacity,
    lengthST,

    -- * Merge/split
    mergeST,
    merge3ST,
    merge4ST,
    splitST,
    split3ST,
    split4ST,
    splitLrST,
    sliceST,

    -- * Read/write
    readST,
    readMaybeST,
    writeST,
    modifyST,
    exchangeST,

    -- * Products
    prodST,
    prodMaybeST,
    prodAllST,

    -- * Applications
    applyInST,
    applyToRootST,
    reverseST,

    -- * Insert/delete
    insertST,
    deleteST,
    deleteST_,
    detachST,

    -- * Balancing
    rotateST,
    splayST,
    splayKthST,

    -- * Bisection methods

    -- ** C++-like
    ilowerBoundST,
    ilowerBoundM,
    ilowerBoundProdST,
    ilowerBoundProdM,

    -- ** Splits
    isplitMaxRightST,
    isplitMaxRightM,
    isplitMaxRightProdST,
    isplitMaxRightProdM,

    -- ** Max right
    imaxRightST,
    imaxRightM,
    imaxRightProdST,
    imaxRightProdM,

    -- * Conversions
    freezeST,

    -- * Internals

    -- | These functions are exported primarily for @Map@ implementations.
    splitMaxRightWithST,
    maxRightWithST,
    updateNodeST,
    writeNodeST,
    modifyNodeST,
    exchangeNodeST,
    propNodeST,
    applyNodeST,
  )
where

import AtCoder.Extra.Pool qualified as P
import AtCoder.Internal.Assert qualified as ACIA
import AtCoder.LazySegTree (SegAct (..))
import Control.Monad (unless, when)
import Control.Monad.Primitive (PrimMonad, PrimState, stToPrim)
import Control.Monad.ST (ST)
import Data.Bit
import Data.Bits hiding (rotate)
import Data.Coerce (coerce)
import Data.Vector.Generic qualified as VG
import Data.Vector.Generic.Mutable qualified as VGM
import Data.Vector.Unboxed qualified as VU
import Data.Vector.Unboxed.Mutable qualified as VUM
import GHC.Stack (HasCallStack)
import Prelude hiding (seq)

-- | Storages of dynamic sequences of monoid values with monoid actions on them through the `SegAct`
-- instance.
--
-- @since 1.2.0.0
data Seq s f a = Seq
  { -- | The maximum number of elements.
    --
    -- @since 1.2.0.0
    forall s f a. Seq s f a -> Int
nSeq :: {-# UNPACK #-} !Int,
    -- | `Pool` for free slot management.
    --
    -- @since 1.2.0.0
    forall s f a. Seq s f a -> Pool s ()
poolSeq :: !(P.Pool s ()),
    -- | Decomposed node data storage: left children.
    --
    -- @since 1.2.0.0
    forall s f a. Seq s f a -> MVector s Index
lSeq :: !(VUM.MVector s P.Index),
    -- | Decomposed node data storage: right children.
    --
    -- @since 1.2.0.0
    forall s f a. Seq s f a -> MVector s Index
rSeq :: !(VUM.MVector s P.Index),
    -- | Decomposed node data storage: parents.
    --
    -- @since 1.2.0.0
    forall s f a. Seq s f a -> MVector s Index
pSeq :: !(VUM.MVector s P.Index),
    -- | Decomposed node data storage: subtree sizes.
    --
    -- @since 1.2.0.0
    forall s f a. Seq s f a -> MVector s Int
sSeq :: !(VUM.MVector s Int),
    -- | Decomposed node data storage: monoid values.
    --
    -- @since 1.2.0.0
    forall s f a. Seq s f a -> MVector s a
vSeq :: !(VUM.MVector s a),
    -- | Decomposed node data storage: monoid products.
    --
    -- @since 1.2.0.0
    forall s f a. Seq s f a -> MVector s a
prodSeq :: !(VUM.MVector s a),
    -- | Decomposed node data storage: reversed flag of children.
    --
    -- @since 1.2.0.0
    forall s f a. Seq s f a -> MVector s Bit
revSeq :: !(VUM.MVector s Bit),
    -- | Decomposed node data storage: lazily propagated monoid action. Use @()@ if you don't need
    -- monoid actions.
    --
    -- @since 1.2.0.0
    forall s f a. Seq s f a -> MVector s f
lazySeq :: !(VUM.MVector s f)
  }

-- | \(O(n)\) Creates a new `Seq` of length \(n\).
--
-- @since 1.2.0.0
{-# INLINEABLE newST #-}
newST :: (Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Int -> ST s (Seq s f a)
newST :: forall f a s.
(Monoid f, Unbox f, Monoid a, Unbox a) =>
Int -> ST s (Seq s f a)
newST Int
nSeq = do
  Pool s ()
poolSeq <- Int -> ST s (Pool (PrimState (ST s)) ())
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
Int -> m (Pool (PrimState m) a)
P.new Int
nSeq
  MVector s Index
lSeq <- Int -> ST s (MVector (PrimState (ST s)) Index)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
nSeq
  MVector s Index
rSeq <- Int -> ST s (MVector (PrimState (ST s)) Index)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
nSeq
  MVector s Index
pSeq <- Int -> ST s (MVector (PrimState (ST s)) Index)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
nSeq
  MVector s Int
sSeq <- Int -> ST s (MVector (PrimState (ST s)) Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
nSeq
  MVector s a
vSeq <- Int -> ST s (MVector (PrimState (ST s)) a)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
nSeq
  MVector s a
prodSeq <- Int -> ST s (MVector (PrimState (ST s)) a)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
nSeq
  MVector s Bit
revSeq <- Int -> ST s (MVector (PrimState (ST s)) Bit)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
nSeq
  MVector s f
lazySeq <- Int -> ST s (MVector (PrimState (ST s)) f)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
nSeq
  Seq s f a -> ST s (Seq s f a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..}

-- | \(O(1)\) Clears the sequence storage.
--
-- @since 1.2.0.0
{-# INLINE resetST #-}
resetST :: Seq s f a -> ST s ()
resetST :: forall s f a. Seq s f a -> ST s ()
resetST Seq {Pool s ()
poolSeq :: forall s f a. Seq s f a -> Pool s ()
poolSeq :: Pool s ()
poolSeq} = ST (PrimState (ST s)) () -> ST s ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState (ST s)) () -> ST s ())
-> ST (PrimState (ST s)) () -> ST s ()
forall a b. (a -> b) -> a -> b
$ Pool (PrimState (ST s)) () -> ST s ()
forall (m :: * -> *) a. PrimMonad m => Pool (PrimState m) a -> m ()
P.clear Pool s ()
Pool (PrimState (ST s)) ()
poolSeq

-- | \(O(1)\) Allocates a new sequence of length \(1\).
--
-- @since 1.2.0.0
{-# INLINEABLE newNodeST #-}
newNodeST :: (HasCallStack, Monoid f, VU.Unbox f, VU.Unbox a) => Seq s f a -> a -> ST s P.Index
newNodeST :: forall f a s.
(HasCallStack, Monoid f, Unbox f, Unbox a) =>
Seq s f a -> a -> ST s Index
newNodeST Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} a
x = do
  Index
i <- Pool (PrimState (ST s)) () -> () -> ST s Index
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Pool (PrimState m) a -> a -> m Index
P.alloc Pool s ()
Pool (PrimState (ST s)) ()
poolSeq ()
  MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) Index
P.undefIndex
  MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) Index
P.undefIndex
  MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) Index
P.undefIndex
  MVector (PrimState (ST s)) Int -> Int -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) Int
1
  MVector (PrimState (ST s)) a -> Int -> a -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s a
MVector (PrimState (ST s)) a
vSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) a
x
  MVector (PrimState (ST s)) a -> Int -> a -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s a
MVector (PrimState (ST s)) a
prodSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) a
x
  MVector (PrimState (ST s)) Bit -> Int -> Bit -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Bit
MVector (PrimState (ST s)) Bit
revSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) (Bit -> ST s ()) -> Bit -> ST s ()
forall a b. (a -> b) -> a -> b
$ Bool -> Bit
Bit Bool
False
  MVector (PrimState (ST s)) f -> Int -> f -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s f
MVector (PrimState (ST s)) f
lazySeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) f
forall a. Monoid a => a
mempty
  Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
i

-- | \(O(n)\) Allocates a new sequence.
--
-- @since 1.2.0.0
{-# INLINEABLE newSeqST #-}
newSeqST :: (HasCallStack, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> VU.Vector a -> ST s P.Index
newSeqST :: forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Vector a -> ST s Index
newSeqST seq :: Seq s f a
seq@Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} !Vector a
xs = do
  -- [l, r)
  let inner :: Int -> Int -> ST s Index
inner Int
l Int
r
        | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
r = Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
P.undefIndex
        | Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
r = Seq s f a -> a -> ST s Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Unbox a) =>
Seq s f a -> a -> ST s Index
newNodeST Seq s f a
seq (a -> ST s Index) -> a -> ST s Index
forall a b. (a -> b) -> a -> b
$ Vector a
xs Vector a -> Int -> a
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
l
        | Bool
otherwise = do
            let !m :: Int
m = (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
r) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
            Index
rootL <- Int -> Int -> ST s Index
inner Int
l Int
m
            Index
root <- Seq s f a -> a -> ST s Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Unbox a) =>
Seq s f a -> a -> ST s Index
newNodeST Seq s f a
seq (Vector a
xs Vector a -> Int -> a
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
m)
            Index
rootR <- Int -> Int -> ST s Index
inner (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Int
r
            Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
rootL) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
              MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root) Index
rootL
              MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
rootL) Index
root
            Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
rootR) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
              MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root) Index
rootR
              MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
rootR) Index
root
            Seq s f a -> Index -> ST s ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
updateNodeST Seq s f a
seq Index
root
            Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root
  Int -> Int -> ST s Index
inner Int
0 (Vector a -> Int
forall a. Unbox a => Vector a -> Int
VU.length Vector a
xs)

-- | \(O(1)\) Frees a node.
--
-- @since 1.2.0.0
{-# INLINE freeNodeST #-}
freeNodeST :: Seq s v a -> P.Index -> ST s ()
freeNodeST :: forall s v a. Seq s v a -> Index -> ST s ()
freeNodeST Seq {Pool s ()
poolSeq :: forall s f a. Seq s f a -> Pool s ()
poolSeq :: Pool s ()
poolSeq} = Pool (PrimState (ST s)) () -> Index -> ST s ()
forall (m :: * -> *) a.
PrimMonad m =>
Pool (PrimState m) a -> Index -> m ()
P.free Pool s ()
Pool (PrimState (ST s)) ()
poolSeq

-- | \(O(n)\) Frees a subtree.
--
-- @since 1.2.0.0
{-# INLINEABLE freeSubtreeST #-}
freeSubtreeST :: (VU.Unbox a) => Seq s f a -> P.Index -> ST s ()
freeSubtreeST :: forall a s f. Unbox a => Seq s f a -> Index -> ST s ()
freeSubtreeST Seq {MVector s Index
lSeq :: forall s f a. Seq s f a -> MVector s Index
lSeq :: MVector s Index
lSeq, MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: MVector s Index
rSeq, Pool s ()
poolSeq :: forall s f a. Seq s f a -> Pool s ()
poolSeq :: Pool s ()
poolSeq} Index
c0
  | Index -> Bool
P.nullIndex Index
c0 = () -> ST s ()
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
  | Bool
otherwise = do
      let inner :: Index -> ST s ()
inner Index
c = do
            Index
cl <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
            Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
cl) (Index -> ST s ()
inner Index
cl)
            Index
cr <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
            Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
cr) (Index -> ST s ()
inner Index
cr)
      Index -> ST s ()
inner Index
c0
      Pool (PrimState (ST s)) () -> Index -> ST s ()
forall (m :: * -> *) a.
PrimMonad m =>
Pool (PrimState m) a -> Index -> m ()
P.free Pool s ()
Pool (PrimState (ST s)) ()
poolSeq Index
c0

-- -------------------------------------------------------------------------------------------------
-- Metadata
-- -------------------------------------------------------------------------------------------------

-- | \(O(1)\) Returns the capacity of the sequence storage.
--
-- @since 1.2.1.0
{-# INLINE capacity #-}
capacity :: Seq s f a -> Int
capacity :: forall s f a. Seq s f a -> Int
capacity = Seq s f a -> Int
forall s f a. Seq s f a -> Int
nSeq

-- | \(O(1)\) Returns the length of a sequence or a subtree.
--
-- @since 1.2.1.0
{-# INLINE lengthST #-}
lengthST :: Seq s f a -> P.Index -> ST s Int
lengthST :: forall s f a. Seq s f a -> Index -> ST s Int
lengthST Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
i
  | Index -> Bool
P.nullIndex Index
i = Int -> ST s Int
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
0
  | Bool
otherwise = MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i)

-- -------------------------------------------------------------------------------------------------
-- Merge/split
-- -------------------------------------------------------------------------------------------------

{-# INLINE assertRootST #-}
assertRootST :: (HasCallStack) => Seq s f a -> P.Index -> ST s ()
assertRootST :: forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootST Seq {MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: MVector s Index
pSeq} Index
i = do
  Index
p <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i)
  let !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (Index -> Bool
P.nullIndex Index
p) (String -> ()) -> String -> ()
forall a b. (a -> b) -> a -> b
$ String
"AtCoder.Extra.Seq.Raw.assertRootST: not a root (node `" String -> String -> String
forall a. [a] -> [a] -> [a]
++ Index -> String
forall a. Show a => a -> String
show Index
i String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
"`, parent `" String -> String -> String
forall a. [a] -> [a] -> [a]
++ Index -> String
forall a. Show a => a -> String
show Index
p String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
"`)"
  () -> ST s ()
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()

{-# INLINE assertRootOrNullST #-}
assertRootOrNullST :: (HasCallStack) => Seq s f a -> P.Index -> ST s ()
assertRootOrNullST :: forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootOrNullST Seq {MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: MVector s Index
pSeq} Index
i
  | Index -> Bool
P.nullIndex Index
i = () -> ST s ()
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
  | Bool
otherwise = do
      Index
p <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i)
      let !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (Index -> Bool
P.nullIndex Index
p) (String -> ()) -> String -> ()
forall a b. (a -> b) -> a -> b
$ String
"AtCoder.Extra.Seq.Raw.assertRootOrNullST: not a root (node `" String -> String -> String
forall a. [a] -> [a] -> [a]
++ Index -> String
forall a. Show a => a -> String
show Index
i String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
"`, parent `" String -> String -> String
forall a. [a] -> [a] -> [a]
++ Index -> String
forall a. Show a => a -> String
show Index
p String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
"`)"
      () -> ST s ()
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()

-- | Amortized \(O(\log n)\). Merges two sequences \(l, r\) into one in the given order, ignoring
-- empty sequences.
--
-- ==== Constraints
-- - The vertices must be either null or a root.
--
-- @since 1.2.0.0
{-# INLINEABLE mergeST #-}
mergeST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> P.Index -> ST s P.Index
mergeST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Index -> ST s Index
mergeST seq :: Seq s f a
seq@Seq {MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: MVector s Index
pSeq, MVector s Index
lSeq :: forall s f a. Seq s f a -> MVector s Index
lSeq :: MVector s Index
lSeq} Index
lRoot Index
rRoot
  | Index -> Bool
P.nullIndex Index
lRoot = Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
rRoot
  | Index -> Bool
P.nullIndex Index
rRoot = Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
lRoot
  | Bool
otherwise = do
      Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootST Seq s f a
seq Index
lRoot
      Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootST Seq s f a
seq Index
rRoot
      Index
rRoot' <- Seq s f a -> Index -> Int -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s Index
splayKthST Seq s f a
seq Index
rRoot Int
0
      MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
rRoot') Index
lRoot
      MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
lRoot) Index
rRoot'
      Seq s f a -> Index -> ST s ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
updateNodeST Seq s f a
seq Index
rRoot'
      Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
rRoot'

-- | Amortized \(O(\log n)\). Merges three sequences \(l, m, r\) into one in the given order,
-- ignoring empty sequences.
--
-- ==== Constraints
-- - The vertices must be either null or a root.
--
-- @since 1.2.0.0
{-# INLINE merge3ST #-}
merge3ST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> P.Index -> P.Index -> ST s P.Index
merge3ST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Index -> Index -> ST s Index
merge3ST Seq s f a
seq Index
a Index
b Index
c = do
  Index
r' <- Seq s f a -> Index -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Index -> ST s Index
mergeST Seq s f a
seq Index
a Index
b
  Seq s f a -> Index -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Index -> ST s Index
mergeST Seq s f a
seq Index
r' Index
c

-- | Amortized \(O(\log n)\). Merges four sequences \(l, b, c, d, m, r\) into one in the given
-- order, ignoring empty sequences.
--
-- ==== Constraints
-- - The vertices must be either null or a root.
--
-- @since 1.2.0.0
{-# INLINE merge4ST #-}
merge4ST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> P.Index -> P.Index -> P.Index -> ST s P.Index
merge4ST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Index -> Index -> Index -> ST s Index
merge4ST Seq s f a
seq Index
a Index
b Index
c Index
d = do
  Index
r' <- Seq s f a -> Index -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Index -> ST s Index
mergeST Seq s f a
seq Index
a Index
b
  Index
r'' <- Seq s f a -> Index -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Index -> ST s Index
mergeST Seq s f a
seq Index
r' Index
c
  Seq s f a -> Index -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Index -> ST s Index
mergeST Seq s f a
seq Index
r'' Index
d

-- | Amortized \(O(\log n)\). Splits a sequences into two: \([0, k), [k, n)\).
--
-- ==== Constraints
-- - The node must be null or a root.
-- - \(0 \le k \le n\).
--
-- @since 1.2.0.0
{-# INLINEABLE splitST #-}
splitST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> ST s (P.Index, P.Index)
splitST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s (Index, Index)
splitST seq :: Seq s f a
seq@Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
root Int
k = do
  Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootOrNullST Seq s f a
seq Index
root
  if Int
k Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0
    then (Index, Index) -> ST s (Index, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
P.undefIndex, Index
root)
    else do
      Int
size <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Int -> ST s Int) -> Int -> ST s Int
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root
      if Int
k Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
size
        then (Index, Index) -> ST s (Index, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
root, Index
P.undefIndex)
        else do
          Index
root' <- Seq s f a -> Index -> Int -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s Index
splayKthST Seq s f a
seq Index
root (Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
          Index
r <- MVector (PrimState (ST s)) Index -> Int -> Index -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
VGM.exchange MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root') Index
P.undefIndex
          MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
r) Index
P.undefIndex
          Seq s f a -> Index -> ST s ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
updateNodeST Seq s f a
seq Index
root'
          (Index, Index) -> ST s (Index, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
root', Index
r)

-- | Amortized \(O(\log n)\). Splits a sequences into three: \([0, l), [l, r), [r, n)\).
--
-- ==== Constraints
-- - The node must be null or a root.
-- - \(0 \le l \le r \le n\).
--
-- @since 1.2.0.0
{-# INLINE split3ST #-}
split3ST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> Int -> ST s (P.Index, P.Index, P.Index)
split3ST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> Int -> ST s (Index, Index, Index)
split3ST Seq s f a
seq Index
root Int
l Int
r = do
  (!Index
root', !Index
c) <- Seq s f a -> Index -> Int -> ST s (Index, Index)
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s (Index, Index)
splitST Seq s f a
seq Index
root Int
r
  (!Index
a, !Index
b) <- Seq s f a -> Index -> Int -> ST s (Index, Index)
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s (Index, Index)
splitST Seq s f a
seq Index
root' Int
l
  (Index, Index, Index) -> ST s (Index, Index, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
a, Index
b, Index
c)

-- | Amortized \(O(\log n)\). Splits a sequences into four: \([0, i), [i, j), [j, k), [k, n)\).
--
-- ==== Constraints
-- - The node must be null or a root.
-- - \(0 \le i \le j \le k \le n\).
--
-- @since 1.2.0.0
{-# INLINE split4ST #-}
split4ST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> Int -> Int -> ST s (P.Index, P.Index, P.Index, P.Index)
split4ST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a
-> Index -> Int -> Int -> Int -> ST s (Index, Index, Index, Index)
split4ST Seq s f a
seq Index
root Int
i Int
j Int
k = do
  (!Index
root', !Index
d) <- Seq s f a -> Index -> Int -> ST s (Index, Index)
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s (Index, Index)
splitST Seq s f a
seq Index
root Int
k
  (!Index
root'', !Index
c) <- Seq s f a -> Index -> Int -> ST s (Index, Index)
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s (Index, Index)
splitST Seq s f a
seq Index
root' Int
j
  (!Index
a, !Index
b) <- Seq s f a -> Index -> Int -> ST s (Index, Index)
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s (Index, Index)
splitST Seq s f a
seq Index
root'' Int
i
  (Index, Index, Index, Index) -> ST s (Index, Index, Index, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
a, Index
b, Index
c, Index
d)

-- | Amortized \(O(\log n)\). Splits a sequence into three: \([0, \mathrm{root}), \mathrm{root}, [\mathrm{root} + 1, n)\).
--
-- ==== Constraints
-- - The node must be a root.
--
-- @since 1.2.0.0
{-# INLINEABLE splitLrST #-}
splitLrST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> ST s (P.Index, P.Index, P.Index)
splitLrST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> ST s (Index, Index, Index)
splitLrST seq :: Seq s f a
seq@Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
root = do
  Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootST Seq s f a
seq Index
root
  Int
s <- do
    Index
rootL <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
    if Index -> Bool
P.nullIndex Index
rootL
      then Int -> ST s Int
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
0
      else MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
rootL)
  Seq s f a -> Index -> Int -> Int -> ST s (Index, Index, Index)
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> Int -> ST s (Index, Index, Index)
split3ST Seq s f a
seq Index
root Int
s (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)

-- | Amortized \(O(\log n)\). Captures the root of a subtree of \([l, r)\). Splay the new root after
-- call.
--
-- ==== Constraints
-- - \(0 \le \lt r \le n\). Note that the interval must have positive length.
--
-- @since 1.2.0.0
{-# INLINEABLE sliceST #-}
sliceST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> Int -> ST s P.Index
sliceST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> Int -> ST s Index
sliceST seq :: Seq s f a
seq@Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
root Int
l Int
r
  | Int
l Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = do
      Int
size <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
      if Int
r Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
size
        then Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root
        else do
          Index
root' <- Seq s f a -> Index -> Int -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s Index
splayKthST Seq s f a
seq Index
root Int
r
          MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root'
  | Bool
otherwise = do
      Int
size <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Int -> ST s Int) -> Int -> ST s Int
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root
      if Int
r Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
size
        then do
          Index
root' <- Seq s f a -> Index -> Int -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s Index
splayKthST Seq s f a
seq Index
root (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
          MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root'
        else do
          -- o--l--o--o--r--o
          --    [        )
          --             * root' (splayed)
          --          * rootL (detached from the root)
          -- \* rootL' (splayed)
          --    * right(rootL'): node that corresponds to [l, r)
          Index
root' <- Seq s f a -> Index -> Int -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s Index
splayKthST Seq s f a
seq Index
root Int
r
          Index
rootL <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root'
          -- detach `rootL` from `root'`
          MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
rootL) Index
P.undefIndex
          Index
rootL' <- Seq s f a -> Index -> Int -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s Index
splayKthST Seq s f a
seq Index
rootL (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
          -- re-attach `rootL'` to `root'`
          MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
rootL') Index
root'
          MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root') Index
rootL'
          Seq s f a -> Index -> ST s ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
updateNodeST Seq s f a
seq Index
root'
          MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
rootL'

-- -------------------------------------------------------------------------------------------------
-- Modifications
-- -------------------------------------------------------------------------------------------------

-- | Amortized \(O(\log n)\). Reads the \(k\)-th node's monoid value.
--
-- ==== Constraints
-- - \(0 \le k \lt n\)
--
-- @since 1.2.0.0
{-# INLINEABLE readST #-}
readST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> ST s (a, P.Index)
readST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s (a, Index)
readST seq :: Seq s f a
seq@Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
root Int
k = do
  Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootST Seq s f a
seq Index
root
  Index
root' <- Seq s f a -> Index -> Int -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s Index
splayKthST Seq s f a
seq Index
root Int
k
  (,Index
root') (a -> (a, Index)) -> ST s a -> ST s (a, Index)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
vSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root')

-- | Amortized \(O(\log n)\). Reads the \(k\)-th node's monoid value.
--
-- ==== Constraints
-- - The root must be empty or a root.
--
-- @since 1.2.0.0
{-# INLINEABLE readMaybeST #-}
readMaybeST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> ST s (Maybe (a, P.Index))
readMaybeST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s (Maybe (a, Index))
readMaybeST seq :: Seq s f a
seq@Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
root Int
k
  | Index -> Bool
P.nullIndex Index
root = Maybe (a, Index) -> ST s (Maybe (a, Index))
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe (a, Index)
forall a. Maybe a
Nothing
  | Bool
otherwise = do
      Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootST Seq s f a
seq Index
root
      Int
s <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
      if Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
k Bool -> Bool -> Bool
&& Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
s
        then do
          Index
root' <- Seq s f a -> Index -> Int -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s Index
splayKthST Seq s f a
seq Index
root Int
k
          (a, Index) -> Maybe (a, Index)
forall a. a -> Maybe a
Just ((a, Index) -> Maybe (a, Index))
-> (a -> (a, Index)) -> a -> Maybe (a, Index)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (,Index
root') (a -> Maybe (a, Index)) -> ST s a -> ST s (Maybe (a, Index))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
vSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root')
        else Maybe (a, Index) -> ST s (Maybe (a, Index))
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe (a, Index)
forall a. Maybe a
Nothing

-- | Amortized \(O(\log n)\). Writes to the \(k\)-th node's monoid value.
--
-- ==== Constraints
-- - The node must be a root.
-- - \(0 \le k \lt n\)
--
-- @since 1.2.0.0
{-# INLINEABLE writeST #-}
writeST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> a -> ST s P.Index
writeST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> a -> ST s Index
writeST Seq s f a
seq Index
root Int
k a
v = do
  Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootST Seq s f a
seq Index
root
  Index
root' <- Seq s f a -> Index -> Int -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s Index
splayKthST Seq s f a
seq Index
root Int
k
  Seq s f a -> Index -> a -> ST s ()
forall a s f.
(Monoid a, Unbox a) =>
Seq s f a -> Index -> a -> ST s ()
writeNodeST Seq s f a
seq Index
root' a
v
  Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root'

-- | Amortized \(O(\log n)\). Modifies the \(k\)-th node's monoid value.
--
-- ==== Constraints
-- - The node must be a root.
-- - \(0 \le k \lt n\)
--
-- @since 1.2.0.0
{-# INLINEABLE modifyST #-}
modifyST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> (a -> a) -> Int -> ST s P.Index
modifyST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> (a -> a) -> Int -> ST s Index
modifyST Seq s f a
seq Index
root a -> a
f Int
k = do
  Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootST Seq s f a
seq Index
root
  Index
root' <- Seq s f a -> Index -> Int -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s Index
splayKthST Seq s f a
seq Index
root Int
k
  Seq s f a -> (a -> a) -> Index -> ST s ()
forall a s f.
(HasCallStack, Monoid a, Unbox a) =>
Seq s f a -> (a -> a) -> Index -> ST s ()
modifyNodeST Seq s f a
seq a -> a
f Index
root'
  Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root'

-- | Amortized \(O(\log n)\). Exchanges the \(k\)-th node's monoid value.
--
-- ==== Constraints
-- - The node must be a root.
-- - \(0 \le k \lt n\)
--
-- @since 1.2.0.0
{-# INLINEABLE exchangeST #-}
exchangeST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> a -> ST s (a, P.Index)
exchangeST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> a -> ST s (a, Index)
exchangeST Seq s f a
seq Index
root Int
k a
v = do
  Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootST Seq s f a
seq Index
root
  Index
root' <- Seq s f a -> Index -> Int -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s Index
splayKthST Seq s f a
seq Index
root Int
k
  a
res <- Seq s f a -> Index -> a -> ST s a
forall a s f.
(HasCallStack, Monoid a, Unbox a) =>
Seq s f a -> Index -> a -> ST s a
exchangeNodeST Seq s f a
seq Index
root' a
v
  (a, Index) -> ST s (a, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a
res, Index
root')

-- | Amortized \(O(\log n)\). Returns the monoid product in an interval \([l, r)\).
--
-- ==== Constraints
-- - The node must be a root
-- - \(0 \le l \le r \le n\)
--
-- @since 1.2.0.0
{-# INLINEABLE prodST #-}
prodST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> Int -> ST s (a, P.Index)
prodST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> Int -> ST s (a, Index)
prodST seq :: Seq s f a
seq@Seq {MVector s Int
sSeq :: forall s f a. Seq s f a -> MVector s Int
sSeq :: MVector s Int
sSeq} Index
root Int
l Int
r = do
  Int
s <- if Index -> Bool
P.nullIndex Index
root then Int -> ST s Int
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
0 else MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
  let !()
_ = HasCallStack => String -> Int -> Int -> Int -> ()
String -> Int -> Int -> Int -> ()
ACIA.checkInterval String
"AtCoder.Extra.Seq.Raw.prodST" Int
l Int
r Int
s
  if Int
l Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
r
    then (a, Index) -> ST s (a, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a
forall a. Monoid a => a
mempty, Index
root)
    else Seq s f a -> Index -> Int -> Int -> ST s (a, Index)
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> Int -> ST s (a, Index)
unsafeProdST Seq s f a
seq Index
root Int
l Int
r

-- | Amortized \(O(\log n)\). Returns the monoid product in an interval \([l, r)\). Returns
-- `Nothing` if an invalid interval is given or for an empty sequence.
--
-- @since 1.2.0.0
{-# INLINEABLE prodMaybeST #-}
prodMaybeST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> Int -> ST s (Maybe (a, P.Index))
prodMaybeST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> Int -> ST s (Maybe (a, Index))
prodMaybeST seq :: Seq s f a
seq@Seq {MVector s Int
sSeq :: forall s f a. Seq s f a -> MVector s Int
sSeq :: MVector s Int
sSeq} Index
root Int
l Int
r
  | Index -> Bool
P.nullIndex Index
root = Maybe (a, Index) -> ST s (Maybe (a, Index))
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe (a, Index)
forall a. Maybe a
Nothing
  | Bool
otherwise = do
      Int
s <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
      if Bool -> Bool
not (Int -> Int -> Int -> Bool
ACIA.testInterval Int
l Int
r Int
s)
        then Maybe (a, Index) -> ST s (Maybe (a, Index))
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe (a, Index)
forall a. Maybe a
Nothing
        else
          if Int
l Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
r
            then Maybe (a, Index) -> ST s (Maybe (a, Index))
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe (a, Index) -> ST s (Maybe (a, Index)))
-> Maybe (a, Index) -> ST s (Maybe (a, Index))
forall a b. (a -> b) -> a -> b
$ (a, Index) -> Maybe (a, Index)
forall a. a -> Maybe a
Just (a
forall a. Monoid a => a
mempty, Index
root)
            else (a, Index) -> Maybe (a, Index)
forall a. a -> Maybe a
Just ((a, Index) -> Maybe (a, Index))
-> ST s (a, Index) -> ST s (Maybe (a, Index))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Seq s f a -> Index -> Int -> Int -> ST s (a, Index)
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> Int -> ST s (a, Index)
unsafeProdST Seq s f a
seq Index
root Int
l Int
r

-- | Amortized \(O(\log n)\).
--
-- ==== Constraint
-- - \(0 \le \lt r \le n\). Note that the interval must have positive length.
{-# INLINEABLE unsafeProdST #-}
unsafeProdST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> Int -> ST s (a, P.Index)
unsafeProdST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> Int -> ST s (a, Index)
unsafeProdST seq :: Seq s f a
seq@Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
root Int
l Int
r = do
  Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootST Seq s f a
seq Index
root
  Index
target <- Seq s f a -> Index -> Int -> Int -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> Int -> ST s Index
sliceST Seq s f a
seq Index
root Int
l Int
r
  a
res <- MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
prodSeq (Int -> ST s a) -> Int -> ST s a
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
target
  Seq s f a -> Index -> Bool -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Bool -> ST s ()
splayST Seq s f a
seq Index
target Bool
True
  (a, Index) -> ST s (a, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a
res, Index
target)

-- | Amortized \(O(\log n)\). Returns the monoid product of the whole sequence. Returns `mempty`
-- for an empty sequence.
--
-- ==== Constraint
-- - The node must be null or a root.
--
-- @since 1.2.0.0
{-# INLINEABLE prodAllST #-}
prodAllST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> ST s a
prodAllST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> ST s a
prodAllST seq :: Seq s f a
seq@Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
root = do
  if Index -> Bool
P.nullIndex Index
root
    then a -> ST s a
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
forall a. Monoid a => a
mempty
    else do
      Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootST Seq s f a
seq Index
root
      MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
prodSeq (Int -> ST s a) -> Int -> ST s a
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root

-- | Amortized \(O(\log n)\). Given an interval \([l, r)\), applies a monoid action \(f\).
--
-- ==== Constraints
-- - \(0 \le l \le r \le n\)
--
-- @since 1.2.0.0
{-# INLINEABLE applyInST #-}
applyInST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> Int -> f -> ST s P.Index
applyInST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> Int -> f -> ST s Index
applyInST seq :: Seq s f a
seq@Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
root Int
l Int
r f
act = do
  -- assertRootOrNullST seq root
  Int
s <- if Index -> Bool
P.nullIndex Index
root then Int -> ST s Int
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
0 else MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
  let !()
_ = HasCallStack => String -> Int -> Int -> Int -> ()
String -> Int -> Int -> Int -> ()
ACIA.checkInterval String
"AtCoder.Extra.Seq.applyInST" Int
l Int
r Int
s
  if Int
l Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
r
    then Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root
    else do
      Index
root' <- Seq s f a -> Index -> Int -> Int -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> Int -> ST s Index
sliceST Seq s f a
seq Index
root Int
l Int
r
      Seq s f a -> Index -> f -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Index -> f -> ST s ()
applyNodeST Seq s f a
seq Index
root' f
act
      Seq s f a -> Index -> Bool -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Bool -> ST s ()
splayST Seq s f a
seq Index
root' Bool
True
      Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root'

-- | \(O(1)\) Applies a monoid action \(f\) to the root of a sequence.
--
-- @since 1.2.0.0
{-# INLINEABLE applyToRootST #-}
applyToRootST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> f -> ST s ()
applyToRootST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> f -> ST s ()
applyToRootST seq :: Seq s f a
seq@Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
root f
act
  | Index -> Bool
P.nullIndex Index
root = () -> ST s ()
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
  | Bool
otherwise = do
      Index
rootP <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
      Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Index -> Bool
P.nullIndex Index
rootP) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
        Seq s f a -> Index -> f -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Index -> f -> ST s ()
applyNodeST Seq s f a
seq Index
root f
act

-- | Amortized \(O(\log n)\). Reverses the sequence in \([l, r)\).
--
-- ==== Constraints
-- - The monoid action \(f\) must be commutative.
-- - The monoid value \(v\) must be commutative.
--
-- @since 1.2.0.0
{-# INLINEABLE reverseST #-}
reverseST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> Int -> ST s P.Index
reverseST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> Int -> ST s Index
reverseST seq :: Seq s f a
seq@Seq {MVector s Int
sSeq :: forall s f a. Seq s f a -> MVector s Int
sSeq :: MVector s Int
sSeq} Index
root0 Int
l Int
r
  | Index -> Bool
P.nullIndex Index
root0 = Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
P.undefIndex
  | Bool
otherwise = do
      Int
s <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root0)
      if Bool -> Bool
not (Int -> Int -> Int -> Bool
ACIA.testInterval Int
l Int
r Int
s)
        then Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root0
        else
          if Int
l Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
r
            then Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root0
            else do
              Index
root' <- Seq s f a -> Index -> Int -> Int -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> Int -> ST s Index
sliceST Seq s f a
seq Index
root0 Int
l Int
r
              Seq s f a -> Index -> ST s ()
forall s v a. Seq s v a -> Index -> ST s ()
reverseNodeST Seq s f a
seq Index
root'
              Seq s f a -> Index -> Bool -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Bool -> ST s ()
splayST Seq s f a
seq Index
root' Bool
True
              Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root'

-- | Amortized \(O(\log n)\). Inserts a new node at \(k\) with initial monoid value \(v\). This
-- functions for an empty index.
--
-- ==== Constraints
-- - The node must be null or a root.
-- - \(0 \le k \le n\)
--
-- @since 1.2.0.0
{-# INLINEABLE insertST #-}
insertST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> a -> ST s P.Index
insertST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> a -> ST s Index
insertST Seq s f a
seq Index
root Int
k a
v = do
  if Index -> Bool
P.nullIndex Index
root
    then do
      -- `insertST` is actually `insertOrNewNodeST`: it's specifically designed to work for an empty
      -- sequence.
      Seq s f a -> a -> ST s Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Unbox a) =>
Seq s f a -> a -> ST s Index
newNodeST Seq s f a
seq a
v
    else do
      (!Index
l, !Index
r) <- Seq s f a -> Index -> Int -> ST s (Index, Index)
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s (Index, Index)
splitST Seq s f a
seq Index
root Int
k
      Index
node <- Seq s f a -> a -> ST s Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Unbox a) =>
Seq s f a -> a -> ST s Index
newNodeST Seq s f a
seq a
v
      Seq s f a -> Index -> Index -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Index -> Index -> ST s Index
merge3ST Seq s f a
seq Index
l Index
node Index
r

-- | Amortized \(O(\log n)\). Frees the \(k\)-th node and returns the monoid value of it.
--
-- ==== Constraints
-- - The node must be null or a root.
-- - \(0 \le k \lt n\)
--
-- @since 1.2.0.0
{-# INLINEABLE deleteST #-}
deleteST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> ST s (a, P.Index)
deleteST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s (a, Index)
deleteST seq :: Seq s f a
seq@Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
root Int
i = do
  (!Index
l, !Index
m, !Index
r) <- Seq s f a -> Index -> Int -> Int -> ST s (Index, Index, Index)
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> Int -> ST s (Index, Index, Index)
split3ST Seq s f a
seq Index
root Int
i (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
  a
x <- MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
vSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
m)
  Seq s f a -> Index -> ST s ()
forall s v a. Seq s v a -> Index -> ST s ()
freeNodeST Seq s f a
seq Index
m
  Index
root' <- Seq s f a -> Index -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Index -> ST s Index
mergeST Seq s f a
seq Index
l Index
r
  (a, Index) -> ST s (a, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a
x, Index
root')

-- | Amortized \(O(\log n)\). Frees the \(k\)-th node.
--
-- ==== Constraints
-- - The node must be null or a root.
-- - \(0 \le k \lt n\)
--
-- @since 1.2.0.0
{-# INLINEABLE deleteST_ #-}
deleteST_ :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> ST s P.Index
deleteST_ :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s Index
deleteST_ Seq s f a
seq Index
root Int
i = do
  (!Index
l, !Index
m, !Index
r) <- Seq s f a -> Index -> Int -> Int -> ST s (Index, Index, Index)
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> Int -> ST s (Index, Index, Index)
split3ST Seq s f a
seq Index
root Int
i (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
  Seq s f a -> Index -> ST s ()
forall s v a. Seq s v a -> Index -> ST s ()
freeNodeST Seq s f a
seq Index
m
  Index
root' <- Seq s f a -> Index -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Index -> ST s Index
mergeST Seq s f a
seq Index
l Index
r
  Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root'

-- | Amortized \(O(\log n)\). Detaches the \(k\)-th node and returns the new root of the original
-- sequence.
--
-- ==== Constraints
-- - The node must be null or a root.
-- - \(0 \le k \lt n\)
--
-- @since 1.2.0.0
{-# INLINEABLE detachST #-}
detachST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> ST s P.Index
detachST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s Index
detachST Seq s f a
seq Index
root Int
i = do
  (!Index
l, !Index
m, !Index
r) <- Seq s f a -> Index -> Int -> Int -> ST s (Index, Index, Index)
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> Int -> ST s (Index, Index, Index)
split3ST Seq s f a
seq Index
root Int
i (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
  Seq s f a -> Index -> ST s ()
forall s v a. Seq s v a -> Index -> ST s ()
freeNodeST Seq s f a
seq Index
m
  Index
root' <- Seq s f a -> Index -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Index -> ST s Index
mergeST Seq s f a
seq Index
l Index
r
  Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root'

-- -------------------------------------------------------------------------------------------------
-- Balancing
-- -------------------------------------------------------------------------------------------------

-- | Amortized \(O(\log n)\). Rotates a child node.
--
-- ==== Constraints
-- - \(0 \le i \lt n\)
--
-- @since 1.2.0.0
{-# INLINEABLE rotateST #-}
rotateST :: (HasCallStack) => Seq s v a -> P.Index -> ST s ()
rotateST :: forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
rotateST Seq {Int
MVector s v
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s v
..} !Index
i = do
  Index
p <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i
  Index
pl <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
p

  Index
c <-
    if Index
pl Index -> Index -> Bool
forall a. Eq a => a -> a -> Bool
== Index
i
      then do
        --   p       i
        --  /         \
        -- i     ->    p
        --  \         /
        --   r       r
        Index
r <- MVector (PrimState (ST s)) Index -> Int -> Index -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
VGM.exchange MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) Index
p
        MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
p) Index
r
        Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
r
      else do
        -- p          i
        --  \        /
        --   i  ->  p
        --  /        \
        -- l          l
        Index
l <- MVector (PrimState (ST s)) Index -> Int -> Index -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
VGM.exchange MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) Index
p
        MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
p) Index
l
        Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
l

  Index
pp <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
p
  Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
pp) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
    --   pp      pp
    --  /    -> /
    -- p       i
    MVector (PrimState (ST s)) Index
-> (Index -> Index) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
VGM.modify MVector s Index
MVector (PrimState (ST s)) Index
lSeq (\Index
ppl -> if Index
ppl Index -> Index -> Bool
forall a. Eq a => a -> a -> Bool
== Index
p then Index
i else Index
ppl) (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
pp
    --   pp       pp
    --     \  ->    \
    --      p        i
    MVector (PrimState (ST s)) Index
-> (Index -> Index) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
VGM.modify MVector s Index
MVector (PrimState (ST s)) Index
rSeq (\Index
ppr -> if Index
ppr Index -> Index -> Bool
forall a. Eq a => a -> a -> Bool
== Index
p then Index
i else Index
ppr) (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
pp

  -- set parents
  MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) Index
pp
  MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
p) Index
i
  Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
c) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
    MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) Index
p

-- | Amortized \(O(\log n)\). Moves up a node to be a root.
--
-- @since 1.2.0.0
{-# INLINEABLE splayST #-}
splayST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Bool -> ST s ()
splayST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Bool -> ST s ()
splayST seq :: Seq s f a
seq@Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
i Bool
doneParentProp = do
  -- we have no chance to call `splayST` with `doneParentProp == False` though
  if Bool
doneParentProp
    then Seq s f a -> Index -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Index -> ST s ()
propNodeST Seq s f a
seq Index
i
    else Seq s f a -> Index -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Unbox f, Unbox a, Monoid a) =>
Seq s f a -> Index -> ST s ()
propNodeFromRootST Seq s f a
seq Index
i

  let inner :: ST s ()
inner = do
        Index
p <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i
        Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
p) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
          Index
pp <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
p
          if Index -> Bool
P.nullIndex Index
pp
            then do
              Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
rotateST Seq s f a
seq Index
i
              Seq s f a -> Index -> ST s ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
updateNodeST Seq s f a
seq Index
p
              () -> ST s ()
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
            else do
              Index
pl <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
p
              Index
pr <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
p
              Index
ppl <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
pp
              Index
ppr <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
pp
              if Index
pl Index -> Index -> Bool
forall a. Eq a => a -> a -> Bool
== Index
i Bool -> Bool -> Bool
&& Index
ppl Index -> Index -> Bool
forall a. Eq a => a -> a -> Bool
== Index
p Bool -> Bool -> Bool
|| Index
pr Index -> Index -> Bool
forall a. Eq a => a -> a -> Bool
== Index
i Bool -> Bool -> Bool
&& Index
ppr Index -> Index -> Bool
forall a. Eq a => a -> a -> Bool
== Index
p
                then do
                  -- same direction twice
                  Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
rotateST Seq s f a
seq Index
p
                  Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
rotateST Seq s f a
seq Index
i
                else do
                  Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
rotateST Seq s f a
seq Index
i
                  Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
rotateST Seq s f a
seq Index
i
              Seq s f a -> Index -> ST s ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
updateNodeST Seq s f a
seq Index
pp
              Seq s f a -> Index -> ST s ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
updateNodeST Seq s f a
seq Index
p
          ST s ()
inner

  ST s ()
inner
  Seq s f a -> Index -> ST s ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
updateNodeST Seq s f a
seq Index
i

-- | Amortized \(O(\log n)\). Finds \(k\)-th node and splays it. Returns the new root.
--
-- ==== Constraints
-- - \(0 \le k \lt n\)
--
-- @since 1.2.0.0
{-# INLINEABLE splayKthST #-}
splayKthST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> Int -> ST s P.Index
splayKthST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Int -> ST s Index
splayKthST seq :: Seq s f a
seq@Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
root0 Int
k0 = do
  Int
size <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Int -> ST s Int) -> Int -> ST s Int
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root0
  let !()
_ = HasCallStack => String -> Int -> Int -> ()
String -> Int -> Int -> ()
ACIA.checkIndex String
"AtCoder.Extra.Seq.Raw.splayKthST" Int
k0 Int
size

  let inner :: Index -> Int -> ST s Index
inner Index
root Int
k = do
        Seq s f a -> Index -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Index -> ST s ()
propNodeST Seq s f a
seq Index
root
        Index
l <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root
        -- The number of left children = the node's index counting from the leftmost.
        Int
sizeL <- if Index -> Bool
P.nullIndex Index
l then Int -> ST s Int
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
0 else MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Int -> ST s Int) -> Int -> ST s Int
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
l
        case Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Int
k Int
sizeL of
          Ordering
EQ -> Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root
          Ordering
LT -> Index -> Int -> ST s Index
inner Index
l Int
k
          Ordering
GT -> do
            Index
r <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root
            Index -> Int -> ST s Index
inner Index
r (Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
- (Int
sizeL Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1))

  Index
target <- Index -> Int -> ST s Index
inner Index
root0 Int
k0
  Seq s f a -> Index -> Bool -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Bool -> ST s ()
splayST Seq s f a
seq Index
target Bool
True
  Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
target

-- -------------------------------------------------------------------------------------------------
-- Bisection methods
-- -------------------------------------------------------------------------------------------------

-- | Amortized \(O(\log n)\).
--
-- @since 1.2.0.0
{-# INLINE ilowerBoundST #-}
ilowerBoundST ::
  (SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq s f a ->
  -- | Root node
  P.Index ->
  -- | User predicate \(f(i, v_i)\) that takes the index and the monoid value
  (Int -> a -> Bool) ->
  -- | (r, root)
  ST s (Int, P.Index)
ilowerBoundST :: forall f a s.
(SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Index -> (Int -> a -> Bool) -> ST s (Int, Index)
ilowerBoundST Seq s f a
seq Index
root Int -> a -> Bool
f = ST (PrimState (ST s)) (Int, Index) -> ST s (Int, Index)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState (ST s)) (Int, Index) -> ST s (Int, Index))
-> ST (PrimState (ST s)) (Int, Index) -> ST s (Int, Index)
forall a b. (a -> b) -> a -> b
$ do
  if Index -> Bool
P.nullIndex Index
root
    then (Int, Index) -> ST s (Int, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
0, Index
P.undefIndex)
    else do
      (!Int
r, !Index
_, !Index
root') <- Seq s f a
-> Index -> (Int -> a -> Bool) -> ST s (Int, Index, Index)
forall f a s.
(SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) =>
Seq s f a
-> Index -> (Int -> a -> Bool) -> ST s (Int, Index, Index)
imaxRightST Seq s f a
seq Index
root Int -> a -> Bool
f
      (Int, Index) -> ST s (Int, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
r, Index
root')

-- | Amortized \(O(\log n)\).
--
-- @since 1.2.0.0
{-# INLINE ilowerBoundM #-}
ilowerBoundM ::
  (PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq (PrimState m) f a ->
  -- | Root node
  P.Index ->
  -- | User predicate \(f(i, v_i)\) that takes the index and the monoid value
  (Int -> a -> m Bool) ->
  -- | (r, root)
  m (Int, P.Index)
ilowerBoundM :: forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Int, Index)
ilowerBoundM Seq (PrimState m) f a
seq Index
root Int -> a -> m Bool
f = do
  if Index -> Bool
P.nullIndex Index
root
    then (Int, Index) -> m (Int, Index)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
0, Index
P.undefIndex)
    else do
      (!Int
r, !Index
_, !Index
root') <- Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Int, Index, Index)
forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Int, Index, Index)
imaxRightM Seq (PrimState m) f a
seq Index
root Int -> a -> m Bool
f
      (Int, Index) -> m (Int, Index)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
r, Index
root')

-- | Amortized \(O(\log n)\).
--
-- ==== Constraints
-- - The node must be a root.
--
-- @since 1.2.0.0
{-# INLINE ilowerBoundProdST #-}
ilowerBoundProdST ::
  (SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq s f a ->
  -- | Root node
  P.Index ->
  -- | User predicate \(f(i, v_0 \dots v_i)\) that takes the index and the monoid product
  (Int -> a -> Bool) ->
  -- | (r, root)
  ST s (Int, P.Index)
ilowerBoundProdST :: forall f a s.
(SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Index -> (Int -> a -> Bool) -> ST s (Int, Index)
ilowerBoundProdST Seq s f a
seq Index
root Int -> a -> Bool
f = do
  if Index -> Bool
P.nullIndex Index
root
    then (Int, Index) -> ST s (Int, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
0, Index
P.undefIndex)
    else do
      (!Int
r, !Index
_, !Index
root') <- Seq s f a
-> Index -> (Int -> a -> Bool) -> ST s (Int, Index, Index)
forall f a s.
(SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) =>
Seq s f a
-> Index -> (Int -> a -> Bool) -> ST s (Int, Index, Index)
imaxRightProdST Seq s f a
seq Index
root Int -> a -> Bool
f
      (Int, Index) -> ST s (Int, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
r, Index
root')

-- | Amortized \(O(\log n)\).
--
-- ==== Constraints
-- - The node must be a root.
--
-- @since 1.2.0.0
{-# INLINE ilowerBoundProdM #-}
ilowerBoundProdM ::
  (PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq (PrimState m) f a ->
  -- | Root node
  P.Index ->
  -- | User predicate \(f(i, v_0 \dots v_i)\) that takes the index and the monoid product
  (Int -> a -> m Bool) ->
  -- | (r, root)
  m (Int, P.Index)
ilowerBoundProdM :: forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Int, Index)
ilowerBoundProdM Seq (PrimState m) f a
seq Index
root Int -> a -> m Bool
f = do
  if Index -> Bool
P.nullIndex Index
root
    then (Int, Index) -> m (Int, Index)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
0, Index
P.undefIndex)
    else do
      (!Int
r, !Index
_, !Index
root') <- Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Int, Index, Index)
forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Int, Index, Index)
imaxRightProdM Seq (PrimState m) f a
seq Index
root Int -> a -> m Bool
f
      (Int, Index) -> m (Int, Index)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
r, Index
root')

-- | Amortized \(O(\log n)\). Given a monotonious sequence, returns the rightmost node \(v_k\)
-- where \(f(v)\) holds for every \([0, i) (0 \le i \lt k)\).
--
-- @since 1.2.0.0
{-# INLINE isplitMaxRightST #-}
isplitMaxRightST ::
  (SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq s f a ->
  -- | Root node
  P.Index ->
  -- | User predicate \(f(i, v_i)\) that takes the index and the monoid value
  (Int -> a -> Bool) ->
  -- | (left, right) sequences where \(f\) holds for the left
  ST s (P.Index, P.Index)
isplitMaxRightST :: forall f a s.
(SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Index -> (Int -> a -> Bool) -> ST s (Index, Index)
isplitMaxRightST Seq s f a
seq Index
root Int -> a -> Bool
f = ST (PrimState (ST s)) (Index, Index) -> ST s (Index, Index)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState (ST s)) (Index, Index) -> ST s (Index, Index))
-> ST (PrimState (ST s)) (Index, Index) -> ST s (Index, Index)
forall a b. (a -> b) -> a -> b
$ Seq (PrimState (ST s)) f a
-> Index -> (Int -> a -> ST s Bool) -> ST s (Index, Index)
forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Index, Index)
isplitMaxRightM Seq s f a
Seq (PrimState (ST s)) f a
seq Index
root (\Int
i a
x -> Bool -> ST s Bool
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int -> a -> Bool
f Int
i a
x))

-- | Amortized \(O(\log n)\). Given a monotonious sequence, returns the rightmost node \(v_k\)
-- where \(f(v)\) holds for every \([0, i) (0 \le i \lt k)\).
--
-- @since 1.2.0.0
{-# INLINEABLE isplitMaxRightM #-}
isplitMaxRightM ::
  (PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq (PrimState m) f a ->
  -- | Root node
  P.Index ->
  -- | User predicate \(f(i, v_i)\) that takes the index and the monoid value
  (Int -> a -> m Bool) ->
  -- | (left, right) sequences where \(f\) holds for the left
  m (P.Index, P.Index)
isplitMaxRightM :: forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Index, Index)
isplitMaxRightM seq :: Seq (PrimState m) f a
seq@Seq {Int
MVector (PrimState m) f
MVector (PrimState m) a
MVector (PrimState m) Int
MVector (PrimState m) Bit
MVector (PrimState m) Index
Pool (PrimState m) ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool (PrimState m) ()
lSeq :: MVector (PrimState m) Index
rSeq :: MVector (PrimState m) Index
pSeq :: MVector (PrimState m) Index
sSeq :: MVector (PrimState m) Int
vSeq :: MVector (PrimState m) a
prodSeq :: MVector (PrimState m) a
revSeq :: MVector (PrimState m) Bit
lazySeq :: MVector (PrimState m) f
..} Index
root Int -> a -> m Bool
f
  | Index -> Bool
P.nullIndex Index
root = (Index, Index) -> m (Index, Index)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
P.undefIndex, Index
P.undefIndex)
  | Bool
otherwise = do
      ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ()) -> ST (PrimState m) () -> m ()
forall a b. (a -> b) -> a -> b
$ Seq (PrimState m) f a -> Index -> ST (PrimState m) ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootST Seq (PrimState m) f a
seq Index
root
      (!Int
_, !Index
c, !Index
_) <- Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Int, Index, Index)
forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Int, Index, Index)
imaxRightM Seq (PrimState m) f a
seq Index
root Int -> a -> m Bool
f
      if Index -> Bool
P.nullIndex Index
c
        then ST (PrimState m) (Index, Index) -> m (Index, Index)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Index, Index) -> m (Index, Index))
-> ST (PrimState m) (Index, Index) -> m (Index, Index)
forall a b. (a -> b) -> a -> b
$ do
          -- `f` does hot hold
          Seq (PrimState m) f a -> Index -> Bool -> ST (PrimState m) ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Bool -> ST s ()
splayST Seq (PrimState m) f a
seq Index
root Bool
True
          (Index, Index) -> ST (PrimState m) (Index, Index)
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
P.undefIndex, Index
root)
        else ST (PrimState m) (Index, Index) -> m (Index, Index)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Index, Index) -> m (Index, Index))
-> ST (PrimState m) (Index, Index) -> m (Index, Index)
forall a b. (a -> b) -> a -> b
$ do
          Seq (PrimState m) f a -> Index -> Bool -> ST (PrimState m) ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Bool -> ST s ()
splayST Seq (PrimState m) f a
seq Index
c Bool
True
          Index
right <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
          if Index -> Bool
P.nullIndex Index
right
            then do
              -- `f` holds for the whole sequence
              (Index, Index) -> ST (PrimState m) (Index, Index)
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
c, Index
P.undefIndex)
            else do
              -- `f` holds for part of the sequence. detach the right child
              MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
pSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
right) Index
P.undefIndex
              MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) Index
P.undefIndex
              Seq (PrimState m) f a -> Index -> ST (PrimState m) ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
updateNodeST Seq (PrimState m) f a
seq Index
c
              (Index, Index) -> ST (PrimState m) (Index, Index)
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
c, Index
right)

-- | Amortized \(O(\log n)\). Given a monotonious sequence, returns the rightmost node \(v_k\)
-- where \(f(v)\) holds for every \([0, i) (0 \le i \lt k)\).
--
-- @since 1.2.0.0
{-# INLINE isplitMaxRightProdST #-}
isplitMaxRightProdST ::
  (SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq s f a ->
  -- | Root node
  P.Index ->
  -- | User predicate \(f(i, v_0 \dots v_i)\) that takes the index and the monoid value
  (Int -> a -> Bool) ->
  -- | (left, right) sequences where \(f\) holds for the left
  ST s (P.Index, P.Index)
isplitMaxRightProdST :: forall f a s.
(SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Index -> (Int -> a -> Bool) -> ST s (Index, Index)
isplitMaxRightProdST Seq s f a
seq Index
root Int -> a -> Bool
f = ST (PrimState (ST s)) (Index, Index) -> ST s (Index, Index)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState (ST s)) (Index, Index) -> ST s (Index, Index))
-> ST (PrimState (ST s)) (Index, Index) -> ST s (Index, Index)
forall a b. (a -> b) -> a -> b
$ Seq (PrimState (ST s)) f a
-> Index -> (Int -> a -> ST s Bool) -> ST s (Index, Index)
forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Index, Index)
isplitMaxRightProdM Seq s f a
Seq (PrimState (ST s)) f a
seq Index
root (\Int
i a
x -> Bool -> ST s Bool
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int -> a -> Bool
f Int
i a
x))

-- | Amortized \(O(\log n)\). Given a monotonious sequence, returns the rightmost node \(v_k\)
-- where \(f(v)\) holds for every \([0, i) (0 \le i \lt k)\).
--
-- @since 1.2.0.0
{-# INLINEABLE isplitMaxRightProdM #-}
isplitMaxRightProdM ::
  (PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq (PrimState m) f a ->
  -- | Root node
  P.Index ->
  -- | User predicate \(f(i, v_i)\) that takes the index and the monoid value
  -- | \(r\)
  (Int -> a -> m Bool) ->
  -- | (left, right) sequences where \(f\) holds for the left
  m (P.Index, P.Index)
isplitMaxRightProdM :: forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Index, Index)
isplitMaxRightProdM seq :: Seq (PrimState m) f a
seq@Seq {Int
MVector (PrimState m) f
MVector (PrimState m) a
MVector (PrimState m) Int
MVector (PrimState m) Bit
MVector (PrimState m) Index
Pool (PrimState m) ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool (PrimState m) ()
lSeq :: MVector (PrimState m) Index
rSeq :: MVector (PrimState m) Index
pSeq :: MVector (PrimState m) Index
sSeq :: MVector (PrimState m) Int
vSeq :: MVector (PrimState m) a
prodSeq :: MVector (PrimState m) a
revSeq :: MVector (PrimState m) Bit
lazySeq :: MVector (PrimState m) f
..} Index
root Int -> a -> m Bool
f
  | Index -> Bool
P.nullIndex Index
root = (Index, Index) -> m (Index, Index)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
P.undefIndex, Index
P.undefIndex)
  | Bool
otherwise = do
      ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ()) -> ST (PrimState m) () -> m ()
forall a b. (a -> b) -> a -> b
$ Seq (PrimState m) f a -> Index -> ST (PrimState m) ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootST Seq (PrimState m) f a
seq Index
root
      (!Int
_, !Index
c, !Index
_) <- Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Int, Index, Index)
forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Int, Index, Index)
imaxRightProdM Seq (PrimState m) f a
seq Index
root Int -> a -> m Bool
f
      if Index -> Bool
P.nullIndex Index
c
        then ST (PrimState m) (Index, Index) -> m (Index, Index)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Index, Index) -> m (Index, Index))
-> ST (PrimState m) (Index, Index) -> m (Index, Index)
forall a b. (a -> b) -> a -> b
$ do
          -- `f` does hot hold
          Seq (PrimState m) f a -> Index -> Bool -> ST (PrimState m) ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Bool -> ST s ()
splayST Seq (PrimState m) f a
seq Index
root Bool
True
          (Index, Index) -> ST (PrimState m) (Index, Index)
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
P.undefIndex, Index
root)
        else ST (PrimState m) (Index, Index) -> m (Index, Index)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Index, Index) -> m (Index, Index))
-> ST (PrimState m) (Index, Index) -> m (Index, Index)
forall a b. (a -> b) -> a -> b
$ do
          Seq (PrimState m) f a -> Index -> Bool -> ST (PrimState m) ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Bool -> ST s ()
splayST Seq (PrimState m) f a
seq Index
c Bool
True
          Index
right <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
          if Index -> Bool
P.nullIndex Index
right
            then do
              -- `f` holds for the whole sequence
              (Index, Index) -> ST (PrimState m) (Index, Index)
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
c, Index
P.undefIndex)
            else do
              -- `f` holds for part of the sequence. detach the right child
              MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
pSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
right) Index
P.undefIndex
              MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) Index
P.undefIndex
              Seq (PrimState m) f a -> Index -> ST (PrimState m) ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
updateNodeST Seq (PrimState m) f a
seq Index
c
              (Index, Index) -> ST (PrimState m) (Index, Index)
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
c, Index
right)

-- | Amortized \(O(\log n)\). Given a monotonious sequence, returns the rightmost node \(v\)
-- where \(f(v)\) holds for every \(v_i (0 \le i \lt k)\). Note that \(f\) works for a single
-- node, not a monoid product.
--
-- ==== Constraints
-- - The node must be a root.
--
-- @since 1.2.0.0
{-# INLINE imaxRightST #-}
imaxRightST ::
  (SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq s f a ->
  -- | Root node
  P.Index ->
  -- | User predicate \(f(i, v_i)\) that takes the index and the monoid value
  (Int -> a -> Bool) ->
  -- | (r, left, right)
  ST s (Int, P.Index, P.Index)
imaxRightST :: forall f a s.
(SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) =>
Seq s f a
-> Index -> (Int -> a -> Bool) -> ST s (Int, Index, Index)
imaxRightST Seq s f a
seq Index
root0 Int -> a -> Bool
f = ST (PrimState (ST s)) (Int, Index, Index)
-> ST s (Int, Index, Index)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState (ST s)) (Int, Index, Index)
 -> ST s (Int, Index, Index))
-> ST (PrimState (ST s)) (Int, Index, Index)
-> ST s (Int, Index, Index)
forall a b. (a -> b) -> a -> b
$ Seq (PrimState (ST s)) f a
-> Index -> (Int -> a -> ST s Bool) -> ST s (Int, Index, Index)
forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Int, Index, Index)
imaxRightM Seq s f a
Seq (PrimState (ST s)) f a
seq Index
root0 (\Int
i a
x -> Bool -> ST s Bool
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int -> a -> Bool
f Int
i a
x))

-- | Amortized \(O(\log n)\). Given a monotonious sequence, returns the rightmost node \(v_k\)
-- where \(f(v)\) holds for every \(v_i (0 \le i \le k)\). Note that \(f\) works for a single
-- node, not a monoid product.
--
-- ==== Constraints
-- - The node must be a root.
--
-- @since 1.2.0.0
{-# INLINEABLE imaxRightM #-}
imaxRightM ::
  (PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq (PrimState m) f a ->
  -- | Root node
  P.Index ->
  -- | User predicate \(f(i, v_i)\) that takes the index and the monoid value
  (Int -> a -> m Bool) ->
  -- | (r, left, right)
  m (Int, P.Index, P.Index)
imaxRightM :: forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Int, Index, Index)
imaxRightM seq :: Seq (PrimState m) f a
seq@Seq {Int
MVector (PrimState m) f
MVector (PrimState m) a
MVector (PrimState m) Int
MVector (PrimState m) Bit
MVector (PrimState m) Index
Pool (PrimState m) ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool (PrimState m) ()
lSeq :: MVector (PrimState m) Index
rSeq :: MVector (PrimState m) Index
pSeq :: MVector (PrimState m) Index
sSeq :: MVector (PrimState m) Int
vSeq :: MVector (PrimState m) a
prodSeq :: MVector (PrimState m) a
revSeq :: MVector (PrimState m) Bit
lazySeq :: MVector (PrimState m) f
..} Index
root0 Int -> a -> m Bool
f = do
  let inner :: Int -> Index -> Index -> Index -> m (Int, Index, Index)
inner Int
offset Index
parent Index
root Index
lastYes
        | Index -> Bool
P.nullIndex Index
root = (Int, Index, Index) -> m (Int, Index, Index)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
offset, Index
lastYes, Index
parent)
        | Bool
otherwise = do
            ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ()) -> ST (PrimState m) () -> m ()
forall a b. (a -> b) -> a -> b
$ Seq (PrimState m) f a -> Index -> ST (PrimState m) ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Index -> ST s ()
propNodeST Seq (PrimState m) f a
seq Index
root
            Index
l <- ST (PrimState m) Index -> m Index
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Index -> m Index)
-> ST (PrimState m) Index -> m Index
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
lSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
            a
v <- ST (PrimState m) a -> m a
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) a -> m a) -> ST (PrimState m) a -> m a
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) a
-> Int -> ST (PrimState m) a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) a
MVector (PrimState (ST (PrimState m))) a
vSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
            Int
pos <- ST (PrimState m) Int -> m Int
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Int -> m Int) -> ST (PrimState m) Int -> m Int
forall a b. (a -> b) -> a -> b
$ do
              if Index -> Bool
P.nullIndex Index
l
                then Int -> ST (PrimState m) Int
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
offset
                else (Int
offset +) (Int -> Int) -> ST (PrimState m) Int -> ST (PrimState m) Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState (ST (PrimState m))) Int
-> Int -> ST (PrimState m) Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Int
MVector (PrimState (ST (PrimState m))) Int
sSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
l)
            !Bool
b <- Int -> a -> m Bool
f Int
pos a
v
            if Bool
b
              then do
                Index
r <- ST (PrimState m) Index -> m Index
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Index -> m Index)
-> ST (PrimState m) Index -> m Index
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
rSeq (Int -> ST (PrimState m) Index) -> Int -> ST (PrimState m) Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root
                Int -> Index -> Index -> Index -> m (Int, Index, Index)
inner (Int
pos Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Index
root Index
r Index
root
              else do
                Int -> Index -> Index -> Index -> m (Int, Index, Index)
inner Int
offset Index
root Index
l Index
lastYes

  (!Int
r, !Index
yes, !Index
root') <- Int -> Index -> Index -> Index -> m (Int, Index, Index)
inner Int
0 Index
P.undefIndex Index
root0 Index
P.undefIndex
  ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ()) -> ST (PrimState m) () -> m ()
forall a b. (a -> b) -> a -> b
$ Seq (PrimState m) f a -> Index -> Bool -> ST (PrimState m) ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Bool -> ST s ()
splayST Seq (PrimState m) f a
seq Index
root' Bool
True
  (Int, Index, Index) -> m (Int, Index, Index)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
r, Index
yes, Index
root')

-- | Amortized \(O(\log n)\). Given a monotonious sequence, returns the rightmost node \(v_k\)
-- where \(f(v)\) holds for every \([0, i) (0 \le i \lt k)\).
--
-- ==== Constraints
-- - The node must be a root.
--
-- @since 1.2.0.0
{-# INLINE imaxRightProdST #-}
imaxRightProdST ::
  (SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq s f a ->
  -- | Root node
  P.Index ->
  -- | User predicate \(f(i, v_0 \dots v_i)\) that takes the index and the monoid value
  (Int -> a -> Bool) ->
  -- | (ilowerBound, rightmost node, new root)
  ST s (Int, P.Index, P.Index)
imaxRightProdST :: forall f a s.
(SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) =>
Seq s f a
-> Index -> (Int -> a -> Bool) -> ST s (Int, Index, Index)
imaxRightProdST Seq s f a
seq Index
root0 Int -> a -> Bool
f = Seq (PrimState (ST s)) f a
-> Index -> (Int -> a -> ST s Bool) -> ST s (Int, Index, Index)
forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Int, Index, Index)
imaxRightProdM Seq s f a
Seq (PrimState (ST s)) f a
seq Index
root0 (\Int
i a
x -> Bool -> ST s Bool
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int -> a -> Bool
f Int
i a
x))

-- | Amortized \(O(\log n)\). Given a monotonious sequence, returns the rightmost node \(v_k\)
-- where \(f(v)\) holds for every \([0, i) (0 \le i \lt k)\).
--
-- ==== Constraints
-- - The node must be a root.
--
-- @since 1.2.0.0
{-# INLINEABLE imaxRightProdM #-}
imaxRightProdM ::
  (PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq (PrimState m) f a ->
  -- | Root node
  P.Index ->
  -- | User predicate \(f(i, v_0 \dots v_i)\) that takes the index and the monoid value
  (Int -> a -> m Bool) ->
  -- | (ilowerBound, rightmost node, new root)
  m (Int, P.Index, P.Index)
imaxRightProdM :: forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Int, Index, Index)
imaxRightProdM seq :: Seq (PrimState m) f a
seq@Seq {Int
MVector (PrimState m) f
MVector (PrimState m) a
MVector (PrimState m) Int
MVector (PrimState m) Bit
MVector (PrimState m) Index
Pool (PrimState m) ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool (PrimState m) ()
lSeq :: MVector (PrimState m) Index
rSeq :: MVector (PrimState m) Index
pSeq :: MVector (PrimState m) Index
sSeq :: MVector (PrimState m) Int
vSeq :: MVector (PrimState m) a
prodSeq :: MVector (PrimState m) a
revSeq :: MVector (PrimState m) Bit
lazySeq :: MVector (PrimState m) f
..} Index
root0 Int -> a -> m Bool
f = do
  let inner :: a -> Int -> Index -> Index -> Index -> m (Int, Index, Index)
inner !a
acc Int
offset Index
parent Index
root Index
lastYes
        | Index -> Bool
P.nullIndex Index
root = (Int, Index, Index) -> m (Int, Index, Index)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
offset, Index
lastYes, Index
parent)
        | Bool
otherwise = do
            ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ()) -> ST (PrimState m) () -> m ()
forall a b. (a -> b) -> a -> b
$ Seq (PrimState m) f a -> Index -> ST (PrimState m) ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Index -> ST s ()
propNodeST Seq (PrimState m) f a
seq Index
root
            Index
l <- ST (PrimState m) Index -> m Index
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Index -> m Index)
-> ST (PrimState m) Index -> m Index
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
lSeq (Int -> ST (PrimState m) Index) -> Int -> ST (PrimState m) Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root
            Int
pos <- ST (PrimState m) Int -> m Int
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Int -> m Int) -> ST (PrimState m) Int -> m Int
forall a b. (a -> b) -> a -> b
$ do
              if Index -> Bool
P.nullIndex Index
l
                then Int -> ST (PrimState m) Int
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
offset
                else (Int
offset +) (Int -> Int) -> ST (PrimState m) Int -> ST (PrimState m) Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState (ST (PrimState m))) Int
-> Int -> ST (PrimState m) Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Int
MVector (PrimState (ST (PrimState m))) Int
sSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
l)
            -- [0, pos]
            a
prodM <- ST (PrimState m) a -> m a
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) a -> m a) -> ST (PrimState m) a -> m a
forall a b. (a -> b) -> a -> b
$ do
              -- detach right child (temporarily) and read the product
              Index
rootR <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
VGM.exchange MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root) Index
P.undefIndex
              Seq (PrimState m) f a -> Index -> ST (PrimState m) ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
updateNodeST Seq (PrimState m) f a
seq Index
root
              a
prodRoot <- MVector (PrimState (ST (PrimState m))) a
-> Int -> ST (PrimState m) a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) a
MVector (PrimState (ST (PrimState m))) a
prodSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
              -- attach the right child again
              MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root) Index
rootR
              Seq (PrimState m) f a -> Index -> ST (PrimState m) ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
updateNodeST Seq (PrimState m) f a
seq Index
root
              a -> ST (PrimState m) a
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a -> ST (PrimState m) a) -> a -> ST (PrimState m) a
forall a b. (a -> b) -> a -> b
$! a
acc a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
prodRoot
            !Bool
b <- Int -> a -> m Bool
f Int
pos a
prodM
            if Bool
b
              then do
                Index
r <- ST (PrimState m) Index -> m Index
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Index -> m Index)
-> ST (PrimState m) Index -> m Index
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
rSeq (Int -> ST (PrimState m) Index) -> Int -> ST (PrimState m) Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root
                a -> Int -> Index -> Index -> Index -> m (Int, Index, Index)
inner a
prodM (Int
pos Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Index
root Index
r Index
root
              else do
                a -> Int -> Index -> Index -> Index -> m (Int, Index, Index)
inner a
acc Int
offset Index
root Index
l Index
lastYes

  (!Int
r, !Index
yes, !Index
root') <- a -> Int -> Index -> Index -> Index -> m (Int, Index, Index)
inner a
forall a. Monoid a => a
mempty Int
0 Index
P.undefIndex Index
root0 Index
P.undefIndex
  ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ()) -> ST (PrimState m) () -> m ()
forall a b. (a -> b) -> a -> b
$ Seq (PrimState m) f a -> Index -> Bool -> ST (PrimState m) ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Bool -> ST s ()
splayST Seq (PrimState m) f a
seq Index
root' Bool
True
  (Int, Index, Index) -> m (Int, Index, Index)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
r, Index
yes, Index
root')

-- -------------------------------------------------------------------------------------------------
-- Conversions
-- -------------------------------------------------------------------------------------------------

-- | Amortized \(O(n)\). Returns the sequence of monoid values.
--
-- @since 1.2.0.0
{-# INLINEABLE freezeST #-}
freezeST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> ST s (VU.Vector a)
freezeST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> ST s (Vector a)
freezeST seq :: Seq s f a
seq@Seq {MVector s Int
sSeq :: forall s f a. Seq s f a -> MVector s Int
sSeq :: MVector s Int
sSeq, MVector s Index
lSeq :: forall s f a. Seq s f a -> MVector s Index
lSeq :: MVector s Index
lSeq, MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: MVector s Index
rSeq, MVector s a
vSeq :: forall s f a. Seq s f a -> MVector s a
vSeq :: MVector s a
vSeq} Index
root0
  | Index -> Bool
P.nullIndex Index
root0 = Vector a -> ST s (Vector a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Vector a
forall a. Unbox a => Vector a
VU.empty
  | Bool
otherwise = do
      Int
size <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root0)
      MVector s a
res <- Int -> ST s (MVector (PrimState (ST s)) a)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
size
      let inner :: Int -> Index -> ST s Int
inner Int
i Index
root
            | Index -> Bool
P.nullIndex Index
root = Int -> ST s Int
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
i
            | Bool
otherwise = do
                -- visit from left to right
                Seq s f a -> Index -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Index -> ST s ()
propNodeST Seq s f a
seq Index
root
                Int
i' <- Int -> Index -> ST s Int
inner Int
i (Index -> ST s Int) -> ST s Index -> ST s Int
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
                a
vx <- MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
vSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
                MVector (PrimState (ST s)) a -> Int -> a -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s a
MVector (PrimState (ST s)) a
res Int
i' a
vx
                Int -> Index -> ST s Int
inner (Int
i' Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (Index -> ST s Int) -> ST s Index -> ST s Int
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
      Int
_ <- Int -> Index -> ST s Int
inner Int
0 Index
root0
      MVector (PrimState (ST s)) a -> ST s (Vector a)
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> m (Vector a)
VU.unsafeFreeze MVector s a
MVector (PrimState (ST s)) a
res

-- -------------------------------------------------------------------------------------------------
-- Internals and node methods
-- -------------------------------------------------------------------------------------------------

-- | Amortized \(O(\log n)\).
--
-- @since 1.2.1.0
{-# INLINEABLE splitMaxRightWithST #-}
splitMaxRightWithST ::
  (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq s f a ->
  -- | Root node
  P.Index ->
  -- | User predicate \(f(i)\)
  (P.Index -> ST s Bool) ->
  -- | (left, right) sequences where \(f\) holds for the left
  ST s (P.Index, P.Index)
splitMaxRightWithST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> (Index -> ST s Bool) -> ST s (Index, Index)
splitMaxRightWithST seq :: Seq s f a
seq@Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
root Index -> ST s Bool
f
  | Index -> Bool
P.nullIndex Index
root = (Index, Index) -> ST s (Index, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
P.undefIndex, Index
P.undefIndex)
  | Bool
otherwise = do
      Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootST Seq s f a
seq Index
root
      (!Index
c, !Index
_) <- Seq s f a -> Index -> (Index -> ST s Bool) -> ST s (Index, Index)
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> (Index -> ST s Bool) -> ST s (Index, Index)
maxRightWithST Seq s f a
seq Index
root Index -> ST s Bool
f
      if Index -> Bool
P.nullIndex Index
c
        then do
          -- `f` does hot hold
          Seq s f a -> Index -> Bool -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Bool -> ST s ()
splayST Seq s f a
seq Index
root Bool
True
          (Index, Index) -> ST s (Index, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
P.undefIndex, Index
root)
        else do
          Seq s f a -> Index -> Bool -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Bool -> ST s ()
splayST Seq s f a
seq Index
c Bool
True
          Index
right <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
          if Index -> Bool
P.nullIndex Index
right
            then do
              -- `f` holds for the whole sequence
              (Index, Index) -> ST s (Index, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
c, Index
P.undefIndex)
            else do
              -- `f` holds for part of the sequence. detach the right child
              MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
right) Index
P.undefIndex
              MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) Index
P.undefIndex
              Seq s f a -> Index -> ST s ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
updateNodeST Seq s f a
seq Index
c
              (Index, Index) -> ST s (Index, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
c, Index
right)

-- | Amortized \(O(\log n)\). Given a monotonious sequence, returns the rightmost node \(v_k\)
-- where \(f(v)\) holds for every \([0, i) (0 \le i \lt k)\).
--
-- ==== Constraints
-- - The node must be a root.
--
-- @since 1.2.1.0
{-# INLINEABLE maxRightWithST #-}
maxRightWithST ::
  (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq s f a ->
  -- | Root node
  P.Index ->
  -- | User predicate
  (P.Index -> ST s Bool) ->
  -- | (rightmost node, new root)
  ST s (P.Index, P.Index)
maxRightWithST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> (Index -> ST s Bool) -> ST s (Index, Index)
maxRightWithST seq :: Seq s f a
seq@Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
root0 Index -> ST s Bool
f = do
  let inner :: Index -> Index -> Index -> ST s (Index, Index)
inner Index
parent Index
lastYes Index
root
        | Index -> Bool
P.nullIndex Index
root = (Index, Index) -> ST s (Index, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
lastYes, Index
parent)
        | Bool
otherwise = do
            ST (PrimState (ST s)) () -> ST s ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState (ST s)) () -> ST s ())
-> ST (PrimState (ST s)) () -> ST s ()
forall a b. (a -> b) -> a -> b
$ Seq s f a -> Index -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Index -> ST s ()
propNodeST Seq s f a
seq Index
root
            !Bool
b <- Index -> ST s Bool
f Index
root
            if Bool
b
              then Index -> Index -> Index -> ST s (Index, Index)
inner Index
root Index
root (Index -> ST s (Index, Index)) -> ST s Index -> ST s (Index, Index)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
              else Index -> Index -> Index -> ST s (Index, Index)
inner Index
root Index
lastYes (Index -> ST s (Index, Index)) -> ST s Index -> ST s (Index, Index)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
  (!Index
yes, !Index
root') <- Index -> Index -> Index -> ST s (Index, Index)
inner Index
P.undefIndex Index
P.undefIndex Index
root0
  ST (PrimState (ST s)) () -> ST s ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState (ST s)) () -> ST s ())
-> ST (PrimState (ST s)) () -> ST s ()
forall a b. (a -> b) -> a -> b
$ Seq s f a -> Index -> Bool -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq s f a -> Index -> Bool -> ST s ()
splayST Seq s f a
seq Index
root' Bool
True
  (Index, Index) -> ST s (Index, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Index
yes, Index
root')

-- NOTE(pref): inlining node functions are important for the speed

-- | \(O(1)\) Recomputes the node size and the monoid product.
--
-- @since 1.2.1.0
{-# INLINEABLE updateNodeST #-}
updateNodeST :: (Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> ST s ()
updateNodeST :: forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
updateNodeST Seq {Int
MVector s a
MVector s f
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
i = do
  Index
l <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i)
  Index
r <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i)
  a
prodM <- MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
vSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i)
  (!Int
size', !a
prod') <-
    if Index -> Bool
P.nullIndex Index
l
      then (Int, a) -> ST s (Int, a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
1, a
prodM)
      else do
        Int
sizeL <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
l)
        a
prodL <- MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
prodSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
l)
        (Int, a) -> ST s (Int, a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
sizeL Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1, a
prodL a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
prodM)
  (!Int
size'', !a
prod'') <-
    if Index -> Bool
P.nullIndex Index
r
      then (Int, a) -> ST s (Int, a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
size', a
prod')
      else do
        Int
sizeR <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
r)
        a
prodR <- MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
prodSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
r)
        (Int, a) -> ST s (Int, a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
size' Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
sizeR, a
prod' a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
prodR)
  MVector (PrimState (ST s)) Int -> Int -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) Int
size''
  MVector (PrimState (ST s)) a -> Int -> a -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s a
MVector (PrimState (ST s)) a
prodSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) a
prod''

-- | \(O(1)\) Writes to the monoid value of a node.
--
-- @since 1.2.1.0
{-# INLINE writeNodeST #-}
writeNodeST :: (Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> a -> ST s ()
writeNodeST :: forall a s f.
(Monoid a, Unbox a) =>
Seq s f a -> Index -> a -> ST s ()
writeNodeST seq :: Seq s f a
seq@Seq {Int
MVector s a
MVector s f
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
root a
v = do
  Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootST Seq s f a
seq Index
root
  MVector (PrimState (ST s)) a -> Int -> a -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s a
MVector (PrimState (ST s)) a
vSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root) a
v
  Seq s f a -> Index -> ST s ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
updateNodeST Seq s f a
seq Index
root

-- | \(O(1)\) Modifies the monoid value of a node.
--
-- @since 1.2.1.0
{-# INLINE modifyNodeST #-}
modifyNodeST :: (HasCallStack, Monoid a, VU.Unbox a) => Seq s f a -> (a -> a) -> P.Index -> ST s ()
modifyNodeST :: forall a s f.
(HasCallStack, Monoid a, Unbox a) =>
Seq s f a -> (a -> a) -> Index -> ST s ()
modifyNodeST seq :: Seq s f a
seq@Seq {Int
MVector s a
MVector s f
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} a -> a
f Index
root = do
  Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootST Seq s f a
seq Index
root
  MVector (PrimState (ST s)) a -> (a -> a) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
VGM.modify MVector s a
MVector (PrimState (ST s)) a
vSeq a -> a
f (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root
  Seq s f a -> Index -> ST s ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
updateNodeST Seq s f a
seq Index
root

-- | \(O(1)\) Exchanges the monoid value of a node.
--
-- @since 1.2.1.0
{-# INLINE exchangeNodeST #-}
exchangeNodeST :: (HasCallStack, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> a -> ST s a
exchangeNodeST :: forall a s f.
(HasCallStack, Monoid a, Unbox a) =>
Seq s f a -> Index -> a -> ST s a
exchangeNodeST seq :: Seq s f a
seq@Seq {Int
MVector s a
MVector s f
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
root a
v = do
  Seq s f a -> Index -> ST s ()
forall s f a. HasCallStack => Seq s f a -> Index -> ST s ()
assertRootST Seq s f a
seq Index
root
  a
res <- MVector (PrimState (ST s)) a -> Int -> a -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
VGM.exchange MVector s a
MVector (PrimState (ST s)) a
vSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root) a
v
  Seq s f a -> Index -> ST s ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
updateNodeST Seq s f a
seq Index
root
  a -> ST s a
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
res

-- | \(O(1)\) Swaps the left and the right children.
{-# INLINE swapLrNodeST #-}
swapLrNodeST :: Seq s f a -> P.Index -> ST s ()
swapLrNodeST :: forall s v a. Seq s v a -> Index -> ST s ()
swapLrNodeST Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
i = do
  MVector (PrimState (ST s)) Index
-> (Index -> ST s Index) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
VGM.modifyM MVector s Index
MVector (PrimState (ST s)) Index
lSeq (MVector (PrimState (ST s)) Index -> Int -> Index -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
VGM.exchange MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i)) (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i)

-- | \(O(1)\) Reverses the left and the right children, lazily and recursively.
{-# INLINE reverseNodeST #-}
reverseNodeST :: Seq s f a -> P.Index -> ST s ()
reverseNodeST :: forall s v a. Seq s v a -> Index -> ST s ()
reverseNodeST seq :: Seq s f a
seq@Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
i = do
  Seq s f a -> Index -> ST s ()
forall s v a. Seq s v a -> Index -> ST s ()
swapLrNodeST Seq s f a
seq Index
i
  -- lazily propagate new reverse or cancel:
  MVector (PrimState (ST s)) Bit -> (Bit -> Bit) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
VGM.modify MVector s Bit
MVector (PrimState (ST s)) Bit
revSeq (Bit -> Bit -> Bit
forall a. Bits a => a -> a -> a
xor (Bool -> Bit
Bit Bool
True)) (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i

-- | Amortized \(O(\log n)\). Propgates the lazily propagated values on a node.
--
-- @since 1.2.1.0
{-# INLINE propNodeST #-}
-- NOTE(pref): Although this function is large, inlining it needs for the speed.
propNodeST :: (HasCallStack, SegAct f a, Eq f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> ST s ()
propNodeST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Index -> ST s ()
propNodeST seq :: Seq s f a
seq@Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
i = do
  -- action
  f
act <- MVector (PrimState (ST s)) f -> Int -> f -> ST s f
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
VGM.exchange MVector s f
MVector (PrimState (ST s)) f
lazySeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) f
forall a. Monoid a => a
mempty
  -- this is where `Eq f` is required:
  Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (f
act f -> f -> Bool
forall a. Eq a => a -> a -> Bool
/= f
forall a. Monoid a => a
mempty) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
    Index
l <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i
    Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
l) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
      Seq s f a -> Index -> f -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Index -> f -> ST s ()
applyNodeST Seq s f a
seq Index
l f
act
    Index
r <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i
    Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
r) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
      Seq s f a -> Index -> f -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Index -> f -> ST s ()
applyNodeST Seq s f a
seq Index
r f
act

  -- reverse
  Bit Bool
b <- MVector (PrimState (ST s)) Bit -> Int -> Bit -> ST s Bit
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
VGM.exchange MVector s Bit
MVector (PrimState (ST s)) Bit
revSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) (Bool -> Bit
Bit Bool
False)
  Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when Bool
b (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
    Index
l <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
lSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i
    Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
l) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
      -- propagate new reverse or cancel:
      Seq s f a -> Index -> ST s ()
forall s v a. Seq s v a -> Index -> ST s ()
reverseNodeST Seq s f a
seq Index
l
    Index
r <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
rSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i
    Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
r) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
      -- propagate new reverse or cancel:
      Seq s f a -> Index -> ST s ()
forall s v a. Seq s v a -> Index -> ST s ()
reverseNodeST Seq s f a
seq Index
r

-- | Amortized \(O(\log n)\). Propagetes from the root to the given node.
{-# INLINE propNodeFromRootST #-}
propNodeFromRootST :: (HasCallStack, SegAct f a, VU.Unbox f, VU.Unbox a, Monoid a) => Seq s f a -> P.Index -> ST s ()
propNodeFromRootST :: forall f a s.
(HasCallStack, SegAct f a, Unbox f, Unbox a, Monoid a) =>
Seq s f a -> Index -> ST s ()
propNodeFromRootST Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} = Index -> ST s ()
inner
  where
    inner :: Index -> ST s ()
inner Index
i = do
      Index
p <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
pSeq (Int -> ST s Index) -> Int -> ST s Index
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i
      Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
p) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
        Index -> ST s ()
inner Index
p
      Index -> ST s ()
inner Index
i

-- | Amortized \(O(\log n)\). Propgates at a node.
--
-- @since 1.2.1.0
{-# INLINE applyNodeST #-}
applyNodeST :: (HasCallStack, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => Seq s f a -> P.Index -> f -> ST s ()
applyNodeST :: forall f a s.
(HasCallStack, SegAct f a, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Index -> f -> ST s ()
applyNodeST Seq {Int
MVector s f
MVector s a
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
nSeq :: forall s f a. Seq s f a -> Int
poolSeq :: forall s f a. Seq s f a -> Pool s ()
lSeq :: forall s f a. Seq s f a -> MVector s Index
rSeq :: forall s f a. Seq s f a -> MVector s Index
pSeq :: forall s f a. Seq s f a -> MVector s Index
sSeq :: forall s f a. Seq s f a -> MVector s Int
vSeq :: forall s f a. Seq s f a -> MVector s a
prodSeq :: forall s f a. Seq s f a -> MVector s a
revSeq :: forall s f a. Seq s f a -> MVector s Bit
lazySeq :: forall s f a. Seq s f a -> MVector s f
nSeq :: Int
poolSeq :: Pool s ()
lSeq :: MVector s Index
rSeq :: MVector s Index
pSeq :: MVector s Index
sSeq :: MVector s Int
vSeq :: MVector s a
prodSeq :: MVector s a
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} Index
i f
act = do
  Int
len <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
sSeq (Int -> ST s Int) -> Int -> ST s Int
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i
  MVector (PrimState (ST s)) a -> (a -> a) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
VGM.modify MVector s a
MVector (PrimState (ST s)) a
vSeq (f -> a -> a
forall f a. SegAct f a => f -> a -> a
segAct f
act) (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i
  MVector (PrimState (ST s)) a -> (a -> a) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
VGM.modify MVector s a
MVector (PrimState (ST s)) a
prodSeq (Int -> f -> a -> a
forall f a. SegAct f a => Int -> f -> a -> a
segActWithLength Int
len f
act) (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i
  MVector (PrimState (ST s)) f -> (f -> f) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
VGM.modify MVector s f
MVector (PrimState (ST s)) f
lazySeq (f
act <>) (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i