{-# 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,

  -- ** 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(..)
  , return, otherwise, flip, const, seq, min, max, not, pure
  , (>>=), (+), (-), (<), (<=), (>=), (==), (/=), (.), ($), (=<<), (>>), (<$>) )

#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 forall a. Ord a => a -> a -> Bool
< forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v = do
                     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
                     forall (m :: * -> *) a. Monad m => a -> m a
return v (PrimState m) a
v
  | Bool
otherwise    = do
                     v (PrimState m) a
v' <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> m (v (PrimState m) a)
enlarge v (PrimState m) a
v
                     forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Internal Int
i (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v') forall a b. (a -> b) -> a -> b
$ 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
                     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 forall a. Eq a => a -> a -> Bool
/= Int
0    = do
                  let i' :: Int
i' = Int
iforall a. Num a => a -> a -> a
-Int
1
                  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
                  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) <- 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
jforall a. Num a => a -> a -> a
-Int
1
                  forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Internal Int
i' (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v') forall a b. (a -> b) -> a -> b
$ 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
                  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 seq :: forall a b. a -> b -> b
`seq` Int
n seq :: forall a b. a -> b -> b
`seq` 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 = 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 forall a. Ord a => a -> a -> Bool
< Int
n     = do a
x <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i
                           forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just (a
x, Int
iforall a. Num a => a -> a -> a
+Int
1)
          | Bool
otherwise = forall (m :: * -> *) a. Monad m => a -> m a
return 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 seq :: forall a b. a -> b -> b
`seq` do
                     Int
n' <- 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
                     forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ 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
                forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Internal Int
i (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v) forall a b. (a -> b) -> a -> b
$ 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
                forall (m :: * -> *) a. Monad m => a -> m a
return (Int
iforall 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 = 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 (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 seq :: forall a b. a -> b -> b
`seq` Int
n seq :: forall a b. a -> b -> b
`seq` 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 = 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 forall a. Ord a => a -> a -> Bool
>= Int
0    = do a
x <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
j
                           forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just (a
x,Int
j)
          | Bool
otherwise = forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
      where
        j :: Int
j = Int
iforall 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 seq :: forall a b. a -> b -> b
`seq` do
                      Int
i <- 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
                      forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
i (Int
nforall a. Num a => a -> a -> a
-Int
i) v (PrimState m) a
v
  where
    n :: Int
n = 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
                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
                forall (m :: * -> *) a. Monad m => a -> m a
return Int
j
      where
        j :: Int
j = Int
iforall 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 = 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 (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 = forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
munstream (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 (forall (m :: * -> *) (v :: * -> *) a. Bundle m v a -> Size
MBundle.size MBundle m u a
s) of
               Just Int
n  -> 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 -> 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 <- forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Internal Int
n forall a b. (a -> b) -> a -> b
$ 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
                       forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Internal Int
i Int
n forall a b. (a -> b) -> a -> b
$ 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
                       forall (m :: * -> *) a. Monad m => a -> m a
return (Int
iforall a. Num a => a -> a -> a
+Int
1)
      Int
n' <- 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
      forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n' Int
n
             forall a b. (a -> b) -> a -> b
$ 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 <- 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) <- forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle m v b -> m a
MBundle.foldM 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
      forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v')
             forall a b. (a -> b) -> a -> b
$ 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' <- 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
                    forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) a
v',Int
iforall 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 = forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
MBundle m v a -> m (Mutable v (PrimState m) a)
vmunstream (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 (forall (m :: * -> *) (v :: * -> *) a. Bundle m v a -> Size
MBundle.size MBundle m v a
s) of
               Just Int
n  -> 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 -> 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 <- forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Internal Int
n forall a b. (a -> b) -> a -> b
$ 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) =
            forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
i Int
m (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length Mutable v (PrimState m) a
v) forall a b. (a -> b) -> a -> b
$ do
              forall (m :: * -> *).
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m ()
f (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)
              forall (m :: * -> *) a. Monad m => a -> m a
return (Int
iforall a. Num a => a -> a -> a
+Int
m)

      Int
n' <- 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 (forall (m :: * -> *) (v :: * -> *) a.
Bundle m v a -> Stream m (Chunk v a)
MBundle.chunks MBundle m v a
s)
      forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n' Int
n
             forall a b. (a -> b) -> a -> b
$ 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 <- 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) <- forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m a) -> a -> Stream m b -> m a
Stream.foldlM 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) (forall (m :: * -> *) (v :: * -> *) a.
Bundle m v a -> Stream m (Chunk v a)
MBundle.chunks MBundle m v a
s)
      forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length Mutable v (PrimState m) a
v')
             forall a b. (a -> b) -> a -> b
$ 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
iforall a. Num a => a -> a -> a
+Int
n
          Mutable v (PrimState m) a
v' <- if forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
basicLength Mutable v (PrimState m) a
v forall a. Ord a => a -> a -> Bool
< Int
j
                  then 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 (forall a b. (a -> b) -> a -> b
delay_inline forall a. Ord a => a -> a -> a
max (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
enlarge_delta Mutable v (PrimState m) a
v) (Int
j forall a. Num a => a -> a -> a
- forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
basicLength Mutable v (PrimState m) a
v))
                  else forall (m :: * -> *) a. Monad m => a -> m a
return Mutable v (PrimState m) a
v
          forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
i Int
n (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length Mutable v (PrimState m) a
v') forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *).
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m ()
f (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')
          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 = forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
munstreamR (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 (forall (m :: * -> *) (v :: * -> *) a. Bundle m v a -> Size
MBundle.size MBundle m u a
s) of
               Just Int
n  -> 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 -> 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 <- forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Internal Int
n forall a b. (a -> b) -> a -> b
$ 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
iforall a. Num a => a -> a -> a
-Int
1
                      forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Internal Int
i' Int
n
                        forall a b. (a -> b) -> a -> b
$ 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
                      forall (m :: * -> *) a. Monad m => a -> m a
return Int
i'
      Int
i <- 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
      forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
i (Int
nforall a. Num a => a -> a -> a
-Int
i) Int
n
             forall a b. (a -> b) -> a -> b
$ forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
i (Int
nforall 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 <- 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) <- forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> b -> m a) -> a -> Bundle m v b -> m a
MBundle.foldM 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 = forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v'
      forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
i (Int
nforall a. Num a => a -> a -> a
-Int
i) Int
n
             forall a b. (a -> b) -> a -> b
$ forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
i (Int
nforall 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 = 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 = 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 = forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v 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 = forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Bounds Int
i Int
n (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v) forall a b. (a -> b) -> a -> b
$ 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 = forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 (forall a. Ord a => a -> a -> a
min (forall a. Ord a => a -> a -> a
max Int
n Int
0) (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 = forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice (forall a. Ord a => a -> a -> a
min Int
m Int
n') (forall a. Ord a => a -> a -> a
max Int
0 (Int
m forall a. Num a => a -> a -> a
- Int
n')) v s a
v
  where
    n' :: Int
n' = forall a. Ord a => a -> a -> a
max Int
n Int
0
    m :: Int
m  = 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 = ( forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 Int
m v s a
v
              , forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
m (forall a. Ord a => a -> a -> a
max Int
0 (Int
len forall a. Num a => a -> a -> a
- Int
n')) v s a
v
              )
    where
      m :: Int
m   = forall a. Ord a => a -> a -> a
min Int
n' Int
len
      n' :: Int
n'  = forall a. Ord a => a -> a -> a
max Int
n Int
0
      len :: Int
len = 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 = forall (v :: * -> * -> *) a s.
(HasCallStack, MVector v a) =>
Int -> Int -> v s a -> v s a
slice Int
0 (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v 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 = forall (v :: * -> * -> *) a s.
(HasCallStack, MVector v a) =>
Int -> Int -> v s a -> v s a
slice Int
1 (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v 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 #-}
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 = forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Unsafe Int
i Int
n (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v)
                  forall a b. (a -> b) -> a -> b
$ 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 = forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
0 (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v 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 = forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
1 (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v 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 = 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 = forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
n (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v s a
v 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 = 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 = forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Bounds Int
n forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim
      forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
n forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \v (PrimState m) a
v -> forall (v :: * -> * -> *) a s. MVector v a => v s a -> ST s ()
basicInitialize v (PrimState m) a
v forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> 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 = forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Unsafe Int
n forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim forall a b. (a -> b) -> a -> b
$ 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 = forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim forall a b. (a -> b) -> a -> b
$ forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> a -> ST s (v s a)
basicUnsafeReplicate (forall a b. (a -> b) -> a -> b
delay_inline 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 = forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
munstream (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 = forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> (Int -> m a) -> m (v (PrimState m) a)
generateM Int
n (forall (m :: * -> *) a. Monad m => a -> m a
return 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 = forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
munstream (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' <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
            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
            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 = forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Bounds Int
by
          forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim
          forall a b. (a -> b) -> a -> b
$ do v (PrimState m) a
vnew <- 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
by
               forall (v :: * -> * -> *) a s. MVector v a => v s a -> ST s ()
basicInitialize forall a b. (a -> b) -> a -> b
$ forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
basicUnsafeSlice (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v) Int
by v (PrimState m) a
vnew
               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 = forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Bounds Int
by
               forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim
               forall a b. (a -> b) -> a -> b
$ do v (PrimState m) a
vnew <- 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
                    forall (v :: * -> * -> *) a s. MVector v a => v s a -> ST s ()
basicInitialize forall a b. (a -> b) -> a -> b
$ 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
                    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 = forall a. Ord a => a -> a -> a
max (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 = forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim forall a b. (a -> b) -> a -> b
$ do
  v (PrimState m) a
vnew <- 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
by
  forall (v :: * -> * -> *) a s. MVector v a => v s a -> ST s ()
basicInitialize forall a b. (a -> b) -> a -> b
$ forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
basicUnsafeSlice (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v) Int
by v (PrimState m) a
vnew
  forall (m :: * -> *) a. Monad m => a -> m a
return v (PrimState m) a
vnew
  where
    by :: Int
by = 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 = forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim forall a b. (a -> b) -> a -> b
$ do
                   v (PrimState m) a
v' <- 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
                   forall (v :: * -> * -> *) a s. MVector v a => v s a -> ST s ()
basicInitialize forall a b. (a -> b) -> a -> b
$ 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'
                   forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) a
v', Int
by)
  where
    by :: Int
by = 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 = forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Unsafe Int
n
               forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim
               forall a b. (a -> b) -> a -> b
$ 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 = forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Unsafe Int
by forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim forall a b. (a -> b) -> a -> b
$ do
                         let n :: Int
n = forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v
                         v (PrimState m) a
v' <- forall (v :: * -> * -> *) a s. MVector v a => Int -> ST s (v s a)
basicUnsafeNew (Int
byforall a. Num a => a -> a -> a
+Int
n)
                         forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> v s a -> ST s ()
basicUnsafeCopy (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
                         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 = forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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.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 = forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
i (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
         forall a b. (a -> b) -> a -> b
$ 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.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` (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v) = forall a. a -> Maybe a
Just forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> 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              = forall (f :: * -> *) a. Applicative f => a -> f a
pure 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 = forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
i (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
            forall a b. (a -> b) -> a -> b
$ 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 = forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
i (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
             forall a b. (a -> b) -> a -> b
$ 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 = forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
i (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
              forall a b. (a -> b) -> a -> b
$ 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 = forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
i (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
           forall a b. (a -> b) -> a -> b
$ forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
j (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
           forall a b. (a -> b) -> a -> b
$ 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 = forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
i (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v) forall a b. (a -> b) -> a -> b
$ 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 #-}
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 = forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
i (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
               forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim
               forall a b. (a -> b) -> a -> b
$ 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 #-}
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 = forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
i (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
                  forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim
                  forall a b. (a -> b) -> a -> b
$ 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 #-}
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 = forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
i (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
                   forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim
                   forall a b. (a -> b) -> a -> b
$ forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> Int -> ST s a
basicUnsafeRead v (PrimState m) a
v Int
i forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \a
x ->
                     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 #-}
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 = forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
i (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
                    forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> Int -> a -> ST s ()
basicUnsafeWrite v (PrimState m) a
v Int
i forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< a -> m a
f forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (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 = forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
i (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
                 forall a b. (a -> b) -> a -> b
$ forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
j (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v)
                 forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim forall a b. (a -> b) -> a -> b
$ do
                     a
x <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i
                     a
y <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
j
                     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
y
                     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

-- | 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 = forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
i (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v) forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim forall a b. (a -> b) -> a -> b
$ do
                         a
y <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i
                         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
                         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 forall a. Ord a => a -> a -> Bool
>= Int
n    = forall (m :: * -> *) a. Monad m => a -> m a
return ()
           | Bool
otherwise = Int -> m b
f Int
i forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Int -> m ()
loop (Int
i forall a. Num a => a -> a -> a
+ Int
1)
    n :: Int
n = 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 = forall (m :: * -> *) (v :: * -> * -> *) a b.
(Monad m, MVector v a) =>
v (PrimState m) a -> (Int -> m b) -> m ()
forI_ v (PrimState m) a
v forall a b. (a -> b) -> a -> b
$ \Int
i -> a -> m b
f forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< 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 = forall (m :: * -> *) (v :: * -> * -> *) a b.
(Monad m, MVector v a) =>
v (PrimState m) a -> (Int -> m b) -> m ()
forI_ v (PrimState m) a
v forall a b. (a -> b) -> a -> b
$ \Int
i -> Int -> a -> m b
f Int
i forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< 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_ = forall a b c. (a -> b -> c) -> b -> a -> c
flip 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_ = forall a b c. (a -> b -> c) -> b -> a -> c
flip 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 = 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 = 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 = forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim forall a b. (a -> b) -> a -> 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 -> forall (m :: * -> *) a. Monad m => a -> m a
return 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

-- | /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 = forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim forall a b. (a -> b) -> a -> 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 -> forall (m :: * -> *) a. Monad m => a -> m a
return 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

-- | /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 = forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(Int -> a -> b -> b) -> b -> v (PrimState m) a -> m b
ifoldr (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 = forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(Int -> a -> b -> b) -> b -> v (PrimState m) a -> m b
ifoldr' (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 = forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim forall a b. (a -> b) -> a -> 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 -> forall (m :: * -> *) a. Monad m => a -> m a
return 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

-- | /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 = forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim forall a b. (a -> b) -> a -> 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 -> forall (m :: * -> *) a. Monad m => a -> m a
return 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

-- | /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 = 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 = 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 forall a. Ord a => a -> a -> Bool
>= Int
n    = forall (m :: * -> *) a. Monad m => a -> m a
return b
b
             | Bool
otherwise = do a
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 forall a. Num a => a -> a -> a
+ Int
1) 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 = 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 forall a. Ord a => a -> a -> Bool
>= Int
n    = forall (m :: * -> *) a. Monad m => a -> m a
return b
b
              | Bool
otherwise = do a
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 forall a. Num a => a -> a -> a
+ Int
1) 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 = 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 = forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(Int -> a -> b -> m b) -> b -> v (PrimState m) a -> m b
ifoldrM (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 = forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(Int -> a -> b -> m b) -> b -> v (PrimState m) a -> m b
ifoldrM' (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
nforall a. Num a => a -> a -> a
-Int
1) b
b0
  where
    loop :: Int -> b -> m b
loop Int
i b
b | Int
i forall a. Ord a => a -> a -> Bool
< Int
0     = forall (m :: * -> *) a. Monad m => a -> m a
return b
b
             | Bool
otherwise = do a
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 forall a. Num a => a -> a -> a
- Int
1) 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 = 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
nforall a. Num a => a -> a -> a
-Int
1) b
b0
  where
    loop :: Int -> b -> m b
loop Int
i !b
b | Int
i forall a. Ord a => a -> a -> Bool
< Int
0     = forall (m :: * -> *) a. Monad m => a -> m a
return b
b
              | Bool
otherwise = do a
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 forall a. Num a => a -> a -> a
- Int
1) 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 = 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 = forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. HasCallStack => Checks -> String -> Bool -> a -> a
check Checks
Bounds String
"overlapping vectors" (Bool -> Bool
not (v (PrimState m) a
dst forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> v s a -> Bool
`overlaps` v (PrimState m) a
src))
             forall a b. (a -> b) -> a -> b
$ forall a. HasCallStack => Checks -> String -> Bool -> a -> a
check Checks
Bounds String
"length mismatch" (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
dst forall a. Eq a => a -> a -> Bool
== forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
src)
             forall a b. (a -> b) -> a -> b
$ 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 = forall a. HasCallStack => Checks -> String -> Bool -> a -> a
check Checks
Bounds String
"length mismatch" (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
dst forall a. Eq a => a -> a -> Bool
== forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
src)
             forall a b. (a -> b) -> a -> b
$ 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 = forall a. HasCallStack => Checks -> String -> Bool -> a -> a
check Checks
Unsafe String
"length mismatch" (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
dst forall a. Eq a => a -> a -> Bool
== forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
src)
                   forall a b. (a -> b) -> a -> b
$ forall a. HasCallStack => Checks -> String -> Bool -> a -> a
check Checks
Unsafe String
"overlapping vectors" (Bool -> Bool
not (v (PrimState m) a
dst forall (v :: * -> * -> *) a s.
MVector v a =>
v s a -> v s a -> Bool
`overlaps` v (PrimState m) a
src))
                   forall a b. (a -> b) -> a -> b
$ v (PrimState m) a
dst seq :: forall a b. a -> b -> b
`seq` v (PrimState m) a
src seq :: forall a b. a -> b -> b
`seq` forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (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 = forall a. HasCallStack => Checks -> String -> Bool -> a -> a
check Checks
Unsafe String
"length mismatch" (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
dst forall a. Eq a => a -> a -> Bool
== forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
src)
                   forall a b. (a -> b) -> a -> b
$ v (PrimState m) a
dst seq :: forall a b. a -> b -> b
`seq` v (PrimState m) a
src seq :: forall a b. a -> b -> b
`seq` forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (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 = forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> m b) -> Bundle v a -> m ()
Bundle.mapM_ HasCallStack => (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 <- forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
i Int
n forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i
                  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 = 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 = forall (m :: * -> *) a b (v :: * -> *).
Monad m =>
(a -> m b) -> Bundle v a -> m ()
Bundle.mapM_ HasCallStack => (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) = forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Bounds Int
i Int
n forall a b. (a -> b) -> a -> b
$ 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 = 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 = 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 <- forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
i Int
n forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i
                  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 = 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 = 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) = forall a. HasCallStack => Checks -> Int -> Int -> a -> a
checkIndex Checks
Unsafe Int
i Int
n forall a b. (a -> b) -> a -> b
$ 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 = 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 (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v forall a. Num a => a -> a -> a
- Int
1)
  where
    reverse_loop :: Int -> Int -> m ()
reverse_loop Int
i Int
j | Int
i forall a. Ord a => a -> a -> Bool
< Int
j = do
                                 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 forall a. Num a => a -> a -> a
+ Int
1) (Int
j forall a. Num a => a -> a -> a
- Int
1)
    reverse_loop Int
_ Int
_ = 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 (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 forall a. Eq a => a -> a -> Bool
== Int
j    = forall (m :: * -> *) a. Monad m => a -> m a
return Int
i
      | Bool
otherwise = do
                      a
x <- 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
iforall a. Num a => a -> a -> a
+Int
1) Int
j
                        else Int -> Int -> m Int
from_right Int
i (Int
jforall 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 forall a. Eq a => a -> a -> Bool
== Int
j    = forall (m :: * -> *) a. Monad m => a -> m a
return Int
i
      | Bool
otherwise = do
                      a
x <- 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 <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) a
v Int
i
                               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
                               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
iforall a. Num a => a -> a -> a
+Int
1) Int
j
                        else Int -> Int -> m Int
from_right Int
i (Int
jforall 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 (forall (v :: * -> *) a. Bundle v a -> Size
Bundle.size Bundle u a
s) of
      Just Int
n  -> 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 -> 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 <- forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Internal Int
n forall a b. (a -> b) -> a -> b
$ 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
                            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
                            forall (m :: * -> *) a. Monad m => a -> m a
return (Int
iforall a. Num a => a -> a -> a
+Int
1, Int
j)
            | Bool
otherwise = do
                            forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
unsafeWrite v (PrimState m) a
v (Int
jforall a. Num a => a -> a -> a
-Int
1) a
x
                            forall (m :: * -> *) a. Monad m => a -> m a
return (Int
i, Int
jforall a. Num a => a -> a -> a
-Int
1)

      (Int
i,Int
j) <- 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
      forall (m :: * -> *) a. Monad m => a -> m a
return (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, forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
j (Int
nforall 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 (forall (v :: * -> *) a. Bundle v a -> Size
Bundle.size Bundle u a
s) of
      Just Int
n  -> 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 -> 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 <- forall a. HasCallStack => Checks -> Int -> a -> a
checkLength Checks
Internal Int
n forall a b. (a -> b) -> a -> b
$ 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
                            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
                            forall (m :: * -> *) a. Monad m => a -> m a
return (Int
iforall a. Num a => a -> a -> a
+Int
1,Int
j)

            | Bool
otherwise = let j' :: Int
j' = Int
jforall a. Num a => a -> a -> a
-Int
1 in
                          do
                            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
                            forall (m :: * -> *) a. Monad m => a -> m a
return (Int
i,Int
j')

      (Int
i,Int
j) <- 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
      forall a. HasCallStack => Checks -> String -> Bool -> a -> a
check Checks
Internal String
"invalid indices" (Int
i forall a. Ord a => a -> a -> Bool
<= Int
j)
        forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. Monad m => a -> m a
return ()
      let l :: v (PrimState m) a
l = 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 = forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice Int
j (Int
nforall a. Num a => a -> a -> a
-Int
j) v (PrimState m) a
v
      forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> m ()
reverse v (PrimState m) a
r
      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 <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
0
      v (PrimState m) a
v2 <- 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) <- 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
      forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n1 (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v1')
        forall a b. (a -> b) -> a -> b
$ forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n2 (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) a
v2')
        forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. Monad m => a -> m a
return (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', 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' <- 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
                      forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) a
v1', Int
i1forall a. Num a => a -> a -> a
+Int
1, v (PrimState m) a
v2, Int
i2)
      | Bool
otherwise = do
                      v (PrimState m) a
v2' <- 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
                      forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) a
v1, Int
i1, v (PrimState m) a
v2', Int
i2forall 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 (forall (v :: * -> *) a. Bundle v a -> Size
Bundle.size Bundle u a
s) of
      Just Int
n  -> 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 -> 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 <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
n
      v (PrimState m) c
v2 <- 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
              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
              forall (m :: * -> *) a. Monad m => a -> m a
return (Int
i1forall a. Num a => a -> a -> a
+Int
1, Int
i2)
            Right c
c -> do
              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
              forall (m :: * -> *) a. Monad m => a -> m a
return (Int
i1, Int
i2forall a. Num a => a -> a -> a
+Int
1)
      (Int
n1, Int
n2) <- 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
      forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n1 (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) b
v1)
        forall a b. (a -> b) -> a -> b
$ forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n2 (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) c
v2)
        forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. Monad m => a -> m a
return (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, 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 <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
unsafeNew Int
0
      v (PrimState m) c
v2 <- 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) <- 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
      forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n1 (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) b
v1')
        forall a b. (a -> b) -> a -> b
$ forall a. HasCallStack => Checks -> Int -> Int -> Int -> a -> a
checkSlice Checks
Internal Int
0 Int
n2 (forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) c
v2')
        forall a b. (a -> b) -> a -> b
$ forall (m :: * -> *) a. Monad m => a -> m a
return (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', 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' <- 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
        forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) b
v1', Int
i1forall a. Num a => a -> a -> a
+Int
1, v (PrimState m) c
v2, Int
i2)
      Right c
c -> do
        v (PrimState m) c
v2' <- 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
        forall (m :: * -> *) a. Monad m => a -> m a
return (v (PrimState m) b
v1, Int
i1, v (PrimState m) c
v2', Int
i2forall a. Num a => a -> a -> a
+Int
1)

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

{-
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]
-}

-- | Compute the (lexicographically) next permutation of the given vector in-place.
-- Returns False when the input is the last permutation.
nextPermutation :: (PrimMonad m,Ord e,MVector v e) => v (PrimState m) e -> m Bool
nextPermutation :: forall (m :: * -> *) e (v :: * -> * -> *).
(PrimMonad m, Ord e, MVector v e) =>
v (PrimState m) e -> m Bool
nextPermutation v (PrimState m) e
v
    | Int
dim forall a. Ord a => a -> a -> Bool
< Int
2 = forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
    | Bool
otherwise = do
        e
val <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) e
v Int
0
        (Int
k,Int
l) <- e -> Int -> Int -> e -> Int -> m (Int, Int)
loop e
val (-Int
1) Int
0 e
val Int
1
        if Int
k forall a. Ord a => a -> a -> Bool
< Int
0
         then forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
         else forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> Int -> m ()
unsafeSwap v (PrimState m) e
v Int
k Int
l forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>>
              forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> m ()
reverse (forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
unsafeSlice (Int
kforall a. Num a => a -> a -> a
+Int
1) (Int
dimforall a. Num a => a -> a -> a
-Int
kforall a. Num a => a -> a -> a
-Int
1) v (PrimState m) e
v) forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>>
              forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True
    where loop :: e -> Int -> Int -> e -> Int -> m (Int, Int)
loop !e
kval !Int
k !Int
l !e
prev !Int
i
              | Int
i forall a. Eq a => a -> a -> Bool
== Int
dim = forall (m :: * -> *) a. Monad m => a -> m a
return (Int
k,Int
l)
              | Bool
otherwise  = do
                  e
cur <- forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
unsafeRead v (PrimState m) e
v Int
i
                  -- TODO: make tuple unboxed
                  let (e
kval',Int
k') = if e
prev forall a. Ord a => a -> a -> Bool
< e
cur then (e
prev,Int
iforall a. Num a => a -> a -> a
-Int
1) else (e
kval,Int
k)
                      l' :: Int
l' = if e
kval' forall a. Ord a => a -> a -> Bool
< e
cur then Int
i else Int
l
                  e -> Int -> Int -> e -> Int -> m (Int, Int)
loop e
kval' Int
k' Int
l' e
cur (Int
iforall a. Num a => a -> a -> a
+Int
1)
          dim :: Int
dim = forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
length v (PrimState m) e
v

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