Haddock comments
[darcs-mirrors/vector.git] / Data / Vector / MVector.hs
1 {-# LANGUAGE MultiParamTypeClasses #-}
2 -- |
3 -- Module : Data.Vector.MVector
4 -- Copyright : (c) Roman Leshchinskiy 2008
5 -- License : BSD-style
6 --
7 -- Maintainer : rl@cse.unsw.edu.au
8 -- Stability : experimental
9 -- Portability : non-portable
10 --
11 -- Generic interface to mutable vectors
12 --
13
14 module Data.Vector.MVector (
15 MVector(..),
16
17 slice, new, newWith, read, write, copy, grow, unstream
18 ) where
19
20 import qualified Data.Vector.Stream as Stream
21 import Data.Vector.Stream ( Stream )
22 import Data.Vector.Stream.Size
23
24 import Control.Monad.ST ( ST )
25 import Control.Exception ( assert )
26
27 import GHC.Float (
28 double2Int, int2Double
29 )
30
31 import Prelude hiding ( length, read )
32
33 gROWTH_FACTOR :: Double
34 gROWTH_FACTOR = 1.5
35
36 -- | Class of mutable vectors. The type @m@ is the monad in which the mutable
37 -- vector can be transformed and @a@ is the type of elements. A vector does
38 -- not necessarily have to be generic in either of them (indeed, it would be
39 -- unusual for a vector to be generic in the monad). Use GADTs if this is the
40 -- case. For instance, regular boxed vectors are defined as
41 --
42 -- > data Vector m a where
43 -- > Vector :: !Int -> !Int -> MutableArray# s a -> Vector (ST s) a
44 --
45 -- This is a bit clumsy but I haven't been able to find a better solution. In
46 -- particular, using a type function for the monad triggers
47 -- <http://hackage.haskell.org/trac/ghc/ticket/2440> and is probably less
48 -- portable.
49 --
50 class Monad m => MVector v m a where
51 -- | Length of the mutable vector
52 length :: v m a -> Int
53
54 -- | Yield a part of the mutable vector without copying it. No range checks!
55 unsafeSlice :: v m a -> Int -- ^ starting index
56 -> Int -- ^ length of the slice
57 -> v m a
58
59 -- | Create a mutable vector of the given length. Length is not checked!
60 unsafeNew :: Int -> m (v m a)
61
62 -- | Create a mutable vector of the given length and fill it with an
63 -- initial value. Length is not checked!
64 unsafeNewWith :: Int -> a -> m (v m a)
65
66 -- | Yield the element at the given position. Index is not checked!
67 unsafeRead :: v m a -> Int -> m a
68
69 -- | Replace the element at the given position. Index is not checked!
70 unsafeWrite :: v m a -> Int -> a -> m ()
71
72 -- | Write the value at each position.
73 set :: v m a -> a -> m ()
74
75 -- | Copy a vector. The two vectors may not overlap. This is not checked!
76 unsafeCopy :: v m a -- ^ target
77 -> v m a -- ^ source
78 -> m ()
79
80 -- | Grow a vector by the given number of elements. The length is not
81 -- checked!
82 unsafeGrow :: v m a -> Int -> m (v m a)
83
84 -- Check whether two vectors overlap.
85 overlaps :: v m a -> v m a -> Bool
86
87 {-# INLINE unsafeNewWith #-}
88 unsafeNewWith n x = do
89 v <- unsafeNew n
90 set v x
91 return v
92
93 {-# INLINE set #-}
94 set v x = do_set 0
95 where
96 n = length v
97
98 do_set i | i < n = do
99 unsafeWrite v i x
100 do_set (i+1)
101 | otherwise = return ()
102
103 {-# INLINE unsafeCopy #-}
104 unsafeCopy dst src = do_copy 0
105 where
106 n = length src
107
108 do_copy i | i < n = do
109 x <- unsafeRead src i
110 unsafeWrite dst i x
111 do_copy (i+1)
112 | otherwise = return ()
113
114 {-# INLINE unsafeGrow #-}
115 unsafeGrow v by = do
116 v' <- unsafeNew (n+by)
117 unsafeCopy (unsafeSlice v' 0 n) v
118 return v'
119 where
120 n = length v
121
122 -- | Test whether the index is valid for the vector
123 inBounds :: MVector v m a => v m a -> Int -> Bool
124 {-# INLINE inBounds #-}
125 inBounds v i = i >= 0 && i < length v
126
127 -- | Yield a part of the mutable vector without copying it. Safer version of
128 -- 'unsafeSlice'.
129 slice :: MVector v m a => v m a -> Int -> Int -> v m a
130 {-# INLINE slice #-}
131 slice v i n = assert (i >=0 && n >= 0 && i+n <= length v)
132 $ unsafeSlice v i n
133
134 -- | Create a mutable vector of the given length. Safer version of
135 -- 'unsafeNew'.
136 new :: MVector v m a => Int -> m (v m a)
137 {-# INLINE new #-}
138 new n = assert (n >= 0) $ unsafeNew n
139
140 -- | Create a mutable vector of the given length and fill it with an
141 -- initial value. Safer version of 'unsafeNewWith'.
142 newWith :: MVector v m a => Int -> a -> m (v m a)
143 {-# INLINE newWith #-}
144 newWith n x = assert (n >= 0) $ unsafeNewWith n x
145
146 -- | Yield the element at the given position. Safer version of 'unsafeRead'.
147 read :: MVector v m a => v m a -> Int -> m a
148 {-# INLINE read #-}
149 read v i = assert (inBounds v i) $ unsafeRead v i
150
151 -- | Replace the element at the given position. Safer version of
152 -- 'unsafeWrite'.
153 write :: MVector v m a => v m a -> Int -> a -> m ()
154 {-# INLINE write #-}
155 write v i x = assert (inBounds v i) $ unsafeWrite v i x
156
157 -- | Copy a vector. The two vectors may not overlap. Safer version of
158 -- 'unsafeCopy'.
159 copy :: MVector v m a => v m a -> v m a -> m ()
160 {-# INLINE copy #-}
161 copy dst src = assert (not (dst `overlaps` src) && length dst == length src)
162 $ unsafeCopy dst src
163
164 -- | Grow a vector by the given number of elements. Safer version of
165 -- 'unsafeGrow'.
166 grow :: MVector v m a => v m a -> Int -> m (v m a)
167 {-# INLINE grow #-}
168 grow v by = assert (by >= 0)
169 $ unsafeGrow v by
170
171
172 -- | Create a new mutable vector and fill it with elements from the 'Stream'.
173 -- The vector will grow logarithmically if the 'Size' hint of the 'Stream' is
174 -- inexact.
175 unstream :: MVector v m a => Stream a -> m (v m a)
176 {-# INLINE unstream #-}
177 unstream s = case upperBound (Stream.size s) of
178 Just n -> unstreamMax s n
179 Nothing -> unstreamUnknown s
180
181 unstreamMax :: MVector v m a => Stream a -> Int -> m (v m a)
182 {-# INLINE unstreamMax #-}
183 unstreamMax s n
184 = do
185 v <- new n
186 let put i x = do { write v i x; return (i+1) }
187 n' <- Stream.foldM put 0 s
188 return $ slice v 0 n'
189
190 unstreamUnknown :: MVector v m a => Stream a -> m (v m a)
191 {-# INLINE unstreamUnknown #-}
192 unstreamUnknown s
193 = do
194 v <- new 0
195 (v', n) <- Stream.foldM put (v, 0) s
196 return $ slice v' 0 n
197 where
198 {-# INLINE put #-}
199 put (v, i) x = do
200 v' <- enlarge v i
201 unsafeWrite v' i x
202 return (v', i+1)
203
204 {-# INLINE enlarge #-}
205 enlarge v i | i < length v = return v
206 | otherwise = unsafeGrow v
207 . max 1
208 . double2Int
209 $ int2Double (length v) * gROWTH_FACTOR
210