{-# LANGUAGE CPP, DeriveDataTypeable, MultiParamTypeClasses, FlexibleInstances, BangPatterns, TypeFamilies #-}

-- |
-- Module      : Data.Vector.Mutable
-- Copyright   : (c) Roman Leshchinskiy 2008-2010
-- License     : BSD-style
--
-- Maintainer  : Roman Leshchinskiy <rl@cse.unsw.edu.au>
-- Stability   : experimental
-- Portability : non-portable
--
-- Mutable boxed vectors.
--

module Data.Vector.Mutable (
  -- * Mutable boxed vectors
  MVector(..), IOVector, STVector,

  -- * 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, clone,

  -- ** Growing
  grow, unsafeGrow,

  -- ** Restricting memory usage
  clear,

  -- * Accessing individual elements
  read, write, modify, swap,
  unsafeRead, unsafeWrite, unsafeModify, unsafeSwap,

  -- * Modifying vectors
  nextPermutation,

  -- ** Filling and copying

  set, copy, move, unsafeCopy, unsafeMove,

  -- ** Arrays
  fromMutableArray, toMutableArray
) where

import           Control.Monad (when, liftM)
import qualified Data.Vector.Generic.Mutable as G
import           Data.Primitive.Array
import           Control.Monad.Primitive

import Prelude hiding ( length, null, replicate, reverse, read,
                        take, drop, splitAt, init, tail )

import Data.Typeable ( Typeable )

#include "vector.h"



-- | Mutable boxed vectors keyed on the monad they live in ('IO' or @'ST' s@).
data MVector s a = MVector {-# UNPACK #-} !Int                -- ^ Offset in underlying array
                           {-# UNPACK #-} !Int                -- ^ Size of slice
                           {-# UNPACK #-} !(MutableArray s a) -- ^ Underlying array
        deriving ( Typeable )

type IOVector = MVector RealWorld
type STVector s = MVector s

-- NOTE: This seems unsafe, see http://trac.haskell.org/vector/ticket/54
{-
instance NFData a => NFData (MVector s a) where
    rnf (MVector i n arr) = unsafeInlineST $ force i
        where
          force !ix | ix < n    = do x <- readArray arr ix
                                     rnf x `seq` force (ix+1)
                    | otherwise = return ()
-}

instance G.MVector MVector a where
  {-# INLINE basicLength #-}
  basicLength :: MVector s a -> Int
basicLength (MVector Int
_ Int
n MutableArray s a
_) = Int
n

  {-# INLINE basicUnsafeSlice #-}
  basicUnsafeSlice :: Int -> Int -> MVector s a -> MVector s a
basicUnsafeSlice Int
j Int
m (MVector Int
i Int
_ MutableArray s a
arr) = Int -> Int -> MutableArray s a -> MVector s a
forall s a. Int -> Int -> MutableArray s a -> MVector s a
MVector (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
j) Int
m MutableArray s a
arr

  {-# INLINE basicOverlaps #-}
  basicOverlaps :: MVector s a -> MVector s a -> Bool
basicOverlaps (MVector Int
i Int
m MutableArray s a
arr1) (MVector Int
j Int
n MutableArray s a
arr2)
    = MutableArray s a -> MutableArray s a -> Bool
forall s a. MutableArray s a -> MutableArray s a -> Bool
sameMutableArray MutableArray s a
arr1 MutableArray s a
arr2
      Bool -> Bool -> Bool
&& (Int -> Int -> Int -> Bool
forall a. Ord a => a -> a -> a -> Bool
between Int
i Int
j (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
n) Bool -> Bool -> Bool
|| Int -> Int -> Int -> Bool
forall a. Ord a => a -> a -> a -> Bool
between Int
j Int
i (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
m))
    where
      between :: a -> a -> a -> Bool
between a
x a
y a
z = a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
y Bool -> Bool -> Bool
&& a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
z

  {-# INLINE basicUnsafeNew #-}
  basicUnsafeNew :: Int -> m (MVector (PrimState m) a)
basicUnsafeNew Int
n
    = do
        MutableArray (PrimState m) a
arr <- Int -> a -> m (MutableArray (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (MutableArray (PrimState m) a)
newArray Int
n a
forall a. a
uninitialised
        MVector (PrimState m) a -> m (MVector (PrimState m) a)
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
-> Int -> MutableArray (PrimState m) a -> MVector (PrimState m) a
forall s a. Int -> Int -> MutableArray s a -> MVector s a
MVector Int
0 Int
n MutableArray (PrimState m) a
arr)

  {-# INLINE basicInitialize #-}
  -- initialization is unnecessary for boxed vectors
  basicInitialize :: MVector (PrimState m) a -> m ()
basicInitialize MVector (PrimState m) a
_ = () -> m ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()

  {-# INLINE basicUnsafeReplicate #-}
  basicUnsafeReplicate :: Int -> a -> m (MVector (PrimState m) a)
basicUnsafeReplicate Int
n a
x
    = do
        MutableArray (PrimState m) a
arr <- Int -> a -> m (MutableArray (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (MutableArray (PrimState m) a)
newArray Int
n a
x
        MVector (PrimState m) a -> m (MVector (PrimState m) a)
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
-> Int -> MutableArray (PrimState m) a -> MVector (PrimState m) a
forall s a. Int -> Int -> MutableArray s a -> MVector s a
MVector Int
0 Int
n MutableArray (PrimState m) a
arr)

  {-# INLINE basicUnsafeRead #-}
  basicUnsafeRead :: MVector (PrimState m) a -> Int -> m a
basicUnsafeRead (MVector Int
i Int
_ MutableArray (PrimState m) a
arr) Int
j = MutableArray (PrimState m) a -> Int -> m a
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> m a
readArray MutableArray (PrimState m) a
arr (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
j)

  {-# INLINE basicUnsafeWrite #-}
  basicUnsafeWrite :: MVector (PrimState m) a -> Int -> a -> m ()
basicUnsafeWrite (MVector Int
i Int
_ MutableArray (PrimState m) a
arr) Int
j a
x = MutableArray (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> a -> m ()
writeArray MutableArray (PrimState m) a
arr (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
j) a
x

  {-# INLINE basicUnsafeCopy #-}
  basicUnsafeCopy :: MVector (PrimState m) a -> MVector (PrimState m) a -> m ()
basicUnsafeCopy (MVector Int
i Int
n MutableArray (PrimState m) a
dst) (MVector Int
j Int
_ MutableArray (PrimState m) a
src)
    = MutableArray (PrimState m) a
-> Int -> MutableArray (PrimState m) a -> Int -> Int -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a
-> Int -> MutableArray (PrimState m) a -> Int -> Int -> m ()
copyMutableArray MutableArray (PrimState m) a
dst Int
i MutableArray (PrimState m) a
src Int
j Int
n

  basicUnsafeMove :: MVector (PrimState m) a -> MVector (PrimState m) a -> m ()
basicUnsafeMove dst :: MVector (PrimState m) a
dst@(MVector Int
iDst Int
n MutableArray (PrimState m) a
arrDst) src :: MVector (PrimState m) a
src@(MVector Int
iSrc Int
_ MutableArray (PrimState m) a
arrSrc)
    = case Int
n of
        Int
0 -> () -> m ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
        Int
1 -> MutableArray (PrimState m) a -> Int -> m a
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> m a
readArray MutableArray (PrimState m) a
arrSrc Int
iSrc m a -> (a -> m ()) -> m ()
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MutableArray (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> a -> m ()
writeArray MutableArray (PrimState m) a
arrDst Int
iDst
        Int
2 -> do
               a
x <- MutableArray (PrimState m) a -> Int -> m a
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> m a
readArray MutableArray (PrimState m) a
arrSrc Int
iSrc
               a
y <- MutableArray (PrimState m) a -> Int -> m a
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> m a
readArray MutableArray (PrimState m) a
arrSrc (Int
iSrc Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
               MutableArray (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> a -> m ()
writeArray MutableArray (PrimState m) a
arrDst Int
iDst a
x
               MutableArray (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> a -> m ()
writeArray MutableArray (PrimState m) a
arrDst (Int
iDst Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) a
y
        Int
_
          | MVector (PrimState m) a -> MVector (PrimState m) a -> Bool
forall s a. MVector s a -> MVector s a -> Bool
overlaps MVector (PrimState m) a
dst MVector (PrimState m) a
src
             -> case Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Int
iDst Int
iSrc of
                  Ordering
LT -> MutableArray (PrimState m) a -> Int -> Int -> Int -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> Int -> Int -> m ()
moveBackwards MutableArray (PrimState m) a
arrDst Int
iDst Int
iSrc Int
n
                  Ordering
EQ -> () -> m ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
                  Ordering
GT | (Int
iDst Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
iSrc) Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
2 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n
                        -> MutableArray (PrimState m) a -> Int -> Int -> Int -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> Int -> Int -> m ()
moveForwardsLargeOverlap MutableArray (PrimState m) a
arrDst Int
iDst Int
iSrc Int
n
                     | Bool
otherwise
                        -> MutableArray (PrimState m) a -> Int -> Int -> Int -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> Int -> Int -> m ()
moveForwardsSmallOverlap MutableArray (PrimState m) a
arrDst Int
iDst Int
iSrc Int
n
          | Bool
otherwise -> MVector (PrimState m) a -> MVector (PrimState m) a -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> v (PrimState m) a -> m ()
G.basicUnsafeCopy MVector (PrimState m) a
dst MVector (PrimState m) a
src

  {-# INLINE basicClear #-}
  basicClear :: MVector (PrimState m) a -> m ()
basicClear MVector (PrimState m) a
v = MVector (PrimState m) a -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> a -> m ()
G.set MVector (PrimState m) a
v a
forall a. a
uninitialised

{-# INLINE moveBackwards #-}
moveBackwards :: PrimMonad m => MutableArray (PrimState m) a -> Int -> Int -> Int -> m ()
moveBackwards :: MutableArray (PrimState m) a -> Int -> Int -> Int -> m ()
moveBackwards !MutableArray (PrimState m) a
arr !Int
dstOff !Int
srcOff !Int
len =
  INTERNAL_CHECK(check) "moveBackwards" "not a backwards move" (dstOff < srcOff)
  (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ Int -> (Int -> m ()) -> m ()
forall (m :: * -> *) a. Monad m => Int -> (Int -> m a) -> m ()
loopM Int
len ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \ Int
i -> MutableArray (PrimState m) a -> Int -> m a
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> m a
readArray MutableArray (PrimState m) a
arr (Int
srcOff Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i) m a -> (a -> m ()) -> m ()
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MutableArray (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> a -> m ()
writeArray MutableArray (PrimState m) a
arr (Int
dstOff Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i)

{-# INLINE moveForwardsSmallOverlap #-}
-- Performs a move when dstOff > srcOff, optimized for when the overlap of the intervals is small.
moveForwardsSmallOverlap :: PrimMonad m => MutableArray (PrimState m) a -> Int -> Int -> Int -> m ()
moveForwardsSmallOverlap :: MutableArray (PrimState m) a -> Int -> Int -> Int -> m ()
moveForwardsSmallOverlap !MutableArray (PrimState m) a
arr !Int
dstOff !Int
srcOff !Int
len =
  INTERNAL_CHECK(check) "moveForwardsSmallOverlap" "not a forward move" (dstOff > srcOff)
  (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
      MutableArray (PrimState m) a
tmp <- Int -> a -> m (MutableArray (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (MutableArray (PrimState m) a)
newArray Int
overlap a
forall a. a
uninitialised
      Int -> (Int -> m ()) -> m ()
forall (m :: * -> *) a. Monad m => Int -> (Int -> m a) -> m ()
loopM Int
overlap ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \ Int
i -> MutableArray (PrimState m) a -> Int -> m a
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> m a
readArray MutableArray (PrimState m) a
arr (Int
dstOff Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i) m a -> (a -> m ()) -> m ()
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MutableArray (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> a -> m ()
writeArray MutableArray (PrimState m) a
tmp Int
i
      Int -> (Int -> m ()) -> m ()
forall (m :: * -> *) a. Monad m => Int -> (Int -> m a) -> m ()
loopM Int
nonOverlap ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \ Int
i -> MutableArray (PrimState m) a -> Int -> m a
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> m a
readArray MutableArray (PrimState m) a
arr (Int
srcOff Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i) m a -> (a -> m ()) -> m ()
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MutableArray (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> a -> m ()
writeArray MutableArray (PrimState m) a
arr (Int
dstOff Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i)
      Int -> (Int -> m ()) -> m ()
forall (m :: * -> *) a. Monad m => Int -> (Int -> m a) -> m ()
loopM Int
overlap ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \ Int
i -> MutableArray (PrimState m) a -> Int -> m a
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> m a
readArray MutableArray (PrimState m) a
tmp Int
i m a -> (a -> m ()) -> m ()
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MutableArray (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> a -> m ()
writeArray MutableArray (PrimState m) a
arr (Int
dstOff Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
nonOverlap Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i)
  where nonOverlap :: Int
nonOverlap = Int
dstOff Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
srcOff; overlap :: Int
overlap = Int
len Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
nonOverlap

-- Performs a move when dstOff > srcOff, optimized for when the overlap of the intervals is large.
moveForwardsLargeOverlap :: PrimMonad m => MutableArray (PrimState m) a -> Int -> Int -> Int -> m ()
moveForwardsLargeOverlap :: MutableArray (PrimState m) a -> Int -> Int -> Int -> m ()
moveForwardsLargeOverlap !MutableArray (PrimState m) a
arr !Int
dstOff !Int
srcOff !Int
len =
  INTERNAL_CHECK(check) "moveForwardsLargeOverlap" "not a forward move" (dstOff > srcOff)
  (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
      MutableArray (PrimState m) a
queue <- Int -> a -> m (MutableArray (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (MutableArray (PrimState m) a)
newArray Int
nonOverlap a
forall a. a
uninitialised
      Int -> (Int -> m ()) -> m ()
forall (m :: * -> *) a. Monad m => Int -> (Int -> m a) -> m ()
loopM Int
nonOverlap ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \ Int
i -> MutableArray (PrimState m) a -> Int -> m a
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> m a
readArray MutableArray (PrimState m) a
arr (Int
srcOff Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i) m a -> (a -> m ()) -> m ()
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MutableArray (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> a -> m ()
writeArray MutableArray (PrimState m) a
queue Int
i
      let mov :: Int -> Int -> m ()
mov !Int
i !Int
qTop = Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
dstOff Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
len) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
            a
x <- MutableArray (PrimState m) a -> Int -> m a
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> m a
readArray MutableArray (PrimState m) a
arr Int
i
            a
y <- MutableArray (PrimState m) a -> Int -> m a
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> m a
readArray MutableArray (PrimState m) a
queue Int
qTop
            MutableArray (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> a -> m ()
writeArray MutableArray (PrimState m) a
arr Int
i a
y
            MutableArray (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a -> Int -> a -> m ()
writeArray MutableArray (PrimState m) a
queue Int
qTop a
x
            Int -> Int -> m ()
mov (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (if Int
qTop Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
nonOverlap then Int
0 else Int
qTop Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
      Int -> Int -> m ()
mov Int
dstOff Int
0
  where nonOverlap :: Int
nonOverlap = Int
dstOff Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
srcOff

{-# INLINE loopM #-}
loopM :: Monad m => Int -> (Int -> m a) -> m ()
loopM :: Int -> (Int -> m a) -> m ()
loopM !Int
n Int -> m a
k = let
  go :: Int -> m ()
go Int
i = Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n) (Int -> m a
k Int
i m a -> m () -> m ()
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Int -> m ()
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1))
  in Int -> m ()
go Int
0

uninitialised :: a
uninitialised :: a
uninitialised = String -> a
forall a. HasCallStack => String -> a
error String
"Data.Vector.Mutable: uninitialised element. If you are trying to compact a vector, use the 'Data.Vector.force' function to remove uninitialised elements from the underlying array."

-- Length information
-- ------------------

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

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

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

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

take :: Int -> MVector s a -> MVector s a
{-# INLINE take #-}
take :: Int -> MVector s a -> MVector s a
take = Int -> MVector s a -> MVector s a
forall (v :: * -> * -> *) a s. MVector v a => Int -> v s a -> v s a
G.take

drop :: Int -> MVector s a -> MVector s a
{-# INLINE drop #-}
drop :: Int -> MVector s a -> MVector s a
drop = Int -> MVector s a -> MVector s a
forall (v :: * -> * -> *) a s. MVector v a => Int -> v s a -> v s a
G.drop

{-# INLINE splitAt #-}
splitAt :: Int -> MVector s a -> (MVector s a, MVector s a)
splitAt :: Int -> MVector s a -> (MVector s a, MVector s a)
splitAt = Int -> MVector s a -> (MVector s a, MVector s a)
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> v s a -> (v s a, v s a)
G.splitAt

init :: MVector s a -> MVector s a
{-# INLINE init #-}
init :: MVector s a -> MVector s a
init = MVector s a -> MVector s a
forall (v :: * -> * -> *) a s. MVector v a => v s a -> v s a
G.init

tail :: MVector s a -> MVector s a
{-# INLINE tail #-}
tail :: MVector s a -> MVector s a
tail = MVector s a -> MVector s a
forall (v :: * -> * -> *) a s. MVector v a => v s a -> v s a
G.tail

-- | Yield a part of the mutable vector without copying it. No bounds checks
-- are performed.
unsafeSlice :: Int  -- ^ starting index
            -> Int  -- ^ length of the slice
            -> MVector s a
            -> MVector s a
{-# INLINE unsafeSlice #-}
unsafeSlice :: Int -> Int -> MVector s a -> MVector s a
unsafeSlice = Int -> Int -> MVector s a -> MVector s a
forall (v :: * -> * -> *) a s.
MVector v a =>
Int -> Int -> v s a -> v s a
G.unsafeSlice

unsafeTake :: Int -> MVector s a -> MVector s a
{-# INLINE unsafeTake #-}
unsafeTake :: Int -> MVector s a -> MVector s a
unsafeTake = Int -> MVector s a -> MVector s a
forall (v :: * -> * -> *) a s. MVector v a => Int -> v s a -> v s a
G.unsafeTake

unsafeDrop :: Int -> MVector s a -> MVector s a
{-# INLINE unsafeDrop #-}
unsafeDrop :: Int -> MVector s a -> MVector s a
unsafeDrop = Int -> MVector s a -> MVector s a
forall (v :: * -> * -> *) a s. MVector v a => Int -> v s a -> v s a
G.unsafeDrop

unsafeInit :: MVector s a -> MVector s a
{-# INLINE unsafeInit #-}
unsafeInit :: MVector s a -> MVector s a
unsafeInit = MVector s a -> MVector s a
forall (v :: * -> * -> *) a s. MVector v a => v s a -> v s a
G.unsafeInit

unsafeTail :: MVector s a -> MVector s a
{-# INLINE unsafeTail #-}
unsafeTail :: MVector s a -> MVector s a
unsafeTail = MVector s a -> MVector s a
forall (v :: * -> * -> *) a s. MVector v a => v s a -> v s a
G.unsafeTail

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

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

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

-- | Create a mutable vector of the given length.
new :: PrimMonad m => Int -> m (MVector (PrimState m) a)
{-# INLINE new #-}
new :: Int -> m (MVector (PrimState m) a)
new = Int -> m (MVector (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
G.new

-- | Create a mutable vector of the given length. The vector elements
--   are set to bottom so accessing them will cause an exception.
--
-- @since 0.5
unsafeNew :: PrimMonad m => Int -> m (MVector (PrimState m) a)
{-# INLINE unsafeNew #-}
unsafeNew :: Int -> m (MVector (PrimState m) a)
unsafeNew = Int -> m (MVector (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
G.unsafeNew

-- | Create a mutable vector of the given length (0 if the length is negative)
-- and fill it with an initial value.
replicate :: PrimMonad m => Int -> a -> m (MVector (PrimState m) a)
{-# INLINE replicate #-}
replicate :: Int -> a -> m (MVector (PrimState m) a)
replicate = Int -> a -> m (MVector (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> a -> m (v (PrimState m) a)
G.replicate

-- | 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 => Int -> m a -> m (MVector (PrimState m) a)
{-# INLINE replicateM #-}
replicateM :: Int -> m a -> m (MVector (PrimState m) a)
replicateM = Int -> m a -> m (MVector (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
Int -> m a -> m (v (PrimState m) a)
G.replicateM

-- | Create a copy of a mutable vector.
clone :: PrimMonad m => MVector (PrimState m) a -> m (MVector (PrimState m) a)
{-# INLINE clone #-}
clone :: MVector (PrimState m) a -> m (MVector (PrimState m) a)
clone = MVector (PrimState m) a -> m (MVector (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> m (v (PrimState m) a)
G.clone

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

-- | Grow a boxed vector by the given number of elements. The number must be
-- non-negative. Same semantics as in `G.grow` for generic vector. It differs
-- from @grow@ functions for unpacked vectors, however, in that only pointers to
-- values are copied over, therefore values themselves will be shared between
-- two vectors. This is an important distinction to know about during memory
-- usage analysis and in case when values themselves are of a mutable type, eg.
-- `Data.IORef.IORef` or another mutable vector.
--
-- ====__Examples__
--
-- >>> import qualified Data.Vector as V
-- >>> import qualified Data.Vector.Mutable as MV
-- >>> mv <- V.thaw $ V.fromList ([10, 20, 30] :: [Integer])
-- >>> mv' <- MV.grow mv 2
--
-- The two extra elements at the end of the newly allocated vector will be
-- uninitialized and will result in an error if evaluated, so me must overwrite
-- them with new values first:
--
-- >>> MV.write mv' 3 999
-- >>> MV.write mv' 4 777
-- >>> V.unsafeFreeze mv'
-- [10,20,30,999,777]
--
-- It is important to note that the source mutable vector is not affected when
-- the newly allocated one is mutated.
--
-- >>> MV.write mv' 2 888
-- >>> V.unsafeFreeze mv'
-- [10,20,888,999,777]
-- >>> V.unsafeFreeze mv
-- [10,20,30]
--
-- @since 0.5
grow :: PrimMonad m
              => MVector (PrimState m) a -> Int -> m (MVector (PrimState m) a)
{-# INLINE grow #-}
grow :: MVector (PrimState m) a -> Int -> m (MVector (PrimState m) a)
grow = MVector (PrimState m) a -> Int -> m (MVector (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (v (PrimState m) a)
G.grow

-- | Grow a vector by the given number of elements. The number must be non-negative but
-- this is not checked. Same semantics as in `G.unsafeGrow` for generic vector.
--
-- @since 0.5
unsafeGrow :: PrimMonad m
               => MVector (PrimState m) a -> Int -> m (MVector (PrimState m) a)
{-# INLINE unsafeGrow #-}
unsafeGrow :: MVector (PrimState m) a -> Int -> m (MVector (PrimState m) a)
unsafeGrow = MVector (PrimState m) a -> Int -> m (MVector (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (v (PrimState m) a)
G.unsafeGrow

-- 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 (PrimState m) a -> m ()
{-# INLINE clear #-}
clear :: MVector (PrimState m) a -> m ()
clear = MVector (PrimState m) a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> m ()
G.clear

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

-- | Yield the element at the given position.
read :: PrimMonad m => MVector (PrimState m) a -> Int -> m a
{-# INLINE read #-}
read :: MVector (PrimState m) a -> Int -> m a
read = MVector (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
G.read

-- | Replace the element at the given position.
write :: PrimMonad m => MVector (PrimState m) a -> Int -> a -> m ()
{-# INLINE write #-}
write :: MVector (PrimState m) a -> Int -> a -> m ()
write = MVector (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
G.write

-- | Modify the element at the given position.
modify :: PrimMonad m => MVector (PrimState m) a -> (a -> a) -> Int -> m ()
{-# INLINE modify #-}
modify :: MVector (PrimState m) a -> (a -> a) -> Int -> m ()
modify = MVector (PrimState m) a -> (a -> a) -> Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
G.modify

-- | Swap the elements at the given positions.
swap :: PrimMonad m => MVector (PrimState m) a -> Int -> Int -> m ()
{-# INLINE swap #-}
swap :: MVector (PrimState m) a -> Int -> Int -> m ()
swap = MVector (PrimState m) a -> Int -> Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> Int -> m ()
G.swap


-- | Yield the element at the given position. No bounds checks are performed.
unsafeRead :: PrimMonad m => MVector (PrimState m) a -> Int -> m a
{-# INLINE unsafeRead #-}
unsafeRead :: MVector (PrimState m) a -> Int -> m a
unsafeRead = MVector (PrimState m) a -> Int -> m a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
G.unsafeRead

-- | Replace the element at the given position. No bounds checks are performed.
unsafeWrite :: PrimMonad m => MVector (PrimState m) a -> Int -> a -> m ()
{-# INLINE unsafeWrite #-}
unsafeWrite :: MVector (PrimState m) a -> Int -> a -> m ()
unsafeWrite = MVector (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
G.unsafeWrite

-- | Modify the element at the given position. No bounds checks are performed.
unsafeModify :: PrimMonad m => MVector (PrimState m) a -> (a -> a) -> Int -> m ()
{-# INLINE unsafeModify #-}
unsafeModify :: MVector (PrimState m) a -> (a -> a) -> Int -> m ()
unsafeModify = MVector (PrimState m) a -> (a -> a) -> Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
G.unsafeModify

-- | Swap the elements at the given positions. No bounds checks are performed.
unsafeSwap :: PrimMonad m => MVector (PrimState m) a -> Int -> Int -> m ()
{-# INLINE unsafeSwap #-}
unsafeSwap :: MVector (PrimState m) a -> Int -> Int -> m ()
unsafeSwap = MVector (PrimState m) a -> Int -> Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> Int -> m ()
G.unsafeSwap

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

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

-- | Copy a vector. The two vectors must have the same length and may not
-- overlap.
copy :: PrimMonad m => MVector (PrimState m) a   -- ^ target
                    -> MVector (PrimState m) a   -- ^ source
                    -> m ()
{-# INLINE copy #-}
copy :: MVector (PrimState m) a -> MVector (PrimState m) a -> m ()
copy = MVector (PrimState m) a -> MVector (PrimState m) a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> v (PrimState m) a -> m ()
G.copy

-- | Copy a vector. The two vectors must have the same length and may not
-- overlap. This is not checked.
unsafeCopy :: PrimMonad m => MVector (PrimState m) a   -- ^ target
                          -> MVector (PrimState m) a   -- ^ source
                          -> m ()
{-# INLINE unsafeCopy #-}
unsafeCopy :: MVector (PrimState m) a -> MVector (PrimState m) a -> m ()
unsafeCopy = MVector (PrimState m) a -> MVector (PrimState m) a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> v (PrimState m) a -> m ()
G.unsafeCopy

-- | 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 :: PrimMonad m => MVector (PrimState m) a   -- ^ target
                    -> MVector (PrimState m) a   -- ^ source
                    -> m ()
{-# INLINE move #-}
move :: MVector (PrimState m) a -> MVector (PrimState m) a -> m ()
move = MVector (PrimState m) a -> MVector (PrimState m) a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> v (PrimState m) a -> m ()
G.move

-- | 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 (PrimState m) a   -- ^ target
                          -> MVector (PrimState m) a   -- ^ source
                          -> m ()
{-# INLINE unsafeMove #-}
unsafeMove :: MVector (PrimState m) a -> MVector (PrimState m) a -> m ()
unsafeMove = MVector (PrimState m) a -> MVector (PrimState m) a -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> v (PrimState m) a -> m ()
G.unsafeMove

-- | Compute the next (lexicographically) permutation of given vector in-place.
--   Returns False when input is the last permutation
nextPermutation :: (PrimMonad m,Ord e) => MVector (PrimState m) e -> m Bool
{-# INLINE nextPermutation #-}
nextPermutation :: MVector (PrimState m) e -> m Bool
nextPermutation = MVector (PrimState m) e -> m Bool
forall (m :: * -> *) e (v :: * -> * -> *).
(PrimMonad m, Ord e, MVector v e) =>
v (PrimState m) e -> m Bool
G.nextPermutation

-- Conversions - Arrays
-- -----------------------------

-- | /O(n)/ Make a copy of a mutable array to a new mutable vector.
--
-- @since 0.12.2.0
fromMutableArray :: PrimMonad m => MutableArray (PrimState m) a -> m (MVector (PrimState m) a)
{-# INLINE fromMutableArray #-}
fromMutableArray :: MutableArray (PrimState m) a -> m (MVector (PrimState m) a)
fromMutableArray MutableArray (PrimState m) a
marr =
  let size :: Int
size = MutableArray (PrimState m) a -> Int
forall s a. MutableArray s a -> Int
sizeofMutableArray MutableArray (PrimState m) a
marr
   in Int
-> Int -> MutableArray (PrimState m) a -> MVector (PrimState m) a
forall s a. Int -> Int -> MutableArray s a -> MVector s a
MVector Int
0 Int
size (MutableArray (PrimState m) a -> MVector (PrimState m) a)
-> m (MutableArray (PrimState m) a) -> m (MVector (PrimState m) a)
forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
`liftM` MutableArray (PrimState m) a
-> Int -> Int -> m (MutableArray (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a
-> Int -> Int -> m (MutableArray (PrimState m) a)
cloneMutableArray MutableArray (PrimState m) a
marr Int
0 Int
size

-- | /O(n)/ Make a copy of a mutable vector into a new mutable array.
--
-- @since 0.12.2.0
toMutableArray :: PrimMonad m => MVector (PrimState m) a -> m (MutableArray (PrimState m) a)
{-# INLINE toMutableArray #-}
toMutableArray :: MVector (PrimState m) a -> m (MutableArray (PrimState m) a)
toMutableArray (MVector Int
offset Int
size MutableArray (PrimState m) a
marr) = MutableArray (PrimState m) a
-> Int -> Int -> m (MutableArray (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
MutableArray (PrimState m) a
-> Int -> Int -> m (MutableArray (PrimState m) a)
cloneMutableArray MutableArray (PrimState m) a
marr Int
offset Int
size