1{-# LANGUAGE CPP #-} 2 3-- | 4-- Module : Data.Vector.Unboxed.Mutable 5-- Copyright : (c) Roman Leshchinskiy 2009-2010 6-- License : BSD-style 7-- 8-- Maintainer : Roman Leshchinskiy <rl@cse.unsw.edu.au> 9-- Stability : experimental 10-- Portability : non-portable 11-- 12-- Mutable adaptive unboxed vectors 13-- 14 15module Data.Vector.Unboxed.Mutable ( 16 -- * Mutable vectors of primitive types 17 MVector(..), IOVector, STVector, Unbox, 18 19 -- * Accessors 20 21 -- ** Length information 22 length, null, 23 24 -- ** Extracting subvectors 25 slice, init, tail, take, drop, splitAt, 26 unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop, 27 28 -- ** Overlapping 29 overlaps, 30 31 -- * Construction 32 33 -- ** Initialisation 34 new, unsafeNew, replicate, replicateM, clone, 35 36 -- ** Growing 37 grow, unsafeGrow, 38 39 -- ** Restricting memory usage 40 clear, 41 42 -- * Zipping and unzipping 43 zip, zip3, zip4, zip5, zip6, 44 unzip, unzip3, unzip4, unzip5, unzip6, 45 46 -- * Accessing individual elements 47 read, write, modify, swap, 48 unsafeRead, unsafeWrite, unsafeModify, unsafeSwap, 49 50 -- * Modifying vectors 51 nextPermutation, 52 53 -- ** Filling and copying 54 set, copy, move, unsafeCopy, unsafeMove 55) where 56 57import Data.Vector.Unboxed.Base 58import qualified Data.Vector.Generic.Mutable as G 59import Data.Vector.Fusion.Util ( delayed_min ) 60import Control.Monad.Primitive 61 62import Prelude hiding ( length, null, replicate, reverse, map, read, 63 take, drop, splitAt, init, tail, 64 zip, zip3, unzip, unzip3 ) 65 66-- don't import an unused Data.Vector.Internal.Check 67#define NOT_VECTOR_MODULE 68#include "vector.h" 69 70-- Length information 71-- ------------------ 72 73-- | Length of the mutable vector. 74length :: Unbox a => MVector s a -> Int 75{-# INLINE length #-} 76length = G.length 77 78-- | Check whether the vector is empty 79null :: Unbox a => MVector s a -> Bool 80{-# INLINE null #-} 81null = G.null 82 83-- Extracting subvectors 84-- --------------------- 85 86-- | Yield a part of the mutable vector without copying it. The vector must 87-- contain at least @i+n@ elements. 88slice :: Unbox a 89 => Int -- ^ @i@ starting index 90 -> Int -- ^ @n@ length 91 -> MVector s a 92 -> MVector s a 93{-# INLINE slice #-} 94slice = G.slice 95 96take :: Unbox a => Int -> MVector s a -> MVector s a 97{-# INLINE take #-} 98take = G.take 99 100drop :: Unbox a => Int -> MVector s a -> MVector s a 101{-# INLINE drop #-} 102drop = G.drop 103 104splitAt :: Unbox a => Int -> MVector s a -> (MVector s a, MVector s a) 105{-# INLINE splitAt #-} 106splitAt = G.splitAt 107 108init :: Unbox a => MVector s a -> MVector s a 109{-# INLINE init #-} 110init = G.init 111 112tail :: Unbox a => MVector s a -> MVector s a 113{-# INLINE tail #-} 114tail = G.tail 115 116-- | Yield a part of the mutable vector without copying it. No bounds checks 117-- are performed. 118unsafeSlice :: Unbox a 119 => Int -- ^ starting index 120 -> Int -- ^ length of the slice 121 -> MVector s a 122 -> MVector s a 123{-# INLINE unsafeSlice #-} 124unsafeSlice = G.unsafeSlice 125 126unsafeTake :: Unbox a => Int -> MVector s a -> MVector s a 127{-# INLINE unsafeTake #-} 128unsafeTake = G.unsafeTake 129 130unsafeDrop :: Unbox a => Int -> MVector s a -> MVector s a 131{-# INLINE unsafeDrop #-} 132unsafeDrop = G.unsafeDrop 133 134unsafeInit :: Unbox a => MVector s a -> MVector s a 135{-# INLINE unsafeInit #-} 136unsafeInit = G.unsafeInit 137 138unsafeTail :: Unbox a => MVector s a -> MVector s a 139{-# INLINE unsafeTail #-} 140unsafeTail = G.unsafeTail 141 142-- Overlapping 143-- ----------- 144 145-- | Check whether two vectors overlap. 146overlaps :: Unbox a => MVector s a -> MVector s a -> Bool 147{-# INLINE overlaps #-} 148overlaps = G.overlaps 149 150-- Initialisation 151-- -------------- 152 153-- | Create a mutable vector of the given length. 154new :: (PrimMonad m, Unbox a) => Int -> m (MVector (PrimState m) a) 155{-# INLINE new #-} 156new = G.new 157 158-- | Create a mutable vector of the given length. The vector content 159-- is uninitialized, which means it is filled with whatever underlying memory 160-- buffer happens to contain. 161-- 162-- @since 0.5 163unsafeNew :: (PrimMonad m, Unbox a) => Int -> m (MVector (PrimState m) a) 164{-# INLINE unsafeNew #-} 165unsafeNew = G.unsafeNew 166 167-- | Create a mutable vector of the given length (0 if the length is negative) 168-- and fill it with an initial value. 169replicate :: (PrimMonad m, Unbox a) => Int -> a -> m (MVector (PrimState m) a) 170{-# INLINE replicate #-} 171replicate = G.replicate 172 173-- | Create a mutable vector of the given length (0 if the length is negative) 174-- and fill it with values produced by repeatedly executing the monadic action. 175replicateM :: (PrimMonad m, Unbox a) => Int -> m a -> m (MVector (PrimState m) a) 176{-# INLINE replicateM #-} 177replicateM = G.replicateM 178 179-- | Create a copy of a mutable vector. 180clone :: (PrimMonad m, Unbox a) 181 => MVector (PrimState m) a -> m (MVector (PrimState m) a) 182{-# INLINE clone #-} 183clone = G.clone 184 185-- Growing 186-- ------- 187 188-- | Grow an unboxed vector by the given number of elements. The number must be 189-- non-negative. Same semantics as in `G.grow` for generic vector. 190-- 191-- ====__Examples__ 192-- 193-- >>> import qualified Data.Vector.Unboxed as VU 194-- >>> import qualified Data.Vector.Unboxed.Mutable as MVU 195-- >>> mv <- VU.thaw $ VU.fromList ([('a', 10), ('b', 20), ('c', 30)] :: [(Char, Int)]) 196-- >>> mv' <- MVU.grow mv 2 197-- 198-- Extra memory at the end of the newly allocated vector is initialized to 0 199-- bytes, which for `Unbox` instance will usually correspond to some default 200-- value for a particular type, eg. @0@ for @Int@, @False@ for @Bool@, 201-- etc. However, if `unsafeGrow` was used instead this would not have been 202-- guaranteed and some garbage would be there instead: 203-- 204-- >>> VU.unsafeFreeze mv' 205-- [('a',10),('b',20),('c',30),('\NUL',0),('\NUL',0)] 206-- 207-- Having the extra space we can write new values in there: 208-- 209-- >>> MVU.write mv' 3 ('d', 999) 210-- >>> VU.unsafeFreeze mv' 211-- [('a',10),('b',20),('c',30),('d',999),('\NUL',0)] 212-- 213-- It is important to note that the source mutable vector is not affected when 214-- the newly allocated one is mutated. 215-- 216-- >>> MVU.write mv' 2 ('X', 888) 217-- >>> VU.unsafeFreeze mv' 218-- [('a',10),('b',20),('X',888),('d',999),('\NUL',0)] 219-- >>> VU.unsafeFreeze mv 220-- [('a',10),('b',20),('c',30)] 221-- 222-- @since 0.5 223grow :: (PrimMonad m, Unbox a) 224 => MVector (PrimState m) a -> Int -> m (MVector (PrimState m) a) 225{-# INLINE grow #-} 226grow = G.grow 227 228-- | Grow a vector by the given number of elements. The number must be non-negative but 229-- this is not checked. Same semantics as in `G.unsafeGrow` for generic vector. 230-- 231-- @since 0.5 232unsafeGrow :: (PrimMonad m, Unbox a) 233 => MVector (PrimState m) a -> Int -> m (MVector (PrimState m) a) 234{-# INLINE unsafeGrow #-} 235unsafeGrow = G.unsafeGrow 236 237-- Restricting memory usage 238-- ------------------------ 239 240-- | Reset all elements of the vector to some undefined value, clearing all 241-- references to external objects. This is usually a noop for unboxed vectors. 242clear :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> m () 243{-# INLINE clear #-} 244clear = G.clear 245 246-- Accessing individual elements 247-- ----------------------------- 248 249-- | Yield the element at the given position. 250read :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> Int -> m a 251{-# INLINE read #-} 252read = G.read 253 254-- | Replace the element at the given position. 255write :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> Int -> a -> m () 256{-# INLINE write #-} 257write = G.write 258 259-- | Modify the element at the given position. 260modify :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> (a -> a) -> Int -> m () 261{-# INLINE modify #-} 262modify = G.modify 263 264-- | Swap the elements at the given positions. 265swap :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> Int -> Int -> m () 266{-# INLINE swap #-} 267swap = G.swap 268 269 270-- | Yield the element at the given position. No bounds checks are performed. 271unsafeRead :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> Int -> m a 272{-# INLINE unsafeRead #-} 273unsafeRead = G.unsafeRead 274 275-- | Replace the element at the given position. No bounds checks are performed. 276unsafeWrite 277 :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> Int -> a -> m () 278{-# INLINE unsafeWrite #-} 279unsafeWrite = G.unsafeWrite 280 281-- | Modify the element at the given position. No bounds checks are performed. 282unsafeModify :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> (a -> a) -> Int -> m () 283{-# INLINE unsafeModify #-} 284unsafeModify = G.unsafeModify 285 286-- | Swap the elements at the given positions. No bounds checks are performed. 287unsafeSwap 288 :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> Int -> Int -> m () 289{-# INLINE unsafeSwap #-} 290unsafeSwap = G.unsafeSwap 291 292-- Filling and copying 293-- ------------------- 294 295-- | Set all elements of the vector to the given value. 296set :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> a -> m () 297{-# INLINE set #-} 298set = G.set 299 300-- | Copy a vector. The two vectors must have the same length and may not 301-- overlap. 302copy :: (PrimMonad m, Unbox a) 303 => MVector (PrimState m) a -- ^ target 304 -> MVector (PrimState m) a -- ^ source 305 -> m () 306{-# INLINE copy #-} 307copy = G.copy 308 309-- | Copy a vector. The two vectors must have the same length and may not 310-- overlap. This is not checked. 311unsafeCopy :: (PrimMonad m, Unbox a) 312 => MVector (PrimState m) a -- ^ target 313 -> MVector (PrimState m) a -- ^ source 314 -> m () 315{-# INLINE unsafeCopy #-} 316unsafeCopy = G.unsafeCopy 317 318-- | Move the contents of a vector. The two vectors must have the same 319-- length. 320-- 321-- If the vectors do not overlap, then this is equivalent to 'copy'. 322-- Otherwise, the copying is performed as if the source vector were 323-- copied to a temporary vector and then the temporary vector was copied 324-- to the target vector. 325move :: (PrimMonad m, Unbox a) 326 => MVector (PrimState m) a -- ^ target 327 -> MVector (PrimState m) a -- ^ source 328 -> m () 329{-# INLINE move #-} 330move = G.move 331 332-- | Move the contents of a vector. The two vectors must have the same 333-- length, but this is not checked. 334-- 335-- If the vectors do not overlap, then this is equivalent to 'unsafeCopy'. 336-- Otherwise, the copying is performed as if the source vector were 337-- copied to a temporary vector and then the temporary vector was copied 338-- to the target vector. 339unsafeMove :: (PrimMonad m, Unbox a) 340 => MVector (PrimState m) a -- ^ target 341 -> MVector (PrimState m) a -- ^ source 342 -> m () 343{-# INLINE unsafeMove #-} 344unsafeMove = G.unsafeMove 345 346-- | Compute the next (lexicographically) permutation of given vector in-place. 347-- Returns False when input is the last permutation 348nextPermutation :: (PrimMonad m,Ord e,Unbox e) => MVector (PrimState m) e -> m Bool 349{-# INLINE nextPermutation #-} 350nextPermutation = G.nextPermutation 351 352#define DEFINE_MUTABLE 353#include "unbox-tuple-instances" 354