\begin{code}
-{-# OPTIONS_GHC -fno-implicit-prelude #-}
+{-# OPTIONS_GHC -fno-implicit-prelude -fno-bang-patterns #-}
-----------------------------------------------------------------------------
-- |
-- Module : GHC.Arr
--
-----------------------------------------------------------------------------
+-- #hide
module GHC.Arr where
import {-# SOURCE #-} GHC.Err ( error )
%*********************************************************
\begin{code}
+-- | The 'Ix' class is used to map a contiguous subrange of values in
+-- a type onto integers. It is used primarily for array indexing
+-- (see "Data.Array", "Data.Array.IArray" and "Data.Array.MArray").
+--
+-- The first argument @(l,u)@ of each of these operations is a pair
+-- specifying the lower and upper bounds of a contiguous subrange of values.
+--
+-- An implementation is entitled to assume the following laws about these
+-- operations:
+--
+-- * @'inRange' (l,u) i == 'elem' i ('range' (l,u))@
+--
+-- * @'range' (l,u) '!!' 'index' (l,u) i == i@, when @'inRange' (l,u) i@
+--
+-- * @'map' ('index' (l,u)) ('range' (l,u))) == [0..'rangeSize' (l,u)-1]@
+--
+-- * @'rangeSize' (l,u) == 'length' ('range' (l,u))@
+--
+-- Minimal complete instance: 'range', 'index' and 'inRange'.
+--
class (Ord a) => Ix a where
+ -- | The list of values in the subrange defined by a bounding pair.
range :: (a,a) -> [a]
- index, unsafeIndex :: (a,a) -> a -> Int
+ -- | The position of a subscript in the subrange.
+ index :: (a,a) -> a -> Int
+ -- | Like 'index', but without checking that the value is in range.
+ unsafeIndex :: (a,a) -> a -> Int
+ -- | Returns 'True' the given subscript lies in the range defined
+ -- the bounding pair.
inRange :: (a,a) -> a -> Bool
+ -- | The size of the subrange defined by a bounding pair.
rangeSize :: (a,a) -> Int
+ -- | like 'rangeSize', but without checking that the upper bound is
+ -- in range.
unsafeRangeSize :: (a,a) -> Int
-- Must specify one of index, unsafeIndex
- index b i | inRange b i = unsafeIndex b i
+ index b i | inRange b i = unsafeIndex b i
| otherwise = error "Error in array index"
unsafeIndex b i = index b i
- -- As long as you don't override the default rangeSize,
- -- you can specify unsafeRangeSize as follows, to speed up
- -- some operations:
- --
- -- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
- --
rangeSize b@(_l,h) | inRange b h = unsafeIndex b h + 1
- | otherwise = 0
- unsafeRangeSize b = rangeSize b
+ | otherwise = 0 -- This case is only here to
+ -- check for an empty range
+ -- NB: replacing (inRange b h) by (l <= h) fails for
+ -- tuples. E.g. (1,2) <= (2,1) but the range is empty
+
+ unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
\end{code}
Note that the following is NOT right
inRange (m,n) i = m <= i && i <= n
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
----------------------------------------------------------------------
instance Ix Int where
{-# INLINE range #-}
{-# INLINE inRange #-}
inRange (I# m,I# n) (I# i) = m <=# i && i <=# n
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
----------------------------------------------------------------------
instance Ix Integer where
{-# INLINE range #-}
inRange (m,n) i = m <= i && i <= n
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
----------------------------------------------------------------------
instance Ix Bool where -- as derived
{-# INLINE range #-}
inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
----------------------------------------------------------------------
instance Ix Ordering where -- as derived
{-# INLINE range #-}
inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
----------------------------------------------------------------------
instance Ix () where
{-# INLINE range #-}
{-# INLINE index #-}
index b i = unsafeIndex b i
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
----------------------------------------------------------------------
instance (Ix a, Ix b) => Ix (a, b) where -- as derived
{-# SPECIALISE instance Ix (Int,Int) #-}
inRange ((l1,l2),(u1,u2)) (i1,i2) =
inRange (l1,u1) i1 && inRange (l2,u2) i2
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
-- Default method for index
----------------------------------------------------------------------
inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
inRange (l3,u3) i3
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
-- Default method for index
----------------------------------------------------------------------
inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
inRange (l3,u3) i3 && inRange (l4,u4) i4
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
-- Default method for index
instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5) where
inRange (l3,u3) i3 && inRange (l4,u4) i4 &&
inRange (l5,u5) i5
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
-- Default method for index
\end{code}