ghc/lib/std/Ix.lhs

   1 %
   2 % (c) The AQUA Project, Glasgow University, 1994-1999
   3 %
   4
   5 \section[Ix]{Module @Ix@}
   6
   7 \begin{code}
   8 {-# OPTIONS -fno-implicit-prelude #-}
   9
  10 module Ix
  11     (
  12         Ix
  13           ( range       -- :: (Ix a) => (a,a) -> [a]
  14           , index       -- :: (Ix a) => (a,a) -> a   -> Int
  15           , inRange     -- :: (Ix a) => (a,a) -> a   -> Bool
  16           )
  17     ,   rangeSize       -- :: (Ix a) => (a,a) -> Int
  18     -- Ix instances:
  19     --
  20     --  Ix Char
  21     --  Ix Int
  22     --  Ix Integer
  23     --  Ix Bool
  24     --  Ix Ordering
  25     --  Ix ()
  26     --  (Ix a, Ix b) => Ix (a, b)
  27     --  ...
  28
  29     -- Implementation checked wrt. Haskell 98 lib report, 1/99.
  30     ) where
  31
  32 import {-# SOURCE #-} PrelErr ( error )
  33 import PrelTup
  34 import PrelBase
  35 import PrelList( null )
  36 import PrelEnum
  37 import PrelShow
  38 import PrelNum
  39 \end{code}
  40
  41 %*********************************************************
  42 %*                                                      *
  43 \subsection{The @Ix@ class}
  44 %*                                                      *
  45 %*********************************************************
  46
  47 \begin{code}
  48 class  (Ord a) => Ix a  where
  49     range               :: (a,a) -> [a]
  50     index, unsafeIndex  :: (a,a) -> a -> Int
  51     inRange             :: (a,a) -> a -> Bool
  52
  53         -- Must specify one of index, unsafeIndex
  54     index b i | inRange b i = unsafeIndex b i
  55               | otherwise   = error "Error in array index"
  56     unsafeIndex b i = index b i
  57 \end{code}
  58
  59 %*********************************************************
  60 %*                                                      *
  61 \subsection{Instances of @Ix@}
  62 %*                                                      *
  63 %*********************************************************
  64
  65 \begin{code}
  66 -- abstract these errors from the relevant index functions so that
  67 -- the guts of the function will be small enough to inline.
  68
  69 {-# NOINLINE indexError #-}
  70 indexError :: Show a => (a,a) -> a -> String -> b
  71 indexError rng i tp
  72   = error (showString "Ix{" . showString tp . showString "}.index: Index " .
  73            showParen True (showsPrec 0 i) .
  74            showString " out of range " $
  75            showParen True (showsPrec 0 rng) "")
  76
  77 ----------------------------------------------------------------------
  78 instance  Ix Char  where
  79     range (m,n)
  80       | m <= n          =  [m..n]
  81       | otherwise       =  []
  82
  83     unsafeIndex (m,n) i = fromEnum i - fromEnum m
  84
  85     index b i | inRange b i =  unsafeIndex b i
  86               | otherwise   =  indexError b i "Char"
  87
  88     inRange (m,n) i     =  m <= i && i <= n
  89
  90 ----------------------------------------------------------------------
  91 instance  Ix Int  where
  92     range (m,n)
  93       | m <= n          =  [m..n]
  94       | otherwise       =  []
  95
  96     unsafeIndex (m,n) i = i - m
  97
  98     index b i | inRange b i =  unsafeIndex b i
  99               | otherwise   =  indexError b i "Int"
 100
 101     inRange (m,n) i     =  m <= i && i <= n
 102
 103
 104 ----------------------------------------------------------------------
 105 instance  Ix Integer  where
 106     range (m,n)
 107       | m <= n          =  [m..n]
 108       | otherwise       =  []
 109
 110     unsafeIndex (m,n) i   = fromInteger (i - m)
 111
 112     index b i | inRange b i =  unsafeIndex b i
 113               | otherwise   =  indexError b i "Integer"
 114
 115     inRange (m,n) i     =  m <= i && i <= n
 116
 117
 118 ----------------------------------------------------------------------
 119 instance Ix Bool where -- as derived
 120     range   (l,u)
 121       | l <= u    = map toEnum [fromEnum l .. fromEnum u]
 122       | otherwise = []
 123
 124     unsafeIndex (l,_) i = fromEnum i - fromEnum l
 125
 126     index b i | inRange b i =  unsafeIndex b i
 127               | otherwise   =  indexError b i "Bool"
 128
 129     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
 130
 131 ----------------------------------------------------------------------
 132 instance Ix Ordering where -- as derived
 133     range   (l,u)
 134       | l <= u    = map toEnum [fromEnum l .. fromEnum u]
 135       | otherwise = []
 136     unsafeIndex (l,_) i = fromEnum i - fromEnum l
 137     index b i | inRange b i =  unsafeIndex b i
 138               | otherwise   =  indexError b i "Ordering"
 139     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
 140
 141 ----------------------------------------------------------------------
 142 instance Ix () where
 143     {-# INLINE range #-}
 144     range   ((), ())    = [()]
 145     {-# INLINE unsafeIndex #-}
 146     unsafeIndex   ((), ()) () = 0
 147     {-# INLINE inRange #-}
 148     inRange ((), ()) () = True
 149     {-# INLINE index #-}
 150     index b i = unsafeIndex b i
 151
 152
 153 ----------------------------------------------------------------------
 154 instance (Ix a, Ix b) => Ix (a, b) where -- as derived
 155     {-# SPECIALISE instance Ix (Int,Int) #-}
 156
 157     {- INLINE range #-}
 158     range ((l1,l2),(u1,u2)) =
 159       [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]
 160
 161     {- INLINE unsafeIndex #-}
 162     unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) =
 163       unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2
 164
 165     {- INLINE inRange #-}
 166     inRange ((l1,l2),(u1,u2)) (i1,i2) =
 167       inRange (l1,u1) i1 && inRange (l2,u2) i2
 168
 169     -- Default method for index
 170
 171 ----------------------------------------------------------------------
 172 instance  (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3)  where
 173     {-# SPECIALISE instance Ix (Int,Int,Int) #-}
 174
 175     range ((l1,l2,l3),(u1,u2,u3)) =
 176         [(i1,i2,i3) | i1 <- range (l1,u1),
 177                       i2 <- range (l2,u2),
 178                       i3 <- range (l3,u3)]
 179
 180     unsafeIndex ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
 181       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 182       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 183       unsafeIndex (l1,u1) i1))
 184
 185     inRange ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
 186       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 187       inRange (l3,u3) i3
 188
 189     -- Default method for index
 190
 191 ----------------------------------------------------------------------
 192 instance  (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4)  where
 193     range ((l1,l2,l3,l4),(u1,u2,u3,u4)) =
 194       [(i1,i2,i3,i4) | i1 <- range (l1,u1),
 195                        i2 <- range (l2,u2),
 196                        i3 <- range (l3,u3),
 197                        i4 <- range (l4,u4)]
 198
 199     unsafeIndex ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
 200       unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
 201       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 202       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 203       unsafeIndex (l1,u1) i1)))
 204
 205     inRange ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
 206       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 207       inRange (l3,u3) i3 && inRange (l4,u4) i4
 208
 209     -- Default method for index
 210
 211 instance  (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5)  where
 212     range ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) =
 213       [(i1,i2,i3,i4,i5) | i1 <- range (l1,u1),
 214                           i2 <- range (l2,u2),
 215                           i3 <- range (l3,u3),
 216                           i4 <- range (l4,u4),
 217                           i5 <- range (l5,u5)]
 218
 219     unsafeIndex ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
 220       unsafeIndex (l5,u5) i5 + unsafeRangeSize (l5,u5) * (
 221       unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
 222       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 223       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 224       unsafeIndex (l1,u1) i1))))
 225
 226     inRange ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
 227       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 228       inRange (l3,u3) i3 && inRange (l4,u4) i4 &&
 229       inRange (l5,u5) i5
 230
 231     -- Default method for index
 232 \end{code}
 233
 234 %********************************************************
 235 %*                                                      *
 236 \subsection{Size of @Ix@ interval}
 237 %*                                                      *
 238 %********************************************************
 239
 240 The @rangeSize@ operator returns the number of elements
 241 in the range for an @Ix@ pair.
 242
 243 \begin{code}
 244 {-# SPECIALISE unsafeRangeSize :: (Int,Int) -> Int #-}
 245 {-# SPECIALISE unsafeRangeSize :: ((Int,Int),(Int,Int)) -> Int #-}
 246 unsafeRangeSize :: (Ix a) => (a,a) -> Int
 247 unsafeRangeSize b@(l,h) = unsafeIndex b h + 1
 248
 249 {-# SPECIALISE rangeSize :: (Int,Int) -> Int #-}
 250 {-# SPECIALISE rangeSize :: ((Int,Int),(Int,Int)) -> Int #-}
 251 rangeSize :: (Ix a) => (a,a) -> Int
 252 rangeSize b@(l,h) | inRange b h = unsafeIndex b h + 1
 253                   | otherwise   = 0
 254
 255 -- Note that the following is NOT right
 256 --      rangeSize (l,h) | l <= h    = index b h + 1
 257 --                      | otherwise = 0
 258 --
 259 -- Because it might be the case that l<h, but the range
 260 -- is nevertheless empty.  Consider
 261 --      ((1,2),(2,1))
 262 -- Here l<h, but the second index ranges from 2..1 and
 263 -- hence is empty
 264 \end{code}