1 -----------------------------------------------------------------------------
3 -- Module : Data.PackedString
4 -- Copyright : (c) The University of Glasgow 2001
5 -- License : BSD-style (see the file libraries/base/LICENSE)
7 -- Maintainer : libraries@haskell.org
8 -- Stability : experimental
9 -- Portability : portable
11 -- An efficient implementation of strings.
13 -----------------------------------------------------------------------------
15 -- Original GHC implementation by Bryan O\'Sullivan,
16 -- rewritten to use UArray by Simon Marlow.
18 module Data.PackedString (
19 -- * The @PackedString@ type
20 PackedString, -- abstract, instances: Eq, Ord, Show, Typeable
22 -- * Converting to and from @PackedString@s
23 packString, -- :: String -> PackedString
24 unpackPS, -- :: PackedString -> String
26 #ifdef __GLASGOW_HASKELL__
27 -- * I\/O with @PackedString@s
28 hPutPS, -- :: Handle -> PackedString -> IO ()
29 hGetPS, -- :: Handle -> Int -> IO PackedString
32 -- * List-like manipulation functions
33 nilPS, -- :: PackedString
34 consPS, -- :: Char -> PackedString -> PackedString
35 headPS, -- :: PackedString -> Char
36 tailPS, -- :: PackedString -> PackedString
37 nullPS, -- :: PackedString -> Bool
38 appendPS, -- :: PackedString -> PackedString -> PackedString
39 lengthPS, -- :: PackedString -> Int
40 indexPS, -- :: PackedString -> Int -> Char
41 mapPS, -- :: (Char -> Char) -> PackedString -> PackedString
42 filterPS, -- :: (Char -> Bool) -> PackedString -> PackedString
43 reversePS, -- :: PackedString -> PackedString
44 concatPS, -- :: [PackedString] -> PackedString
45 elemPS, -- :: Char -> PackedString -> Bool
46 substrPS, -- :: PackedString -> Int -> Int -> PackedString
47 takePS, -- :: Int -> PackedString -> PackedString
48 dropPS, -- :: Int -> PackedString -> PackedString
49 splitAtPS, -- :: Int -> PackedString -> (PackedString, PackedString)
51 foldlPS, -- :: (a -> Char -> a) -> a -> PackedString -> a
52 foldrPS, -- :: (Char -> a -> a) -> a -> PackedString -> a
53 takeWhilePS, -- :: (Char -> Bool) -> PackedString -> PackedString
54 dropWhilePS, -- :: (Char -> Bool) -> PackedString -> PackedString
55 spanPS, -- :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
56 breakPS, -- :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
57 linesPS, -- :: PackedString -> [PackedString]
58 unlinesPS, -- :: [PackedString] -> PackedString
59 wordsPS, -- :: PackedString -> [PackedString]
60 unwordsPS, -- :: [PackedString] -> PackedString
61 splitPS, -- :: Char -> PackedString -> [PackedString]
62 splitWithPS, -- :: (Char -> Bool) -> PackedString -> [PackedString]
64 joinPS, -- :: PackedString -> [PackedString] -> PackedString
72 import Data.Array.Unboxed
79 -- -----------------------------------------------------------------------------
80 -- PackedString type declaration
82 -- | A space-efficient representation of a 'String', which supports various
83 -- efficient operations. A 'PackedString' contains full Unicode 'Char's.
84 newtype PackedString = PS (UArray Int Char)
86 instance Eq PackedString where
87 (PS x) == (PS y) = x == y
89 instance Ord PackedString where
90 compare (PS x) (PS y) = compare x y
92 --instance Read PackedString: ToDo
94 instance Show PackedString where
95 showsPrec p ps r = showsPrec p (unpackPS ps) r
98 INSTANCE_TYPEABLE0(PackedString,packedStringTc,"PackedString")
100 -- -----------------------------------------------------------------------------
101 -- Constructor functions
103 nilPS :: PackedString
104 nilPS = PS (array (0,-1) [])
106 consPS :: Char -> PackedString -> PackedString
107 consPS c cs = packString (c : (unpackPS cs)) -- ToDo:better
109 -- | Convert a 'String' into a 'PackedString'
110 packString :: String -> PackedString
111 packString str = packNChars (length str) str
113 packNChars :: Int -> [Char] -> PackedString
114 packNChars len str = PS (array (0,len-1) (zip [0..] str))
116 -- -----------------------------------------------------------------------------
117 -- Destructor functions (taking PackedStrings apart)
119 -- | Convert a 'PackedString' into a 'String'
120 unpackPS :: PackedString -> String
121 unpackPS (PS ps) = elems ps
123 -- -----------------------------------------------------------------------------
124 -- List-mimicking functions for PackedStrings
126 lengthPS :: PackedString -> Int
127 lengthPS (PS ps) = rangeSize (bounds ps)
129 indexPS :: PackedString -> Int -> Char
130 indexPS (PS ps) i = ps ! i
132 headPS :: PackedString -> Char
134 | nullPS ps = error "Data.PackedString.headPS: head []"
135 | otherwise = indexPS ps 0
137 tailPS :: PackedString -> PackedString
139 | len <= 0 = error "Data.PackedString.tailPS: tail []"
141 | otherwise = substrPS ps 1 (len - 1)
145 nullPS :: PackedString -> Bool
146 nullPS (PS ps) = rangeSize (bounds ps) == 0
148 appendPS :: PackedString -> PackedString -> PackedString
152 | otherwise = concatPS [xs,ys]
154 mapPS :: (Char -> Char) -> PackedString -> PackedString
155 mapPS f (PS ps) = PS (amap f ps)
157 filterPS :: (Char -> Bool) -> PackedString -> PackedString {-or String?-}
158 filterPS pred ps = packString (filter pred (unpackPS ps))
160 foldlPS :: (a -> Char -> a) -> a -> PackedString -> a
161 foldlPS f b ps = foldl f b (unpackPS ps)
163 foldrPS :: (Char -> a -> a) -> a -> PackedString -> a
164 foldrPS f v ps = foldr f v (unpackPS ps)
166 takePS :: Int -> PackedString -> PackedString
167 takePS n ps = substrPS ps 0 (n-1)
169 dropPS :: Int -> PackedString -> PackedString
170 dropPS n ps = substrPS ps n (lengthPS ps - 1)
172 splitAtPS :: Int -> PackedString -> (PackedString, PackedString)
173 splitAtPS n ps = (takePS n ps, dropPS n ps)
175 takeWhilePS :: (Char -> Bool) -> PackedString -> PackedString
176 takeWhilePS pred ps = packString (takeWhile pred (unpackPS ps))
178 dropWhilePS :: (Char -> Bool) -> PackedString -> PackedString
179 dropWhilePS pred ps = packString (dropWhile pred (unpackPS ps))
181 elemPS :: Char -> PackedString -> Bool
182 elemPS c ps = c `elem` unpackPS ps
184 spanPS :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
185 spanPS p ps = (takeWhilePS p ps, dropWhilePS p ps)
187 breakPS :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
188 breakPS p ps = spanPS (not . p) ps
190 linesPS :: PackedString -> [PackedString]
191 linesPS ps = splitPS '\n' ps
193 unlinesPS :: [PackedString] -> PackedString
194 unlinesPS = joinPS (packString "\n")
196 wordsPS :: PackedString -> [PackedString]
197 wordsPS ps = filter (not.nullPS) (splitWithPS isSpace ps)
199 unwordsPS :: [PackedString] -> PackedString
200 unwordsPS = joinPS (packString " ")
202 reversePS :: PackedString -> PackedString
203 reversePS ps = packString (reverse (unpackPS ps))
205 concatPS :: [PackedString] -> PackedString
206 concatPS pss = packString (concat (map unpackPS pss))
208 ------------------------------------------------------------
210 joinPS :: PackedString -> [PackedString] -> PackedString
211 joinPS filler pss = concatPS (splice pss)
215 splice (x:y:xs) = x:filler:splice (y:xs)
217 -- ToDo: the obvious generalisation
219 Some properties that hold:
222 where False = any (map (x `elemPS`) ls')
224 * joinPS (packString [x]) (splitPS x ls) = ls
227 splitPS :: Char -> PackedString -> [PackedString]
228 splitPS c = splitWithPS (== c)
230 splitWithPS :: (Char -> Bool) -> PackedString -> [PackedString]
231 splitWithPS pred (PS ps) =
234 len = lengthPS (PS ps)
240 break_pt = first_pos_that_satisfies pred ps len n
242 if break_pt == n then -- immediate match, empty substring
244 : splitify (break_pt + 1)
246 substrPS (PS ps) n (break_pt - 1) -- leave out the matching character
247 : splitify (break_pt + 1)
249 first_pos_that_satisfies pred ps len n =
250 case [ m | m <- [n..len-1], pred (ps ! m) ] of
254 -- -----------------------------------------------------------------------------
255 -- Local utility functions
257 -- The definition of @_substrPS@ is essentially:
258 -- @take (end - begin + 1) (drop begin str)@.
260 substrPS :: PackedString -> Int -> Int -> PackedString
261 substrPS (PS ps) begin end = packString [ ps ! i | i <- [begin..end] ]
263 #ifdef __GLASGOW_HASKELL__
264 -- -----------------------------------------------------------------------------
267 -- | Outputs a 'PackedString' to the specified 'Handle' (GHC only).
269 -- NOTE: the representation of the 'PackedString' in the file is assumed to
270 -- be in the ISO-8859-1 encoding. In other words, only the least signficant
271 -- byte is taken from each character in the 'PackedString'.
272 hPutPS :: Handle -> PackedString -> IO ()
273 hPutPS h (PS ps) = do
274 let l = lengthPS (PS ps)
275 arr <- newArray_ (0, l-1)
276 sequence_ [ writeArray arr i (fromIntegral (ord (ps ! i))) | i <- [0..l-1] ]
279 -- -----------------------------------------------------------------------------
282 -- | Read a 'PackedString' directly from the specified 'Handle' (GHC only).
283 -- This is far more efficient than reading the characters into a 'String'
284 -- and then using 'packString'.
286 -- NOTE: as with 'hPutPS', the string representation in the file is
287 -- assumed to be ISO-8859-1.
288 hGetPS :: Handle -> Int -> IO PackedString
290 arr <- newArray_ (0, i-1)
291 l <- hGetArray h arr i
292 chars <- mapM (\i -> readArray arr i >>= return.chr.fromIntegral) [0..l-1]
293 return (packString chars)
294 #endif /* __GLASGOW_HASKELL__ */
298 --import Prelude hiding (append, break, concat, cons, drop, dropWhile,
299 -- filter, foldl, foldr, head, length, lines, map,
300 -- nil, null, reverse, span, splitAt, subst, tail,
301 -- take, takeWhile, unlines, unwords, words)
302 -- also hiding: Ix(..), Functor(..)
303 import qualified NHC.PackedString
304 import NHC.PackedString (PackedString,packString,unpackPS)
305 import List (intersperse)
308 nilPS :: PackedString
309 consPS :: Char -> PackedString -> PackedString
310 headPS :: PackedString -> Char
311 tailPS :: PackedString -> PackedString
312 nullPS :: PackedString -> Bool
313 appendPS :: PackedString -> PackedString -> PackedString
314 lengthPS :: PackedString -> Int
315 indexPS :: PackedString -> Int -> Char
316 mapPS :: (Char -> Char) -> PackedString -> PackedString
317 filterPS :: (Char -> Bool) -> PackedString -> PackedString
318 reversePS :: PackedString -> PackedString
319 concatPS :: [PackedString] -> PackedString
320 elemPS :: Char -> PackedString -> Bool
321 substrPS :: PackedString -> Int -> Int -> PackedString
322 takePS :: Int -> PackedString -> PackedString
323 dropPS :: Int -> PackedString -> PackedString
324 splitAtPS :: Int -> PackedString -> (PackedString, PackedString)
326 foldlPS :: (a -> Char -> a) -> a -> PackedString -> a
327 foldrPS :: (Char -> a -> a) -> a -> PackedString -> a
328 takeWhilePS :: (Char -> Bool) -> PackedString -> PackedString
329 dropWhilePS :: (Char -> Bool) -> PackedString -> PackedString
330 spanPS :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
331 breakPS :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
332 linesPS :: PackedString -> [PackedString]
333 unlinesPS :: [PackedString] -> PackedString
335 wordsPS :: PackedString -> [PackedString]
336 unwordsPS :: [PackedString] -> PackedString
337 splitPS :: Char -> PackedString -> [PackedString]
338 splitWithPS :: (Char -> Bool) -> PackedString -> [PackedString]
339 joinPS :: PackedString -> [PackedString] -> PackedString
341 nilPS = NHC.PackedString.nil
342 consPS = NHC.PackedString.cons
343 headPS = NHC.PackedString.head
344 tailPS = NHC.PackedString.tail
345 nullPS = NHC.PackedString.null
346 appendPS = NHC.PackedString.append
347 lengthPS = NHC.PackedString.length
348 indexPS p i = (unpackPS p) !! i
349 mapPS = NHC.PackedString.map
350 filterPS = NHC.PackedString.filter
351 reversePS = NHC.PackedString.reverse
352 concatPS = NHC.PackedString.concat
353 elemPS c p = c `elem` unpackPS p
354 substrPS = NHC.PackedString.substr
355 takePS = NHC.PackedString.take
356 dropPS = NHC.PackedString.drop
357 splitAtPS = NHC.PackedString.splitAt
359 foldlPS = NHC.PackedString.foldl
360 foldrPS = NHC.PackedString.foldr
361 takeWhilePS = NHC.PackedString.takeWhile
362 dropWhilePS = NHC.PackedString.dropWhile
363 spanPS = NHC.PackedString.span
364 breakPS = NHC.PackedString.break
365 linesPS = NHC.PackedString.lines
366 unlinesPS = NHC.PackedString.unlines
368 wordsPS = NHC.PackedString.words
369 unwordsPS = NHC.PackedString.unwords
370 splitPS c = splitWithPS (==c)
372 map packString . split' p [] . unpackPS
374 split' :: (Char->Bool) -> String -> String -> [String]
375 split' pred [] [] = []
376 split' pred acc [] = [reverse acc]
377 split' pred acc (x:xs) | pred x = reverse acc: split' pred [] xs
378 | otherwise = split' pred (x:acc) xs
380 joinPS sep = concatPS . intersperse sep