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     {-# INLINE range #-}
  80     range (m,n) = [m..n]
  81
  82     {-# INLINE unsafeIndex #-}
  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     {-# INLINE range #-}
  93         -- The INLINE stops the build in the RHS from getting inlined,
  94         -- so that callers can fuse with the result of range
  95     range (m,n) = [m..n]
  96
  97     {-# INLINE unsafeIndex #-}
  98     unsafeIndex (m,_n) i = i - m
  99
 100     index b i | inRange b i =  unsafeIndex b i
 101               | otherwise   =  indexError b i "Int"
 102
 103     inRange (m,n) i     =  m <= i && i <= n
 104
 105
 106 ----------------------------------------------------------------------
 107 instance  Ix Integer  where
 108     {-# INLINE range #-}
 109     range (m,n) = [m..n]
 110
 111     {-# INLINE unsafeIndex #-}
 112     unsafeIndex (m,_n) i   = fromInteger (i - m)
 113
 114     index b i | inRange b i =  unsafeIndex b i
 115               | otherwise   =  indexError b i "Integer"
 116
 117     inRange (m,n) i     =  m <= i && i <= n
 118
 119
 120 ----------------------------------------------------------------------
 121 instance Ix Bool where -- as derived
 122     {-# INLINE range #-}
 123     range (m,n) = [m..n]
 124
 125     {-# INLINE unsafeIndex #-}
 126     unsafeIndex (l,_) i = fromEnum i - fromEnum l
 127
 128     index b i | inRange b i =  unsafeIndex b i
 129               | otherwise   =  indexError b i "Bool"
 130
 131     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
 132
 133 ----------------------------------------------------------------------
 134 instance Ix Ordering where -- as derived
 135     {-# INLINE range #-}
 136     range (m,n) = [m..n]
 137
 138     {-# INLINE unsafeIndex #-}
 139     unsafeIndex (l,_) i = fromEnum i - fromEnum l
 140
 141     index b i | inRange b i =  unsafeIndex b i
 142               | otherwise   =  indexError b i "Ordering"
 143
 144     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
 145
 146 ----------------------------------------------------------------------
 147 instance Ix () where
 148     {-# INLINE range #-}
 149     range   ((), ())    = [()]
 150     {-# INLINE unsafeIndex #-}
 151     unsafeIndex   ((), ()) () = 0
 152     {-# INLINE inRange #-}
 153     inRange ((), ()) () = True
 154     {-# INLINE index #-}
 155     index b i = unsafeIndex b i
 156
 157
 158 ----------------------------------------------------------------------
 159 instance (Ix a, Ix b) => Ix (a, b) where -- as derived
 160     {-# SPECIALISE instance Ix (Int,Int) #-}
 161
 162     {- INLINE range #-}
 163     range ((l1,l2),(u1,u2)) =
 164       [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]
 165
 166     {- INLINE unsafeIndex #-}
 167     unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) =
 168       unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2
 169
 170     {- INLINE inRange #-}
 171     inRange ((l1,l2),(u1,u2)) (i1,i2) =
 172       inRange (l1,u1) i1 && inRange (l2,u2) i2
 173
 174     -- Default method for index
 175
 176 ----------------------------------------------------------------------
 177 instance  (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3)  where
 178     {-# SPECIALISE instance Ix (Int,Int,Int) #-}
 179
 180     range ((l1,l2,l3),(u1,u2,u3)) =
 181         [(i1,i2,i3) | i1 <- range (l1,u1),
 182                       i2 <- range (l2,u2),
 183                       i3 <- range (l3,u3)]
 184
 185     unsafeIndex ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
 186       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 187       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 188       unsafeIndex (l1,u1) i1))
 189
 190     inRange ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
 191       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 192       inRange (l3,u3) i3
 193
 194     -- Default method for index
 195
 196 ----------------------------------------------------------------------
 197 instance  (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4)  where
 198     range ((l1,l2,l3,l4),(u1,u2,u3,u4)) =
 199       [(i1,i2,i3,i4) | i1 <- range (l1,u1),
 200                        i2 <- range (l2,u2),
 201                        i3 <- range (l3,u3),
 202                        i4 <- range (l4,u4)]
 203
 204     unsafeIndex ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
 205       unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
 206       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 207       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 208       unsafeIndex (l1,u1) i1)))
 209
 210     inRange ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
 211       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 212       inRange (l3,u3) i3 && inRange (l4,u4) i4
 213
 214     -- Default method for index
 215
 216 instance  (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5)  where
 217     range ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) =
 218       [(i1,i2,i3,i4,i5) | i1 <- range (l1,u1),
 219                           i2 <- range (l2,u2),
 220                           i3 <- range (l3,u3),
 221                           i4 <- range (l4,u4),
 222                           i5 <- range (l5,u5)]
 223
 224     unsafeIndex ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
 225       unsafeIndex (l5,u5) i5 + unsafeRangeSize (l5,u5) * (
 226       unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
 227       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 228       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 229       unsafeIndex (l1,u1) i1))))
 230
 231     inRange ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
 232       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 233       inRange (l3,u3) i3 && inRange (l4,u4) i4 &&
 234       inRange (l5,u5) i5
 235
 236     -- Default method for index
 237 \end{code}
 238
 239 %********************************************************
 240 %*                                                      *
 241 \subsection{Size of @Ix@ interval}
 242 %*                                                      *
 243 %********************************************************
 244
 245 The @rangeSize@ operator returns the number of elements
 246 in the range for an @Ix@ pair.
 247
 248 \begin{code}
 249 {-# SPECIALISE unsafeRangeSize :: (Int,Int) -> Int #-}
 250 {-# SPECIALISE unsafeRangeSize :: ((Int,Int),(Int,Int)) -> Int #-}
 251 unsafeRangeSize :: (Ix a) => (a,a) -> Int
 252 unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
 253
 254 {-# SPECIALISE rangeSize :: (Int,Int) -> Int #-}
 255 {-# SPECIALISE rangeSize :: ((Int,Int),(Int,Int)) -> Int #-}
 256 rangeSize :: (Ix a) => (a,a) -> Int
 257 rangeSize b@(_l,h) | inRange b h = unsafeIndex b h + 1
 258                    | otherwise   = 0
 259
 260 -- Note that the following is NOT right
 261 --      rangeSize (l,h) | l <= h    = index b h + 1
 262 --                      | otherwise = 0
 263 --
 264 -- Because it might be the case that l<h, but the range
 265 -- is nevertheless empty.  Consider
 266 --      ((1,2),(2,1))
 267 -- Here l<h, but the second index ranges from 2..1 and
 268 -- hence is empty
 269 \end{code}