{-# LANGUAGE Unsafe #-}
{-# LANGUAGE NoImplicitPrelude, MagicHash, UnboxedTuples, RoleAnnotations #-}
{-# LANGUAGE BangPatterns #-}
{-# OPTIONS_HADDOCK not-home #-}

-----------------------------------------------------------------------------
-- |
-- Module      :  GHC.Arr
-- Copyright   :  (c) The University of Glasgow, 1994-2000
-- License     :  see libraries/base/LICENSE
--
-- Maintainer  :  cvs-ghc@haskell.org
-- Stability   :  internal
-- Portability :  non-portable (GHC extensions)
--
-- GHC\'s array implementation.
--
-----------------------------------------------------------------------------

module GHC.Arr (
        Ix(..), Array(..), STArray(..),

        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,

        -- * Unsafe operations
        fill, done,
        unsafeArray, unsafeArray',
        lessSafeIndex, unsafeAt, unsafeReplace,
        unsafeAccumArray, unsafeAccumArray', unsafeAccum,
        unsafeReadSTArray, unsafeWriteSTArray,
        unsafeFreezeSTArray, unsafeThawSTArray,
    ) where

import GHC.Num
import GHC.ST
import GHC.Base
import GHC.List
import GHC.Ix
import GHC.Show

infixl 9  !, //

default ()

-- | The type of immutable non-strict (boxed) arrays
-- with indices in @i@ and elements in @e@.
data Array i e
   = Array            !i         -- the lower bound, l
                      !i         -- the upper bound, u
       {-# UNPACK #-} !Int       -- A cache of (rangeSize (l,u))
                                 -- used to make sure an index is
                                 -- really in range
                      (Array# e) -- The actual elements

-- | Mutable, boxed, non-strict arrays in the 'ST' monad.  The type
-- arguments are as follows:
--
--  * @s@: the state variable argument for the 'ST' type
--
--  * @i@: the index type of the array (should be an instance of 'Ix')
--
--  * @e@: the element type of the array.
--
data STArray s i e
  = STArray           !i               -- the lower bound, l
                      !i               -- the upper bound, u
      {-# UNPACK #-}  !Int             -- A cache of (rangeSize (l,u))
                                       -- used to make sure an index is
                                       -- really in range
                   (MutableArray# s e) -- The actual elements
        -- No Ix context for STArray.  They are stupid,
        -- and force an Ix context on the equality instance.

-- Index types should have nominal role, because of Ix class. See also #9220.
type role Array nominal representational
type role STArray nominal nominal representational

-- Just pointer equality on mutable arrays:
-- | @since 2.01
instance Eq (STArray s i e) where
    STArray i
_ i
_ Int
_ MutableArray# s e
arr1# == :: STArray s i e -> STArray s i e -> Bool
== STArray i
_ i
_ Int
_ MutableArray# s e
arr2# =
        Int# -> Bool
isTrue# (MutableArray# s e -> MutableArray# s e -> Int#
forall s a. MutableArray# s a -> MutableArray# s a -> Int#
sameMutableArray# MutableArray# s e
arr1# MutableArray# s e
arr2#)

----------------------------------------------------------------------
-- Operations on immutable arrays

{-# NOINLINE arrEleBottom #-}
arrEleBottom :: a
arrEleBottom :: forall a. a
arrEleBottom = [Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace [Char]
"(Array.!): undefined array element"

-- | Construct an array with the specified bounds and containing values
-- for given indices within these bounds.
--
-- The array is undefined (i.e. bottom) if any index in the list is
-- out of bounds.  The Haskell 2010 Report further specifies that if any
-- two associations in the list have the same index, the value at that
-- index is undefined (i.e. bottom).  However in GHC's implementation,
-- the value at such an index is the value part of the last association
-- with that index in the list.
--
-- Because the indices must be checked for these errors, 'array' is
-- strict in the bounds argument and in the indices of the association
-- list, but non-strict in the values.  Thus, recurrences such as the
-- following are possible:
--
-- > a = array (1,100) ((1,1) : [(i, i * a!(i-1)) | i <- [2..100]])
--
-- Not every index within the bounds of the array need appear in the
-- association list, but the values associated with indices that do not
-- appear will be undefined (i.e. bottom).
--
-- If, in any dimension, the lower bound is greater than the upper bound,
-- then the array is legal, but empty.  Indexing an empty array always
-- gives an array-bounds error, but 'bounds' still yields the bounds
-- with which the array was constructed.
{-# INLINE array #-}
array :: Ix i
        => (i,i)        -- ^ a pair of /bounds/, each of the index type
                        -- of the array.  These bounds are the lowest and
                        -- highest indices in the array, in that order.
                        -- For example, a one-origin vector of length
                        -- @10@ has bounds @(1,10)@, and a one-origin @10@
                        -- by @10@ matrix has bounds @((1,1),(10,10))@.
        -> [(i, e)]     -- ^ a list of /associations/ of the form
                        -- (/index/, /value/).  Typically, this list will
                        -- be expressed as a comprehension.  An
                        -- association @(i, x)@ defines the value of
                        -- the array at index @i@ to be @x@.
        -> Array i e
array :: forall i e. Ix i => (i, i) -> [(i, e)] -> Array i e
array (i
l,i
u) [(i, e)]
ies
    = let n :: Int
n = (i, i) -> Int
forall i. Ix i => (i, i) -> Int
safeRangeSize (i
l,i
u)
      in (i, i) -> Int -> [(Int, e)] -> Array i e
forall i e. (i, i) -> Int -> [(Int, e)] -> Array i e
unsafeArray' (i
l,i
u) Int
n
                      [((i, i) -> Int -> i -> Int
forall i. Ix i => (i, i) -> Int -> i -> Int
safeIndex (i
l,i
u) Int
n i
i, e
e) | (i
i, e
e) <- [(i, e)]
ies]

{-# INLINE unsafeArray #-}
unsafeArray :: Ix i => (i,i) -> [(Int, e)] -> Array i e
unsafeArray :: forall i e. Ix i => (i, i) -> [(Int, e)] -> Array i e
unsafeArray (i, i)
b [(Int, e)]
ies = (i, i) -> Int -> [(Int, e)] -> Array i e
forall i e. (i, i) -> Int -> [(Int, e)] -> Array i e
unsafeArray' (i, i)
b ((i, i) -> Int
forall i. Ix i => (i, i) -> Int
rangeSize (i, i)
b) [(Int, e)]
ies

{-# INLINE unsafeArray' #-}
unsafeArray' :: (i,i) -> Int -> [(Int, e)] -> Array i e
unsafeArray' :: forall i e. (i, i) -> Int -> [(Int, e)] -> Array i e
unsafeArray' (i
l,i
u) n :: Int
n@(I# Int#
n#) [(Int, e)]
ies = (forall s. ST s (Array i e)) -> Array i e
forall a. (forall s. ST s a) -> a
runST (STRep s (Array i e) -> ST s (Array i e)
forall s a. STRep s a -> ST s a
ST (STRep s (Array i e) -> ST s (Array i e))
-> STRep s (Array i e) -> ST s (Array i e)
forall a b. (a -> b) -> a -> b
$ \State# s
s1# ->
    case Int# -> e -> State# s -> (# State# s, MutableArray# s e #)
forall a d.
Int# -> a -> State# d -> (# State# d, MutableArray# d a #)
newArray# Int#
n# e
forall a. a
arrEleBottom State# s
s1# of
        (# State# s
s2#, MutableArray# s e
marr# #) ->
            ((Int, e) -> STRep s (Array i e) -> STRep s (Array i e))
-> STRep s (Array i e) -> [(Int, e)] -> STRep s (Array i e)
forall a b. (a -> b -> b) -> b -> [a] -> b
foldr (MutableArray# s e
-> (Int, e) -> STRep s (Array i e) -> STRep s (Array i e)
forall s e a.
MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
fill MutableArray# s e
marr#) (i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
forall i s e.
i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
done i
l i
u Int
n MutableArray# s e
marr#) [(Int, e)]
ies State# s
s2#)

{-# INLINE fill #-}
fill :: MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
-- NB: put the \s after the "=" so that 'fill'
--     inlines when applied to three args
fill :: forall s e a.
MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
fill MutableArray# s e
marr# (I# Int#
i#, e
e) STRep s a
next
 = \State# s
s1# -> case MutableArray# s e -> Int# -> e -> State# s -> State# s
forall d a. MutableArray# d a -> Int# -> a -> State# d -> State# d
writeArray# MutableArray# s e
marr# Int#
i# e
e State# s
s1# of
             State# s
s2# -> STRep s a
next State# s
s2#

{-# INLINE done #-}
done :: i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
-- See NB on 'fill'
-- Make sure it is strict in 'n'
done :: forall i s e.
i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
done i
l i
u n :: Int
n@(I# Int#
_) MutableArray# s e
marr#
  = \State# s
s1# -> case MutableArray# s e -> State# s -> (# State# s, Array# e #)
forall d a.
MutableArray# d a -> State# d -> (# State# d, Array# a #)
unsafeFreezeArray# MutableArray# s e
marr# State# s
s1# of
              (# State# s
s2#, Array# e
arr# #) -> (# State# s
s2#, i -> i -> Int -> Array# e -> Array i e
forall i e. i -> i -> Int -> Array# e -> Array i e
Array i
l i
u Int
n Array# e
arr# #)

-- | Construct an array from a pair of bounds and a list of values in
-- index order.
{-# INLINE listArray #-}
listArray :: Ix i => (i,i) -> [e] -> Array i e
listArray :: forall i e. Ix i => (i, i) -> [e] -> Array i e
listArray (i
l,i
u) [e]
es = (forall s. ST s (Array i e)) -> Array i e
forall a. (forall s. ST s a) -> a
runST (STRep s (Array i e) -> ST s (Array i e)
forall s a. STRep s a -> ST s a
ST (STRep s (Array i e) -> ST s (Array i e))
-> STRep s (Array i e) -> ST s (Array i e)
forall a b. (a -> b) -> a -> b
$ \State# s
s1# ->
    case (i, i) -> Int
forall i. Ix i => (i, i) -> Int
safeRangeSize (i
l,i
u)            of { n :: Int
n@(I# Int#
n#) ->
    case Int# -> e -> State# s -> (# State# s, MutableArray# s e #)
forall a d.
Int# -> a -> State# d -> (# State# d, MutableArray# d a #)
newArray# Int#
n# e
forall a. a
arrEleBottom State# s
s1#  of { (# State# s
s2#, MutableArray# s e
marr# #) ->
      let
        go :: e -> (Int# -> State# s -> State# s) -> Int# -> State# s -> State# s
go e
y Int# -> State# s -> State# s
r = \ Int#
i# State# s
s3# ->
            case MutableArray# s e -> Int# -> e -> State# s -> State# s
forall d a. MutableArray# d a -> Int# -> a -> State# d -> State# d
writeArray# MutableArray# s e
marr# Int#
i# e
y State# s
s3# of
              State# s
s4# -> if (Int# -> Bool
isTrue# (Int#
i# Int# -> Int# -> Int#
==# Int#
n# Int# -> Int# -> Int#
-# Int#
1#))
                     then State# s
s4#
                     else Int# -> State# s -> State# s
r (Int#
i# Int# -> Int# -> Int#
+# Int#
1#) State# s
s4#
      in
        i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
forall i s e.
i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
done i
l i
u Int
n MutableArray# s e
marr# (
          if Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0
          then State# s
s2#
          else (e
 -> (Int# -> State# s -> State# s) -> Int# -> State# s -> State# s)
-> (Int# -> State# s -> State# s)
-> [e]
-> Int#
-> State# s
-> State# s
forall a b. (a -> b -> b) -> b -> [a] -> b
foldr e -> (Int# -> State# s -> State# s) -> Int# -> State# s -> State# s
go (\Int#
_ State# s
s# -> State# s
s#) [e]
es Int#
0# State# s
s2#)}})

-- | The value at the given index in an array.
{-# INLINE (!) #-}
(!) :: Ix i => Array i e -> i -> e
! :: forall i e. Ix i => Array i e -> i -> e
(!) arr :: Array i e
arr@(Array i
l i
u Int
n Array# e
_) i
i = Array i e -> Int -> e
forall i e. Array i e -> Int -> e
unsafeAt Array i e
arr (Int -> e) -> Int -> e
forall a b. (a -> b) -> a -> b
$ (i, i) -> Int -> i -> Int
forall i. Ix i => (i, i) -> Int -> i -> Int
safeIndex (i
l,i
u) Int
n i
i

{-# INLINE (!#) #-}
(!#) :: Ix i => Array i e -> i -> (# e #)
!# :: forall i e. Ix i => Array i e -> i -> (# e #)
(!#) arr :: Array i e
arr@(Array i
l i
u Int
n Array# e
_) i
i = Array i e -> Int -> (# e #)
forall i e. Array i e -> Int -> (# e #)
unsafeAt# Array i e
arr (Int -> (# e #)) -> Int -> (# e #)
forall a b. (a -> b) -> a -> b
$ (i, i) -> Int -> i -> Int
forall i. Ix i => (i, i) -> Int -> i -> Int
safeIndex (i
l,i
u) Int
n i
i

{-# INLINE safeRangeSize #-}
safeRangeSize :: Ix i => (i, i) -> Int
safeRangeSize :: forall i. Ix i => (i, i) -> Int
safeRangeSize (i
l,i
u) = let r :: Int
r = (i, i) -> Int
forall i. Ix i => (i, i) -> Int
rangeSize (i
l, i
u)
                      in if Int
r Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 then Int
negRange
                                  else Int
r

-- Don't inline this error message everywhere!!
negRange :: Int   -- Uninformative, but Ix does not provide Show
negRange :: Int
negRange = [Char] -> Int
forall a. [Char] -> a
errorWithoutStackTrace [Char]
"Negative range size"

{-# INLINE[1] safeIndex #-}
-- See Note [Double bounds-checking of index values]
-- Inline *after* (!) so the rules can fire
-- Make sure it is strict in n
safeIndex :: Ix i => (i, i) -> Int -> i -> Int
safeIndex :: forall i. Ix i => (i, i) -> Int -> i -> Int
safeIndex (i
l,i
u) n :: Int
n@(I# Int#
_) i
i
  | (Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
i') Bool -> Bool -> Bool
&& (Int
i' Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n) = Int
i'
  | Bool
otherwise             = Int -> Int -> Int
badSafeIndex Int
i' Int
n
  where
    i' :: Int
i' = (i, i) -> i -> Int
forall a. Ix a => (a, a) -> a -> Int
index (i
l,i
u) i
i

-- See Note [Double bounds-checking of index values]
{-# 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
-- See Note [Double bounds-checking of index values]
-- Do only (A), the semantic check
lessSafeIndex :: forall i. Ix i => (i, i) -> Int -> i -> Int
lessSafeIndex (i
l,i
u) Int
_ i
i = (i, i) -> i -> Int
forall a. Ix a => (a, a) -> a -> Int
index (i
l,i
u) i
i

-- Don't inline this long error message everywhere!!
badSafeIndex :: Int -> Int -> Int
badSafeIndex :: Int -> Int -> Int
badSafeIndex Int
i' Int
n = [Char] -> Int
forall a. [Char] -> a
errorWithoutStackTrace ([Char]
"Error in array index; " [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ Int -> [Char]
forall a. Show a => a -> [Char]
show Int
i' [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++
                        [Char]
" not in range [0.." [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ Int -> [Char]
forall a. Show a => a -> [Char]
show Int
n [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
")")

{-# INLINE unsafeAt #-}
unsafeAt :: Array i e -> Int -> e
unsafeAt :: forall i e. Array i e -> Int -> e
unsafeAt (Array i
_ i
_ Int
_ Array# e
arr#) (I# Int#
i#) =
    case Array# e -> Int# -> (# e #)
forall a. Array# a -> Int# -> (# a #)
indexArray# Array# e
arr# Int#
i# of (# e
e #) -> e
e

-- | Look up an element in an array without forcing it
unsafeAt# :: Array i e -> Int -> (# e #)
unsafeAt# :: forall i e. Array i e -> Int -> (# e #)
unsafeAt# (Array i
_ i
_ Int
_ Array# e
arr#) (I# Int#
i#) = Array# e -> Int# -> (# e #)
forall a. Array# a -> Int# -> (# a #)
indexArray# Array# e
arr# Int#
i#

-- | A convenient version of unsafeAt#
unsafeAtA :: Applicative f
          => Array i e -> Int -> f e
unsafeAtA :: forall (f :: * -> *) i e. Applicative f => Array i e -> Int -> f e
unsafeAtA Array i e
ary Int
i = case Array i e -> Int -> (# e #)
forall i e. Array i e -> Int -> (# e #)
unsafeAt# Array i e
ary Int
i of (# e
e #) -> e -> f e
forall (f :: * -> *) a. Applicative f => a -> f a
pure e
e

-- | The bounds with which an array was constructed.
{-# INLINE bounds #-}
bounds :: Array i e -> (i,i)
bounds :: forall i e. Array i e -> (i, i)
bounds (Array i
l i
u Int
_ Array# e
_) = (i
l,i
u)

-- | The number of elements in the array.
{-# INLINE numElements #-}
numElements :: Array i e -> Int
numElements :: forall i e. Array i e -> Int
numElements (Array i
_ i
_ Int
n Array# e
_) = Int
n

-- | The list of indices of an array in ascending order.
{-# INLINE indices #-}
indices :: Ix i => Array i e -> [i]
indices :: forall i e. Ix i => Array i e -> [i]
indices (Array i
l i
u Int
_ Array# e
_) = (i, i) -> [i]
forall a. Ix a => (a, a) -> [a]
range (i
l,i
u)

-- | The list of elements of an array in index order.
{-# INLINE elems #-}
elems :: Array i e -> [e]
elems :: forall i e. Array i e -> [e]
elems arr :: Array i e
arr@(Array i
_ i
_ Int
n Array# e
_) =
    [e
e | Int
i <- [Int
0 .. Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1], e
e <- Array i e -> Int -> [e]
forall (f :: * -> *) i e. Applicative f => Array i e -> Int -> f e
unsafeAtA Array i e
arr Int
i]

-- | A right fold over the elements
{-# INLINABLE foldrElems #-}
foldrElems :: (a -> b -> b) -> b -> Array i a -> b
foldrElems :: forall a b i. (a -> b -> b) -> b -> Array i a -> b
foldrElems a -> b -> b
f b
b0 = \ arr :: Array i a
arr@(Array i
_ i
_ Int
n Array# a
_) ->
  let
    go :: Int -> b
go Int
i | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
n    = b
b0
         | (# a
e #) <- Array i a -> Int -> (# a #)
forall i e. Array i e -> Int -> (# e #)
unsafeAt# Array i a
arr Int
i
         = a -> b -> b
f a
e (Int -> b
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1))
  in Int -> b
go Int
0

-- | A left fold over the elements
{-# INLINABLE foldlElems #-}
foldlElems :: (b -> a -> b) -> b -> Array i a -> b
foldlElems :: forall b a i. (b -> a -> b) -> b -> Array i a -> b
foldlElems b -> a -> b
f b
b0 = \ arr :: Array i a
arr@(Array i
_ i
_ Int
n Array# a
_) ->
  let
    go :: Int -> b
go Int
i | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== (-Int
1) = b
b0
         | (# a
e #) <- Array i a -> Int -> (# a #)
forall i e. Array i e -> Int -> (# e #)
unsafeAt# Array i a
arr Int
i
         = b -> a -> b
f (Int -> b
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)) a
e
  in Int -> b
go (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)

-- | A strict right fold over the elements
{-# INLINABLE foldrElems' #-}
foldrElems' :: (a -> b -> b) -> b -> Array i a -> b
foldrElems' :: forall a b i. (a -> b -> b) -> b -> Array i a -> b
foldrElems' a -> b -> b
f b
b0 = \ arr :: Array i a
arr@(Array i
_ i
_ Int
n Array# a
_) ->
  let
    go :: Int -> b -> b
go Int
i b
a | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== (-Int
1) = b
a
           | (# a
e #) <- Array i a -> Int -> (# a #)
forall i e. Array i e -> Int -> (# e #)
unsafeAt# Array i a
arr Int
i
           = Int -> b -> b
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) (a -> b -> b
f a
e (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! b
a)
  in Int -> b -> b
go (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) b
b0

-- | A strict left fold over the elements
{-# INLINABLE foldlElems' #-}
foldlElems' :: (b -> a -> b) -> b -> Array i a -> b
foldlElems' :: forall b a i. (b -> a -> b) -> b -> Array i a -> b
foldlElems' b -> a -> b
f b
b0 = \ arr :: Array i a
arr@(Array i
_ i
_ Int
n Array# a
_) ->
  let
    go :: Int -> b -> b
go Int
i b
a | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
n    = b
a
           | (# a
e #) <- Array i a -> Int -> (# a #)
forall i e. Array i e -> Int -> (# e #)
unsafeAt# Array i a
arr Int
i
           = Int -> b -> b
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (b
a b -> b -> b
forall a b. a -> b -> b
`seq` b -> a -> b
f b
a a
e)
  in Int -> b -> b
go Int
0 b
b0

-- | A left fold over the elements with no starting value
{-# INLINABLE foldl1Elems #-}
foldl1Elems :: (a -> a -> a) -> Array i a -> a
foldl1Elems :: forall a i. (a -> a -> a) -> Array i a -> a
foldl1Elems a -> a -> a
f = \ arr :: Array i a
arr@(Array i
_ i
_ Int
n Array# a
_) ->
  let
    go :: Int -> a
go Int
i | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = Array i a -> Int -> a
forall i e. Array i e -> Int -> e
unsafeAt Array i a
arr Int
0
         | (# a
e #) <- Array i a -> Int -> (# a #)
forall i e. Array i e -> Int -> (# e #)
unsafeAt# Array i a
arr Int
i
         = a -> a -> a
f (Int -> a
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)) a
e
  in
    if Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 then [Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace [Char]
"foldl1: empty Array" else Int -> a
go (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)

-- | A right fold over the elements with no starting value
{-# INLINABLE foldr1Elems #-}
foldr1Elems :: (a -> a -> a) -> Array i a -> a
foldr1Elems :: forall a i. (a -> a -> a) -> Array i a -> a
foldr1Elems a -> a -> a
f = \ arr :: Array i a
arr@(Array i
_ i
_ Int
n Array# a
_) ->
  let
    go :: Int -> a
go Int
i | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1  = Array i a -> Int -> a
forall i e. Array i e -> Int -> e
unsafeAt Array i a
arr Int
i
         | (# a
e #) <- Array i a -> Int -> (# a #)
forall i e. Array i e -> Int -> (# e #)
unsafeAt# Array i a
arr Int
i
         = a -> a -> a
f a
e (Int -> a
go (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1))
  in
    if Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 then [Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace [Char]
"foldr1: empty Array" else Int -> a
go Int
0

-- | The list of associations of an array in index order.
{-# INLINE assocs #-}
assocs :: Ix i => Array i e -> [(i, e)]
assocs :: forall i e. Ix i => Array i e -> [(i, e)]
assocs arr :: Array i e
arr@(Array i
l i
u Int
_ Array# e
_) =
    [(i
i, e
e) | i
i <- (i, i) -> [i]
forall a. Ix a => (a, a) -> [a]
range (i
l,i
u), let !(# e
e #) = Array i e
arr Array i e -> i -> (# e #)
forall i e. Ix i => Array i e -> i -> (# e #)
!# i
i]

-- | The 'accumArray' function deals with repeated indices in the association
-- list using an /accumulating function/ which combines the values of
-- associations with the same index.
--
-- For example, given a list of values of some index type, @hist@
-- produces a histogram of the number of occurrences of each index within
-- a specified range:
--
-- > hist :: (Ix a, Num b) => (a,a) -> [a] -> Array a b
-- > hist bnds is = accumArray (+) 0 bnds [(i, 1) | i<-is, inRange bnds i]
--
-- @accumArray@ is strict in each result of applying the accumulating
-- function, although it is lazy in the initial value. Thus, unlike
-- arrays built with 'array', accumulated arrays should not in general
-- be recursive.
{-# INLINE accumArray #-}
accumArray :: Ix i
        => (e -> a -> e)        -- ^ accumulating function
        -> e                    -- ^ initial value
        -> (i,i)                -- ^ bounds of the array
        -> [(i, a)]             -- ^ association list
        -> Array i e
accumArray :: forall i e a.
Ix i =>
(e -> a -> e) -> e -> (i, i) -> [(i, a)] -> Array i e
accumArray e -> a -> e
f e
initial (i
l,i
u) [(i, a)]
ies =
    let n :: Int
n = (i, i) -> Int
forall i. Ix i => (i, i) -> Int
safeRangeSize (i
l,i
u)
    in (e -> a -> e) -> e -> (i, i) -> Int -> [(Int, a)] -> Array i e
forall e a i.
(e -> a -> e) -> e -> (i, i) -> Int -> [(Int, a)] -> Array i e
unsafeAccumArray' e -> a -> e
f e
initial (i
l,i
u) Int
n
                         [((i, i) -> Int -> i -> Int
forall i. Ix i => (i, i) -> Int -> i -> Int
safeIndex (i
l,i
u) Int
n i
i, a
e) | (i
i, a
e) <- [(i, a)]
ies]

{-# INLINE unsafeAccumArray #-}
unsafeAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(Int, a)] -> Array i e
unsafeAccumArray :: forall i e a.
Ix i =>
(e -> a -> e) -> e -> (i, i) -> [(Int, a)] -> Array i e
unsafeAccumArray e -> a -> e
f e
initial (i, i)
b [(Int, a)]
ies = (e -> a -> e) -> e -> (i, i) -> Int -> [(Int, a)] -> Array i e
forall e a i.
(e -> a -> e) -> e -> (i, i) -> Int -> [(Int, a)] -> Array i e
unsafeAccumArray' e -> a -> e
f e
initial (i, i)
b ((i, i) -> Int
forall i. Ix i => (i, i) -> Int
rangeSize (i, i)
b) [(Int, a)]
ies

{-# INLINE unsafeAccumArray' #-}
unsafeAccumArray' :: (e -> a -> e) -> e -> (i,i) -> Int -> [(Int, a)] -> Array i e
unsafeAccumArray' :: forall e a i.
(e -> a -> e) -> e -> (i, i) -> Int -> [(Int, a)] -> Array i e
unsafeAccumArray' e -> a -> e
f e
initial (i
l,i
u) n :: Int
n@(I# Int#
n#) [(Int, a)]
ies = (forall s. ST s (Array i e)) -> Array i e
forall a. (forall s. ST s a) -> a
runST (STRep s (Array i e) -> ST s (Array i e)
forall s a. STRep s a -> ST s a
ST (STRep s (Array i e) -> ST s (Array i e))
-> STRep s (Array i e) -> ST s (Array i e)
forall a b. (a -> b) -> a -> b
$ \State# s
s1# ->
    case Int# -> e -> State# s -> (# State# s, MutableArray# s e #)
forall a d.
Int# -> a -> State# d -> (# State# d, MutableArray# d a #)
newArray# Int#
n# e
initial State# s
s1#          of { (# State# s
s2#, MutableArray# s e
marr# #) ->
    ((Int, a) -> STRep s (Array i e) -> STRep s (Array i e))
-> STRep s (Array i e) -> [(Int, a)] -> STRep s (Array i e)
forall a b. (a -> b -> b) -> b -> [a] -> b
foldr ((e -> a -> e)
-> MutableArray# s e
-> (Int, a)
-> STRep s (Array i e)
-> STRep s (Array i e)
forall e a s b.
(e -> a -> e)
-> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b
adjust' e -> a -> e
f MutableArray# s e
marr#) (i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
forall i s e.
i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
done i
l i
u Int
n MutableArray# s e
marr#) [(Int, a)]
ies State# s
s2# })

{-# INLINE adjust #-}
adjust :: (e -> a -> e) -> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b
-- See NB on 'fill'
adjust :: forall e a s b.
(e -> a -> e)
-> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b
adjust e -> a -> e
f MutableArray# s e
marr# (I# Int#
i#, a
new) STRep s b
next
  = \State# s
s1# -> case MutableArray# s e -> Int# -> State# s -> (# State# s, e #)
forall d a.
MutableArray# d a -> Int# -> State# d -> (# State# d, a #)
readArray# MutableArray# s e
marr# Int#
i# State# s
s1# of
                (# State# s
s2#, e
old #) ->
                    case MutableArray# s e -> Int# -> e -> State# s -> State# s
forall d a. MutableArray# d a -> Int# -> a -> State# d -> State# d
writeArray# MutableArray# s e
marr# Int#
i# (e -> a -> e
f e
old a
new) State# s
s2# of
                        State# s
s3# -> STRep s b
next State# s
s3#

{-# INLINE adjust' #-}
adjust' :: (e -> a -> e)
        -> MutableArray# s e
        -> (Int, a)
        -> STRep s b -> STRep s b
adjust' :: forall e a s b.
(e -> a -> e)
-> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b
adjust' e -> a -> e
f MutableArray# s e
marr# (I# Int#
i#, a
new) STRep s b
next
  = \State# s
s1# -> case MutableArray# s e -> Int# -> State# s -> (# State# s, e #)
forall d a.
MutableArray# d a -> Int# -> State# d -> (# State# d, a #)
readArray# MutableArray# s e
marr# Int#
i# State# s
s1# of
                (# State# s
s2#, e
old #) ->
                    let !combined :: e
combined = e -> a -> e
f e
old a
new
                    in STRep s b
next (MutableArray# s e -> Int# -> e -> State# s -> State# s
forall d a. MutableArray# d a -> Int# -> a -> State# d -> State# d
writeArray# MutableArray# s e
marr# Int#
i# e
combined State# s
s2#)


-- | Constructs an array identical to the first argument except that it has
-- been updated by the associations in the right argument.
-- For example, if @m@ is a 1-origin, @n@ by @n@ matrix, then
--
-- > m//[((i,i), 0) | i <- [1..n]]
--
-- is the same matrix, except with the diagonal zeroed.
--
-- Repeated indices in the association list are handled as for 'array':
-- Haskell 2010 specifies that the resulting array is undefined (i.e. bottom),
-- but GHC's implementation uses the last association for each index.
{-# INLINE (//) #-}
(//) :: Ix i => Array i e -> [(i, e)] -> Array i e
arr :: Array i e
arr@(Array i
l i
u Int
n Array# e
_) // :: forall i e. Ix i => Array i e -> [(i, e)] -> Array i e
// [(i, e)]
ies =
    Array i e -> [(Int, e)] -> Array i e
forall i e. Array i e -> [(Int, e)] -> Array i e
unsafeReplace Array i e
arr [((i, i) -> Int -> i -> Int
forall i. Ix i => (i, i) -> Int -> i -> Int
safeIndex (i
l,i
u) Int
n i
i, e
e) | (i
i, e
e) <- [(i, e)]
ies]

{-# INLINE unsafeReplace #-}
unsafeReplace :: Array i e -> [(Int, e)] -> Array i e
unsafeReplace :: forall i e. Array i e -> [(Int, e)] -> Array i e
unsafeReplace Array i e
arr [(Int, e)]
ies = (forall s. ST s (Array i e)) -> Array i e
forall a. (forall s. ST s a) -> a
runST (do
    STArray i
l i
u Int
n MutableArray# s e
marr# <- Array i e -> ST s (STArray s i e)
forall i e s. Array i e -> ST s (STArray s i e)
thawSTArray Array i e
arr
    STRep s (Array i e) -> ST s (Array i e)
forall s a. STRep s a -> ST s a
ST (((Int, e) -> STRep s (Array i e) -> STRep s (Array i e))
-> STRep s (Array i e) -> [(Int, e)] -> STRep s (Array i e)
forall a b. (a -> b -> b) -> b -> [a] -> b
foldr (MutableArray# s e
-> (Int, e) -> STRep s (Array i e) -> STRep s (Array i e)
forall s e a.
MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
fill MutableArray# s e
marr#) (i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
forall i s e.
i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
done i
l i
u Int
n MutableArray# s e
marr#) [(Int, e)]
ies))

-- | @'accum' f@ takes an array and an association list and accumulates
-- pairs from the list into the array with the accumulating function @f@.
-- Thus 'accumArray' can be defined using 'accum':
--
-- > accumArray f z b = accum f (array b [(i, z) | i <- range b])
--
-- @accum@ is strict in all the results of applying the accumulation.
-- However, it is lazy in the initial values of the array.
{-# INLINE accum #-}
accum :: Ix i => (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
accum :: forall i e a.
Ix i =>
(e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
accum e -> a -> e
f arr :: Array i e
arr@(Array i
l i
u Int
n Array# e
_) [(i, a)]
ies =
    (e -> a -> e) -> Array i e -> [(Int, a)] -> Array i e
forall e a i. (e -> a -> e) -> Array i e -> [(Int, a)] -> Array i e
unsafeAccum e -> a -> e
f Array i e
arr [((i, i) -> Int -> i -> Int
forall i. Ix i => (i, i) -> Int -> i -> Int
safeIndex (i
l,i
u) Int
n i
i, a
e) | (i
i, a
e) <- [(i, a)]
ies]

{-# INLINE unsafeAccum #-}
unsafeAccum :: (e -> a -> e) -> Array i e -> [(Int, a)] -> Array i e
unsafeAccum :: forall e a i. (e -> a -> e) -> Array i e -> [(Int, a)] -> Array i e
unsafeAccum e -> a -> e
f Array i e
arr [(Int, a)]
ies = (forall s. ST s (Array i e)) -> Array i e
forall a. (forall s. ST s a) -> a
runST (do
    STArray i
l i
u Int
n MutableArray# s e
marr# <- Array i e -> ST s (STArray s i e)
forall i e s. Array i e -> ST s (STArray s i e)
thawSTArray Array i e
arr
    STRep s (Array i e) -> ST s (Array i e)
forall s a. STRep s a -> ST s a
ST (((Int, a) -> STRep s (Array i e) -> STRep s (Array i e))
-> STRep s (Array i e) -> [(Int, a)] -> STRep s (Array i e)
forall a b. (a -> b -> b) -> b -> [a] -> b
foldr ((e -> a -> e)
-> MutableArray# s e
-> (Int, a)
-> STRep s (Array i e)
-> STRep s (Array i e)
forall e a s b.
(e -> a -> e)
-> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b
adjust' e -> a -> e
f MutableArray# s e
marr#) (i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
forall i s e.
i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
done i
l i
u Int
n MutableArray# s e
marr#) [(Int, a)]
ies))

{-# INLINE [1] amap #-}  -- See Note [amap]
amap :: (a -> b) -> Array i a -> Array i b
amap :: forall a b i. (a -> b) -> Array i a -> Array i b
amap a -> b
f arr :: Array i a
arr@(Array i
l i
u n :: Int
n@(I# Int#
n#) Array# a
_) = (forall s. ST s (Array i b)) -> Array i b
forall a. (forall s. ST s a) -> a
runST (STRep s (Array i b) -> ST s (Array i b)
forall s a. STRep s a -> ST s a
ST (STRep s (Array i b) -> ST s (Array i b))
-> STRep s (Array i b) -> ST s (Array i b)
forall a b. (a -> b) -> a -> b
$ \State# s
s1# ->
    case Int# -> b -> State# s -> (# State# s, MutableArray# s b #)
forall a d.
Int# -> a -> State# d -> (# State# d, MutableArray# d a #)
newArray# Int#
n# b
forall a. a
arrEleBottom State# s
s1# of
        (# State# s
s2#, MutableArray# s b
marr# #) ->
          let go :: Int -> STRep s (Array i b)
go Int
i State# s
s#
                | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
n    = i -> i -> Int -> MutableArray# s b -> STRep s (Array i b)
forall i s e.
i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
done i
l i
u Int
n MutableArray# s b
marr# State# s
s#
                | (# a
e #) <- Array i a -> Int -> (# a #)
forall i e. Array i e -> Int -> (# e #)
unsafeAt# Array i a
arr Int
i
                = MutableArray# s b
-> (Int, b) -> STRep s (Array i b) -> STRep s (Array i b)
forall s e a.
MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
fill MutableArray# s b
marr# (Int
i, a -> b
f a
e) (Int -> STRep s (Array i b)
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)) State# s
s#
          in Int -> STRep s (Array i b)
go Int
0 State# s
s2# )

{- Note [amap]
~~~~~~~~~~~~~~
amap was originally defined like this:

 amap f arr@(Array l u n _) =
     unsafeArray' (l,u) n [(i, f (unsafeAt arr i)) | i <- [0 .. n - 1]]

There are two problems:

1. The enumFromTo implementation produces (spurious) code for the impossible
   case of n<0 that ends up duplicating the array freezing code.

2. This implementation relies on list fusion for efficiency. In order
   to implement the "amap/coerce" rule, we need to delay inlining amap
   until simplifier phase 1, which is when the eftIntList rule kicks
   in and makes that impossible.  (c.f. #8767)
-}


-- See Breitner, Eisenberg, Peyton Jones, and Weirich, "Safe Zero-cost
-- Coercions for Haskell", section 6.5:
--   http://research.microsoft.com/en-us/um/people/simonpj/papers/ext-f/coercible.pdf
{-# RULES
"amap/coerce" amap coerce = coerce  -- See Note [amap]
 #-}

-- Second functor law:
{-# RULES
"amap/amap" forall f g a . amap f (amap g a) = amap (f . g) a
 #-}

-- | 'ixmap' allows for transformations on array indices.
-- It may be thought of as providing function composition on the right
-- with the mapping that the original array embodies.
--
-- A similar transformation of array values may be achieved using 'fmap'
-- from the 'Array' instance of the 'Functor' class.
{-# INLINE ixmap #-}
ixmap :: (Ix i, Ix j) => (i,i) -> (i -> j) -> Array j e -> Array i e
ixmap :: forall i j e.
(Ix i, Ix j) =>
(i, i) -> (i -> j) -> Array j e -> Array i e
ixmap (i
l,i
u) i -> j
f Array j e
arr =
    (i, i) -> [(i, e)] -> Array i e
forall i e. Ix i => (i, i) -> [(i, e)] -> Array i e
array (i
l,i
u) [(i
i, Array j e
arr Array j e -> j -> e
forall i e. Ix i => Array i e -> i -> e
! i -> j
f i
i) | i
i <- (i, i) -> [i]
forall a. Ix a => (a, a) -> [a]
range (i
l,i
u)]

{-# INLINE eqArray #-}
eqArray :: (Ix i, Eq e) => Array i e -> Array i e -> Bool
eqArray :: forall i e. (Ix i, Eq e) => Array i e -> Array i e -> Bool
eqArray arr1 :: Array i e
arr1@(Array i
l1 i
u1 Int
n1 Array# e
_) arr2 :: Array i e
arr2@(Array i
l2 i
u2 Int
n2 Array# e
_) =
    if Int
n1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 then Int
n2 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 else
    i
l1 i -> i -> Bool
forall a. Eq a => a -> a -> Bool
== i
l2 Bool -> Bool -> Bool
&& i
u1 i -> i -> Bool
forall a. Eq a => a -> a -> Bool
== i
u2 Bool -> Bool -> Bool
&&
    [Bool] -> Bool
and [Array i e -> Int -> e
forall i e. Array i e -> Int -> e
unsafeAt Array i e
arr1 Int
i e -> e -> Bool
forall a. Eq a => a -> a -> Bool
== Array i e -> Int -> e
forall i e. Array i e -> Int -> e
unsafeAt Array i e
arr2 Int
i | Int
i <- [Int
0 .. Int
n1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1]]

{-# INLINE [1] cmpArray #-}
cmpArray :: (Ix i, Ord e) => Array i e -> Array i e -> Ordering
cmpArray :: forall i e. (Ix i, Ord e) => Array i e -> Array i e -> Ordering
cmpArray Array i e
arr1 Array i e
arr2 = [(i, e)] -> [(i, e)] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Array i e -> [(i, e)]
forall i e. Ix i => Array i e -> [(i, e)]
assocs Array i e
arr1) (Array i e -> [(i, e)]
forall i e. Ix i => Array i e -> [(i, e)]
assocs Array i e
arr2)

{-# INLINE cmpIntArray #-}
cmpIntArray :: Ord e => Array Int e -> Array Int e -> Ordering
cmpIntArray :: forall e. Ord e => Array Int e -> Array Int e -> Ordering
cmpIntArray arr1 :: Array Int e
arr1@(Array Int
l1 Int
u1 Int
n1 Array# e
_) arr2 :: Array Int e
arr2@(Array Int
l2 Int
u2 Int
n2 Array# e
_) =
    if Int
n1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 then
        if Int
n2 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 then Ordering
EQ else Ordering
LT
    else if Int
n2 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 then Ordering
GT
    else case Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Int
l1 Int
l2 of
             Ordering
EQ    -> (Int -> Ordering -> Ordering) -> Ordering -> [Int] -> Ordering
forall a b. (a -> b -> b) -> b -> [a] -> b
foldr Int -> Ordering -> Ordering
cmp (Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Int
u1 Int
u2) [Int
0 .. (Int
n1 Int -> Int -> Int
forall a. Ord a => a -> a -> a
`min` Int
n2) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1]
             Ordering
other -> Ordering
other
  where
    cmp :: Int -> Ordering -> Ordering
cmp Int
i Ordering
rest = case e -> e -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Array Int e -> Int -> e
forall i e. Array i e -> Int -> e
unsafeAt Array Int e
arr1 Int
i) (Array Int e -> Int -> e
forall i e. Array i e -> Int -> e
unsafeAt Array Int e
arr2 Int
i) of
        Ordering
EQ    -> Ordering
rest
        Ordering
other -> Ordering
other

{-# RULES "cmpArray/Int" cmpArray = cmpIntArray #-}

----------------------------------------------------------------------
-- Array instances

-- | @since 2.01
instance Functor (Array i) where
    fmap :: forall a b. (a -> b) -> Array i a -> Array i b
fmap = (a -> b) -> Array i a -> Array i b
forall a b i. (a -> b) -> Array i a -> Array i b
amap

    {-# INLINE (<$) #-}
    a
x <$ :: forall a b. a -> Array i b -> Array i a
<$ Array i
l i
u n :: Int
n@(I# Int#
n#) Array# b
_ =
        -- Sadly we can't just use 'newSTArray' (with 'unsafeFreezeSTArray')
        -- since that would require proof that the indices of the original array
        -- are instances of 'Ix'.
        (forall {s}. ST s (Array i a)) -> Array i a
forall a. (forall s. ST s a) -> a
runST ((forall {s}. ST s (Array i a)) -> Array i a)
-> (forall {s}. ST s (Array i a)) -> Array i a
forall a b. (a -> b) -> a -> b
$ STRep s (Array i a) -> ST s (Array i a)
forall s a. STRep s a -> ST s a
ST (STRep s (Array i a) -> ST s (Array i a))
-> STRep s (Array i a) -> ST s (Array i a)
forall a b. (a -> b) -> a -> b
$ \State# s
s1# ->
            case Int# -> a -> State# s -> (# State# s, MutableArray# s a #)
forall a d.
Int# -> a -> State# d -> (# State# d, MutableArray# d a #)
newArray# Int#
n# a
x State# s
s1# of
                (# State# s
s2#, MutableArray# s a
marr# #) -> i -> i -> Int -> MutableArray# s a -> STRep s (Array i a)
forall i s e.
i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
done i
l i
u Int
n MutableArray# s a
marr# State# s
s2#

-- | @since 2.01
instance (Ix i, Eq e) => Eq (Array i e) where
    == :: Array i e -> Array i e -> Bool
(==) = Array i e -> Array i e -> Bool
forall i e. (Ix i, Eq e) => Array i e -> Array i e -> Bool
eqArray

-- | @since 2.01
instance (Ix i, Ord e) => Ord (Array i e) where
    compare :: Array i e -> Array i e -> Ordering
compare = Array i e -> Array i e -> Ordering
forall i e. (Ix i, Ord e) => Array i e -> Array i e -> Ordering
cmpArray

-- | @since 2.01
instance (Ix a, Show a, Show b) => Show (Array a b) where
    showsPrec :: Int -> Array a b -> [Char] -> [Char]
showsPrec Int
p Array a b
a =
        Bool -> ([Char] -> [Char]) -> [Char] -> [Char]
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
appPrec) (([Char] -> [Char]) -> [Char] -> [Char])
-> ([Char] -> [Char]) -> [Char] -> [Char]
forall a b. (a -> b) -> a -> b
$
        [Char] -> [Char] -> [Char]
showString [Char]
"array " ([Char] -> [Char]) -> ([Char] -> [Char]) -> [Char] -> [Char]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
        Int -> (a, a) -> [Char] -> [Char]
forall a. Show a => Int -> a -> [Char] -> [Char]
showsPrec Int
appPrec1 (Array a b -> (a, a)
forall i e. Array i e -> (i, i)
bounds Array a b
a) ([Char] -> [Char]) -> ([Char] -> [Char]) -> [Char] -> [Char]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
        Char -> [Char] -> [Char]
showChar Char
' ' ([Char] -> [Char]) -> ([Char] -> [Char]) -> [Char] -> [Char]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
        Int -> [(a, b)] -> [Char] -> [Char]
forall a. Show a => Int -> a -> [Char] -> [Char]
showsPrec Int
appPrec1 (Array a b -> [(a, b)]
forall i e. Ix i => Array i e -> [(i, e)]
assocs Array a b
a)
        -- Precedence of 'array' is the precedence of application

-- The Read instance is in GHC.Read

----------------------------------------------------------------------
-- Operations on mutable arrays

{-
Idle ADR question: What's the tradeoff here between flattening these
datatypes into @STArray ix ix (MutableArray# s elt)@ and using
it as is?  As I see it, the former uses slightly less heap and
provides faster access to the individual parts of the bounds while the
code used has the benefit of providing a ready-made @(lo, hi)@ pair as
required by many array-related functions.  Which wins? Is the
difference significant (probably not).

Idle AJG answer: When I looked at the outputted code (though it was 2
years ago) it seems like you often needed the tuple, and we build
it frequently. Now we've got the overloading specialiser things
might be different, though.
-}

{-# INLINE newSTArray #-}
newSTArray :: Ix i => (i,i) -> e -> ST s (STArray s i e)
newSTArray :: forall i e s. Ix i => (i, i) -> e -> ST s (STArray s i e)
newSTArray (i
l,i
u) e
initial = STRep s (STArray s i e) -> ST s (STArray s i e)
forall s a. STRep s a -> ST s a
ST (STRep s (STArray s i e) -> ST s (STArray s i e))
-> STRep s (STArray s i e) -> ST s (STArray s i e)
forall a b. (a -> b) -> a -> b
$ \State# s
s1# ->
    case (i, i) -> Int
forall i. Ix i => (i, i) -> Int
safeRangeSize (i
l,i
u)            of { n :: Int
n@(I# Int#
n#) ->
    case Int# -> e -> State# s -> (# State# s, MutableArray# s e #)
forall a d.
Int# -> a -> State# d -> (# State# d, MutableArray# d a #)
newArray# Int#
n# e
initial State# s
s1#       of { (# State# s
s2#, MutableArray# s e
marr# #) ->
    (# State# s
s2#, i -> i -> Int -> MutableArray# s e -> STArray s i e
forall s i e. i -> i -> Int -> MutableArray# s e -> STArray s i e
STArray i
l i
u Int
n MutableArray# s e
marr# #) }}

{-# INLINE boundsSTArray #-}
boundsSTArray :: STArray s i e -> (i,i)
boundsSTArray :: forall s i e. STArray s i e -> (i, i)
boundsSTArray (STArray i
l i
u Int
_ MutableArray# s e
_) = (i
l,i
u)

{-# INLINE numElementsSTArray #-}
numElementsSTArray :: STArray s i e -> Int
numElementsSTArray :: forall s i e. STArray s i e -> Int
numElementsSTArray (STArray i
_ i
_ Int
n MutableArray# s e
_) = Int
n

{-# INLINE readSTArray #-}
readSTArray :: Ix i => STArray s i e -> i -> ST s e
readSTArray :: forall i s e. Ix i => STArray s i e -> i -> ST s e
readSTArray marr :: STArray s i e
marr@(STArray i
l i
u Int
n MutableArray# s e
_) i
i =
    STArray s i e -> Int -> ST s e
forall s i e. STArray s i e -> Int -> ST s e
unsafeReadSTArray STArray s i e
marr ((i, i) -> Int -> i -> Int
forall i. Ix i => (i, i) -> Int -> i -> Int
safeIndex (i
l,i
u) Int
n i
i)

{-# INLINE unsafeReadSTArray #-}
unsafeReadSTArray :: STArray s i e -> Int -> ST s e
unsafeReadSTArray :: forall s i e. STArray s i e -> Int -> ST s e
unsafeReadSTArray (STArray i
_ i
_ Int
_ MutableArray# s e
marr#) (I# Int#
i#)
    = STRep s e -> ST s e
forall s a. STRep s a -> ST s a
ST (STRep s e -> ST s e) -> STRep s e -> ST s e
forall a b. (a -> b) -> a -> b
$ \State# s
s1# -> MutableArray# s e -> Int# -> STRep s e
forall d a.
MutableArray# d a -> Int# -> State# d -> (# State# d, a #)
readArray# MutableArray# s e
marr# Int#
i# State# s
s1#

{-# INLINE writeSTArray #-}
writeSTArray :: Ix i => STArray s i e -> i -> e -> ST s ()
writeSTArray :: forall i s e. Ix i => STArray s i e -> i -> e -> ST s ()
writeSTArray marr :: STArray s i e
marr@(STArray i
l i
u Int
n MutableArray# s e
_) i
i e
e =
    STArray s i e -> Int -> e -> ST s ()
forall s i e. STArray s i e -> Int -> e -> ST s ()
unsafeWriteSTArray STArray s i e
marr ((i, i) -> Int -> i -> Int
forall i. Ix i => (i, i) -> Int -> i -> Int
safeIndex (i
l,i
u) Int
n i
i) e
e

{-# INLINE unsafeWriteSTArray #-}
unsafeWriteSTArray :: STArray s i e -> Int -> e -> ST s ()
unsafeWriteSTArray :: forall s i e. STArray s i e -> Int -> e -> ST s ()
unsafeWriteSTArray (STArray i
_ i
_ Int
_ MutableArray# s e
marr#) (I# Int#
i#) e
e = STRep s () -> ST s ()
forall s a. STRep s a -> ST s a
ST (STRep s () -> ST s ()) -> STRep s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ \State# s
s1# ->
    case MutableArray# s e -> Int# -> e -> State# s -> State# s
forall d a. MutableArray# d a -> Int# -> a -> State# d -> State# d
writeArray# MutableArray# s e
marr# Int#
i# e
e State# s
s1# of
        State# s
s2# -> (# State# s
s2#, () #)

----------------------------------------------------------------------
-- Moving between mutable and immutable

freezeSTArray :: STArray s i e -> ST s (Array i e)
freezeSTArray :: forall s i e. STArray s i e -> ST s (Array i e)
freezeSTArray (STArray i
l i
u n :: Int
n@(I# Int#
n#) MutableArray# s e
marr#) = STRep s (Array i e) -> ST s (Array i e)
forall s a. STRep s a -> ST s a
ST (STRep s (Array i e) -> ST s (Array i e))
-> STRep s (Array i e) -> ST s (Array i e)
forall a b. (a -> b) -> a -> b
$ \State# s
s1# ->
    case Int# -> e -> State# s -> (# State# s, MutableArray# s e #)
forall a d.
Int# -> a -> State# d -> (# State# d, MutableArray# d a #)
newArray# Int#
n# e
forall a. a
arrEleBottom State# s
s1#  of { (# State# s
s2#, MutableArray# s e
marr'# #) ->
    let copy :: Int# -> State# s -> State# s
copy Int#
i# State# s
s3# | Int# -> Bool
isTrue# (Int#
i# Int# -> Int# -> Int#
==# Int#
n#) = State# s
s3#
                    | Bool
otherwise =
            case MutableArray# s e -> Int# -> State# s -> (# State# s, e #)
forall d a.
MutableArray# d a -> Int# -> State# d -> (# State# d, a #)
readArray# MutableArray# s e
marr# Int#
i# State# s
s3# of { (# State# s
s4#, e
e #) ->
            case MutableArray# s e -> Int# -> e -> State# s -> State# s
forall d a. MutableArray# d a -> Int# -> a -> State# d -> State# d
writeArray# MutableArray# s e
marr'# Int#
i# e
e State# s
s4# of { State# s
s5# ->
            Int# -> State# s -> State# s
copy (Int#
i# Int# -> Int# -> Int#
+# Int#
1#) State# s
s5# }} in
    case Int# -> State# s -> State# s
copy Int#
0# State# s
s2#                    of { State# s
s3# ->
    case MutableArray# s e -> State# s -> (# State# s, Array# e #)
forall d a.
MutableArray# d a -> State# d -> (# State# d, Array# a #)
unsafeFreezeArray# MutableArray# s e
marr'# State# s
s3#  of { (# State# s
s4#, Array# e
arr# #) ->
    (# State# s
s4#, i -> i -> Int -> Array# e -> Array i e
forall i e. i -> i -> Int -> Array# e -> Array i e
Array i
l i
u Int
n Array# e
arr# #) }}}

{-# INLINE unsafeFreezeSTArray #-}
unsafeFreezeSTArray :: STArray s i e -> ST s (Array i e)
unsafeFreezeSTArray :: forall s i e. STArray s i e -> ST s (Array i e)
unsafeFreezeSTArray (STArray i
l i
u Int
n MutableArray# s e
marr#) = STRep s (Array i e) -> ST s (Array i e)
forall s a. STRep s a -> ST s a
ST (STRep s (Array i e) -> ST s (Array i e))
-> STRep s (Array i e) -> ST s (Array i e)
forall a b. (a -> b) -> a -> b
$ \State# s
s1# ->
    case MutableArray# s e -> State# s -> (# State# s, Array# e #)
forall d a.
MutableArray# d a -> State# d -> (# State# d, Array# a #)
unsafeFreezeArray# MutableArray# s e
marr# State# s
s1#   of { (# State# s
s2#, Array# e
arr# #) ->
    (# State# s
s2#, i -> i -> Int -> Array# e -> Array i e
forall i e. i -> i -> Int -> Array# e -> Array i e
Array i
l i
u Int
n Array# e
arr# #) }

thawSTArray :: Array i e -> ST s (STArray s i e)
thawSTArray :: forall i e s. Array i e -> ST s (STArray s i e)
thawSTArray (Array i
l i
u n :: Int
n@(I# Int#
n#) Array# e
arr#) = STRep s (STArray s i e) -> ST s (STArray s i e)
forall s a. STRep s a -> ST s a
ST (STRep s (STArray s i e) -> ST s (STArray s i e))
-> STRep s (STArray s i e) -> ST s (STArray s i e)
forall a b. (a -> b) -> a -> b
$ \State# s
s1# ->
    case Int# -> e -> State# s -> (# State# s, MutableArray# s e #)
forall a d.
Int# -> a -> State# d -> (# State# d, MutableArray# d a #)
newArray# Int#
n# e
forall a. a
arrEleBottom State# s
s1#  of { (# State# s
s2#, MutableArray# s e
marr# #) ->
    let copy :: Int# -> State# s -> State# s
copy Int#
i# State# s
s3# | Int# -> Bool
isTrue# (Int#
i# Int# -> Int# -> Int#
==# Int#
n#) = State# s
s3#
                    | Bool
otherwise =
            case Array# e -> Int# -> (# e #)
forall a. Array# a -> Int# -> (# a #)
indexArray# Array# e
arr# Int#
i#    of { (# e
e #) ->
            case MutableArray# s e -> Int# -> e -> State# s -> State# s
forall d a. MutableArray# d a -> Int# -> a -> State# d -> State# d
writeArray# MutableArray# s e
marr# Int#
i# e
e State# s
s3# of { State# s
s4# ->
            Int# -> State# s -> State# s
copy (Int#
i# Int# -> Int# -> Int#
+# Int#
1#) State# s
s4# }} in
    case Int# -> State# s -> State# s
copy Int#
0# State# s
s2#                    of { State# s
s3# ->
    (# State# s
s3#, i -> i -> Int -> MutableArray# s e -> STArray s i e
forall s i e. i -> i -> Int -> MutableArray# s e -> STArray s i e
STArray i
l i
u Int
n MutableArray# s e
marr# #) }}

{-# INLINE unsafeThawSTArray #-}
unsafeThawSTArray :: Array i e -> ST s (STArray s i e)
unsafeThawSTArray :: forall i e s. Array i e -> ST s (STArray s i e)
unsafeThawSTArray (Array i
l i
u Int
n Array# e
arr#) = STRep s (STArray s i e) -> ST s (STArray s i e)
forall s a. STRep s a -> ST s a
ST (STRep s (STArray s i e) -> ST s (STArray s i e))
-> STRep s (STArray s i e) -> ST s (STArray s i e)
forall a b. (a -> b) -> a -> b
$ \State# s
s1# ->
    case Array# e -> State# s -> (# State# s, MutableArray# s e #)
forall a d.
Array# a -> State# d -> (# State# d, MutableArray# d a #)
unsafeThawArray# Array# e
arr# State# s
s1#      of { (# State# s
s2#, MutableArray# s e
marr# #) ->
    (# State# s
s2#, i -> i -> Int -> MutableArray# s e -> STArray s i e
forall s i e. i -> i -> Int -> MutableArray# s e -> STArray s i e
STArray i
l i
u Int
n MutableArray# s e
marr# #) }