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