-- | Miscellaneous vector functions. These functions are __not__ the fastest implementations, but
-- fills in some lacking features.
--
-- @since 1.2.2.0
module AtCoder.Extra.Vector
  ( -- * Sort functions
    argsort,

    -- * Index compression
    compress,

    -- * Vector Utilities
    iconcatMap,
    concatMapM,
    iconcatMapM,
    mapAccumL,
    chunks,

    -- ** Monadic scanl
    prescanlM,
    prescanlM',
    postscanlM,
    postscanlM',
    scanlM,
    scanlM',
    scanl1M,
    scanl1M',

    -- * Queries
    maxRangeSum,
    minRangeSum,
    slideMinIndices,
    slideMaxIndices,
  )
where

-- TODO: maybe add lexicographic permutations, combinations, and subsequences.

import AtCoder.Internal.Assert qualified as ACIA
import AtCoder.Internal.Queue qualified as Q
import AtCoder.Extra.Bisect (lowerBound)
import Control.Monad (when)
import Control.Monad.Fix (fix)
import Control.Monad.Primitive (PrimMonad)
import Control.Monad.ST (ST, runST)
import Control.Monad.Trans.State.Strict (StateT, runStateT, state)
import Data.Ord (Down (..))
import Data.Vector qualified as V
import Data.Vector.Algorithms.Intro qualified as VAI
import Data.Vector.Fusion.Bundle qualified as Bundle
import Data.Vector.Fusion.Bundle.Monadic qualified as BundleM
import Data.Vector.Fusion.Stream.Monadic qualified as S
import Data.Vector.Generic qualified as VG
import Data.Vector.Generic.Mutable qualified as VGM
import Data.Vector.Unboxed qualified as VU
import GHC.Stack (HasCallStack)

-- | \(O(n \log n)\) Returns indices of the vector elements, stably sorted by their value.
--
-- ==== Example
-- >>> import AtCoder.Extra.Vector qualified as EV
-- >>> import Data.Vector.Unboxed qualified as VU
-- >>> EV.argsort $ VU.fromList @Int [0, 1, 0, 1, 0]
-- [0,2,4,1,3]
--
-- @since 1.2.3.0
{-# INLINEABLE argsort #-}
-- TODO: use generic vector
argsort :: (HasCallStack, Ord a, VU.Unbox a) => VU.Vector a -> VU.Vector Int
argsort :: forall a. (HasCallStack, Ord a, Unbox a) => Vector a -> Vector Int
argsort Vector a
xs =
  (forall s. MVector s Int -> ST s ()) -> Vector Int -> Vector Int
forall a.
Unbox a =>
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
VU.modify
    (Comparison Int -> MVector (PrimState (ST s)) Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) e.
(PrimMonad m, MVector v e) =>
Comparison e -> v (PrimState m) e -> m ()
VAI.sortBy (\Int
i Int
j -> a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Vector a
xs Vector a -> Int -> a
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
i) (Vector a
xs Vector a -> Int -> a
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
j) Ordering -> Ordering -> Ordering
forall a. Semigroup a => a -> a -> a
<> Comparison Int
forall a. Ord a => a -> a -> Ordering
compare Int
i Int
j))
    (Vector Int -> Vector Int) -> Vector Int -> Vector Int
forall a b. (a -> b) -> a -> b
$ Int -> (Int -> Int) -> Vector Int
forall a. Unbox a => Int -> (Int -> a) -> Vector a
VU.generate (Vector a -> Int
forall a. Unbox a => Vector a -> Int
VU.length Vector a
xs) Int -> Int
forall a. a -> a
id

-- | \(O(n \log n)\) One dimensional index compression: xs -> (nubSortXs, xs')
--
-- ==== Example
-- >>> import AtCoder.Extra.Bisect (lowerBound)
-- >>> import AtCoder.Extra.Vector qualified as EV
-- >>> import Data.Vector.Unboxed qualified as VU
-- >>> let xs = VU.fromList [0, 20, 40, 10, 30]
-- >>> let (dict, xs') = EV.compress xs
-- >>> xs'
-- [0,2,4,1,3]
-- >>> lowerBound dict 10
-- 1
--
-- @since 1.5.1.0
{-# INLINE compress #-}
compress :: VU.Vector Int -> (VU.Vector Int, VU.Vector Int)
compress :: Vector Int -> (Vector Int, Vector Int)
compress Vector Int
xs = (Vector Int
dict, (Int -> Int) -> Vector Int -> Vector Int
forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b) -> v a -> v b
VG.map (Vector Int -> Int -> Int
forall (v :: * -> *) a.
(HasCallStack, Vector v a, Ord a) =>
v a -> a -> Int
lowerBound Vector Int
dict) Vector Int
xs)
  where
    !dict :: Vector Int
dict = Vector Int -> Vector Int
forall (v :: * -> *) a. (Vector v a, Eq a) => v a -> v a
VG.uniq (Vector Int -> Vector Int) -> Vector Int -> Vector Int
forall a b. (a -> b) -> a -> b
$ (forall s. Mutable Vector s Int -> ST s ())
-> Vector Int -> Vector Int
forall (v :: * -> *) a.
Vector v a =>
(forall s. Mutable v s a -> ST s ()) -> v a -> v a
VG.modify MVector (PrimState (ST s)) Int -> ST s ()
Mutable Vector s Int -> ST s ()
forall s. Mutable Vector s Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) e.
(PrimMonad m, MVector v e, Ord e) =>
v (PrimState m) e -> m ()
VAI.sort Vector Int
xs

-- | Maps each element to a vector and concatenate the results.
--
-- ==== Example
-- >>> import AtCoder.Extra.Vector qualified as EV
-- >>> import Data.Vector.Unboxed qualified as VU
-- >>> EV.iconcatMap (\i x -> VU.fromList [i + x, i + x]) $ VU.replicate @Int 3 0
-- [0,0,1,1,2,2]
--
-- @since 1.5.1.0
{-# INLINE iconcatMap #-}
iconcatMap :: (HasCallStack, VG.Vector v a, VG.Vector v b) => (Int -> a -> v b) -> v a -> v b
iconcatMap :: forall (v :: * -> *) a b.
(HasCallStack, Vector v a, Vector v b) =>
(Int -> a -> v b) -> v a -> v b
iconcatMap Int -> a -> v b
f =
  Bundle v b -> v b
forall (v :: * -> *) a. Vector v a => Bundle v a -> v a
VG.unstream
    (Bundle v b -> v b) -> (v a -> Bundle v b) -> v a -> v b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bundle v (v b) -> Bundle v b
forall (v :: * -> *) a (u :: * -> *).
Vector v a =>
Bundle u (v a) -> Bundle v a
Bundle.concatVectors
    (Bundle v (v b) -> Bundle v b)
-> (v a -> Bundle v (v b)) -> v a -> Bundle v b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (forall (m :: * -> *). Monad m => Stream m a -> Stream m (v b))
-> (Size -> Size) -> Bundle v a -> Bundle v (v b)
forall a b (v :: * -> *).
(forall (m :: * -> *). Monad m => Stream m a -> Stream m b)
-> (Size -> Size) -> Bundle v a -> Bundle v b
Bundle.inplace (((Int, a) -> v b) -> Stream m (Int, a) -> Stream m (v b)
forall (m :: * -> *) a b.
Monad m =>
(a -> b) -> Stream m a -> Stream m b
S.map ((Int -> a -> v b) -> (Int, a) -> v b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Int -> a -> v b
f) (Stream m (Int, a) -> Stream m (v b))
-> (Stream m a -> Stream m (Int, a))
-> Stream m a
-> Stream m (v b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Stream m a -> Stream m (Int, a)
forall (m :: * -> *) a. Monad m => Stream m a -> Stream m (Int, a)
S.indexed) Size -> Size
forall a. a -> a
id
    (Bundle v a -> Bundle v (v b))
-> (v a -> Bundle v a) -> v a -> Bundle v (v b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v a -> Bundle v a
forall (v :: * -> *) a. Vector v a => v a -> Bundle v a
VG.stream

-- | Maps each element to a vector and concatenate the results.
--
-- ==== Example
-- >>> import AtCoder.Extra.Vector qualified as EV
-- >>> import Data.Vector.Unboxed qualified as VU
-- >>> EV.iconcatMap (\x -> pure (VU.fromList [x, x])) $ VU.generate @Int 3 id
-- [0,0,1,1,2,2]
--
-- @since 1.5.1.0
{-# INLINE concatMapM #-}
concatMapM ::
  (HasCallStack, Monad m, VG.Vector v a, VG.Vector v b) =>
  (a -> m (v b)) ->
  v a ->
  m (v b)
concatMapM :: forall (m :: * -> *) (v :: * -> *) a b.
(HasCallStack, Monad m, Vector v a, Vector v b) =>
(a -> m (v b)) -> v a -> m (v b)
concatMapM a -> m (v b)
f =
  MBundle m v b -> m (v b)
forall (m :: * -> *) (v :: * -> *) a (u :: * -> *).
(Monad m, Vector v a) =>
MBundle m u a -> m (v a)
VG.unstreamM
    (MBundle m v b -> m (v b))
-> (v a -> MBundle m v b) -> v a -> m (v b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bundle m v (v b) -> MBundle m v b
forall (m :: * -> *) (v :: * -> *) a (u :: * -> *).
(Monad m, Vector v a) =>
Bundle m u (v a) -> Bundle m v a
BundleM.concatVectors
    (Bundle m v (v b) -> MBundle m v b)
-> (v a -> Bundle m v (v b)) -> v a -> MBundle m v b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> m (v b)) -> Bundle m v a -> Bundle m v (v b)
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> m b) -> Bundle m v a -> Bundle m v b
BundleM.mapM a -> m (v b)
f
    (Bundle m v a -> Bundle m v (v b))
-> (v a -> Bundle m v a) -> v a -> Bundle m v (v b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v a -> Bundle m v a
forall (m :: * -> *) (v :: * -> *) a.
(Monad m, Vector v a) =>
v a -> Bundle m v a
BundleM.fromVector

-- | Maps each element to a vector and concatenate the results.
--
-- ==== Example
-- >>> import AtCoder.Extra.Vector qualified as EV
-- >>> import Data.Vector.Unboxed qualified as VU
-- >>> EV.iconcatMapM (\i x -> pure (VU.fromList [i + x, i + x])) $ VU.replicate @Int 3 0
-- [0,0,1,1,2,2]
--
-- @since 1.5.1.0
{-# INLINE iconcatMapM #-}
iconcatMapM ::
  (HasCallStack, Monad m, VG.Vector v a, VG.Vector v b) =>
  (Int -> a -> m (v b)) ->
  v a ->
  m (v b)
iconcatMapM :: forall (m :: * -> *) (v :: * -> *) a b.
(HasCallStack, Monad m, Vector v a, Vector v b) =>
(Int -> a -> m (v b)) -> v a -> m (v b)
iconcatMapM Int -> a -> m (v b)
f =
  MBundle m v b -> m (v b)
forall (m :: * -> *) (v :: * -> *) a (u :: * -> *).
(Monad m, Vector v a) =>
MBundle m u a -> m (v a)
VG.unstreamM
    (MBundle m v b -> m (v b))
-> (v a -> MBundle m v b) -> v a -> m (v b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bundle m v (v b) -> MBundle m v b
forall (m :: * -> *) (v :: * -> *) a (u :: * -> *).
(Monad m, Vector v a) =>
Bundle m u (v a) -> Bundle m v a
BundleM.concatVectors
    (Bundle m v (v b) -> MBundle m v b)
-> (v a -> Bundle m v (v b)) -> v a -> MBundle m v b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, a) -> m (v b)) -> Bundle m v (Int, a) -> Bundle m v (v b)
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> m b) -> Bundle m v a -> Bundle m v b
BundleM.mapM ((Int -> a -> m (v b)) -> (Int, a) -> m (v b)
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Int -> a -> m (v b)
f)
    (Bundle m v (Int, a) -> Bundle m v (v b))
-> (v a -> Bundle m v (Int, a)) -> v a -> Bundle m v (v b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bundle m v a -> Bundle m v (Int, a)
forall (m :: * -> *) (v :: * -> *) a.
Monad m =>
Bundle m v a -> Bundle m v (Int, a)
BundleM.indexed
    (Bundle m v a -> Bundle m v (Int, a))
-> (v a -> Bundle m v a) -> v a -> Bundle m v (Int, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v a -> Bundle m v a
forall (m :: * -> *) (v :: * -> *) a.
(Monad m, Vector v a) =>
v a -> Bundle m v a
BundleM.fromVector

-- | \(O(n)\) Maps a vector with an accumulator.
--
-- ==== Example
-- >>> import AtCoder.Extra.Vector qualified as EV
-- >>> import Data.Vector.Unboxed qualified as VU
-- >>> EV.mapAccumL (\s x -> (s + 1, s * x)) (0 :: Int) $ VU.generate @Int 4 id
-- (4,[0,1,4,9])
--
-- @since 1.5.1.0
{-# INLINE mapAccumL #-}
mapAccumL ::
  forall v s a b.
  (HasCallStack, VG.Vector v a, VG.Vector v b) =>
  (s -> a -> (s, b)) ->
  s ->
  v a ->
  (s, v b)
mapAccumL :: forall (v :: * -> *) s a b.
(HasCallStack, Vector v a, Vector v b) =>
(s -> a -> (s, b)) -> s -> v a -> (s, v b)
mapAccumL s -> a -> (s, b)
f s
s0 v a
xs = (\(!v b
x, !s
s) -> (s
s, v b
x)) ((v b, s) -> (s, v b)) -> (v b, s) -> (s, v b)
forall a b. (a -> b) -> a -> b
$ (forall s. ST s (v b, s)) -> (v b, s)
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (v b, s)) -> (v b, s))
-> (forall s. ST s (v b, s)) -> (v b, s)
forall a b. (a -> b) -> a -> b
$ (StateT s (ST s) (v b) -> s -> ST s (v b, s)
forall s (m :: * -> *) a. StateT s m a -> s -> m (a, s)
`runStateT` s
s0) (StateT s (ST s) (v b) -> ST s (v b, s))
-> StateT s (ST s) (v b) -> ST s (v b, s)
forall a b. (a -> b) -> a -> b
$ do
  Bundle (StateT s (ST s)) v b -> StateT s (ST s) (v b)
forall (m :: * -> *) (v :: * -> *) a (u :: * -> *).
(PrimMonad m, Vector v a) =>
Bundle m u a -> m (v a)
unstreamPrimM
    (Bundle (StateT s (ST s)) v b -> StateT s (ST s) (v b))
-> (Bundle (StateT s (ST s)) v a -> Bundle (StateT s (ST s)) v b)
-> Bundle (StateT s (ST s)) v a
-> StateT s (ST s) (v b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> StateT s (ST s) b)
-> Bundle (StateT s (ST s)) v a -> Bundle (StateT s (ST s)) v b
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> m b) -> Bundle m v a -> Bundle m v b
BundleM.mapM a -> StateT s (ST s) b
forall st. a -> StateT s (ST st) b
g
    (Bundle (StateT s (ST s)) v a -> StateT s (ST s) (v b))
-> Bundle (StateT s (ST s)) v a -> StateT s (ST s) (v b)
forall a b. (a -> b) -> a -> b
$ v a -> Bundle (StateT s (ST s)) v a
forall (m :: * -> *) (v :: * -> *) a.
(Monad m, Vector v a) =>
v a -> Bundle m v a
BundleM.fromVector v a
xs
  where
    g :: forall st. a -> StateT s (ST st) b
    g :: forall st. a -> StateT s (ST st) b
g a
a =
      (s -> (b, s)) -> StateT s (ST st) b
forall (m :: * -> *) s a. Monad m => (s -> (a, s)) -> StateT s m a
state
        ( \s
s ->
            let (!s
s', !b
b) = s -> a -> (s, b)
f s
s a
a
             in (b
b, s
s')
        )

-- | https://github.com/haskell/vector/issues/416
{-# INLINE [1] unstreamPrimM #-}
unstreamPrimM :: (PrimMonad m, VG.Vector v a) => BundleM.Bundle m u a -> m (v a)
unstreamPrimM :: forall (m :: * -> *) (v :: * -> *) a (u :: * -> *).
(PrimMonad m, Vector v a) =>
Bundle m u a -> m (v a)
unstreamPrimM Bundle m u a
s = Bundle m u a -> m (Mutable v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
VGM.munstream Bundle m u a
s m (Mutable v (PrimState m) a)
-> (Mutable v (PrimState m) a -> m (v a)) -> m (v a)
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Mutable v (PrimState m) a -> m (v a)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m (v a)
VG.unsafeFreeze

-- | @since 1.5.1.0
{-# INLINE prescanlM #-}
prescanlM :: (HasCallStack, Monad m, VG.Vector v a, VG.Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)
prescanlM :: forall (m :: * -> *) (v :: * -> *) a b.
(HasCallStack, Monad m, Vector v a, Vector v b) =>
(a -> b -> m a) -> a -> v b -> m (v a)
prescanlM a -> b -> m a
f a
x0 =
  MBundle m v a -> m (v a)
forall (m :: * -> *) (v :: * -> *) a (u :: * -> *).
(Monad m, Vector v a) =>
MBundle m u a -> m (v a)
VG.unstreamM
    (MBundle m v a -> m (v a))
-> (v b -> MBundle m v a) -> v b -> m (v a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> m a) -> a -> Bundle v b -> MBundle m v a
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle v b -> Bundle m v a
prescanlMB a -> b -> m a
f a
x0
    (Bundle v b -> MBundle m v a)
-> (v b -> Bundle v b) -> v b -> MBundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v b -> Bundle v b
forall (v :: * -> *) a. Vector v a => v a -> Bundle v a
VG.stream

-- | @since 1.5.1.0
{-# INLINE prescanlM' #-}
prescanlM' :: (HasCallStack, Monad m, VG.Vector v a, VG.Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)
prescanlM' :: forall (m :: * -> *) (v :: * -> *) a b.
(HasCallStack, Monad m, Vector v a, Vector v b) =>
(a -> b -> m a) -> a -> v b -> m (v a)
prescanlM' a -> b -> m a
f a
x0 =
  MBundle m v a -> m (v a)
forall (m :: * -> *) (v :: * -> *) a (u :: * -> *).
(Monad m, Vector v a) =>
MBundle m u a -> m (v a)
VG.unstreamM
    (MBundle m v a -> m (v a))
-> (v b -> MBundle m v a) -> v b -> m (v a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> m a) -> a -> Bundle v b -> MBundle m v a
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle v b -> Bundle m v a
prescanlMB' a -> b -> m a
f a
x0
    (Bundle v b -> MBundle m v a)
-> (v b -> Bundle v b) -> v b -> MBundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v b -> Bundle v b
forall (v :: * -> *) a. Vector v a => v a -> Bundle v a
VG.stream

-- | @since 1.5.1.0
{-# INLINE postscanlM #-}
postscanlM :: (HasCallStack, Monad m, VG.Vector v a, VG.Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)
postscanlM :: forall (m :: * -> *) (v :: * -> *) a b.
(HasCallStack, Monad m, Vector v a, Vector v b) =>
(a -> b -> m a) -> a -> v b -> m (v a)
postscanlM a -> b -> m a
f a
x0 =
  MBundle m v a -> m (v a)
forall (m :: * -> *) (v :: * -> *) a (u :: * -> *).
(Monad m, Vector v a) =>
MBundle m u a -> m (v a)
VG.unstreamM
    (MBundle m v a -> m (v a))
-> (v b -> MBundle m v a) -> v b -> m (v a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> m a) -> a -> Bundle v b -> MBundle m v a
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle v b -> Bundle m v a
postscanlMB a -> b -> m a
f a
x0
    (Bundle v b -> MBundle m v a)
-> (v b -> Bundle v b) -> v b -> MBundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v b -> Bundle v b
forall (v :: * -> *) a. Vector v a => v a -> Bundle v a
VG.stream

-- | @since 1.5.1.0
{-# INLINE postscanlM' #-}
postscanlM' :: (HasCallStack, Monad m, VG.Vector v a, VG.Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)
postscanlM' :: forall (m :: * -> *) (v :: * -> *) a b.
(HasCallStack, Monad m, Vector v a, Vector v b) =>
(a -> b -> m a) -> a -> v b -> m (v a)
postscanlM' a -> b -> m a
f a
x0 =
  MBundle m v a -> m (v a)
forall (m :: * -> *) (v :: * -> *) a (u :: * -> *).
(Monad m, Vector v a) =>
MBundle m u a -> m (v a)
VG.unstreamM
    (MBundle m v a -> m (v a))
-> (v b -> MBundle m v a) -> v b -> m (v a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> m a) -> a -> Bundle v b -> MBundle m v a
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle v b -> Bundle m v a
postscanlMB' a -> b -> m a
f a
x0
    (Bundle v b -> MBundle m v a)
-> (v b -> Bundle v b) -> v b -> MBundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v b -> Bundle v b
forall (v :: * -> *) a. Vector v a => v a -> Bundle v a
VG.stream

-- | @since 1.5.1.0
{-# INLINE scanlM #-}
scanlM :: (HasCallStack, Monad m, VG.Vector v a, VG.Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)
scanlM :: forall (m :: * -> *) (v :: * -> *) a b.
(HasCallStack, Monad m, Vector v a, Vector v b) =>
(a -> b -> m a) -> a -> v b -> m (v a)
scanlM a -> b -> m a
f a
x0 =
  MBundle m v a -> m (v a)
forall (m :: * -> *) (v :: * -> *) a (u :: * -> *).
(Monad m, Vector v a) =>
MBundle m u a -> m (v a)
VG.unstreamM
    (MBundle m v a -> m (v a))
-> (v b -> MBundle m v a) -> v b -> m (v a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> m a) -> a -> Bundle v b -> MBundle m v a
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle v b -> Bundle m v a
scanlMB a -> b -> m a
f a
x0
    (Bundle v b -> MBundle m v a)
-> (v b -> Bundle v b) -> v b -> MBundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v b -> Bundle v b
forall (v :: * -> *) a. Vector v a => v a -> Bundle v a
VG.stream

-- | @since 1.5.1.0
{-# INLINE scanlM' #-}
scanlM' :: (HasCallStack, Monad m, VG.Vector v a, VG.Vector v b) => (a -> b -> m a) -> a -> v b -> m (v a)
scanlM' :: forall (m :: * -> *) (v :: * -> *) a b.
(HasCallStack, Monad m, Vector v a, Vector v b) =>
(a -> b -> m a) -> a -> v b -> m (v a)
scanlM' a -> b -> m a
f a
x0 =
  MBundle m v a -> m (v a)
forall (m :: * -> *) (v :: * -> *) a (u :: * -> *).
(Monad m, Vector v a) =>
MBundle m u a -> m (v a)
VG.unstreamM
    (MBundle m v a -> m (v a))
-> (v b -> MBundle m v a) -> v b -> m (v a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> m a) -> a -> Bundle v b -> MBundle m v a
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle v b -> Bundle m v a
scanlMB' a -> b -> m a
f a
x0
    (Bundle v b -> MBundle m v a)
-> (v b -> Bundle v b) -> v b -> MBundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v b -> Bundle v b
forall (v :: * -> *) a. Vector v a => v a -> Bundle v a
VG.stream

-- | @since 1.5.1.0
{-# INLINE scanl1M #-}
scanl1M :: (HasCallStack, Monad m, VG.Vector v a) => (a -> a -> m a) -> v a -> m (v a)
scanl1M :: forall (m :: * -> *) (v :: * -> *) a.
(HasCallStack, Monad m, Vector v a) =>
(a -> a -> m a) -> v a -> m (v a)
scanl1M a -> a -> m a
f =
  MBundle m v a -> m (v a)
forall (m :: * -> *) (v :: * -> *) a (u :: * -> *).
(Monad m, Vector v a) =>
MBundle m u a -> m (v a)
VG.unstreamM
    (MBundle m v a -> m (v a))
-> (v a -> MBundle m v a) -> v a -> m (v a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> m a) -> Bundle v a -> MBundle m v a
forall (m :: * -> *) a (v :: * -> *).
Monad m =>
(a -> a -> m a) -> Bundle v a -> Bundle m v a
scanl1MB a -> a -> m a
f
    (Bundle v a -> MBundle m v a)
-> (v a -> Bundle v a) -> v a -> MBundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v a -> Bundle v a
forall (v :: * -> *) a. Vector v a => v a -> Bundle v a
VG.stream

-- | @since 1.5.1.0
{-# INLINE scanl1M' #-}
scanl1M' :: (HasCallStack, Monad m, VG.Vector v a) => (a -> a -> m a) -> v a -> m (v a)
scanl1M' :: forall (m :: * -> *) (v :: * -> *) a.
(HasCallStack, Monad m, Vector v a) =>
(a -> a -> m a) -> v a -> m (v a)
scanl1M' a -> a -> m a
f =
  MBundle m v a -> m (v a)
forall (m :: * -> *) (v :: * -> *) a (u :: * -> *).
(Monad m, Vector v a) =>
MBundle m u a -> m (v a)
VG.unstreamM
    (MBundle m v a -> m (v a))
-> (v a -> MBundle m v a) -> v a -> m (v a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> m a) -> Bundle v a -> MBundle m v a
forall (m :: * -> *) a (v :: * -> *).
Monad m =>
(a -> a -> m a) -> Bundle v a -> Bundle m v a
scanl1MB' a -> a -> m a
f
    (Bundle v a -> MBundle m v a)
-> (v a -> Bundle v a) -> v a -> MBundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v a -> Bundle v a
forall (v :: * -> *) a. Vector v a => v a -> Bundle v a
VG.stream

{-# INLINE prescanlMB #-}
prescanlMB :: (Monad m) => (a -> b -> m a) -> a -> Bundle.Bundle v b -> BundleM.Bundle m v a
prescanlMB :: forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle v b -> Bundle m v a
prescanlMB a -> b -> m a
f a
x0 = (a -> b -> m a) -> a -> Bundle m v b -> Bundle m v a
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle m v b -> Bundle m v a
BundleM.prescanlM a -> b -> m a
f a
x0 (Bundle m v b -> Bundle m v a)
-> (Bundle v b -> Bundle m v b) -> Bundle v b -> Bundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bundle v b -> Bundle m v b
forall (m :: * -> *) (v :: * -> *) a.
Monad m =>
Bundle Id v a -> Bundle m v a
Bundle.lift

{-# INLINE prescanlMB' #-}
prescanlMB' :: (Monad m) => (a -> b -> m a) -> a -> Bundle.Bundle v b -> BundleM.Bundle m v a
prescanlMB' :: forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle v b -> Bundle m v a
prescanlMB' a -> b -> m a
f a
x0 = (a -> b -> m a) -> a -> Bundle m v b -> Bundle m v a
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle m v b -> Bundle m v a
BundleM.prescanlM' a -> b -> m a
f a
x0 (Bundle m v b -> Bundle m v a)
-> (Bundle v b -> Bundle m v b) -> Bundle v b -> Bundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bundle v b -> Bundle m v b
forall (m :: * -> *) (v :: * -> *) a.
Monad m =>
Bundle Id v a -> Bundle m v a
Bundle.lift

{-# INLINE postscanlMB #-}
postscanlMB :: (Monad m) => (a -> b -> m a) -> a -> Bundle.Bundle v b -> BundleM.Bundle m v a
postscanlMB :: forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle v b -> Bundle m v a
postscanlMB a -> b -> m a
f a
x0 = (a -> b -> m a) -> a -> Bundle m v b -> Bundle m v a
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle m v b -> Bundle m v a
BundleM.postscanlM a -> b -> m a
f a
x0 (Bundle m v b -> Bundle m v a)
-> (Bundle v b -> Bundle m v b) -> Bundle v b -> Bundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bundle v b -> Bundle m v b
forall (m :: * -> *) (v :: * -> *) a.
Monad m =>
Bundle Id v a -> Bundle m v a
Bundle.lift

{-# INLINE postscanlMB' #-}
postscanlMB' :: (Monad m) => (a -> b -> m a) -> a -> Bundle.Bundle v b -> BundleM.Bundle m v a
postscanlMB' :: forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle v b -> Bundle m v a
postscanlMB' a -> b -> m a
f a
x0 = (a -> b -> m a) -> a -> Bundle m v b -> Bundle m v a
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle m v b -> Bundle m v a
BundleM.postscanlM' a -> b -> m a
f a
x0 (Bundle m v b -> Bundle m v a)
-> (Bundle v b -> Bundle m v b) -> Bundle v b -> Bundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bundle v b -> Bundle m v b
forall (m :: * -> *) (v :: * -> *) a.
Monad m =>
Bundle Id v a -> Bundle m v a
Bundle.lift

{-# INLINE scanlMB #-}
scanlMB :: (Monad m) => (a -> b -> m a) -> a -> Bundle.Bundle v b -> BundleM.Bundle m v a
scanlMB :: forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle v b -> Bundle m v a
scanlMB a -> b -> m a
f a
x0 = (a -> b -> m a) -> a -> Bundle m v b -> Bundle m v a
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle m v b -> Bundle m v a
BundleM.scanlM a -> b -> m a
f a
x0 (Bundle m v b -> Bundle m v a)
-> (Bundle v b -> Bundle m v b) -> Bundle v b -> Bundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bundle v b -> Bundle m v b
forall (m :: * -> *) (v :: * -> *) a.
Monad m =>
Bundle Id v a -> Bundle m v a
Bundle.lift

{-# INLINE scanlMB' #-}
scanlMB' :: (Monad m) => (a -> b -> m a) -> a -> Bundle.Bundle v b -> BundleM.Bundle m v a
scanlMB' :: forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle v b -> Bundle m v a
scanlMB' a -> b -> m a
f a
x0 = (a -> b -> m a) -> a -> Bundle m v b -> Bundle m v a
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle m v b -> Bundle m v a
BundleM.scanlM' a -> b -> m a
f a
x0 (Bundle m v b -> Bundle m v a)
-> (Bundle v b -> Bundle m v b) -> Bundle v b -> Bundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bundle v b -> Bundle m v b
forall (m :: * -> *) (v :: * -> *) a.
Monad m =>
Bundle Id v a -> Bundle m v a
Bundle.lift

{-# INLINE scanl1MB #-}
scanl1MB :: (Monad m) => (a -> a -> m a) -> Bundle.Bundle v a -> BundleM.Bundle m v a
scanl1MB :: forall (m :: * -> *) a (v :: * -> *).
Monad m =>
(a -> a -> m a) -> Bundle v a -> Bundle m v a
scanl1MB a -> a -> m a
f = (a -> a -> m a) -> Bundle m v a -> Bundle m v a
forall (m :: * -> *) a (v :: * -> *).
Monad m =>
(a -> a -> m a) -> Bundle m v a -> Bundle m v a
BundleM.scanl1M a -> a -> m a
f (Bundle m v a -> Bundle m v a)
-> (Bundle v a -> Bundle m v a) -> Bundle v a -> Bundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bundle v a -> Bundle m v a
forall (m :: * -> *) (v :: * -> *) a.
Monad m =>
Bundle Id v a -> Bundle m v a
Bundle.lift

{-# INLINE scanl1MB' #-}
scanl1MB' :: (Monad m) => (a -> a -> m a) -> Bundle.Bundle v a -> BundleM.Bundle m v a
scanl1MB' :: forall (m :: * -> *) a (v :: * -> *).
Monad m =>
(a -> a -> m a) -> Bundle v a -> Bundle m v a
scanl1MB' a -> a -> m a
f = (a -> a -> m a) -> Bundle m v a -> Bundle m v a
forall (m :: * -> *) a (v :: * -> *).
Monad m =>
(a -> a -> m a) -> Bundle m v a -> Bundle m v a
BundleM.scanl1M' a -> a -> m a
f (Bundle m v a -> Bundle m v a)
-> (Bundle v a -> Bundle m v a) -> Bundle v a -> Bundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bundle v a -> Bundle m v a
forall (m :: * -> *) (v :: * -> *) a.
Monad m =>
Bundle Id v a -> Bundle m v a
Bundle.lift

-- | \(O(n)\) Converts a vector into chunks of vectors with lenth \(k\). The last vector may have
-- smaller length than \(k\).
--
-- >>> import AtCoder.Extra.Vector qualified as EV
-- >>> import Data.Vector.Unboxed qualified as VU
-- >>> EV.chunks 3 $ VU.fromList ([1, 2, 3, 4, 5, 6, 7] :: [Int])
-- [[1,2,3],[4,5,6],[7]]
--
-- @since 1.5.1.0
{-# INLINE chunks #-}
chunks :: (VG.Vector v a) => Int -> v a -> V.Vector (v a)
chunks :: forall (v :: * -> *) a. Vector v a => Int -> v a -> Vector (v a)
chunks Int
len v a
xs0 = Int -> (v a -> (v a, v a)) -> v a -> Vector (v a)
forall b a. Int -> (b -> (a, b)) -> b -> Vector a
V.unfoldrExactN Int
n v a -> (v a, v a)
forall {v :: * -> *} {a}. Vector v a => v a -> (v a, v a)
step v a
xs0
  where
    n :: Int
n = (v a -> Int
forall (v :: * -> *) a. Vector v a => v a -> Int
VG.length v a
xs0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
len Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
len
    step :: v a -> (v a, v a)
step v a
xs = (Int -> v a -> v a
forall (v :: * -> *) a. Vector v a => Int -> v a -> v a
VG.take Int
len v a
xs, Int -> v a -> v a
forall (v :: * -> *) a. Vector v a => Int -> v a -> v a
VG.drop Int
len v a
xs)

-- | \(O(n)\) Returns maximum range sum.
--
-- ==== Example
-- >>> import AtCoder.Extra.Vector qualified as EV
-- >>> import Data.Vector.Unboxed qualified as VU
-- >>> EV.maxRangeSum $ VU.fromList @Int [-3, 1, 6, -2, 7, -5]
-- 12
--
-- @since 1.5.1.0
{-# INLINE maxRangeSum #-}
maxRangeSum :: forall v a. (VG.Vector v a, Ord a, Num a) => v a -> a
maxRangeSum :: forall (v :: * -> *) a. (Vector v a, Ord a, Num a) => v a -> a
maxRangeSum v a
xs = (a, a) -> a
forall a b. (a, b) -> a
fst ((a, a) -> a) -> (a, a) -> a
forall a b. (a -> b) -> a -> b
$ ((a, a) -> a -> (a, a)) -> (a, a) -> v a -> (a, a)
forall (v :: * -> *) b a.
Vector v b =>
(a -> b -> a) -> a -> v b -> a
VG.foldl' (a, a) -> a -> (a, a)
forall {b}. (Ord b, Num b) => (b, b) -> b -> (b, b)
f (a
0 :: a, a
0 :: a) v a
csum
  where
    csum :: v a
csum = (a -> a -> a) -> a -> v a -> v a
forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b -> a) -> a -> v b -> v a
VG.postscanl' a -> a -> a
forall a. Num a => a -> a -> a
(+) (a
0 :: a) v a
xs
    f :: (b, b) -> b -> (b, b)
f (!b
acc, !b
minL) b
x = (b -> b -> b
forall a. Ord a => a -> a -> a
max b
acc (b
x b -> b -> b
forall a. Num a => a -> a -> a
- b
minL), b -> b -> b
forall a. Ord a => a -> a -> a
min b
minL b
x)

-- | \(O(n)\) Returns minimum range sum.
--
-- ==== Example
-- >>> import AtCoder.Extra.Vector qualified as EV
-- >>> import Data.Vector.Unboxed qualified as VU
-- >>> EV.minRangeSum $ VU.fromList @Int[-3, 1, 6, -20, 7, -9]
-- -22
--
-- @since 1.5.1.0
{-# INLINE minRangeSum #-}
minRangeSum :: forall v a. (VG.Vector v a, Ord a, Num a) => v a -> a
minRangeSum :: forall (v :: * -> *) a. (Vector v a, Ord a, Num a) => v a -> a
minRangeSum v a
xs = (a, a) -> a
forall a b. (a, b) -> a
fst ((a, a) -> a) -> (a, a) -> a
forall a b. (a -> b) -> a -> b
$ ((a, a) -> a -> (a, a)) -> (a, a) -> v a -> (a, a)
forall (v :: * -> *) b a.
Vector v b =>
(a -> b -> a) -> a -> v b -> a
VG.foldl' (a, a) -> a -> (a, a)
forall {b}. (Ord b, Num b) => (b, b) -> b -> (b, b)
f (a
0 :: a, a
0 :: a) v a
csum
  where
    csum :: v a
csum = (a -> a -> a) -> a -> v a -> v a
forall (v :: * -> *) a b.
(Vector v a, Vector v b) =>
(a -> b -> a) -> a -> v b -> v a
VG.postscanl' a -> a -> a
forall a. Num a => a -> a -> a
(+) (a
0 :: a) v a
xs
    f :: (b, b) -> b -> (b, b)
f (!b
acc, !b
maxL) b
x = (b -> b -> b
forall a. Ord a => a -> a -> a
min b
acc (b
x b -> b -> b
forall a. Num a => a -> a -> a
- b
maxL), b -> b -> b
forall a. Ord a => a -> a -> a
max b
maxL b
x)

-- | \(O(N)\) Returns indices of minimum values in the windows with the specified length.
--
-- ==== Constraints
-- - \(k \gt 0\)
--
-- ==== Example
--
-- >>> slideMinIndices 3 (VU.fromList [0 .. 5])
-- [0,1,2,3]
-- >>> slideMinIndices 3 (VU.fromList [5, 4 .. 0])
-- [2,3,4,5]
--
-- @since 1.5.1.0
{-# INLINE slideMinIndices #-}
slideMinIndices :: (HasCallStack) => Int -> VU.Vector Int -> VU.Vector Int
slideMinIndices :: HasCallStack => Int -> Vector Int -> Vector Int
slideMinIndices Int
k Vector Int
xs
  | Vector Int -> Bool
forall a. Unbox a => Vector a -> Bool
VU.null Vector Int
xs = Vector Int
forall a. Unbox a => Vector a
VU.empty
  | Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Vector Int -> Int
forall a. Unbox a => Vector a -> Int
VU.length Vector Int
xs = Int -> Vector Int
forall a. Unbox a => a -> Vector a
VU.singleton (Int -> Vector Int) -> Int -> Vector Int
forall a b. (a -> b) -> a -> b
$ Vector Int -> Int
forall a. (Unbox a, Ord a) => Vector a -> Int
VU.minIndex Vector Int
xs
  | Bool
otherwise = (Int -> Down Int) -> Int -> Vector Int -> Vector Int
forall (v :: * -> *) a b.
(Vector v a, Ord b) =>
(a -> b) -> Int -> v a -> Vector Int
slideCmpIndicesOn Int -> Down Int
forall a. a -> Down a
Down Int
k Vector Int
xs
  where
    !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0) String
"AtCoder.Extra.Vector.slideMinIndices: given non-positive k"

-- | \(O(N)\) Returns indices of maximum values in the windows with the specified length.
--
-- ==== Constraints
-- - \(k \gt 0\)
--
-- ==== Example
--
-- @
-- indices: 0 1 2 3 4 5
-- values:  0 1 2 3 4 5   max value indices:
--          [---]         2
--            [---]       3
--              [---]     4
--                [---]   5
-- @
--
-- >>> slideMaxIndices 3 (VU.fromList [0 .. 5])
-- [2,3,4,5]
-- >>> slideMaxIndices 3 (VU.fromList [5, 4 .. 0])
-- [0,1,2,3]
--
-- @since 1.5.1.0
{-# INLINE slideMaxIndices #-}
slideMaxIndices :: (HasCallStack) => Int -> VU.Vector Int -> VU.Vector Int
slideMaxIndices :: HasCallStack => Int -> Vector Int -> Vector Int
slideMaxIndices Int
k Vector Int
xs
  | Vector Int -> Bool
forall a. Unbox a => Vector a -> Bool
VU.null Vector Int
xs = Vector Int
forall a. Unbox a => Vector a
VU.empty
  | Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Vector Int -> Int
forall a. Unbox a => Vector a -> Int
VU.length Vector Int
xs = Int -> Vector Int
forall a. Unbox a => a -> Vector a
VU.singleton (Int -> Vector Int) -> Int -> Vector Int
forall a b. (a -> b) -> a -> b
$ Vector Int -> Int
forall a. (Unbox a, Ord a) => Vector a -> Int
VU.maxIndex Vector Int
xs
  | Bool
otherwise = (Int -> Int) -> Int -> Vector Int -> Vector Int
forall (v :: * -> *) a b.
(Vector v a, Ord b) =>
(a -> b) -> Int -> v a -> Vector Int
slideCmpIndicesOn Int -> Int
forall a. a -> a
id Int
k Vector Int
xs
  where
    !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0) String
"AtCoder.Extra.Vector.slideMaxIndices: given non-positive k"

-- | \(O(N)\) (1) in <https://qiita.com/kuuso1/items/318d42cd089a49eeb332>
{-# INLINE slideCmpIndicesOn #-}
slideCmpIndicesOn :: (VG.Vector v a, Ord b) => (a -> b) -> Int -> v a -> VU.Vector Int
slideCmpIndicesOn :: forall (v :: * -> *) a b.
(Vector v a, Ord b) =>
(a -> b) -> Int -> v a -> Vector Int
slideCmpIndicesOn a -> b
wrap Int
len v a
xs = (forall s. ST s (Vector Int)) -> Vector Int
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (Vector Int)) -> Vector Int)
-> (forall s. ST s (Vector Int)) -> Vector Int
forall a b. (a -> b) -> a -> b
$ do
  -- dequeue of maximum number indices.
  !Queue s Int
buf <- Int -> ST s (Queue (PrimState (ST s)) Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (Queue (PrimState m) a)
Q.new (v a -> Int
forall (v :: * -> *) a. Vector v a => v a -> Int
VG.length v a
xs)

  (Vector Int -> Vector Int)
-> ST s (Vector Int) -> ST s (Vector Int)
forall a b. (a -> b) -> ST s a -> ST s b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Int -> Vector Int -> Vector Int
forall a. Unbox a => Int -> Vector a -> Vector a
VU.drop (Int
len Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)) (ST s (Vector Int) -> ST s (Vector Int))
-> ST s (Vector Int) -> ST s (Vector Int)
forall a b. (a -> b) -> a -> b
$ Int -> (Int -> ST s Int) -> ST s (Vector Int)
forall (m :: * -> *) (v :: * -> *) a.
(Monad m, Vector v a) =>
Int -> (Int -> m a) -> m (v a)
VG.generateM (v a -> Int
forall (v :: * -> *) a. Vector v a => v a -> Int
VG.length v a
xs) ((Int -> ST s Int) -> ST s (Vector Int))
-> (Int -> ST s Int) -> ST s (Vector Int)
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    -- remove the front indices that are no longer in the span
    (ST s () -> ST s ()) -> ST s ()
forall a. (a -> a) -> a
fix ((ST s () -> ST s ()) -> ST s ())
-> (ST s () -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \ST s ()
loop -> do
      Bool
b <- Bool -> (Int -> Bool) -> Maybe Int -> Bool
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Bool
False (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
len) (Maybe Int -> Bool) -> ST s (Maybe Int) -> ST s Bool
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Queue (PrimState (ST s)) Int -> Int -> ST s (Maybe Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> Int -> m (Maybe a)
Q.readMaybeFront Queue s Int
Queue (PrimState (ST s)) Int
buf Int
0
      Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when Bool
b (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
        Queue (PrimState (ST s)) Int -> ST s ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> m ()
Q.popFront_ Queue s Int
Queue (PrimState (ST s)) Int
buf
        ST s ()
loop

    -- remove the last indices that are less attractive to the new coming value
    (ST s () -> ST s ()) -> ST s ()
forall a. (a -> a) -> a
fix ((ST s () -> ST s ()) -> ST s ())
-> (ST s () -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \ST s ()
loop -> do
      Bool
b <- Bool -> (Int -> Bool) -> Maybe Int -> Bool
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Bool
False ((b -> b -> Bool
forall a. Ord a => a -> a -> Bool
< a -> b
wrap (v a
xs v a -> Int -> a
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
i)) (b -> Bool) -> (Int -> b) -> Int -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
wrap (a -> b) -> (Int -> a) -> Int -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (v a
xs VG.!)) (Maybe Int -> Bool) -> ST s (Maybe Int) -> ST s Bool
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Queue (PrimState (ST s)) Int -> Int -> ST s (Maybe Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> Int -> m (Maybe a)
Q.readMaybeBack Queue s Int
Queue (PrimState (ST s)) Int
buf Int
0
      Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when Bool
b (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
        Queue (PrimState (ST s)) Int -> ST s ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> m ()
Q.popBack_ Queue s Int
Queue (PrimState (ST s)) Int
buf
        ST s ()
loop

    Queue (PrimState (ST s)) Int -> Int -> ST s ()
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> a -> m ()
Q.pushBack Queue s Int
Queue (PrimState (ST s)) Int
buf Int
i
    Queue (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Queue (PrimState m) a -> Int -> m a
Q.readFront Queue s Int
Queue (PrimState (ST s)) Int
buf Int
0