{-# LANGUAGE DerivingVia #-}
{-# LANGUAGE TypeFamilies #-}

-- | Dynamic sequence of monoid values with monoid actions on them through the `SegAct` instance.
--
-- ==== Performance
-- This module is __slow__ as an ordinary dynamic sequence. Consider using another module if you
-- don't need monoid products.
--
-- ==== __Example__
--
-- Create a `Seq` storage of length \(10\):
--
-- >>> import AtCoder.Extra.Monoid.RangeAdd qualified as RangeAdd
-- >>> import AtCoder.Extra.Seq qualified as Seq
-- >>> import Data.Semigroup (Sum (..))
-- >>> import Data.Vector.Unboxed qualified as VU
-- >>> seq <- Seq.new @_ @(RangeAdd.RangeAdd (Sum Int)) @(Sum Int) 10
--
-- Allocate a sequence of \(0, 1, 2, 3\):
--
-- >>> handle <- Seq.newSeq seq (VU.fromList [0, 1, 2, 3])
--
-- Get monoid products:
--
-- >>> Seq.prodAll seq handle
-- Sum {getSum = 6}
--
-- >>> Seq.prod seq handle 1 3
-- Sum {getSum = 3}
--
-- `read`, `write`, `modify` and `exchange` are available:
--
-- >>> -- [0, 1, 2, 3] -> [0, 10, 2, 30]
-- >>> Seq.write seq handle 3 30
-- >>> Seq.modify seq handle (* 10) 1
--
-- Actions can be performed with `SegAct` instances:
--
-- >>> -- [0, 10, 2, 30] -> [0, 20, 12, 40]
-- >>> Seq.applyIn seq handle 1 4 (RangeAdd.new 10)
-- >>> Seq.prod seq handle 1 4
-- Sum {getSum = 72}
--
-- The sequence can be reversed if the action type is commutative:
--
-- >>> Seq.reverse seq handle 0 4
-- >>> VU.map getSum <$> Seq.freeze seq handle
-- [40,12,20,0]
--
-- The sequence is dynamic and new elements can be inserted or deleted:
--
-- >>> -- [40, 12, 20, 0] -> [40, 33, 12, 20, 0]
-- >>> Seq.insert seq handle 1 (Sum 33)
-- >>> -- [40, 33, 12, 20, 0] -> [40, 33, 12, 0]
-- >>> Seq.delete seq handle 3
-- Sum {getSum = 20}
--
-- >>> VU.map getSum <$> Seq.freeze seq handle
-- [40,33,12,0]
--
-- The `Seq` storage can store multiple sequences:
--
-- >>> handle2 <- Seq.newSeq seq (VU.generate 2 Sum)
-- >>> VU.map getSum <$> Seq.freeze seq handle2
-- [0,1]
--
-- Merge/split operations are available. `merge` functions mutate the given @handle@ to be the
-- merged sequence handle:
--
-- >>> Seq.merge seq handle handle2
-- >>> VU.map getSum <$> Seq.freeze seq handle
-- [40,33,12,0,0,1]
--
-- `split` functions mutate the given @handle@ to be the leftmost one and returns right sequence
-- handles:
--
-- >>> (handleM, handleR) <- Seq.split3 seq handle 2 4
-- >>> VU.map getSum <$> Seq.freeze seq handle
-- [40,33]
--
-- >>> VU.map getSum <$> Seq.freeze seq handleM
-- [12,0]
--
-- >>> VU.map getSum <$> Seq.freeze seq handleR
-- [0,1]
--
-- Bisection methods are available for monoid values and their products:
--
-- >>> Seq.reset seq
-- >>> handle <- Seq.newSeq seq $ VU.generate 10 Sum
-- >>> Seq.ilowerBound seq handle (\_ x -> x < 5)
-- 5
--
-- >>> Seq.ilowerBoundProd seq handle (\_ x -> x < 5)
-- 3
--
-- @since 1.2.0.0
module AtCoder.Extra.Seq
  ( -- * Seq
    Seq.Seq (..),

    -- * Handle (re-exports)
    Handle (..),
    -- TODO: hide
    newHandle,
    nullHandle,
    invalidateHandle,

    -- * Re-exports
    SegAct (..),

    -- * Constructors
    new,
    reset,
    free,
    newNode,
    newSeq,

    -- * Metadata
    capacity,
    length,

    -- * Merge/split
    merge,
    merge3,
    merge4,
    split,
    split3,
    split4,
    splitLr,
    -- slice, -- because it returns a raw `P.Index`, use the `Raw.sliceST` instead

    -- * Read/write
    read,
    readMaybe,
    write,
    modify,
    exchange,

    -- * Products
    prod,
    prodMaybe,
    prodAll,

    -- * Applications
    applyIn,
    applyToRoot,
    reverse,

    -- * Insert/delete
    insert,
    delete,
    delete_,
    detach,

    -- * Bisection methods

    -- ** C++-like
    ilowerBound,
    ilowerBoundM,
    ilowerBoundProd,
    ilowerBoundProdM,

    -- ** Splits
    isplitMaxRight,
    isplitMaxRightM,
    isplitMaxRightProd,
    isplitMaxRightProdM,

    -- * Conversions
    freeze,
  )
where

import AtCoder.Extra.Pool (Handle (..), invalidateHandle, newHandle, nullHandle)
import AtCoder.Extra.Pool qualified as P
import AtCoder.Extra.Seq.Raw (Seq (..))
import AtCoder.Extra.Seq.Raw qualified as Seq
import AtCoder.LazySegTree (SegAct (..))
import Control.Monad.Primitive (PrimMonad, PrimState, stToPrim)
import Data.Vector.Generic.Mutable qualified as VGM
import Data.Vector.Unboxed qualified as VU
import GHC.Stack (HasCallStack)
import Prelude hiding (length, read, reverse, seq)

-- | \(O(n)\) Creates a new `Seq` of length \(n\).
--
-- @since 1.2.0.0
{-# INLINE new #-}
new :: (PrimMonad m, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Int -> m (Seq (PrimState m) f a)
new :: forall (m :: * -> *) f a.
(PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) =>
Int -> m (Seq (PrimState m) f a)
new Int
n = ST (PrimState m) (Seq (PrimState m) f a)
-> m (Seq (PrimState m) f a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Seq (PrimState m) f a)
 -> m (Seq (PrimState m) f a))
-> ST (PrimState m) (Seq (PrimState m) f a)
-> m (Seq (PrimState m) f a)
forall a b. (a -> b) -> a -> b
$ Int -> ST (PrimState m) (Seq (PrimState m) f a)
forall f a s.
(Monoid f, Unbox f, Monoid a, Unbox a) =>
Int -> ST s (Seq s f a)
Seq.newST Int
n

-- | \(O(1)\) Clears the sequence storage. All the handles must not be used again.
--
-- @since 1.2.0.0
{-# INLINE reset #-}
reset :: (PrimMonad m) => Seq (PrimState m) f a -> m ()
reset :: forall (m :: * -> *) f a.
PrimMonad m =>
Seq (PrimState m) f a -> m ()
reset Seq (PrimState m) f a
seq = 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 -> ST (PrimState m) ()
forall s f a. Seq s f a -> ST s ()
Seq.resetST Seq (PrimState m) f a
seq

-- | \(O(1)\) Allocates a new sequence of length \(1\).
--
-- @since 1.2.0.0
{-# INLINE newNode #-}
newNode :: (HasCallStack, PrimMonad m, Monoid f, VU.Unbox f, VU.Unbox a) => Seq (PrimState m) f a -> a -> m (Handle (PrimState m))
newNode :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, Monoid f, Unbox f, Unbox a) =>
Seq (PrimState m) f a -> a -> m (Handle (PrimState m))
newNode Seq (PrimState m) f a
seq a
x = ST (PrimState m) (Handle (PrimState m)) -> m (Handle (PrimState m))
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Handle (PrimState m))
 -> m (Handle (PrimState m)))
-> ST (PrimState m) (Handle (PrimState m))
-> m (Handle (PrimState m))
forall a b. (a -> b) -> a -> b
$ Index -> ST (PrimState m) (Handle (PrimState m))
Index -> ST (PrimState m) (Handle (PrimState (ST (PrimState m))))
forall (m :: * -> *).
PrimMonad m =>
Index -> m (Handle (PrimState m))
newHandle (Index -> ST (PrimState m) (Handle (PrimState m)))
-> ST (PrimState m) Index
-> ST (PrimState m) (Handle (PrimState m))
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Seq (PrimState m) f a -> a -> ST (PrimState m) Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Unbox a) =>
Seq s f a -> a -> ST s Index
Seq.newNodeST Seq (PrimState m) f a
seq a
x

-- | \(O(n)\) Allocates a new sequence.
--
-- @since 1.2.0.0
{-# INLINE newSeq #-}
newSeq :: (HasCallStack, PrimMonad m, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> VU.Vector a -> m (Handle (PrimState m))
newSeq :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a -> Vector a -> m (Handle (PrimState m))
newSeq Seq (PrimState m) f a
seq !Vector a
xs = ST (PrimState m) (Handle (PrimState m)) -> m (Handle (PrimState m))
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Handle (PrimState m))
 -> m (Handle (PrimState m)))
-> ST (PrimState m) (Handle (PrimState m))
-> m (Handle (PrimState m))
forall a b. (a -> b) -> a -> b
$ Index -> ST (PrimState m) (Handle (PrimState m))
Index -> ST (PrimState m) (Handle (PrimState (ST (PrimState m))))
forall (m :: * -> *).
PrimMonad m =>
Index -> m (Handle (PrimState m))
newHandle (Index -> ST (PrimState m) (Handle (PrimState m)))
-> ST (PrimState m) Index
-> ST (PrimState m) (Handle (PrimState m))
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Seq (PrimState m) f a -> Vector a -> ST (PrimState m) Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Vector a -> ST s Index
Seq.newSeqST Seq (PrimState m) f a
seq Vector a
xs

-- | \(O(n)\) Frees a sequence and invalidates the handle.
--
-- @since 1.2.0.0
{-# INLINE free #-}
free :: (PrimMonad m, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> m ()
free :: forall (m :: * -> *) a f.
(PrimMonad m, Unbox a) =>
Seq (PrimState m) f a -> Handle (PrimState m) -> m ()
free Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
handle) = 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
$ do
  Index
c0 <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
handle Int
0
  Seq (PrimState m) f a -> Index -> ST (PrimState m) ()
forall a s f. Unbox a => Seq s f a -> Index -> ST s ()
Seq.freeSubtreeST Seq (PrimState m) f a
seq Index
c0
  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
handle Int
0 Index
P.undefIndex

-- -------------------------------------------------------------------------------------------------
-- Meta
-- -------------------------------------------------------------------------------------------------

-- | \(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
Seq.capacity

-- | \(O(1)\) Returns the length of the sequence.
--
-- @since 1.2.1.0
{-# INLINE length #-}
length :: (PrimMonad m) => Seq (PrimState m) f a -> Handle (PrimState m) -> m Int
length :: forall (m :: * -> *) f a.
PrimMonad m =>
Seq (PrimState m) f a -> Handle (PrimState m) -> m Int
length Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
handle) = 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
  Index
i <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
handle Int
0
  Seq (PrimState m) f a -> Index -> ST (PrimState m) Int
forall s f a. Seq s f a -> Index -> ST s Int
Seq.lengthST Seq (PrimState m) f a
seq Index
i

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

-- | Amortized \(O(\log n)\). Merges two sequences \(l, r\) into one in the given order, ignoring
-- empty sequences. The right sequence handle will be invalidated.
--
-- @since 1.2.0.0
{-# INLINE merge #-}
merge :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Handle (PrimState m) -> m ()
merge :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a
-> Handle (PrimState m) -> Handle (PrimState m) -> m ()
merge Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
l) (Handle MVector (PrimState m) Index
r) = 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
$ do
  Index
lRoot <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
l Int
0
  Index
rRoot <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
r Int
0
  Index
root' <- Seq (PrimState m) f a -> Index -> Index -> ST (PrimState m) 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
Seq.mergeST Seq (PrimState m) f a
seq Index
lRoot Index
rRoot
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
l Int
0 Index
root'
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
r Int
0 Index
P.undefIndex

-- | Amortized \(O(\log n)\). Merges three sequences \(l, m, r\) into one in the given order,
-- ignoring empty sequences. All handles, except for the leftmost one, will be invalidated.
--
-- @since 1.2.0.0
{-# INLINE merge3 #-}
merge3 :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Handle (PrimState m) -> Handle (PrimState m) -> m ()
merge3 :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a
-> Handle (PrimState m)
-> Handle (PrimState m)
-> Handle (PrimState m)
-> m ()
merge3 Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hA) (Handle MVector (PrimState m) Index
hB) (Handle MVector (PrimState m) Index
hC) = 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
$ do
  Index
a <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hA Int
0
  Index
b <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hB Int
0
  Index
c <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hC Int
0
  Index
root' <- Seq (PrimState m) f a
-> Index -> Index -> Index -> ST (PrimState m) 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
Seq.merge3ST Seq (PrimState m) f a
seq Index
a Index
b Index
c
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hA Int
0 Index
root'
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hB Int
0 Index
P.undefIndex
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hC Int
0 Index
P.undefIndex

-- | Amortized \(O(\log n)\). Merges four sequences \(a, b, c, d\) into one in the given order,
-- ignoring empty sequences. All handles, except for the leftmost one, will be invalidated.
--
-- ==== Constraints
-- - The vertices must be roots.
--
-- @since 1.2.0.0
{-# INLINE merge4 #-}
merge4 :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Handle (PrimState m) -> Handle (PrimState m) -> Handle (PrimState m) -> m ()
merge4 :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a
-> Handle (PrimState m)
-> Handle (PrimState m)
-> Handle (PrimState m)
-> Handle (PrimState m)
-> m ()
merge4 Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hA) (Handle MVector (PrimState m) Index
hB) (Handle MVector (PrimState m) Index
hC) (Handle MVector (PrimState m) Index
hD) = 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
$ do
  Index
a <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hA Int
0
  Index
b <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hB Int
0
  Index
c <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hC Int
0
  Index
d <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hC Int
0
  Index
root' <- Seq (PrimState m) f a
-> Index -> Index -> Index -> Index -> ST (PrimState m) 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 -> Index -> ST s Index
Seq.merge4ST Seq (PrimState m) f a
seq Index
a Index
b Index
c Index
d
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hA Int
0 Index
root'
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hB Int
0 Index
P.undefIndex
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hC Int
0 Index
P.undefIndex
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hD Int
0 Index
P.undefIndex

-- | Amortized \(O(\log n)\). Splits a sequences into two: \([0, k), [k, n)\). The handle will
-- point to the left sequence. Returns the right sequence handle.
--
-- ==== Constraints
-- - \(0 \le k \le n\).
--
-- @since 1.2.0.0
{-# INLINE split #-}
split :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m (Handle (PrimState m))
split :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a
-> Handle (PrimState m) -> Int -> m (Handle (PrimState m))
split Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) Int
k = ST (PrimState m) (Handle (PrimState m)) -> m (Handle (PrimState m))
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Handle (PrimState m))
 -> m (Handle (PrimState m)))
-> ST (PrimState m) (Handle (PrimState m))
-> m (Handle (PrimState m))
forall a b. (a -> b) -> a -> b
$ do
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0
  (!Index
r1, !Index
r2) <- Seq (PrimState m) f a
-> Index -> Int -> ST (PrimState m) (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)
Seq.splitST Seq (PrimState m) f a
seq Index
root Int
k
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0 Index
r1
  Index -> ST (PrimState m) (Handle (PrimState (ST (PrimState m))))
forall (m :: * -> *).
PrimMonad m =>
Index -> m (Handle (PrimState m))
newHandle Index
r2

-- | Amortized \(O(\log n)\). Splits a sequences into three: \([0, l), [l, r), [r, n)\). The handle
-- will point to the leftmost sequence. Returns the middle and the right sequence handles.
--
-- ==== Constraints
-- - \(0 \le l \le r \le n\).
--
-- @since 1.2.0.0
{-# INLINE split3 #-}
split3 :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> m (Handle (PrimState m), Handle (PrimState m))
split3 :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a
-> Handle (PrimState m)
-> Int
-> Int
-> m (Handle (PrimState m), Handle (PrimState m))
split3 Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) Int
l Int
r = ST (PrimState m) (Handle (PrimState m), Handle (PrimState m))
-> m (Handle (PrimState m), Handle (PrimState m))
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Handle (PrimState m), Handle (PrimState m))
 -> m (Handle (PrimState m), Handle (PrimState m)))
-> ST (PrimState m) (Handle (PrimState m), Handle (PrimState m))
-> m (Handle (PrimState m), Handle (PrimState m))
forall a b. (a -> b) -> a -> b
$ do
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0
  (!Index
r1, !Index
r2, !Index
r3) <- Seq (PrimState m) f a
-> Index -> Int -> Int -> ST (PrimState m) (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)
Seq.split3ST Seq (PrimState m) f a
seq Index
root Int
l Int
r
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0 Index
r1
  (,) (Handle (PrimState m)
 -> Handle (PrimState m)
 -> (Handle (PrimState m), Handle (PrimState m)))
-> ST (PrimState m) (Handle (PrimState m))
-> ST
     (PrimState m)
     (Handle (PrimState m)
      -> (Handle (PrimState m), Handle (PrimState m)))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Index -> ST (PrimState m) (Handle (PrimState (ST (PrimState m))))
forall (m :: * -> *).
PrimMonad m =>
Index -> m (Handle (PrimState m))
newHandle Index
r2 ST
  (PrimState m)
  (Handle (PrimState m)
   -> (Handle (PrimState m), Handle (PrimState m)))
-> ST (PrimState m) (Handle (PrimState m))
-> ST (PrimState m) (Handle (PrimState m), Handle (PrimState m))
forall a b.
ST (PrimState m) (a -> b)
-> ST (PrimState m) a -> ST (PrimState m) b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Index -> ST (PrimState m) (Handle (PrimState (ST (PrimState m))))
forall (m :: * -> *).
PrimMonad m =>
Index -> m (Handle (PrimState m))
newHandle Index
r3

-- | Amortized \(O(\log n)\). Splits a sequences into four: \([0, i), [i, j), [j, k), [k, n)\).
-- The handle will point to the leftmost sequence. Returns the non-leftmost sequence handles.
--
-- ==== Constraints
-- - \(0 \le i \le j \le k \le n\).
--
-- @since 1.2.0.0
{-# INLINE split4 #-}
split4 :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> Int -> m (Handle (PrimState m), Handle (PrimState m), Handle (PrimState m))
split4 :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a
-> Handle (PrimState m)
-> Int
-> Int
-> Int
-> m (Handle (PrimState m), Handle (PrimState m),
      Handle (PrimState m))
split4 Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) Int
i Int
j Int
k = ST
  (PrimState m)
  (Handle (PrimState m), Handle (PrimState m), Handle (PrimState m))
-> m (Handle (PrimState m), Handle (PrimState m),
      Handle (PrimState m))
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST
   (PrimState m)
   (Handle (PrimState m), Handle (PrimState m), Handle (PrimState m))
 -> m (Handle (PrimState m), Handle (PrimState m),
       Handle (PrimState m)))
-> ST
     (PrimState m)
     (Handle (PrimState m), Handle (PrimState m), Handle (PrimState m))
-> m (Handle (PrimState m), Handle (PrimState m),
      Handle (PrimState m))
forall a b. (a -> b) -> a -> b
$ do
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0
  (!Index
r1, !Index
r2, !Index
r3, !Index
r4) <- Seq (PrimState m) f a
-> Index
-> Int
-> Int
-> Int
-> ST (PrimState m) (Index, 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 -> Int -> ST s (Index, Index, Index, Index)
Seq.split4ST Seq (PrimState m) f a
seq Index
root Int
i Int
j Int
k
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0 Index
r1
  (,,) (Handle (PrimState m)
 -> Handle (PrimState m)
 -> Handle (PrimState m)
 -> (Handle (PrimState m), Handle (PrimState m),
     Handle (PrimState m)))
-> ST (PrimState m) (Handle (PrimState m))
-> ST
     (PrimState m)
     (Handle (PrimState m)
      -> Handle (PrimState m)
      -> (Handle (PrimState m), Handle (PrimState m),
          Handle (PrimState m)))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Index -> ST (PrimState m) (Handle (PrimState (ST (PrimState m))))
forall (m :: * -> *).
PrimMonad m =>
Index -> m (Handle (PrimState m))
newHandle Index
r2 ST
  (PrimState m)
  (Handle (PrimState m)
   -> Handle (PrimState m)
   -> (Handle (PrimState m), Handle (PrimState m),
       Handle (PrimState m)))
-> ST (PrimState m) (Handle (PrimState m))
-> ST
     (PrimState m)
     (Handle (PrimState m)
      -> (Handle (PrimState m), Handle (PrimState m),
          Handle (PrimState m)))
forall a b.
ST (PrimState m) (a -> b)
-> ST (PrimState m) a -> ST (PrimState m) b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Index -> ST (PrimState m) (Handle (PrimState (ST (PrimState m))))
forall (m :: * -> *).
PrimMonad m =>
Index -> m (Handle (PrimState m))
newHandle Index
r3 ST
  (PrimState m)
  (Handle (PrimState m)
   -> (Handle (PrimState m), Handle (PrimState m),
       Handle (PrimState m)))
-> ST (PrimState m) (Handle (PrimState m))
-> ST
     (PrimState m)
     (Handle (PrimState m), Handle (PrimState m), Handle (PrimState m))
forall a b.
ST (PrimState m) (a -> b)
-> ST (PrimState m) a -> ST (PrimState m) b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Index -> ST (PrimState m) (Handle (PrimState (ST (PrimState m))))
forall (m :: * -> *).
PrimMonad m =>
Index -> m (Handle (PrimState m))
newHandle Index
r4

-- | Amortized \(O(\log n)\). Splits a sequence into three: \([0, \mathrm{root}), \mathrm{root}, [\mathrm{root} + 1, n)\).
--
-- ==== Constraints
-- - The sequence must be non-empty.
--
-- @since 1.2.0.0
{-# INLINE splitLr #-}
splitLr :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> m (Handle (PrimState m), Handle (PrimState m))
splitLr :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a
-> Handle (PrimState m)
-> m (Handle (PrimState m), Handle (PrimState m))
splitLr Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) = ST (PrimState m) (Handle (PrimState m), Handle (PrimState m))
-> m (Handle (PrimState m), Handle (PrimState m))
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Handle (PrimState m), Handle (PrimState m))
 -> m (Handle (PrimState m), Handle (PrimState m)))
-> ST (PrimState m) (Handle (PrimState m), Handle (PrimState m))
-> m (Handle (PrimState m), Handle (PrimState m))
forall a b. (a -> b) -> a -> b
$ do
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0
  (!Index
l, !Index
root', !Index
r) <- Seq (PrimState m) f a
-> Index -> ST (PrimState m) (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 -> ST s (Index, Index, Index)
Seq.splitLrST Seq (PrimState m) f a
seq Index
root
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0 Index
root'
  (,) (Handle (PrimState m)
 -> Handle (PrimState m)
 -> (Handle (PrimState m), Handle (PrimState m)))
-> ST (PrimState m) (Handle (PrimState m))
-> ST
     (PrimState m)
     (Handle (PrimState m)
      -> (Handle (PrimState m), Handle (PrimState m)))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Index -> ST (PrimState m) (Handle (PrimState (ST (PrimState m))))
forall (m :: * -> *).
PrimMonad m =>
Index -> m (Handle (PrimState m))
newHandle Index
l ST
  (PrimState m)
  (Handle (PrimState m)
   -> (Handle (PrimState m), Handle (PrimState m)))
-> ST (PrimState m) (Handle (PrimState m))
-> ST (PrimState m) (Handle (PrimState m), Handle (PrimState m))
forall a b.
ST (PrimState m) (a -> b)
-> ST (PrimState m) a -> ST (PrimState m) b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Index -> ST (PrimState m) (Handle (PrimState (ST (PrimState m))))
forall (m :: * -> *).
PrimMonad m =>
Index -> m (Handle (PrimState m))
newHandle Index
r

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

-- | Amortized \(O(\log n)\). Reads the \(k\)-th node's monoid value.
--
-- ==== Constraints
-- - \(0 \le k \lt n\)
--
-- @since 1.2.0.0
{-# INLINE read #-}
read :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m a
read :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m a
read Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) Int
k = 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
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0
  (!a
v, !Index
root') <- Seq (PrimState m) f a
-> Index -> Int -> ST (PrimState m) (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 -> ST s (a, Index)
Seq.readST Seq (PrimState m) f a
seq Index
root Int
k
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0 Index
root'
  a -> ST (PrimState m) a
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
v

-- | Amortized \(O(\log n)\). Reads the \(k\)-th node's monoid value.
--
-- @since 1.2.0.0
{-# INLINE readMaybe #-}
readMaybe :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m (Maybe a)
readMaybe :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m (Maybe a)
readMaybe Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) Int
k = ST (PrimState m) (Maybe a) -> m (Maybe a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Maybe a) -> m (Maybe a))
-> ST (PrimState m) (Maybe a) -> m (Maybe a)
forall a b. (a -> b) -> a -> b
$ do
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0
  Maybe (a, Index)
res <- Seq (PrimState m) f a
-> Index -> Int -> ST (PrimState m) (Maybe (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 -> ST s (Maybe (a, Index))
Seq.readMaybeST Seq (PrimState m) f a
seq Index
root Int
k
  case Maybe (a, Index)
res of
    Just (!a
v, !Index
root') -> do
      MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0 Index
root'
      Maybe a -> ST (PrimState m) (Maybe a)
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe a -> ST (PrimState m) (Maybe a))
-> Maybe a -> ST (PrimState m) (Maybe a)
forall a b. (a -> b) -> a -> b
$ a -> Maybe a
forall a. a -> Maybe a
Just a
v
    Maybe (a, Index)
Nothing -> Maybe a -> ST (PrimState m) (Maybe a)
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe a
forall a. Maybe a
Nothing

-- | Amortized \(O(\log n)\). Writes to the \(k\)-th node's monoid value.
--
-- ==== Constraints
-- - \(0 \le k \lt n\)
--
-- @since 1.2.0.0
{-# INLINE write #-}
write :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> a -> m ()
write :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> a -> m ()
write Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) Int
k a
v = 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
$ do
  MVector (PrimState (ST (PrimState m))) Index
-> (Index -> ST (PrimState m) Index) -> Int -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
VGM.unsafeModifyM
    MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot
    ( \Index
root -> do
        Seq (PrimState m) f a
-> Index -> Int -> a -> ST (PrimState m) 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 -> a -> ST s Index
Seq.writeST Seq (PrimState m) f a
seq Index
root Int
k a
v
    )
    Int
0

-- | Amortized \(O(\log n)\). Modifies the \(k\)-th node's monoid value.
--
-- ==== Constraints
-- - \(0 \le k \lt n\)
--
-- @since 1.2.0.0
{-# INLINE modify #-}
modify :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> (a -> a) -> Int -> m ()
modify :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a
-> Handle (PrimState m) -> (a -> a) -> Int -> m ()
modify Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) a -> a
f Int
k = 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
$ do
  MVector (PrimState (ST (PrimState m))) Index
-> (Index -> ST (PrimState m) Index) -> Int -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
VGM.unsafeModifyM
    MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot
    ( \Index
root -> do
        Seq (PrimState m) f a
-> Index -> (a -> a) -> Int -> ST (PrimState m) Index
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
Seq.modifyST Seq (PrimState m) f a
seq Index
root a -> a
f Int
k
    )
    Int
0

-- | Amortized \(O(\log n)\). Exchanges the \(k\)-th node's monoid value.
--
-- ==== Constraints
-- - \(0 \le k \lt n\)
--
-- @since 1.2.0.0
{-# INLINE exchange #-}
exchange :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> a -> m a
exchange :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> a -> m a
exchange Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) Int
k 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
$ do
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0
  (!a
x, !Index
root') <- Seq (PrimState m) f a
-> Index -> Int -> a -> ST (PrimState m) (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 -> a -> ST s (a, Index)
Seq.exchangeST Seq (PrimState m) f a
seq Index
root Int
k a
v
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0 Index
root'
  a -> ST (PrimState m) a
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
x

-- | Amortized \(O(\log n)\). Returns the monoid product in an interval \([l, r)\).
--
-- ==== Constraints
-- - \(0 \le l \le r \le n\)
--
-- @since 1.2.0.0
{-# INLINE prod #-}
prod :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> m a
prod :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> m a
prod Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) Int
l Int
r = 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
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0
  (!a
v, !Index
root') <- Seq (PrimState m) f a
-> Index -> Int -> Int -> ST (PrimState m) (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)
Seq.prodST Seq (PrimState m) f a
seq Index
root Int
l Int
r
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0 Index
root'
  a -> ST (PrimState m) a
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
v

-- | Amortized \(O(\log n)\). Returns the monoid product in an interval \([l, r)\). Returns
-- `Nothing` if the interval is invalid.
--
-- @since 1.2.0.0
{-# INLINEABLE prodMaybe #-}
prodMaybe :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> m (Maybe a)
prodMaybe :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a
-> Handle (PrimState m) -> Int -> Int -> m (Maybe a)
prodMaybe Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
handle) Int
l Int
r = ST (PrimState m) (Maybe a) -> m (Maybe a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Maybe a) -> m (Maybe a))
-> ST (PrimState m) (Maybe a) -> m (Maybe a)
forall a b. (a -> b) -> a -> b
$ do
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
handle Int
0
  if Index -> Bool
P.nullIndex Index
root
    then Maybe a -> ST (PrimState m) (Maybe a)
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe a -> ST (PrimState m) (Maybe a))
-> Maybe a -> ST (PrimState m) (Maybe a)
forall a b. (a -> b) -> a -> b
$ a -> Maybe a
forall a. a -> Maybe a
Just a
forall a. Monoid a => a
mempty
    else do
      Maybe (a, Index)
res <- Seq (PrimState m) f a
-> Index -> Int -> Int -> ST (PrimState m) (Maybe (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 (Maybe (a, Index))
Seq.prodMaybeST Seq (PrimState m) f a
seq Index
root Int
l Int
r
      case Maybe (a, Index)
res of
        Just (!a
v, !Index
root') -> do
          MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
handle Int
0 Index
root'
          Maybe a -> ST (PrimState m) (Maybe a)
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe a -> ST (PrimState m) (Maybe a))
-> Maybe a -> ST (PrimState m) (Maybe a)
forall a b. (a -> b) -> a -> b
$ a -> Maybe a
forall a. a -> Maybe a
Just a
v
        Maybe (a, Index)
Nothing -> Maybe a -> ST (PrimState m) (Maybe a)
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe a
forall a. Maybe a
Nothing

-- | Amortized \(O(\log n)\). Returns the monoid product of the whole sequence.
--
-- @since 1.2.0.0
{-# INLINE prodAll #-}
prodAll :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> m a
prodAll :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a -> Handle (PrimState m) -> m a
prodAll Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
handle) = 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
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
handle Int
0
  Seq (PrimState m) f a -> Index -> ST (PrimState m) a
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
Seq.prodAllST Seq (PrimState m) f a
seq 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
{-# INLINE applyIn #-}
applyIn :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> f -> m ()
applyIn :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a
-> Handle (PrimState m) -> Int -> Int -> f -> m ()
applyIn Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) Int
l Int
r f
act = 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
$ do
  MVector (PrimState (ST (PrimState m))) Index
-> (Index -> ST (PrimState m) Index) -> Int -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
VGM.unsafeModifyM
    MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot
    ( \Index
root -> do
        Seq (PrimState m) f a
-> Index -> Int -> Int -> f -> ST (PrimState m) 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 -> f -> ST s Index
Seq.applyInST Seq (PrimState m) f a
seq Index
root Int
l Int
r f
act
    )
    Int
0

-- | \(O(1)\) Applies a monoid action \(f\) to the root of a sequence.
--
-- @since 1.2.0.0
{-# INLINE applyToRoot #-}
applyToRoot :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> f -> m ()
applyToRoot :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a -> Handle (PrimState m) -> f -> m ()
applyToRoot Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) f
act = 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
$ do
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0
  Seq (PrimState m) f a -> Index -> f -> 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 -> f -> ST s ()
Seq.applyToRootST Seq (PrimState m) 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
{-# INLINE reverse #-}
reverse :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> m ()
reverse :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> m ()
reverse Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) Int
l Int
r = 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
$ do
  MVector (PrimState (ST (PrimState m))) Index
-> (Index -> ST (PrimState m) Index) -> Int -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
VGM.unsafeModifyM
    MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot
    ( \Index
root -> do
        Seq (PrimState m) f a
-> Index -> Int -> Int -> ST (PrimState m) 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
Seq.reverseST Seq (PrimState m) f a
seq Index
root Int
l Int
r
    )
    Int
0

-- | Amortized \(O(\log n)\). Inserts a new node at \(k\) with initial monoid value \(v\). This
-- function works for an empty sequence handle.
--
-- ==== Constraints
-- - \(0 \le k \le n\)
--
-- @since 1.2.0.0
{-# INLINE insert #-}
insert :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> a -> m ()
insert :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> a -> m ()
insert Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) Int
k a
v = 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
$ do
  MVector (PrimState (ST (PrimState m))) Index
-> (Index -> ST (PrimState m) Index) -> Int -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
VGM.unsafeModifyM
    MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot
    ( \Index
root -> do
        Seq (PrimState m) f a
-> Index -> Int -> a -> ST (PrimState m) 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 -> a -> ST s Index
Seq.insertST Seq (PrimState m) f a
seq Index
root Int
k a
v
    )
    Int
0

-- | Amortized \(O(\log n)\). Frees the \(k\)-th node and returns the monoid value of it.
--
-- ==== Constraints
-- - \(0 \le k \lt n\)
--
-- @since 1.2.0.0
{-# INLINE delete #-}
delete :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m a
delete :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m a
delete Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) Int
i = 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
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0
  (!a
v, !Index
root') <- Seq (PrimState m) f a
-> Index -> Int -> ST (PrimState m) (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 -> ST s (a, Index)
Seq.deleteST Seq (PrimState m) f a
seq Index
root Int
i
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0 Index
root'
  a -> ST (PrimState m) a
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
v

-- | Amortized \(O(\log n)\). Frees the \(k\)-th node.
--
-- ==== Constraints
-- - \(0 \le k \lt n\)
--
-- @since 1.2.0.0
{-# INLINE delete_ #-}
delete_ :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m ()
delete_ :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m ()
delete_ Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) Int
i = 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
$ do
  MVector (PrimState (ST (PrimState m))) Index
-> (Index -> ST (PrimState m) Index) -> Int -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
VGM.unsafeModifyM
    MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot
    ( \Index
root -> do
        Seq (PrimState m) f a -> Index -> Int -> ST (PrimState m) 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
Seq.deleteST_ Seq (PrimState m) f a
seq Index
root Int
i
    )
    Int
0

-- | Amortized \(O(\log n)\). Detaches the \(k\)-th node and returns a handle for it.
--
-- ==== Constraints
-- - \(0 \le k \lt n\)
--
-- @since 1.2.0.0
{-# INLINE detach #-}
detach :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m (Handle (PrimState m))
detach :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a
-> Handle (PrimState m) -> Int -> m (Handle (PrimState m))
detach Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) Int
i = ST (PrimState m) (Handle (PrimState m)) -> m (Handle (PrimState m))
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Handle (PrimState m))
 -> m (Handle (PrimState m)))
-> ST (PrimState m) (Handle (PrimState m))
-> m (Handle (PrimState m))
forall a b. (a -> b) -> a -> b
$ do
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0
  Index
root' <- Seq (PrimState m) f a -> Index -> Int -> ST (PrimState m) 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
Seq.detachST Seq (PrimState m) f a
seq Index
root Int
i
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0 Index
root'
  Index -> ST (PrimState m) (Handle (PrimState (ST (PrimState m))))
forall (m :: * -> *).
PrimMonad m =>
Index -> m (Handle (PrimState m))
newHandle Index
root

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

-- | Amortized \(O(\log n)\).
--
-- @since 1.2.0.0
{-# INLINE ilowerBound #-}
ilowerBound ::
  (PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq (PrimState m) f a ->
  -- | Sequence handle
  Handle (PrimState m) ->
  -- | User predicate \(f(i, v_i)\) that takes the index and the monoid value
  (Int -> a -> Bool) ->
  -- | Maximum \(r\), where \(f(i, v_i)\) holds for \(i \in [0, r)\)
  m Int
ilowerBound :: forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Handle (PrimState m) -> (Int -> a -> Bool) -> m Int
ilowerBound Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
root0) Int -> a -> Bool
f = 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
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
root0 Int
0
  (!Int
r, !Index
root') <- Seq (PrimState m) f a
-> Index -> (Int -> a -> Bool) -> ST (PrimState m) (Int, 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)
Seq.ilowerBoundST Seq (PrimState m) f a
seq Index
root Int -> a -> Bool
f
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
root0 Int
0 Index
root'
  Int -> ST (PrimState m) Int
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
r

-- | 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 ->
  -- | Sequence handle
  Handle (PrimState m) ->
  -- | User predicate \(f(i, v_i)\) that takes the index and the monoid value
  (Int -> a -> m Bool) ->
  -- | Maximum \(r\), where \(f(i, v_i)\) holds for \(i \in [0, r)\)
  m Int
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
-> Handle (PrimState m) -> (Int -> a -> m Bool) -> m Int
ilowerBoundM Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
root0) Int -> a -> m Bool
f = do
  Index
root <- MVector (PrimState m) Index -> Int -> m Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
root0 Int
0
  (!Int
r, !Index
root') <- Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Int, 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)
Seq.ilowerBoundM Seq (PrimState m) f a
seq Index
root Int -> a -> m Bool
f
  MVector (PrimState m) Index -> Int -> Index -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
root0 Int
0 Index
root'
  Int -> m Int
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
r

-- | Amortized \(O(\log n)\).
--
-- @since 1.2.0.0
{-# INLINE ilowerBoundProd #-}
ilowerBoundProd ::
  (PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq (PrimState m) f a ->
  -- | Sequence handle
  Handle (PrimState m) ->
  -- | User predicate \(f(i, v_0 \dots v_i)\) that takes the index and the monoid product
  (Int -> a -> Bool) ->
  -- | Maximum \(r\), where \(f(i, v_0 \dots v_i)\) holds for \(i \in [0, r)\)
  m Int
ilowerBoundProd :: forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Handle (PrimState m) -> (Int -> a -> Bool) -> m Int
ilowerBoundProd Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
root0) Int -> a -> Bool
f = 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
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
root0 Int
0
  (!Int
r, !Index
root') <- Seq (PrimState m) f a
-> Index -> (Int -> a -> Bool) -> ST (PrimState m) (Int, 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)
Seq.ilowerBoundProdST Seq (PrimState m) f a
seq Index
root Int -> a -> Bool
f
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
root0 Int
0 Index
root'
  Int -> ST (PrimState m) Int
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
r

-- | Amortized \(O(\log n)\).
--
-- @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 ->
  -- | Sequence handle
  Handle (PrimState m) ->
  -- | User predicate \(f(i, v_0 \dots v_i)\) that takes the index and the monoid product
  (Int -> a -> m Bool) ->
  -- | Maximum \(r\), where \(f(i, v_0 \dots v_i)\) holds for \(i \in [0, r)\)
  m Int
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
-> Handle (PrimState m) -> (Int -> a -> m Bool) -> m Int
ilowerBoundProdM Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
root0) Int -> a -> m Bool
f = do
  Index
root <- MVector (PrimState m) Index -> Int -> m Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
root0 Int
0
  (!Int
r, !Index
root') <- Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (Int, 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)
Seq.ilowerBoundProdM Seq (PrimState m) f a
seq Index
root Int -> a -> m Bool
f
  MVector (PrimState m) Index -> Int -> Index -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
root0 Int
0 Index
root'
  Int -> m Int
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
r

-- | Amortized \(O(\log n)\). Splits a sequence into two with the user predicate and returns the
-- right sequence handle.
--
-- @since 1.2.0.0
{-# INLINE isplitMaxRight #-}
isplitMaxRight ::
  (PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq (PrimState m) f a ->
  -- | Sequence handle
  Handle (PrimState m) ->
  -- | User predicate \(f(i, v_i)\) that takes the index and the monoid value
  (Int -> a -> Bool) ->
  -- | Handle of the right sequence \([r, n)\), where \(r\) is the maximum \(r\) such that
  -- \(f(i, v_i)\) holds for \(i \in [0, r)\)
  m (Handle (PrimState m))
isplitMaxRight :: forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Handle (PrimState m)
-> (Int -> a -> Bool)
-> m (Handle (PrimState m))
isplitMaxRight Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
root0) Int -> a -> Bool
f = ST (PrimState m) (Handle (PrimState m)) -> m (Handle (PrimState m))
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Handle (PrimState m))
 -> m (Handle (PrimState m)))
-> ST (PrimState m) (Handle (PrimState m))
-> m (Handle (PrimState m))
forall a b. (a -> b) -> a -> b
$ do
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
root0 Int
0
  (!Index
l, !Index
r) <- Seq (PrimState m) f a
-> Index -> (Int -> a -> Bool) -> ST (PrimState m) (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 (Index, Index)
Seq.isplitMaxRightST Seq (PrimState m) f a
seq Index
root Int -> a -> Bool
f
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
root0 Int
0 Index
l
  Index -> ST (PrimState m) (Handle (PrimState (ST (PrimState m))))
forall (m :: * -> *).
PrimMonad m =>
Index -> m (Handle (PrimState m))
newHandle Index
r

-- | Amortized \(O(\log n)\). Splits a sequence into two with the user predicate and returns the
-- right sequence handle.
--
-- @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 ->
  -- | Sequence handle
  Handle (PrimState m) ->
  -- | User predicate \(f(i, v_i)\) that takes the index and the monoid value
  (Int -> a -> m Bool) ->
  -- | Handle of the right sequence \([r, n)\), where \(r\) is the maximum \(r\) such that
  -- \(f(i, v_i)\) holds for \(i \in [0, r)\)
  m (Handle (PrimState m))
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
-> Handle (PrimState m)
-> (Int -> a -> m Bool)
-> m (Handle (PrimState m))
isplitMaxRightM Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
root0) Int -> a -> m Bool
f = do
  Index
root <- MVector (PrimState m) Index -> Int -> m Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
root0 Int
0
  (!Index
l, !Index
r) <- Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (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)
Seq.isplitMaxRightM Seq (PrimState m) f a
seq Index
root Int -> a -> m Bool
f
  MVector (PrimState m) Index -> Int -> Index -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
root0 Int
0 Index
l
  Index -> m (Handle (PrimState m))
forall (m :: * -> *).
PrimMonad m =>
Index -> m (Handle (PrimState m))
newHandle Index
r

-- | Amortized \(O(\log n)\). Splits a sequence into two with the user predicate and returns the
-- right sequence handle.
--
-- @since 1.2.0.0
{-# INLINE isplitMaxRightProd #-}
isplitMaxRightProd ::
  (PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Sequence storage
  Seq (PrimState m) f a ->
  -- | Sequence handle
  Handle (PrimState m) ->
  -- | User predicate \(f(i, v_0 \dots v_i)\) that takes the index and the monoid value
  (Int -> a -> Bool) ->
  -- | Handle of the right sequence \([r, n)\), where \(r\) is the maximum \(r\) such that
  -- \(f(i, v_0 \dots v_i)\) holds for \(i \in [0, r)\)
  m (Handle (PrimState m))
isplitMaxRightProd :: forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Seq (PrimState m) f a
-> Handle (PrimState m)
-> (Int -> a -> Bool)
-> m (Handle (PrimState m))
isplitMaxRightProd Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
root0) Int -> a -> Bool
f = ST (PrimState m) (Handle (PrimState m)) -> m (Handle (PrimState m))
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Handle (PrimState m))
 -> m (Handle (PrimState m)))
-> ST (PrimState m) (Handle (PrimState m))
-> m (Handle (PrimState m))
forall a b. (a -> b) -> a -> b
$ do
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
root0 Int
0
  (!Index
l, !Index
r) <- Seq (PrimState m) f a
-> Index -> (Int -> a -> Bool) -> ST (PrimState m) (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 (Index, Index)
Seq.isplitMaxRightProdST Seq (PrimState m) f a
seq Index
root Int -> a -> Bool
f
  MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
root0 Int
0 Index
l
  Index -> ST (PrimState m) (Handle (PrimState (ST (PrimState m))))
forall (m :: * -> *).
PrimMonad m =>
Index -> m (Handle (PrimState m))
newHandle Index
r

-- | Amortized \(O(\log n)\). Splits a sequence into two with the user predicate and returns the
-- right sequence handle.
--
-- @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 ->
  -- | Sequence handle
  Handle (PrimState m) ->
  -- | User predicate \(f(i, v_0 \dots v_i)\) that takes the index and the monoid value
  (Int -> a -> m Bool) ->
  -- | Handle of the right sequence \([r, n)\), where \(r\) is the maximum \(r\) such that
  -- \(f(i, v_0 \dots v_i)\) holds for \(i \in [0, r)\)
  m (Handle (PrimState m))
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
-> Handle (PrimState m)
-> (Int -> a -> m Bool)
-> m (Handle (PrimState m))
isplitMaxRightProdM Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
root0) Int -> a -> m Bool
f = do
  Index
root <- MVector (PrimState m) Index -> Int -> m Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
root0 Int
0
  (!Index
l, !Index
r) <- Seq (PrimState m) f a
-> Index -> (Int -> a -> m Bool) -> m (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)
Seq.isplitMaxRightProdM Seq (PrimState m) f a
seq Index
root Int -> a -> m Bool
f
  MVector (PrimState m) Index -> Int -> Index -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector (PrimState m) Index
root0 Int
0 Index
l
  Index -> m (Handle (PrimState m))
forall (m :: * -> *).
PrimMonad m =>
Index -> m (Handle (PrimState m))
newHandle Index
r

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

-- | Amortized \(O(n)\). Returns the sequence of monoid values.
--
-- @since 1.2.0.0
{-# INLINEABLE freeze #-}
freeze :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> m (VU.Vector a)
freeze :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Seq (PrimState m) f a -> Handle (PrimState m) -> m (Vector a)
freeze Seq (PrimState m) f a
seq (Handle MVector (PrimState m) Index
hRoot) = ST (PrimState m) (Vector a) -> m (Vector a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Vector a) -> m (Vector a))
-> ST (PrimState m) (Vector a) -> m (Vector a)
forall a b. (a -> b) -> a -> b
$ do
  Index
root <- MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
hRoot Int
0
  Seq (PrimState m) f a -> Index -> ST (PrimState m) (Vector a)
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)
Seq.freezeST Seq (PrimState m) f a
seq Index
root