    {-# LANGUAGE BangPatterns, MagicHash, Rank2Types, UnboxedTuples #-}

    -- | Zero based arrays.
    --
    -- Note that no bounds checking are performed.
    module Data.Array
        ( Array
        , length
        , index
        , fromList
        , toList
        ) where

    import Control.Monad.ST
    import GHC.Exts (Array#, Int(..), MutableArray#, indexArray#, newArray#,
                     sizeofArray#, sizeofMutableArray#, unsafeFreezeArray#,
                     writeArray#)
    import GHC.ST (ST(..))
    import Prelude hiding (foldr, length)

    data Array a = Array { Array a -> Array# a
    unArray :: !(Array# a) }

    length :: Array a -> Int
    length :: Array a -> Int
    length ary :: Array a
    ary = Int# -> Int
    I# (Array# a -> Int#
    forall a. Array# a -> Int#
    sizeofArray# (Array a -> Array# a
    forall a. Array a -> Array# a
    unArray Array a
    ary))
    {-# INLINE length #-}

    -- | Smart constructor
    array :: Array# a -> Int -> Array a
    array :: Array# a -> Int -> Array a
    array ary :: Array# a
    ary _n :: Int
    _n = Array# a -> Array a
    forall a. Array# a -> Array a
    Array Array# a
    ary
    {-# INLINE array #-}

    data MArray s a = MArray {
          MArray s a -> MutableArray# s a
    unMArray :: !(MutableArray# s a)
        }

    lengthM :: MArray s a -> Int
    lengthM :: MArray s a -> Int
    lengthM mary :: MArray s a
    mary = Int# -> Int
    I# (MutableArray# s a -> Int#
    forall d a. MutableArray# d a -> Int#
    sizeofMutableArray# (MArray s a -> MutableArray# s a
    forall s a. MArray s a -> MutableArray# s a
    unMArray MArray s a
    mary))
    {-# INLINE lengthM #-}

    -- | Smart constructor
    marray :: MutableArray# s a -> Int -> MArray s a
    marray :: MutableArray# s a -> Int -> MArray s a
    marray mary :: MutableArray# s a
    mary _n :: Int
    _n = MutableArray# s a -> MArray s a
    forall s a. MutableArray# s a -> MArray s a
    MArray MutableArray# s a
    mary
    {-# INLINE marray #-}

    new :: Int -> a -> ST s (MArray s a)
    new :: Int -> a -> ST s (MArray s a)
    new n :: Int
    n@(I# n# :: Int#
    n#) b :: a
    b =
        STRep s (MArray s a) -> ST s (MArray s a)
    forall s a. STRep s a -> ST s a
    ST (STRep s (MArray s a) -> ST s (MArray s a))
    -> STRep s (MArray s a) -> ST s (MArray s a)
    forall a b. (a -> b) -> a -> b
    $ \s :: State# s
    s ->
            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
    b State# s
    s of
                (# s' :: State# s
    s', ary :: MutableArray# s a
    ary #) -> (# State# s
    s', MutableArray# s a -> Int -> MArray s a
    forall s a. MutableArray# s a -> Int -> MArray s a
    marray MutableArray# s a
    ary Int
    n #)
    {-# INLINE new #-}

    new_ :: Int -> ST s (MArray s a)
    new_ :: Int -> ST s (MArray s a)
    new_ n :: Int
    n = Int -> a -> ST s (MArray s a)
    forall a s. Int -> a -> ST s (MArray s a)
    new Int
    n a
    forall a. a
    undefinedElem

    write :: MArray s a -> Int -> a -> ST s ()
    write :: MArray s a -> Int -> a -> ST s ()
    write ary :: MArray s a
    ary _i :: Int
    _i@(I# i# :: Int#
    i#) b :: a
    b = 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
    $ \ s :: State# s
    s ->
        case MutableArray# s a -> Int# -> a -> State# s -> State# s
    forall d a. MutableArray# d a -> Int# -> a -> State# d -> State# d
    writeArray# (MArray s a -> MutableArray# s a
    forall s a. MArray s a -> MutableArray# s a
    unMArray MArray s a
    ary) Int#
    i# a
    b State# s
    s of
            s' :: State# s
    s' -> (# State# s
    s' , () #)
    {-# INLINE write #-}

    index :: Array a -> Int -> a
    index :: Array a -> Int -> a
    index ary :: Array a
    ary _i :: Int
    _i@(I# i# :: Int#
    i#) =
        case Array# a -> Int# -> (# a #)
    forall a. Array# a -> Int# -> (# a #)
    indexArray# (Array a -> Array# a
    forall a. Array a -> Array# a
    unArray Array a
    ary) Int#
    i# of (# b :: a
    b #) -> a
    b
    {-# INLINE index #-}

    unsafeFreeze :: MArray s a -> ST s (Array a)
    unsafeFreeze :: MArray s a -> ST s (Array a)
    unsafeFreeze mary :: MArray s a
    mary
        = STRep s (Array a) -> ST s (Array a)
    forall s a. STRep s a -> ST s a
    ST (STRep s (Array a) -> ST s (Array a))
    -> STRep s (Array a) -> ST s (Array a)
    forall a b. (a -> b) -> a -> b
    $ \s :: State# s
    s -> case MutableArray# s a -> State# s -> (# State# s, Array# a #)
    forall d a.
    MutableArray# d a -> State# d -> (# State# d, Array# a #)
    unsafeFreezeArray# (MArray s a -> MutableArray# s a
    forall s a. MArray s a -> MutableArray# s a
    unMArray MArray s a
    mary) State# s
    s of
            (# s' :: State# s
    s', ary :: Array# a
    ary #) -> (# State# s
    s', Array# a -> Int -> Array a
    forall a. Array# a -> Int -> Array a
    array Array# a
    ary (MArray s a -> Int
    forall s a. MArray s a -> Int
    lengthM MArray s a
    mary) #)
    {-# INLINE unsafeFreeze #-}

    run :: (forall s . ST s (MArray s e)) -> Array e
    run :: (forall s. ST s (MArray s e)) -> Array e
    run act :: forall s. ST s (MArray s e)
    act = (forall s. ST s (Array e)) -> Array e
    forall a. (forall s. ST s a) -> a
    runST ((forall s. ST s (Array e)) -> Array e)
    -> (forall s. ST s (Array e)) -> Array e
    forall a b. (a -> b) -> a -> b
    $ ST s (MArray s e)
    forall s. ST s (MArray s e)
    act ST s (MArray s e)
    -> (MArray s e -> ST s (Array e)) -> ST s (Array e)
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= MArray s e -> ST s (Array e)
    forall s a. MArray s a -> ST s (Array a)
    unsafeFreeze
    {-# INLINE run #-}

    undefinedElem :: a
    undefinedElem :: a
    undefinedElem = [Char] -> a
    forall a. HasCallStack => [Char] -> a
    error "Data.HashMap.Array: Undefined element"
    {-# NOINLINE undefinedElem #-}

    fromList :: Int -> [a] -> Array a
    fromList :: Int -> [a] -> Array a
    fromList n :: Int
    n xs0 :: [a]
    xs0 = (forall s. ST s (MArray s a)) -> Array a
    forall e. (forall s. ST s (MArray s e)) -> Array e
    run ((forall s. ST s (MArray s a)) -> Array a)
    -> (forall s. ST s (MArray s a)) -> Array a
    forall a b. (a -> b) -> a -> b
    $ do
        MArray s a
    mary <- Int -> ST s (MArray s a)
    forall s a. Int -> ST s (MArray s a)
    new_ Int
    n
        [a] -> MArray s a -> Int -> ST s (MArray s a)
    forall a s. [a] -> MArray s a -> Int -> ST s (MArray s a)
    go [a]
    xs0 MArray s a
    mary 0
      where
        go :: [a] -> MArray s a -> Int -> ST s (MArray s a)
    go [] !MArray s a
    mary !Int
    _   = MArray s a -> ST s (MArray s a)
    forall (m :: * -> *) a. Monad m => a -> m a
    return MArray s a
    mary
        go (x :: a
    x:xs :: [a]
    xs) mary :: MArray s a
    mary i :: Int
    i = do MArray s a -> Int -> a -> ST s ()
    forall s a. MArray s a -> Int -> a -> ST s ()
    write MArray s a
    mary Int
    i a
    x
                              [a] -> MArray s a -> Int -> ST s (MArray s a)
    go [a]
    xs MArray s a
    mary (Int
    iInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +1)

    toList :: Array a -> [a]
    toList :: Array a -> [a]
    toList = (a -> [a] -> [a]) -> [a] -> Array a -> [a]
    forall a b. (a -> b -> b) -> b -> Array a -> b
    foldr (:) []

    foldr :: (a -> b -> b) -> b -> Array a -> b
    foldr :: (a -> b -> b) -> b -> Array a -> b
    foldr f :: a -> b -> b
    f = \ z0 :: b
    z0 ary0 :: Array a
    ary0 -> Array a -> Int -> Int -> b -> b
    go Array a
    ary0 (Array a -> Int
    forall a. Array a -> Int
    length Array a
    ary0) 0 b
    z0
      where
        go :: Array a -> Int -> Int -> b -> b
    go ary :: Array a
    ary n :: Int
    n i :: Int
    i z :: b
    z
            | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    n    = b
    z
            | Bool
    otherwise = a -> b -> b
    f (Array a -> Int -> a
    forall a. Array a -> Int -> a
    index Array a
    ary Int
    i) (Array a -> Int -> Int -> b -> b
    go Array a
    ary Int
    n (Int
    iInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +1) b
    z)
    {-# INLINE foldr #-}