{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeFamilies #-}
-- |
-- Module      : Data.Vector.Generic.Mutable
-- Copyright   : (c) Roman Leshchinskiy 2008-2010
--                   Alexey Kuleshevich 2020-2022
--                   Aleksey Khudyakov 2020-2022
--                   Andrew Lelechenko 2020-2022
-- License     : BSD-style
--
-- Maintainer  : Haskell Libraries Team <libraries@haskell.org>
-- Stability   : experimental
-- Portability : non-portable
--
-- Generic interface to mutable vectors.

module Data.Vector.Generic.Mutable (
  -- * Class of mutable vector types
  MVector(..),

  -- * Accessors

  -- ** Length information
  length, null,

  -- ** Extracting subvectors
  slice, init, tail, take, drop, splitAt,
  unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,

  -- ** Overlapping
  overlaps,

  -- * Construction

  -- ** Initialisation
  new, unsafeNew, replicate, replicateM, generate, generateM, clone,

  -- ** Growing
  grow, unsafeGrow,
  growFront, unsafeGrowFront,

  -- ** Restricting memory usage
  clear,

  -- * Accessing individual elements
  read, readMaybe, write, modify, modifyM, swap, exchange,
  unsafeRead, unsafeWrite, unsafeModify, unsafeModifyM, unsafeSwap, unsafeExchange,

  -- * Folds
  mapM_, imapM_, forM_, iforM_,
  foldl, foldl', foldM, foldM',
  foldr, foldr', foldrM, foldrM',
  ifoldl, ifoldl', ifoldM, ifoldM',
  ifoldr, ifoldr', ifoldrM, ifoldrM',

  -- * Modifying vectors
  nextPermutation, nextPermutationBy,
  prevPermutation, prevPermutationBy,

  -- ** Filling and copying
  set, copy, move, unsafeCopy, unsafeMove,

  -- * Internal operations
  mstream, mstreamR,
  unstream, unstreamR, vunstream,
  munstream, munstreamR,
  transform, transformR,
  fill, fillR,
  unsafeAccum, accum, unsafeUpdate, update, reverse,
  unstablePartition, unstablePartitionBundle, partitionBundle,
  partitionWithBundle,
  -- * Re-exports
  PrimMonad, PrimState, RealWorld
) where

import           Data.Vector.Generic.Mutable.Base
import qualified Data.Vector.Generic.Base as V

import qualified Data.Vector.Fusion.Bundle      as Bundle
import           Data.Vector.Fusion.Bundle      ( Bundle, MBundle, Chunk(..) )
import qualified Data.Vector.Fusion.Bundle.Monadic as MBundle
import           Data.Vector.Fusion.Stream.Monadic ( Stream )
import qualified Data.Vector.Fusion.Stream.Monadic as Stream
import           Data.Vector.Fusion.Bundle.Size
import           Data.Vector.Fusion.Util        ( delay_inline )
import           Data.Vector.Internal.Check

import Control.Monad.Primitive ( PrimMonad(..), RealWorld, stToPrim )

import Prelude
  ( Ord, Monad, Bool(..), Int, Maybe(..), Either(..), Ordering(..)
  , return, otherwise, flip, const, seq, min, max, not, pure
  , (>>=), (+), (-), (<), (<=), (>), (>=), (==), (/=), (.), ($), (=<<), (>>), (<$>) )
import Data.Bits ( Bits(shiftR) )

#include "vector.h"


-- ------------------
-- Internal functions
-- ------------------

unsafeAppend1 :: (PrimMonad m, MVector v a)
        => v (PrimState m) a -> Int -> a -> m (v (PrimState m) a)
{-# INLINE_INNER unsafeAppend1 #-}
    -- NOTE: The case distinction has to be on the outside because
    -- GHC creates a join point for the unsafeWrite even when everything
    -- is inlined. This is bad because with the join point, v isn't getting
    -- unboxed.
unsafeAppend1 :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m (v (PrimState m) a)
unsafeAppend1 v (PrimState m) a
v Int
i a
x
  | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v = do
                     v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v Int
i a
x
                     v (PrimState m) a -> m (v (PrimState m) a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return v (PrimState m) a
v
  | Bool
otherwise    = do
                     v (PrimState m) a
v' <- v (PrimState m) a -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> m (v (PrimState m) a)
enlarge v (PrimState m) a
v
                     Checks -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Internal Int
i (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v') (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v' Int
i a
x
                     v (PrimState m) a -> m (v (PrimState m) a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return v (PrimState m) a
v'

unsafePrepend1 :: (PrimMonad m, MVector v a)
        => v (PrimState m) a -> Int -> a -> m (v (PrimState m) a, Int)
{-# INLINE_INNER unsafePrepend1 #-}
unsafePrepend1 :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m (v (PrimState m) a, Int)
unsafePrepend1 v (PrimState m) a
v Int
i a
x
  | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
0    = do
                  let i' :: Int
i' = Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1
                  v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v Int
i' a
x
                  (v (PrimState m) a, Int) -> m (v (PrimState m) a, Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) a
v, Int
i')
  | Bool
otherwise = do
                  (v (PrimState m) a
v', Int
j) <- v (PrimState m) a -> m (v (PrimState m) a, Int)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> m (v (PrimState m) a, Int)
enlargeFront v (PrimState m) a
v
                  let i' :: Int
i' = Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1
                  Checks -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Internal Int
i' (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v') (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v' Int
i' a
x
                  (v (PrimState m) a, Int) -> m (v (PrimState m) a, Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) a
v', Int
i')

mstream :: (PrimMonad m, MVector v a) => v (PrimState m) a -> Stream m a
{-# INLINE mstream #-}
mstream :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Stream m a
mstream v (PrimState m) a
v = v (PrimState m) a
v v (PrimState m) a -> Stream m a -> Stream m a
forall a b. a -> b -> b
`seq` Int
n Int -> Stream m a -> Stream m a
forall a b. a -> b -> b
`seq` (Int -> m (Maybe (a, Int))) -> Int -> Stream m a
forall (m :: * -> *) s a.
Monad m =>
(s -> m (Maybe (a, s))) -> s -> Stream m a
Stream.unfoldrM Int -> m (Maybe (a, Int))
get Int
0
  where
    n :: Int
n = v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v

    {-# INLINE_INNER get #-}
    get :: Int -> m (Maybe (a, Int))
get Int
i | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n     = do a
x <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i
                           Maybe (a, Int) -> m (Maybe (a, Int))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Maybe (a, Int) -> m (Maybe (a, Int)))
-> Maybe (a, Int) -> m (Maybe (a, Int))
forall a b. (a -> b) -> a -> b
$ (a, Int) -> Maybe (a, Int)
forall a. a -> Maybe a
Just (a
x, Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
          | Bool
otherwise = Maybe (a, Int) -> m (Maybe (a, Int))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe (a, Int)
forall a. Maybe a
Nothing

fill :: (PrimMonad m, MVector v a)
     => v (PrimState m) a -> Stream m a -> m (v (PrimState m) a)
{-# INLINE fill #-}
fill :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Stream m a -> m (v (PrimState m) a)
fill v (PrimState m) a
v Stream m a
s = v (PrimState m) a
v v (PrimState m) a -> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. a -> b -> b
`seq` do
                     Int
n' <- (Int -> a -> m Int) -> Int -> Stream m a -> m Int
forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m a) -> a -> Stream m b -> m a
Stream.foldM Int -> a -> m Int
put Int
0 Stream m a
s
                     v (PrimState m) a -> m (v (PrimState m) a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) a -> m (v (PrimState m) a))
-> v (PrimState m) a -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 Int
n' v (PrimState m) a
v
  where
    {-# INLINE_INNER put #-}
    put :: Int -> a -> m Int
put Int
i a
x = do
                Checks -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Internal Int
i (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v Int
i a
x
                Int -> m Int
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)

transform
  :: (PrimMonad m, MVector v a)
  => (Stream m a -> Stream m a) -> v (PrimState m) a -> m (v (PrimState m) a)
{-# INLINE_FUSED transform #-}
transform :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
(Stream m a -> Stream m a)
-> v (PrimState m) a -> m (v (PrimState m) a)
transform Stream m a -> Stream m a
f v (PrimState m) a
v = v (PrimState m) a -> Stream m a -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Stream m a -> m (v (PrimState m) a)
fill v (PrimState m) a
v (Stream m a -> Stream m a
f (v (PrimState m) a -> Stream m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Stream m a
mstream v (PrimState m) a
v))

mstreamR :: (PrimMonad m, MVector v a) => v (PrimState m) a -> Stream m a
{-# INLINE mstreamR #-}
mstreamR :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Stream m a
mstreamR v (PrimState m) a
v = v (PrimState m) a
v v (PrimState m) a -> Stream m a -> Stream m a
forall a b. a -> b -> b
`seq` Int
n Int -> Stream m a -> Stream m a
forall a b. a -> b -> b
`seq` (Int -> m (Maybe (a, Int))) -> Int -> Stream m a
forall (m :: * -> *) s a.
Monad m =>
(s -> m (Maybe (a, s))) -> s -> Stream m a
Stream.unfoldrM Int -> m (Maybe (a, Int))
get Int
n
  where
    n :: Int
n = v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v

    {-# INLINE_INNER get #-}
    get :: Int -> m (Maybe (a, Int))
get Int
i | Int
j Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0    = do a
x <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
j
                           Maybe (a, Int) -> m (Maybe (a, Int))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Maybe (a, Int) -> m (Maybe (a, Int)))
-> Maybe (a, Int) -> m (Maybe (a, Int))
forall a b. (a -> b) -> a -> b
$ (a, Int) -> Maybe (a, Int)
forall a. a -> Maybe a
Just (a
x,Int
j)
          | Bool
otherwise = Maybe (a, Int) -> m (Maybe (a, Int))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe (a, Int)
forall a. Maybe a
Nothing
      where
        j :: Int
j = Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1

fillR :: (PrimMonad m, MVector v a)
      => v (PrimState m) a -> Stream m a -> m (v (PrimState m) a)
{-# INLINE fillR #-}
fillR :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Stream m a -> m (v (PrimState m) a)
fillR v (PrimState m) a
v Stream m a
s = v (PrimState m) a
v v (PrimState m) a -> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. a -> b -> b
`seq` do
                      Int
i <- (Int -> a -> m Int) -> Int -> Stream m a -> m Int
forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m a) -> a -> Stream m b -> m a
Stream.foldM Int -> a -> m Int
put Int
n Stream m a
s
                      v (PrimState m) a -> m (v (PrimState m) a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) a -> m (v (PrimState m) a))
-> v (PrimState m) a -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
i (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
i) v (PrimState m) a
v
  where
    n :: Int
n = v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v

    {-# INLINE_INNER put #-}
    put :: Int -> a -> m Int
put Int
i a
x = do
                v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v Int
j a
x
                Int -> m Int
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Int
j
      where
        j :: Int
j = Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1

transformR
  :: (PrimMonad m, MVector v a)
  => (Stream m a -> Stream m a) -> v (PrimState m) a -> m (v (PrimState m) a)
{-# INLINE_FUSED transformR #-}
transformR :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
(Stream m a -> Stream m a)
-> v (PrimState m) a -> m (v (PrimState m) a)
transformR Stream m a -> Stream m a
f v (PrimState m) a
v = v (PrimState m) a -> Stream m a -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Stream m a -> m (v (PrimState m) a)
fillR v (PrimState m) a
v (Stream m a -> Stream m a
f (v (PrimState m) a -> Stream m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Stream m a
mstreamR v (PrimState m) a
v))

-- | Create a new mutable vector and fill it with elements from the 'Bundle'.
-- The vector will grow exponentially if the maximum size of the 'Bundle' is
-- unknown.
unstream :: (PrimMonad m, MVector v a)
         => Bundle u a -> m (v (PrimState m) a)
-- NOTE: replace INLINE_FUSED by INLINE? (also in unstreamR)
{-# INLINE_FUSED unstream #-}
unstream :: forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
Bundle u a -> m (v (PrimState m) a)
unstream Bundle u a
s = MBundle m u a -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
munstream (Bundle u a -> MBundle m u a
forall (m :: * -> *) (v :: * -> *) a.
Monad m =>
Bundle Id v a -> Bundle m v a
Bundle.lift Bundle u a
s)

-- | Create a new mutable vector and fill it with elements from the monadic
-- stream. The vector will grow exponentially if the maximum size of the stream
-- is unknown.
munstream :: (PrimMonad m, MVector v a)
          => MBundle m u a -> m (v (PrimState m) a)
{-# INLINE_FUSED munstream #-}
munstream :: forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
munstream MBundle m u a
s = case Size -> Maybe Int
upperBound (MBundle m u a -> Size
forall (m :: * -> *) (v :: * -> *) a. Bundle m v a -> Size
MBundle.size MBundle m u a
s) of
               Just Int
n  -> MBundle m u a -> Int -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> Int -> m (v (PrimState m) a)
munstreamMax     MBundle m u a
s Int
n
               Maybe Int
Nothing -> MBundle m u a -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
munstreamUnknown MBundle m u a
s

munstreamMax :: (PrimMonad m, MVector v a)
             => MBundle m u a -> Int -> m (v (PrimState m) a)
{-# INLINE munstreamMax #-}
munstreamMax :: forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> Int -> m (v (PrimState m) a)
munstreamMax MBundle m u a
s Int
n
  = do
      v (PrimState m) a
v <- Checks -> Int -> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Internal Int
n (m (v (PrimState m) a) -> m (v (PrimState m) a))
-> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Int -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
n
      let put :: Int -> a -> m Int
put Int
i a
x = do
                       Checks -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Internal Int
i Int
n (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v Int
i a
x
                       Int -> m Int
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
      Int
n' <- (Int -> a -> m Int) -> Int -> MBundle m u a -> m Int
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle m v b -> m a
MBundle.foldM' Int -> a -> m Int
put Int
0 MBundle m u a
s
      v (PrimState m) a -> m (v (PrimState m) a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) a -> m (v (PrimState m) a))
-> v (PrimState m) a -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Checks
-> Int -> Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n' Int
n
             (v (PrimState m) a -> v (PrimState m) a)
-> v (PrimState m) a -> v (PrimState m) a
forall a b. (a -> b) -> a -> b
$ Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 Int
n' v (PrimState m) a
v

munstreamUnknown :: (PrimMonad m, MVector v a)
                 => MBundle m u a -> m (v (PrimState m) a)
{-# INLINE munstreamUnknown #-}
munstreamUnknown :: forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
munstreamUnknown MBundle m u a
s
  = do
      v (PrimState m) a
v <- Int -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
0
      (v (PrimState m) a
v', Int
n) <- ((v (PrimState m) a, Int) -> a -> m (v (PrimState m) a, Int))
-> (v (PrimState m) a, Int)
-> MBundle m u a
-> m (v (PrimState m) a, Int)
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle m v b -> m a
MBundle.foldM (v (PrimState m) a, Int) -> a -> m (v (PrimState m) a, Int)
forall {m :: * -> *} {v :: * -> * -> *} {a}.
(PrimMonad m, MVector v a) =>
(v (PrimState m) a, Int) -> a -> m (v (PrimState m) a, Int)
put (v (PrimState m) a
v, Int
0) MBundle m u a
s
      v (PrimState m) a -> m (v (PrimState m) a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) a -> m (v (PrimState m) a))
-> v (PrimState m) a -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Checks
-> Int -> Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v')
             (v (PrimState m) a -> v (PrimState m) a)
-> v (PrimState m) a -> v (PrimState m) a
forall a b. (a -> b) -> a -> b
$ Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 Int
n v (PrimState m) a
v'
  where
    {-# INLINE_INNER put #-}
    put :: (v (PrimState m) a, Int) -> a -> m (v (PrimState m) a, Int)
put (v (PrimState m) a
v,Int
i) a
x = do
                    v (PrimState m) a
v' <- v (PrimState m) a -> Int -> a -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m (v (PrimState m) a)
unsafeAppend1 v (PrimState m) a
v Int
i a
x
                    (v (PrimState m) a, Int) -> m (v (PrimState m) a, Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) a
v',Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)


-- | Create a new mutable vector and fill it with elements from the 'Bundle'.
-- The vector will grow exponentially if the maximum size of the 'Bundle' is
-- unknown.
vunstream :: (PrimMonad m, V.Vector v a)
         => Bundle v a -> m (V.Mutable v (PrimState m) a)
-- NOTE: replace INLINE_FUSED by INLINE? (also in unstreamR)
{-# INLINE_FUSED vunstream #-}
vunstream :: forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
Bundle v a -> m (Mutable v (PrimState m) a)
vunstream Bundle v a
s = MBundle m v a -> m (Mutable v (PrimState m) a)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
MBundle m v a -> m (Mutable v (PrimState m) a)
vmunstream (Bundle v a -> MBundle m v a
forall (m :: * -> *) (v :: * -> *) a.
Monad m =>
Bundle Id v a -> Bundle m v a
Bundle.lift Bundle v a
s)

-- | Create a new mutable vector and fill it with elements from the monadic
-- stream. The vector will grow exponentially if the maximum size of the stream
-- is unknown.
vmunstream :: (PrimMonad m, V.Vector v a)
           => MBundle m v a -> m (V.Mutable v (PrimState m) a)
{-# INLINE_FUSED vmunstream #-}
vmunstream :: forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
MBundle m v a -> m (Mutable v (PrimState m) a)
vmunstream MBundle m v a
s = case Size -> Maybe Int
upperBound (MBundle m v a -> Size
forall (m :: * -> *) (v :: * -> *) a. Bundle m v a -> Size
MBundle.size MBundle m v a
s) of
               Just Int
n  -> MBundle m v a -> Int -> m (Mutable v (PrimState m) a)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
MBundle m v a -> Int -> m (Mutable v (PrimState m) a)
vmunstreamMax     MBundle m v a
s Int
n
               Maybe Int
Nothing -> MBundle m v a -> m (Mutable v (PrimState m) a)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
MBundle m v a -> m (Mutable v (PrimState m) a)
vmunstreamUnknown MBundle m v a
s

vmunstreamMax :: (PrimMonad m, V.Vector v a)
              => MBundle m v a -> Int -> m (V.Mutable v (PrimState m) a)
{-# INLINE vmunstreamMax #-}
vmunstreamMax :: forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
MBundle m v a -> Int -> m (Mutable v (PrimState m) a)
vmunstreamMax MBundle m v a
s Int
n
  = do
      Mutable v (PrimState m) a
v <- Checks
-> Int
-> m (Mutable v (PrimState m) a)
-> m (Mutable v (PrimState m) a)
forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Internal Int
n (m (Mutable v (PrimState m) a) -> m (Mutable v (PrimState m) a))
-> m (Mutable v (PrimState m) a) -> m (Mutable v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Int -> m (Mutable v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
n
      let {-# INLINE_INNER copyChunk #-}
          copyChunk :: Int -> Chunk v a -> m Int
copyChunk Int
i (Chunk Int
m forall (m :: * -> *).
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m ()
f) =
            Checks -> Int -> Int -> Int -> m Int -> m Int
forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
i Int
m (Mutable v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length Mutable v (PrimState m) a
v) (m Int -> m Int) -> m Int -> m Int
forall a b. (a -> b) -> a -> b
$ do
              Mutable v (PrimState m) a -> m ()
forall (m :: * -> *).
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m ()
f (Int
-> Int -> Mutable v (PrimState m) a -> Mutable v (PrimState m) a
forall s. Int -> Int -> Mutable v s a -> Mutable v s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
basicUnsafeSlice Int
i Int
m Mutable v (PrimState m) a
v)
              Int -> m Int
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
m)

      Int
n' <- (Int -> Chunk v a -> m Int) -> Int -> Stream m (Chunk v a) -> m Int
forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m a) -> a -> Stream m b -> m a
Stream.foldlM' Int -> Chunk v a -> m Int
copyChunk Int
0 (MBundle m v a -> Stream m (Chunk v a)
forall (m :: * -> *) (v :: * -> *) a.
Bundle m v a -> Stream m (Chunk v a)
MBundle.chunks MBundle m v a
s)
      Mutable v (PrimState m) a -> m (Mutable v (PrimState m) a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Mutable v (PrimState m) a -> m (Mutable v (PrimState m) a))
-> Mutable v (PrimState m) a -> m (Mutable v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Checks
-> Int
-> Int
-> Int
-> Mutable v (PrimState m) a
-> Mutable v (PrimState m) a
forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n' Int
n
             (Mutable v (PrimState m) a -> Mutable v (PrimState m) a)
-> Mutable v (PrimState m) a -> Mutable v (PrimState m) a
forall a b. (a -> b) -> a -> b
$ Int
-> Int -> Mutable v (PrimState m) a -> Mutable v (PrimState m) a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 Int
n' Mutable v (PrimState m) a
v

vmunstreamUnknown :: (PrimMonad m, V.Vector v a)
                 => MBundle m v a -> m (V.Mutable v (PrimState m) a)
{-# INLINE vmunstreamUnknown #-}
vmunstreamUnknown :: forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
MBundle m v a -> m (Mutable v (PrimState m) a)
vmunstreamUnknown MBundle m v a
s
  = do
      Mutable v (PrimState m) a
v <- Int -> m (Mutable v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
0
      (Mutable v (PrimState m) a
v', Int
n) <- ((Mutable v (PrimState m) a, Int)
 -> Chunk v a -> m (Mutable v (PrimState m) a, Int))
-> (Mutable v (PrimState m) a, Int)
-> Stream m (Chunk v a)
-> m (Mutable v (PrimState m) a, Int)
forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m a) -> a -> Stream m b -> m a
Stream.foldlM (Mutable v (PrimState m) a, Int)
-> Chunk v a -> m (Mutable v (PrimState m) a, Int)
forall {m :: * -> *} {v :: * -> *} {a}.
(PrimMonad m, Vector v a) =>
(Mutable v (PrimState m) a, Int)
-> Chunk v a -> m (Mutable v (PrimState m) a, Int)
copyChunk (Mutable v (PrimState m) a
v,Int
0) (MBundle m v a -> Stream m (Chunk v a)
forall (m :: * -> *) (v :: * -> *) a.
Bundle m v a -> Stream m (Chunk v a)
MBundle.chunks MBundle m v a
s)
      Mutable v (PrimState m) a -> m (Mutable v (PrimState m) a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Mutable v (PrimState m) a -> m (Mutable v (PrimState m) a))
-> Mutable v (PrimState m) a -> m (Mutable v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Checks
-> Int
-> Int
-> Int
-> Mutable v (PrimState m) a
-> Mutable v (PrimState m) a
forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n (Mutable v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length Mutable v (PrimState m) a
v')
             (Mutable v (PrimState m) a -> Mutable v (PrimState m) a)
-> Mutable v (PrimState m) a -> Mutable v (PrimState m) a
forall a b. (a -> b) -> a -> b
$ Int
-> Int -> Mutable v (PrimState m) a -> Mutable v (PrimState m) a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 Int
n Mutable v (PrimState m) a
v'
  where
    {-# INLINE_INNER copyChunk #-}
    copyChunk :: (Mutable v (PrimState m) a, Int)
-> Chunk v a -> m (Mutable v (PrimState m) a, Int)
copyChunk (Mutable v (PrimState m) a
v,Int
i) (Chunk Int
n forall (m :: * -> *).
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m ()
f)
      = do
          let j :: Int
j = Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
n
          Mutable v (PrimState m) a
v' <- if Mutable v (PrimState m) a -> Int
forall s. Mutable v s a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
basicLength Mutable v (PrimState m) a
v Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
j
                  then Mutable v (PrimState m) a -> Int -> m (Mutable v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (v (PrimState m) a)
unsafeGrow Mutable v (PrimState m) a
v ((Int -> Int -> Int) -> Int -> Int -> Int
forall a b. (a -> b) -> a -> b
delay_inline Int -> Int -> Int
forall a. Ord a => a -> a -> a
max (Mutable v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
enlarge_delta Mutable v (PrimState m) a
v) (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
- Mutable v (PrimState m) a -> Int
forall s. Mutable v s a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
basicLength Mutable v (PrimState m) a
v))
                  else Mutable v (PrimState m) a -> m (Mutable v (PrimState m) a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Mutable v (PrimState m) a
v
          Checks -> Int -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
i Int
n (Mutable v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length Mutable v (PrimState m) a
v') (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ Mutable v (PrimState m) a -> m ()
forall (m :: * -> *).
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m ()
f (Int
-> Int -> Mutable v (PrimState m) a -> Mutable v (PrimState m) a
forall s. Int -> Int -> Mutable v s a -> Mutable v s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
basicUnsafeSlice Int
i Int
n Mutable v (PrimState m) a
v')
          (Mutable v (PrimState m) a, Int)
-> m (Mutable v (PrimState m) a, Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Mutable v (PrimState m) a
v',Int
j)


-- | Create a new mutable vector and fill it with elements from the 'Bundle'
-- from right to left. The vector will grow exponentially if the maximum size
-- of the 'Bundle' is unknown.
unstreamR :: (PrimMonad m, MVector v a)
          => Bundle u a -> m (v (PrimState m) a)
-- NOTE: replace INLINE_FUSED by INLINE? (also in unstream)
{-# INLINE_FUSED unstreamR #-}
unstreamR :: forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
Bundle u a -> m (v (PrimState m) a)
unstreamR Bundle u a
s = MBundle m u a -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
munstreamR (Bundle u a -> MBundle m u a
forall (m :: * -> *) (v :: * -> *) a.
Monad m =>
Bundle Id v a -> Bundle m v a
Bundle.lift Bundle u a
s)

-- | Create a new mutable vector and fill it with elements from the monadic
-- stream from right to left. The vector will grow exponentially if the maximum
-- size of the stream is unknown.
munstreamR :: (PrimMonad m, MVector v a)
           => MBundle m u a -> m (v (PrimState m) a)
{-# INLINE_FUSED munstreamR #-}
munstreamR :: forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
munstreamR MBundle m u a
s = case Size -> Maybe Int
upperBound (MBundle m u a -> Size
forall (m :: * -> *) (v :: * -> *) a. Bundle m v a -> Size
MBundle.size MBundle m u a
s) of
               Just Int
n  -> MBundle m u a -> Int -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> Int -> m (v (PrimState m) a)
munstreamRMax     MBundle m u a
s Int
n
               Maybe Int
Nothing -> MBundle m u a -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(HasCallStack, PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
munstreamRUnknown MBundle m u a
s

munstreamRMax :: (PrimMonad m, MVector v a)
              => MBundle m u a -> Int -> m (v (PrimState m) a)
{-# INLINE munstreamRMax #-}
munstreamRMax :: forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> Int -> m (v (PrimState m) a)
munstreamRMax MBundle m u a
s Int
n
  = do
      v (PrimState m) a
v <- Checks -> Int -> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Internal Int
n (m (v (PrimState m) a) -> m (v (PrimState m) a))
-> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Int -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
n
      let put :: Int -> a -> m Int
put Int
i a
x = do
                      let i' :: Int
i' = Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1
                      Checks -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Internal Int
i' Int
n
                        (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v Int
i' a
x
                      Int -> m Int
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Int
i'
      Int
i <- (Int -> a -> m Int) -> Int -> MBundle m u a -> m Int
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle m v b -> m a
MBundle.foldM' Int -> a -> m Int
put Int
n MBundle m u a
s
      v (PrimState m) a -> m (v (PrimState m) a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) a -> m (v (PrimState m) a))
-> v (PrimState m) a -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Checks
-> Int -> Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
i (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
i) Int
n
             (v (PrimState m) a -> v (PrimState m) a)
-> v (PrimState m) a -> v (PrimState m) a
forall a b. (a -> b) -> a -> b
$ Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
i (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
i) v (PrimState m) a
v

munstreamRUnknown :: (HasCallStack, PrimMonad m, MVector v a)
                  => MBundle m u a -> m (v (PrimState m) a)
{-# INLINE munstreamRUnknown #-}
munstreamRUnknown :: forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(HasCallStack, PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
munstreamRUnknown MBundle m u a
s
  = do
      v (PrimState m) a
v <- Int -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
0
      (v (PrimState m) a
v', Int
i) <- ((v (PrimState m) a, Int) -> a -> m (v (PrimState m) a, Int))
-> (v (PrimState m) a, Int)
-> MBundle m u a
-> m (v (PrimState m) a, Int)
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle m v b -> m a
MBundle.foldM (v (PrimState m) a, Int) -> a -> m (v (PrimState m) a, Int)
forall {m :: * -> *} {v :: * -> * -> *} {a}.
(PrimMonad m, MVector v a) =>
(v (PrimState m) a, Int) -> a -> m (v (PrimState m) a, Int)
put (v (PrimState m) a
v, Int
0) MBundle m u a
s
      let n :: Int
n = v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v'
      v (PrimState m) a -> m (v (PrimState m) a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) a -> m (v (PrimState m) a))
-> v (PrimState m) a -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Checks
-> Int -> Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
i (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
i) Int
n
             (v (PrimState m) a -> v (PrimState m) a)
-> v (PrimState m) a -> v (PrimState m) a
forall a b. (a -> b) -> a -> b
$ Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
i (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
i) v (PrimState m) a
v'
  where
    {-# INLINE_INNER put #-}
    put :: (v (PrimState m) a, Int) -> a -> m (v (PrimState m) a, Int)
put (v (PrimState m) a
v,Int
i) a
x = v (PrimState m) a -> Int -> a -> m (v (PrimState m) a, Int)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m (v (PrimState m) a, Int)
unsafePrepend1 v (PrimState m) a
v Int
i a
x

-- Length
-- ------

-- | Length of the mutable vector.
length :: MVector v a => v s a -> Int
{-# INLINE length #-}
length :: forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length = v s a -> Int
forall s. v s a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
basicLength

-- | Check whether the vector is empty.
null :: MVector v a => v s a -> Bool
{-# INLINE null #-}
null :: forall (v :: * -> * -> *) a s. MVector v a => v s a -> Bool
null v s a
v = v s a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0

-- Extracting subvectors
-- ---------------------

-- | Yield a part of the mutable vector without copying it. The vector must
-- contain at least @i+n@ elements.
slice :: (HasCallStack, MVector v a)
      => Int  -- ^ @i@ starting index
      -> Int  -- ^ @n@ length
      -> v s a
      -> v s a
{-# INLINE slice #-}
slice :: forall (v :: * -> * -> *) a s.
(HasCallStack, MVector v a) =>
Int -> Int -> v s a -> v s a
slice Int
i Int
n v s a
v = Checks -> Int -> Int -> Int -> v s a -> v s a
forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Bounds Int
i Int
n (v s a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v) (v s a -> v s a) -> v s a -> v s a
forall a b. (a -> b) -> a -> b
$ Int -> Int -> v s a -> v s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
i Int
n v s a
v

-- | Take the @n@ first elements of the mutable vector without making a
-- copy. For negative @n@, the empty vector is returned. If @n@ is larger
-- than the vector's length, the vector is returned unchanged.
take :: MVector v a => Int -> v s a -> v s a
{-# INLINE take #-}
take :: forall (v :: * -> * -> *) a s. MVector v a => Int -> v s a -> v s a
take Int
n v s a
v = Int -> Int -> v s a -> v s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 (Int -> Int -> Int
forall a. Ord a => a -> a -> a
min (Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
n Int
0) (v s a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v)) v s a
v

-- | Drop the @n@ first element of the mutable vector without making a
-- copy. For negative @n@, the vector is returned unchanged. If @n@ is
-- larger than the vector's length, the empty vector is returned.
drop :: MVector v a => Int -> v s a -> v s a
{-# INLINE drop #-}
drop :: forall (v :: * -> * -> *) a s. MVector v a => Int -> v s a -> v s a
drop Int
n v s a
v = Int -> Int -> v s a -> v s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice (Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
m Int
n') (Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
0 (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
n')) v s a
v
  where
    n' :: Int
n' = Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
n Int
0
    m :: Int
m  = v s a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v

-- | /O(1)/ Split the mutable vector into the first @n@ elements
-- and the remainder, without copying.
--
-- Note that @'splitAt' n v@ is equivalent to @('take' n v, 'drop' n v)@,
-- but slightly more efficient.
splitAt :: MVector v a => Int -> v s a -> (v s a, v s a)
{-# INLINE splitAt #-}
splitAt :: forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> v s a -> (v s a, v s a)
splitAt Int
n v s a
v = ( Int -> Int -> v s a -> v s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 Int
m v s a
v
              , Int -> Int -> v s a -> v s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
m (Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
0 (Int
len Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
n')) v s a
v
              )
    where
      m :: Int
m   = Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
n' Int
len
      n' :: Int
n'  = Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
n Int
0
      len :: Int
len = v s a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v

-- | Drop the last element of the mutable vector without making a copy.
-- If the vector is empty, an exception is thrown.
init :: MVector v a => v s a -> v s a
{-# INLINE init #-}
init :: forall (v :: * -> * -> *) a s. MVector v a => v s a -> v s a
init v s a
v = Int -> Int -> v s a -> v s a
forall (v :: * -> * -> *) a s.
(HasCallStack, MVector v a) =>
Int -> Int -> v s a -> v s a
slice Int
0 (v s a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) v s a
v

-- | Drop the first element of the mutable vector without making a copy.
-- If the vector is empty, an exception is thrown.
tail :: MVector v a => v s a -> v s a
{-# INLINE tail #-}
tail :: forall (v :: * -> * -> *) a s. MVector v a => v s a -> v s a
tail v s a
v = Int -> Int -> v s a -> v s a
forall (v :: * -> * -> *) a s.
(HasCallStack, MVector v a) =>
Int -> Int -> v s a -> v s a
slice Int
1 (v s a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) v s a
v

-- | Yield a part of the mutable vector without copying it. No bounds checks
-- are performed.
unsafeSlice :: MVector v a => Int  -- ^ starting index
                           -> Int  -- ^ length of the slice
                           -> v s a
                           -> v s a
{-# INLINE unsafeSlice #-}
-- See NOTE: [Strict indexing] in D.V.Generic
unsafeSlice :: forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice !Int
i !Int
n v s a
v = Checks -> Int -> Int -> Int -> v s a -> v s a
forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Unsafe Int
i Int
n (v s a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v)
                    (v s a -> v s a) -> v s a -> v s a
forall a b. (a -> b) -> a -> b
$ Int -> Int -> v s a -> v s a
forall s. Int -> Int -> v s a -> v s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
basicUnsafeSlice Int
i Int
n v s a
v

-- | Same as 'init', but doesn't do range checks.
unsafeInit :: MVector v a => v s a -> v s a
{-# INLINE unsafeInit #-}
unsafeInit :: forall (v :: * -> * -> *) a s. MVector v a => v s a -> v s a
unsafeInit v s a
v = Int -> Int -> v s a -> v s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 (v s a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) v s a
v

-- | Same as 'tail', but doesn't do range checks.
unsafeTail :: MVector v a => v s a -> v s a
{-# INLINE unsafeTail #-}
unsafeTail :: forall (v :: * -> * -> *) a s. MVector v a => v s a -> v s a
unsafeTail v s a
v = Int -> Int -> v s a -> v s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
1 (v s a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) v s a
v

-- | Unsafe variant of 'take'. If @n@ is out of range, it will
-- simply create an invalid slice that likely violate memory safety.
unsafeTake :: MVector v a => Int -> v s a -> v s a
{-# INLINE unsafeTake #-}
unsafeTake :: forall (v :: * -> * -> *) a s. MVector v a => Int -> v s a -> v s a
unsafeTake Int
n v s a
v = Int -> Int -> v s a -> v s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 Int
n v s a
v

-- | Unsafe variant of 'drop'. If @n@ is out of range, it will
-- simply create an invalid slice that likely violate memory safety.
unsafeDrop :: MVector v a => Int -> v s a -> v s a
{-# INLINE unsafeDrop #-}
unsafeDrop :: forall (v :: * -> * -> *) a s. MVector v a => Int -> v s a -> v s a
unsafeDrop Int
n v s a
v = Int -> Int -> v s a -> v s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
n (v s a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
n) v s a
v

-- Overlapping
-- -----------

-- | Check whether two vectors overlap.
overlaps :: MVector v a => v s a -> v s a -> Bool
{-# INLINE overlaps #-}
overlaps :: forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> v s a -> Bool
overlaps = v s a -> v s a -> Bool
forall s. v s a -> v s a -> Bool
forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> v s a -> Bool
basicOverlaps

-- Initialisation
-- --------------

-- | Create a mutable vector of the given length.
new :: (HasCallStack, PrimMonad m, MVector v a) => Int -> m (v (PrimState m) a)
{-# INLINE new #-}
new :: forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
new Int
n = Checks -> Int -> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Bounds Int
n (m (v (PrimState m) a) -> m (v (PrimState m) a))
-> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim
      (ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a))
-> ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Int -> ST (PrimState m) (v (PrimState (ST (PrimState m))) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
n ST (PrimState m) (v (PrimState m) a)
-> (v (PrimState m) a -> ST (PrimState m) (v (PrimState m) a))
-> ST (PrimState m) (v (PrimState m) a)
forall a b.
ST (PrimState m) a
-> (a -> ST (PrimState m) b) -> ST (PrimState m) b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \v (PrimState m) a
v -> v (PrimState m) a -> ST (PrimState m) ()
forall s. v s a -> ST s ()
forall (v :: * -> * -> *) a s. MVector v a => v s a -> ST s ()
basicInitialize v (PrimState m) a
v ST (PrimState m) ()
-> ST (PrimState m) (v (PrimState m) a)
-> ST (PrimState m) (v (PrimState m) a)
forall a b.
ST (PrimState m) a -> ST (PrimState m) b -> ST (PrimState m) b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> v (PrimState m) a -> ST (PrimState m) (v (PrimState m) a)
forall a. a -> ST (PrimState m) a
forall (m :: * -> *) a. Monad m => a -> m a
return v (PrimState m) a
v

-- | Create a mutable vector of the given length. The vector content
-- should be assumed to be uninitialized. However, the exact semantics depend
-- on the vector implementation. For example, unboxed and storable
-- vectors will create a vector filled with whatever the underlying memory
-- buffer happens to contain, while boxed vector's elements are
-- initialized to bottoms which will throw exception when evaluated.
--
-- @since 0.4
unsafeNew :: (PrimMonad m, MVector v a) => Int -> m (v (PrimState m) a)
{-# INLINE unsafeNew #-}
unsafeNew :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
n = Checks -> Int -> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Unsafe Int
n (m (v (PrimState m) a) -> m (v (PrimState m) a))
-> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a))
-> ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Int -> ST (PrimState m) (v (PrimState m) a)
forall s. Int -> ST s (v s a)
forall (v :: * -> * -> *) a s. MVector v a => Int -> ST s (v s a)
basicUnsafeNew Int
n

-- | Create a mutable vector of the given length (0 if the length is negative)
-- and fill it with an initial value.
replicate :: (PrimMonad m, MVector v a) => Int -> a -> m (v (PrimState m) a)
{-# INLINE replicate #-}
replicate :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> a -> m (v (PrimState m) a)
replicate Int
n a
x = ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a))
-> ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Int -> a -> ST (PrimState m) (v (PrimState m) a)
forall s. Int -> a -> ST s (v s a)
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> a -> ST s (v s a)
basicUnsafeReplicate ((Int -> Int -> Int) -> Int -> Int -> Int
forall a b. (a -> b) -> a -> b
delay_inline Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
0 Int
n) a
x

-- | Create a mutable vector of the given length (0 if the length is negative)
-- and fill it with values produced by repeatedly executing the monadic action.
replicateM :: (PrimMonad m, MVector v a) => Int -> m a -> m (v (PrimState m) a)
{-# INLINE replicateM #-}
replicateM :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m a -> m (v (PrimState m) a)
replicateM Int
n m a
m = MBundle m Any a -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
munstream (Int -> m a -> MBundle m Any a
forall (m :: * -> *) a (v :: * -> *).
Monad m =>
Int -> m a -> Bundle m v a
MBundle.replicateM Int
n m a
m)

-- | /O(n)/ Create a mutable vector of the given length (0 if the length is negative)
-- and fill it with the results of applying the function to each index.
-- Iteration starts at index 0.
--
-- @since 0.12.3.0
generate :: (PrimMonad m, MVector v a) => Int -> (Int -> a) -> m (v (PrimState m) a)
{-# INLINE generate #-}
generate :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> (Int -> a) -> m (v (PrimState m) a)
generate Int
n Int -> a
f = ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a))
-> ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Int
-> (Int -> ST (PrimState m) a)
-> ST (PrimState m) (v (PrimState (ST (PrimState m))) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> (Int -> m a) -> m (v (PrimState m) a)
generateM Int
n (a -> ST (PrimState m) a
forall a. a -> ST (PrimState m) a
forall (m :: * -> *) a. Monad m => a -> m a
return (a -> ST (PrimState m) a)
-> (Int -> a) -> Int -> ST (PrimState m) a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> a
f)

-- | /O(n)/ Create a mutable vector of the given length (0 if the length is
-- negative) and fill it with the results of applying the monadic function to each
-- index. Iteration starts at index 0.
--
-- @since 0.12.3.0
generateM :: (PrimMonad m, MVector v a) => Int -> (Int -> m a) -> m (v (PrimState m) a)
{-# INLINE generateM #-}
generateM :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> (Int -> m a) -> m (v (PrimState m) a)
generateM Int
n Int -> m a
f = MBundle m Any a -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
munstream (Int -> (Int -> m a) -> MBundle m Any a
forall (m :: * -> *) a (v :: * -> *).
Monad m =>
Int -> (Int -> m a) -> Bundle m v a
MBundle.generateM Int
n Int -> m a
f)

-- | Create a copy of a mutable vector.
clone :: (PrimMonad m, MVector v a) => v (PrimState m) a -> m (v (PrimState m) a)
{-# INLINE clone #-}
clone :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> m (v (PrimState m) a)
clone v (PrimState m) a
v = do
            v (PrimState m) a
v' <- Int -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
            v (PrimState m) a -> v (PrimState m) a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> v (PrimState m) a -> m ()
unsafeCopy v (PrimState m) a
v' v (PrimState m) a
v
            v (PrimState m) a -> m (v (PrimState m) a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return v (PrimState m) a
v'

-- Growing
-- -------

-- | Grow a vector by the given number of elements. The number must not be
-- negative, otherwise an exception is thrown. The semantics of this function
-- are exactly the same as of 'unsafeGrow', except that it will initialize the newly
-- allocated memory first.
--
-- It is important to note that mutating the returned vector will not affect the
-- vector that was used as a source. In other words, it does not, nor will it
-- ever have the semantics of @realloc@ from C.
--
-- > grow mv 0 === clone mv
--
-- @since 0.4.0
grow :: (HasCallStack, PrimMonad m, MVector v a)
     => v (PrimState m) a -> Int -> m (v (PrimState m) a)
{-# INLINE grow #-}
grow :: forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (v (PrimState m) a)
grow v (PrimState m) a
v Int
by = Checks -> Int -> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Bounds Int
by
          (m (v (PrimState m) a) -> m (v (PrimState m) a))
-> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim
          (ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a))
-> ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ do v (PrimState m) a
vnew <- v (PrimState (ST (PrimState m))) a
-> Int -> ST (PrimState m) (v (PrimState (ST (PrimState m))) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (v (PrimState m) a)
unsafeGrow v (PrimState m) a
v (PrimState (ST (PrimState m))) a
v Int
by
               v (PrimState m) a -> ST (PrimState m) ()
forall s. v s a -> ST s ()
forall (v :: * -> * -> *) a s. MVector v a => v s a -> ST s ()
basicInitialize (v (PrimState m) a -> ST (PrimState m) ())
-> v (PrimState m) a -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall s. Int -> Int -> v s a -> v s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
basicUnsafeSlice (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v) Int
by v (PrimState m) a
vnew
               v (PrimState m) a -> ST (PrimState m) (v (PrimState m) a)
forall a. a -> ST (PrimState m) a
forall (m :: * -> *) a. Monad m => a -> m a
return v (PrimState m) a
vnew

-- | Same as 'grow', except that it copies data towards the end of the newly
-- allocated vector, making extra space available at the beginning.
--
-- @since 0.11.0.0
growFront :: (HasCallStack, PrimMonad m, MVector v a)
          => v (PrimState m) a -> Int -> m (v (PrimState m) a)
{-# INLINE growFront #-}
growFront :: forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (v (PrimState m) a)
growFront v (PrimState m) a
v Int
by = Checks -> Int -> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Bounds Int
by
               (m (v (PrimState m) a) -> m (v (PrimState m) a))
-> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim
               (ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a))
-> ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ do v (PrimState m) a
vnew <- v (PrimState (ST (PrimState m))) a
-> Int -> ST (PrimState m) (v (PrimState (ST (PrimState m))) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (v (PrimState m) a)
unsafeGrowFront v (PrimState m) a
v (PrimState (ST (PrimState m))) a
v Int
by
                    v (PrimState m) a -> ST (PrimState m) ()
forall s. v s a -> ST s ()
forall (v :: * -> * -> *) a s. MVector v a => v s a -> ST s ()
basicInitialize (v (PrimState m) a -> ST (PrimState m) ())
-> v (PrimState m) a -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall s. Int -> Int -> v s a -> v s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
basicUnsafeSlice Int
0 Int
by v (PrimState m) a
vnew
                    v (PrimState m) a -> ST (PrimState m) (v (PrimState m) a)
forall a. a -> ST (PrimState m) a
forall (m :: * -> *) a. Monad m => a -> m a
return v (PrimState m) a
vnew

enlarge_delta :: MVector v a => v s a -> Int
enlarge_delta :: forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
enlarge_delta v s a
v = Int -> Int -> Int
forall a. Ord a => a -> a -> a
max (v s a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v) Int
1

-- | Grow a vector logarithmically.
enlarge :: (PrimMonad m, MVector v a)
        => v (PrimState m) a -> m (v (PrimState m) a)
{-# INLINE enlarge #-}
enlarge :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> m (v (PrimState m) a)
enlarge v (PrimState m) a
v = ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a))
-> ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ do
  v (PrimState m) a
vnew <- v (PrimState (ST (PrimState m))) a
-> Int -> ST (PrimState m) (v (PrimState (ST (PrimState m))) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (v (PrimState m) a)
unsafeGrow v (PrimState m) a
v (PrimState (ST (PrimState m))) a
v Int
by
  v (PrimState m) a -> ST (PrimState m) ()
forall s. v s a -> ST s ()
forall (v :: * -> * -> *) a s. MVector v a => v s a -> ST s ()
basicInitialize (v (PrimState m) a -> ST (PrimState m) ())
-> v (PrimState m) a -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall s. Int -> Int -> v s a -> v s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
basicUnsafeSlice (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v) Int
by v (PrimState m) a
vnew
  v (PrimState m) a -> ST (PrimState m) (v (PrimState m) a)
forall a. a -> ST (PrimState m) a
forall (m :: * -> *) a. Monad m => a -> m a
return v (PrimState m) a
vnew
  where
    by :: Int
by = v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
enlarge_delta v (PrimState m) a
v

enlargeFront :: (PrimMonad m, MVector v a)
             => v (PrimState m) a -> m (v (PrimState m) a, Int)
{-# INLINE enlargeFront #-}
enlargeFront :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> m (v (PrimState m) a, Int)
enlargeFront v (PrimState m) a
v = ST (PrimState m) (v (PrimState m) a, Int)
-> m (v (PrimState m) a, Int)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (v (PrimState m) a, Int)
 -> m (v (PrimState m) a, Int))
-> ST (PrimState m) (v (PrimState m) a, Int)
-> m (v (PrimState m) a, Int)
forall a b. (a -> b) -> a -> b
$ do
                   v (PrimState m) a
v' <- v (PrimState (ST (PrimState m))) a
-> Int -> ST (PrimState m) (v (PrimState (ST (PrimState m))) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (v (PrimState m) a)
unsafeGrowFront v (PrimState m) a
v (PrimState (ST (PrimState m))) a
v Int
by
                   v (PrimState m) a -> ST (PrimState m) ()
forall s. v s a -> ST s ()
forall (v :: * -> * -> *) a s. MVector v a => v s a -> ST s ()
basicInitialize (v (PrimState m) a -> ST (PrimState m) ())
-> v (PrimState m) a -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall s. Int -> Int -> v s a -> v s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
basicUnsafeSlice Int
0 Int
by v (PrimState m) a
v'
                   (v (PrimState m) a, Int)
-> ST (PrimState m) (v (PrimState m) a, Int)
forall a. a -> ST (PrimState m) a
forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) a
v', Int
by)
  where
    by :: Int
by = v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
enlarge_delta v (PrimState m) a
v

-- | Grow a vector by allocating a new mutable vector of the same size plus the
-- the given number of elements and copying all the data over to the new vector,
-- starting at its beginning. The newly allocated memory is not initialized and
-- the extra space at the end will likely contain garbage data or bottoms.
-- Use 'unsafeGrowFront' to make the extra space available in the front
-- of the new vector.
--
-- It is important to note that mutating the returned vector will not affect
-- elements of the vector that was used as a source. In other words, it does not,
-- nor will it ever have the semantics of @realloc@ from C. Keep in mind,
-- however, that values themselves can be of a mutable type
-- (eg. 'Foreign.Ptr.Ptr'), in which case it would be possible to affect values
-- stored in both vectors.
--
-- > unsafeGrow mv 0 === clone mv
--
-- @since 0.4.0
unsafeGrow
  :: (PrimMonad m, MVector v a)
  => v (PrimState m) a
  -- ^ mutable vector to copy from
  -> Int
  -- ^ number of elements to grow the vector by (must be non-negative, but
  -- this is not checked)
  -> m (v (PrimState m) a)
{-# INLINE unsafeGrow #-}
unsafeGrow :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (v (PrimState m) a)
unsafeGrow v (PrimState m) a
v Int
n = Checks -> Int -> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Unsafe Int
n
               (m (v (PrimState m) a) -> m (v (PrimState m) a))
-> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim
               (ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a))
-> ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> Int -> ST (PrimState m) (v (PrimState m) a)
forall s. v s a -> Int -> ST s (v s a)
forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> Int -> ST s (v s a)
basicUnsafeGrow v (PrimState m) a
v Int
n

-- | Same as 'unsafeGrow', except that it copies data towards the end of the
-- newly allocated vector, making extra space available at the beginning.
--
-- @since 0.11.0.0
unsafeGrowFront :: (PrimMonad m, MVector v a)
                => v (PrimState m) a -> Int -> m (v (PrimState m) a)
{-# INLINE unsafeGrowFront #-}
unsafeGrowFront :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (v (PrimState m) a)
unsafeGrowFront v (PrimState m) a
v Int
by = Checks -> Int -> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Unsafe Int
by (m (v (PrimState m) a) -> m (v (PrimState m) a))
-> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a))
-> ST (PrimState m) (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ do
                         let n :: Int
n = v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v
                         v (PrimState m) a
v' <- Int -> ST (PrimState m) (v (PrimState m) a)
forall s. Int -> ST s (v s a)
forall (v :: * -> * -> *) a s. MVector v a => Int -> ST s (v s a)
basicUnsafeNew (Int
byInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
n)
                         v (PrimState m) a -> v (PrimState m) a -> ST (PrimState m) ()
forall s. v s a -> v s a -> ST s ()
forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> v s a -> ST s ()
basicUnsafeCopy (Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall s. Int -> Int -> v s a -> v s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
basicUnsafeSlice Int
by Int
n v (PrimState m) a
v') v (PrimState m) a
v
                         v (PrimState m) a -> ST (PrimState m) (v (PrimState m) a)
forall a. a -> ST (PrimState m) a
forall (m :: * -> *) a. Monad m => a -> m a
return v (PrimState m) a
v'

-- Restricting memory usage
-- ------------------------

-- | Reset all elements of the vector to some undefined value, clearing all
-- references to external objects. This is usually a noop for unboxed vectors.
clear :: (PrimMonad m, MVector v a) => v (PrimState m) a -> m ()
{-# INLINE clear #-}
clear :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> m ()
clear = ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ())
-> (v (PrimState m) a -> ST (PrimState m) ())
-> v (PrimState m) a
-> m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v (PrimState m) a -> ST (PrimState m) ()
forall s. v s a -> ST s ()
forall (v :: * -> * -> *) a s. MVector v a => v s a -> ST s ()
basicClear

-- Accessing individual elements
-- -----------------------------

-- | Yield the element at the given position. Will throw an exception if
-- the index is out of range.
--
-- ==== __Examples__
--
-- >>> import qualified Data.Vector.Strict.Mutable as MV
-- >>> v <- MV.generate 10 (\x -> x*x)
-- >>> MV.read v 3
-- 9
read :: (HasCallStack, PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> m a
{-# INLINE read #-}
read :: forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
read v (PrimState m) a
v Int
i = Checks -> Int -> Int -> m a -> m a
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
i (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
         (m a -> m a) -> m a -> m a
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i

-- | Yield the element at the given position. Returns 'Nothing' if
-- the index is out of range.
--
-- @since 0.13
--
-- ==== __Examples__
--
-- >>> import qualified Data.Vector.Strict.Mutable as MV
-- >>> v <- MV.generate 10 (\x -> x*x)
-- >>> MV.readMaybe v 3
-- Just 9
-- >>> MV.readMaybe v 13
-- Nothing
readMaybe :: (PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> m (Maybe a)
{-# INLINE readMaybe #-}
readMaybe :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (Maybe a)
readMaybe v (PrimState m) a
v Int
i | Int
i Int -> Int -> Bool
`inRange` (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v) = a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> m a -> m (Maybe a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i
              | Bool
otherwise              = Maybe a -> m (Maybe a)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe a
forall a. Maybe a
Nothing

-- | Replace the element at the given position.
write :: (HasCallStack, PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> a -> m ()
{-# INLINE write #-}
write :: forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
write v (PrimState m) a
v Int
i a
x = Checks -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
i (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
            (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v Int
i a
x

-- | Modify the element at the given position.
modify :: (HasCallStack, PrimMonad m, MVector v a) => v (PrimState m) a -> (a -> a) -> Int -> m ()
{-# INLINE modify #-}
modify :: forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
modify v (PrimState m) a
v a -> a
f Int
i = Checks -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
i (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
             (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> (a -> a) -> Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
unsafeModify v (PrimState m) a
v a -> a
f Int
i

-- | Modify the element at the given position using a monadic function.
--
-- @since 0.12.3.0
modifyM :: (HasCallStack, PrimMonad m, MVector v a) => v (PrimState m) a -> (a -> m a) -> Int -> m ()
{-# INLINE modifyM #-}
modifyM :: forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
modifyM v (PrimState m) a
v a -> m a
f Int
i = Checks -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
i (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
              (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> (a -> m a) -> Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
unsafeModifyM v (PrimState m) a
v a -> m a
f Int
i

-- | Swap the elements at the given positions.
swap :: (HasCallStack, PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> Int -> m ()
{-# INLINE swap #-}
swap :: forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> Int -> m ()
swap v (PrimState m) a
v Int
i Int
j = Checks -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
i (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
           (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ Checks -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
j (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
           (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> Int -> Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> Int -> m ()
unsafeSwap v (PrimState m) a
v Int
i Int
j

-- | Replace the element at the given position and return the old element.
exchange :: (HasCallStack, PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> a -> m a
{-# INLINE exchange #-}
exchange :: forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
exchange v (PrimState m) a
v Int
i a
x = Checks -> Int -> Int -> m a -> m a
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
i (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v) (m a -> m a) -> m a -> m a
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> Int -> a -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
unsafeExchange v (PrimState m) a
v Int
i a
x

-- | Yield the element at the given position. No bounds checks are performed.
unsafeRead :: (PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> m a
{-# INLINE unsafeRead #-}
-- See NOTE: [Strict indexing] in D.V.Generic
unsafeRead :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v !Int
i = Checks -> Int -> Int -> m a -> m a
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
i (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
                (m a -> m a) -> m a -> m a
forall a b. (a -> b) -> a -> b
$ ST (PrimState m) a -> m a
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim
                (ST (PrimState m) a -> m a) -> ST (PrimState m) a -> m a
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> Int -> ST (PrimState m) a
forall s. v s a -> Int -> ST s a
forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> Int -> ST s a
basicUnsafeRead v (PrimState m) a
v Int
i

-- | Replace the element at the given position. No bounds checks are performed.
unsafeWrite :: (PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> a -> m ()
{-# INLINE unsafeWrite #-}
-- See NOTE: [Strict indexing] in D.V.Generic
unsafeWrite :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v !Int
i a
x = Checks -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
i (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
                   (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ 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
$ v (PrimState m) a -> Int -> a -> ST (PrimState m) ()
forall s. v s a -> Int -> a -> ST s ()
forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> Int -> a -> ST s ()
basicUnsafeWrite v (PrimState m) a
v Int
i a
x

-- | Modify the element at the given position. No bounds checks are performed.
unsafeModify :: (PrimMonad m, MVector v a) => v (PrimState m) a -> (a -> a) -> Int -> m ()
{-# INLINE unsafeModify #-}
-- See NOTE: [Strict indexing] in D.V.Generic
unsafeModify :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
unsafeModify v (PrimState m) a
v a -> a
f !Int
i = Checks -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
i (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
                    (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ 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
$ v (PrimState m) a -> Int -> ST (PrimState m) a
forall s. v s a -> Int -> ST s a
forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> Int -> ST s a
basicUnsafeRead v (PrimState m) a
v Int
i ST (PrimState m) a
-> (a -> ST (PrimState m) ()) -> ST (PrimState m) ()
forall a b.
ST (PrimState m) a
-> (a -> ST (PrimState m) b) -> ST (PrimState m) b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \a
x ->
                      v (PrimState m) a -> Int -> a -> ST (PrimState m) ()
forall s. v s a -> Int -> a -> ST s ()
forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> Int -> a -> ST s ()
basicUnsafeWrite v (PrimState m) a
v Int
i (a -> a
f a
x)

-- | Modify the element at the given position using a monadic
-- function. No bounds checks are performed.
--
-- @since 0.12.3.0
unsafeModifyM :: (PrimMonad m, MVector v a) => v (PrimState m) a -> (a -> m a) -> Int -> m ()
{-# INLINE unsafeModifyM #-}
-- See NOTE: [Strict indexing] in D.V.Generic
unsafeModifyM :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
unsafeModifyM v (PrimState m) a
v a -> m a
f !Int
i = Checks -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
i (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
                     (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ())
-> (a -> ST (PrimState m) ()) -> a -> m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v (PrimState m) a -> Int -> a -> ST (PrimState m) ()
forall s. v s a -> Int -> a -> ST s ()
forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> Int -> a -> ST s ()
basicUnsafeWrite v (PrimState m) a
v Int
i (a -> m ()) -> m a -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< a -> m a
f (a -> m a) -> m a -> m a
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< ST (PrimState m) a -> m a
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (v (PrimState m) a -> Int -> ST (PrimState m) a
forall s. v s a -> Int -> ST s a
forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> Int -> ST s a
basicUnsafeRead v (PrimState m) a
v Int
i)

-- | Swap the elements at the given positions. No bounds checks are performed.
unsafeSwap :: (PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> Int -> m ()
{-# INLINE unsafeSwap #-}
unsafeSwap :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> Int -> m ()
unsafeSwap v (PrimState m) a
v Int
i Int
j = Checks -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
i (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
                 (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ Checks -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
j (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
                 (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ 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
                     a
x <- v (PrimState (ST (PrimState m))) a -> Int -> ST (PrimState m) a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v (PrimState (ST (PrimState m))) a
v Int
i
                     a
y <- v (PrimState (ST (PrimState m))) a -> Int -> ST (PrimState m) a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v (PrimState (ST (PrimState m))) a
v Int
j
                     v (PrimState (ST (PrimState m))) a
-> Int -> a -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v (PrimState (ST (PrimState m))) a
v Int
i a
y
                     v (PrimState (ST (PrimState m))) a
-> Int -> a -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v (PrimState (ST (PrimState m))) a
v Int
j a
x

-- | Replace the element at the given position and return the old element. No
-- bounds checks are performed.
unsafeExchange :: (PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> a -> m a
{-# INLINE unsafeExchange #-}
unsafeExchange :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
unsafeExchange v (PrimState m) a
v Int
i a
x = Checks -> Int -> Int -> m a -> m a
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
i (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v) (m a -> m a) -> m a -> m a
forall a b. (a -> b) -> a -> b
$ ST (PrimState m) a -> m a
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) a -> m a) -> ST (PrimState m) a -> m a
forall a b. (a -> b) -> a -> b
$ do
                         a
y <- v (PrimState (ST (PrimState m))) a -> Int -> ST (PrimState m) a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v (PrimState (ST (PrimState m))) a
v Int
i
                         v (PrimState (ST (PrimState m))) a
-> Int -> a -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v (PrimState (ST (PrimState m))) a
v Int
i a
x
                         a -> ST (PrimState m) a
forall a. a -> ST (PrimState m) a
forall (m :: * -> *) a. Monad m => a -> m a
return a
y

-- Folds
-- -----

forI_ :: (Monad m, MVector v a) => v (PrimState m) a -> (Int -> m b) -> m ()
{-# INLINE forI_ #-}
forI_ :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(Monad m, MVector v a) =>
v (PrimState m) a -> (Int -> m b) -> m ()
forI_ v (PrimState m) a
v Int -> m b
f = Int -> m ()
loop Int
0
  where
    loop :: Int -> m ()
loop Int
i | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n    = () -> m ()
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ()
           | Bool
otherwise = Int -> m b
f Int
i m b -> m () -> m ()
forall a b. m a -> m b -> m b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Int -> m ()
loop (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
    n :: Int
n = v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v

-- | /O(n)/ Apply the monadic action to every element of the vector, discarding the results.
--
-- @since 0.12.3.0
mapM_ :: (PrimMonad m, MVector v a) => (a -> m b) -> v (PrimState m) a -> m ()
{-# INLINE mapM_ #-}
mapM_ :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(a -> m b) -> v (PrimState m) a -> m ()
mapM_ a -> m b
f v (PrimState m) a
v = v (PrimState m) a -> (Int -> m b) -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a b.
(Monad m, MVector v a) =>
v (PrimState m) a -> (Int -> m b) -> m ()
forI_ v (PrimState m) a
v ((Int -> m b) -> m ()) -> (Int -> m b) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> a -> m b
f (a -> m b) -> m a -> m b
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i

-- | /O(n)/ Apply the monadic action to every element of the vector and its index, discarding the results.
--
-- @since 0.12.3.0
imapM_ :: (PrimMonad m, MVector v a) => (Int -> a -> m b) -> v (PrimState m) a -> m ()
{-# INLINE imapM_ #-}
imapM_ :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(Int -> a -> m b) -> v (PrimState m) a -> m ()
imapM_ Int -> a -> m b
f v (PrimState m) a
v = v (PrimState m) a -> (Int -> m b) -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a b.
(Monad m, MVector v a) =>
v (PrimState m) a -> (Int -> m b) -> m ()
forI_ v (PrimState m) a
v ((Int -> m b) -> m ()) -> (Int -> m b) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> Int -> a -> m b
f Int
i (a -> m b) -> m a -> m b
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i

-- | /O(n)/ Apply the monadic action to every element of the vector,
-- discarding the results. It's the same as @flip mapM_@.
--
-- @since 0.12.3.0
forM_ :: (PrimMonad m, MVector v a) => v (PrimState m) a -> (a -> m b) -> m ()
{-# INLINE forM_ #-}
forM_ :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m b) -> m ()
forM_ = ((a -> m b) -> v (PrimState m) a -> m ())
-> v (PrimState m) a -> (a -> m b) -> m ()
forall a b c. (a -> b -> c) -> b -> a -> c
flip (a -> m b) -> v (PrimState m) a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(a -> m b) -> v (PrimState m) a -> m ()
mapM_

-- | /O(n)/ Apply the monadic action to every element of the vector
-- and its index, discarding the results. It's the same as @flip imapM_@.
--
-- @since 0.12.3.0
iforM_ :: (PrimMonad m, MVector v a) => v (PrimState m) a -> (Int -> a -> m b) -> m ()
{-# INLINE iforM_ #-}
iforM_ :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (Int -> a -> m b) -> m ()
iforM_ = ((Int -> a -> m b) -> v (PrimState m) a -> m ())
-> v (PrimState m) a -> (Int -> a -> m b) -> m ()
forall a b c. (a -> b -> c) -> b -> a -> c
flip (Int -> a -> m b) -> v (PrimState m) a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(Int -> a -> m b) -> v (PrimState m) a -> m ()
imapM_

-- | /O(n)/ Pure left fold.
--
-- @since 0.12.3.0
foldl :: (PrimMonad m, MVector v a) => (b -> a -> b) -> b -> v (PrimState m) a -> m b
{-# INLINE foldl #-}
foldl :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> a -> b) -> b -> v (PrimState m) a -> m b
foldl b -> a -> b
f = (b -> Int -> a -> b) -> b -> v (PrimState m) a -> m b
forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> Int -> a -> b) -> b -> v (PrimState m) a -> m b
ifoldl (\b
b Int
_ -> b -> a -> b
f b
b)

-- | /O(n)/ Pure left fold with strict accumulator.
--
-- @since 0.12.3.0
foldl' :: (PrimMonad m, MVector v a) => (b -> a -> b) -> b -> v (PrimState m) a -> m b
{-# INLINE foldl' #-}
foldl' :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> a -> b) -> b -> v (PrimState m) a -> m b
foldl' b -> a -> b
f = (b -> Int -> a -> b) -> b -> v (PrimState m) a -> m b
forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> Int -> a -> b) -> b -> v (PrimState m) a -> m b
ifoldl' (\b
b Int
_ -> b -> a -> b
f b
b)

-- | /O(n)/ Pure left fold using a function applied to each element and its index.
--
-- @since 0.12.3.0
ifoldl :: (PrimMonad m, MVector v a) => (b -> Int -> a -> b) -> b -> v (PrimState m) a -> m b
{-# INLINE ifoldl #-}
ifoldl :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> Int -> a -> b) -> b -> v (PrimState m) a -> m b
ifoldl b -> Int -> a -> b
f b
b0 v (PrimState m) a
v = ST (PrimState m) b -> m b
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) b -> m b) -> ST (PrimState m) b -> m b
forall a b. (a -> b) -> a -> b
$ (b -> Int -> a -> ST (PrimState m) b)
-> b -> v (PrimState (ST (PrimState m))) a -> ST (PrimState m) b
forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> Int -> a -> m b) -> b -> v (PrimState m) a -> m b
ifoldM (\b
b Int
i a
a -> b -> ST (PrimState m) b
forall a. a -> ST (PrimState m) a
forall (m :: * -> *) a. Monad m => a -> m a
return (b -> ST (PrimState m) b) -> b -> ST (PrimState m) b
forall a b. (a -> b) -> a -> b
$ b -> Int -> a -> b
f b
b Int
i a
a) b
b0 v (PrimState m) a
v (PrimState (ST (PrimState m))) a
v

-- | /O(n)/ Pure left fold with strict accumulator using a function applied to each element and its index.
--
-- @since 0.12.3.0
ifoldl' :: (PrimMonad m, MVector v a) => (b -> Int -> a -> b) -> b -> v (PrimState m) a -> m b
{-# INLINE ifoldl' #-}
ifoldl' :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> Int -> a -> b) -> b -> v (PrimState m) a -> m b
ifoldl' b -> Int -> a -> b
f b
b0 v (PrimState m) a
v = ST (PrimState m) b -> m b
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) b -> m b) -> ST (PrimState m) b -> m b
forall a b. (a -> b) -> a -> b
$ (b -> Int -> a -> ST (PrimState m) b)
-> b -> v (PrimState (ST (PrimState m))) a -> ST (PrimState m) b
forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> Int -> a -> m b) -> b -> v (PrimState m) a -> m b
ifoldM' (\b
b Int
i a
a -> b -> ST (PrimState m) b
forall a. a -> ST (PrimState m) a
forall (m :: * -> *) a. Monad m => a -> m a
return (b -> ST (PrimState m) b) -> b -> ST (PrimState m) b
forall a b. (a -> b) -> a -> b
$ b -> Int -> a -> b
f b
b Int
i a
a) b
b0 v (PrimState m) a
v (PrimState (ST (PrimState m))) a
v

-- | /O(n)/ Pure right fold.
--
-- @since 0.12.3.0
foldr :: (PrimMonad m, MVector v a) => (a -> b -> b) -> b -> v (PrimState m) a -> m b
{-# INLINE foldr #-}
foldr :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(a -> b -> b) -> b -> v (PrimState m) a -> m b
foldr a -> b -> b
f = (Int -> a -> b -> b) -> b -> v (PrimState m) a -> m b
forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(Int -> a -> b -> b) -> b -> v (PrimState m) a -> m b
ifoldr ((a -> b -> b) -> Int -> a -> b -> b
forall a b. a -> b -> a
const a -> b -> b
f)

-- | /O(n)/ Pure right fold with strict accumulator.
--
-- @since 0.12.3.0
foldr' :: (PrimMonad m, MVector v a) => (a -> b -> b) -> b -> v (PrimState m) a -> m b
{-# INLINE foldr' #-}
foldr' :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(a -> b -> b) -> b -> v (PrimState m) a -> m b
foldr' a -> b -> b
f = (Int -> a -> b -> b) -> b -> v (PrimState m) a -> m b
forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(Int -> a -> b -> b) -> b -> v (PrimState m) a -> m b
ifoldr' ((a -> b -> b) -> Int -> a -> b -> b
forall a b. a -> b -> a
const a -> b -> b
f)

-- | /O(n)/ Pure right fold using a function applied to each element and its index.
--
-- @since 0.12.3.0
ifoldr :: (PrimMonad m, MVector v a) => (Int -> a -> b -> b) -> b -> v (PrimState m) a -> m b
{-# INLINE ifoldr #-}
ifoldr :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(Int -> a -> b -> b) -> b -> v (PrimState m) a -> m b
ifoldr Int -> a -> b -> b
f b
b0 v (PrimState m) a
v = ST (PrimState m) b -> m b
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) b -> m b) -> ST (PrimState m) b -> m b
forall a b. (a -> b) -> a -> b
$ (Int -> a -> b -> ST (PrimState m) b)
-> b -> v (PrimState (ST (PrimState m))) a -> ST (PrimState m) b
forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(Int -> a -> b -> m b) -> b -> v (PrimState m) a -> m b
ifoldrM (\Int
i a
a b
b -> b -> ST (PrimState m) b
forall a. a -> ST (PrimState m) a
forall (m :: * -> *) a. Monad m => a -> m a
return (b -> ST (PrimState m) b) -> b -> ST (PrimState m) b
forall a b. (a -> b) -> a -> b
$ Int -> a -> b -> b
f Int
i a
a b
b) b
b0 v (PrimState m) a
v (PrimState (ST (PrimState m))) a
v

-- | /O(n)/ Pure right fold with strict accumulator using a function applied
-- to each element and its index.
--
-- @since 0.12.3.0
ifoldr' :: (PrimMonad m, MVector v a) => (Int -> a -> b -> b) -> b -> v (PrimState m) a -> m b
{-# INLINE ifoldr' #-}
ifoldr' :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(Int -> a -> b -> b) -> b -> v (PrimState m) a -> m b
ifoldr' Int -> a -> b -> b
f b
b0 v (PrimState m) a
v = ST (PrimState m) b -> m b
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) b -> m b) -> ST (PrimState m) b -> m b
forall a b. (a -> b) -> a -> b
$ (Int -> a -> b -> ST (PrimState m) b)
-> b -> v (PrimState (ST (PrimState m))) a -> ST (PrimState m) b
forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(Int -> a -> b -> m b) -> b -> v (PrimState m) a -> m b
ifoldrM' (\Int
i a
a b
b -> b -> ST (PrimState m) b
forall a. a -> ST (PrimState m) a
forall (m :: * -> *) a. Monad m => a -> m a
return (b -> ST (PrimState m) b) -> b -> ST (PrimState m) b
forall a b. (a -> b) -> a -> b
$ Int -> a -> b -> b
f Int
i a
a b
b) b
b0 v (PrimState m) a
v (PrimState (ST (PrimState m))) a
v

-- | /O(n)/ Monadic fold.
--
-- @since 0.12.3.0
foldM :: (PrimMonad m, MVector v a) => (b -> a -> m b) -> b -> v (PrimState m) a -> m b
{-# INLINE foldM #-}
foldM :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> a -> m b) -> b -> v (PrimState m) a -> m b
foldM b -> a -> m b
f = (b -> Int -> a -> m b) -> b -> v (PrimState m) a -> m b
forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> Int -> a -> m b) -> b -> v (PrimState m) a -> m b
ifoldM (\b
x Int
_ -> b -> a -> m b
f b
x)

-- | /O(n)/ Monadic fold with strict accumulator.
--
-- @since 0.12.3.0
foldM' :: (PrimMonad m, MVector v a) => (b -> a -> m b) -> b -> v (PrimState m) a -> m b
{-# INLINE foldM' #-}
foldM' :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> a -> m b) -> b -> v (PrimState m) a -> m b
foldM' b -> a -> m b
f = (b -> Int -> a -> m b) -> b -> v (PrimState m) a -> m b
forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> Int -> a -> m b) -> b -> v (PrimState m) a -> m b
ifoldM' (\b
x Int
_ -> b -> a -> m b
f b
x)

-- | /O(n)/ Monadic fold using a function applied to each element and its index.
--
-- @since 0.12.3.0
ifoldM :: (PrimMonad m, MVector v a) => (b -> Int -> a -> m b) -> b -> v (PrimState m) a -> m b
{-# INLINE ifoldM #-}
ifoldM :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> Int -> a -> m b) -> b -> v (PrimState m) a -> m b
ifoldM b -> Int -> a -> m b
f b
b0 v (PrimState m) a
v = Int -> b -> m b
loop Int
0 b
b0
  where
    loop :: Int -> b -> m b
loop Int
i b
b | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n    = b -> m b
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return b
b
             | Bool
otherwise = do a
a <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i
                              Int -> b -> m b
loop (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (b -> m b) -> m b -> m b
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< b -> Int -> a -> m b
f b
b Int
i a
a
    n :: Int
n = v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v

-- | /O(n)/ Monadic fold with strict accumulator using a function applied to each element and its index.
--
-- @since 0.12.3.0
ifoldM' :: (PrimMonad m, MVector v a) => (b -> Int -> a -> m b) -> b -> v (PrimState m) a -> m b
{-# INLINE ifoldM' #-}
ifoldM' :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> Int -> a -> m b) -> b -> v (PrimState m) a -> m b
ifoldM' b -> Int -> a -> m b
f b
b0 v (PrimState m) a
v = Int -> b -> m b
loop Int
0 b
b0
  where
    loop :: Int -> b -> m b
loop Int
i !b
b | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n    = b -> m b
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return b
b
              | Bool
otherwise = do a
a <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i
                               Int -> b -> m b
loop (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (b -> m b) -> m b -> m b
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< b -> Int -> a -> m b
f b
b Int
i a
a
    n :: Int
n = v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v

-- | /O(n)/ Monadic right fold.
--
-- @since 0.12.3.0
foldrM :: (PrimMonad m, MVector v a) => (a -> b -> m b) -> b -> v (PrimState m) a -> m b
{-# INLINE foldrM #-}
foldrM :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(a -> b -> m b) -> b -> v (PrimState m) a -> m b
foldrM a -> b -> m b
f = (Int -> a -> b -> m b) -> b -> v (PrimState m) a -> m b
forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(Int -> a -> b -> m b) -> b -> v (PrimState m) a -> m b
ifoldrM ((a -> b -> m b) -> Int -> a -> b -> m b
forall a b. a -> b -> a
const a -> b -> m b
f)

-- | /O(n)/ Monadic right fold with strict accumulator.
--
-- @since 0.12.3.0
foldrM' :: (PrimMonad m, MVector v a) => (a -> b -> m b) -> b -> v (PrimState m) a -> m b
{-# INLINE foldrM' #-}
foldrM' :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(a -> b -> m b) -> b -> v (PrimState m) a -> m b
foldrM' a -> b -> m b
f = (Int -> a -> b -> m b) -> b -> v (PrimState m) a -> m b
forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(Int -> a -> b -> m b) -> b -> v (PrimState m) a -> m b
ifoldrM' ((a -> b -> m b) -> Int -> a -> b -> m b
forall a b. a -> b -> a
const a -> b -> m b
f)

-- | /O(n)/ Monadic right fold using a function applied to each element and its index.
--
-- @since 0.12.3.0
ifoldrM :: (PrimMonad m, MVector v a) => (Int -> a -> b -> m b) -> b -> v (PrimState m) a -> m b
{-# INLINE ifoldrM #-}
ifoldrM :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(Int -> a -> b -> m b) -> b -> v (PrimState m) a -> m b
ifoldrM Int -> a -> b -> m b
f b
b0 v (PrimState m) a
v = Int -> b -> m b
loop (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) b
b0
  where
    loop :: Int -> b -> m b
loop Int
i b
b | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0     = b -> m b
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return b
b
             | Bool
otherwise = do a
a <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i
                              Int -> b -> m b
loop (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) (b -> m b) -> m b -> m b
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Int -> a -> b -> m b
f Int
i a
a b
b
    n :: Int
n = v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v

-- | /O(n)/ Monadic right fold with strict accumulator using a function applied
-- to each element and its index.
--
-- @since 0.12.3.0
ifoldrM' :: (PrimMonad m, MVector v a) => (Int -> a -> b -> m b) -> b -> v (PrimState m) a -> m b
{-# INLINE ifoldrM' #-}
ifoldrM' :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(Int -> a -> b -> m b) -> b -> v (PrimState m) a -> m b
ifoldrM' Int -> a -> b -> m b
f b
b0 v (PrimState m) a
v = Int -> b -> m b
loop (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) b
b0
  where
    loop :: Int -> b -> m b
loop Int
i !b
b | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0     = b -> m b
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return b
b
              | Bool
otherwise = do a
a <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i
                               Int -> b -> m b
loop (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) (b -> m b) -> m b -> m b
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Int -> a -> b -> m b
f Int
i a
a b
b
    n :: Int
n = v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v

-- Filling and copying
-- -------------------

-- | Set all elements of the vector to the given value.
set :: (PrimMonad m, MVector v a) => v (PrimState m) a -> a -> m ()
{-# INLINE set #-}
set :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> a -> m ()
set v (PrimState m) a
v = ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ())
-> (a -> ST (PrimState m) ()) -> a -> m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v (PrimState m) a -> a -> ST (PrimState m) ()
forall s. v s a -> a -> ST s ()
forall (v :: * -> * -> *) a s. MVector v a => v s a -> a -> ST s ()
basicSet v (PrimState m) a
v

-- | Copy a vector. The two vectors must have the same length and may not
-- overlap.
copy :: (HasCallStack, PrimMonad m, MVector v a)
     => v (PrimState m) a   -- ^ target
     -> v (PrimState m) a   -- ^ source
     -> m ()
{-# INLINE copy #-}
copy :: forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> v (PrimState m) a -> m ()
copy v (PrimState m) a
dst v (PrimState m) a
src = Checks -> String -> Bool -> m () -> m ()
forall a. HasCallStack => Checks -> String -> Bool -> a -> a
check Checks
Bounds String
"overlapping vectors" (Bool -> Bool
not (v (PrimState m) a
dst v (PrimState m) a -> v (PrimState m) a -> Bool
forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> v s a -> Bool
`overlaps` v (PrimState m) a
src))
             (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ Checks -> String -> Bool -> m () -> m ()
forall a. HasCallStack => Checks -> String -> Bool -> a -> a
check Checks
Bounds String
"length mismatch" (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
dst Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
src)
             (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> v (PrimState m) a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> v (PrimState m) a -> m ()
unsafeCopy v (PrimState m) a
dst v (PrimState m) a
src

-- | Move the contents of a vector. The two vectors must have the same
-- length.
--
-- If the vectors do not overlap, then this is equivalent to 'copy'.
-- Otherwise, the copying is performed as if the source vector were
-- copied to a temporary vector and then the temporary vector was copied
-- to the target vector.
move :: (HasCallStack, PrimMonad m, MVector v a)
     => v (PrimState m) a   -- ^ target
     -> v (PrimState m) a   -- ^ source
     -> m ()
{-# INLINE move #-}
move :: forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> v (PrimState m) a -> m ()
move v (PrimState m) a
dst v (PrimState m) a
src = Checks -> String -> Bool -> m () -> m ()
forall a. HasCallStack => Checks -> String -> Bool -> a -> a
check Checks
Bounds String
"length mismatch" (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
dst Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
src)
             (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> v (PrimState m) a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> v (PrimState m) a -> m ()
unsafeMove v (PrimState m) a
dst v (PrimState m) a
src

-- | Copy a vector. The two vectors must have the same length and may not
-- overlap, but this is not checked.
unsafeCopy :: (PrimMonad m, MVector v a)
           => v (PrimState m) a   -- ^ target
           -> v (PrimState m) a   -- ^ source
           -> m ()
{-# INLINE unsafeCopy #-}
unsafeCopy :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> v (PrimState m) a -> m ()
unsafeCopy v (PrimState m) a
dst v (PrimState m) a
src = Checks -> String -> Bool -> m () -> m ()
forall a. HasCallStack => Checks -> String -> Bool -> a -> a
check Checks
Unsafe String
"length mismatch" (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
dst Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
src)
                   (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ Checks -> String -> Bool -> m () -> m ()
forall a. HasCallStack => Checks -> String -> Bool -> a -> a
check Checks
Unsafe String
"overlapping vectors" (Bool -> Bool
not (v (PrimState m) a
dst v (PrimState m) a -> v (PrimState m) a -> Bool
forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> v s a -> Bool
`overlaps` v (PrimState m) a
src))
                   (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a
dst v (PrimState m) a -> m () -> m ()
forall a b. a -> b -> b
`seq` v (PrimState m) a
src v (PrimState m) a -> m () -> m ()
forall a b. a -> b -> b
`seq` ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (v (PrimState m) a -> v (PrimState m) a -> ST (PrimState m) ()
forall s. v s a -> v s a -> ST s ()
forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> v s a -> ST s ()
basicUnsafeCopy v (PrimState m) a
dst v (PrimState m) a
src)

-- | Move the contents of a vector. The two vectors must have the same
-- length, but this is not checked.
--
-- If the vectors do not overlap, then this is equivalent to 'unsafeCopy'.
-- Otherwise, the copying is performed as if the source vector were
-- copied to a temporary vector and then the temporary vector was copied
-- to the target vector.
unsafeMove :: (PrimMonad m, MVector v a)
           => v (PrimState m) a   -- ^ target
           -> v (PrimState m) a   -- ^ source
           -> m ()
{-# INLINE unsafeMove #-}
unsafeMove :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> v (PrimState m) a -> m ()
unsafeMove v (PrimState m) a
dst v (PrimState m) a
src = Checks -> String -> Bool -> m () -> m ()
forall a. HasCallStack => Checks -> String -> Bool -> a -> a
check Checks
Unsafe String
"length mismatch" (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
dst Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
src)
                   (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a
dst v (PrimState m) a -> m () -> m ()
forall a b. a -> b -> b
`seq` v (PrimState m) a
src v (PrimState m) a -> m () -> m ()
forall a b. a -> b -> b
`seq` ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (v (PrimState m) a -> v (PrimState m) a -> ST (PrimState m) ()
forall s. v s a -> v s a -> ST s ()
forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> v s a -> ST s ()
basicUnsafeMove v (PrimState m) a
dst v (PrimState m) a
src)


accum :: forall m v a b u. (HasCallStack, PrimMonad m, MVector v a)
      => (a -> b -> a) -> v (PrimState m) a -> Bundle u (Int, b) -> m ()
{-# INLINE accum #-}
accum :: forall (m :: * -> *) (v :: * -> * -> *) a b (u :: * -> *).
(HasCallStack, PrimMonad m, MVector v a) =>
(a -> b -> a) -> v (PrimState m) a -> Bundle u (Int, b) -> m ()
accum a -> b -> a
f !v (PrimState m) a
v Bundle u (Int, b)
s = ((Int, b) -> m ()) -> Bundle u (Int, b) -> m ()
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> m b) -> Bundle v a -> m ()
Bundle.mapM_ HasCallStack => (Int, b) -> m ()
(Int, b) -> m ()
upd Bundle u (Int, b)
s
  where
    {-# INLINE_INNER upd #-}
    upd :: HasCallStack => (Int, b) -> m ()
    upd :: HasCallStack => (Int, b) -> m ()
upd (Int
i,b
b) = do
                  a
a <- Checks -> Int -> Int -> m a -> m a
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
i Int
n (m a -> m a) -> m a -> m a
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i
                  v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v Int
i (a -> b -> a
f a
a b
b)
    !n :: Int
n = v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v

update :: forall m v a u. (HasCallStack, PrimMonad m, MVector v a)
       => v (PrimState m) a -> Bundle u (Int, a) -> m ()
{-# INLINE update #-}
update :: forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Bundle u (Int, a) -> m ()
update !v (PrimState m) a
v Bundle u (Int, a)
s = ((Int, a) -> m ()) -> Bundle u (Int, a) -> m ()
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> m b) -> Bundle v a -> m ()
Bundle.mapM_ HasCallStack => (Int, a) -> m ()
(Int, a) -> m ()
upd Bundle u (Int, a)
s
  where
    {-# INLINE_INNER upd #-}
    upd :: HasCallStack => (Int, a) -> m ()
    upd :: HasCallStack => (Int, a) -> m ()
upd (Int
i,a
b) = Checks -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
i Int
n (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v Int
i a
b

    !n :: Int
n = v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v

unsafeAccum :: (PrimMonad m, MVector v a)
            => (a -> b -> a) -> v (PrimState m) a -> Bundle u (Int, b) -> m ()
{-# INLINE unsafeAccum #-}
unsafeAccum :: forall (m :: * -> *) (v :: * -> * -> *) a b (u :: * -> *).
(PrimMonad m, MVector v a) =>
(a -> b -> a) -> v (PrimState m) a -> Bundle u (Int, b) -> m ()
unsafeAccum a -> b -> a
f !v (PrimState m) a
v Bundle u (Int, b)
s = ((Int, b) -> m ()) -> Bundle u (Int, b) -> m ()
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> m b) -> Bundle v a -> m ()
Bundle.mapM_ (Int, b) -> m ()
upd Bundle u (Int, b)
s
  where
    {-# INLINE_INNER upd #-}
    upd :: (Int, b) -> m ()
upd (Int
i,b
b) = do
                  a
a <- Checks -> Int -> Int -> m a -> m a
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
i Int
n (m a -> m a) -> m a -> m a
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i
                  v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v Int
i (a -> b -> a
f a
a b
b)
    !n :: Int
n = v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v

unsafeUpdate :: (PrimMonad m, MVector v a)
                        => v (PrimState m) a -> Bundle u (Int, a) -> m ()
{-# INLINE unsafeUpdate #-}
unsafeUpdate :: forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Bundle u (Int, a) -> m ()
unsafeUpdate !v (PrimState m) a
v Bundle u (Int, a)
s = ((Int, a) -> m ()) -> Bundle u (Int, a) -> m ()
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> m b) -> Bundle v a -> m ()
Bundle.mapM_ (Int, a) -> m ()
upd Bundle u (Int, a)
s
  where
    {-# INLINE_INNER upd #-}
    upd :: (Int, a) -> m ()
upd (Int
i,a
b) = Checks -> Int -> Int -> m () -> m ()
forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
i Int
n (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v Int
i a
b
    !n :: Int
n = v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v

reverse :: (PrimMonad m, MVector v a) => v (PrimState m) a -> m ()
{-# INLINE reverse #-}
reverse :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> m ()
reverse !v (PrimState m) a
v = Int -> Int -> m ()
reverse_loop Int
0 (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
  where
    reverse_loop :: Int -> Int -> m ()
reverse_loop Int
i Int
j | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
j = do
                                 v (PrimState m) a -> Int -> Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> Int -> m ()
unsafeSwap v (PrimState m) a
v Int
i Int
j
                                 Int -> Int -> m ()
reverse_loop (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
    reverse_loop Int
_ Int
_ = () -> m ()
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ()

unstablePartition :: forall m v a. (PrimMonad m, MVector v a)
                  => (a -> Bool) -> v (PrimState m) a -> m Int
{-# INLINE unstablePartition #-}
unstablePartition :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
(a -> Bool) -> v (PrimState m) a -> m Int
unstablePartition a -> Bool
f !v (PrimState m) a
v = Int -> Int -> m Int
from_left Int
0 (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
  where
    -- NOTE: GHC 6.10.4 panics without the signatures on from_left and
    -- from_right
    from_left :: Int -> Int -> m Int
    from_left :: Int -> Int -> m Int
from_left Int
i Int
j
      | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
j    = Int -> m Int
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Int
i
      | Bool
otherwise = do
                      a
x <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i
                      if a -> Bool
f a
x
                        then Int -> Int -> m Int
from_left (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int
j
                        else Int -> Int -> m Int
from_right Int
i (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)

    from_right :: Int -> Int -> m Int
    from_right :: Int -> Int -> m Int
from_right Int
i Int
j
      | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
j    = Int -> m Int
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Int
i
      | Bool
otherwise = do
                      a
x <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
j
                      if a -> Bool
f a
x
                        then do
                               a
y <- v (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i
                               v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v Int
i a
x
                               v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v Int
j a
y
                               Int -> Int -> m Int
from_left (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int
j
                        else Int -> Int -> m Int
from_right Int
i (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)

unstablePartitionBundle :: (PrimMonad m, MVector v a)
        => (a -> Bool) -> Bundle u a -> m (v (PrimState m) a, v (PrimState m) a)
{-# INLINE unstablePartitionBundle #-}
unstablePartitionBundle :: forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
(a -> Bool)
-> Bundle u a -> m (v (PrimState m) a, v (PrimState m) a)
unstablePartitionBundle a -> Bool
f Bundle u a
s
  = case Size -> Maybe Int
upperBound (Bundle u a -> Size
forall (v :: * -> *) a. Bundle v a -> Size
Bundle.size Bundle u a
s) of
      Just Int
n  -> (a -> Bool)
-> Bundle u a -> Int -> m (v (PrimState m) a, v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
(a -> Bool)
-> Bundle u a -> Int -> m (v (PrimState m) a, v (PrimState m) a)
unstablePartitionMax a -> Bool
f Bundle u a
s Int
n
      Maybe Int
Nothing -> (a -> Bool)
-> Bundle u a -> m (v (PrimState m) a, v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
(a -> Bool)
-> Bundle u a -> m (v (PrimState m) a, v (PrimState m) a)
partitionUnknown a -> Bool
f Bundle u a
s

unstablePartitionMax :: (PrimMonad m, MVector v a)
        => (a -> Bool) -> Bundle u a -> Int
        -> m (v (PrimState m) a, v (PrimState m) a)
{-# INLINE unstablePartitionMax #-}
unstablePartitionMax :: forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
(a -> Bool)
-> Bundle u a -> Int -> m (v (PrimState m) a, v (PrimState m) a)
unstablePartitionMax a -> Bool
f Bundle u a
s Int
n
  = do
      v (PrimState m) a
v <- Checks -> Int -> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Internal Int
n (m (v (PrimState m) a) -> m (v (PrimState m) a))
-> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Int -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
n
      let {-# INLINE_INNER put #-}
          put :: (Int, Int) -> a -> m (Int, Int)
put (Int
i, Int
j) a
x
            | a -> Bool
f a
x       = do
                            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v Int
i a
x
                            (Int, Int) -> m (Int, Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1, Int
j)
            | Bool
otherwise = do
                            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) a
x
                            (Int, Int) -> m (Int, Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
i, Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)

      (Int
i,Int
j) <- ((Int, Int) -> a -> m (Int, Int))
-> (Int, Int) -> Bundle u a -> m (Int, Int)
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle v b -> m a
Bundle.foldM' (Int, Int) -> a -> m (Int, Int)
put (Int
0, Int
n) Bundle u a
s
      (v (PrimState m) a, v (PrimState m) a)
-> m (v (PrimState m) a, v (PrimState m) a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 Int
i v (PrimState m) a
v, Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
j (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
j) v (PrimState m) a
v)

partitionBundle :: (PrimMonad m, MVector v a)
        => (a -> Bool) -> Bundle u a -> m (v (PrimState m) a, v (PrimState m) a)
{-# INLINE partitionBundle #-}
partitionBundle :: forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
(a -> Bool)
-> Bundle u a -> m (v (PrimState m) a, v (PrimState m) a)
partitionBundle a -> Bool
f Bundle u a
s
  = case Size -> Maybe Int
upperBound (Bundle u a -> Size
forall (v :: * -> *) a. Bundle v a -> Size
Bundle.size Bundle u a
s) of
      Just Int
n  -> (a -> Bool)
-> Bundle u a -> Int -> m (v (PrimState m) a, v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
(a -> Bool)
-> Bundle u a -> Int -> m (v (PrimState m) a, v (PrimState m) a)
partitionMax a -> Bool
f Bundle u a
s Int
n
      Maybe Int
Nothing -> (a -> Bool)
-> Bundle u a -> m (v (PrimState m) a, v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
(a -> Bool)
-> Bundle u a -> m (v (PrimState m) a, v (PrimState m) a)
partitionUnknown a -> Bool
f Bundle u a
s

partitionMax :: (PrimMonad m, MVector v a)
  => (a -> Bool) -> Bundle u a -> Int -> m (v (PrimState m) a, v (PrimState m) a)
{-# INLINE partitionMax #-}
partitionMax :: forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
(a -> Bool)
-> Bundle u a -> Int -> m (v (PrimState m) a, v (PrimState m) a)
partitionMax a -> Bool
f Bundle u a
s Int
n
  = do
      v (PrimState m) a
v <- Checks -> Int -> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Internal Int
n (m (v (PrimState m) a) -> m (v (PrimState m) a))
-> m (v (PrimState m) a) -> m (v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Int -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
n

      let {-# INLINE_INNER put #-}
          put :: (Int, Int) -> a -> m (Int, Int)
put (Int
i,Int
j) a
x
            | a -> Bool
f a
x       = do
                            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v Int
i a
x
                            (Int, Int) -> m (Int, Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1,Int
j)

            | Bool
otherwise = let j' :: Int
j' = Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1 in
                          do
                            v (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v Int
j' a
x
                            (Int, Int) -> m (Int, Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
i,Int
j')

      (Int
i,Int
j) <- ((Int, Int) -> a -> m (Int, Int))
-> (Int, Int) -> Bundle u a -> m (Int, Int)
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle v b -> m a
Bundle.foldM' (Int, Int) -> a -> m (Int, Int)
put (Int
0,Int
n) Bundle u a
s
      Checks -> String -> Bool -> m () -> m ()
forall a. HasCallStack => Checks -> String -> Bool -> a -> a
check Checks
Internal String
"invalid indices" (Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
j)
        (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ () -> m ()
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ()
      let l :: v (PrimState m) a
l = Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 Int
i v (PrimState m) a
v
          r :: v (PrimState m) a
r = Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
j (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
j) v (PrimState m) a
v
      v (PrimState m) a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> m ()
reverse v (PrimState m) a
r
      (v (PrimState m) a, v (PrimState m) a)
-> m (v (PrimState m) a, v (PrimState m) a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) a
l,v (PrimState m) a
r)

partitionUnknown :: (PrimMonad m, MVector v a)
        => (a -> Bool) -> Bundle u a -> m (v (PrimState m) a, v (PrimState m) a)
{-# INLINE partitionUnknown #-}
partitionUnknown :: forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
(a -> Bool)
-> Bundle u a -> m (v (PrimState m) a, v (PrimState m) a)
partitionUnknown a -> Bool
f Bundle u a
s
  = do
      v (PrimState m) a
v1 <- Int -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
0
      v (PrimState m) a
v2 <- Int -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
0
      (v (PrimState m) a
v1', Int
n1, v (PrimState m) a
v2', Int
n2) <- ((v (PrimState m) a, Int, v (PrimState m) a, Int)
 -> a -> m (v (PrimState m) a, Int, v (PrimState m) a, Int))
-> (v (PrimState m) a, Int, v (PrimState m) a, Int)
-> Bundle u a
-> m (v (PrimState m) a, Int, v (PrimState m) a, Int)
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle v b -> m a
Bundle.foldM' (v (PrimState m) a, Int, v (PrimState m) a, Int)
-> a -> m (v (PrimState m) a, Int, v (PrimState m) a, Int)
put (v (PrimState m) a
v1, Int
0, v (PrimState m) a
v2, Int
0) Bundle u a
s
      Checks
-> Int
-> Int
-> Int
-> m (v (PrimState m) a, v (PrimState m) a)
-> m (v (PrimState m) a, v (PrimState m) a)
forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n1 (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v1')
        (m (v (PrimState m) a, v (PrimState m) a)
 -> m (v (PrimState m) a, v (PrimState m) a))
-> m (v (PrimState m) a, v (PrimState m) a)
-> m (v (PrimState m) a, v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ Checks
-> Int
-> Int
-> Int
-> m (v (PrimState m) a, v (PrimState m) a)
-> m (v (PrimState m) a, v (PrimState m) a)
forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n2 (v (PrimState m) a -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v2')
        (m (v (PrimState m) a, v (PrimState m) a)
 -> m (v (PrimState m) a, v (PrimState m) a))
-> m (v (PrimState m) a, v (PrimState m) a)
-> m (v (PrimState m) a, v (PrimState m) a)
forall a b. (a -> b) -> a -> b
$ (v (PrimState m) a, v (PrimState m) a)
-> m (v (PrimState m) a, v (PrimState m) a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 Int
n1 v (PrimState m) a
v1', Int -> Int -> v (PrimState m) a -> v (PrimState m) a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 Int
n2 v (PrimState m) a
v2')
  where
    -- NOTE: The case distinction has to be on the outside because
    -- GHC creates a join point for the unsafeWrite even when everything
    -- is inlined. This is bad because with the join point, v isn't getting
    -- unboxed.
    {-# INLINE_INNER put #-}
    put :: (v (PrimState m) a, Int, v (PrimState m) a, Int)
-> a -> m (v (PrimState m) a, Int, v (PrimState m) a, Int)
put (v (PrimState m) a
v1, Int
i1, v (PrimState m) a
v2, Int
i2) a
x
      | a -> Bool
f a
x       = do
                      v (PrimState m) a
v1' <- v (PrimState m) a -> Int -> a -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m (v (PrimState m) a)
unsafeAppend1 v (PrimState m) a
v1 Int
i1 a
x
                      (v (PrimState m) a, Int, v (PrimState m) a, Int)
-> m (v (PrimState m) a, Int, v (PrimState m) a, Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) a
v1', Int
i1Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1, v (PrimState m) a
v2, Int
i2)
      | Bool
otherwise = do
                      v (PrimState m) a
v2' <- v (PrimState m) a -> Int -> a -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m (v (PrimState m) a)
unsafeAppend1 v (PrimState m) a
v2 Int
i2 a
x
                      (v (PrimState m) a, Int, v (PrimState m) a, Int)
-> m (v (PrimState m) a, Int, v (PrimState m) a, Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) a
v1, Int
i1, v (PrimState m) a
v2', Int
i2Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)


partitionWithBundle :: (PrimMonad m, MVector v a, MVector v b, MVector v c)
        => (a -> Either b c) -> Bundle u a -> m (v (PrimState m) b, v (PrimState m) c)
{-# INLINE partitionWithBundle #-}
partitionWithBundle :: forall (m :: * -> *) (v :: * -> * -> *) a b c (u :: * -> *).
(PrimMonad m, MVector v a, MVector v b, MVector v c) =>
(a -> Either b c)
-> Bundle u a -> m (v (PrimState m) b, v (PrimState m) c)
partitionWithBundle a -> Either b c
f Bundle u a
s
  = case Size -> Maybe Int
upperBound (Bundle u a -> Size
forall (v :: * -> *) a. Bundle v a -> Size
Bundle.size Bundle u a
s) of
      Just Int
n  -> (a -> Either b c)
-> Bundle u a -> Int -> m (v (PrimState m) b, v (PrimState m) c)
forall (m :: * -> *) (v :: * -> * -> *) a b c (u :: * -> *).
(PrimMonad m, MVector v a, MVector v b, MVector v c) =>
(a -> Either b c)
-> Bundle u a -> Int -> m (v (PrimState m) b, v (PrimState m) c)
partitionWithMax a -> Either b c
f Bundle u a
s Int
n
      Maybe Int
Nothing -> (a -> Either b c)
-> Bundle u a -> m (v (PrimState m) b, v (PrimState m) c)
forall (m :: * -> *) (v :: * -> * -> *) (u :: * -> *) a b c.
(PrimMonad m, MVector v a, MVector v b, MVector v c) =>
(a -> Either b c)
-> Bundle u a -> m (v (PrimState m) b, v (PrimState m) c)
partitionWithUnknown a -> Either b c
f Bundle u a
s

partitionWithMax :: (PrimMonad m, MVector v a, MVector v b, MVector v c)
  => (a -> Either b c) -> Bundle u a -> Int -> m (v (PrimState m) b, v (PrimState m) c)
{-# INLINE partitionWithMax #-}
partitionWithMax :: forall (m :: * -> *) (v :: * -> * -> *) a b c (u :: * -> *).
(PrimMonad m, MVector v a, MVector v b, MVector v c) =>
(a -> Either b c)
-> Bundle u a -> Int -> m (v (PrimState m) b, v (PrimState m) c)
partitionWithMax a -> Either b c
f Bundle u a
s Int
n
  = do
      v (PrimState m) b
v1 <- Int -> m (v (PrimState m) b)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
n
      v (PrimState m) c
v2 <- Int -> m (v (PrimState m) c)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
n
      let {-# INLINE_INNER put #-}
          put :: (Int, Int) -> a -> m (Int, Int)
put (Int
i1, Int
i2) a
x = case a -> Either b c
f a
x of
            Left b
b -> do
              v (PrimState m) b -> Int -> b -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) b
v1 Int
i1 b
b
              (Int, Int) -> m (Int, Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
i1Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1, Int
i2)
            Right c
c -> do
              v (PrimState m) c -> Int -> c -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) c
v2 Int
i2 c
c
              (Int, Int) -> m (Int, Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
i1, Int
i2Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
      (Int
n1, Int
n2) <- ((Int, Int) -> a -> m (Int, Int))
-> (Int, Int) -> Bundle u a -> m (Int, Int)
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle v b -> m a
Bundle.foldM' (Int, Int) -> a -> m (Int, Int)
put (Int
0, Int
0) Bundle u a
s
      Checks
-> Int
-> Int
-> Int
-> m (v (PrimState m) b, v (PrimState m) c)
-> m (v (PrimState m) b, v (PrimState m) c)
forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n1 (v (PrimState m) b -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) b
v1)
        (m (v (PrimState m) b, v (PrimState m) c)
 -> m (v (PrimState m) b, v (PrimState m) c))
-> m (v (PrimState m) b, v (PrimState m) c)
-> m (v (PrimState m) b, v (PrimState m) c)
forall a b. (a -> b) -> a -> b
$ Checks
-> Int
-> Int
-> Int
-> m (v (PrimState m) b, v (PrimState m) c)
-> m (v (PrimState m) b, v (PrimState m) c)
forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n2 (v (PrimState m) c -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) c
v2)
        (m (v (PrimState m) b, v (PrimState m) c)
 -> m (v (PrimState m) b, v (PrimState m) c))
-> m (v (PrimState m) b, v (PrimState m) c)
-> m (v (PrimState m) b, v (PrimState m) c)
forall a b. (a -> b) -> a -> b
$ (v (PrimState m) b, v (PrimState m) c)
-> m (v (PrimState m) b, v (PrimState m) c)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int -> Int -> v (PrimState m) b -> v (PrimState m) b
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 Int
n1 v (PrimState m) b
v1, Int -> Int -> v (PrimState m) c -> v (PrimState m) c
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 Int
n2 v (PrimState m) c
v2)

partitionWithUnknown :: forall m v u a b c.
     (PrimMonad m, MVector v a, MVector v b, MVector v c)
  => (a -> Either b c) -> Bundle u a -> m (v (PrimState m) b, v (PrimState m) c)
{-# INLINE partitionWithUnknown #-}
partitionWithUnknown :: forall (m :: * -> *) (v :: * -> * -> *) (u :: * -> *) a b c.
(PrimMonad m, MVector v a, MVector v b, MVector v c) =>
(a -> Either b c)
-> Bundle u a -> m (v (PrimState m) b, v (PrimState m) c)
partitionWithUnknown a -> Either b c
f Bundle u a
s
  = do
      v (PrimState m) b
v1 <- Int -> m (v (PrimState m) b)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
0
      v (PrimState m) c
v2 <- Int -> m (v (PrimState m) c)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
0
      (v (PrimState m) b
v1', Int
n1, v (PrimState m) c
v2', Int
n2) <- ((v (PrimState m) b, Int, v (PrimState m) c, Int)
 -> a -> m (v (PrimState m) b, Int, v (PrimState m) c, Int))
-> (v (PrimState m) b, Int, v (PrimState m) c, Int)
-> Bundle u a
-> m (v (PrimState m) b, Int, v (PrimState m) c, Int)
forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle v b -> m a
Bundle.foldM' (v (PrimState m) b, Int, v (PrimState m) c, Int)
-> a -> m (v (PrimState m) b, Int, v (PrimState m) c, Int)
put (v (PrimState m) b
v1, Int
0, v (PrimState m) c
v2, Int
0) Bundle u a
s
      Checks
-> Int
-> Int
-> Int
-> m (v (PrimState m) b, v (PrimState m) c)
-> m (v (PrimState m) b, v (PrimState m) c)
forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n1 (v (PrimState m) b -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) b
v1')
        (m (v (PrimState m) b, v (PrimState m) c)
 -> m (v (PrimState m) b, v (PrimState m) c))
-> m (v (PrimState m) b, v (PrimState m) c)
-> m (v (PrimState m) b, v (PrimState m) c)
forall a b. (a -> b) -> a -> b
$ Checks
-> Int
-> Int
-> Int
-> m (v (PrimState m) b, v (PrimState m) c)
-> m (v (PrimState m) b, v (PrimState m) c)
forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n2 (v (PrimState m) c -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) c
v2')
        (m (v (PrimState m) b, v (PrimState m) c)
 -> m (v (PrimState m) b, v (PrimState m) c))
-> m (v (PrimState m) b, v (PrimState m) c)
-> m (v (PrimState m) b, v (PrimState m) c)
forall a b. (a -> b) -> a -> b
$ (v (PrimState m) b, v (PrimState m) c)
-> m (v (PrimState m) b, v (PrimState m) c)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int -> Int -> v (PrimState m) b -> v (PrimState m) b
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 Int
n1 v (PrimState m) b
v1', Int -> Int -> v (PrimState m) c -> v (PrimState m) c
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 Int
n2 v (PrimState m) c
v2')
  where
    put :: (v (PrimState m) b, Int, v (PrimState m) c, Int)
        -> a
        -> m (v (PrimState m) b, Int, v (PrimState m) c, Int)
    {-# INLINE_INNER put #-}
    put :: (v (PrimState m) b, Int, v (PrimState m) c, Int)
-> a -> m (v (PrimState m) b, Int, v (PrimState m) c, Int)
put (v (PrimState m) b
v1, Int
i1, v (PrimState m) c
v2, Int
i2) a
x = case a -> Either b c
f a
x of
      Left b
b -> do
        v (PrimState m) b
v1' <- v (PrimState m) b -> Int -> b -> m (v (PrimState m) b)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m (v (PrimState m) a)
unsafeAppend1 v (PrimState m) b
v1 Int
i1 b
b
        (v (PrimState m) b, Int, v (PrimState m) c, Int)
-> m (v (PrimState m) b, Int, v (PrimState m) c, Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) b
v1', Int
i1Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1, v (PrimState m) c
v2, Int
i2)
      Right c
c -> do
        v (PrimState m) c
v2' <- v (PrimState m) c -> Int -> c -> m (v (PrimState m) c)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m (v (PrimState m) a)
unsafeAppend1 v (PrimState m) c
v2 Int
i2 c
c
        (v (PrimState m) b, Int, v (PrimState m) c, Int)
-> m (v (PrimState m) b, Int, v (PrimState m) c, Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) b
v1, Int
i1, v (PrimState m) c
v2', Int
i2Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)

-- Modifying vectors
-- -----------------


-- | Compute the (lexicographically) next permutation of the given vector in-place.
-- Returns False when the input is the last item in the enumeration, i.e., if it is in
-- weakly descending order. In this case the vector will not get updated,
-- as opposed to the behavior of the C++ function @std::next_permutation@.
nextPermutation :: (PrimMonad m, Ord e, MVector v e) => v (PrimState m) e -> m Bool
{-# INLINE nextPermutation #-}
nextPermutation :: forall (m :: * -> *) e (v :: * -> * -> *).
(PrimMonad m, Ord e, MVector v e) =>
v (PrimState m) e -> m Bool
nextPermutation = (e -> e -> Bool) -> v (PrimState m) e -> m Bool
forall (m :: * -> *) (v :: * -> * -> *) e.
(PrimMonad m, MVector v e) =>
(e -> e -> Bool) -> v (PrimState m) e -> m Bool
nextPermutationByLt e -> e -> Bool
forall a. Ord a => a -> a -> Bool
(<)

-- | Compute the (lexicographically) next permutation of the given vector in-place,
-- using the provided comparison function.
-- Returns False when the input is the last item in the enumeration, i.e., if it is in
-- weakly descending order. In this case the vector will not get updated,
-- as opposed to the behavior of the C++ function @std::next_permutation@.
--
-- @since 0.13.2.0
nextPermutationBy :: (PrimMonad m, MVector v e) => (e -> e -> Ordering) -> v (PrimState m) e -> m Bool
{-# INLINE nextPermutationBy #-}
nextPermutationBy :: forall (m :: * -> *) (v :: * -> * -> *) e.
(PrimMonad m, MVector v e) =>
(e -> e -> Ordering) -> v (PrimState m) e -> m Bool
nextPermutationBy e -> e -> Ordering
cmp = (e -> e -> Bool) -> v (PrimState m) e -> m Bool
forall (m :: * -> *) (v :: * -> * -> *) e.
(PrimMonad m, MVector v e) =>
(e -> e -> Bool) -> v (PrimState m) e -> m Bool
nextPermutationByLt (\e
x e
y -> e -> e -> Ordering
cmp e
x e
y Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
== Ordering
LT)

-- | Compute the (lexicographically) previous permutation of the given vector in-place.
-- Returns False when the input is the last item in the enumeration, i.e., if it is in
-- weakly ascending order. In this case the vector will not get updated,
-- as opposed to the behavior of the C++ function @std::prev_permutation@.
--
-- @since 0.13.2.0
prevPermutation :: (PrimMonad m, Ord e, MVector v e) => v (PrimState m) e -> m Bool
{-# INLINE prevPermutation #-}
prevPermutation :: forall (m :: * -> *) e (v :: * -> * -> *).
(PrimMonad m, Ord e, MVector v e) =>
v (PrimState m) e -> m Bool
prevPermutation = (e -> e -> Bool) -> v (PrimState m) e -> m Bool
forall (m :: * -> *) (v :: * -> * -> *) e.
(PrimMonad m, MVector v e) =>
(e -> e -> Bool) -> v (PrimState m) e -> m Bool
nextPermutationByLt e -> e -> Bool
forall a. Ord a => a -> a -> Bool
(>)

-- | Compute the (lexicographically) previous permutation of the given vector in-place,
-- using the provided comparison function.
-- Returns False when the input is the last item in the enumeration, i.e., if it is in
-- weakly ascending order. In this case the vector will not get updated,
-- as opposed to the behavior of the C++ function @std::prev_permutation@.
--
-- @since 0.13.2.0
prevPermutationBy :: (PrimMonad m, MVector v e) => (e -> e -> Ordering) -> v (PrimState m) e -> m Bool
{-# INLINE prevPermutationBy #-}
prevPermutationBy :: forall (m :: * -> *) (v :: * -> * -> *) e.
(PrimMonad m, MVector v e) =>
(e -> e -> Ordering) -> v (PrimState m) e -> m Bool
prevPermutationBy e -> e -> Ordering
cmp = (e -> e -> Bool) -> v (PrimState m) e -> m Bool
forall (m :: * -> *) (v :: * -> * -> *) e.
(PrimMonad m, MVector v e) =>
(e -> e -> Bool) -> v (PrimState m) e -> m Bool
nextPermutationByLt (\e
x e
y -> e -> e -> Ordering
cmp e
x e
y Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
== Ordering
GT)

{-
http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

The following algorithm generates the next permutation lexicographically after
a given permutation. It changes the given permutation in-place.

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists,
   the permutation is the last permutation.
2. Find the largest index l greater than k such that a[k] < a[l].
3. Swap the value of a[k] with that of a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n]

The algorithm has been updated to look up the k in Step 1 beginning from the
last of the vector; which renders the algorithm to achieve the average time
complexity of O(1) each call. The worst case time complexity is still O(n).
The orginal implementation, which scanned the vector from the left, had the
time complexity of O(n) on the best case.
-}

-- | Compute the (lexicographically) next permutation of the given vector in-place.
-- Here, the first argument should be a less-than comparison function.
-- Returns False when the input is the last permutation; in this case the vector
-- will not get updated, as opposed to the behavior of the C++ function 
-- @std::next_permutation@.
nextPermutationByLt :: (PrimMonad m, MVector v e) => (e -> e -> Bool) -> v (PrimState m) e -> m Bool
{-# INLINE nextPermutationByLt #-}
nextPermutationByLt :: forall (m :: * -> *) (v :: * -> * -> *) e.
(PrimMonad m, MVector v e) =>
(e -> e -> Bool) -> v (PrimState m) e -> m Bool
nextPermutationByLt e -> e -> Bool
lt v (PrimState m) e
v
  | Int
dim Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
2 = Bool -> m Bool
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
  | Bool
otherwise = 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
      !e
vlast <- v (PrimState (ST (PrimState m))) e -> Int -> ST (PrimState m) e
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) e
v (PrimState (ST (PrimState m))) e
v (Int
dim Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
      Int -> e -> ST (PrimState m) Bool
decrLoop (Int
dim Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
2) e
vlast
  where
    dim :: Int
dim = v (PrimState m) e -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) e
v
    -- find the largest index k such that a[k] < a[k + 1], and then pass to the rest.
    decrLoop :: Int -> e -> ST (PrimState m) Bool
decrLoop !Int
i !e
vi1 | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 = do
      !e
vi <- v (PrimState (ST (PrimState m))) e -> Int -> ST (PrimState m) e
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) e
v (PrimState (ST (PrimState m))) e
v Int
i
      if e
vi e -> e -> Bool
`lt` e
vi1 then Int -> e -> Int -> e -> Int -> ST (PrimState m) Bool
swapLoop Int
i e
vi (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) e
vi1 Int
dim else Int -> e -> ST (PrimState m) Bool
decrLoop (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) e
vi
    decrLoop Int
_ !e
_ = Bool -> ST (PrimState m) Bool
forall a. a -> ST (PrimState m) a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
    -- find the largest index l greater than k such that a[k] < a[l], and do the rest.
    swapLoop :: Int -> e -> Int -> e -> Int -> ST (PrimState m) Bool
swapLoop !Int
k !e
vk = Int -> e -> Int -> ST (PrimState m) Bool
go
      where
        -- binary search.
        go :: Int -> e -> Int -> ST (PrimState m) Bool
go !Int
l !e
vl !Int
r | Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
1 = do
          -- Done; do the rest of the algorithm.
          v (PrimState (ST (PrimState m))) e
-> Int -> e -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) e
v (PrimState (ST (PrimState m))) e
v Int
k e
vl
          v (PrimState (ST (PrimState m))) e
-> Int -> e -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) e
v (PrimState (ST (PrimState m))) e
v Int
l e
vk
          v (PrimState (ST (PrimState m))) e -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> m ()
reverse (v (PrimState (ST (PrimState m))) e -> ST (PrimState m) ())
-> v (PrimState (ST (PrimState m))) e -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ Int -> Int -> v (PrimState m) e -> v (PrimState m) e
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice (Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (Int
dim Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) v (PrimState m) e
v
          Bool -> ST (PrimState m) Bool
forall a. a -> ST (PrimState m) a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True
        go !Int
l !e
vl !Int
r = do
          !e
vmid <- v (PrimState (ST (PrimState m))) e -> Int -> ST (PrimState m) e
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) e
v (PrimState (ST (PrimState m))) e
v Int
mid
          if e
vk e -> e -> Bool
`lt` e
vmid
            then Int -> e -> Int -> ST (PrimState m) Bool
go Int
mid e
vmid Int
r
            else Int -> e -> Int -> ST (PrimState m) Bool
go Int
l e
vl Int
mid
          where
            !mid :: Int
mid = Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftR` Int
1
  

-- $setup
-- >>> import Prelude ((*))