{-# LANGUAGE Unsafe #-}
{-# LANGUAGE NoImplicitPrelude, MagicHash, UnboxedTuples, RoleAnnotations #-}
{-# OPTIONS_HADDOCK hide #-}
module GHC.Arr (
Ix(..), Array(..), STArray(..),
indexError, hopelessIndexError,
arrEleBottom, array, listArray,
(!), safeRangeSize, negRange, safeIndex, badSafeIndex,
bounds, numElements, numElementsSTArray, indices, elems,
assocs, accumArray, adjust, (//), accum,
amap, ixmap,
eqArray, cmpArray, cmpIntArray,
newSTArray, boundsSTArray,
readSTArray, writeSTArray,
freezeSTArray, thawSTArray,
foldlElems, foldlElems', foldl1Elems,
foldrElems, foldrElems', foldr1Elems,
fill, done,
unsafeArray, unsafeArray',
lessSafeIndex, unsafeAt, unsafeReplace,
unsafeAccumArray, unsafeAccumArray', unsafeAccum,
unsafeReadSTArray, unsafeWriteSTArray,
unsafeFreezeSTArray, unsafeThawSTArray,
) where
import GHC.Enum
import GHC.Num
import GHC.ST
import GHC.Base
import GHC.List
import GHC.Real( fromIntegral )
import GHC.Show
infixl 9 !, //
default ()
class (Ord a) => Ix a where
{-# MINIMAL range, (index | unsafeIndex), inRange #-}
range :: (a,a) -> [a]
index :: (a,a) -> a -> Int
unsafeIndex :: (a,a) -> a -> Int
inRange :: (a,a) -> a -> Bool
rangeSize :: (a,a) -> Int
unsafeRangeSize :: (a,a) -> Int
{-# INLINE index #-}
index b i | inRange b i = unsafeIndex b i
| otherwise = hopelessIndexError
unsafeIndex b i = index b i
rangeSize b@(_l,h) | inRange b h = unsafeIndex b h + 1
| otherwise = 0
unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
{-# NOINLINE indexError #-}
indexError :: Show a => (a,a) -> a -> String -> b
indexError rng i tp
= errorWithoutStackTrace (showString "Ix{" . showString tp . showString "}.index: Index " .
showParen True (showsPrec 0 i) .
showString " out of range " $
showParen True (showsPrec 0 rng) "")
hopelessIndexError :: Int
hopelessIndexError = errorWithoutStackTrace "Error in array index"
instance Ix Char where
{-# INLINE range #-}
range (m,n) = [m..n]
{-# INLINE unsafeIndex #-}
unsafeIndex (m,_n) i = fromEnum i - fromEnum m
{-# INLINE index #-}
index b i | inRange b i = unsafeIndex b i
| otherwise = indexError b i "Char"
inRange (m,n) i = m <= i && i <= n
instance Ix Int where
{-# INLINE range #-}
range (m,n) = [m..n]
{-# INLINE unsafeIndex #-}
unsafeIndex (m,_n) i = i - m
{-# INLINE index #-}
index b i | inRange b i = unsafeIndex b i
| otherwise = indexError b i "Int"
{-# INLINE inRange #-}
inRange (I# m,I# n) (I# i) = isTrue# (m <=# i) && isTrue# (i <=# n)
instance Ix Word where
range (m,n) = [m..n]
unsafeIndex (m,_) i = fromIntegral (i - m)
inRange (m,n) i = m <= i && i <= n
instance Ix Integer where
{-# INLINE range #-}
range (m,n) = [m..n]
{-# INLINE unsafeIndex #-}
unsafeIndex (m,_n) i = fromInteger (i - m)
{-# INLINE index #-}
index b i | inRange b i = unsafeIndex b i
| otherwise = indexError b i "Integer"
inRange (m,n) i = m <= i && i <= n
instance Ix Bool where
{-# INLINE range #-}
range (m,n) = [m..n]
{-# INLINE unsafeIndex #-}
unsafeIndex (l,_) i = fromEnum i - fromEnum l
{-# INLINE index #-}
index b i | inRange b i = unsafeIndex b i
| otherwise = indexError b i "Bool"
inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
instance Ix Ordering where
{-# INLINE range #-}
range (m,n) = [m..n]
{-# INLINE unsafeIndex #-}
unsafeIndex (l,_) i = fromEnum i - fromEnum l
{-# INLINE index #-}
index b i | inRange b i = unsafeIndex b i
| otherwise = indexError b i "Ordering"
inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
instance Ix () where
{-# INLINE range #-}
range ((), ()) = [()]
{-# INLINE unsafeIndex #-}
unsafeIndex ((), ()) () = 0
{-# INLINE inRange #-}
inRange ((), ()) () = True
{-# INLINE index #-}
index b i = unsafeIndex b i
instance (Ix a, Ix b) => Ix (a, b) where
{-# SPECIALISE instance Ix (Int,Int) #-}
{-# INLINE range #-}
range ((l1,l2),(u1,u2)) =
[ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]
{-# INLINE unsafeIndex #-}
unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) =
unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2
{-# INLINE inRange #-}
inRange ((l1,l2),(u1,u2)) (i1,i2) =
inRange (l1,u1) i1 && inRange (l2,u2) i2
instance (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3) where
{-# SPECIALISE instance Ix (Int,Int,Int) #-}
range ((l1,l2,l3),(u1,u2,u3)) =
[(i1,i2,i3) | i1 <- range (l1,u1),
i2 <- range (l2,u2),
i3 <- range (l3,u3)]
unsafeIndex ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
unsafeIndex (l1,u1) i1))
inRange ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
inRange (l3,u3) i3
instance (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4) where
range ((l1,l2,l3,l4),(u1,u2,u3,u4)) =
[(i1,i2,i3,i4) | i1 <- range (l1,u1),
i2 <- range (l2,u2),
i3 <- range (l3,u3),
i4 <- range (l4,u4)]
unsafeIndex ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
unsafeIndex (l1,u1) i1)))
inRange ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
inRange (l3,u3) i3 && inRange (l4,u4) i4
instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5) where
range ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) =
[(i1,i2,i3,i4,i5) | i1 <- range (l1,u1),
i2 <- range (l2,u2),
i3 <- range (l3,u3),
i4 <- range (l4,u4),
i5 <- range (l5,u5)]
unsafeIndex ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
unsafeIndex (l5,u5) i5 + unsafeRangeSize (l5,u5) * (
unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
unsafeIndex (l1,u1) i1))))
inRange ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
inRange (l3,u3) i3 && inRange (l4,u4) i4 &&
inRange (l5,u5) i5
data Array i e
= Array !i
!i
{-# UNPACK #-} !Int
(Array# e)
data STArray s i e
= STArray !i
!i
{-# UNPACK #-} !Int
(MutableArray# s e)
type role Array nominal representational
type role STArray nominal nominal representational
instance Eq (STArray s i e) where
STArray _ _ _ arr1# == STArray _ _ _ arr2# =
isTrue# (sameMutableArray# arr1# arr2#)
{-# NOINLINE arrEleBottom #-}
arrEleBottom :: a
arrEleBottom = errorWithoutStackTrace "(Array.!): undefined array element"
{-# INLINE array #-}
array :: Ix i
=> (i,i)
-> [(i, e)]
-> Array i e
array (l,u) ies
= let n = safeRangeSize (l,u)
in unsafeArray' (l,u) n
[(safeIndex (l,u) n i, e) | (i, e) <- ies]
{-# INLINE unsafeArray #-}
unsafeArray :: Ix i => (i,i) -> [(Int, e)] -> Array i e
unsafeArray b ies = unsafeArray' b (rangeSize b) ies
{-# INLINE unsafeArray' #-}
unsafeArray' :: (i,i) -> Int -> [(Int, e)] -> Array i e
unsafeArray' (l,u) n@(I# n#) ies = runST (ST $ \s1# ->
case newArray# n# arrEleBottom s1# of
(# s2#, marr# #) ->
foldr (fill marr#) (done l u n marr#) ies s2#)
{-# INLINE fill #-}
fill :: MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
fill marr# (I# i#, e) next
= \s1# -> case writeArray# marr# i# e s1# of
s2# -> next s2#
{-# INLINE done #-}
done :: i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
done l u n@(I# _) marr#
= \s1# -> case unsafeFreezeArray# marr# s1# of
(# s2#, arr# #) -> (# s2#, Array l u n arr# #)
{-# INLINE listArray #-}
listArray :: Ix i => (i,i) -> [e] -> Array i e
listArray (l,u) es = runST (ST $ \s1# ->
case safeRangeSize (l,u) of { n@(I# n#) ->
case newArray# n# arrEleBottom s1# of { (# s2#, marr# #) ->
let
go y r = \ i# s3# ->
case writeArray# marr# i# y s3# of
s4# -> if (isTrue# (i# ==# n# -# 1#))
then s4#
else r (i# +# 1#) s4#
in
done l u n marr# (
if n == 0
then s2#
else foldr go (\_ s# -> s#) es 0# s2#)}})
{-# INLINE (!) #-}
(!) :: Ix i => Array i e -> i -> e
arr@(Array l u n _) ! i = unsafeAt arr $ safeIndex (l,u) n i
{-# INLINE safeRangeSize #-}
safeRangeSize :: Ix i => (i, i) -> Int
safeRangeSize (l,u) = let r = rangeSize (l, u)
in if r < 0 then negRange
else r
negRange :: Int
negRange = errorWithoutStackTrace "Negative range size"
{-# INLINE[1] safeIndex #-}
safeIndex :: Ix i => (i, i) -> Int -> i -> Int
safeIndex (l,u) n@(I# _) i
| (0 <= i') && (i' < n) = i'
| otherwise = badSafeIndex i' n
where
i' = index (l,u) i
{-# RULES
"safeIndex/I" safeIndex = lessSafeIndex :: (Int,Int) -> Int -> Int -> Int
"safeIndex/(I,I)" safeIndex = lessSafeIndex :: ((Int,Int),(Int,Int)) -> Int -> (Int,Int) -> Int
"safeIndex/(I,I,I)" safeIndex = lessSafeIndex :: ((Int,Int,Int),(Int,Int,Int)) -> Int -> (Int,Int,Int) -> Int
#-}
lessSafeIndex :: Ix i => (i, i) -> Int -> i -> Int
lessSafeIndex (l,u) _ i = index (l,u) i
badSafeIndex :: Int -> Int -> Int
badSafeIndex i' n = errorWithoutStackTrace ("Error in array index; " ++ show i' ++
" not in range [0.." ++ show n ++ ")")
{-# INLINE unsafeAt #-}
unsafeAt :: Array i e -> Int -> e
unsafeAt (Array _ _ _ arr#) (I# i#) =
case indexArray# arr# i# of (# e #) -> e
{-# INLINE bounds #-}
bounds :: Array i e -> (i,i)
bounds (Array l u _ _) = (l,u)
{-# INLINE numElements #-}
numElements :: Array i e -> Int
numElements (Array _ _ n _) = n
{-# INLINE indices #-}
indices :: Ix i => Array i e -> [i]
indices (Array l u _ _) = range (l,u)
{-# INLINE elems #-}
elems :: Array i e -> [e]
elems arr@(Array _ _ n _) =
[unsafeAt arr i | i <- [0 .. n - 1]]
{-# INLINABLE foldrElems #-}
foldrElems :: (a -> b -> b) -> b -> Array i a -> b
foldrElems f b0 = \ arr@(Array _ _ n _) ->
let
go i | i == n = b0
| otherwise = f (unsafeAt arr i) (go (i+1))
in go 0
{-# INLINABLE foldlElems #-}
foldlElems :: (b -> a -> b) -> b -> Array i a -> b
foldlElems f b0 = \ arr@(Array _ _ n _) ->
let
go i | i == (-1) = b0
| otherwise = f (go (i-1)) (unsafeAt arr i)
in go (n-1)
{-# INLINABLE foldrElems' #-}
foldrElems' :: (a -> b -> b) -> b -> Array i a -> b
foldrElems' f b0 = \ arr@(Array _ _ n _) ->
let
go i a | i == (-1) = a
| otherwise = go (i-1) (f (unsafeAt arr i) $! a)
in go (n-1) b0
{-# INLINABLE foldlElems' #-}
foldlElems' :: (b -> a -> b) -> b -> Array i a -> b
foldlElems' f b0 = \ arr@(Array _ _ n _) ->
let
go i a | i == n = a
| otherwise = go (i+1) (a `seq` f a (unsafeAt arr i))
in go 0 b0
{-# INLINABLE foldl1Elems #-}
foldl1Elems :: (a -> a -> a) -> Array i a -> a
foldl1Elems f = \ arr@(Array _ _ n _) ->
let
go i | i == 0 = unsafeAt arr 0
| otherwise = f (go (i-1)) (unsafeAt arr i)
in
if n == 0 then errorWithoutStackTrace "foldl1: empty Array" else go (n-1)
{-# INLINABLE foldr1Elems #-}
foldr1Elems :: (a -> a -> a) -> Array i a -> a
foldr1Elems f = \ arr@(Array _ _ n _) ->
let
go i | i == n-1 = unsafeAt arr i
| otherwise = f (unsafeAt arr i) (go (i + 1))
in
if n == 0 then errorWithoutStackTrace "foldr1: empty Array" else go 0
{-# INLINE assocs #-}
assocs :: Ix i => Array i e -> [(i, e)]
assocs arr@(Array l u _ _) =
[(i, arr ! i) | i <- range (l,u)]
{-# INLINE accumArray #-}
accumArray :: Ix i
=> (e -> a -> e)
-> e
-> (i,i)
-> [(i, a)]
-> Array i e
accumArray f initial (l,u) ies =
let n = safeRangeSize (l,u)
in unsafeAccumArray' f initial (l,u) n
[(safeIndex (l,u) n i, e) | (i, e) <- ies]
{-# INLINE unsafeAccumArray #-}
unsafeAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(Int, a)] -> Array i e
unsafeAccumArray f initial b ies = unsafeAccumArray' f initial b (rangeSize b) ies
{-# INLINE unsafeAccumArray' #-}
unsafeAccumArray' :: (e -> a -> e) -> e -> (i,i) -> Int -> [(Int, a)] -> Array i e
unsafeAccumArray' f initial (l,u) n@(I# n#) ies = runST (ST $ \s1# ->
case newArray# n# initial s1# of { (# s2#, marr# #) ->
foldr (adjust f marr#) (done l u n marr#) ies s2# })
{-# INLINE adjust #-}
adjust :: (e -> a -> e) -> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b
adjust f marr# (I# i#, new) next
= \s1# -> case readArray# marr# i# s1# of
(# s2#, old #) ->
case writeArray# marr# i# (f old new) s2# of
s3# -> next s3#
{-# INLINE (//) #-}
(//) :: Ix i => Array i e -> [(i, e)] -> Array i e
arr@(Array l u n _) // ies =
unsafeReplace arr [(safeIndex (l,u) n i, e) | (i, e) <- ies]
{-# INLINE unsafeReplace #-}
unsafeReplace :: Array i e -> [(Int, e)] -> Array i e
unsafeReplace arr ies = runST (do
STArray l u n marr# <- thawSTArray arr
ST (foldr (fill marr#) (done l u n marr#) ies))
{-# INLINE accum #-}
accum :: Ix i => (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
accum f arr@(Array l u n _) ies =
unsafeAccum f arr [(safeIndex (l,u) n i, e) | (i, e) <- ies]
{-# INLINE unsafeAccum #-}
unsafeAccum :: (e -> a -> e) -> Array i e -> [(Int, a)] -> Array i e
unsafeAccum f arr ies = runST (do
STArray l u n marr# <- thawSTArray arr
ST (foldr (adjust f marr#) (done l u n marr#) ies))
{-# INLINE [1] amap #-}
amap :: (a -> b) -> Array i a -> Array i b
amap f arr@(Array l u n@(I# n#) _) = runST (ST $ \s1# ->
case newArray# n# arrEleBottom s1# of
(# s2#, marr# #) ->
let go i s#
| i == n = done l u n marr# s#
| otherwise = fill marr# (i, f (unsafeAt arr i)) (go (i+1)) s#
in go 0 s2# )
{-# RULES
"amap/coerce" amap coerce = coerce -- See Note [amap]
#-}
{-# RULES
"amap/amap" forall f g a . amap f (amap g a) = amap (f . g) a
#-}
{-# INLINE ixmap #-}
ixmap :: (Ix i, Ix j) => (i,i) -> (i -> j) -> Array j e -> Array i e
ixmap (l,u) f arr =
array (l,u) [(i, arr ! f i) | i <- range (l,u)]
{-# INLINE eqArray #-}
eqArray :: (Ix i, Eq e) => Array i e -> Array i e -> Bool
eqArray arr1@(Array l1 u1 n1 _) arr2@(Array l2 u2 n2 _) =
if n1 == 0 then n2 == 0 else
l1 == l2 && u1 == u2 &&
and [unsafeAt arr1 i == unsafeAt arr2 i | i <- [0 .. n1 - 1]]
{-# INLINE [1] cmpArray #-}
cmpArray :: (Ix i, Ord e) => Array i e -> Array i e -> Ordering
cmpArray arr1 arr2 = compare (assocs arr1) (assocs arr2)
{-# INLINE cmpIntArray #-}
cmpIntArray :: Ord e => Array Int e -> Array Int e -> Ordering
cmpIntArray arr1@(Array l1 u1 n1 _) arr2@(Array l2 u2 n2 _) =
if n1 == 0 then
if n2 == 0 then EQ else LT
else if n2 == 0 then GT
else case compare l1 l2 of
EQ -> foldr cmp (compare u1 u2) [0 .. (n1 `min` n2) - 1]
other -> other
where
cmp i rest = case compare (unsafeAt arr1 i) (unsafeAt arr2 i) of
EQ -> rest
other -> other
{-# RULES "cmpArray/Int" cmpArray = cmpIntArray #-}
instance Functor (Array i) where
fmap = amap
instance (Ix i, Eq e) => Eq (Array i e) where
(==) = eqArray
instance (Ix i, Ord e) => Ord (Array i e) where
compare = cmpArray
instance (Ix a, Show a, Show b) => Show (Array a b) where
showsPrec p a =
showParen (p > appPrec) $
showString "array " .
showsPrec appPrec1 (bounds a) .
showChar ' ' .
showsPrec appPrec1 (assocs a)
{-# INLINE newSTArray #-}
newSTArray :: Ix i => (i,i) -> e -> ST s (STArray s i e)
newSTArray (l,u) initial = ST $ \s1# ->
case safeRangeSize (l,u) of { n@(I# n#) ->
case newArray# n# initial s1# of { (# s2#, marr# #) ->
(# s2#, STArray l u n marr# #) }}
{-# INLINE boundsSTArray #-}
boundsSTArray :: STArray s i e -> (i,i)
boundsSTArray (STArray l u _ _) = (l,u)
{-# INLINE numElementsSTArray #-}
numElementsSTArray :: STArray s i e -> Int
numElementsSTArray (STArray _ _ n _) = n
{-# INLINE readSTArray #-}
readSTArray :: Ix i => STArray s i e -> i -> ST s e
readSTArray marr@(STArray l u n _) i =
unsafeReadSTArray marr (safeIndex (l,u) n i)
{-# INLINE unsafeReadSTArray #-}
unsafeReadSTArray :: STArray s i e -> Int -> ST s e
unsafeReadSTArray (STArray _ _ _ marr#) (I# i#)
= ST $ \s1# -> readArray# marr# i# s1#
{-# INLINE writeSTArray #-}
writeSTArray :: Ix i => STArray s i e -> i -> e -> ST s ()
writeSTArray marr@(STArray l u n _) i e =
unsafeWriteSTArray marr (safeIndex (l,u) n i) e
{-# INLINE unsafeWriteSTArray #-}
unsafeWriteSTArray :: STArray s i e -> Int -> e -> ST s ()
unsafeWriteSTArray (STArray _ _ _ marr#) (I# i#) e = ST $ \s1# ->
case writeArray# marr# i# e s1# of
s2# -> (# s2#, () #)
freezeSTArray :: STArray s i e -> ST s (Array i e)
freezeSTArray (STArray l u n@(I# n#) marr#) = ST $ \s1# ->
case newArray# n# arrEleBottom s1# of { (# s2#, marr'# #) ->
let copy i# s3# | isTrue# (i# ==# n#) = s3#
| otherwise =
case readArray# marr# i# s3# of { (# s4#, e #) ->
case writeArray# marr'# i# e s4# of { s5# ->
copy (i# +# 1#) s5# }} in
case copy 0# s2# of { s3# ->
case unsafeFreezeArray# marr'# s3# of { (# s4#, arr# #) ->
(# s4#, Array l u n arr# #) }}}
{-# INLINE unsafeFreezeSTArray #-}
unsafeFreezeSTArray :: STArray s i e -> ST s (Array i e)
unsafeFreezeSTArray (STArray l u n marr#) = ST $ \s1# ->
case unsafeFreezeArray# marr# s1# of { (# s2#, arr# #) ->
(# s2#, Array l u n arr# #) }
thawSTArray :: Array i e -> ST s (STArray s i e)
thawSTArray (Array l u n@(I# n#) arr#) = ST $ \s1# ->
case newArray# n# arrEleBottom s1# of { (# s2#, marr# #) ->
let copy i# s3# | isTrue# (i# ==# n#) = s3#
| otherwise =
case indexArray# arr# i# of { (# e #) ->
case writeArray# marr# i# e s3# of { s4# ->
copy (i# +# 1#) s4# }} in
case copy 0# s2# of { s3# ->
(# s3#, STArray l u n marr# #) }}
{-# INLINE unsafeThawSTArray #-}
unsafeThawSTArray :: Array i e -> ST s (STArray s i e)
unsafeThawSTArray (Array l u n arr#) = ST $ \s1# ->
case unsafeThawArray# arr# s1# of { (# s2#, marr# #) ->
(# s2#, STArray l u n marr# #) }