{-# 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 { forall a. Array a -> Array# a
unArray :: !(Array# a) }

length :: Array a -> Int
length :: forall a. Array a -> Int
length 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 :: forall a. Array# a -> Int -> Array a
array Array# a
ary Int
_n = Array# a -> Array a
forall a. Array# a -> Array a
Array Array# a
ary
{-# INLINE array #-}

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

lengthM :: MArray s a -> Int
lengthM :: forall s a. MArray s a -> Int
lengthM 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 :: forall s a. MutableArray# s a -> Int -> MArray s a
marray MutableArray# s a
mary 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 :: forall a s. Int -> a -> ST s (MArray s a)
new n :: Int
n@(I# Int#
n#) 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
$ \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
            (# State# s
s', 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_ :: forall s a. Int -> ST s (MArray s a)
new_ 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 :: forall s a. MArray s a -> Int -> a -> ST s ()
write MArray s a
ary _i :: Int
_i@(I# Int#
i#) 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
$ \ 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
        State# s
s' -> (# State# s
s' , () #)
{-# INLINE write #-}

index :: Array a -> Int -> a
index :: forall a. Array a -> Int -> a
index Array a
ary _i :: Int
_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 (# a
b #) -> a
b
{-# INLINE index #-}

unsafeFreeze :: MArray s a -> ST s (Array a)
unsafeFreeze :: forall s a. MArray s a -> ST s (Array a)
unsafeFreeze 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
$ \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
        (# State# s
s', 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 e. (forall s. ST s (MArray s e)) -> Array e
run 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 a b. ST s a -> (a -> ST s b) -> ST s b
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 :: forall a. a
undefinedElem = [Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"Data.HashMap.Array: Undefined element"
{-# NOINLINE undefinedElem #-}

fromList :: Int -> [a] -> Array a
fromList :: forall a. Int -> [a] -> Array a
fromList Int
n [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 Int
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 a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return MArray s a
mary
    go (a
x:[a]
xs) MArray s a
mary 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
+Int
1)

toList :: Array a -> [a]
toList :: forall a. 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 :: forall a b. (a -> b -> b) -> b -> Array a -> b
foldr a -> b -> b
f = \ b
z0 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) Int
0 b
z0
  where
    go :: Array a -> Int -> Int -> b -> b
go Array a
ary Int
n Int
i 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
+Int
1) b
z)
{-# INLINE foldr #-}