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 )
44 %*********************************************************
46 \subsection{The @Ix@ class}
48 %*********************************************************
51 class (Ord a) => Ix a where
53 index, unsafeIndex :: (a,a) -> a -> Int
54 inRange :: (a,a) -> a -> Bool
56 -- Must specify one of index, unsafeIndex
57 index b i | inRange b i = unsafeIndex b i
58 | otherwise = error "Error in array index"
59 unsafeIndex b i = index b i
62 %*********************************************************
64 \subsection{Instances of @Ix@}
66 %*********************************************************
69 -- abstract these errors from the relevant index functions so that
70 -- the guts of the function will be small enough to inline.
72 {-# NOINLINE indexError #-}
73 indexError :: Show a => (a,a) -> a -> String -> b
75 = error (showString "Ix{" . showString tp . showString "}.index: Index " .
76 showParen True (showsPrec 0 i) .
77 showString " out of range " $
78 showParen True (showsPrec 0 rng) "")
80 ----------------------------------------------------------------------
81 instance Ix Char where
85 {-# INLINE unsafeIndex #-}
86 unsafeIndex (m,_n) i = fromEnum i - fromEnum m
88 index b i | inRange b i = unsafeIndex b i
89 | otherwise = indexError b i "Char"
91 inRange (m,n) i = m <= i && i <= n
93 ----------------------------------------------------------------------
96 -- The INLINE stops the build in the RHS from getting inlined,
97 -- so that callers can fuse with the result of range
100 {-# INLINE unsafeIndex #-}
101 unsafeIndex (m,_n) i = i - m
103 index b i | inRange b i = unsafeIndex b i
104 | otherwise = indexError b i "Int"
106 {-# INLINE inRange #-}
107 inRange (I# m,I# n) (I# i) = m <=# i && i <=# n
109 ----------------------------------------------------------------------
110 instance Ix Integer where
114 {-# INLINE unsafeIndex #-}
115 unsafeIndex (m,_n) i = fromInteger (i - m)
117 index b i | inRange b i = unsafeIndex b i
118 | otherwise = indexError b i "Integer"
120 inRange (m,n) i = m <= i && i <= n
123 ----------------------------------------------------------------------
124 instance Ix Bool where -- as derived
128 {-# INLINE unsafeIndex #-}
129 unsafeIndex (l,_) i = fromEnum i - fromEnum l
131 index b i | inRange b i = unsafeIndex b i
132 | otherwise = indexError b i "Bool"
134 inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
136 ----------------------------------------------------------------------
137 instance Ix Ordering where -- as derived
141 {-# INLINE unsafeIndex #-}
142 unsafeIndex (l,_) i = fromEnum i - fromEnum l
144 index b i | inRange b i = unsafeIndex b i
145 | otherwise = indexError b i "Ordering"
147 inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
149 ----------------------------------------------------------------------
152 range ((), ()) = [()]
153 {-# INLINE unsafeIndex #-}
154 unsafeIndex ((), ()) () = 0
155 {-# INLINE inRange #-}
156 inRange ((), ()) () = True
158 index b i = unsafeIndex b i
161 ----------------------------------------------------------------------
162 instance (Ix a, Ix b) => Ix (a, b) where -- as derived
163 {-# SPECIALISE instance Ix (Int,Int) #-}
166 range ((l1,l2),(u1,u2)) =
167 [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]
169 {- INLINE unsafeIndex #-}
170 unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) =
171 unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2
173 {- INLINE inRange #-}
174 inRange ((l1,l2),(u1,u2)) (i1,i2) =
175 inRange (l1,u1) i1 && inRange (l2,u2) i2
177 -- Default method for index
179 ----------------------------------------------------------------------
180 instance (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3) where
181 {-# SPECIALISE instance Ix (Int,Int,Int) #-}
183 range ((l1,l2,l3),(u1,u2,u3)) =
184 [(i1,i2,i3) | i1 <- range (l1,u1),
188 unsafeIndex ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
189 unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
190 unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
191 unsafeIndex (l1,u1) i1))
193 inRange ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
194 inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
197 -- Default method for index
199 ----------------------------------------------------------------------
200 instance (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4) where
201 range ((l1,l2,l3,l4),(u1,u2,u3,u4)) =
202 [(i1,i2,i3,i4) | i1 <- range (l1,u1),
207 unsafeIndex ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
208 unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
209 unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
210 unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
211 unsafeIndex (l1,u1) i1)))
213 inRange ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
214 inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
215 inRange (l3,u3) i3 && inRange (l4,u4) i4
217 -- Default method for index
219 instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5) where
220 range ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) =
221 [(i1,i2,i3,i4,i5) | i1 <- range (l1,u1),
227 unsafeIndex ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
228 unsafeIndex (l5,u5) i5 + unsafeRangeSize (l5,u5) * (
229 unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
230 unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
231 unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
232 unsafeIndex (l1,u1) i1))))
234 inRange ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
235 inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
236 inRange (l3,u3) i3 && inRange (l4,u4) i4 &&
239 -- Default method for index
242 %********************************************************
244 \subsection{Size of @Ix@ interval}
246 %********************************************************
248 The @rangeSize@ operator returns the number of elements
249 in the range for an @Ix@ pair.
252 {-# SPECIALISE unsafeRangeSize :: (Int,Int) -> Int #-}
253 {-# SPECIALISE unsafeRangeSize :: ((Int,Int),(Int,Int)) -> Int #-}
254 unsafeRangeSize :: (Ix a) => (a,a) -> Int
255 unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
257 {-# SPECIALISE rangeSize :: (Int,Int) -> Int #-}
258 {-# SPECIALISE rangeSize :: ((Int,Int),(Int,Int)) -> Int #-}
259 rangeSize :: (Ix a) => (a,a) -> Int
260 rangeSize b@(_l,h) | inRange b h = unsafeIndex b h + 1
263 -- Note that the following is NOT right
264 -- rangeSize (l,h) | l <= h = index b h + 1
267 -- Because it might be the case that l<h, but the range
268 -- is nevertheless empty. Consider
270 -- Here l<h, but the second index ranges from 2..1 and
276 -- This module is empty; Ix is currently defined in the prelude, but should
277 -- eventually be moved to this library file instead.