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, generate, generateM, 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, modifyM, swap, exchange, 48 unsafeRead, unsafeWrite, unsafeModify, unsafeModifyM, unsafeSwap, unsafeExchange, 49 50 -- * Folds 51 mapM_, imapM_, forM_, iforM_, 52 foldl, foldl', foldM, foldM', 53 foldr, foldr', foldrM, foldrM', 54 ifoldl, ifoldl', ifoldM, ifoldM', 55 ifoldr, ifoldr', ifoldrM, ifoldrM', 56 57 -- * Modifying vectors 58 nextPermutation, 59 60 -- ** Filling and copying 61 set, copy, move, unsafeCopy, unsafeMove 62) where 63 64import Data.Vector.Unboxed.Base 65import qualified Data.Vector.Generic.Mutable as G 66import Data.Vector.Fusion.Util ( delayed_min ) 67import Control.Monad.Primitive 68 69import Prelude hiding ( length, null, replicate, reverse, map, read, 70 take, drop, splitAt, init, tail, 71 zip, zip3, unzip, unzip3, foldr, foldl, mapM_ ) 72 73-- don't import an unused Data.Vector.Internal.Check 74#define NOT_VECTOR_MODULE 75#include "vector.h" 76 77-- Length information 78-- ------------------ 79 80-- | Length of the mutable vector. 81length :: Unbox a => MVector s a -> Int 82{-# INLINE length #-} 83length = G.length 84 85-- | Check whether the vector is empty 86null :: Unbox a => MVector s a -> Bool 87{-# INLINE null #-} 88null = G.null 89 90-- Extracting subvectors 91-- --------------------- 92 93-- | Yield a part of the mutable vector without copying it. The vector must 94-- contain at least @i+n@ elements. 95slice :: Unbox a 96 => Int -- ^ @i@ starting index 97 -> Int -- ^ @n@ length 98 -> MVector s a 99 -> MVector s a 100{-# INLINE slice #-} 101slice = G.slice 102 103take :: Unbox a => Int -> MVector s a -> MVector s a 104{-# INLINE take #-} 105take = G.take 106 107drop :: Unbox a => Int -> MVector s a -> MVector s a 108{-# INLINE drop #-} 109drop = G.drop 110 111splitAt :: Unbox a => Int -> MVector s a -> (MVector s a, MVector s a) 112{-# INLINE splitAt #-} 113splitAt = G.splitAt 114 115init :: Unbox a => MVector s a -> MVector s a 116{-# INLINE init #-} 117init = G.init 118 119tail :: Unbox a => MVector s a -> MVector s a 120{-# INLINE tail #-} 121tail = G.tail 122 123-- | Yield a part of the mutable vector without copying it. No bounds checks 124-- are performed. 125unsafeSlice :: Unbox a 126 => Int -- ^ starting index 127 -> Int -- ^ length of the slice 128 -> MVector s a 129 -> MVector s a 130{-# INLINE unsafeSlice #-} 131unsafeSlice = G.unsafeSlice 132 133unsafeTake :: Unbox a => Int -> MVector s a -> MVector s a 134{-# INLINE unsafeTake #-} 135unsafeTake = G.unsafeTake 136 137unsafeDrop :: Unbox a => Int -> MVector s a -> MVector s a 138{-# INLINE unsafeDrop #-} 139unsafeDrop = G.unsafeDrop 140 141unsafeInit :: Unbox a => MVector s a -> MVector s a 142{-# INLINE unsafeInit #-} 143unsafeInit = G.unsafeInit 144 145unsafeTail :: Unbox a => MVector s a -> MVector s a 146{-# INLINE unsafeTail #-} 147unsafeTail = G.unsafeTail 148 149-- Overlapping 150-- ----------- 151 152-- | Check whether two vectors overlap. 153overlaps :: Unbox a => MVector s a -> MVector s a -> Bool 154{-# INLINE overlaps #-} 155overlaps = G.overlaps 156 157-- Initialisation 158-- -------------- 159 160-- | Create a mutable vector of the given length. 161new :: (PrimMonad m, Unbox a) => Int -> m (MVector (PrimState m) a) 162{-# INLINE new #-} 163new = G.new 164 165-- | Create a mutable vector of the given length. The vector content 166-- is uninitialized, which means it is filled with whatever underlying memory 167-- buffer happens to contain. 168-- 169-- @since 0.5 170unsafeNew :: (PrimMonad m, Unbox a) => Int -> m (MVector (PrimState m) a) 171{-# INLINE unsafeNew #-} 172unsafeNew = G.unsafeNew 173 174-- | Create a mutable vector of the given length (0 if the length is negative) 175-- and fill it with an initial value. 176replicate :: (PrimMonad m, Unbox a) => Int -> a -> m (MVector (PrimState m) a) 177{-# INLINE replicate #-} 178replicate = G.replicate 179 180-- | Create a mutable vector of the given length (0 if the length is negative) 181-- and fill it with values produced by repeatedly executing the monadic action. 182replicateM :: (PrimMonad m, Unbox a) => Int -> m a -> m (MVector (PrimState m) a) 183{-# INLINE replicateM #-} 184replicateM = G.replicateM 185 186-- | /O(n)/ Create a mutable vector of the given length (0 if the length is negative) 187-- and fill it with the results of applying the function to each index. 188-- 189-- @since 0.12.3.0 190generate :: (PrimMonad m, Unbox a) => Int -> (Int -> a) -> m (MVector (PrimState m) a) 191{-# INLINE generate #-} 192generate = G.generate 193 194-- | /O(n)/ Create a mutable vector of the given length (0 if the length is 195-- negative) and fill it with the results of applying the monadic function to each 196-- index. Iteration starts at index 0. 197-- 198-- @since 0.12.3.0 199generateM :: (PrimMonad m, Unbox a) => Int -> (Int -> m a) -> m (MVector (PrimState m) a) 200{-# INLINE generateM #-} 201generateM = G.generateM 202 203-- | Create a copy of a mutable vector. 204clone :: (PrimMonad m, Unbox a) 205 => MVector (PrimState m) a -> m (MVector (PrimState m) a) 206{-# INLINE clone #-} 207clone = G.clone 208 209-- Growing 210-- ------- 211 212-- | Grow an unboxed vector by the given number of elements. The number must be 213-- non-negative. Same semantics as in `G.grow` for generic vector. 214-- 215-- ====__Examples__ 216-- 217-- >>> import qualified Data.Vector.Unboxed as VU 218-- >>> import qualified Data.Vector.Unboxed.Mutable as MVU 219-- >>> mv <- VU.thaw $ VU.fromList ([('a', 10), ('b', 20), ('c', 30)] :: [(Char, Int)]) 220-- >>> mv' <- MVU.grow mv 2 221-- 222-- Extra memory at the end of the newly allocated vector is initialized to 0 223-- bytes, which for `Unbox` instance will usually correspond to some default 224-- value for a particular type, eg. @0@ for @Int@, @False@ for @Bool@, 225-- etc. However, if `unsafeGrow` was used instead this would not have been 226-- guaranteed and some garbage would be there instead: 227-- 228-- >>> VU.unsafeFreeze mv' 229-- [('a',10),('b',20),('c',30),('\NUL',0),('\NUL',0)] 230-- 231-- Having the extra space we can write new values in there: 232-- 233-- >>> MVU.write mv' 3 ('d', 999) 234-- >>> VU.unsafeFreeze mv' 235-- [('a',10),('b',20),('c',30),('d',999),('\NUL',0)] 236-- 237-- It is important to note that the source mutable vector is not affected when 238-- the newly allocated one is mutated. 239-- 240-- >>> MVU.write mv' 2 ('X', 888) 241-- >>> VU.unsafeFreeze mv' 242-- [('a',10),('b',20),('X',888),('d',999),('\NUL',0)] 243-- >>> VU.unsafeFreeze mv 244-- [('a',10),('b',20),('c',30)] 245-- 246-- @since 0.5 247grow :: (PrimMonad m, Unbox a) 248 => MVector (PrimState m) a -> Int -> m (MVector (PrimState m) a) 249{-# INLINE grow #-} 250grow = G.grow 251 252-- | Grow a vector by the given number of elements. The number must be non-negative but 253-- this is not checked. Same semantics as in `G.unsafeGrow` for generic vector. 254-- 255-- @since 0.5 256unsafeGrow :: (PrimMonad m, Unbox a) 257 => MVector (PrimState m) a -> Int -> m (MVector (PrimState m) a) 258{-# INLINE unsafeGrow #-} 259unsafeGrow = G.unsafeGrow 260 261-- Restricting memory usage 262-- ------------------------ 263 264-- | Reset all elements of the vector to some undefined value, clearing all 265-- references to external objects. This is usually a noop for unboxed vectors. 266clear :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> m () 267{-# INLINE clear #-} 268clear = G.clear 269 270-- Accessing individual elements 271-- ----------------------------- 272 273-- | Yield the element at the given position. 274read :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> Int -> m a 275{-# INLINE read #-} 276read = G.read 277 278-- | Replace the element at the given position. 279write :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> Int -> a -> m () 280{-# INLINE write #-} 281write = G.write 282 283-- | Modify the element at the given position. 284modify :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> (a -> a) -> Int -> m () 285{-# INLINE modify #-} 286modify = G.modify 287 288-- | Modify the element at the given position using a monadic function. 289-- 290-- @since 0.12.3.0 291modifyM :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> (a -> m a) -> Int -> m () 292{-# INLINE modifyM #-} 293modifyM = G.modifyM 294 295-- | Swap the elements at the given positions. 296swap :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> Int -> Int -> m () 297{-# INLINE swap #-} 298swap = G.swap 299 300-- | Replace the element at the given position and return the old element. 301exchange :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> Int -> a -> m a 302{-# INLINE exchange #-} 303exchange = G.exchange 304 305-- | Yield the element at the given position. No bounds checks are performed. 306unsafeRead :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> Int -> m a 307{-# INLINE unsafeRead #-} 308unsafeRead = G.unsafeRead 309 310-- | Replace the element at the given position. No bounds checks are performed. 311unsafeWrite 312 :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> Int -> a -> m () 313{-# INLINE unsafeWrite #-} 314unsafeWrite = G.unsafeWrite 315 316-- | Modify the element at the given position. No bounds checks are performed. 317unsafeModify :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> (a -> a) -> Int -> m () 318{-# INLINE unsafeModify #-} 319unsafeModify = G.unsafeModify 320 321-- | Modify the element at the given position using a monadic 322-- function. No bounds checks are performed. 323-- 324-- @since 0.12.3.0 325unsafeModifyM :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> (a -> m a) -> Int -> m () 326{-# INLINE unsafeModifyM #-} 327unsafeModifyM = G.unsafeModifyM 328 329-- | Swap the elements at the given positions. No bounds checks are performed. 330unsafeSwap 331 :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> Int -> Int -> m () 332{-# INLINE unsafeSwap #-} 333unsafeSwap = G.unsafeSwap 334 335-- | Replace the element at the given position and return the old element. No 336-- bounds checks are performed. 337unsafeExchange :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> Int -> a -> m a 338{-# INLINE unsafeExchange #-} 339unsafeExchange = G.unsafeExchange 340 341-- Filling and copying 342-- ------------------- 343 344-- | Set all elements of the vector to the given value. 345set :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> a -> m () 346{-# INLINE set #-} 347set = G.set 348 349-- | Copy a vector. The two vectors must have the same length and may not 350-- overlap. 351copy :: (PrimMonad m, Unbox a) 352 => MVector (PrimState m) a -- ^ target 353 -> MVector (PrimState m) a -- ^ source 354 -> m () 355{-# INLINE copy #-} 356copy = G.copy 357 358-- | Copy a vector. The two vectors must have the same length and may not 359-- overlap. This is not checked. 360unsafeCopy :: (PrimMonad m, Unbox a) 361 => MVector (PrimState m) a -- ^ target 362 -> MVector (PrimState m) a -- ^ source 363 -> m () 364{-# INLINE unsafeCopy #-} 365unsafeCopy = G.unsafeCopy 366 367-- | Move the contents of a vector. The two vectors must have the same 368-- length. 369-- 370-- If the vectors do not overlap, then this is equivalent to 'copy'. 371-- Otherwise, the copying is performed as if the source vector were 372-- copied to a temporary vector and then the temporary vector was copied 373-- to the target vector. 374move :: (PrimMonad m, Unbox a) 375 => MVector (PrimState m) a -- ^ target 376 -> MVector (PrimState m) a -- ^ source 377 -> m () 378{-# INLINE move #-} 379move = G.move 380 381-- | Move the contents of a vector. The two vectors must have the same 382-- length, but this is not checked. 383-- 384-- If the vectors do not overlap, then this is equivalent to 'unsafeCopy'. 385-- Otherwise, the copying is performed as if the source vector were 386-- copied to a temporary vector and then the temporary vector was copied 387-- to the target vector. 388unsafeMove :: (PrimMonad m, Unbox a) 389 => MVector (PrimState m) a -- ^ target 390 -> MVector (PrimState m) a -- ^ source 391 -> m () 392{-# INLINE unsafeMove #-} 393unsafeMove = G.unsafeMove 394 395-- | Compute the next (lexicographically) permutation of given vector in-place. 396-- Returns False when input is the last permutation 397nextPermutation :: (PrimMonad m,Ord e,Unbox e) => MVector (PrimState m) e -> m Bool 398{-# INLINE nextPermutation #-} 399nextPermutation = G.nextPermutation 400 401 402-- Folds 403-- ----- 404 405-- | /O(n)/ Apply the monadic action to every element of the vector, discarding the results. 406-- 407-- @since 0.12.3.0 408mapM_ :: (PrimMonad m, Unbox a) => (a -> m b) -> MVector (PrimState m) a -> m () 409{-# INLINE mapM_ #-} 410mapM_ = G.mapM_ 411 412-- | /O(n)/ Apply the monadic action to every element of the vector and its index, 413-- discarding the results. 414-- 415-- @since 0.12.3.0 416imapM_ :: (PrimMonad m, Unbox a) => (Int -> a -> m b) -> MVector (PrimState m) a -> m () 417{-# INLINE imapM_ #-} 418imapM_ = G.imapM_ 419 420-- | /O(n)/ Apply the monadic action to every element of the vector, 421-- discarding the results. It's same as the @flip mapM_@. 422-- 423-- @since 0.12.3.0 424forM_ :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> (a -> m b) -> m () 425{-# INLINE forM_ #-} 426forM_ = G.forM_ 427 428-- | /O(n)/ Apply the monadic action to every element of the vector 429-- and its index, discarding the results. It's same as the @flip imapM_@. 430-- 431-- @since 0.12.3.0 432iforM_ :: (PrimMonad m, Unbox a) => MVector (PrimState m) a -> (Int -> a -> m b) -> m () 433{-# INLINE iforM_ #-} 434iforM_ = G.iforM_ 435 436-- | /O(n)/ Pure left fold. 437-- 438-- @since 0.12.3.0 439foldl :: (PrimMonad m, Unbox a) => (b -> a -> b) -> b -> MVector (PrimState m) a -> m b 440{-# INLINE foldl #-} 441foldl = G.foldl 442 443-- | /O(n)/ Pure left fold with strict accumulator. 444-- 445-- @since 0.12.3.0 446foldl' :: (PrimMonad m, Unbox a) => (b -> a -> b) -> b -> MVector (PrimState m) a -> m b 447{-# INLINE foldl' #-} 448foldl' = G.foldl' 449 450-- | /O(n)/ Pure left fold (function applied to each element and its index). 451-- 452-- @since 0.12.3.0 453ifoldl :: (PrimMonad m, Unbox a) => (b -> Int -> a -> b) -> b -> MVector (PrimState m) a -> m b 454{-# INLINE ifoldl #-} 455ifoldl = G.ifoldl 456 457-- | /O(n)/ Pure left fold with strict accumulator (function applied to each element and its index). 458-- 459-- @since 0.12.3.0 460ifoldl' :: (PrimMonad m, Unbox a) => (b -> Int -> a -> b) -> b -> MVector (PrimState m) a -> m b 461{-# INLINE ifoldl' #-} 462ifoldl' = G.ifoldl' 463 464-- | /O(n)/ Pure right fold. 465-- 466-- @since 0.12.3.0 467foldr :: (PrimMonad m, Unbox a) => (a -> b -> b) -> b -> MVector (PrimState m) a -> m b 468{-# INLINE foldr #-} 469foldr = G.foldr 470 471-- | /O(n)/ Pure right fold with strict accumulator. 472-- 473-- @since 0.12.3.0 474foldr' :: (PrimMonad m, Unbox a) => (a -> b -> b) -> b -> MVector (PrimState m) a -> m b 475{-# INLINE foldr' #-} 476foldr' = G.foldr' 477 478-- | /O(n)/ Pure right fold (function applied to each element and its index). 479-- 480-- @since 0.12.3.0 481ifoldr :: (PrimMonad m, Unbox a) => (Int -> a -> b -> b) -> b -> MVector (PrimState m) a -> m b 482{-# INLINE ifoldr #-} 483ifoldr = G.ifoldr 484 485-- | /O(n)/ Pure right fold with strict accumulator (function applied 486-- to each element and its index). 487-- 488-- @since 0.12.3.0 489ifoldr' :: (PrimMonad m, Unbox a) => (Int -> a -> b -> b) -> b -> MVector (PrimState m) a -> m b 490{-# INLINE ifoldr' #-} 491ifoldr' = G.ifoldr' 492 493-- | /O(n)/ Monadic fold. 494-- 495-- @since 0.12.3.0 496foldM :: (PrimMonad m, Unbox a) => (b -> a -> m b) -> b -> MVector (PrimState m) a -> m b 497{-# INLINE foldM #-} 498foldM = G.foldM 499 500-- | /O(n)/ Monadic fold with strict accumulator. 501-- 502-- @since 0.12.3.0 503foldM' :: (PrimMonad m, Unbox a) => (b -> a -> m b) -> b -> MVector (PrimState m) a -> m b 504{-# INLINE foldM' #-} 505foldM' = G.foldM' 506 507-- | /O(n)/ Monadic fold (action applied to each element and its index). 508-- 509-- @since 0.12.3.0 510ifoldM :: (PrimMonad m, Unbox a) => (b -> Int -> a -> m b) -> b -> MVector (PrimState m) a -> m b 511{-# INLINE ifoldM #-} 512ifoldM = G.ifoldM 513 514-- | /O(n)/ Monadic fold with strict accumulator (action applied to each element and its index). 515-- 516-- @since 0.12.3.0 517ifoldM' :: (PrimMonad m, Unbox a) => (b -> Int -> a -> m b) -> b -> MVector (PrimState m) a -> m b 518{-# INLINE ifoldM' #-} 519ifoldM' = G.ifoldM' 520 521-- | /O(n)/ Monadic right fold. 522-- 523-- @since 0.12.3.0 524foldrM :: (PrimMonad m, Unbox a) => (a -> b -> m b) -> b -> MVector (PrimState m) a -> m b 525{-# INLINE foldrM #-} 526foldrM = G.foldrM 527 528-- | /O(n)/ Monadic right fold with strict accumulator. 529-- 530-- @since 0.12.3.0 531foldrM' :: (PrimMonad m, Unbox a) => (a -> b -> m b) -> b -> MVector (PrimState m) a -> m b 532{-# INLINE foldrM' #-} 533foldrM' = G.foldrM' 534 535-- | /O(n)/ Monadic right fold (action applied to each element and its index). 536-- 537-- @since 0.12.3.0 538ifoldrM :: (PrimMonad m, Unbox a) => (Int -> a -> b -> m b) -> b -> MVector (PrimState m) a -> m b 539{-# INLINE ifoldrM #-} 540ifoldrM = G.ifoldrM 541 542-- | /O(n)/ Monadic right fold with strict accumulator (action applied 543-- to each element and its index). 544-- 545-- @since 0.12.3.0 546ifoldrM' :: (PrimMonad m, Unbox a) => (Int -> a -> b -> m b) -> b -> MVector (PrimState m) a -> m b 547{-# INLINE ifoldrM' #-} 548ifoldrM' = G.ifoldrM' 549 550 551#define DEFINE_MUTABLE 552#include "unbox-tuple-instances" 553