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