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 #ifndef __HUGS__
  33 import {-# SOURCE #-} PrelErr ( error )
  34 import PrelTup
  35 import PrelBase
  36 import PrelList( null )
  37 import PrelEnum
  38 import PrelShow
  39 import PrelNum
  40 \end{code}
  41
  42 %*********************************************************
  43 %*                                                      *
  44 \subsection{The @Ix@ class}
  45 %*                                                      *
  46 %*********************************************************
  47
  48 \begin{code}
  49 class  (Ord a) => Ix a  where
  50     range               :: (a,a) -> [a]
  51     index, unsafeIndex  :: (a,a) -> a -> Int
  52     inRange             :: (a,a) -> a -> Bool
  53
  54         -- Must specify one of index, unsafeIndex
  55     index b i | inRange b i = unsafeIndex b i
  56               | otherwise   = error "Error in array index"
  57                                 -- ToDo: raise (ArrayException IndexOutOfRange)
  58     unsafeIndex b i = index b i
  59 \end{code}
  60
  61 %*********************************************************
  62 %*                                                      *
  63 \subsection{Instances of @Ix@}
  64 %*                                                      *
  65 %*********************************************************
  66
  67 \begin{code}
  68 -- abstract these errors from the relevant index functions so that
  69 -- the guts of the function will be small enough to inline.
  70
  71 {-# NOINLINE indexError #-}
  72 indexError :: Show a => (a,a) -> a -> String -> b
  73 indexError rng i tp
  74   = error (showString "Ix{" . showString tp . showString "}.index: Index " .
  75            showParen True (showsPrec 0 i) .
  76            showString " out of range " $
  77            showParen True (showsPrec 0 rng) "")
  78
  79 ----------------------------------------------------------------------
  80 instance  Ix Char  where
  81     {-# INLINE range #-}
  82     range (m,n) = [m..n]
  83
  84     {-# INLINE unsafeIndex #-}
  85     unsafeIndex (m,_n) i = fromEnum i - fromEnum m
  86
  87     index b i | inRange b i =  unsafeIndex b i
  88               | otherwise   =  indexError b i "Char"
  89
  90     inRange (m,n) i     =  m <= i && i <= n
  91
  92 ----------------------------------------------------------------------
  93 instance  Ix Int  where
  94     {-# INLINE range #-}
  95         -- The INLINE stops the build in the RHS from getting inlined,
  96         -- so that callers can fuse with the result of range
  97     range (m,n) = [m..n]
  98
  99     {-# INLINE unsafeIndex #-}
 100     unsafeIndex (m,_n) i = i - m
 101
 102     index b i | inRange b i =  unsafeIndex b i
 103               | otherwise   =  indexError b i "Int"
 104
 105     {-# INLINE inRange #-}
 106     inRange (I# m,I# n) (I# i) =  m <=# i && i <=# n
 107
 108 ----------------------------------------------------------------------
 109 instance  Ix Integer  where
 110     {-# INLINE range #-}
 111     range (m,n) = [m..n]
 112
 113     {-# INLINE unsafeIndex #-}
 114     unsafeIndex (m,_n) i   = fromInteger (i - m)
 115
 116     index b i | inRange b i =  unsafeIndex b i
 117               | otherwise   =  indexError b i "Integer"
 118
 119     inRange (m,n) i     =  m <= i && i <= n
 120
 121
 122 ----------------------------------------------------------------------
 123 instance Ix Bool where -- as derived
 124     {-# INLINE range #-}
 125     range (m,n) = [m..n]
 126
 127     {-# INLINE unsafeIndex #-}
 128     unsafeIndex (l,_) i = fromEnum i - fromEnum l
 129
 130     index b i | inRange b i =  unsafeIndex b i
 131               | otherwise   =  indexError b i "Bool"
 132
 133     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
 134
 135 ----------------------------------------------------------------------
 136 instance Ix Ordering where -- as derived
 137     {-# INLINE range #-}
 138     range (m,n) = [m..n]
 139
 140     {-# INLINE unsafeIndex #-}
 141     unsafeIndex (l,_) i = fromEnum i - fromEnum l
 142
 143     index b i | inRange b i =  unsafeIndex b i
 144               | otherwise   =  indexError b i "Ordering"
 145
 146     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
 147
 148 ----------------------------------------------------------------------
 149 instance Ix () where
 150     {-# INLINE range #-}
 151     range   ((), ())    = [()]
 152     {-# INLINE unsafeIndex #-}
 153     unsafeIndex   ((), ()) () = 0
 154     {-# INLINE inRange #-}
 155     inRange ((), ()) () = True
 156     {-# INLINE index #-}
 157     index b i = unsafeIndex b i
 158
 159
 160 ----------------------------------------------------------------------
 161 instance (Ix a, Ix b) => Ix (a, b) where -- as derived
 162     {-# SPECIALISE instance Ix (Int,Int) #-}
 163
 164     {- INLINE range #-}
 165     range ((l1,l2),(u1,u2)) =
 166       [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]
 167
 168     {- INLINE unsafeIndex #-}
 169     unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) =
 170       unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2
 171
 172     {- INLINE inRange #-}
 173     inRange ((l1,l2),(u1,u2)) (i1,i2) =
 174       inRange (l1,u1) i1 && inRange (l2,u2) i2
 175
 176     -- Default method for index
 177
 178 ----------------------------------------------------------------------
 179 instance  (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3)  where
 180     {-# SPECIALISE instance Ix (Int,Int,Int) #-}
 181
 182     range ((l1,l2,l3),(u1,u2,u3)) =
 183         [(i1,i2,i3) | i1 <- range (l1,u1),
 184                       i2 <- range (l2,u2),
 185                       i3 <- range (l3,u3)]
 186
 187     unsafeIndex ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
 188       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 189       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 190       unsafeIndex (l1,u1) i1))
 191
 192     inRange ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
 193       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 194       inRange (l3,u3) i3
 195
 196     -- Default method for index
 197
 198 ----------------------------------------------------------------------
 199 instance  (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4)  where
 200     range ((l1,l2,l3,l4),(u1,u2,u3,u4)) =
 201       [(i1,i2,i3,i4) | i1 <- range (l1,u1),
 202                        i2 <- range (l2,u2),
 203                        i3 <- range (l3,u3),
 204                        i4 <- range (l4,u4)]
 205
 206     unsafeIndex ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
 207       unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
 208       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 209       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 210       unsafeIndex (l1,u1) i1)))
 211
 212     inRange ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
 213       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 214       inRange (l3,u3) i3 && inRange (l4,u4) i4
 215
 216     -- Default method for index
 217
 218 instance  (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5)  where
 219     range ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) =
 220       [(i1,i2,i3,i4,i5) | i1 <- range (l1,u1),
 221                           i2 <- range (l2,u2),
 222                           i3 <- range (l3,u3),
 223                           i4 <- range (l4,u4),
 224                           i5 <- range (l5,u5)]
 225
 226     unsafeIndex ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
 227       unsafeIndex (l5,u5) i5 + unsafeRangeSize (l5,u5) * (
 228       unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
 229       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 230       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 231       unsafeIndex (l1,u1) i1))))
 232
 233     inRange ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
 234       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 235       inRange (l3,u3) i3 && inRange (l4,u4) i4 &&
 236       inRange (l5,u5) i5
 237
 238     -- Default method for index
 239 \end{code}
 240
 241 %********************************************************
 242 %*                                                      *
 243 \subsection{Size of @Ix@ interval}
 244 %*                                                      *
 245 %********************************************************
 246
 247 The @rangeSize@ operator returns the number of elements
 248 in the range for an @Ix@ pair.
 249
 250 \begin{code}
 251 {-# SPECIALISE unsafeRangeSize :: (Int,Int) -> Int #-}
 252 {-# SPECIALISE unsafeRangeSize :: ((Int,Int),(Int,Int)) -> Int #-}
 253 unsafeRangeSize :: (Ix a) => (a,a) -> Int
 254 unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
 255
 256 {-# SPECIALISE rangeSize :: (Int,Int) -> Int #-}
 257 {-# SPECIALISE rangeSize :: ((Int,Int),(Int,Int)) -> Int #-}
 258 rangeSize :: (Ix a) => (a,a) -> Int
 259 rangeSize b@(_l,h) | inRange b h = unsafeIndex b h + 1
 260                    | otherwise   = 0
 261
 262 -- Note that the following is NOT right
 263 --      rangeSize (l,h) | l <= h    = index b h + 1
 264 --                      | otherwise = 0
 265 --
 266 -- Because it might be the case that l<h, but the range
 267 -- is nevertheless empty.  Consider
 268 --      ((1,2),(2,1))
 269 -- Here l<h, but the second index ranges from 2..1 and
 270 -- hence is empty
 271 \end{code}
 272
 273 \begin{code}
 274 #else
 275 -- This module is empty; Ix is currently defined in the prelude, but should
 276 -- eventually be moved to this library file instead.
 277 #endif
 278 \end{code}