fd4528b5526bd3734972a380b6a7e5305ecf5bff
[packages/base.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/core/LICENSE)
6 --
7 -- Maintainer : libraries@haskell.org
8 -- Stability : experimental
9 -- Portability : portable
10 --
11 -- The PackedString type, and associated operations.
12 --
13 -- Original GHC implementation by Bryan O\'Sullivan,
14 -- rewritten to use UArray by Simon Marlow.
15 --
16 -----------------------------------------------------------------------------
17
18 module Data.PackedString (
19 PackedString, -- abstract, instances: Eq, Ord, Show, Typeable
20
21 -- Creating the beasts
22 packString, -- :: [Char] -> PackedString
23 unpackPS, -- :: PackedString -> [Char]
24
25 hPutPS, -- :: Handle -> PackedString -> IO ()
26 hGetPS, -- :: Handle -> Int -> IO PackedString
27
28 nilPS, -- :: PackedString
29 consPS, -- :: Char -> PackedString -> PackedString
30 headPS, -- :: PackedString -> Char
31 tailPS, -- :: PackedString -> PackedString
32 nullPS, -- :: PackedString -> Bool
33 appendPS, -- :: PackedString -> PackedString -> PackedString
34 lengthPS, -- :: PackedString -> Int
35 indexPS, -- :: PackedString -> Int -> Char
36 mapPS, -- :: (Char -> Char) -> PackedString -> PackedString
37 filterPS, -- :: (Char -> Bool) -> PackedString -> PackedString
38 reversePS, -- :: PackedString -> PackedString
39 concatPS, -- :: [PackedString] -> PackedString
40 elemPS, -- :: Char -> PackedString -> Bool
41 substrPS, -- :: PackedString -> Int -> Int -> PackedString
42 takePS, -- :: Int -> PackedString -> PackedString
43 dropPS, -- :: Int -> PackedString -> PackedString
44 splitAtPS, -- :: Int -> PackedString -> (PackedString, PackedString)
45
46 foldlPS, -- :: (a -> Char -> a) -> a -> PackedString -> a
47 foldrPS, -- :: (Char -> a -> a) -> a -> PackedString -> a
48 takeWhilePS, -- :: (Char -> Bool) -> PackedString -> PackedString
49 dropWhilePS, -- :: (Char -> Bool) -> PackedString -> PackedString
50 spanPS, -- :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
51 breakPS, -- :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
52 linesPS, -- :: PackedString -> [PackedString]
53
54 wordsPS, -- :: PackedString -> [PackedString]
55 splitPS, -- :: Char -> PackedString -> [PackedString]
56 splitWithPS, -- :: (Char -> Bool) -> PackedString -> [PackedString]
57
58 -- joinPS, -- :: PackedString -> [PackedString] -> PackedString
59
60 ) where
61
62 import Prelude
63
64 import Data.Array.Unboxed
65 import Data.Array.IO
66 import Data.Dynamic
67 import Data.Char
68
69 import System.IO
70
71 -- -----------------------------------------------------------------------------
72 -- PackedString type declaration
73
74 newtype PackedString = PS (UArray Int Char)
75
76 instance Eq PackedString where
77 (PS x) == (PS y) = x == y
78
79 instance Ord PackedString where
80 compare (PS x) (PS y) = compare x y
81
82 --instance Read PackedString: ToDo
83
84 instance Show PackedString where
85 showsPrec p ps r = showsPrec p (unpackPS ps) r
86
87 #include "Dynamic.h"
88 INSTANCE_TYPEABLE0(PackedString,packedStringTc,"PackedString")
89
90 -- -----------------------------------------------------------------------------
91 -- Constructor functions
92
93 nilPS :: PackedString
94 nilPS = PS (array (0,-1) [])
95
96 consPS :: Char -> PackedString -> PackedString
97 consPS c cs = packString (c : (unpackPS cs)) -- ToDo:better
98
99 packString :: [Char] -> PackedString
100 packString str = packNChars (length str) str
101
102 packNChars :: Int -> [Char] -> PackedString
103 packNChars len str = PS (array (0,len-1) (zip [0..] str))
104
105 -- -----------------------------------------------------------------------------
106 -- Destructor functions (taking PackedStrings apart)
107
108 unpackPS :: PackedString -> [Char]
109 unpackPS (PS ps) = elems ps
110
111 -- -----------------------------------------------------------------------------
112 -- List-mimicking functions for PackedStrings
113
114 lengthPS :: PackedString -> Int
115 lengthPS (PS ps) = rangeSize (bounds ps)
116
117 indexPS :: PackedString -> Int -> Char
118 indexPS (PS ps) i = ps ! i
119
120 headPS :: PackedString -> Char
121 headPS ps
122 | nullPS ps = error "Data.PackedString.headPS: head []"
123 | otherwise = indexPS ps 0
124
125 tailPS :: PackedString -> PackedString
126 tailPS ps
127 | len <= 0 = error "Data.PackedString.tailPS: tail []"
128 | len == 1 = nilPS
129 | otherwise = substrPS ps 1 (len - 1)
130 where
131 len = lengthPS ps
132
133 nullPS :: PackedString -> Bool
134 nullPS (PS ps) = rangeSize (bounds ps) == 0
135
136 appendPS :: PackedString -> PackedString -> PackedString
137 appendPS xs ys
138 | nullPS xs = ys
139 | nullPS ys = xs
140 | otherwise = concatPS [xs,ys]
141
142 mapPS :: (Char -> Char) -> PackedString -> PackedString
143 mapPS f (PS ps) = PS (amap f ps)
144
145 filterPS :: (Char -> Bool) -> PackedString -> PackedString {-or String?-}
146 filterPS pred ps = packString (filter pred (unpackPS ps))
147
148 foldlPS :: (a -> Char -> a) -> a -> PackedString -> a
149 foldlPS f b ps = foldl f b (unpackPS ps)
150
151 foldrPS :: (Char -> a -> a) -> a -> PackedString -> a
152 foldrPS f v ps = foldr f v (unpackPS ps)
153
154 takePS :: Int -> PackedString -> PackedString
155 takePS n ps = substrPS ps 0 (n-1)
156
157 dropPS :: Int -> PackedString -> PackedString
158 dropPS n ps = substrPS ps n (lengthPS ps - 1)
159
160 splitAtPS :: Int -> PackedString -> (PackedString, PackedString)
161 splitAtPS n ps = (takePS n ps, dropPS n ps)
162
163 takeWhilePS :: (Char -> Bool) -> PackedString -> PackedString
164 takeWhilePS pred ps = packString (takeWhile pred (unpackPS ps))
165
166 dropWhilePS :: (Char -> Bool) -> PackedString -> PackedString
167 dropWhilePS pred ps = packString (dropWhile pred (unpackPS ps))
168
169 elemPS :: Char -> PackedString -> Bool
170 elemPS c ps = c `elem` unpackPS ps
171
172 spanPS :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
173 spanPS p ps = (takeWhilePS p ps, dropWhilePS p ps)
174
175 breakPS :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
176 breakPS p ps = spanPS (not . p) ps
177
178 linesPS :: PackedString -> [PackedString]
179 linesPS ps = splitPS '\n' ps
180
181 wordsPS :: PackedString -> [PackedString]
182 wordsPS ps = splitWithPS isSpace ps
183
184 reversePS :: PackedString -> PackedString
185 reversePS ps = packString (reverse (unpackPS ps))
186
187 concatPS :: [PackedString] -> PackedString
188 concatPS pss = packString (concat (map unpackPS pss))
189
190 ------------------------------------------------------------
191 {-
192 joinPS :: PackedString -> [PackedString] -> PackedString
193 joinPS filler pss = concatPS (splice pss)
194 where
195 splice [] = []
196 splice [x] = [x]
197 splice (x:y:xs) = x:filler:splice (y:xs)
198
199 -- ToDo: the obvious generalisation
200 {-
201 Some properties that hold:
202
203 * splitPS x ls = ls'
204 where False = any (map (x `elemPS`) ls')
205 False = any (map (nullPS) ls')
206
207 * all x's have been chopped out.
208 * no empty PackedStrings in returned list. A conseq.
209 of this is:
210 splitPS x nilPS = []
211
212
213 * joinPS (packString [x]) (_splitPS x ls) = ls
214
215 -}
216 -}
217
218 splitPS :: Char -> PackedString -> [PackedString]
219 splitPS c = splitWithPS (== c)
220
221 splitWithPS :: (Char -> Bool) -> PackedString -> [PackedString]
222 splitWithPS pred (PS ps) =
223 splitify 0
224 where
225 len = lengthPS (PS ps)
226
227 splitify n
228 | n >= len = []
229 | otherwise =
230 let
231 break_pt = first_pos_that_satisfies pred ps len n
232 in
233 if break_pt == n then -- immediate match, no substring to cut out.
234 splitify (break_pt + 1)
235 else
236 substrPS (PS ps) n (break_pt - 1) -- leave out the matching character
237 : splitify (break_pt + 1)
238
239 first_pos_that_satisfies pred ps len n =
240 case [ m | m <- [n..len], pred (ps ! m) ] of
241 [] -> len
242 (m:_) -> m
243
244 -- -----------------------------------------------------------------------------
245 -- Local utility functions
246
247 -- The definition of @_substrPS@ is essentially:
248 -- @take (end - begin + 1) (drop begin str)@.
249
250 substrPS :: PackedString -> Int -> Int -> PackedString
251 substrPS (PS ps) begin end = packString [ ps ! i | i <- [begin..end] ]
252
253 -- -----------------------------------------------------------------------------
254 -- hPutPS
255
256 hPutPS :: Handle -> PackedString -> IO ()
257 hPutPS h (PS ps) = do
258 let l = lengthPS (PS ps)
259 arr <- newArray_ (0, l-1)
260 sequence_ [ writeArray arr i (fromIntegral (ord (ps ! i))) | i <- [0..l-1] ]
261 hPutArray h arr l
262
263 -- -----------------------------------------------------------------------------
264 -- hGetPS
265
266 hGetPS :: Handle -> Int -> IO PackedString
267 hGetPS h i = do
268 arr <- newArray_ (0, i-1)
269 l <- hGetArray h arr i
270 chars <- mapM (\i -> readArray arr i >>= return.chr.fromIntegral) [0..l-1]
271 return (packString chars)