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.
32 import {-# SOURCE #-} PrelErr ( error )
35 import PrelList( null )
41 %*********************************************************
43 \subsection{The @Ix@ class}
45 %*********************************************************
48 class (Ord a) => Ix a where
50 index, unsafeIndex :: (a,a) -> a -> Int
51 inRange :: (a,a) -> a -> Bool
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
59 %*********************************************************
61 \subsection{Instances of @Ix@}
63 %*********************************************************
66 -- abstract these errors from the relevant index functions so that
67 -- the guts of the function will be small enough to inline.
69 {-# NOINLINE indexError #-}
70 indexError :: Show a => (a,a) -> a -> String -> b
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) "")
77 ----------------------------------------------------------------------
78 instance Ix Char where
82 {-# INLINE unsafeIndex #-}
83 unsafeIndex (m,n) i = fromEnum i - fromEnum m
85 index b i | inRange b i = unsafeIndex b i
86 | otherwise = indexError b i "Char"
88 inRange (m,n) i = m <= i && i <= n
90 ----------------------------------------------------------------------
93 -- The INLINE stops the build in the RHS from getting inlined,
94 -- so that callers can fuse with the result of range
97 {-# INLINE unsafeIndex #-}
98 unsafeIndex (m,n) i = i - m
100 index b i | inRange b i = unsafeIndex b i
101 | otherwise = indexError b i "Int"
103 inRange (m,n) i = m <= i && i <= n
106 ----------------------------------------------------------------------
107 instance Ix Integer where
111 {-# INLINE unsafeIndex #-}
112 unsafeIndex (m,n) i = fromInteger (i - m)
114 index b i | inRange b i = unsafeIndex b i
115 | otherwise = indexError b i "Integer"
117 inRange (m,n) i = m <= i && i <= n
120 ----------------------------------------------------------------------
121 instance Ix Bool where -- as derived
125 {-# INLINE unsafeIndex #-}
126 unsafeIndex (l,_) i = fromEnum i - fromEnum l
128 index b i | inRange b i = unsafeIndex b i
129 | otherwise = indexError b i "Bool"
131 inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
133 ----------------------------------------------------------------------
134 instance Ix Ordering where -- as derived
138 {-# INLINE unsafeIndex #-}
139 unsafeIndex (l,_) i = fromEnum i - fromEnum l
141 index b i | inRange b i = unsafeIndex b i
142 | otherwise = indexError b i "Ordering"
144 inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
146 ----------------------------------------------------------------------
149 range ((), ()) = [()]
150 {-# INLINE unsafeIndex #-}
151 unsafeIndex ((), ()) () = 0
152 {-# INLINE inRange #-}
153 inRange ((), ()) () = True
155 index b i = unsafeIndex b i
158 ----------------------------------------------------------------------
159 instance (Ix a, Ix b) => Ix (a, b) where -- as derived
160 {-# SPECIALISE instance Ix (Int,Int) #-}
163 range ((l1,l2),(u1,u2)) =
164 [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]
166 {- INLINE unsafeIndex #-}
167 unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) =
168 unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2
170 {- INLINE inRange #-}
171 inRange ((l1,l2),(u1,u2)) (i1,i2) =
172 inRange (l1,u1) i1 && inRange (l2,u2) i2
174 -- Default method for index
176 ----------------------------------------------------------------------
177 instance (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3) where
178 {-# SPECIALISE instance Ix (Int,Int,Int) #-}
180 range ((l1,l2,l3),(u1,u2,u3)) =
181 [(i1,i2,i3) | i1 <- range (l1,u1),
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))
190 inRange ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
191 inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
194 -- Default method for index
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),
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)))
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
214 -- Default method for index
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),
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))))
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 &&
236 -- Default method for index
239 %********************************************************
241 \subsection{Size of @Ix@ interval}
243 %********************************************************
245 The @rangeSize@ operator returns the number of elements
246 in the range for an @Ix@ pair.
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
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
260 -- Note that the following is NOT right
261 -- rangeSize (l,h) | l <= h = index b h + 1
264 -- Because it might be the case that l<h, but the range
265 -- is nevertheless empty. Consider
267 -- Here l<h, but the second index ranges from 2..1 and