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

-- | Key-value pairs with monoid products and monoid actions on them through the `SegAct` instance.
--
-- ==== Performance
-- This module is __extremely slow__ as an ordinary map. Do not use it unless you need monoid
-- products.
--
-- ==== __Example__
--
-- >>> import AtCoder.Extra.Monoid.RangeAdd qualified as RangeAdd
-- >>> import AtCoder.Extra.Seq.Map qualified as M
-- >>> import Data.Semigroup (Sum (..))
-- >>> import Data.Vector.Unboxed qualified as VU
-- >>> m <- M.new @_ @(RangeAdd.RangeAdd (Sum Int)) @Int @(Sum Int) 10
-- >>> M.insert m 1 10
-- >>> M.insert m 3 30
-- >>> M.prod m 1 2
-- Sum {getSum = 10}
--
-- @since 1.2.1.0
module AtCoder.Extra.Seq.Map
  ( -- * Map
    Map (..),

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

    -- * Constructors
    new,
    build,
    reset,

    -- * Metadata
    capacity,
    size,

    -- * Key-based operations

    -- ** Read/write
    member,
    lookup,
    adjust,

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

    -- ** Products

    -- sliceST,
    prod,
    prodMaybe,
    allProd, -- FIXME: rename to `prodAll`

    -- ** Applications
    applyIn,
    applyAll,

    -- ** Bisection methods
    lookupLE,
    lookupLT,
    lookupGE,
    lookupGT,

    -- * Index-based operations

    -- ** Read/write
    readAt,
    readMaybeAt,
    writeAt,
    modifyAt,
    exchangeAt,

    -- ** Products
    prodInInterval,
    -- TODO: prodIn

    -- ** Applications
    applyInInterval,

    -- ** Bisection methods
    ilowerBound,
    ilowerBoundM,
    ilowerBoundProd,
    ilowerBoundProdM,

    -- * Conversion
    freeze,
  )
where

import AtCoder.Extra.Pool qualified as P
import AtCoder.Extra.Seq qualified as Seq
import AtCoder.Extra.Seq.Raw qualified as Raw
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.Coerce (coerce)
import Data.Ord (comparing)
import Data.Vector.Algorithms.Intro qualified as VAI
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 (lookup, read, reverse, seq)

-- | Key-value pairs with monoid products and monoid actions on them through the `SegAct` instance.
--
-- @since 1.2.1.0
data Map s f k v = Map
  { -- | The sequence storage
    --
    -- @since 1.2.1.0
    forall s f k v. Map s f k v -> Seq s f v
seqMap :: !(Seq.Seq s f v),
    -- | Keys
    --
    -- @since 1.2.1.0
    forall s f k v. Map s f k v -> MVector s k
kMap :: !(VUM.MVector s k),
    -- | Handle of the root node.
    --
    -- @since 1.2.1.0
    forall s f k v. Map s f k v -> Handle s
rootMap :: !(Seq.Handle s)
  }

{-# INLINE assertRootST #-}
assertRootST :: (HasCallStack) => Raw.Seq s f v -> P.Index -> ST s ()
assertRootST :: forall s f v. HasCallStack => Seq s f v -> Index -> ST s ()
assertRootST Seq.Seq {MVector s Index
pSeq :: MVector s Index
pSeq :: forall s f a. Seq s f a -> 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.Map.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 ()

-- | \(O(n)\) Creates a new `Map` of capacity \(n\). Always prefer `build` to `new` for performance.
--
-- @since 1.2.1.0
{-# INLINEABLE new #-}
new :: (PrimMonad m, Monoid f, VU.Unbox f, VU.Unbox k, VU.Unbox v, Monoid v) => Int -> m (Map (PrimState m) f k v)
new :: forall (m :: * -> *) f k v.
(PrimMonad m, Monoid f, Unbox f, Unbox k, Unbox v, Monoid v) =>
Int -> m (Map (PrimState m) f k v)
new Int
n = ST (PrimState m) (Map (PrimState m) f k v)
-> m (Map (PrimState m) f k v)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Map (PrimState m) f k v)
 -> m (Map (PrimState m) f k v))
-> ST (PrimState m) (Map (PrimState m) f k v)
-> m (Map (PrimState m) f k v)
forall a b. (a -> b) -> a -> b
$ do
  Seq (PrimState m) f v
seqMap <- Int -> ST (PrimState m) (Seq (PrimState (ST (PrimState m))) f v)
forall (m :: * -> *) f a.
(PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) =>
Int -> m (Seq (PrimState m) f a)
Seq.new Int
n
  MVector (PrimState m) k
kMap <- Int -> ST (PrimState m) (MVector (PrimState (ST (PrimState m))) k)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
n
  Handle (PrimState m)
rootMap <- Index -> ST (PrimState m) (Handle (PrimState (ST (PrimState m))))
forall (m :: * -> *).
PrimMonad m =>
Index -> m (Handle (PrimState m))
Seq.newHandle Index
P.undefIndex
  Map (PrimState m) f k v
-> ST (PrimState m) (Map (PrimState m) f k v)
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..}

-- | \(O(n \log n)\) Creates a new `Map` of capacity \(n\) with initial values. Always prefer `build` to
-- `new` for performance.
--
-- @since 1.2.1.0
{-# INLINEABLE build #-}
build :: (HasCallStack, PrimMonad m, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, VU.Unbox v, Monoid v) => Int -> VU.Vector (k, v) -> m (Map (PrimState m) f k v)
build :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Monoid f, Unbox f, Ord k, Unbox k,
 Unbox v, Monoid v) =>
Int -> Vector (k, v) -> m (Map (PrimState m) f k v)
build Int
n Vector (k, v)
kvs = ST (PrimState m) (Map (PrimState m) f k v)
-> m (Map (PrimState m) f k v)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Map (PrimState m) f k v)
 -> m (Map (PrimState m) f k v))
-> ST (PrimState m) (Map (PrimState m) f k v)
-> m (Map (PrimState m) f k v)
forall a b. (a -> b) -> a -> b
$ do
  -- let !_ = ACIA.runtimeAssert (VU.length kvs <= n) "AtCoder.Extra.Seq.Map"
  Seq (PrimState m) f v
seqMap <- Int -> ST (PrimState m) (Seq (PrimState (ST (PrimState m))) f v)
forall (m :: * -> *) f a.
(PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) =>
Int -> m (Seq (PrimState m) f a)
Seq.new Int
n
  MVector (PrimState m) k
kMap <- Int -> ST (PrimState m) (MVector (PrimState (ST (PrimState m))) k)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
n
  -- note that `unzip` is O(1) for tuples:
  let (!Vector k
ks, !Vector v
vs) = Vector (k, v) -> (Vector k, Vector v)
forall a b.
(Unbox a, Unbox b) =>
Vector (a, b) -> (Vector a, Vector b)
VU.unzip (Vector (k, v) -> (Vector k, Vector v))
-> Vector (k, v) -> (Vector k, Vector v)
forall a b. (a -> b) -> a -> b
$ (forall s. MVector s (k, v) -> ST s ())
-> Vector (k, v) -> Vector (k, v)
forall a.
Unbox a =>
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
VU.modify (Comparison (k, v) -> MVector (PrimState (ST s)) (k, v) -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) e.
(PrimMonad m, MVector v e) =>
Comparison e -> v (PrimState m) e -> m ()
VAI.sortBy (((k, v) -> k) -> Comparison (k, v)
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing (k, v) -> k
forall a b. (a, b) -> a
fst)) Vector (k, v)
kvs
  Vector k
-> (Int -> k -> ST (PrimState m) ()) -> ST (PrimState m) ()
forall (m :: * -> *) a b.
(Monad m, Unbox a) =>
Vector a -> (Int -> a -> m b) -> m ()
VU.iforM_ Vector k
ks ((Int -> k -> ST (PrimState m) ()) -> ST (PrimState m) ())
-> (Int -> k -> ST (PrimState m) ()) -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) k
-> Int -> k -> 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) k
MVector (PrimState (ST (PrimState m))) k
kMap
  Handle (PrimState m)
rootMap <- Seq (PrimState (ST (PrimState m))) f v
-> Vector v
-> ST (PrimState m) (Handle (PrimState (ST (PrimState m))))
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))
Seq.newSeq Seq (PrimState m) f v
Seq (PrimState (ST (PrimState m))) f v
seqMap Vector v
vs
  Map (PrimState m) f k v
-> ST (PrimState m) (Map (PrimState m) f k v)
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..}

-- | \(O(1)\) Clears the map. All the handles must not be used again.
--
-- @since 1.2.1.0
{-# INLINEABLE reset #-}
reset :: (PrimMonad m, Monoid f, VU.Unbox f, VU.Unbox k, VU.Unbox v, Monoid v) => Map (PrimState m) f k v -> m ()
reset :: forall (m :: * -> *) f k v.
(PrimMonad m, Monoid f, Unbox f, Unbox k, Unbox v, Monoid v) =>
Map (PrimState m) f k v -> m ()
reset Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} = 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
  Seq (PrimState m) f v -> ST (PrimState m) ()
forall s f a. Seq s f a -> ST s ()
Raw.resetST Seq (PrimState m) f v
seqMap
  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 (Handle (PrimState m) -> MVector (PrimState m) Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle (PrimState m)
rootMap) Int
0 Index
P.undefIndex

-- -------------------------------------------------------------------------------------------
-- Metadta
-- -------------------------------------------------------------------------------------------

-- | \(O(1)\) Returns the maximum number of elements the map can store.
--
-- @since 1.2.1.0
{-# INLINEABLE capacity #-}
capacity :: Map s f k v -> Int
capacity :: forall s f k v. Map s f k v -> Int
capacity Map {Seq s f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
seqMap :: Seq s f v
seqMap} = Seq s f v -> Int
forall s f a. Seq s f a -> Int
Raw.capacity Seq s f v
seqMap

-- | \(O(1)\) Returns the number of elements in the map.
--
-- @since 1.2.1.0
{-# INLINEABLE size #-}
size :: (PrimMonad m) => Map (PrimState m) f k v -> m Int
size :: forall (m :: * -> *) f k v.
PrimMonad m =>
Map (PrimState m) f k v -> m Int
size Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} = 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.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read (Handle (PrimState m) -> MVector (PrimState m) Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle (PrimState m)
rootMap) Int
0
  Seq (PrimState m) f v -> Index -> ST (PrimState m) Int
forall s f a. Seq s f a -> Index -> ST s Int
Raw.lengthST Seq (PrimState m) f v
seqMap Index
root

-- -------------------------------------------------------------------------------------------
-- Key-based operations
-- -------------------------------------------------------------------------------------------

-- | Amortized \(O(\log n)\). Finds a node with key \(k\).
{-# INLINEABLE lookupNodeST #-}
lookupNodeST :: (HasCallStack, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map s f k v -> k -> ST s (Bool, P.Index, P.Index)
lookupNodeST :: forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> k -> ST s (Bool, Index, Index)
lookupNodeST Map {MVector s k
Handle s
Seq s f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq s f v
kMap :: MVector s k
rootMap :: Handle s
..} k
k = do
  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 (Handle s -> MVector s Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle s
rootMap) Int
0
  if Index -> Bool
P.nullIndex Index
root
    then (Bool, Index, Index) -> ST s (Bool, Index, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Bool
False, Index
P.undefIndex, Index
P.undefIndex)
    else do
      (!Index
l, !Index
root') <- Seq s f v -> 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)
Raw.maxRightWithST Seq s f v
seqMap Index
root ((Index -> ST s Bool) -> ST s (Index, Index))
-> (Index -> ST s Bool) -> ST s (Index, Index)
forall a b. (a -> b) -> a -> b
$ \Index
i -> do
        k
ki <- MVector (PrimState (ST s)) k -> Int -> ST s k
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s k
MVector (PrimState (ST s)) k
kMap (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i)
        Bool -> ST s Bool
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Bool -> ST s Bool) -> Bool -> ST s Bool
forall a b. (a -> b) -> a -> b
$ k
ki k -> k -> Bool
forall a. Ord a => a -> a -> Bool
<= k
k
      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 (Handle s -> MVector s Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle s
rootMap) Int
0 Index
root'
      if Index -> Bool
P.nullIndex Index
l
        then do
          (Bool, Index, Index) -> ST s (Bool, Index, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Bool
False, Index
root', Index
root')
        else do
          k
kl <- MVector (PrimState (ST s)) k -> Int -> ST s k
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s k
MVector (PrimState (ST s)) k
kMap (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
l)
          (Bool, Index, Index) -> ST s (Bool, Index, Index)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (k
kl k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k, Index
l, Index
root')

-- | Amoritzed \(O(\log n)\). Returns whether a node with key \(k\) is in the map.
--
-- @since 1.2.1.0
{-# INLINE member #-}
member :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m Bool
member :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> k -> m Bool
member Map (PrimState m) f k v
m k
k = ST (PrimState m) Bool -> m Bool
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Bool -> m Bool)
-> ST (PrimState m) Bool -> m Bool
forall a b. (a -> b) -> a -> b
$ do
  (!Bool
b, !Index
_, !Index
_) <- Map (PrimState m) f k v
-> k -> ST (PrimState m) (Bool, Index, Index)
forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> k -> ST s (Bool, Index, Index)
lookupNodeST Map (PrimState m) f k v
m k
k
  Bool -> ST (PrimState m) Bool
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Bool
b

-- | Amortized \(O(\log n)\). Looks up for the monoid value of a node with key \(k\).
--
-- @since 1.2.1.0
{-# INLINE lookup #-}
lookup :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe v)
lookup :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> k -> m (Maybe v)
lookup m :: Map (PrimState m) f k v
m@Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} k
k = ST (PrimState m) (Maybe v) -> m (Maybe v)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Maybe v) -> m (Maybe v))
-> ST (PrimState m) (Maybe v) -> m (Maybe v)
forall a b. (a -> b) -> a -> b
$ do
  (!Bool
b, !Index
l, !Index
_) <- Map (PrimState m) f k v
-> k -> ST (PrimState m) (Bool, Index, Index)
forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> k -> ST s (Bool, Index, Index)
lookupNodeST Map (PrimState m) f k v
m k
k
  if Bool
b
    then do
      Seq (PrimState m) f v -> 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 ()
Raw.splayST Seq (PrimState m) f v
seqMap Index
l Bool
True
      v -> Maybe v
forall a. a -> Maybe a
Just (v -> Maybe v) -> ST (PrimState m) v -> ST (PrimState m) (Maybe v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState (ST (PrimState m))) v
-> Int -> ST (PrimState m) v
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read (Seq (PrimState m) f v -> MVector (PrimState m) v
forall s f a. Seq s f a -> MVector s a
Seq.vSeq Seq (PrimState m) f v
seqMap) Int
0
    else do
      Maybe v -> ST (PrimState m) (Maybe v)
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe v
forall a. Maybe a
Nothing

-- | Amoritzed \(O(\log n)\). Adjusts the monoid value of a node with key \(k\).
--
-- @since 1.2.1.0
{-# INLINE adjust #-}
adjust :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> (v -> v) -> k -> m ()
adjust :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> (v -> v) -> k -> m ()
adjust m :: Map (PrimState m) f k v
m@Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} v -> v
f k
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
  (!Bool
b, !Index
l, !Index
_) <- Map (PrimState m) f k v
-> k -> ST (PrimState m) (Bool, Index, Index)
forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> k -> ST s (Bool, Index, Index)
lookupNodeST Map (PrimState m) f k v
m k
k
  Bool -> ST (PrimState m) () -> ST (PrimState m) ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when Bool
b (ST (PrimState m) () -> ST (PrimState m) ())
-> ST (PrimState m) () -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ do
    Seq (PrimState m) f v -> 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 ()
Raw.splayST Seq (PrimState m) f v
seqMap Index
l Bool
True
    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 (Handle (PrimState m) -> MVector (PrimState m) Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle (PrimState m)
rootMap) Int
0 Index
l
    Seq (PrimState m) f v -> (v -> v) -> Index -> ST (PrimState m) ()
forall a s f.
(HasCallStack, Monoid a, Unbox a) =>
Seq s f a -> (a -> a) -> Index -> ST s ()
Raw.modifyNodeST Seq (PrimState m) f v
seqMap v -> v
f Index
l

-- | Amortized \(O(\log n)\). Inserts a \((k, v)\) pair. If the key is already present in the map,
-- the associated value is replaced with the supplied value.
--
-- @since 1.2.1.0
{-# INLINE insert #-}
insert :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> v -> m ()
insert :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> k -> v -> m ()
insert Map (PrimState m) f k v
m k
k v
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
  Map (PrimState m) f k v
-> (v -> v -> v) -> k -> v -> ST (PrimState m) ()
forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> (v -> v -> v) -> k -> v -> ST s ()
insertWithST Map (PrimState m) f k v
m v -> v -> v
forall a b. a -> b -> a
const k
k v
v

-- | Amortized \(O(\log n)\). Inserts a \((k, v)\) pairs, combining new value and old value.
--
-- @since 1.2.1.0
{-# INLINE insertWith #-}
insertWith ::
  (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) =>
  -- | Map
  Map (PrimState m) f k v ->
  -- | new -> old -> combined
  (v -> v -> v) ->
  -- | Key
  k ->
  -- | Value
  v ->
  m ()
insertWith :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> (v -> v -> v) -> k -> v -> m ()
insertWith Map (PrimState m) f k v
m v -> v -> v
f k
k v
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
  Map (PrimState m) f k v
-> (v -> v -> v) -> k -> v -> ST (PrimState m) ()
forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> (v -> v -> v) -> k -> v -> ST s ()
insertWithST Map (PrimState m) f k v
m v -> v -> v
f k
k v
v

-- | Amortized \(O(\log n)\).
{-# INLINEABLE insertWithST #-}
insertWithST ::
  (HasCallStack, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) =>
  -- | Map
  Map s f k v ->
  -- | new -> old -> combined
  (v -> v -> v) ->
  -- | Key
  k ->
  -- | Value
  v ->
  ST s ()
insertWithST :: forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> (v -> v -> v) -> k -> v -> ST s ()
insertWithST Map {MVector s k
Handle s
Seq s f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq s f v
kMap :: MVector s k
rootMap :: Handle s
..} v -> v -> v
f k
k v
v = 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
$ do
  -- split and merge
  MVector (PrimState (ST s)) Index
-> (Index -> ST s Index) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
VGM.unsafeModifyM
    (Handle s -> MVector s Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle s
rootMap)
    ( \Index
root -> do
        (!Index
l, !Index
r) <- Seq s f v -> 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)
Raw.splitMaxRightWithST Seq s f v
seqMap Index
root ((Index -> ST s Bool) -> ST s (Index, Index))
-> (Index -> ST s Bool) -> ST s (Index, Index)
forall a b. (a -> b) -> a -> b
$ \Index
i -> do
          k
ki <- MVector (PrimState (ST s)) k -> Int -> ST s k
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s k
MVector (PrimState (ST s)) k
kMap (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i)
          Bool -> ST s Bool
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Bool -> ST s Bool) -> Bool -> ST s Bool
forall a b. (a -> b) -> a -> b
$ k
ki k -> k -> Bool
forall a. Ord a => a -> a -> Bool
<= k
k
        if Index -> Bool
P.nullIndex Index
l
          then do
            -- insert
            Index
node <- Seq s f v -> v -> ST s Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Unbox a) =>
Seq s f a -> a -> ST s Index
Raw.newNodeST Seq s f v
seqMap v
v
            MVector (PrimState (ST s)) k -> Int -> k -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s k
MVector (PrimState (ST s)) k
kMap (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
node) k
k
            Seq s f v -> 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
Raw.mergeST Seq s f v
seqMap Index
node Index
r
          else do
            k
kl <- MVector (PrimState (ST s)) k -> Int -> ST s k
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s k
MVector (PrimState (ST s)) k
kMap (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
l)
            if k
kl k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k
              then do
                -- overwrite the node
                Seq s f v -> 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 ()
Raw.splayST Seq s f v
seqMap Index
l Bool
True
                Seq s f v -> (v -> v) -> Index -> ST s ()
forall a s f.
(HasCallStack, Monoid a, Unbox a) =>
Seq s f a -> (a -> a) -> Index -> ST s ()
Raw.modifyNodeST Seq s f v
seqMap (v -> v -> v
f v
v) Index
l
                MVector (PrimState (ST s)) k -> Int -> k -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s k
MVector (PrimState (ST s)) k
kMap (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
l) k
k
                Seq s f v -> 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
Raw.mergeST Seq s f v
seqMap Index
l Index
r
              else do
                -- insert
                Index
node <- Seq s f v -> v -> ST s Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Unbox a) =>
Seq s f a -> a -> ST s Index
Raw.newNodeST Seq s f v
seqMap v
v
                MVector (PrimState (ST s)) k -> Int -> k -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s k
MVector (PrimState (ST s)) k
kMap (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
node) k
k
                Seq s f v -> 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
Raw.merge3ST Seq s f v
seqMap Index
l Index
node Index
r
    )
    Int
0

-- | Amortized \(O(\log n)\). Deletes an element with key \(k\).
--
-- @since 1.2.1.0
{-# INLINEABLE delete #-}
delete :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe v)
delete :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> k -> m (Maybe v)
delete m :: Map (PrimState m) f k v
m@Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} k
k = ST (PrimState m) (Maybe v) -> m (Maybe v)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Maybe v) -> m (Maybe v))
-> ST (PrimState m) (Maybe v) -> m (Maybe v)
forall a b. (a -> b) -> a -> b
$ do
  (!Bool
b, !Index
l, !Index
_) <- Map (PrimState m) f k v
-> k -> ST (PrimState m) (Bool, Index, Index)
forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> k -> ST s (Bool, Index, Index)
lookupNodeST Map (PrimState m) f k v
m k
k
  if Bool
b
    then do
      let Raw.Seq {Int
MVector (PrimState m) f
MVector (PrimState m) v
MVector (PrimState m) Int
MVector (PrimState m) Bit
MVector (PrimState m) Index
Pool (PrimState m) ()
pSeq :: forall s f a. Seq s f a -> MVector s Index
vSeq :: forall s f a. Seq s f a -> MVector s a
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) v
prodSeq :: MVector (PrimState m) v
revSeq :: MVector (PrimState m) Bit
lazySeq :: MVector (PrimState m) f
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
sSeq :: forall s f a. Seq s f a -> MVector s Int
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
..} = Seq (PrimState m) f v
seqMap
      Seq (PrimState m) f v -> 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 ()
Raw.splayST Seq (PrimState m) f v
seqMap Index
l Bool
True
      Index
xl <- 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
l
      Index
xr <- 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
l
      Bool -> ST (PrimState m) () -> ST (PrimState m) ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
xl) (ST (PrimState m) () -> ST (PrimState m) ())
-> ST (PrimState m) () -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ 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
xl) Index
P.undefIndex
      Bool -> ST (PrimState m) () -> ST (PrimState m) ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
xr) (ST (PrimState m) () -> ST (PrimState m) ())
-> ST (PrimState m) () -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ 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
xr) Index
P.undefIndex
      v
v <- MVector (PrimState (ST (PrimState m))) v
-> Int -> ST (PrimState m) v
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) v
MVector (PrimState (ST (PrimState m))) v
vSeq (Int -> ST (PrimState m) v) -> Int -> ST (PrimState m) v
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
l
      Seq (PrimState m) f v -> Index -> ST (PrimState m) ()
forall s v a. Seq s v a -> Index -> ST s ()
Raw.freeNodeST Seq (PrimState m) f v
seqMap Index
l
      Index
root'' <- Seq (PrimState m) f v -> 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
Raw.mergeST Seq (PrimState m) f v
seqMap Index
xl Index
xr
      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 (Handle (PrimState m) -> MVector (PrimState m) Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle (PrimState m)
rootMap) Int
0 Index
root''
      Maybe v -> ST (PrimState m) (Maybe v)
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe v -> ST (PrimState m) (Maybe v))
-> Maybe v -> ST (PrimState m) (Maybe v)
forall a b. (a -> b) -> a -> b
$ v -> Maybe v
forall a. a -> Maybe a
Just v
v
    else do
      Maybe v -> ST (PrimState m) (Maybe v)
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe v
forall a. Maybe a
Nothing

-- | Amortized \(O(\log n)\). Deletes an element with key \(k\).
--
-- @since 1.2.1.0
{-# INLINE delete_ #-}
delete_ :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m ()
delete_ :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> k -> m ()
delete_ Map (PrimState m) f k v
m k
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
  Maybe v
_ <- Map (PrimState (ST (PrimState m))) f k v
-> k -> ST (PrimState m) (Maybe v)
forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> k -> m (Maybe v)
delete Map (PrimState m) f k v
Map (PrimState (ST (PrimState m))) f k v
m k
k
  () -> ST (PrimState m) ()
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()

-- | Amortized \(O(\log n)\). Captures a node that corresponds to \([k1, k2)\).
{-# INLINEABLE sliceST #-}
sliceST :: (HasCallStack, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map s f k v -> k -> k -> ST s P.Index
sliceST :: forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> k -> k -> ST s Index
sliceST Map {MVector s k
Handle s
Seq s f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq s f v
kMap :: MVector s k
rootMap :: Handle s
..} k
k1 k
k2 = do
  let handle :: MVector s Index
handle = Handle s -> MVector s Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle s
rootMap
  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
handle Int
0
  if Index -> Bool
P.nullIndex Index
root
    then Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
P.undefIndex
    else do
      (!Index
lm, !Index
r) <- Seq s f v -> 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)
Raw.splitMaxRightWithST Seq s f v
seqMap Index
root ((Index -> ST s Bool) -> ST s (Index, Index))
-> (Index -> ST s Bool) -> ST s (Index, Index)
forall a b. (a -> b) -> a -> b
$ \Index
i -> do
        k
k' <- MVector (PrimState (ST s)) k -> Int -> ST s k
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s k
MVector (PrimState (ST s)) k
kMap (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i)
        Bool -> ST s Bool
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Bool -> ST s Bool) -> Bool -> ST s Bool
forall a b. (a -> b) -> a -> b
$! k
k' k -> k -> Bool
forall a. Ord a => a -> a -> Bool
< k
k2

      case (Index -> Bool
P.nullIndex Index
lm, Index -> Bool
P.nullIndex Index
r) of
        (Bool
True, Bool
True) -> String -> ST s Index
forall a. HasCallStack => String -> a
error String
"unreachable"
        (Bool
True, Bool
False) -> 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
handle Int
0 Index
r
          Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
P.undefIndex
        (Bool
False, Bool
True) -> do
          (!Index
l, !Index
root') <- Seq s f v -> 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)
Raw.maxRightWithST Seq s f v
seqMap Index
lm ((Index -> ST s Bool) -> ST s (Index, Index))
-> (Index -> ST s Bool) -> ST s (Index, Index)
forall a b. (a -> b) -> a -> b
$ \Index
i -> do
            k
k' <- MVector (PrimState (ST s)) k -> Int -> ST s k
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s k
MVector (PrimState (ST s)) k
kMap (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i)
            Bool -> ST s Bool
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Bool -> ST s Bool) -> Bool -> ST s Bool
forall a b. (a -> b) -> a -> b
$! k
k' k -> k -> Bool
forall a. Ord a => a -> a -> Bool
< k
k1
          if Index -> Bool
P.nullIndex Index
l
            then 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
handle Int
0 Index
root'
              Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root'
            else do
              Seq s f v -> 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 ()
Raw.splayST Seq s f v
seqMap Index
l Bool
True
              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
handle Int
0 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
rSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
l)
        (Bool
False, Bool
False) -> do
          Index
r' <- Seq s f v -> 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
Raw.splayKthST Seq s f v
seqMap Index
r 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
handle Int
0 Index
r'
          (!Index
l, !Index
root') <- Seq s f v -> 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)
Raw.maxRightWithST Seq s f v
seqMap Index
lm ((Index -> ST s Bool) -> ST s (Index, Index))
-> (Index -> ST s Bool) -> ST s (Index, Index)
forall a b. (a -> b) -> a -> b
$ \Index
i -> do
            k
k' <- MVector (PrimState (ST s)) k -> Int -> ST s k
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s k
MVector (PrimState (ST s)) k
kMap (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i)
            Bool -> ST s Bool
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Bool -> ST s Bool) -> Bool -> ST s Bool
forall a b. (a -> b) -> a -> b
$! k
k' k -> k -> Bool
forall a. Ord a => a -> a -> Bool
< k
k1
          if Index -> Bool
P.nullIndex Index
l
            then do
              -- root' is [l, r)
              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
root') Index
r'
              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
r') Index
root'
              Seq s f v -> Index -> ST s ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
Raw.updateNodeST Seq s f v
seqMap Index
root'
              Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root'
            else do
              -- o--l--o--r--o
              --          r
              --     /---/
              --    l
              --     \
              --      m
              Seq s f v -> 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 ()
Raw.splayST Seq s f v
seqMap Index
l Bool
True
              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
l) Index
r'
              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
r') Index
l
              Seq s f v -> Index -> ST s ()
forall a s f. (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()
Raw.updateNodeST Seq s f v
seqMap 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
l)
  where
    Raw.Seq {Int
MVector s f
MVector s v
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
pSeq :: forall s f a. Seq s f a -> MVector s Index
vSeq :: forall s f a. Seq s f a -> MVector s a
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
sSeq :: forall s f a. Seq s f a -> MVector s Int
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
rSeq :: MVector s Index
pSeq :: MVector s Index
lSeq :: MVector s Index
nSeq :: Int
poolSeq :: Pool s ()
sSeq :: MVector s Int
vSeq :: MVector s v
prodSeq :: MVector s v
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} = Seq s f v
seqMap

-- | Amortized \(O(\log n)\). Returns the monoid product in an interval \([k_1, k_2)\). Throws an
-- error for \(k_1 \gt k_2\).
--
-- ==== Constraints
-- - \(k_1 \le k_2\)
--
-- @since 1.2.1.0
{-# INLINE prod #-}
prod :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> k -> m v
prod :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> k -> k -> m v
prod m :: Map (PrimState m) f k v
m@Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} k
l k
r = ST (PrimState m) v -> m v
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) v -> m v) -> ST (PrimState m) v -> m v
forall a b. (a -> b) -> a -> b
$ do
  let !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (k
l k -> k -> Bool
forall a. Ord a => a -> a -> Bool
<= k
r) String
"AtCoder.Extra.Seq.Map.prod: k1 > k2"
  Index
root <- 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 (Handle (PrimState m) -> MVector (PrimState m) Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle (PrimState m)
rootMap) Int
0
  if Index -> Bool
P.nullIndex Index
root Bool -> Bool -> Bool
|| k
l k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
r
    then v -> ST (PrimState m) v
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure v
forall a. Monoid a => a
mempty
    else Map (PrimState m) f k v -> k -> k -> ST (PrimState m) v
forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> k -> k -> ST s v
unsafeProdST Map (PrimState m) f k v
m k
l k
r

-- | Amortized \(O(\log n)\). Returns the monoid product in an interval \([k_1, k_2)\). Returns
-- `Nothing` if an invalid interval is given or for an empty sequence.
--
-- @since 1.2.1.0
{-# INLINE prodMaybe #-}
prodMaybe :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> k -> m (Maybe v)
prodMaybe :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> k -> k -> m (Maybe v)
prodMaybe Map (PrimState m) f k v
m k
l k
r
  | k
l k -> k -> Bool
forall a. Ord a => a -> a -> Bool
> k
r = Maybe v -> m (Maybe v)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe v
forall a. Maybe a
Nothing
  | Bool
otherwise = v -> Maybe v
forall a. a -> Maybe a
Just (v -> Maybe v) -> m v -> m (Maybe v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Map (PrimState m) f k v -> k -> k -> m v
forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> k -> k -> m v
prod Map (PrimState m) f k v
m k
l k
r

-- | Amortized \(O(\log n)\). Returns the monoid product in an interval \([k_1, k_2)\). Returns
-- `Nothing` if an invalid interval is given or for an empty sequence.
--
-- @since 1.2.1.0
{-# INLINE allProd #-}
allProd :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> m v
allProd :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> m v
allProd Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} = do
  Index
root <- MVector (PrimState m) Index -> Int -> m Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read (Handle (PrimState m) -> MVector (PrimState m) Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle (PrimState m)
rootMap) Int
0
  if Index -> Bool
P.nullIndex Index
root
    then v -> m v
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure v
forall a. Monoid a => a
mempty
    else MVector (PrimState m) v -> Int -> m v
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read (Seq (PrimState m) f v -> MVector (PrimState m) v
forall s f a. Seq s f a -> MVector s a
Raw.prodSeq Seq (PrimState m) f v
seqMap) (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)

-- | Amortized \(O(\log n)\).
--
-- ==== Constraint
-- - \(0 \le \lt r \le n\). Note that the interval must have positive length.
{-# INLINEABLE unsafeProdST #-}
unsafeProdST :: (HasCallStack, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map s f k v -> k -> k -> ST s v
unsafeProdST :: forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> k -> k -> ST s v
unsafeProdST m :: Map s f k v
m@Map {MVector s k
Handle s
Seq s f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq s f v
kMap :: MVector s k
rootMap :: Handle s
..} k
l k
r = do
  let Seq.Seq {Int
MVector s f
MVector s v
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
pSeq :: forall s f a. Seq s f a -> MVector s Index
vSeq :: forall s f a. Seq s f a -> MVector s a
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
sSeq :: forall s f a. Seq s f a -> MVector s Int
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 v
prodSeq :: MVector s v
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} = Seq s f v
seqMap
  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 (Handle s -> MVector s Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle s
rootMap) Int
0
  Seq s f v -> Index -> ST s ()
forall s f v. HasCallStack => Seq s f v -> Index -> ST s ()
assertRootST Seq s f v
seqMap Index
root -- TODO: remove
  Index
target <- Map s f k v -> k -> k -> ST s Index
forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> k -> k -> ST s Index
sliceST Map s f k v
m k
l k
r
  if Index -> Bool
P.nullIndex Index
target
    then v -> ST s v
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure v
forall a. Monoid a => a
mempty
    else do
      v
res <- MVector (PrimState (ST s)) v -> Int -> ST s v
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s v
MVector (PrimState (ST s)) v
prodSeq (Int -> ST s v) -> Int -> ST s v
forall a b. (a -> b) -> a -> b
$ Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
target
      Seq s f v -> 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 ()
Raw.splayST Seq s f v
seqMap Index
target Bool
True
      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 (Handle s -> MVector s Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle s
rootMap) Int
0 Index
target
      v -> ST s v
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure v
res

-- | Amortized \(O(\log n)\). Given an interval \([l, r)\), applies a monoid action \(f\).
--
-- ==== Constraints
-- - \(0 \le l \le r \le n\)
-- - The root must point to a non-empty sequence.
--
-- @since 1.2.1.0
{-# INLINEABLE applyIn #-}
applyIn :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> k -> f -> m ()
applyIn :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> k -> k -> f -> m ()
applyIn m :: Map (PrimState m) f k v
m@Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} k
l k
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
  let !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (k
l k -> k -> Bool
forall a. Ord a => a -> a -> Bool
<= k
r) String
"AtCoder.Extra.Seq.Map.applyIn: k1 > k2"
  Bool -> ST (PrimState m) () -> ST (PrimState m) ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (k
l k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
r) (ST (PrimState m) () -> ST (PrimState m) ())
-> ST (PrimState m) () -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ do
    Index
target <- Map (PrimState m) f k v -> k -> k -> ST (PrimState m) Index
forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> k -> k -> ST s Index
sliceST Map (PrimState m) f k v
m k
l k
r
    Bool -> ST (PrimState m) () -> ST (PrimState m) ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
target) (ST (PrimState m) () -> ST (PrimState m) ())
-> ST (PrimState m) () -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ do
      Seq (PrimState m) f v -> Index -> f -> ST (PrimState m) ()
forall f a s.
(HasCallStack, SegAct f a, Unbox f, Monoid a, Unbox a) =>
Seq s f a -> Index -> f -> ST s ()
Raw.applyNodeST Seq (PrimState m) f v
seqMap Index
target f
act
      Seq (PrimState m) f v -> 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 ()
Raw.splayST Seq (PrimState m) f v
seqMap Index
target Bool
True
      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 (Handle (PrimState m) -> MVector (PrimState m) Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle (PrimState m)
rootMap) Int
0 Index
target

-- | Amortized \(O(\log n)\).
--
-- @since 1.2.1.0
{-# INLINE applyAll #-}
applyAll :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> f -> m ()
applyAll :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> f -> m ()
applyAll Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} 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.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read (Handle (PrimState m) -> MVector (PrimState m) Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle (PrimState m)
rootMap) Int
0
  Seq (PrimState m) f v -> 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 ()
Raw.applyToRootST Seq (PrimState m) f v
seqMap Index
root f
act

-- -------------------------------------------------------------------------------------------
-- Key-based bisection method
-- -------------------------------------------------------------------------------------------

-- | Amortized \(O(\log n)\). Looks up for \((k, v)\) pair with the maximum key \(k\) such that
-- \(k \le k_{\mathrm{ref}}\).
--
-- @since 1.2.1.0
{-# INLINE lookupLE #-}
lookupLE :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe (k, v))
lookupLE :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> k -> m (Maybe (k, v))
lookupLE Map (PrimState m) f k v
m k
k = ST (PrimState m) (Maybe (k, v)) -> m (Maybe (k, v))
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Maybe (k, v)) -> m (Maybe (k, v)))
-> ST (PrimState m) (Maybe (k, v)) -> m (Maybe (k, v))
forall a b. (a -> b) -> a -> b
$ do
  Map (PrimState m) f k v
-> k -> Ordering -> ST (PrimState m) (Maybe (k, v))
forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> k -> Ordering -> ST s (Maybe (k, v))
lookupImplL Map (PrimState m) f k v
m k
k Ordering
EQ

-- | Amortized \(O(\log n)\). Looks up for \((k, v)\) pair with the maximum key \(k\) such that
-- \(k \lt k_{\mathrm{ref}}\).
--
-- @since 1.2.1.0
{-# INLINE lookupLT #-}
lookupLT :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe (k, v))
lookupLT :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> k -> m (Maybe (k, v))
lookupLT Map (PrimState m) f k v
m k
k = ST (PrimState m) (Maybe (k, v)) -> m (Maybe (k, v))
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Maybe (k, v)) -> m (Maybe (k, v)))
-> ST (PrimState m) (Maybe (k, v)) -> m (Maybe (k, v))
forall a b. (a -> b) -> a -> b
$ do
  Map (PrimState m) f k v
-> k -> Ordering -> ST (PrimState m) (Maybe (k, v))
forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> k -> Ordering -> ST s (Maybe (k, v))
lookupImplL Map (PrimState m) f k v
m k
k Ordering
LT

-- | Amortized \(O(\log n)\).
{-# INLINEABLE lookupImplL #-}
lookupImplL :: (HasCallStack, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map s f k v -> k -> Ordering -> ST s (Maybe (k, v))
lookupImplL :: forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> k -> Ordering -> ST s (Maybe (k, v))
lookupImplL Map {MVector s k
Handle s
Seq s f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq s f v
kMap :: MVector s k
rootMap :: Handle s
..} k
k Ordering
o = do
  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 (Handle s -> MVector s Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle s
rootMap) Int
0
  if Index -> Bool
P.nullIndex Index
root
    then Maybe (k, v) -> ST s (Maybe (k, v))
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe (k, v)
forall a. Maybe a
Nothing
    else do
      (!Index
l, !Index
root') <- Seq s f v -> 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)
Raw.maxRightWithST Seq s f v
seqMap Index
root ((Index -> ST s Bool) -> ST s (Index, Index))
-> (Index -> ST s Bool) -> ST s (Index, Index)
forall a b. (a -> b) -> a -> b
$ \Index
i -> do
        k
ki <- MVector (PrimState (ST s)) k -> Int -> ST s k
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s k
MVector (PrimState (ST s)) k
kMap (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i)
        Bool -> ST s Bool
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Bool -> ST s Bool) -> Bool -> ST s Bool
forall a b. (a -> b) -> a -> b
$! k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
ki k
k Ordering -> Ordering -> Bool
forall a. Ord a => a -> a -> Bool
<= Ordering
o
      if Index -> Bool
P.nullIndex Index
l
        then 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 (Handle s -> MVector s Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle s
rootMap) Int
0 Index
root'
          Maybe (k, v) -> ST s (Maybe (k, v))
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe (k, v)
forall a. Maybe a
Nothing
        else do
          Seq s f v -> 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 ()
Raw.splayST Seq s f v
seqMap Index
l Bool
True -- TODO: is it True?
          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 (Handle s -> MVector s Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle s
rootMap) Int
0 Index
l
          k
kl <- MVector (PrimState (ST s)) k -> Int -> ST s k
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s k
MVector (PrimState (ST s)) k
kMap (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
l)
          v
vl <- MVector (PrimState (ST s)) v -> Int -> ST s v
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read (Seq s f v -> MVector s v
forall s f a. Seq s f a -> MVector s a
Seq.vSeq Seq s f v
seqMap) (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
l)
          Maybe (k, v) -> ST s (Maybe (k, v))
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe (k, v) -> ST s (Maybe (k, v)))
-> Maybe (k, v) -> ST s (Maybe (k, v))
forall a b. (a -> b) -> a -> b
$! (k, v) -> Maybe (k, v)
forall a. a -> Maybe a
Just (k
kl, v
vl)

-- | Amortized \(O(\log n)\). Looks up for \((k, v)\) pair with the minimum key \(k\) such that
-- \(k \ge k_{\mathrm{ref}}\).
--
-- @since 1.2.1.0
{-# INLINE lookupGE #-}
lookupGE :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe (k, v))
lookupGE :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> k -> m (Maybe (k, v))
lookupGE Map (PrimState m) f k v
m k
k = ST (PrimState m) (Maybe (k, v)) -> m (Maybe (k, v))
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Maybe (k, v)) -> m (Maybe (k, v)))
-> ST (PrimState m) (Maybe (k, v)) -> m (Maybe (k, v))
forall a b. (a -> b) -> a -> b
$ do
  Map (PrimState m) f k v
-> k -> Ordering -> ST (PrimState m) (Maybe (k, v))
forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> k -> Ordering -> ST s (Maybe (k, v))
lookupImplR Map (PrimState m) f k v
m k
k Ordering
LT

-- | Amortized \(O(\log n)\). Looks up for \((k, v)\) pair with the minimum key \(k\) such that
-- \(k \gt k_{\mathrm{ref}}\).
--
-- @since 1.2.1.0
{-# INLINE lookupGT #-}
lookupGT :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe (k, v))
lookupGT :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> k -> m (Maybe (k, v))
lookupGT Map (PrimState m) f k v
m k
k = ST (PrimState m) (Maybe (k, v)) -> m (Maybe (k, v))
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Maybe (k, v)) -> m (Maybe (k, v)))
-> ST (PrimState m) (Maybe (k, v)) -> m (Maybe (k, v))
forall a b. (a -> b) -> a -> b
$ do
  Map (PrimState m) f k v
-> k -> Ordering -> ST (PrimState m) (Maybe (k, v))
forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> k -> Ordering -> ST s (Maybe (k, v))
lookupImplR Map (PrimState m) f k v
m k
k Ordering
EQ

-- | Amortized \(O(\log n)\).
{-# INLINEABLE lookupImplR #-}
lookupImplR :: (HasCallStack, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map s f k v -> k -> Ordering -> ST s (Maybe (k, v))
lookupImplR :: forall f k v s.
(HasCallStack, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v,
 Unbox v, SegAct f v) =>
Map s f k v -> k -> Ordering -> ST s (Maybe (k, v))
lookupImplR Map {MVector s k
Handle s
Seq s f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq s f v
kMap :: MVector s k
rootMap :: Handle s
..} k
k Ordering
o = do
  let handle :: MVector s Index
handle = Handle s -> MVector s Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle s
rootMap
  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
handle Int
0
  if Index -> Bool
P.nullIndex Index
root
    then Maybe (k, v) -> ST s (Maybe (k, v))
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe (k, v)
forall a. Maybe a
Nothing
    else do
      let Raw.Seq {Int
MVector s f
MVector s v
MVector s Int
MVector s Bit
MVector s Index
Pool s ()
pSeq :: forall s f a. Seq s f a -> MVector s Index
vSeq :: forall s f a. Seq s f a -> MVector s a
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
sSeq :: forall s f a. Seq s f a -> MVector s Int
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 v
prodSeq :: MVector s v
revSeq :: MVector s Bit
lazySeq :: MVector s f
..} = Seq s f v
seqMap
      (!Index
l, !Index
root') <- Seq s f v -> 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)
Raw.maxRightWithST Seq s f v
seqMap Index
root ((Index -> ST s Bool) -> ST s (Index, Index))
-> (Index -> ST s Bool) -> ST s (Index, Index)
forall a b. (a -> b) -> a -> b
$ \Index
i -> do
        k
k' <- MVector (PrimState (ST s)) k -> Int -> ST s k
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s k
MVector (PrimState (ST s)) k
kMap (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i)
        Bool -> ST s Bool
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Bool -> ST s Bool) -> Bool -> ST s Bool
forall a b. (a -> b) -> a -> b
$! k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k' k
k Ordering -> Ordering -> Bool
forall a. Ord a => a -> a -> Bool
<= Ordering
o

      if Index -> Bool
P.nullIndex Index
l
        then do
          Index
r <- Seq s f v -> 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
Raw.splayKthST Seq s f v
seqMap (Index -> Index
forall a b. Coercible a b => a -> b
coerce Index
root') 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
handle Int
0 Index
r
          k
kr <- MVector (PrimState (ST s)) k -> Int -> ST s k
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s k
MVector (PrimState (ST s)) k
kMap (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
r)
          v
vr <- MVector (PrimState (ST s)) v -> Int -> ST s v
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s v
MVector (PrimState (ST s)) v
vSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
r)
          Maybe (k, v) -> ST s (Maybe (k, v))
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe (k, v) -> ST s (Maybe (k, v)))
-> Maybe (k, v) -> ST s (Maybe (k, v))
forall a b. (a -> b) -> a -> b
$ (k, v) -> Maybe (k, v)
forall a. a -> Maybe a
Just (k
kr, v
vr)
        else do
          Seq s f v -> 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 ()
Raw.splayST Seq s f v
seqMap Index
l Bool
True -- TODO: is it `True`?
          Index
r0 <- 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
l)
          if Index -> Bool
P.nullIndex Index
r0
            then 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
handle Int
0 Index
l
              Maybe (k, v) -> ST s (Maybe (k, v))
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe (k, v)
forall a. Maybe a
Nothing
            else do
              Index
r <- Seq s f v -> 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
Raw.splayKthST Seq s f v
seqMap (Index -> Index
forall a b. Coercible a b => a -> b
coerce Index
r0) 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
handle Int
0 Index
r
              k
kr <- MVector (PrimState (ST s)) k -> Int -> ST s k
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s k
MVector (PrimState (ST s)) k
kMap (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
r)
              v
vr <- MVector (PrimState (ST s)) v -> Int -> ST s v
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s v
MVector (PrimState (ST s)) v
vSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
r)
              Maybe (k, v) -> ST s (Maybe (k, v))
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe (k, v) -> ST s (Maybe (k, v)))
-> Maybe (k, v) -> ST s (Maybe (k, v))
forall a b. (a -> b) -> a -> b
$ (k, v) -> Maybe (k, v)
forall a. a -> Maybe a
Just (k
kr, v
vr)

-- -------------------------------------------------------------------------------------------
-- Index-based operations
-- -------------------------------------------------------------------------------------------

-- | Amortized \(O(\log n)\).
--
-- @since 1.2.1.0
{-# INLINE readAt #-}
readAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> m v
readAt :: forall (m :: * -> *) f v k.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v,
 Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> Int -> m v
readAt Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} Int
i = ST (PrimState m) v -> m v
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) v -> m v) -> ST (PrimState m) v -> m v
forall a b. (a -> b) -> a -> b
$ do
  Seq (PrimState (ST (PrimState m))) f v
-> Handle (PrimState (ST (PrimState m)))
-> Int
-> ST (PrimState m) v
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
Seq.read Seq (PrimState m) f v
Seq (PrimState (ST (PrimState m))) f v
seqMap Handle (PrimState m)
Handle (PrimState (ST (PrimState m)))
rootMap Int
i

-- | Amortized \(O(\log n)\).
--
-- @since 1.2.1.0
{-# INLINE readMaybeAt #-}
readMaybeAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> m (Maybe v)
readMaybeAt :: forall (m :: * -> *) f v k.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v,
 Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> Int -> m (Maybe v)
readMaybeAt Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} Int
i = ST (PrimState m) (Maybe v) -> m (Maybe v)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Maybe v) -> m (Maybe v))
-> ST (PrimState m) (Maybe v) -> m (Maybe v)
forall a b. (a -> b) -> a -> b
$ do
  Seq (PrimState (ST (PrimState m))) f v
-> Handle (PrimState (ST (PrimState m)))
-> Int
-> ST (PrimState m) (Maybe v)
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)
Seq.readMaybe Seq (PrimState m) f v
Seq (PrimState (ST (PrimState m))) f v
seqMap Handle (PrimState m)
Handle (PrimState (ST (PrimState m)))
rootMap Int
i

-- | Amortized \(O(\log n)\).
--
-- @since 1.2.1.0
{-# INLINE writeAt #-}
writeAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> v -> m ()
writeAt :: forall (m :: * -> *) f v k.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v,
 Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> Int -> v -> m ()
writeAt Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} Int
i v
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
  Seq (PrimState (ST (PrimState m))) f v
-> Handle (PrimState (ST (PrimState m)))
-> Int
-> v
-> ST (PrimState m) ()
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 ()
Seq.write Seq (PrimState m) f v
Seq (PrimState (ST (PrimState m))) f v
seqMap Handle (PrimState m)
Handle (PrimState (ST (PrimState m)))
rootMap Int
i v
v

-- | Amortized \(O(\log n)\).
--
-- @since 1.2.1.0
{-# INLINE modifyAt #-}
modifyAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> (v -> v) -> Int -> m ()
modifyAt :: forall (m :: * -> *) f v k.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v,
 Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> (v -> v) -> Int -> m ()
modifyAt Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} v -> v
f 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
  Seq (PrimState (ST (PrimState m))) f v
-> Handle (PrimState (ST (PrimState m)))
-> (v -> v)
-> Int
-> ST (PrimState m) ()
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 ()
Seq.modify Seq (PrimState m) f v
Seq (PrimState (ST (PrimState m))) f v
seqMap Handle (PrimState m)
Handle (PrimState (ST (PrimState m)))
rootMap v -> v
f Int
i

-- | Amortized \(O(\log n)\).
--
-- @since 1.2.1.0
{-# INLINE exchangeAt #-}
exchangeAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> v -> m v
exchangeAt :: forall (m :: * -> *) f v k.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v,
 Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> Int -> v -> m v
exchangeAt Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} Int
i v
v = ST (PrimState m) v -> m v
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) v -> m v) -> ST (PrimState m) v -> m v
forall a b. (a -> b) -> a -> b
$ do
  Seq (PrimState (ST (PrimState m))) f v
-> Handle (PrimState (ST (PrimState m)))
-> Int
-> v
-> ST (PrimState m) v
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
Seq.exchange Seq (PrimState m) f v
Seq (PrimState (ST (PrimState m))) f v
seqMap Handle (PrimState m)
Handle (PrimState (ST (PrimState m)))
rootMap Int
i v
v

-- | Amortized \(O(\log n)\).
--
-- @since 1.2.1.0
{-# INLINE prodInInterval #-}
prodInInterval :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> Int -> m v
prodInInterval :: forall (m :: * -> *) f v k.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v,
 Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> Int -> Int -> m v
prodInInterval Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} Int
l Int
r = ST (PrimState m) v -> m v
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) v -> m v) -> ST (PrimState m) v -> m v
forall a b. (a -> b) -> a -> b
$ do
  Seq (PrimState (ST (PrimState m))) f v
-> Handle (PrimState (ST (PrimState m)))
-> Int
-> Int
-> ST (PrimState m) v
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
Seq.prod Seq (PrimState m) f v
Seq (PrimState (ST (PrimState m))) f v
seqMap Handle (PrimState m)
Handle (PrimState (ST (PrimState m)))
rootMap Int
l Int
r

-- | Amortized \(O(\log n)\).
--
-- @since 1.2.1.0
{-# INLINE applyInInterval #-}
applyInInterval :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> Int -> f -> m ()
applyInInterval :: forall (m :: * -> *) f v k.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v,
 Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> Int -> Int -> f -> m ()
applyInInterval Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} Int
l Int
r f
f = 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
  Seq (PrimState (ST (PrimState m))) f v
-> Handle (PrimState (ST (PrimState m)))
-> Int
-> Int
-> f
-> ST (PrimState m) ()
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 ()
Seq.applyIn Seq (PrimState m) f v
Seq (PrimState (ST (PrimState m))) f v
seqMap Handle (PrimState m)
Handle (PrimState (ST (PrimState m)))
rootMap Int
l Int
r f
f

-- | Amortized \(O(\log n)\).
--
-- @since 1.2.1.0
{-# INLINE ilowerBound #-}
ilowerBound ::
  (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Map
  Map (PrimState m) f k a ->
  -- | 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 k.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Map (PrimState m) f k a -> (Int -> a -> Bool) -> m Int
ilowerBound Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f a
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f a
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} 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
  Seq (PrimState (ST (PrimState m))) f a
-> Handle (PrimState (ST (PrimState m)))
-> (Int -> a -> Bool)
-> ST (PrimState m) Int
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
Seq.ilowerBound Seq (PrimState m) f a
Seq (PrimState (ST (PrimState m))) f a
seqMap Handle (PrimState m)
Handle (PrimState (ST (PrimState m)))
rootMap Int -> a -> Bool
f

-- | Amortized \(O(\log n)\).
--
-- @since 1.2.1.0
{-# INLINE ilowerBoundM #-}
ilowerBoundM ::
  (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Map
  Map (PrimState m) f k a ->
  -- | 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 k.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Map (PrimState m) f k a -> (Int -> a -> m Bool) -> m Int
ilowerBoundM Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f a
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f a
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} Int -> a -> m Bool
f = do
  Seq (PrimState m) f a
-> Handle (PrimState m) -> (Int -> a -> m Bool) -> m Int
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
Seq.ilowerBoundM Seq (PrimState m) f a
seqMap Handle (PrimState m)
rootMap Int -> a -> m Bool
f

-- | Amortized \(O(\log n)\).
--
-- @since 1.2.1.0
{-# INLINE ilowerBoundProd #-}
ilowerBoundProd ::
  (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Map
  Map (PrimState m) f k a ->
  -- | 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 k.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Map (PrimState m) f k a -> (Int -> a -> Bool) -> m Int
ilowerBoundProd Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f a
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f a
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} 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
  Seq (PrimState (ST (PrimState m))) f a
-> Handle (PrimState (ST (PrimState m)))
-> (Int -> a -> Bool)
-> ST (PrimState m) Int
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
Seq.ilowerBoundProd Seq (PrimState m) f a
Seq (PrimState (ST (PrimState m))) f a
seqMap Handle (PrimState m)
Handle (PrimState (ST (PrimState m)))
rootMap Int -> a -> Bool
f

-- | Amortized \(O(\log n)\).
--
-- @since 1.2.1.0
{-# INLINE ilowerBoundProdM #-}
ilowerBoundProdM ::
  (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Map
  Map (PrimState m) f k a ->
  -- | 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 k.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
Map (PrimState m) f k a -> (Int -> a -> m Bool) -> m Int
ilowerBoundProdM Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f a
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f a
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} Int -> a -> m Bool
f = do
  Seq (PrimState m) f a
-> Handle (PrimState m) -> (Int -> a -> m Bool) -> m Int
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
Seq.ilowerBoundProdM Seq (PrimState m) f a
seqMap Handle (PrimState m)
rootMap Int -> a -> m Bool
f

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

-- | \(O(n)\) Returns the \(k, v\) pairs in the map
--
-- @since 1.2.1.0
{-# INLINEABLE freeze #-}
freeze :: (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) => Map (PrimState m) f k v -> m (VU.Vector (k, v))
freeze :: forall (m :: * -> *) f k v.
(HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k,
 Unbox k, Monoid v, Unbox v, SegAct f v) =>
Map (PrimState m) f k v -> m (Vector (k, v))
freeze Map {MVector (PrimState m) k
Handle (PrimState m)
Seq (PrimState m) f v
seqMap :: forall s f k v. Map s f k v -> Seq s f v
kMap :: forall s f k v. Map s f k v -> MVector s k
rootMap :: forall s f k v. Map s f k v -> Handle s
seqMap :: Seq (PrimState m) f v
kMap :: MVector (PrimState m) k
rootMap :: Handle (PrimState m)
..} = ST (PrimState m) (Vector (k, v)) -> m (Vector (k, v))
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Vector (k, v)) -> m (Vector (k, v)))
-> ST (PrimState m) (Vector (k, v)) -> m (Vector (k, v))
forall a b. (a -> b) -> a -> b
$ do
  let Raw.Seq {Int
MVector (PrimState m) f
MVector (PrimState m) v
MVector (PrimState m) Int
MVector (PrimState m) Bit
MVector (PrimState m) Index
Pool (PrimState m) ()
pSeq :: forall s f a. Seq s f a -> MVector s Index
vSeq :: forall s f a. Seq s f a -> MVector s a
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
sSeq :: forall s f a. Seq s f a -> MVector s Int
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) v
prodSeq :: MVector (PrimState m) v
revSeq :: MVector (PrimState m) Bit
lazySeq :: MVector (PrimState m) f
..} = Seq (PrimState m) f v
seqMap
  Index
root0 <- 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 (Handle (PrimState m) -> MVector (PrimState m) Index
forall s. Handle s -> MVector s Index
Seq.unHandle Handle (PrimState m)
rootMap) Int
0
  if Index -> Bool
P.nullIndex Index
root0
    then Vector (k, v) -> ST (PrimState m) (Vector (k, v))
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Vector (k, v)
forall a. Unbox a => Vector a
VU.empty
    else do
      Seq (PrimState m) f v -> Index -> ST (PrimState m) ()
forall s f v. HasCallStack => Seq s f v -> Index -> ST s ()
assertRootST Seq (PrimState m) f v
seqMap Index
root0
      Int
size_ <- 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
root0)
      MVector (PrimState m) (k, v)
res <- Int
-> ST (PrimState m) (MVector (PrimState (ST (PrimState m))) (k, v))
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
size_
      let inner :: Int -> Index -> ST (PrimState m) Int
inner Int
i Index
root
            | Index -> Bool
P.nullIndex Index
root = Int -> ST (PrimState m) Int
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
i
            | Bool
otherwise = do
                -- visit from left to right
                Seq (PrimState m) f v -> 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 ()
Raw.propNodeST Seq (PrimState m) f v
seqMap Index
root
                Int
i' <- Int -> Index -> ST (PrimState m) Int
inner Int
i (Index -> ST (PrimState m) Int)
-> ST (PrimState m) Index -> ST (PrimState m) Int
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m 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)
                k
kx <- MVector (PrimState (ST (PrimState m))) k
-> Int -> ST (PrimState m) k
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) k
MVector (PrimState (ST (PrimState m))) k
kMap (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
                v
vx <- MVector (PrimState (ST (PrimState m))) v
-> Int -> ST (PrimState m) v
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) v
MVector (PrimState (ST (PrimState m))) v
vSeq (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
                MVector (PrimState (ST (PrimState m))) (k, v)
-> Int -> (k, v) -> 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) (k, v)
MVector (PrimState (ST (PrimState m))) (k, v)
res Int
i' (k
kx, v
vx)
                Int -> Index -> ST (PrimState m) Int
inner (Int
i' Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (Index -> ST (PrimState m) Int)
-> ST (PrimState m) Index -> ST (PrimState m) Int
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m 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 (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root)
      Int
_ <- Int -> Index -> ST (PrimState m) Int
inner Int
0 Index
root0
      MVector (PrimState (ST (PrimState m))) (k, v)
-> ST (PrimState m) (Vector (k, v))
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> m (Vector a)
VU.unsafeFreeze MVector (PrimState m) (k, v)
MVector (PrimState (ST (PrimState m))) (k, v)
res