Remove Control.Parallel*, now in package parallel
[packages/random.git] / Data / PackedString.hs
1 -----------------------------------------------------------------------------
2 -- |
3 -- Module : Data.PackedString
4 -- Copyright : (c) The University of Glasgow 2001
5 -- License : BSD-style (see the file libraries/base/LICENSE)
6 --
7 -- Maintainer : libraries@haskell.org
8 -- Stability : experimental
9 -- Portability : portable
10 --
11 -- This API is deprecated. You might be able to use "Data.ByteString"
12 -- or "Data.ByteString.Char8", provided you don't need full Unicode support.
13 -- The long term aim is to provide a Unicode layer on "Data.ByteString",
14 -- and then to provide a replacement for this "Data.PackedString" API based on
15 -- that.
16 --
17 -----------------------------------------------------------------------------
18
19 -- Original GHC implementation by Bryan O\'Sullivan,
20 -- rewritten to use UArray by Simon Marlow.
21
22 module Data.PackedString
23 {-# DEPRECATED "use Data.ByteString, Data.ByteString.Char8, or plain String." #-}
24 (
25 -- * The @PackedString@ type
26 PackedString, -- abstract, instances: Eq, Ord, Show, Typeable
27
28 -- * Converting to and from @PackedString@s
29 packString, -- :: String -> PackedString
30 unpackPS, -- :: PackedString -> String
31
32 #ifndef __NHC__
33 -- * I\/O with @PackedString@s
34 hPutPS, -- :: Handle -> PackedString -> IO ()
35 hGetPS, -- :: Handle -> Int -> IO PackedString
36 #endif
37
38 -- * List-like manipulation functions
39 nilPS, -- :: PackedString
40 consPS, -- :: Char -> PackedString -> PackedString
41 headPS, -- :: PackedString -> Char
42 tailPS, -- :: PackedString -> PackedString
43 nullPS, -- :: PackedString -> Bool
44 appendPS, -- :: PackedString -> PackedString -> PackedString
45 lengthPS, -- :: PackedString -> Int
46 indexPS, -- :: PackedString -> Int -> Char
47 mapPS, -- :: (Char -> Char) -> PackedString -> PackedString
48 filterPS, -- :: (Char -> Bool) -> PackedString -> PackedString
49 reversePS, -- :: PackedString -> PackedString
50 concatPS, -- :: [PackedString] -> PackedString
51 elemPS, -- :: Char -> PackedString -> Bool
52 substrPS, -- :: PackedString -> Int -> Int -> PackedString
53 takePS, -- :: Int -> PackedString -> PackedString
54 dropPS, -- :: Int -> PackedString -> PackedString
55 splitAtPS, -- :: Int -> PackedString -> (PackedString, PackedString)
56
57 foldlPS, -- :: (a -> Char -> a) -> a -> PackedString -> a
58 foldrPS, -- :: (Char -> a -> a) -> a -> PackedString -> a
59 takeWhilePS, -- :: (Char -> Bool) -> PackedString -> PackedString
60 dropWhilePS, -- :: (Char -> Bool) -> PackedString -> PackedString
61 spanPS, -- :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
62 breakPS, -- :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
63 linesPS, -- :: PackedString -> [PackedString]
64 unlinesPS, -- :: [PackedString] -> PackedString
65 wordsPS, -- :: PackedString -> [PackedString]
66 unwordsPS, -- :: [PackedString] -> PackedString
67 splitPS, -- :: Char -> PackedString -> [PackedString]
68 splitWithPS, -- :: (Char -> Bool) -> PackedString -> [PackedString]
69
70 joinPS, -- :: PackedString -> [PackedString] -> PackedString
71
72 ) where
73
74 import Prelude
75
76 #ifndef __NHC__
77
78 import Data.Array.Unboxed
79 import Data.Array.IO
80 import Data.Typeable
81 import Data.Char
82
83 import System.IO
84
85 -- -----------------------------------------------------------------------------
86 -- PackedString type declaration
87
88 -- | A space-efficient representation of a 'String', which supports various
89 -- efficient operations. A 'PackedString' contains full Unicode 'Char's.
90 newtype PackedString = PS (UArray Int Char)
91
92 -- ToDo: we could support "slices", i.e. include offset and length fields into
93 -- the string, so that operations like take/drop could be O(1). Perhaps making
94 -- a slice should be conditional on the ratio of the slice/string size to
95 -- limit memory leaks.
96
97 instance Eq PackedString where
98 (PS x) == (PS y) = x == y
99
100 instance Ord PackedString where
101 compare (PS x) (PS y) = compare x y
102
103 --instance Read PackedString: ToDo
104
105 instance Show PackedString where
106 showsPrec p ps r = showsPrec p (unpackPS ps) r
107
108 #include "Typeable.h"
109 INSTANCE_TYPEABLE0(PackedString,packedStringTc,"PackedString")
110
111 -- -----------------------------------------------------------------------------
112 -- Constructor functions
113
114 -- | The 'nilPS' value is the empty string.
115 nilPS :: PackedString
116 nilPS = PS (array (0,-1) [])
117
118 -- | The 'consPS' function prepends the given character to the
119 -- given string.
120 consPS :: Char -> PackedString -> PackedString
121 consPS c cs = packString (c : (unpackPS cs)) -- ToDo:better
122
123 -- | Convert a 'String' into a 'PackedString'
124 packString :: String -> PackedString
125 packString str = packNChars (length str) str
126
127 -- | The 'packNChars' function creates a 'PackedString' out of the
128 -- first @len@ elements of the given 'String'.
129 packNChars :: Int -> [Char] -> PackedString
130 packNChars len str = PS (listArray (0,len-1) str)
131
132 -- -----------------------------------------------------------------------------
133 -- Destructor functions (taking PackedStrings apart)
134
135 -- | Convert a 'PackedString' into a 'String'
136 unpackPS :: PackedString -> String
137 unpackPS (PS ps) = elems ps
138
139 -- -----------------------------------------------------------------------------
140 -- List-mimicking functions for PackedStrings
141
142 -- | The 'lengthPS' function returns the length of the input list. Analogous to 'length'.
143 lengthPS :: PackedString -> Int
144 lengthPS (PS ps) = rangeSize (bounds ps)
145
146 -- | The 'indexPS' function returns the character in the string at the given position.
147 indexPS :: PackedString -> Int -> Char
148 indexPS (PS ps) i = ps ! i
149
150 -- | The 'headPS' function returns the first element of a 'PackedString' or throws an
151 -- error if the string is empty.
152 headPS :: PackedString -> Char
153 headPS ps
154 | nullPS ps = error "Data.PackedString.headPS: head []"
155 | otherwise = indexPS ps 0
156
157 -- | The 'tailPS' function returns the tail of a 'PackedString' or throws an error
158 -- if the string is empty.
159 tailPS :: PackedString -> PackedString
160 tailPS ps
161 | len <= 0 = error "Data.PackedString.tailPS: tail []"
162 | len == 1 = nilPS
163 | otherwise = substrPS ps 1 (len - 1)
164 where
165 len = lengthPS ps
166
167 -- | The 'nullPS' function returns True iff the argument is null.
168 nullPS :: PackedString -> Bool
169 nullPS (PS ps) = rangeSize (bounds ps) == 0
170
171 -- | The 'appendPS' function appends the second string onto the first.
172 appendPS :: PackedString -> PackedString -> PackedString
173 appendPS xs ys
174 | nullPS xs = ys
175 | nullPS ys = xs
176 | otherwise = concatPS [xs,ys]
177
178 -- | The 'mapPS' function applies a function to each character in the string.
179 mapPS :: (Char -> Char) -> PackedString -> PackedString
180 mapPS f (PS ps) = PS (amap f ps)
181
182 -- | The 'filterPS' function filters out the appropriate substring.
183 filterPS :: (Char -> Bool) -> PackedString -> PackedString {-or String?-}
184 filterPS pred ps = packString (filter pred (unpackPS ps))
185
186 -- | The 'foldlPS' function behaves like 'foldl' on 'PackedString's.
187 foldlPS :: (a -> Char -> a) -> a -> PackedString -> a
188 foldlPS f b ps = foldl f b (unpackPS ps)
189
190 -- | The 'foldrPS' function behaves like 'foldr' on 'PackedString's.
191 foldrPS :: (Char -> a -> a) -> a -> PackedString -> a
192 foldrPS f v ps = foldr f v (unpackPS ps)
193
194 -- | The 'takePS' function takes the first @n@ characters of a 'PackedString'.
195 takePS :: Int -> PackedString -> PackedString
196 takePS n ps = substrPS ps 0 (n-1)
197
198 -- | The 'dropPS' function drops the first @n@ characters of a 'PackedString'.
199 dropPS :: Int -> PackedString -> PackedString
200 dropPS n ps = substrPS ps n (lengthPS ps - 1)
201
202 -- | The 'splitWithPS' function splits a 'PackedString' at a given index.
203 splitAtPS :: Int -> PackedString -> (PackedString, PackedString)
204 splitAtPS n ps = (takePS n ps, dropPS n ps)
205
206 -- | The 'takeWhilePS' function is analogous to the 'takeWhile' function.
207 takeWhilePS :: (Char -> Bool) -> PackedString -> PackedString
208 takeWhilePS pred ps = packString (takeWhile pred (unpackPS ps))
209
210 -- | The 'dropWhilePS' function is analogous to the 'dropWhile' function.
211 dropWhilePS :: (Char -> Bool) -> PackedString -> PackedString
212 dropWhilePS pred ps = packString (dropWhile pred (unpackPS ps))
213
214 -- | The 'elemPS' function returns True iff the given element is in the string.
215 elemPS :: Char -> PackedString -> Bool
216 elemPS c ps = c `elem` unpackPS ps
217
218 -- | The 'spanPS' function returns a pair containing the result of
219 -- running both 'takeWhilePS' and 'dropWhilePS'.
220 spanPS :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
221 spanPS p ps = (takeWhilePS p ps, dropWhilePS p ps)
222
223 -- | The 'breakPS' function breaks a string at the first position which
224 -- satisfies the predicate.
225 breakPS :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
226 breakPS p ps = spanPS (not . p) ps
227
228 -- | The 'linesPS' function splits the input on line-breaks.
229 linesPS :: PackedString -> [PackedString]
230 linesPS ps = splitPS '\n' ps
231
232 -- | The 'unlinesPS' function concatenates the input list after
233 -- interspersing newlines.
234 unlinesPS :: [PackedString] -> PackedString
235 unlinesPS = joinPS (packString "\n")
236
237 -- | The 'wordsPS' function is analogous to the 'words' function.
238 wordsPS :: PackedString -> [PackedString]
239 wordsPS ps = filter (not.nullPS) (splitWithPS isSpace ps)
240
241 -- | The 'unwordsPS' function is analogous to the 'unwords' function.
242 unwordsPS :: [PackedString] -> PackedString
243 unwordsPS = joinPS (packString " ")
244
245 -- | The 'reversePS' function reverses the string.
246 reversePS :: PackedString -> PackedString
247 reversePS ps = packString (reverse (unpackPS ps))
248
249 -- | The 'concatPS' function concatenates a list of 'PackedString's.
250 concatPS :: [PackedString] -> PackedString
251 concatPS pss = packString (concat (map unpackPS pss))
252
253 ------------------------------------------------------------
254
255 -- | The 'joinPS' function takes a 'PackedString' and a list of 'PackedString's
256 -- and concatenates the list after interspersing the first argument between
257 -- each element of the list.
258 joinPS :: PackedString -> [PackedString] -> PackedString
259 joinPS filler pss = concatPS (splice pss)
260 where
261 splice [] = []
262 splice [x] = [x]
263 splice (x:y:xs) = x:filler:splice (y:xs)
264
265 -- ToDo: the obvious generalisation
266 {-
267 Some properties that hold:
268
269 * splitPS x ls = ls'
270 where False = any (map (x `elemPS`) ls')
271
272 * joinPS (packString [x]) (splitPS x ls) = ls
273 -}
274
275 -- | The 'splitPS' function splits the input string on each occurrence of the given 'Char'.
276 splitPS :: Char -> PackedString -> [PackedString]
277 splitPS c = splitWithPS (== c)
278
279 -- | The 'splitWithPS' function takes a character predicate and splits the input string
280 -- at each character which satisfies the predicate.
281 splitWithPS :: (Char -> Bool) -> PackedString -> [PackedString]
282 splitWithPS pred (PS ps) =
283 splitify 0
284 where
285 len = lengthPS (PS ps)
286
287 splitify n
288 | n >= len = []
289 | otherwise =
290 let
291 break_pt = first_pos_that_satisfies pred ps len n
292 in
293 if break_pt == n then -- immediate match, empty substring
294 nilPS
295 : splitify (break_pt + 1)
296 else
297 substrPS (PS ps) n (break_pt - 1) -- leave out the matching character
298 : splitify (break_pt + 1)
299
300 first_pos_that_satisfies pred ps len n =
301 case [ m | m <- [n..len-1], pred (ps ! m) ] of
302 [] -> len
303 (m:_) -> m
304
305 -- -----------------------------------------------------------------------------
306 -- Local utility functions
307
308 -- The definition of @_substrPS@ is essentially:
309 -- @take (end - begin + 1) (drop begin str)@.
310
311 -- | The 'substrPS' function takes a 'PackedString' and two indices
312 -- and returns the substring of the input string between (and including)
313 -- these indices.
314 substrPS :: PackedString -> Int -> Int -> PackedString
315 substrPS (PS ps) begin end = packString [ ps ! i | i <- [begin..end] ]
316
317 -- -----------------------------------------------------------------------------
318 -- hPutPS
319
320 -- | Outputs a 'PackedString' to the specified 'Handle'.
321 --
322 -- NOTE: the representation of the 'PackedString' in the file is assumed to
323 -- be in the ISO-8859-1 encoding. In other words, only the least significant
324 -- byte is taken from each character in the 'PackedString'.
325 hPutPS :: Handle -> PackedString -> IO ()
326 hPutPS h (PS ps) = do
327 let l = lengthPS (PS ps)
328 arr <- newArray_ (0, l-1)
329 sequence_ [ writeArray arr i (fromIntegral (ord (ps ! i))) | i <- [0..l-1] ]
330 hPutArray h arr l
331
332 -- -----------------------------------------------------------------------------
333 -- hGetPS
334
335 -- | Read a 'PackedString' directly from the specified 'Handle'.
336 -- This is far more efficient than reading the characters into a 'String'
337 -- and then using 'packString'.
338 --
339 -- NOTE: as with 'hPutPS', the string representation in the file is
340 -- assumed to be ISO-8859-1.
341 hGetPS :: Handle -> Int -> IO PackedString
342 hGetPS h i = do
343 arr <- newArray_ (0, i-1)
344 l <- hGetArray h arr i
345 chars <- mapM (\i -> readArray arr i >>= return.chr.fromIntegral) [0..l-1]
346 return (packNChars l chars)
347
348 #else /* __NHC__ */
349
350 --import Prelude hiding (append, break, concat, cons, drop, dropWhile,
351 -- filter, foldl, foldr, head, length, lines, map,
352 -- nil, null, reverse, span, splitAt, subst, tail,
353 -- take, takeWhile, unlines, unwords, words)
354 -- also hiding: Ix(..), Functor(..)
355 import qualified NHC.PackedString
356 import NHC.PackedString (PackedString,packString,unpackPS)
357 import List (intersperse)
358
359
360 nilPS :: PackedString
361 consPS :: Char -> PackedString -> PackedString
362 headPS :: PackedString -> Char
363 tailPS :: PackedString -> PackedString
364 nullPS :: PackedString -> Bool
365 appendPS :: PackedString -> PackedString -> PackedString
366 lengthPS :: PackedString -> Int
367 indexPS :: PackedString -> Int -> Char
368 mapPS :: (Char -> Char) -> PackedString -> PackedString
369 filterPS :: (Char -> Bool) -> PackedString -> PackedString
370 reversePS :: PackedString -> PackedString
371 concatPS :: [PackedString] -> PackedString
372 elemPS :: Char -> PackedString -> Bool
373 substrPS :: PackedString -> Int -> Int -> PackedString
374 takePS :: Int -> PackedString -> PackedString
375 dropPS :: Int -> PackedString -> PackedString
376 splitAtPS :: Int -> PackedString -> (PackedString, PackedString)
377
378 foldlPS :: (a -> Char -> a) -> a -> PackedString -> a
379 foldrPS :: (Char -> a -> a) -> a -> PackedString -> a
380 takeWhilePS :: (Char -> Bool) -> PackedString -> PackedString
381 dropWhilePS :: (Char -> Bool) -> PackedString -> PackedString
382 spanPS :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
383 breakPS :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
384 linesPS :: PackedString -> [PackedString]
385 unlinesPS :: [PackedString] -> PackedString
386
387 wordsPS :: PackedString -> [PackedString]
388 unwordsPS :: [PackedString] -> PackedString
389 splitPS :: Char -> PackedString -> [PackedString]
390 splitWithPS :: (Char -> Bool) -> PackedString -> [PackedString]
391 joinPS :: PackedString -> [PackedString] -> PackedString
392
393 nilPS = NHC.PackedString.nil
394 consPS = NHC.PackedString.cons
395 headPS = NHC.PackedString.head
396 tailPS = NHC.PackedString.tail
397 nullPS = NHC.PackedString.null
398 appendPS = NHC.PackedString.append
399 lengthPS = NHC.PackedString.length
400 indexPS p i = (unpackPS p) !! i
401 mapPS = NHC.PackedString.map
402 filterPS = NHC.PackedString.filter
403 reversePS = NHC.PackedString.reverse
404 concatPS = NHC.PackedString.concat
405 elemPS c p = c `elem` unpackPS p
406 substrPS = NHC.PackedString.substr
407 takePS = NHC.PackedString.take
408 dropPS = NHC.PackedString.drop
409 splitAtPS = NHC.PackedString.splitAt
410
411 foldlPS = NHC.PackedString.foldl
412 foldrPS = NHC.PackedString.foldr
413 takeWhilePS = NHC.PackedString.takeWhile
414 dropWhilePS = NHC.PackedString.dropWhile
415 spanPS = NHC.PackedString.span
416 breakPS = NHC.PackedString.break
417 linesPS = NHC.PackedString.lines
418 unlinesPS = NHC.PackedString.unlines
419
420 wordsPS = NHC.PackedString.words
421 unwordsPS = NHC.PackedString.unwords
422 splitPS c = splitWithPS (==c)
423 splitWithPS p =
424 map packString . split' p [] . unpackPS
425 where
426 split' :: (Char->Bool) -> String -> String -> [String]
427 split' pred [] [] = []
428 split' pred acc [] = [reverse acc]
429 split' pred acc (x:xs) | pred x = reverse acc: split' pred [] xs
430 | otherwise = split' pred (x:acc) xs
431
432 joinPS sep = concatPS . intersperse sep
433
434 #endif