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)