    {-# LANGUAGE MultiParamTypeClasses, BangPatterns, ScopedTypeVariables #-}
    -- |
    -- Module      : Data.Vector.Generic.Mutable
    -- Copyright   : (c) Roman Leshchinskiy 2008-2010
    -- License     : BSD-style
    --
    -- Maintainer  : Roman Leshchinskiy <rl@cse.unsw.edu.au>
    -- 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, clone,

      -- ** Growing
      grow, unsafeGrow,

      -- ** Restricting memory usage
      clear,

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

      -- * Modifying vectors

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

      -- * Internal operations
      mstream, mstreamR,
      unstream, unstreamR,
      munstream, munstreamR,
      transform, transformR,
      fill, fillR,
      unsafeAccum, accum, unsafeUpdate, update, reverse,
      unstablePartition, unstablePartitionStream, partitionStream
    ) where

    import qualified Data.Vector.Fusion.Stream      as Stream
    import           Data.Vector.Fusion.Stream      ( Stream, MStream )
    import qualified Data.Vector.Fusion.Stream.Monadic as MStream
    import           Data.Vector.Fusion.Stream.Size
    import           Data.Vector.Fusion.Util        ( delay_inline )

    import Control.Monad.Primitive ( PrimMonad, PrimState )

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

    #include "vector.h"

    -- | Class of mutable vectors parametrised with a primitive state token.
    --
    -- Minimum complete implementation:
    --
    --   * 'basicLength'
    --
    --   * 'basicUnsafeSlice'
    --
    --   * 'basicOverlaps'
    --
    --   * 'basicUnsafeNew'
    --
    --   * 'basicUnsafeRead'
    --
    --   * 'basicUnsafeWrite'
    --
    class MVector v a where
      -- | Length of the mutable vector. This method should not be
      -- called directly, use 'length' instead.
      basicLength       :: v s a -> Int

      -- | Yield a part of the mutable vector without copying it. This method
      -- should not be called directly, use 'unsafeSlice' instead.
      basicUnsafeSlice :: Int  -- ^ starting index
                       -> Int  -- ^ length of the slice
                       -> v s a
                       -> v s a

      -- Check whether two vectors overlap. This method should not be
      -- called directly, use 'overlaps' instead.
      basicOverlaps    :: v s a -> v s a -> Bool

      -- | Create a mutable vector of the given length. This method should not be
      -- called directly, use 'unsafeNew' instead.
      basicUnsafeNew   :: PrimMonad m => Int -> m (v (PrimState m) a)

      -- | Create a mutable vector of the given length and fill it with an
      -- initial value. This method should not be called directly, use
      -- 'replicate' instead.
      basicUnsafeReplicate :: PrimMonad m => Int -> a -> m (v (PrimState m) a)

      -- | Yield the element at the given position. This method should not be
      -- called directly, use 'unsafeRead' instead.
      basicUnsafeRead  :: PrimMonad m => v (PrimState m) a -> Int -> m a

      -- | Replace the element at the given position. This method should not be
      -- called directly, use 'unsafeWrite' instead.
      basicUnsafeWrite :: PrimMonad m => v (PrimState m) a -> Int -> a -> m ()

      -- | Reset all elements of the vector to some undefined value, clearing all
      -- references to external objects. This is usually a noop for unboxed
      -- vectors. This method should not be called directly, use 'clear' instead.
      basicClear       :: PrimMonad m => v (PrimState m) a -> m ()

      -- | Set all elements of the vector to the given value. This method should
      -- not be called directly, use 'set' instead.
      basicSet         :: PrimMonad m => v (PrimState m) a -> a -> m ()

      -- | Copy a vector. The two vectors may not overlap. This method should not
      -- be called directly, use 'unsafeCopy' instead.
      basicUnsafeCopy  :: PrimMonad m => v (PrimState m) a   -- ^ target
                                      -> v (PrimState m) a   -- ^ source
                                      -> m ()

      -- | Move the contents of a vector. The two vectors may overlap. This method
      -- should not be called directly, use 'unsafeMove' instead.
      basicUnsafeMove  :: PrimMonad m => v (PrimState m) a   -- ^ target
                                      -> v (PrimState m) a   -- ^ source
                                      -> m ()

      -- | Grow a vector by the given number of elements. This method should not be
      -- called directly, use 'unsafeGrow' instead.
      basicUnsafeGrow  :: PrimMonad m => v (PrimState m) a -> Int
                                                           -> m (v (PrimState m) a)

      {-# INLINE basicUnsafeReplicate #-}
      basicUnsafeReplicate n x
        = do
            v <- basicUnsafeNew n
            basicSet v x
            return v

      {-# INLINE basicClear #-}
      basicClear _ = return ()

      {-# INLINE basicSet #-}
      basicSet !v x
        | n == 0    = return ()
        | otherwise = do
                        basicUnsafeWrite v 0 x
                        do_set 1
        where
          !n = basicLength v

          do_set i | 2*i < n = do basicUnsafeCopy (basicUnsafeSlice i i v)
                                                  (basicUnsafeSlice 0 i v)
                                  do_set (2*i)
                   | otherwise = basicUnsafeCopy (basicUnsafeSlice i (n-i) v)
                                                 (basicUnsafeSlice 0 (n-i) v)

      {-# INLINE basicUnsafeCopy #-}
      basicUnsafeCopy !dst !src = do_copy 0
        where
          !n = basicLength src

          do_copy i | i < n = do
                                x <- basicUnsafeRead src i
                                basicUnsafeWrite dst i x
                                do_copy (i+1)
                    | otherwise = return ()

      {-# INLINE basicUnsafeMove #-}
      basicUnsafeMove !dst !src
        | basicOverlaps dst src = do
            srcCopy <- clone src
            basicUnsafeCopy dst srcCopy
        | otherwise = basicUnsafeCopy dst src

      {-# INLINE basicUnsafeGrow #-}
      basicUnsafeGrow v by
        = do
            v' <- basicUnsafeNew (n+by)
            basicUnsafeCopy (basicUnsafeSlice 0 n v') v
            return v'
        where
          n = basicLength v

    -- ------------------
    -- 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 v i x
      | i < length v = do
                         unsafeWrite v i x
                         return v
      | otherwise    = do
                         v' <- enlarge v
                         INTERNAL_CHECK(checkIndex) "unsafeAppend1" i (length v')
                           $ unsafeWrite v' i x
                         return v'

    unsafePrepend1 :: (PrimMonad m, MVector v a)
            => v (PrimState m) a -> Int -> a -> m (v (PrimState m) a, Int)
    {-# INLINE_INNER unsafePrepend1 #-}
    unsafePrepend1 v i x
      | i /= 0    = do
                      let i' = i-1
                      unsafeWrite v i' x
                      return (v, i')
      | otherwise = do
                      (v', i) <- enlargeFront v
                      let i' = i-1
                      INTERNAL_CHECK(checkIndex) "unsafePrepend1" i' (length v')
                        $ unsafeWrite v' i' x
                      return (v', i')

    mstream :: (PrimMonad m, MVector v a) => v (PrimState m) a -> MStream m a
    {-# INLINE mstream #-}
    mstream v = v `seq` n `seq` (MStream.unfoldrM get 0 `MStream.sized` Exact n)
      where
        n = length v

        {-# INLINE_INNER get #-}
        get i | i < n     = do x <- unsafeRead v i
                               return $ Just (x, i+1)
              | otherwise = return $ Nothing

    fill :: (PrimMonad m, MVector v a)
               => v (PrimState m) a -> MStream m a -> m (v (PrimState m) a)
    {-# INLINE fill #-}
    fill v s = v `seq` do
                         n' <- MStream.foldM put 0 s
                         return $ unsafeSlice 0 n' v
      where
        {-# INLINE_INNER put #-}
        put i x = do
                    INTERNAL_CHECK(checkIndex) "fill" i (length v)
                      $ unsafeWrite v i x
                    return (i+1)

    transform :: (PrimMonad m, MVector v a)
      => (MStream m a -> MStream m a) -> v (PrimState m) a -> m (v (PrimState m) a)
    {-# INLINE_STREAM transform #-}
    transform f v = fill v (f (mstream v))

    mstreamR :: (PrimMonad m, MVector v a) => v (PrimState m) a -> MStream m a
    {-# INLINE mstreamR #-}
    mstreamR v = v `seq` n `seq` (MStream.unfoldrM get n `MStream.sized` Exact n)
      where
        n = length v

        {-# INLINE_INNER get #-}
        get i | j >= 0    = do x <- unsafeRead v j
                               return $ Just (x,j)
              | otherwise = return Nothing
          where
            j = i-1

    fillR :: (PrimMonad m, MVector v a)
               => v (PrimState m) a -> MStream m a -> m (v (PrimState m) a)
    {-# INLINE fillR #-}
    fillR v s = v `seq` do
                          i <- MStream.foldM put n s
                          return $ unsafeSlice i (n-i) v
      where
        n = length v

        {-# INLINE_INNER put #-}
        put i x = do
                    unsafeWrite v j x
                    return j
          where
            j = i-1

    transformR :: (PrimMonad m, MVector v a)
      => (MStream m a -> MStream m a) -> v (PrimState m) a -> m (v (PrimState m) a)
    {-# INLINE_STREAM transformR #-}
    transformR f v = fillR v (f (mstreamR v))

    -- | Create a new mutable vector and fill it with elements from the 'Stream'.
    -- The vector will grow exponentially if the maximum size of the 'Stream' is
    -- unknown.
    unstream :: (PrimMonad m, MVector v a) => Stream a -> m (v (PrimState m) a)
    -- NOTE: replace INLINE_STREAM by INLINE? (also in unstreamR)
    {-# INLINE_STREAM unstream #-}
    unstream s = munstream (Stream.liftStream 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) => MStream m a -> m (v (PrimState m) a)
    {-# INLINE_STREAM munstream #-}
    munstream s = case upperBound (MStream.size s) of
                   Just n  -> munstreamMax     s n
                   Nothing -> munstreamUnknown s

    -- FIXME: I can't think of how to prevent GHC from floating out
    -- unstreamUnknown. That is bad because SpecConstr then generates two
    -- specialisations: one for when it is called from unstream (it doesn't know
    -- the shape of the vector) and one for when the vector has grown. To see the
    -- problem simply compile this:
    --
    -- fromList = Data.Vector.Unboxed.unstream . Stream.fromList
    --
    -- I'm not sure this still applies (19/04/2010)

    munstreamMax
      :: (PrimMonad m, MVector v a) => MStream m a -> Int -> m (v (PrimState m) a)
    {-# INLINE munstreamMax #-}
    munstreamMax s n
      = do
          v <- INTERNAL_CHECK(checkLength) "munstreamMax" n
               $ unsafeNew n
          let put i x = do
                           INTERNAL_CHECK(checkIndex) "munstreamMax" i n
                             $ unsafeWrite v i x
                           return (i+1)
          n' <- MStream.foldM' put 0 s
          return $ INTERNAL_CHECK(checkSlice) "munstreamMax" 0 n' n
                 $ unsafeSlice 0 n' v

    munstreamUnknown
      :: (PrimMonad m, MVector v a) => MStream m a -> m (v (PrimState m) a)
    {-# INLINE munstreamUnknown #-}
    munstreamUnknown s
      = do
          v <- unsafeNew 0
          (v', n) <- MStream.foldM put (v, 0) s
          return $ INTERNAL_CHECK(checkSlice) "munstreamUnknown" 0 n (length v')
                 $ unsafeSlice 0 n v'
      where
        {-# INLINE_INNER put #-}
        put (v,i) x = do
                        v' <- unsafeAppend1 v i x
                        return (v',i+1)

    -- | Create a new mutable vector and fill it with elements from the 'Stream'
    -- from right to left. The vector will grow exponentially if the maximum size
    -- of the 'Stream' is unknown.
    unstreamR :: (PrimMonad m, MVector v a) => Stream a -> m (v (PrimState m) a)
    -- NOTE: replace INLINE_STREAM by INLINE? (also in unstream)
    {-# INLINE_STREAM unstreamR #-}
    unstreamR s = munstreamR (Stream.liftStream 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) => MStream m a -> m (v (PrimState m) a)
    {-# INLINE_STREAM munstreamR #-}
    munstreamR s = case upperBound (MStream.size s) of
                   Just n  -> munstreamRMax     s n
                   Nothing -> munstreamRUnknown s

    munstreamRMax
      :: (PrimMonad m, MVector v a) => MStream m a -> Int -> m (v (PrimState m) a)
    {-# INLINE munstreamRMax #-}
    munstreamRMax s n
      = do
          v <- INTERNAL_CHECK(checkLength) "munstreamRMax" n
               $ unsafeNew n
          let put i x = do
                          let i' = i-1
                          INTERNAL_CHECK(checkIndex) "munstreamRMax" i' n
                            $ unsafeWrite v i' x
                          return i'
          i <- MStream.foldM' put n s
          return $ INTERNAL_CHECK(checkSlice) "munstreamRMax" i (n-i) n
                 $ unsafeSlice i (n-i) v

    munstreamRUnknown
      :: (PrimMonad m, MVector v a) => MStream m a -> m (v (PrimState m) a)
    {-# INLINE munstreamRUnknown #-}
    munstreamRUnknown s
      = do
          v <- unsafeNew 0
          (v', i) <- MStream.foldM put (v, 0) s
          let n = length v'
          return $ INTERNAL_CHECK(checkSlice) "unstreamRUnknown" i (n-i) n
                 $ unsafeSlice i (n-i) v'
      where
        {-# INLINE_INNER put #-}
        put (v,i) x = unsafePrepend1 v i x

    -- Length
    -- ------

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

    -- | Check whether the vector is empty
    null :: MVector v a => v s a -> Bool
    {-# INLINE null #-}
    null v = length v == 0

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

    -- | Yield a part of the mutable vector without copying it.
    slice :: MVector v a => Int -> Int -> v s a -> v s a
    {-# INLINE slice #-}
    slice i n v = BOUNDS_CHECK(checkSlice) "slice" i n (length v)
                $ unsafeSlice i n v

    take :: MVector v a => Int -> v s a -> v s a
    {-# INLINE take #-}
    take n v = unsafeSlice 0 (min (max n 0) (length v)) v

    drop :: MVector v a => Int -> v s a -> v s a
    {-# INLINE drop #-}
    drop n v = unsafeSlice (min m n') (max 0 (m - n')) v
      where
        n' = max n 0
        m  = length v

    {-# INLINE splitAt #-}
    splitAt :: MVector v a => Int -> v s a -> (v s a, v s a)
    splitAt n v = ( unsafeSlice 0 m v
                  , unsafeSlice m (max 0 (len - n')) v
                  )
        where
          m   = min n' len
          n'  = max n 0
          len = length v

    init :: MVector v a => v s a -> v s a
    {-# INLINE init #-}
    init v = slice 0 (length v - 1) v

    tail :: MVector v a => v s a -> v s a
    {-# INLINE tail #-}
    tail v = slice 1 (length v - 1) 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 i n v = UNSAFE_CHECK(checkSlice) "unsafeSlice" i n (length v)
                      $ basicUnsafeSlice i n v

    unsafeInit :: MVector v a => v s a -> v s a
    {-# INLINE unsafeInit #-}
    unsafeInit v = unsafeSlice 0 (length v - 1) v

    unsafeTail :: MVector v a => v s a -> v s a
    {-# INLINE unsafeTail #-}
    unsafeTail v = unsafeSlice 1 (length v - 1) v

    unsafeTake :: MVector v a => Int -> v s a -> v s a
    {-# INLINE unsafeTake #-}
    unsafeTake n v = unsafeSlice 0 n v

    unsafeDrop :: MVector v a => Int -> v s a -> v s a
    {-# INLINE unsafeDrop #-}
    unsafeDrop n v = unsafeSlice n (length v - n) v

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

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

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

    -- | Create a mutable vector of the given length.
    new :: (PrimMonad m, MVector v a) => Int -> m (v (PrimState m) a)
    {-# INLINE new #-}
    new n = BOUNDS_CHECK(checkLength) "new" n
          $ unsafeNew n

    -- | Create a mutable vector of the given length. The length is not checked.
    unsafeNew :: (PrimMonad m, MVector v a) => Int -> m (v (PrimState m) a)
    {-# INLINE unsafeNew #-}
    unsafeNew n = UNSAFE_CHECK(checkLength) "unsafeNew" n
                $ basicUnsafeNew 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 n x = basicUnsafeReplicate (delay_inline max 0 n) 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 n m = munstream (MStream.replicateM n m)

    -- | 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 v = do
                v' <- unsafeNew (length v)
                unsafeCopy v' v
                return v'

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

    -- | Grow a vector by the given number of elements. The number must be
    -- positive.
    grow :: (PrimMonad m, MVector v a)
                    => v (PrimState m) a -> Int -> m (v (PrimState m) a)
    {-# INLINE grow #-}
    grow v by = BOUNDS_CHECK(checkLength) "grow" by
              $ unsafeGrow v by

    growFront :: (PrimMonad m, MVector v a)
                    => v (PrimState m) a -> Int -> m (v (PrimState m) a)
    {-# INLINE growFront #-}
    growFront v by = BOUNDS_CHECK(checkLength) "growFront" by
                   $ unsafeGrowFront v by

    enlarge_delta v = max (length v) 1

    -- | Grow a vector logarithmically
    enlarge :: (PrimMonad m, MVector v a)
                    => v (PrimState m) a -> m (v (PrimState m) a)
    {-# INLINE enlarge #-}
    enlarge v = unsafeGrow v (enlarge_delta v)

    enlargeFront :: (PrimMonad m, MVector v a)
                    => v (PrimState m) a -> m (v (PrimState m) a, Int)
    {-# INLINE enlargeFront #-}
    enlargeFront v = do
                       v' <- unsafeGrowFront v by
                       return (v', by)
      where
        by = enlarge_delta v

    -- | Grow a vector by the given number of elements. The number must be
    -- positive but this is not checked.
    unsafeGrow :: (PrimMonad m, MVector v a)
                            => v (PrimState m) a -> Int -> m (v (PrimState m) a)
    {-# INLINE unsafeGrow #-}
    unsafeGrow v n = UNSAFE_CHECK(checkLength) "unsafeGrow" n
                   $ basicUnsafeGrow v n

    unsafeGrowFront :: (PrimMonad m, MVector v a)
                            => v (PrimState m) a -> Int -> m (v (PrimState m) a)
    {-# INLINE unsafeGrowFront #-}
    unsafeGrowFront v by = UNSAFE_CHECK(checkLength) "unsafeGrowFront" by
                         $ do
                             let n = length v
                             v' <- basicUnsafeNew (by+n)
                             basicUnsafeCopy (basicUnsafeSlice by n v') v
                             return 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 = basicClear

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

    -- | Yield the element at the given position.
    read :: (PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> m a
    {-# INLINE read #-}
    read v i = BOUNDS_CHECK(checkIndex) "read" i (length v)
             $ unsafeRead v i

    -- | Replace the element at the given position.
    write :: (PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> a -> m ()
    {-# INLINE write #-}
    write v i x = BOUNDS_CHECK(checkIndex) "write" i (length v)
                $ unsafeWrite v i x

    -- | Swap the elements at the given positions.
    swap :: (PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> Int -> m ()
    {-# INLINE swap #-}
    swap v i j = BOUNDS_CHECK(checkIndex) "swap" i (length v)
               $ BOUNDS_CHECK(checkIndex) "swap" j (length v)
               $ unsafeSwap v i j

    -- | Replace the element at the give position and return the old element.
    exchange :: (PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> a -> m a
    {-# INLINE exchange #-}
    exchange v i x = BOUNDS_CHECK(checkIndex) "exchange" i (length v)
                   $ unsafeExchange v i 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 v i = UNSAFE_CHECK(checkIndex) "unsafeRead" i (length v)
                   $ basicUnsafeRead v 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 v i x = UNSAFE_CHECK(checkIndex) "unsafeWrite" i (length v)
                      $ basicUnsafeWrite v i x

    -- | 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 v i j = UNSAFE_CHECK(checkIndex) "unsafeSwap" i (length v)
                     $ UNSAFE_CHECK(checkIndex) "unsafeSwap" j (length v)
                     $ do
                         x <- unsafeRead v i
                         y <- unsafeRead v j
                         unsafeWrite v i y
                         unsafeWrite v j x

    -- | Replace the element at the give 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 v i x = UNSAFE_CHECK(checkIndex) "unsafeExchange" i (length v)
                         $ do
                             y <- unsafeRead v i
                             unsafeWrite v i x
                             return y

    -- 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 = basicSet

    -- | Copy a vector. The two vectors must have the same length and may not
    -- overlap.
    copy :: (PrimMonad m, MVector v a)
                    => v (PrimState m) a -> v (PrimState m) a -> m ()
    {-# INLINE copy #-}
    copy dst src = BOUNDS_CHECK(check) "copy" "overlapping vectors"
                                              (not (dst `overlaps` src))
                 $ BOUNDS_CHECK(check) "copy" "length mismatch"
                                              (length dst == length src)
                 $ unsafeCopy dst 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 :: (PrimMonad m, MVector v a)
                    => v (PrimState m) a -> v (PrimState m) a -> m ()
    {-# INLINE move #-}
    move dst src = BOUNDS_CHECK(check) "move" "length mismatch"
                                              (length dst == length src)
                 $ unsafeMove dst src

    -- | Copy a vector. The two vectors must have the same length and may not
    -- overlap. This is not checked.
    unsafeCopy :: (PrimMonad m, MVector v a) => v (PrimState m) a   -- ^ target
                                             -> v (PrimState m) a   -- ^ source
                                             -> m ()
    {-# INLINE unsafeCopy #-}
    unsafeCopy dst src = UNSAFE_CHECK(check) "unsafeCopy" "length mismatch"
                                             (length dst == length src)
                       $ UNSAFE_CHECK(check) "unsafeCopy" "overlapping vectors"
                                             (not (dst `overlaps` src))
                       $ (dst `seq` src `seq` basicUnsafeCopy dst 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 dst src = UNSAFE_CHECK(check) "unsafeMove" "length mismatch"
                                             (length dst == length src)
                       $ (dst `seq` src `seq` basicUnsafeMove dst src)

    -- Permutations
    -- ------------

    accum :: (PrimMonad m, MVector v a)
            => (a -> b -> a) -> v (PrimState m) a -> Stream (Int, b) -> m ()
    {-# INLINE accum #-}
    accum f !v s = Stream.mapM_ upd s
      where
        {-# INLINE_INNER upd #-}
        upd (i,b) = do
                      a <- BOUNDS_CHECK(checkIndex) "accum" i n
                         $ unsafeRead v i
                      unsafeWrite v i (f a b)

        !n = length v

    update :: (PrimMonad m, MVector v a)
                            => v (PrimState m) a -> Stream (Int, a) -> m ()
    {-# INLINE update #-}
    update !v s = Stream.mapM_ upd s
      where
        {-# INLINE_INNER upd #-}
        upd (i,b) = BOUNDS_CHECK(checkIndex) "update" i n
                  $ unsafeWrite v i b

        !n = length v

    unsafeAccum :: (PrimMonad m, MVector v a)
                => (a -> b -> a) -> v (PrimState m) a -> Stream (Int, b) -> m ()
    {-# INLINE unsafeAccum #-}
    unsafeAccum f !v s = Stream.mapM_ upd s
      where
        {-# INLINE_INNER upd #-}
        upd (i,b) = do
                      a <- UNSAFE_CHECK(checkIndex) "accum" i n
                         $ unsafeRead v i
                      unsafeWrite v i (f a b)

        !n = length v

    unsafeUpdate :: (PrimMonad m, MVector v a)
                            => v (PrimState m) a -> Stream (Int, a) -> m ()
    {-# INLINE unsafeUpdate #-}
    unsafeUpdate !v s = Stream.mapM_ upd s
      where
        {-# INLINE_INNER upd #-}
        upd (i,b) = UNSAFE_CHECK(checkIndex) "accum" i n
                      $ unsafeWrite v i b

        !n = length v

    reverse :: (PrimMonad m, MVector v a) => v (PrimState m) a -> m ()
    {-# INLINE reverse #-}
    reverse !v = reverse_loop 0 (length v - 1)
      where
        reverse_loop i j | i < j = do
                                     unsafeSwap v i j
                                     reverse_loop (i + 1) (j - 1)
        reverse_loop _ _ = return ()

    unstablePartition :: forall m v a. (PrimMonad m, MVector v a)
                      => (a -> Bool) -> v (PrimState m) a -> m Int
    {-# INLINE unstablePartition #-}
    unstablePartition f !v = from_left 0 (length 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 i j
          | i == j    = return i
          | otherwise = do
                          x <- unsafeRead v i
                          if f x
                            then from_left (i+1) j
                            else from_right i (j-1)

        from_right :: Int -> Int -> m Int
        from_right i j
          | i == j    = return i
          | otherwise = do
                          x <- unsafeRead v j
                          if f x
                            then do
                                   y <- unsafeRead v i
                                   unsafeWrite v i x
                                   unsafeWrite v j y
                                   from_left (i+1) j
                            else from_right i (j-1)

    unstablePartitionStream :: (PrimMonad m, MVector v a)
            => (a -> Bool) -> Stream a -> m (v (PrimState m) a, v (PrimState m) a)
    {-# INLINE unstablePartitionStream #-}
    unstablePartitionStream f s
      = case upperBound (Stream.size s) of
          Just n  -> unstablePartitionMax f s n
          Nothing -> partitionUnknown f s

    unstablePartitionMax :: (PrimMonad m, MVector v a)
            => (a -> Bool) -> Stream a -> Int
            -> m (v (PrimState m) a, v (PrimState m) a)
    {-# INLINE unstablePartitionMax #-}
    unstablePartitionMax f s n
      = do
          v <- INTERNAL_CHECK(checkLength) "unstablePartitionMax" n
               $ unsafeNew n
          let {-# INLINE_INNER put #-}
              put (i, j) x
                | f x       = do
                                unsafeWrite v i x
                                return (i+1, j)
                | otherwise = do
                                unsafeWrite v (j-1) x
                                return (i, j-1)

          (i,j) <- Stream.foldM' put (0, n) s
          return (unsafeSlice 0 i v, unsafeSlice j (n-j) v)

    partitionStream :: (PrimMonad m, MVector v a)
            => (a -> Bool) -> Stream a -> m (v (PrimState m) a, v (PrimState m) a)
    {-# INLINE partitionStream #-}
    partitionStream f s
      = case upperBound (Stream.size s) of
          Just n  -> partitionMax f s n
          Nothing -> partitionUnknown f s

    partitionMax :: (PrimMonad m, MVector v a)
      => (a -> Bool) -> Stream a -> Int -> m (v (PrimState m) a, v (PrimState m) a)
    {-# INLINE partitionMax #-}
    partitionMax f s n
      = do
          v <- INTERNAL_CHECK(checkLength) "unstablePartitionMax" n
             $ unsafeNew n

          let {-# INLINE_INNER put #-}
              put (i,j) x
                | f x       = do
                                unsafeWrite v i x
                                return (i+1,j)

                | otherwise = let j' = j-1 in
                              do
                                unsafeWrite v j' x
                                return (i,j')

          (i,j) <- Stream.foldM' put (0,n) s
          INTERNAL_CHECK(check) "partitionMax" "invalid indices" (i <= j)
            $ return ()
          let l = unsafeSlice 0 i v
              r = unsafeSlice j (n-j) v
          reverse r
          return (l,r)

    partitionUnknown :: (PrimMonad m, MVector v a)
            => (a -> Bool) -> Stream a -> m (v (PrimState m) a, v (PrimState m) a)
    {-# INLINE partitionUnknown #-}
    partitionUnknown f s
      = do
          v1 <- unsafeNew 0
          v2 <- unsafeNew 0
          (v1', n1, v2', n2) <- Stream.foldM' put (v1, 0, v2, 0) s
          INTERNAL_CHECK(checkSlice) "partitionUnknown" 0 n1 (length v1')
            $ INTERNAL_CHECK(checkSlice) "partitionUnknown" 0 n2 (length v2')
            $ return (unsafeSlice 0 n1 v1', unsafeSlice 0 n2 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 (v1, i1, v2, i2) x
          | f x       = do
                          v1' <- unsafeAppend1 v1 i1 x
                          return (v1', i1+1, v2, i2)
          | otherwise = do
                          v2' <- unsafeAppend1 v2 i2 x
                          return (v1, i1, v2', i2+1)