-- |
-- Module      : Streamly.Internal.Data.Array.Foreign
-- Copyright   : (c) 2019 Composewell Technologies
--
-- License     : BSD3
-- Maintainer  : streamly@composewell.com
-- Stability   : experimental
-- Portability : GHC
--
-- To summarize:
--
--  * Arrays are finite and fixed in size
--  * provide /O(1)/ access to elements
--  * store only data and not functions
--  * provide efficient IO interfacing
--
-- 'Foldable' instance is not provided because the implementation would be much
-- less efficient compared to folding via streams.  'Semigroup' and 'Monoid'
-- instances should be used with care; concatenating arrays using binary
-- operations can be highly inefficient.  Instead, use
-- 'Streamly.Internal.Data.Array.Stream.Foreign.toArray' to concatenate N
-- arrays at once.
--
-- Each array is one pointer visible to the GC.  Too many small arrays (e.g.
-- single byte) are only as good as holding those elements in a Haskell list.
-- However, small arrays can be compacted into large ones to reduce the
-- overhead. To hold 32GB memory in 32k sized buffers we need 1 million arrays
-- if we use one array for each chunk. This is still significant to add
-- pressure to GC.

module Streamly.Internal.Data.Array.Foreign
    (
      Array

    -- * Construction

    -- Pure, From Static Memory (Unsafe)
    -- We can use fromPtrM#, fromCStringM# and fromAddrM# to create arrays from
    -- a dynamic memory address which requires a finalizer.
    , A.fromPtr
    , A.fromAddr#
    , A.fromCString#

    -- Pure List APIs
    , A.fromListN
    , A.fromList

    -- Stream Folds
    , fromStreamN
    , fromStream

    -- Monadic Folds
    , A.writeN      -- drop new
    , A.writeNAligned
    , A.write       -- full buffer
    , writeLastN

    -- * Elimination
    , A.toList
    , A.toStream
    , A.toStreamRev
    , read
    , unsafeRead    -- XXX readUnsafe?
    , A.readRev
    , producer -- experimental

    -- * Random Access
    -- , (!!)
    , getIndex
    , A.unsafeIndex -- XXX Rename to getIndexUnsafe??
    , getIndexRev
    , last           -- XXX getIndexLast?
    , getIndices
    , getIndicesFromThenTo
    -- , getIndicesFrom    -- read from a given position to the end of file
    -- , getIndicesUpto    -- read from beginning up to the given position
    -- , getIndicesFromTo
    -- , getIndicesFromRev  -- read from a given position to the beginning of file
    -- , getIndicesUptoRev  -- read from end to the given position in file

    -- * Size
    , length
    , null

    -- * Search
    , binarySearch
    , findIndicesOf
    -- , findIndexOf
    -- , find

    -- * Casting
    , cast
    , asBytes
    , unsafeCast   -- castUnsafe?
    , asPtrUnsafe
    , unsafeAsCString -- asCStringUnsafe?
    , A.unsafeFreeze -- asImmutableUnsafe?
    , A.unsafeThaw   -- asMutableUnsafe?

    -- * Subarrays
    , getSliceUnsafe
    -- , getSlice
    , genSlicesFromLen
    , getSlicesFromLen
    , splitOn

    -- * Streaming Operations
    , streamTransform

    -- ** Folding
    , streamFold
    , fold
    )
where

#include "inline.hs"
#include "ArrayMacros.h"

import Control.Exception (assert)
import Control.Monad (when)
import Control.Monad.IO.Class (MonadIO(..))
import Data.Functor.Identity (Identity)
#if !(MIN_VERSION_base(4,11,0))
import Data.Semigroup ((<>))
#endif
import Data.Word (Word8)
import Foreign.C.String (CString)
import Foreign.Ptr (plusPtr, castPtr)
import Foreign.Storable (Storable(..))
import Prelude hiding (length, null, last, map, (!!), read, concat)

import Streamly.Internal.Data.Array.Foreign.Mut.Type (ReadUState(..), touch)
import Streamly.Internal.Data.Array.Foreign.Type
    (Array(..), length, asPtrUnsafe)
import Streamly.Internal.Data.Fold.Type (Fold(..))
import Streamly.Internal.Data.Producer.Type (Producer(..))
import Streamly.Internal.Data.Stream.Serial (SerialT(..))
import Streamly.Internal.Data.Tuple.Strict (Tuple3Fused'(..))
import Streamly.Internal.Data.Unfold.Type (Unfold(..))
import Streamly.Internal.System.IO (unsafeInlineIO)

import qualified Streamly.Internal.Data.Array.Foreign.Mut.Type as MA
import qualified Streamly.Internal.Data.Array.Foreign.Mut as MA
import qualified Streamly.Internal.Data.Array.Foreign.Type as A
import qualified Streamly.Internal.Data.Fold as FL
import qualified Streamly.Internal.Data.Producer as Producer
import qualified Streamly.Internal.Data.Stream.Prelude as P
import qualified Streamly.Internal.Data.Stream.StreamD as D
import qualified Streamly.Internal.Data.Unfold as Unfold
import qualified Streamly.Internal.Data.Ring.Foreign as RB

-------------------------------------------------------------------------------
-- Construction
-------------------------------------------------------------------------------

-- | Create an 'Array' from the first N elements of a stream. The array is
-- allocated to size N, if the stream terminates before N elements then the
-- array may hold less than N elements.
--
-- /Pre-release/
{-# INLINE fromStreamN #-}
fromStreamN :: (MonadIO m, Storable a) => Int -> SerialT m a -> m (Array a)
fromStreamN :: Int -> SerialT m a -> m (Array a)
fromStreamN Int
n (SerialT Stream m a
m) = do
    Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ [Char] -> m ()
forall a. HasCallStack => [Char] -> a
error [Char]
"writeN: negative write count specified"
    Int -> Stream m a -> m (Array a)
forall (m :: * -> *) a.
(MonadIO m, Storable a) =>
Int -> Stream m a -> m (Array a)
A.fromStreamDN Int
n (Stream m a -> m (Array a)) -> Stream m a -> m (Array a)
forall a b. (a -> b) -> a -> b
$ Stream m a -> Stream m a
forall (m :: * -> *) a. Applicative m => Stream m a -> Stream m a
D.fromStreamK Stream m a
m

-- | Create an 'Array' from a stream. This is useful when we want to create a
-- single array from a stream of unknown size. 'writeN' is at least twice
-- as efficient when the size is already known.
--
-- Note that if the input stream is too large memory allocation for the array
-- may fail.  When the stream size is not known, `arraysOf` followed by
-- processing of indvidual arrays in the resulting stream should be preferred.
--
-- /Pre-release/
{-# INLINE fromStream #-}
fromStream :: (MonadIO m, Storable a) => SerialT m a -> m (Array a)
fromStream :: SerialT m a -> m (Array a)
fromStream (SerialT Stream m a
m) = Fold m a (Array a) -> Stream m a -> m (Array a)
forall (m :: * -> *) a b.
Monad m =>
Fold m a b -> Stream m a -> m b
P.fold Fold m a (Array a)
forall (m :: * -> *) a.
(MonadIO m, Storable a) =>
Fold m a (Array a)
A.write Stream m a
m
-- write m = A.fromStreamD $ D.fromStreamK m

-------------------------------------------------------------------------------
-- Elimination
-------------------------------------------------------------------------------

{-# INLINE_NORMAL producer #-}
producer :: forall m a. (Monad m, Storable a) => Producer m (Array a) a
producer :: Producer m (Array a) a
producer = (ReadUState a -> m (Step (ReadUState a) a))
-> (Array a -> m (ReadUState a))
-> (ReadUState a -> m (Array a))
-> Producer m (Array a) a
forall (m :: * -> *) a b s.
(s -> m (Step s b)) -> (a -> m s) -> (s -> m a) -> Producer m a b
Producer ReadUState a -> m (Step (ReadUState a) a)
forall (m :: * -> *) a.
(Monad m, Storable a) =>
ReadUState a -> m (Step (ReadUState a) a)
step Array a -> m (ReadUState a)
forall (m :: * -> *) a. Monad m => Array a -> m (ReadUState a)
inject ReadUState a -> m (Array a)
forall (m :: * -> *) a. Monad m => ReadUState a -> m (Array a)
extract
    where

    {-# INLINE inject #-}
    inject :: Array a -> m (ReadUState a)
inject (Array ArrayContents
contents Ptr a
start Ptr a
end) = ReadUState a -> m (ReadUState a)
forall (m :: * -> *) a. Monad m => a -> m a
return (ReadUState a -> m (ReadUState a))
-> ReadUState a -> m (ReadUState a)
forall a b. (a -> b) -> a -> b
$ ArrayContents -> Ptr a -> Ptr a -> ReadUState a
forall a. ArrayContents -> Ptr a -> Ptr a -> ReadUState a
ReadUState ArrayContents
contents Ptr a
end Ptr a
start

    {-# INLINE_LATE step #-}
    step :: ReadUState a -> m (Step (ReadUState a) a)
step (ReadUState ArrayContents
contents Ptr a
end Ptr a
cur)
        | Bool -> Bool -> Bool
forall a. HasCallStack => Bool -> a -> a
assert (Ptr a
cur Ptr a -> Ptr a -> Bool
forall a. Ord a => a -> a -> Bool
<= Ptr a
end) (Ptr a
cur Ptr a -> Ptr a -> Bool
forall a. Eq a => a -> a -> Bool
== Ptr a
end) =
            let x :: ()
x = IO () -> ()
forall a. IO a -> a
unsafeInlineIO (IO () -> ()) -> IO () -> ()
forall a b. (a -> b) -> a -> b
$ ArrayContents -> IO ()
touch ArrayContents
contents
            in ()
x () -> m (Step (ReadUState a) a) -> m (Step (ReadUState a) a)
`seq` Step (ReadUState a) a -> m (Step (ReadUState a) a)
forall (m :: * -> *) a. Monad m => a -> m a
return Step (ReadUState a) a
forall s a. Step s a
D.Stop
    step (ReadUState ArrayContents
contents Ptr a
end Ptr a
cur) = do
            -- unsafeInlineIO allows us to run this in Identity monad for pure
            -- toList/foldr case which makes them much faster due to not
            -- accumulating the list and fusing better with the pure consumers.
            --
            -- This should be safe as the array contents are guaranteed to be
            -- evaluated/written to before we peek at them.
            let !x :: a
x = IO a -> a
forall a. IO a -> a
unsafeInlineIO (IO a -> a) -> IO a -> a
forall a b. (a -> b) -> a -> b
$ Ptr a -> IO a
forall a. Storable a => Ptr a -> IO a
peek Ptr a
cur
            Step (ReadUState a) a -> m (Step (ReadUState a) a)
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (ReadUState a) a -> m (Step (ReadUState a) a))
-> Step (ReadUState a) a -> m (Step (ReadUState a) a)
forall a b. (a -> b) -> a -> b
$ a -> ReadUState a -> Step (ReadUState a) a
forall s a. a -> s -> Step s a
D.Yield a
x (ArrayContents -> Ptr a -> Ptr a -> ReadUState a
forall a. ArrayContents -> Ptr a -> Ptr a -> ReadUState a
ReadUState ArrayContents
contents Ptr a
end (PTR_NEXT(cur,a)))

    extract :: ReadUState a -> m (Array a)
extract (ReadUState ArrayContents
contents Ptr a
end Ptr a
cur) = Array a -> m (Array a)
forall (m :: * -> *) a. Monad m => a -> m a
return (Array a -> m (Array a)) -> Array a -> m (Array a)
forall a b. (a -> b) -> a -> b
$ ArrayContents -> Ptr a -> Ptr a -> Array a
forall a. ArrayContents -> Ptr a -> Ptr a -> Array a
Array ArrayContents
contents Ptr a
cur Ptr a
end

-- | Unfold an array into a stream.
--
-- /Since 0.7.0 (Streamly.Memory.Array)/
--
-- @since 0.8.0
{-# INLINE_NORMAL read #-}
read :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
read :: Unfold m (Array a) a
read = Producer m (Array a) a -> Unfold m (Array a) a
forall (m :: * -> *) a b. Producer m a b -> Unfold m a b
Producer.simplify Producer m (Array a) a
forall (m :: * -> *) a.
(Monad m, Storable a) =>
Producer m (Array a) a
producer

-- | Unfold an array into a stream, does not check the end of the array, the
-- user is responsible for terminating the stream within the array bounds. For
-- high performance application where the end condition can be determined by
-- a terminating fold.
--
-- Written in the hope that it may be faster than "read", however, in the case
-- for which this was written, "read" proves to be faster even though the core
-- generated with unsafeRead looks simpler.
--
-- /Pre-release/
--
{-# INLINE_NORMAL unsafeRead #-}
unsafeRead :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
unsafeRead :: Unfold m (Array a) a
unsafeRead = (ReadUState a -> m (Step (ReadUState a) a))
-> (Array a -> m (ReadUState a)) -> Unfold m (Array a) a
forall (m :: * -> *) a b s.
(s -> m (Step s b)) -> (a -> m s) -> Unfold m a b
Unfold ReadUState a -> m (Step (ReadUState a) a)
forall (m :: * -> *) a.
(Monad m, Storable a) =>
ReadUState a -> m (Step (ReadUState a) a)
step Array a -> m (ReadUState a)
forall (m :: * -> *) a. Monad m => Array a -> m (ReadUState a)
inject
    where

    inject :: Array a -> m (ReadUState a)
inject (Array ArrayContents
contents Ptr a
start Ptr a
end) =
        ReadUState a -> m (ReadUState a)
forall (m :: * -> *) a. Monad m => a -> m a
return (ArrayContents -> Ptr a -> Ptr a -> ReadUState a
forall a. ArrayContents -> Ptr a -> Ptr a -> ReadUState a
ReadUState ArrayContents
contents Ptr a
end Ptr a
start)

    {-# INLINE_LATE step #-}
    step :: ReadUState a -> m (Step (ReadUState a) a)
step (ReadUState ArrayContents
contents Ptr a
end Ptr a
p) = do
            -- unsafeInlineIO allows us to run this in Identity monad for pure
            -- toList/foldr case which makes them much faster due to not
            -- accumulating the list and fusing better with the pure consumers.
            --
            -- This should be safe as the array contents are guaranteed to be
            -- evaluated/written to before we peek at them.
            let !x :: a
x = IO a -> a
forall a. IO a -> a
unsafeInlineIO (IO a -> a) -> IO a -> a
forall a b. (a -> b) -> a -> b
$ do
                        a
r <- Ptr a -> IO a
forall a. Storable a => Ptr a -> IO a
peek Ptr a
p
                        ArrayContents -> IO ()
touch ArrayContents
contents
                        a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return a
r
            let !p1 :: Ptr b
p1 = PTR_NEXT(p,a)
            Step (ReadUState a) a -> m (Step (ReadUState a) a)
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (ReadUState a) a -> m (Step (ReadUState a) a))
-> Step (ReadUState a) a -> m (Step (ReadUState a) a)
forall a b. (a -> b) -> a -> b
$ a -> ReadUState a -> Step (ReadUState a) a
forall s a. a -> s -> Step s a
D.Yield a
x (ArrayContents -> Ptr a -> Ptr a -> ReadUState a
forall a. ArrayContents -> Ptr a -> Ptr a -> ReadUState a
ReadUState ArrayContents
contents Ptr a
end Ptr a
forall b. Ptr b
p1)

-- |
--
-- >>> import qualified Streamly.Internal.Data.Array.Foreign.Type as Array
-- >>> null arr = Array.byteLength arr == 0
--
-- /Pre-release/
{-# INLINE null #-}
null :: Array a -> Bool
null :: Array a -> Bool
null Array a
arr = Array a -> Int
forall a. Array a -> Int
A.byteLength Array a
arr Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0

-- | Like 'getIndex' but indexes the array in reverse from the end.
--
-- /Pre-release/
{-# INLINE getIndexRev #-}
getIndexRev :: forall a. Storable a => Int -> Array a -> Maybe a
getIndexRev :: Int -> Array a -> Maybe a
getIndexRev Int
i Array a
arr =
    IO (Maybe a) -> Maybe a
forall a. IO a -> a
unsafeInlineIO
        (IO (Maybe a) -> Maybe a) -> IO (Maybe a) -> Maybe a
forall a b. (a -> b) -> a -> b
$ Array a -> (Ptr a -> IO (Maybe a)) -> IO (Maybe a)
forall (m :: * -> *) a b.
MonadIO m =>
Array a -> (Ptr a -> m b) -> m b
asPtrUnsafe Array a
arr
            ((Ptr a -> IO (Maybe a)) -> IO (Maybe a))
-> (Ptr a -> IO (Maybe a)) -> IO (Maybe a)
forall a b. (a -> b) -> a -> b
$ \Ptr a
ptr -> do
                let elemPtr :: Ptr b
elemPtr = PTR_RINDEX(aEnd arr,i,a)
                if Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 Bool -> Bool -> Bool
&& Ptr a
forall b. Ptr b
elemPtr Ptr a -> Ptr a -> Bool
forall a. Ord a => a -> a -> Bool
>= Ptr a
ptr
                then a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> IO a -> IO (Maybe a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Ptr a -> IO a
forall a. Storable a => Ptr a -> IO a
peek Ptr a
forall b. Ptr b
elemPtr
                else Maybe a -> IO (Maybe a)
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe a
forall a. Maybe a
Nothing

-- |
--
-- >>> import qualified Streamly.Internal.Data.Array.Foreign as Array
-- >>> last arr = Array.getIndexRev arr 0
--
-- /Pre-release/
{-# INLINE last #-}
last :: Storable a => Array a -> Maybe a
last :: Array a -> Maybe a
last = Int -> Array a -> Maybe a
forall a. Storable a => Int -> Array a -> Maybe a
getIndexRev Int
0

-------------------------------------------------------------------------------
-- Folds with Array as the container
-------------------------------------------------------------------------------

-- | @writeLastN n@ folds a maximum of @n@ elements from the end of the input
-- stream to an 'Array'.
--
-- @since 0.8.0
{-# INLINE writeLastN #-}
writeLastN :: (Storable a, MonadIO m) => Int -> Fold m a (Array a)
writeLastN :: Int -> Fold m a (Array a)
writeLastN Int
n
    | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = (() -> Array a) -> Fold m a () -> Fold m a (Array a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Array a -> () -> Array a
forall a b. a -> b -> a
const Array a
forall a. Monoid a => a
mempty) Fold m a ()
forall (m :: * -> *) a. Monad m => Fold m a ()
FL.drain
    | Bool
otherwise = Array a -> Array a
forall a. Array a -> Array a
A.unsafeFreeze (Array a -> Array a) -> Fold m a (Array a) -> Fold m a (Array a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Tuple3Fused' (Ring a) (Ptr a) Int
 -> a -> m (Step (Tuple3Fused' (Ring a) (Ptr a) Int) (Array a)))
-> m (Step (Tuple3Fused' (Ring a) (Ptr a) Int) (Array a))
-> (Tuple3Fused' (Ring a) (Ptr a) Int -> m (Array a))
-> Fold m a (Array a)
forall (m :: * -> *) a b s.
(s -> a -> m (Step s b))
-> m (Step s b) -> (s -> m b) -> Fold m a b
Fold Tuple3Fused' (Ring a) (Ptr a) Int
-> a -> m (Step (Tuple3Fused' (Ring a) (Ptr a) Int) (Array a))
forall (m :: * -> *) a c b.
(MonadIO m, Storable a, Num c) =>
Tuple3Fused' (Ring a) (Ptr a) c
-> a -> m (Step (Tuple3Fused' (Ring a) (Ptr a) c) b)
step m (Step (Tuple3Fused' (Ring a) (Ptr a) Int) (Array a))
forall b. m (Step (Tuple3Fused' (Ring a) (Ptr a) Int) b)
initial Tuple3Fused' (Ring a) (Ptr a) Int -> m (Array a)
forall (m :: * -> *) a.
(MonadIO m, Storable a) =>
Tuple3Fused' (Ring a) (Ptr a) Int -> m (Array a)
done

    where

    step :: Tuple3Fused' (Ring a) (Ptr a) c
-> a -> m (Step (Tuple3Fused' (Ring a) (Ptr a) c) b)
step (Tuple3Fused' Ring a
rb Ptr a
rh c
i) a
a = do
        Ptr a
rh1 <- IO (Ptr a) -> m (Ptr a)
forall (m :: * -> *) a. MonadIO m => IO a -> m a
liftIO (IO (Ptr a) -> m (Ptr a)) -> IO (Ptr a) -> m (Ptr a)
forall a b. (a -> b) -> a -> b
$ Ring a -> Ptr a -> a -> IO (Ptr a)
forall a. Storable a => Ring a -> Ptr a -> a -> IO (Ptr a)
RB.unsafeInsert Ring a
rb Ptr a
rh a
a
        Step (Tuple3Fused' (Ring a) (Ptr a) c) b
-> m (Step (Tuple3Fused' (Ring a) (Ptr a) c) b)
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (Tuple3Fused' (Ring a) (Ptr a) c) b
 -> m (Step (Tuple3Fused' (Ring a) (Ptr a) c) b))
-> Step (Tuple3Fused' (Ring a) (Ptr a) c) b
-> m (Step (Tuple3Fused' (Ring a) (Ptr a) c) b)
forall a b. (a -> b) -> a -> b
$ Tuple3Fused' (Ring a) (Ptr a) c
-> Step (Tuple3Fused' (Ring a) (Ptr a) c) b
forall s b. s -> Step s b
FL.Partial (Tuple3Fused' (Ring a) (Ptr a) c
 -> Step (Tuple3Fused' (Ring a) (Ptr a) c) b)
-> Tuple3Fused' (Ring a) (Ptr a) c
-> Step (Tuple3Fused' (Ring a) (Ptr a) c) b
forall a b. (a -> b) -> a -> b
$ Ring a -> Ptr a -> c -> Tuple3Fused' (Ring a) (Ptr a) c
forall a b c. a -> b -> c -> Tuple3Fused' a b c
Tuple3Fused' Ring a
rb Ptr a
rh1 (c
i c -> c -> c
forall a. Num a => a -> a -> a
+ c
1)

    initial :: m (Step (Tuple3Fused' (Ring a) (Ptr a) Int) b)
initial =
        let f :: (a, b) -> Step (Tuple3Fused' a b Int) b
f (a
a, b
b) = Tuple3Fused' a b Int -> Step (Tuple3Fused' a b Int) b
forall s b. s -> Step s b
FL.Partial (Tuple3Fused' a b Int -> Step (Tuple3Fused' a b Int) b)
-> Tuple3Fused' a b Int -> Step (Tuple3Fused' a b Int) b
forall a b. (a -> b) -> a -> b
$ a -> b -> Int -> Tuple3Fused' a b Int
forall a b c. a -> b -> c -> Tuple3Fused' a b c
Tuple3Fused' a
a b
b (Int
0 :: Int)
         in ((Ring a, Ptr a) -> Step (Tuple3Fused' (Ring a) (Ptr a) Int) b)
-> m (Ring a, Ptr a)
-> m (Step (Tuple3Fused' (Ring a) (Ptr a) Int) b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Ring a, Ptr a) -> Step (Tuple3Fused' (Ring a) (Ptr a) Int) b
forall a b b. (a, b) -> Step (Tuple3Fused' a b Int) b
f (m (Ring a, Ptr a)
 -> m (Step (Tuple3Fused' (Ring a) (Ptr a) Int) b))
-> m (Ring a, Ptr a)
-> m (Step (Tuple3Fused' (Ring a) (Ptr a) Int) b)
forall a b. (a -> b) -> a -> b
$ IO (Ring a, Ptr a) -> m (Ring a, Ptr a)
forall (m :: * -> *) a. MonadIO m => IO a -> m a
liftIO (IO (Ring a, Ptr a) -> m (Ring a, Ptr a))
-> IO (Ring a, Ptr a) -> m (Ring a, Ptr a)
forall a b. (a -> b) -> a -> b
$ Int -> IO (Ring a, Ptr a)
forall a. Storable a => Int -> IO (Ring a, Ptr a)
RB.new Int
n

    done :: Tuple3Fused' (Ring a) (Ptr a) Int -> m (Array a)
done (Tuple3Fused' Ring a
rb Ptr a
rh Int
i) = do
        Array a
arr <- IO (Array a) -> m (Array a)
forall (m :: * -> *) a. MonadIO m => IO a -> m a
liftIO (IO (Array a) -> m (Array a)) -> IO (Array a) -> m (Array a)
forall a b. (a -> b) -> a -> b
$ Int -> IO (Array a)
forall (m :: * -> *) a.
(MonadIO m, Storable a) =>
Int -> m (Array a)
MA.newArray Int
n
        Int
-> Ptr a
-> (Array a -> a -> m (Array a))
-> Array a
-> Ring a
-> m (Array a)
forall (m :: * -> *) a b.
(MonadIO m, Storable a) =>
Int -> Ptr a -> (b -> a -> m b) -> b -> Ring a -> m b
foldFunc Int
i Ptr a
rh Array a -> a -> m (Array a)
forall (m :: * -> *) a.
(MonadIO m, Storable a) =>
Array a -> a -> m (Array a)
snoc' Array a
arr Ring a
rb

    -- XXX We should write a read unfold for ring.
    snoc' :: Array a -> a -> m (Array a)
snoc' Array a
b a
a = IO (Array a) -> m (Array a)
forall (m :: * -> *) a. MonadIO m => IO a -> m a
liftIO (IO (Array a) -> m (Array a)) -> IO (Array a) -> m (Array a)
forall a b. (a -> b) -> a -> b
$ Array a -> a -> IO (Array a)
forall (m :: * -> *) a.
(MonadIO m, Storable a) =>
Array a -> a -> m (Array a)
MA.snocUnsafe Array a
b a
a

    foldFunc :: Int -> Ptr a -> (b -> a -> m b) -> b -> Ring a -> m b
foldFunc Int
i
        | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n = Ptr a -> (b -> a -> m b) -> b -> Ring a -> m b
forall (m :: * -> *) a b.
(MonadIO m, Storable a) =>
Ptr a -> (b -> a -> m b) -> b -> Ring a -> m b
RB.unsafeFoldRingM
        | Bool
otherwise = Ptr a -> (b -> a -> m b) -> b -> Ring a -> m b
forall (m :: * -> *) a b.
(MonadIO m, Storable a) =>
Ptr a -> (b -> a -> m b) -> b -> Ring a -> m b
RB.unsafeFoldRingFullM

-------------------------------------------------------------------------------
-- Random Access
-------------------------------------------------------------------------------

-------------------------------------------------------------------------------
-- Searching
-------------------------------------------------------------------------------

-- | Given a sorted array, perform a binary search to find the given element.
-- Returns the index of the element if found.
--
-- /Unimplemented/
{-# INLINE binarySearch #-}
binarySearch :: a -> Array a -> Maybe Int
binarySearch :: a -> Array a -> Maybe Int
binarySearch = a -> Array a -> Maybe Int
forall a. HasCallStack => a
undefined

-- find/findIndex etc can potentially be implemented more efficiently on arrays
-- compared to streams by using SIMD instructions.
-- We can also return a bit array instead.

-- | Perform a linear search to find all the indices where a given element is
-- present in an array.
--
-- /Unimplemented/
findIndicesOf :: (a -> Bool) -> Unfold Identity (Array a) Int
findIndicesOf :: (a -> Bool) -> Unfold Identity (Array a) Int
findIndicesOf = (a -> Bool) -> Unfold Identity (Array a) Int
forall a. HasCallStack => a
undefined

{-
findIndexOf :: (a -> Bool) -> Array a -> Maybe Int
findIndexOf p = Unfold.fold Fold.head . Stream.unfold (findIndicesOf p)

find :: (a -> Bool) -> Array a -> Bool
find = Unfold.fold Fold.null . Stream.unfold (findIndicesOf p)
-}

-------------------------------------------------------------------------------
-- Folds
-------------------------------------------------------------------------------

-- XXX We can potentially use SIMD instructions on arrays to fold faster.

-------------------------------------------------------------------------------
-- Slice
-------------------------------------------------------------------------------

-- | /O(1)/ Slice an array in constant time.
--
-- Caution: The bounds of the slice are not checked.
--
-- /Unsafe/
--
-- /Pre-release/
{-# INLINE getSliceUnsafe #-}
getSliceUnsafe ::
       forall a. Storable a
    => Int -- ^ starting index
    -> Int -- ^ length of the slice
    -> Array a
    -> Array a
getSliceUnsafe :: Int -> Int -> Array a -> Array a
getSliceUnsafe Int
index Int
len (Array ArrayContents
contents Ptr a
start Ptr a
e) =
    let size :: Int
size = SIZE_OF(a)
        fp1 :: Ptr b
fp1 = Ptr a
start Ptr a -> Int -> Ptr b
forall a b. Ptr a -> Int -> Ptr b
`plusPtr` (Int
index Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
size)
        end :: Ptr b
end = Ptr Any
forall b. Ptr b
fp1 Ptr Any -> Int -> Ptr b
forall a b. Ptr a -> Int -> Ptr b
`plusPtr` (Int
len Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
size)
     in Bool -> Array a -> Array a
forall a. HasCallStack => Bool -> a -> a
assert (Ptr a
forall b. Ptr b
end Ptr a -> Ptr a -> Bool
forall a. Ord a => a -> a -> Bool
<= Ptr a
e) (ArrayContents -> Ptr a -> Ptr a -> Array a
forall a. ArrayContents -> Ptr a -> Ptr a -> Array a
Array ArrayContents
contents Ptr a
forall b. Ptr b
fp1 Ptr a
forall b. Ptr b
end)

-- | Split the array into a stream of slices using a predicate. The element
-- matching the predicate is dropped.
--
-- /Pre-release/
{-# INLINE splitOn #-}
splitOn :: (Monad m, Storable a) =>
    (a -> Bool) -> Array a -> SerialT m (Array a)
splitOn :: (a -> Bool) -> Array a -> SerialT m (Array a)
splitOn a -> Bool
predicate Array a
arr =
    Stream m (Array a) -> SerialT m (Array a)
forall (m :: * -> *) a. Stream m a -> SerialT m a
SerialT (Stream m (Array a) -> SerialT m (Array a))
-> Stream m (Array a) -> SerialT m (Array a)
forall a b. (a -> b) -> a -> b
$ Stream m (Array a) -> Stream m (Array a)
forall (m :: * -> *) a. Monad m => Stream m a -> Stream m a
D.toStreamK
        (Stream m (Array a) -> Stream m (Array a))
-> Stream m (Array a) -> Stream m (Array a)
forall a b. (a -> b) -> a -> b
$ ((Int, Int) -> Array a)
-> Stream m (Int, Int) -> Stream m (Array a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(Int
i, Int
len) -> Int -> Int -> Array a -> Array a
forall a. Storable a => Int -> Int -> Array a -> Array a
getSliceUnsafe Int
i Int
len Array a
arr)
        (Stream m (Int, Int) -> Stream m (Array a))
-> Stream m (Int, Int) -> Stream m (Array a)
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> Stream m a -> Stream m (Int, Int)
forall (m :: * -> *) a.
Monad m =>
(a -> Bool) -> Stream m a -> Stream m (Int, Int)
D.sliceOnSuffix a -> Bool
predicate (Array a -> Stream m a
forall (m :: * -> *) a.
(Monad m, Storable a) =>
Array a -> Stream m a
A.toStreamD Array a
arr)

{-# INLINE genSlicesFromLen #-}
genSlicesFromLen :: forall m a. (Monad m, Storable a)
    => Int -- ^ from index
    -> Int -- ^ length of the slice
    -> Unfold m (Array a) (Int, Int)
genSlicesFromLen :: Int -> Int -> Unfold m (Array a) (Int, Int)
genSlicesFromLen Int
from Int
len =
    (Array a -> Array a)
-> Unfold m (Array a) (Int, Int) -> Unfold m (Array a) (Int, Int)
forall a c (m :: * -> *) b.
(a -> c) -> Unfold m c b -> Unfold m a b
Unfold.lmap Array a -> Array a
forall a. Array a -> Array a
A.unsafeThaw (Int -> Int -> Unfold m (Array a) (Int, Int)
forall (m :: * -> *) a.
(Monad m, Storable a) =>
Int -> Int -> Unfold m (Array a) (Int, Int)
MA.genSlicesFromLen Int
from Int
len)

-- | Generate a stream of slices of specified length from an array, starting
-- from the supplied array index. The last slice may be shorter than the
-- requested length.
--
-- /Pre-release//
{-# INLINE getSlicesFromLen #-}
getSlicesFromLen :: forall m a. (Monad m, Storable a)
    => Int -- ^ from index
    -> Int -- ^ length of the slice
    -> Unfold m (Array a) (Array a)
getSlicesFromLen :: Int -> Int -> Unfold m (Array a) (Array a)
getSlicesFromLen Int
from Int
len =
    (Array a -> Array a)
-> Unfold m (Array a) (Array a) -> Unfold m (Array a) (Array a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Array a -> Array a
forall a. Array a -> Array a
A.unsafeFreeze
        (Unfold m (Array a) (Array a) -> Unfold m (Array a) (Array a))
-> Unfold m (Array a) (Array a) -> Unfold m (Array a) (Array a)
forall a b. (a -> b) -> a -> b
$ (Array a -> Array a)
-> Unfold m (Array a) (Array a) -> Unfold m (Array a) (Array a)
forall a c (m :: * -> *) b.
(a -> c) -> Unfold m c b -> Unfold m a b
Unfold.lmap Array a -> Array a
forall a. Array a -> Array a
A.unsafeThaw (Int -> Int -> Unfold m (Array a) (Array a)
forall (m :: * -> *) a.
(Monad m, Storable a) =>
Int -> Int -> Unfold m (Array a) (Array a)
MA.getSlicesFromLen Int
from Int
len)

-------------------------------------------------------------------------------
-- Random reads and writes
-------------------------------------------------------------------------------

-- XXX Change this to a partial function instead of a Maybe type? And use
-- MA.getIndex instead.
--
-- XXX The signature should be "Int -> Array a -> Maybe a"
-- XXX This is a released API so make this change in the next major release.
-- | /O(1)/ Lookup the element at the given index. Index starts from 0.
--
-- @since 0.8.0
{-# INLINE getIndex #-}
getIndex :: forall a. Storable a => Array a -> Int -> Maybe a
getIndex :: Array a -> Int -> Maybe a
getIndex Array a
arr Int
i =
    IO (Maybe a) -> Maybe a
forall a. IO a -> a
unsafeInlineIO
        (IO (Maybe a) -> Maybe a) -> IO (Maybe a) -> Maybe a
forall a b. (a -> b) -> a -> b
$ Array a -> (Ptr a -> IO (Maybe a)) -> IO (Maybe a)
forall (m :: * -> *) a b.
MonadIO m =>
Array a -> (Ptr a -> m b) -> m b
asPtrUnsafe Array a
arr
            ((Ptr a -> IO (Maybe a)) -> IO (Maybe a))
-> (Ptr a -> IO (Maybe a)) -> IO (Maybe a)
forall a b. (a -> b) -> a -> b
$ \Ptr a
ptr -> do
                let elemPtr :: Ptr b
elemPtr = PTR_INDEX(ptr,i,a)
                if Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 Bool -> Bool -> Bool
&& PTR_VALID(elemPtr,aEnd arr,a)
                then a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> IO a -> IO (Maybe a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Ptr a -> IO a
forall a. Storable a => Ptr a -> IO a
peek Ptr a
forall b. Ptr b
elemPtr
                else Maybe a -> IO (Maybe a)
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe a
forall a. Maybe a
Nothing

-- | Given a stream of array indices, read the elements on those indices from
-- the supplied Array. An exception is thrown if an index is out of bounds.
--
-- This is the most general operation. We can implement other operations in
-- terms of this:
--
-- @
-- read =
--      let u = lmap (\arr -> (0, length arr - 1)) Unfold.enumerateFromTo
--       in Unfold.lmap f (getIndices arr)
--
-- readRev =
--      let i = length arr - 1
--       in Unfold.lmap f (getIndicesFromThenTo i (i - 1) 0)
-- @
--
-- /Pre-release/
{-# INLINE getIndices #-}
getIndices :: (Monad m, Storable a) => SerialT m Int -> Unfold m (Array a) a
getIndices :: SerialT m Int -> Unfold m (Array a) a
getIndices (SerialT Stream m Int
stream) =
    let unf :: Unfold m (Array a) a
unf = (forall b. IO b -> m b) -> Stream m Int -> Unfold m (Array a) a
forall (m :: * -> *) a.
(Monad m, Storable a) =>
(forall b. IO b -> m b) -> Stream m Int -> Unfold m (Array a) a
MA.getIndicesD (b -> m b
forall (m :: * -> *) a. Monad m => a -> m a
return (b -> m b) -> (IO b -> b) -> IO b -> m b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IO b -> b
forall a. IO a -> a
unsafeInlineIO) (Stream m Int -> Unfold m (Array a) a)
-> Stream m Int -> Unfold m (Array a) a
forall a b. (a -> b) -> a -> b
$ Stream m Int -> Stream m Int
forall (m :: * -> *) a. Applicative m => Stream m a -> Stream m a
D.fromStreamK Stream m Int
stream
     in (Array a -> Array a)
-> Unfold m (Array a) a -> Unfold m (Array a) a
forall a c (m :: * -> *) b.
(a -> c) -> Unfold m c b -> Unfold m a b
Unfold.lmap Array a -> Array a
forall a. Array a -> Array a
A.unsafeThaw Unfold m (Array a) a
unf

-- | Unfolds @(from, then, to, array)@ generating a finite stream whose first
-- element is the array value from the index @from@ and the successive elements
-- are from the indices in increments of @then@ up to @to@. Index enumeration
-- can occur downwards or upwards depending on whether @then@ comes before or
-- after @from@.
--
-- @
-- getIndicesFromThenTo =
--     let f (from, next, to, arr) =
--             (Stream.enumerateFromThenTo from next to, arr)
--      in Unfold.lmap f getIndices
-- @
--
-- /Unimplemented/
{-# INLINE getIndicesFromThenTo #-}
getIndicesFromThenTo :: Unfold m (Int, Int, Int, Array a) a
getIndicesFromThenTo :: Unfold m (Int, Int, Int, Array a) a
getIndicesFromThenTo = Unfold m (Int, Int, Int, Array a) a
forall a. HasCallStack => a
undefined

-------------------------------------------------------------------------------
-- Transform via stream operations
-------------------------------------------------------------------------------

-- for non-length changing operations we can use the original length for
-- allocation. If we can predict the length then we can use the prediction for
-- new allocation. Otherwise we can use a hint and adjust dynamically.

{-
-- | Transform an array into another array using a pipe transformation
-- operation.
--
-- @since 0.7.0
{-# INLINE runPipe #-}
runPipe :: (MonadIO m, Storable a, Storable b)
    => Pipe m a b -> Array a -> m (Array b)
runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
-}

-- XXX For transformations that cannot change the number of elements e.g. "map"
-- we can use a predetermined array length.
--
-- | Transform an array into another array using a stream transformation
-- operation.
--
-- /Pre-release/
{-# INLINE streamTransform #-}
streamTransform :: forall m a b. (MonadIO m, Storable a, Storable b)
    => (SerialT m a -> SerialT m b) -> Array a -> m (Array b)
streamTransform :: (SerialT m a -> SerialT m b) -> Array a -> m (Array b)
streamTransform SerialT m a -> SerialT m b
f Array a
arr =
    Fold m b (Array b) -> Stream m b -> m (Array b)
forall (m :: * -> *) a b.
Monad m =>
Fold m a b -> Stream m a -> m b
P.fold (Int -> Fold m b (Array b)
forall (m :: * -> *) a.
(MonadIO m, Storable a) =>
Int -> Fold m a (Array a)
A.writeWith (Array a -> Int
forall a. Storable a => Array a -> Int
length Array a
arr)) (Stream m b -> m (Array b)) -> Stream m b -> m (Array b)
forall a b. (a -> b) -> a -> b
$ SerialT m b -> Stream m b
forall (m :: * -> *) a. SerialT m a -> Stream m a
getSerialT (SerialT m b -> Stream m b) -> SerialT m b -> Stream m b
forall a b. (a -> b) -> a -> b
$ SerialT m a -> SerialT m b
f (Array a -> SerialT m a
forall (m :: * -> *) a.
(Monad m, Storable a) =>
Array a -> SerialT m a
A.toStream Array a
arr)

-------------------------------------------------------------------------------
-- Casts
-------------------------------------------------------------------------------

-- | Cast an array having elements of type @a@ into an array having elements of
-- type @b@. The array size must be a multiple of the size of type @b@
-- otherwise accessing the last element of the array may result into a crash or
-- a random value.
--
-- /Pre-release/
--
unsafeCast ::
#ifdef DEVBUILD
    Storable b =>
#endif
    Array a -> Array b
unsafeCast :: Array a -> Array b
unsafeCast (Array ArrayContents
contents Ptr a
start Ptr a
end) =
    ArrayContents -> Ptr b -> Ptr b -> Array b
forall a. ArrayContents -> Ptr a -> Ptr a -> Array a
Array ArrayContents
contents (Ptr a -> Ptr b
forall a b. Ptr a -> Ptr b
castPtr Ptr a
start) (Ptr a -> Ptr b
forall a b. Ptr a -> Ptr b
castPtr Ptr a
end)

-- | Cast an @Array a@ into an @Array Word8@.
--
-- @since 0.8.0
--
asBytes :: Array a -> Array Word8
asBytes :: Array a -> Array Word8
asBytes = Array a -> Array Word8
forall a b. Array a -> Array b
unsafeCast

-- | Cast an array having elements of type @a@ into an array having elements of
-- type @b@. The length of the array should be a multiple of the size of the
-- target element otherwise 'Nothing' is returned.
--
-- @since 0.8.0
--
cast :: forall a b. (Storable b) => Array a -> Maybe (Array b)
cast :: Array a -> Maybe (Array b)
cast Array a
arr =
    let len :: Int
len = Array a -> Int
forall a. Array a -> Int
A.byteLength Array a
arr
        r :: Int
r = Int
len Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` SIZE_OF(b)
     in if Int
r Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
0
        then Maybe (Array b)
forall a. Maybe a
Nothing
        else Array b -> Maybe (Array b)
forall a. a -> Maybe a
Just (Array b -> Maybe (Array b)) -> Array b -> Maybe (Array b)
forall a b. (a -> b) -> a -> b
$ Array a -> Array b
forall a b. Array a -> Array b
unsafeCast Array a
arr

-- | Convert an array of any type into a null terminated CString Ptr.
--
-- /Unsafe/
--
-- /O(n) Time: (creates a copy of the array)/
--
-- /Pre-release/
--
unsafeAsCString :: Array a -> (CString -> IO b) -> IO b
unsafeAsCString :: Array a -> (CString -> IO b) -> IO b
unsafeAsCString Array a
arr CString -> IO b
act = do
    let arr1 :: Array Word8
arr1 = Array a -> Array Word8
forall a. Array a -> Array Word8
asBytes Array a
arr Array Word8 -> Array Word8 -> Array Word8
forall a. Semigroup a => a -> a -> a
<> [Word8] -> Array Word8
forall a. Storable a => [a] -> Array a
A.fromList [Word8
0]
    Array Word8 -> (Ptr Word8 -> IO b) -> IO b
forall (m :: * -> *) a b.
MonadIO m =>
Array a -> (Ptr a -> m b) -> m b
asPtrUnsafe Array Word8
arr1 ((Ptr Word8 -> IO b) -> IO b) -> (Ptr Word8 -> IO b) -> IO b
forall a b. (a -> b) -> a -> b
$ \Ptr Word8
ptr -> CString -> IO b
act (Ptr Word8 -> CString
forall a b. Ptr a -> Ptr b
castPtr Ptr Word8
ptr)

-------------------------------------------------------------------------------
-- Folds
-------------------------------------------------------------------------------

-- | Fold an array using a 'Fold'.
--
-- /Pre-release/
{-# INLINE fold #-}
fold :: forall m a b. (MonadIO m, Storable a) => Fold m a b -> Array a -> m b
fold :: Fold m a b -> Array a -> m b
fold Fold m a b
f Array a
arr = Fold m a b -> Stream m a -> m b
forall (m :: * -> *) a b.
Monad m =>
Fold m a b -> Stream m a -> m b
P.fold Fold m a b
f (SerialT m a -> Stream m a
forall (m :: * -> *) a. SerialT m a -> Stream m a
getSerialT (Array a -> SerialT m a
forall (m :: * -> *) a.
(Monad m, Storable a) =>
Array a -> SerialT m a
A.toStream Array a
arr))

-- | Fold an array using a stream fold operation.
--
-- /Pre-release/
{-# INLINE streamFold #-}
streamFold :: (MonadIO m, Storable a) => (SerialT m a -> m b) -> Array a -> m b
streamFold :: (SerialT m a -> m b) -> Array a -> m b
streamFold SerialT m a -> m b
f Array a
arr = SerialT m a -> m b
f (Array a -> SerialT m a
forall (m :: * -> *) a.
(Monad m, Storable a) =>
Array a -> SerialT m a
A.toStream Array a
arr)