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)