2 % (c) The AQUA Project, Glasgow University, 1994-1999
5 \section[Ix]{Module @Ix@}
8 {-# OPTIONS -fno-implicit-prelude #-}
13 ( range -- :: (Ix a) => (a,a) -> [a]
14 , index -- :: (Ix a) => (a,a) -> a -> Int
15 , inRange -- :: (Ix a) => (a,a) -> a -> Bool
17 , rangeSize -- :: (Ix a) => (a,a) -> Int
26 -- (Ix a, Ix b) => Ix (a, b)
29 -- Implementation checked wrt. Haskell 98 lib report, 1/99.
33 import {-# SOURCE #-} PrelErr ( error )
36 import PrelList( null )
42 %*********************************************************
44 \subsection{The @Ix@ class}
46 %*********************************************************
49 class (Ord a) => Ix a where
51 index, unsafeIndex :: (a,a) -> a -> Int
52 inRange :: (a,a) -> a -> Bool
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 unsafeIndex b i = index b i
60 %*********************************************************
62 \subsection{Instances of @Ix@}
64 %*********************************************************
67 -- abstract these errors from the relevant index functions so that
68 -- the guts of the function will be small enough to inline.
70 {-# NOINLINE indexError #-}
71 indexError :: Show a => (a,a) -> a -> String -> b
73 = error (showString "Ix{" . showString tp . showString "}.index: Index " .
74 showParen True (showsPrec 0 i) .
75 showString " out of range " $
76 showParen True (showsPrec 0 rng) "")
78 ----------------------------------------------------------------------
79 instance Ix Char where
83 {-# INLINE unsafeIndex #-}
84 unsafeIndex (m,_n) i = fromEnum i - fromEnum m
86 index b i | inRange b i = unsafeIndex b i
87 | otherwise = indexError b i "Char"
89 inRange (m,n) i = m <= i && i <= n
91 ----------------------------------------------------------------------
94 -- The INLINE stops the build in the RHS from getting inlined,
95 -- so that callers can fuse with the result of range
98 {-# INLINE unsafeIndex #-}
99 unsafeIndex (m,_n) i = i - m
101 index b i | inRange b i = unsafeIndex b i
102 | otherwise = indexError b i "Int"
104 {-# INLINE inRange #-}
105 inRange (I# m,I# n) (I# i) = m <=# i && i <=# n
107 ----------------------------------------------------------------------
108 instance Ix Integer where
112 {-# INLINE unsafeIndex #-}
113 unsafeIndex (m,_n) i = fromInteger (i - m)
115 index b i | inRange b i = unsafeIndex b i
116 | otherwise = indexError b i "Integer"
118 inRange (m,n) i = m <= i && i <= n
121 ----------------------------------------------------------------------
122 instance Ix Bool where -- as derived
126 {-# INLINE unsafeIndex #-}
127 unsafeIndex (l,_) i = fromEnum i - fromEnum l
129 index b i | inRange b i = unsafeIndex b i
130 | otherwise = indexError b i "Bool"
132 inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
134 ----------------------------------------------------------------------
135 instance Ix Ordering where -- as derived
139 {-# INLINE unsafeIndex #-}
140 unsafeIndex (l,_) i = fromEnum i - fromEnum l
142 index b i | inRange b i = unsafeIndex b i
143 | otherwise = indexError b i "Ordering"
145 inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
147 ----------------------------------------------------------------------
150 range ((), ()) = [()]
151 {-# INLINE unsafeIndex #-}
152 unsafeIndex ((), ()) () = 0
153 {-# INLINE inRange #-}
154 inRange ((), ()) () = True
156 index b i = unsafeIndex b i
159 ----------------------------------------------------------------------
160 instance (Ix a, Ix b) => Ix (a, b) where -- as derived
161 {-# SPECIALISE instance Ix (Int,Int) #-}
164 range ((l1,l2),(u1,u2)) =
165 [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]
167 {- INLINE unsafeIndex #-}
168 unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) =
169 unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2
171 {- INLINE inRange #-}
172 inRange ((l1,l2),(u1,u2)) (i1,i2) =
173 inRange (l1,u1) i1 && inRange (l2,u2) i2
175 -- Default method for index
177 ----------------------------------------------------------------------
178 instance (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3) where
179 {-# SPECIALISE instance Ix (Int,Int,Int) #-}
181 range ((l1,l2,l3),(u1,u2,u3)) =
182 [(i1,i2,i3) | i1 <- range (l1,u1),
186 unsafeIndex ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
187 unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
188 unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
189 unsafeIndex (l1,u1) i1))
191 inRange ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
192 inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
195 -- Default method for index
197 ----------------------------------------------------------------------
198 instance (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4) where
199 range ((l1,l2,l3,l4),(u1,u2,u3,u4)) =
200 [(i1,i2,i3,i4) | i1 <- range (l1,u1),
205 unsafeIndex ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
206 unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
207 unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
208 unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
209 unsafeIndex (l1,u1) i1)))
211 inRange ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
212 inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
213 inRange (l3,u3) i3 && inRange (l4,u4) i4
215 -- Default method for index
217 instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5) where
218 range ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) =
219 [(i1,i2,i3,i4,i5) | i1 <- range (l1,u1),
225 unsafeIndex ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
226 unsafeIndex (l5,u5) i5 + unsafeRangeSize (l5,u5) * (
227 unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
228 unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
229 unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
230 unsafeIndex (l1,u1) i1))))
232 inRange ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
233 inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
234 inRange (l3,u3) i3 && inRange (l4,u4) i4 &&
237 -- Default method for index
240 %********************************************************
242 \subsection{Size of @Ix@ interval}
244 %********************************************************
246 The @rangeSize@ operator returns the number of elements
247 in the range for an @Ix@ pair.
250 {-# SPECIALISE unsafeRangeSize :: (Int,Int) -> Int #-}
251 {-# SPECIALISE unsafeRangeSize :: ((Int,Int),(Int,Int)) -> Int #-}
252 unsafeRangeSize :: (Ix a) => (a,a) -> Int
253 unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
255 {-# SPECIALISE rangeSize :: (Int,Int) -> Int #-}
256 {-# SPECIALISE rangeSize :: ((Int,Int),(Int,Int)) -> Int #-}
257 rangeSize :: (Ix a) => (a,a) -> Int
258 rangeSize b@(_l,h) | inRange b h = unsafeIndex b h + 1
261 -- Note that the following is NOT right
262 -- rangeSize (l,h) | l <= h = index b h + 1
265 -- Because it might be the case that l<h, but the range
266 -- is nevertheless empty. Consider
268 -- Here l<h, but the second index ranges from 2..1 and
274 -- This module is empty; Ix is currently defined in the prelude, but should
275 -- eventually be moved to this library file instead.