{-# 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(..),

        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,

        -- * Unsafe operations
        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 ()

-- | 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 the array package).
--
-- 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))@ @ @
--
class (Ord a) => Ix a where
    {-# MINIMAL range, (index | unsafeIndex), inRange #-}

    -- | The list of values in the subrange defined by a bounding pair.
    range               :: (a,a) -> [a]
    -- | 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' is typically over-ridden in instances, with essentially
        -- the same code, but using indexError instead of hopelessIndexError
        -- Reason: we have 'Show' at the instances
    {-# INLINE index #-}  -- See Note [Inlining index]
    index b :: (a, a)
b i :: a
i | (a, a) -> a -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (a, a)
b a
i = (a, a) -> a -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (a, a)
b a
i
              | Bool
otherwise   = Int
hopelessIndexError

    unsafeIndex b :: (a, a)
b i :: a
i = (a, a) -> a -> Int
forall a. Ix a => (a, a) -> a -> Int
index (a, a)
b a
i

    rangeSize b :: (a, a)
b@(_l :: a
_l,h :: a
h) | (a, a) -> a -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (a, a)
b a
h = (a, a) -> a -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (a, a)
b a
h Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1
                       | Bool
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 :: (a, a)
b@(_l :: a
_l,h :: a
h) = (a, a) -> a -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (a, a)
b a
h Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1

{-
Note that the following is NOT right
        rangeSize (l,h) | l <= h    = index b h + 1
                        | otherwise = 0

Because it might be the case that l<h, but the range
is nevertheless empty.  Consider
        ((1,2),(2,1))
Here l<h, but the second index ranges from 2..1 and
hence is empty


Note [Inlining index]
~~~~~~~~~~~~~~~~~~~~~
We inline the 'index' operation,

 * Partly because it generates much faster code
   (although bigger); see Trac #1216

 * Partly because it exposes the bounds checks to the simplifier which
   might help a big.

If you make a per-instance index method, you may consider inlining it.

Note [Double bounds-checking of index values]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
When you index an array, a!x, there are two possible bounds checks we might make:

  (A) Check that (inRange (bounds a) x) holds.

      (A) is checked in the method for 'index'

  (B) Check that (index (bounds a) x) lies in the range 0..n,
      where n is the size of the underlying array

      (B) is checked in the top-level function (!), in safeIndex.

Of course it *should* be the case that (A) holds iff (B) holds, but that
is a property of the particular instances of index, bounds, and inRange,
so GHC cannot guarantee it.

 * If you do (A) and not (B), then you might get a seg-fault,
   by indexing at some bizarre location.  Trac #1610

 * If you do (B) but not (A), you may get no complaint when you index
   an array out of its semantic bounds.  Trac #2120

At various times we have had (A) and not (B), or (B) and not (A); both
led to complaints.  So now we implement *both* checks (Trac #2669).

For 1-d, 2-d, and 3-d arrays of Int we have specialised instances to avoid this.

Note [Out-of-bounds error messages]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The default method for 'index' generates hoplelessIndexError, because
Ix doesn't have Show as a superclass.  For particular base types we
can do better, so we override the default method for index.
-}

-- Abstract these errors from the relevant index functions so that
-- the guts of the function will be small enough to inline.

{-# NOINLINE indexError #-}
indexError :: Show a => (a,a) -> a -> String -> b
indexError :: (a, a) -> a -> String -> b
indexError rng :: (a, a)
rng i :: a
i tp :: String
tp
  = String -> b
forall a. String -> a
errorWithoutStackTrace (String -> ShowS
showString "Ix{" ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
tp ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString "}.index: Index " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
           Bool -> ShowS -> ShowS
showParen Bool
True (Int -> a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec 0 a
i) ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
           String -> ShowS
showString " out of range " ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
           Bool -> ShowS -> ShowS
showParen Bool
True (Int -> (a, a) -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec 0 (a, a)
rng) "")

hopelessIndexError :: Int -- Try to use 'indexError' instead!
hopelessIndexError :: Int
hopelessIndexError = String -> Int
forall a. String -> a
errorWithoutStackTrace "Error in array index"

----------------------------------------------------------------------
-- | @since 2.01
instance  Ix Char  where
    {-# INLINE range #-}
    range :: (Char, Char) -> String
range (m :: Char
m,n :: Char
n) = [Char
m..Char
n]

    {-# INLINE unsafeIndex #-}
    unsafeIndex :: (Char, Char) -> Char -> Int
unsafeIndex (m :: Char
m,_n :: Char
_n) i :: Char
i = Char -> Int
forall a. Enum a => a -> Int
fromEnum Char
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Char -> Int
forall a. Enum a => a -> Int
fromEnum Char
m

    {-# INLINE index #-}  -- See Note [Out-of-bounds error messages]
                          -- and Note [Inlining index]
    index :: (Char, Char) -> Char -> Int
index b :: (Char, Char)
b i :: Char
i | (Char, Char) -> Char -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (Char, Char)
b Char
i =  (Char, Char) -> Char -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (Char, Char)
b Char
i
              | Bool
otherwise   =  (Char, Char) -> Char -> String -> Int
forall a b. Show a => (a, a) -> a -> String -> b
indexError (Char, Char)
b Char
i "Char"

    inRange :: (Char, Char) -> Char -> Bool
inRange (m :: Char
m,n :: Char
n) i :: Char
i     =  Char
m Char -> Char -> Bool
forall a. Ord a => a -> a -> Bool
<= Char
i Bool -> Bool -> Bool
&& Char
i Char -> Char -> Bool
forall a. Ord a => a -> a -> Bool
<= Char
n

----------------------------------------------------------------------
-- | @since 2.01
instance  Ix Int  where
    {-# INLINE range #-}
        -- The INLINE stops the build in the RHS from getting inlined,
        -- so that callers can fuse with the result of range
    range :: (Int, Int) -> [Int]
range (m :: Int
m,n :: Int
n) = [Int
m..Int
n]

    {-# INLINE unsafeIndex #-}
    unsafeIndex :: (Int, Int) -> Int -> Int
unsafeIndex (m :: Int
m,_n :: Int
_n) i :: Int
i = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
m

    {-# INLINE index #-}  -- See Note [Out-of-bounds error messages]
                          -- and Note [Inlining index]
    index :: (Int, Int) -> Int -> Int
index b :: (Int, Int)
b i :: Int
i | (Int, Int) -> Int -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (Int, Int)
b Int
i =  (Int, Int) -> Int -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (Int, Int)
b Int
i
              | Bool
otherwise   =  (Int, Int) -> Int -> String -> Int
forall a b. Show a => (a, a) -> a -> String -> b
indexError (Int, Int)
b Int
i "Int"

    {-# INLINE inRange #-}
    inRange :: (Int, Int) -> Int -> Bool
inRange (I# m :: Int#
m,I# n :: Int#
n) (I# i :: Int#
i) =  Int# -> Bool
isTrue# (Int#
m Int# -> Int# -> Int#
<=# Int#
i) Bool -> Bool -> Bool
&& Int# -> Bool
isTrue# (Int#
i Int# -> Int# -> Int#
<=# Int#
n)

-- | @since 4.6.0.0
instance Ix Word where
    range :: (Word, Word) -> [Word]
range (m :: Word
m,n :: Word
n)         = [Word
m..Word
n]
    unsafeIndex :: (Word, Word) -> Word -> Int
unsafeIndex (m :: Word
m,_) i :: Word
i = Word -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word
i Word -> Word -> Word
forall a. Num a => a -> a -> a
- Word
m)
    inRange :: (Word, Word) -> Word -> Bool
inRange (m :: Word
m,n :: Word
n) i :: Word
i     = Word
m Word -> Word -> Bool
forall a. Ord a => a -> a -> Bool
<= Word
i Bool -> Bool -> Bool
&& Word
i Word -> Word -> Bool
forall a. Ord a => a -> a -> Bool
<= Word
n

----------------------------------------------------------------------
-- | @since 2.01
instance  Ix Integer  where
    {-# INLINE range #-}
    range :: (Integer, Integer) -> [Integer]
range (m :: Integer
m,n :: Integer
n) = [Integer
m..Integer
n]

    {-# INLINE unsafeIndex #-}
    unsafeIndex :: (Integer, Integer) -> Integer -> Int
unsafeIndex (m :: Integer
m,_n :: Integer
_n) i :: Integer
i   = Integer -> Int
forall a. Num a => Integer -> a
fromInteger (Integer
i Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
m)

    {-# INLINE index #-}  -- See Note [Out-of-bounds error messages]
                          -- and Note [Inlining index]
    index :: (Integer, Integer) -> Integer -> Int
index b :: (Integer, Integer)
b i :: Integer
i | (Integer, Integer) -> Integer -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (Integer, Integer)
b Integer
i =  (Integer, Integer) -> Integer -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (Integer, Integer)
b Integer
i
              | Bool
otherwise   =  (Integer, Integer) -> Integer -> String -> Int
forall a b. Show a => (a, a) -> a -> String -> b
indexError (Integer, Integer)
b Integer
i "Integer"

    inRange :: (Integer, Integer) -> Integer -> Bool
inRange (m :: Integer
m,n :: Integer
n) i :: Integer
i     =  Integer
m Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
i Bool -> Bool -> Bool
&& Integer
i Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
n

----------------------------------------------------------------------
-- | @since 4.8.0.0
instance Ix Natural where
    range :: (Natural, Natural) -> [Natural]
range (m :: Natural
m,n :: Natural
n) = [Natural
m..Natural
n]
    inRange :: (Natural, Natural) -> Natural -> Bool
inRange (m :: Natural
m,n :: Natural
n) i :: Natural
i = Natural
m Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
<= Natural
i Bool -> Bool -> Bool
&& Natural
i Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
<= Natural
n
    unsafeIndex :: (Natural, Natural) -> Natural -> Int
unsafeIndex (m :: Natural
m,_) i :: Natural
i = Natural -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Natural
iNatural -> Natural -> Natural
forall a. Num a => a -> a -> a
-Natural
m)
    index :: (Natural, Natural) -> Natural -> Int
index b :: (Natural, Natural)
b i :: Natural
i | (Natural, Natural) -> Natural -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (Natural, Natural)
b Natural
i = (Natural, Natural) -> Natural -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (Natural, Natural)
b Natural
i
              | Bool
otherwise   = (Natural, Natural) -> Natural -> String -> Int
forall a b. Show a => (a, a) -> a -> String -> b
indexError (Natural, Natural)
b Natural
i "Natural"

----------------------------------------------------------------------
-- | @since 2.01
instance Ix Bool where -- as derived
    {-# INLINE range #-}
    range :: (Bool, Bool) -> [Bool]
range (m :: Bool
m,n :: Bool
n) = [Bool
m..Bool
n]

    {-# INLINE unsafeIndex #-}
    unsafeIndex :: (Bool, Bool) -> Bool -> Int
unsafeIndex (l :: Bool
l,_) i :: Bool
i = Bool -> Int
forall a. Enum a => a -> Int
fromEnum Bool
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Bool -> Int
forall a. Enum a => a -> Int
fromEnum Bool
l

    {-# INLINE index #-}  -- See Note [Out-of-bounds error messages]
                          -- and Note [Inlining index]
    index :: (Bool, Bool) -> Bool -> Int
index b :: (Bool, Bool)
b i :: Bool
i | (Bool, Bool) -> Bool -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (Bool, Bool)
b Bool
i =  (Bool, Bool) -> Bool -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (Bool, Bool)
b Bool
i
              | Bool
otherwise   =  (Bool, Bool) -> Bool -> String -> Int
forall a b. Show a => (a, a) -> a -> String -> b
indexError (Bool, Bool)
b Bool
i "Bool"

    inRange :: (Bool, Bool) -> Bool -> Bool
inRange (l :: Bool
l,u :: Bool
u) i :: Bool
i = Bool -> Int
forall a. Enum a => a -> Int
fromEnum Bool
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Bool -> Int
forall a. Enum a => a -> Int
fromEnum Bool
l Bool -> Bool -> Bool
&& Bool -> Int
forall a. Enum a => a -> Int
fromEnum Bool
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Bool -> Int
forall a. Enum a => a -> Int
fromEnum Bool
u

----------------------------------------------------------------------
-- | @since 2.01
instance Ix Ordering where -- as derived
    {-# INLINE range #-}
    range :: (Ordering, Ordering) -> [Ordering]
range (m :: Ordering
m,n :: Ordering
n) = [Ordering
m..Ordering
n]

    {-# INLINE unsafeIndex #-}
    unsafeIndex :: (Ordering, Ordering) -> Ordering -> Int
unsafeIndex (l :: Ordering
l,_) i :: Ordering
i = Ordering -> Int
forall a. Enum a => a -> Int
fromEnum Ordering
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Ordering -> Int
forall a. Enum a => a -> Int
fromEnum Ordering
l

    {-# INLINE index #-}  -- See Note [Out-of-bounds error messages]
                          -- and Note [Inlining index]
    index :: (Ordering, Ordering) -> Ordering -> Int
index b :: (Ordering, Ordering)
b i :: Ordering
i | (Ordering, Ordering) -> Ordering -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (Ordering, Ordering)
b Ordering
i =  (Ordering, Ordering) -> Ordering -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (Ordering, Ordering)
b Ordering
i
              | Bool
otherwise   =  (Ordering, Ordering) -> Ordering -> String -> Int
forall a b. Show a => (a, a) -> a -> String -> b
indexError (Ordering, Ordering)
b Ordering
i "Ordering"

    inRange :: (Ordering, Ordering) -> Ordering -> Bool
inRange (l :: Ordering
l,u :: Ordering
u) i :: Ordering
i = Ordering -> Int
forall a. Enum a => a -> Int
fromEnum Ordering
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Ordering -> Int
forall a. Enum a => a -> Int
fromEnum Ordering
l Bool -> Bool -> Bool
&& Ordering -> Int
forall a. Enum a => a -> Int
fromEnum Ordering
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Ordering -> Int
forall a. Enum a => a -> Int
fromEnum Ordering
u

----------------------------------------------------------------------
-- | @since 2.01
instance Ix () where
    {-# INLINE range #-}
    range :: ((), ()) -> [()]
range   ((), ())    = [()]
    {-# INLINE unsafeIndex #-}
    unsafeIndex :: ((), ()) -> () -> Int
unsafeIndex   ((), ()) () = 0
    {-# INLINE inRange #-}
    inRange :: ((), ()) -> () -> Bool
inRange ((), ()) () = Bool
True

    {-# INLINE index #-}  -- See Note [Inlining index]
    index :: ((), ()) -> () -> Int
index b :: ((), ())
b i :: ()
i = ((), ()) -> () -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex ((), ())
b ()
i

----------------------------------------------------------------------
-- | @since 2.01
instance (Ix a, Ix b) => Ix (a, b) where -- as derived
    {-# SPECIALISE instance Ix (Int,Int) #-}

    {-# INLINE range #-}
    range :: ((a, b), (a, b)) -> [(a, b)]
range ((l1 :: a
l1,l2 :: b
l2),(u1 :: a
u1,u2 :: b
u2)) =
      [ (a
i1,b
i2) | a
i1 <- (a, a) -> [a]
forall a. Ix a => (a, a) -> [a]
range (a
l1,a
u1), b
i2 <- (b, b) -> [b]
forall a. Ix a => (a, a) -> [a]
range (b
l2,b
u2) ]

    {-# INLINE unsafeIndex #-}
    unsafeIndex :: ((a, b), (a, b)) -> (a, b) -> Int
unsafeIndex ((l1 :: a
l1,l2 :: b
l2),(u1 :: a
u1,u2 :: b
u2)) (i1 :: a
i1,i2 :: b
i2) =
      (a, a) -> a -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (a
l1,a
u1) a
i1 Int -> Int -> Int
forall a. Num a => a -> a -> a
* (b, b) -> Int
forall a. Ix a => (a, a) -> Int
unsafeRangeSize (b
l2,b
u2) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (b, b) -> b -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (b
l2,b
u2) b
i2

    {-# INLINE inRange #-}
    inRange :: ((a, b), (a, b)) -> (a, b) -> Bool
inRange ((l1 :: a
l1,l2 :: b
l2),(u1 :: a
u1,u2 :: b
u2)) (i1 :: a
i1,i2 :: b
i2) =
      (a, a) -> a -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (a
l1,a
u1) a
i1 Bool -> Bool -> Bool
&& (b, b) -> b -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (b
l2,b
u2) b
i2

    -- Default method for index

----------------------------------------------------------------------
-- | @since 2.01
instance  (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3)  where
    {-# SPECIALISE instance Ix (Int,Int,Int) #-}

    range :: ((a1, a2, a3), (a1, a2, a3)) -> [(a1, a2, a3)]
range ((l1 :: a1
l1,l2 :: a2
l2,l3 :: a3
l3),(u1 :: a1
u1,u2 :: a2
u2,u3 :: a3
u3)) =
        [(a1
i1,a2
i2,a3
i3) | a1
i1 <- (a1, a1) -> [a1]
forall a. Ix a => (a, a) -> [a]
range (a1
l1,a1
u1),
                      a2
i2 <- (a2, a2) -> [a2]
forall a. Ix a => (a, a) -> [a]
range (a2
l2,a2
u2),
                      a3
i3 <- (a3, a3) -> [a3]
forall a. Ix a => (a, a) -> [a]
range (a3
l3,a3
u3)]

    unsafeIndex :: ((a1, a2, a3), (a1, a2, a3)) -> (a1, a2, a3) -> Int
unsafeIndex ((l1 :: a1
l1,l2 :: a2
l2,l3 :: a3
l3),(u1 :: a1
u1,u2 :: a2
u2,u3 :: a3
u3)) (i1 :: a1
i1,i2 :: a2
i2,i3 :: a3
i3) =
      (a3, a3) -> a3 -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (a3
l3,a3
u3) a3
i3 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (a3, a3) -> Int
forall a. Ix a => (a, a) -> Int
unsafeRangeSize (a3
l3,a3
u3) Int -> Int -> Int
forall a. Num a => a -> a -> a
* (
      (a2, a2) -> a2 -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (a2
l2,a2
u2) a2
i2 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (a2, a2) -> Int
forall a. Ix a => (a, a) -> Int
unsafeRangeSize (a2
l2,a2
u2) Int -> Int -> Int
forall a. Num a => a -> a -> a
* (
      (a1, a1) -> a1 -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (a1
l1,a1
u1) a1
i1))

    inRange :: ((a1, a2, a3), (a1, a2, a3)) -> (a1, a2, a3) -> Bool
inRange ((l1 :: a1
l1,l2 :: a2
l2,l3 :: a3
l3),(u1 :: a1
u1,u2 :: a2
u2,u3 :: a3
u3)) (i1 :: a1
i1,i2 :: a2
i2,i3 :: a3
i3) =
      (a1, a1) -> a1 -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (a1
l1,a1
u1) a1
i1 Bool -> Bool -> Bool
&& (a2, a2) -> a2 -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (a2
l2,a2
u2) a2
i2 Bool -> Bool -> Bool
&&
      (a3, a3) -> a3 -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (a3
l3,a3
u3) a3
i3

    -- Default method for index

----------------------------------------------------------------------
-- | @since 2.01
instance  (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4)  where
    range :: ((a1, a2, a3, a4), (a1, a2, a3, a4)) -> [(a1, a2, a3, a4)]
range ((l1 :: a1
l1,l2 :: a2
l2,l3 :: a3
l3,l4 :: a4
l4),(u1 :: a1
u1,u2 :: a2
u2,u3 :: a3
u3,u4 :: a4
u4)) =
      [(a1
i1,a2
i2,a3
i3,a4
i4) | a1
i1 <- (a1, a1) -> [a1]
forall a. Ix a => (a, a) -> [a]
range (a1
l1,a1
u1),
                       a2
i2 <- (a2, a2) -> [a2]
forall a. Ix a => (a, a) -> [a]
range (a2
l2,a2
u2),
                       a3
i3 <- (a3, a3) -> [a3]
forall a. Ix a => (a, a) -> [a]
range (a3
l3,a3
u3),
                       a4
i4 <- (a4, a4) -> [a4]
forall a. Ix a => (a, a) -> [a]
range (a4
l4,a4
u4)]

    unsafeIndex :: ((a1, a2, a3, a4), (a1, a2, a3, a4)) -> (a1, a2, a3, a4) -> Int
unsafeIndex ((l1 :: a1
l1,l2 :: a2
l2,l3 :: a3
l3,l4 :: a4
l4),(u1 :: a1
u1,u2 :: a2
u2,u3 :: a3
u3,u4 :: a4
u4)) (i1 :: a1
i1,i2 :: a2
i2,i3 :: a3
i3,i4 :: a4
i4) =
      (a4, a4) -> a4 -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (a4
l4,a4
u4) a4
i4 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (a4, a4) -> Int
forall a. Ix a => (a, a) -> Int
unsafeRangeSize (a4
l4,a4
u4) Int -> Int -> Int
forall a. Num a => a -> a -> a
* (
      (a3, a3) -> a3 -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (a3
l3,a3
u3) a3
i3 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (a3, a3) -> Int
forall a. Ix a => (a, a) -> Int
unsafeRangeSize (a3
l3,a3
u3) Int -> Int -> Int
forall a. Num a => a -> a -> a
* (
      (a2, a2) -> a2 -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (a2
l2,a2
u2) a2
i2 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (a2, a2) -> Int
forall a. Ix a => (a, a) -> Int
unsafeRangeSize (a2
l2,a2
u2) Int -> Int -> Int
forall a. Num a => a -> a -> a
* (
      (a1, a1) -> a1 -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (a1
l1,a1
u1) a1
i1)))

    inRange :: ((a1, a2, a3, a4), (a1, a2, a3, a4)) -> (a1, a2, a3, a4) -> Bool
inRange ((l1 :: a1
l1,l2 :: a2
l2,l3 :: a3
l3,l4 :: a4
l4),(u1 :: a1
u1,u2 :: a2
u2,u3 :: a3
u3,u4 :: a4
u4)) (i1 :: a1
i1,i2 :: a2
i2,i3 :: a3
i3,i4 :: a4
i4) =
      (a1, a1) -> a1 -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (a1
l1,a1
u1) a1
i1 Bool -> Bool -> Bool
&& (a2, a2) -> a2 -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (a2
l2,a2
u2) a2
i2 Bool -> Bool -> Bool
&&
      (a3, a3) -> a3 -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (a3
l3,a3
u3) a3
i3 Bool -> Bool -> Bool
&& (a4, a4) -> a4 -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (a4
l4,a4
u4) a4
i4

    -- Default method for index
-- | @since 2.01
instance  (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5)  where
    range :: ((a1, a2, a3, a4, a5), (a1, a2, a3, a4, a5))
-> [(a1, a2, a3, a4, a5)]
range ((l1 :: a1
l1,l2 :: a2
l2,l3 :: a3
l3,l4 :: a4
l4,l5 :: a5
l5),(u1 :: a1
u1,u2 :: a2
u2,u3 :: a3
u3,u4 :: a4
u4,u5 :: a5
u5)) =
      [(a1
i1,a2
i2,a3
i3,a4
i4,a5
i5) | a1
i1 <- (a1, a1) -> [a1]
forall a. Ix a => (a, a) -> [a]
range (a1
l1,a1
u1),
                          a2
i2 <- (a2, a2) -> [a2]
forall a. Ix a => (a, a) -> [a]
range (a2
l2,a2
u2),
                          a3
i3 <- (a3, a3) -> [a3]
forall a. Ix a => (a, a) -> [a]
range (a3
l3,a3
u3),
                          a4
i4 <- (a4, a4) -> [a4]
forall a. Ix a => (a, a) -> [a]
range (a4
l4,a4
u4),
                          a5
i5 <- (a5, a5) -> [a5]
forall a. Ix a => (a, a) -> [a]
range (a5
l5,a5
u5)]

    unsafeIndex :: ((a1, a2, a3, a4, a5), (a1, a2, a3, a4, a5))
-> (a1, a2, a3, a4, a5) -> Int
unsafeIndex ((l1 :: a1
l1,l2 :: a2
l2,l3 :: a3
l3,l4 :: a4
l4,l5 :: a5
l5),(u1 :: a1
u1,u2 :: a2
u2,u3 :: a3
u3,u4 :: a4
u4,u5 :: a5
u5)) (i1 :: a1
i1,i2 :: a2
i2,i3 :: a3
i3,i4 :: a4
i4,i5 :: a5
i5) =
      (a5, a5) -> a5 -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (a5
l5,a5
u5) a5
i5 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (a5, a5) -> Int
forall a. Ix a => (a, a) -> Int
unsafeRangeSize (a5
l5,a5
u5) Int -> Int -> Int
forall a. Num a => a -> a -> a
* (
      (a4, a4) -> a4 -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (a4
l4,a4
u4) a4
i4 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (a4, a4) -> Int
forall a. Ix a => (a, a) -> Int
unsafeRangeSize (a4
l4,a4
u4) Int -> Int -> Int
forall a. Num a => a -> a -> a
* (
      (a3, a3) -> a3 -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (a3
l3,a3
u3) a3
i3 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (a3, a3) -> Int
forall a. Ix a => (a, a) -> Int
unsafeRangeSize (a3
l3,a3
u3) Int -> Int -> Int
forall a. Num a => a -> a -> a
* (
      (a2, a2) -> a2 -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (a2
l2,a2
u2) a2
i2 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (a2, a2) -> Int
forall a. Ix a => (a, a) -> Int
unsafeRangeSize (a2
l2,a2
u2) Int -> Int -> Int
forall a. Num a => a -> a -> a
* (
      (a1, a1) -> a1 -> Int
forall a. Ix a => (a, a) -> a -> Int
unsafeIndex (a1
l1,a1
u1) a1
i1))))

    inRange :: ((a1, a2, a3, a4, a5), (a1, a2, a3, a4, a5))
-> (a1, a2, a3, a4, a5) -> Bool
inRange ((l1 :: a1
l1,l2 :: a2
l2,l3 :: a3
l3,l4 :: a4
l4,l5 :: a5
l5),(u1 :: a1
u1,u2 :: a2
u2,u3 :: a3
u3,u4 :: a4
u4,u5 :: a5
u5)) (i1 :: a1
i1,i2 :: a2
i2,i3 :: a3
i3,i4 :: a4
i4,i5 :: a5
i5) =
      (a1, a1) -> a1 -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (a1
l1,a1
u1) a1
i1 Bool -> Bool -> Bool
&& (a2, a2) -> a2 -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (a2
l2,a2
u2) a2
i2 Bool -> Bool -> Bool
&&
      (a3, a3) -> a3 -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (a3
l3,a3
u3) a3
i3 Bool -> Bool -> Bool
&& (a4, a4) -> a4 -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (a4
l4,a4
u4) a4
i4 Bool -> Bool -> Bool
&&
      (a5, a5) -> a5 -> Bool
forall a. Ix a => (a, a) -> a -> Bool
inRange (a5
l5,a5
u5) a5
i5

    -- Default method for index

-- | 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 _ _ _ arr1# :: MutableArray# s e
arr1# == :: STArray s i e -> STArray s i e -> Bool
== STArray _ _ _ arr2# :: MutableArray# s e
arr2# =
        Int# -> Bool
isTrue# (MutableArray# s e -> MutableArray# s e -> Int#
forall d a. MutableArray# d a -> MutableArray# d a -> Int#
sameMutableArray# MutableArray# s e
arr1# MutableArray# s e
arr2#)

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

{-# NOINLINE arrEleBottom #-}
arrEleBottom :: a
arrEleBottom :: a
arrEleBottom = String -> a
forall a. String -> a
errorWithoutStackTrace "(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 :: (i, i) -> [(i, e)] -> Array i e
array (l :: i
l,u :: i
u) ies :: [(i, e)]
ies
    = let n :: Int
n = (i, i) -> Int
forall a. Ix a => (a, a) -> 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
i, e :: e
e) <- [(i, e)]
ies]

{-# INLINE unsafeArray #-}
unsafeArray :: Ix i => (i,i) -> [(Int, e)] -> Array i e
unsafeArray :: (i, i) -> [(Int, e)] -> Array i e
unsafeArray b :: (i, i)
b ies :: [(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 a. Ix a => (a, a) -> Int
rangeSize (i, i)
b) [(Int, e)]
ies

{-# INLINE unsafeArray' #-}
unsafeArray' :: (i,i) -> Int -> [(Int, e)] -> Array i e
unsafeArray' :: (i, i) -> Int -> [(Int, e)] -> Array i e
unsafeArray' (l :: i
l,u :: i
u) n :: Int
n@(I# n# :: Int#
n#) ies :: [(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
$ \s1# :: 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
        (# s2# :: State# s
s2#, marr# :: 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 :: MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
fill marr# :: MutableArray# s e
marr# (I# i# :: Int#
i#, e :: e
e) next :: STRep s a
next
 = \s1# :: 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
             s2# :: 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 :: i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
done l :: i
l u :: i
u n :: Int
n@(I# _) marr# :: MutableArray# s e
marr#
  = \s1# :: 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
              (# s2# :: State# s
s2#, arr# :: 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 :: (i, i) -> [e] -> Array i e
listArray (l :: i
l,u :: i
u) es :: [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
$ \s1# :: State# s
s1# ->
    case (i, i) -> Int
forall a. Ix a => (a, a) -> Int
safeRangeSize (i
l,i
u)            of { n :: Int
n@(I# n# :: 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 { (# s2# :: State# s
s2#, marr# :: MutableArray# s e
marr# #) ->
      let
        go :: e -> (Int# -> State# s -> State# s) -> Int# -> State# s -> State# s
go y :: e
y r :: Int# -> State# s -> State# s
r = \ i# :: Int#
i# s3# :: 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
              s4# :: State# s
s4# -> if (Int# -> Bool
isTrue# (Int#
i# Int# -> Int# -> Int#
==# Int#
n# Int# -> Int# -> Int#
-# 1#))
                     then State# s
s4#
                     else Int# -> State# s -> State# s
r (Int#
i# 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
== 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 (\_ s# :: State# s
s# -> State# s
s#) [e]
es 0# State# s
s2#)}})

-- | The value at the given index in an array.
{-# INLINE (!) #-}
(!) :: Ix i => Array i e -> i -> e
(!) arr :: Array i e
arr@(Array l :: i
l u :: i
u n :: Int
n _) i :: 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 #)
!# :: Array i e -> i -> (# e #)
(!#) arr :: Array i e
arr@(Array l :: i
l u :: i
u n :: Int
n _) i :: 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 :: (i, i) -> Int
safeRangeSize (l :: i
l,u :: i
u) = let r :: Int
r = (i, i) -> Int
forall a. Ix a => (a, a) -> Int
rangeSize (i
l, i
u)
                      in if Int
r Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< 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 = String -> Int
forall a. String -> a
errorWithoutStackTrace "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 :: (i, i) -> Int -> i -> Int
safeIndex (l :: i
l,u :: i
u) n :: Int
n@(I# _) i :: i
i
  | (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 :: (i, i) -> Int -> i -> Int
lessSafeIndex (l :: i
l,u :: i
u) _ i :: 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 i' :: Int
i' n :: Int
n = String -> Int
forall a. String -> a
errorWithoutStackTrace ("Error in array index; " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
i' String -> ShowS
forall a. [a] -> [a] -> [a]
++
                        " not in range [0.." String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
n String -> ShowS
forall a. [a] -> [a] -> [a]
++ ")")

{-# INLINE unsafeAt #-}
unsafeAt :: Array i e -> Int -> e
unsafeAt :: Array i e -> Int -> e
unsafeAt (Array _ _ _ arr# :: Array# e
arr#) (I# 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
e

-- | Look up an element in an array without forcing it
unsafeAt# :: Array i e -> Int -> (# e #)
unsafeAt# :: Array i e -> Int -> (# e #)
unsafeAt# (Array _ _ _ arr# :: Array# e
arr#) (I# 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 :: Array i e -> Int -> f e
unsafeAtA ary :: Array i e
ary i :: 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 #) -> 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 :: Array i e -> (i, i)
bounds (Array l :: i
l u :: i
u _ _) = (i
l,i
u)

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

-- | The list of indices of an array in ascending order.
{-# INLINE indices #-}
indices :: Ix i => Array i e -> [i]
indices :: Array i e -> [i]
indices (Array l :: i
l u :: i
u _ _) = (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 :: Array i e -> [e]
elems arr :: Array i e
arr@(Array _ _ n :: Int
n _) =
    [e
e | Int
i <- [0 .. Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- 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 :: (a -> b -> b) -> b -> Array i a -> b
foldrElems f :: a -> b -> b
f b0 :: b
b0 = \ arr :: Array i a
arr@(Array _ _ n :: Int
n _) ->
  let
    go :: Int -> b
go i :: Int
i | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
n    = b
b0
         | (# e :: 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
+1))
  in Int -> b
go 0

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

-- | A strict right fold over the elements
{-# INLINABLE foldrElems' #-}
foldrElems' :: (a -> b -> b) -> b -> Array i a -> b
foldrElems' :: (a -> b -> b) -> b -> Array i a -> b
foldrElems' f :: a -> b -> b
f b0 :: b
b0 = \ arr :: Array i a
arr@(Array _ _ n :: Int
n _) ->
  let
    go :: Int -> b -> b
go i :: Int
i a :: b
a | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== (-1) = b
a
           | (# e :: 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
-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
-1) b
b0

-- | A strict left fold over the elements
{-# INLINABLE foldlElems' #-}
foldlElems' :: (b -> a -> b) -> b -> Array i a -> b
foldlElems' :: (b -> a -> b) -> b -> Array i a -> b
foldlElems' f :: b -> a -> b
f b0 :: b
b0 = \ arr :: Array i a
arr@(Array _ _ n :: Int
n _) ->
  let
    go :: Int -> b -> b
go i :: Int
i a :: b
a | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
n    = b
a
           | (# e :: 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
+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 0 b
b0

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

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

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

{-# INLINE unsafeAccumArray #-}
unsafeAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(Int, a)] -> Array i e
unsafeAccumArray :: (e -> a -> e) -> e -> (i, i) -> [(Int, a)] -> Array i e
unsafeAccumArray f :: e -> a -> e
f initial :: e
initial b :: (i, i)
b ies :: [(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 a. Ix a => (a, a) -> Int
rangeSize (i, i)
b) [(Int, a)]
ies

{-# INLINE unsafeAccumArray' #-}
unsafeAccumArray' :: (e -> a -> e) -> e -> (i,i) -> Int -> [(Int, a)] -> Array i e
unsafeAccumArray' :: (e -> a -> e) -> e -> (i, i) -> Int -> [(Int, a)] -> Array i e
unsafeAccumArray' f :: e -> a -> e
f initial :: e
initial (l :: i
l,u :: i
u) n :: Int
n@(I# n# :: Int#
n#) ies :: [(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
$ \s1# :: 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 { (# s2# :: State# s
s2#, marr# :: 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 :: (e -> a -> e)
-> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b
adjust f :: e -> a -> e
f marr# :: MutableArray# s e
marr# (I# i# :: Int#
i#, new :: a
new) next :: STRep s b
next
  = \s1# :: 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
                (# s2# :: State# s
s2#, old :: 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
                        s3# :: 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' :: (e -> a -> e)
-> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b
adjust' f :: e -> a -> e
f marr# :: MutableArray# s e
marr# (I# i# :: Int#
i#, new :: a
new) next :: STRep s b
next
  = \s1# :: 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
                (# s2# :: State# s
s2#, old :: 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 l :: i
l u :: i
u n :: Int
n _) // :: Array i e -> [(i, e)] -> Array i e
// ies :: [(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
i, e :: e
e) <- [(i, e)]
ies]

{-# INLINE unsafeReplace #-}
unsafeReplace :: Array i e -> [(Int, e)] -> Array i e
unsafeReplace :: Array i e -> [(Int, e)] -> Array i e
unsafeReplace arr :: Array i e
arr ies :: [(Int, e)]
ies = (forall s. ST s (Array i e)) -> Array i e
forall a. (forall s. ST s a) -> a
runST (do
    STArray l :: i
l u :: i
u n :: Int
n marr# :: 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 :: (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
accum f :: e -> a -> e
f arr :: Array i e
arr@(Array l :: i
l u :: i
u n :: Int
n _) ies :: [(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
i, e :: a
e) <- [(i, a)]
ies]

{-# INLINE unsafeAccum #-}
unsafeAccum :: (e -> a -> e) -> Array i e -> [(Int, a)] -> Array i e
unsafeAccum :: (e -> a -> e) -> Array i e -> [(Int, a)] -> Array i e
unsafeAccum f :: e -> a -> e
f arr :: Array i e
arr ies :: [(Int, a)]
ies = (forall s. ST s (Array i e)) -> Array i e
forall a. (forall s. ST s a) -> a
runST (do
    STArray l :: i
l u :: i
u n :: Int
n marr# :: 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 :: (a -> b) -> Array i a -> Array i b
amap f :: a -> b
f arr :: Array i a
arr@(Array l :: i
l u :: i
u n :: Int
n@(I# n# :: Int#
n#) _) = (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
$ \s1# :: 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
        (# s2# :: State# s
s2#, marr# :: MutableArray# s b
marr# #) ->
          let go :: Int -> STRep s (Array i b)
go i :: Int
i s# :: 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#
                | (# e :: 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
+1)) State# s
s#
          in Int -> STRep s (Array i b)
go 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. Trac #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 :: (i, i) -> (i -> j) -> Array j e -> Array i e
ixmap (l :: i
l,u :: i
u) f :: i -> j
f arr :: 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 :: Array i e -> Array i e -> Bool
eqArray arr1 :: Array i e
arr1@(Array l1 :: i
l1 u1 :: i
u1 n1 :: Int
n1 _) arr2 :: Array i e
arr2@(Array l2 :: i
l2 u2 :: i
u2 n2 :: Int
n2 _) =
    if Int
n1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 0 then Int
n2 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 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 <- [0 .. Int
n1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- 1]]

{-# INLINE [1] cmpArray #-}
cmpArray :: (Ix i, Ord e) => Array i e -> Array i e -> Ordering
cmpArray :: Array i e -> Array i e -> Ordering
cmpArray arr1 :: Array i e
arr1 arr2 :: 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 :: Array Int e -> Array Int e -> Ordering
cmpIntArray arr1 :: Array Int e
arr1@(Array l1 :: Int
l1 u1 :: Int
u1 n1 :: Int
n1 _) arr2 :: Array Int e
arr2@(Array l2 :: Int
l2 u2 :: Int
u2 n2 :: Int
n2 _) =
    if Int
n1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 0 then
        if Int
n2 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 0 then Ordering
EQ else Ordering
LT
    else if Int
n2 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 0 then Ordering
GT
    else case Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Int
l1 Int
l2 of
             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) [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
- 1]
             other :: Ordering
other -> Ordering
other
  where
    cmp :: Int -> Ordering -> Ordering
cmp i :: Int
i rest :: 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
        EQ    -> Ordering
rest
        other :: Ordering
other -> Ordering
other

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

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

-- | @since 2.01
instance Functor (Array i) where
    fmap :: (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

-- | @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 -> ShowS
showsPrec p :: Int
p a :: Array a b
a =
        Bool -> ShowS -> ShowS
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
appPrec) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
        String -> ShowS
showString "array " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
        Int -> (a, a) -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
appPrec1 (Array a b -> (a, a)
forall i e. Array i e -> (i, i)
bounds Array a b
a) ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
        Char -> ShowS
showChar ' ' ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
        Int -> [(a, b)] -> ShowS
forall a. Show a => Int -> a -> ShowS
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 :: (i, i) -> e -> ST s (STArray s i e)
newSTArray (l :: i
l,u :: i
u) initial :: 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
$ \s1# :: State# s
s1# ->
    case (i, i) -> Int
forall a. Ix a => (a, a) -> Int
safeRangeSize (i
l,i
u)            of { n :: Int
n@(I# n# :: 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 { (# s2# :: State# s
s2#, marr# :: 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 :: STArray s i e -> (i, i)
boundsSTArray (STArray l :: i
l u :: i
u _ _) = (i
l,i
u)

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

{-# INLINE readSTArray #-}
readSTArray :: Ix i => STArray s i e -> i -> ST s e
readSTArray :: STArray s i e -> i -> ST s e
readSTArray marr :: STArray s i e
marr@(STArray l :: i
l u :: i
u n :: Int
n _) i :: 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 :: STArray s i e -> Int -> ST s e
unsafeReadSTArray (STArray _ _ _ marr# :: MutableArray# s e
marr#) (I# 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
$ \s1# :: 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 :: STArray s i e -> i -> e -> ST s ()
writeSTArray marr :: STArray s i e
marr@(STArray l :: i
l u :: i
u n :: Int
n _) i :: i
i e :: 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 :: STArray s i e -> Int -> e -> ST s ()
unsafeWriteSTArray (STArray _ _ _ marr# :: MutableArray# s e
marr#) (I# i# :: Int#
i#) e :: 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
$ \s1# :: 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
        s2# :: State# s
s2# -> (# State# s
s2#, () #)

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

freezeSTArray :: STArray s i e -> ST s (Array i e)
freezeSTArray :: STArray s i e -> ST s (Array i e)
freezeSTArray (STArray l :: i
l u :: i
u n :: Int
n@(I# n# :: Int#
n#) marr# :: 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
$ \s1# :: 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 { (# s2# :: State# s
s2#, marr'# :: MutableArray# s e
marr'# #) ->
    let copy :: Int# -> State# s -> State# s
copy i# :: Int#
i# s3# :: 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 { (# s4# :: State# s
s4#, e :: 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 { s5# :: State# s
s5# ->
            Int# -> State# s -> State# s
copy (Int#
i# Int# -> Int# -> Int#
+# 1#) State# s
s5# }} in
    case Int# -> State# s -> State# s
copy 0# State# s
s2#                    of { s3# :: 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 { (# s4# :: State# s
s4#, arr# :: 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 :: STArray s i e -> ST s (Array i e)
unsafeFreezeSTArray (STArray l :: i
l u :: i
u n :: Int
n marr# :: 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
$ \s1# :: 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 { (# s2# :: State# s
s2#, arr# :: 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 :: Array i e -> ST s (STArray s i e)
thawSTArray (Array l :: i
l u :: i
u n :: Int
n@(I# n# :: Int#
n#) arr# :: 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
$ \s1# :: 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 { (# s2# :: State# s
s2#, marr# :: MutableArray# s e
marr# #) ->
    let copy :: Int# -> State# s -> State# s
copy i# :: Int#
i# s3# :: 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
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 { s4# :: State# s
s4# ->
            Int# -> State# s -> State# s
copy (Int#
i# Int# -> Int# -> Int#
+# 1#) State# s
s4# }} in
    case Int# -> State# s -> State# s
copy 0# State# s
s2#                    of { s3# :: 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 :: Array i e -> ST s (STArray s i e)
unsafeThawSTArray (Array l :: i
l u :: i
u n :: Int
n arr# :: 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
$ \s1# :: 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 { (# s2# :: State# s
s2#, marr# :: 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# #) }