{-|
Module      : Z.Data.Vector.Extra
Description : Fast vector slice manipulation
Copyright   : (c) Dong Han, 2017-2018
License     : BSD
Maintainer  : winterland1989@gmail.com
Stability   : experimental
Portability : non-portable

Various combinators works on 'Vec' class instances.

-}

module Z.Data.Vector.Extra (
  -- * Slice manipulation
    cons, snoc
  , uncons, unsnoc
  , headMaybe, tailMayEmpty
  , lastMaybe, initMayEmpty
  , inits, tails
  , take, drop, takeR, dropR
  , slice
  , splitAt
  , takeWhile, takeWhileR, dropWhile, dropWhileR, dropAround
  , break, span, breakR, spanR, breakOn
  , group, groupBy
  , stripPrefix, stripSuffix
  , split, splitWith, splitOn
  , isPrefixOf, isSuffixOf, isInfixOf
  , commonPrefix
  , words, lines, unwords, unlines
  , padLeft, padRight
  -- * Transform
  , reverse
  , intersperse
  , intercalate
  , intercalateElem
  , transpose
  -- * Zipping
  , zipWith', unzipWith'
  -- * Scans
  , scanl', scanl1'
  , scanr', scanr1'
  -- * Misc
  , rangeCut
  -- * Unsafe operations
  , head
  , tail
  , init
  , last
  , index, indexM
  , modifyIndex, modifyIndexMaybe
  , insertIndex, insertIndexMaybe
  , deleteIndex, deleteIndexMaybe
  , unsafeHead
  , unsafeTail
  , unsafeInit
  , unsafeLast
  , unsafeIndex, unsafeIndexM, unsafeModifyIndex, unsafeInsertIndex, unsafeDeleteIndex
  , unsafeTake
  , unsafeDrop
  ) where

import           Control.Exception              (assert)
import           Control.Monad.ST
import           Data.Primitive.ByteArray
import           GHC.Stack
import           GHC.Word
import           GHC.Exts
import           Z.Data.Array
import           Z.Data.ASCII                   (isSpace)
import           Z.Data.Vector.Base
import           Z.Data.Vector.Search
import           Prelude                        hiding (concat, concatMap,
                                                elem, notElem, null, length, map,
                                                foldl, foldl1, foldr, foldr1,
                                                maximum, minimum, product, sum,
                                                all, any, replicate, traverse,
                                                head, tail, init, last,
                                                take, drop, splitAt,
                                                takeWhile, dropWhile,
                                                break, span, reverse,
                                                words, lines, unwords, unlines)
import qualified Data.List                      as List
import           System.IO.Unsafe               (unsafeDupablePerformIO)

--------------------------------------------------------------------------------
-- Slice
--
-- | /O(n)/ 'cons' is analogous to (:) for lists, but of different
-- complexity, as it requires making a copy.
cons :: Vec v a => a -> v a -> v a
{-# INLINE cons #-}
cons :: forall (v :: * -> *) a. Vec v a => a -> v a -> v a
cons a
x (Vec IArray v a
arr Int
s Int
l) = forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create (Int
lforall a. Num a => a -> a -> a
+Int
1) forall a b. (a -> b) -> a -> b
$ \ MArr (IArray v) s a
marr ->
    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
0 a
x forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> arr a -> Int -> Int -> m ()
copyArr MArr (IArray v) s a
marr Int
1 IArray v a
arr Int
s Int
l

-- | /O(n)/ Append a byte to the end of a vector
snoc :: Vec v a => v a -> a -> v a
{-# INLINE snoc #-}
snoc :: forall (v :: * -> *) a. Vec v a => v a -> a -> v a
snoc (Vec IArray v a
arr Int
s Int
l) a
x = forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create (Int
lforall a. Num a => a -> a -> a
+Int
1) forall a b. (a -> b) -> a -> b
$ \ MArr (IArray v) s a
marr ->
    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> arr a -> Int -> Int -> m ()
copyArr MArr (IArray v) s a
marr Int
0 IArray v a
arr Int
s Int
l forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
l a
x

-- | /O(1)/ Extract the head and tail of a vector, return 'Nothing'
-- if it is empty.
uncons :: Vec v a => v a -> Maybe (a, v a)
{-# INLINE uncons #-}
uncons :: forall (v :: * -> *) a. Vec v a => v a -> Maybe (a, v a)
uncons (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = forall a. Maybe a
Nothing
    | Bool
otherwise = let !v :: v a
v = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
1) (Int
lforall a. Num a => a -> a -> a
-Int
1)
                  in case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
s of (# a
x #) -> forall a. a -> Maybe a
Just (a
x ,v a
v)

-- | /O(1)/ Extract the init and last of a vector, return 'Nothing'
-- if vector is empty.
unsnoc :: Vec v a => v a -> Maybe (v a, a)
{-# INLINE unsnoc #-}
unsnoc :: forall (v :: * -> *) a. Vec v a => v a -> Maybe (v a, a)
unsnoc (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = forall a. Maybe a
Nothing
    | Bool
otherwise = let !v :: v a
v = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s (Int
lforall a. Num a => a -> a -> a
-Int
1)
                  in case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
lforall a. Num a => a -> a -> a
-Int
1) of (# a
x #) -> forall a. a -> Maybe a
Just (v a
v, a
x)

-- | /O(1)/ Extract the first element of a vector.
headMaybe :: Vec v a => v a -> Maybe a
{-# INLINE headMaybe #-}
headMaybe :: forall (v :: * -> *) a. Vec v a => v a -> Maybe a
headMaybe (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = forall a. Maybe a
Nothing
    | Bool
otherwise = forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray v a
arr Int
s

-- | /O(1)/ Extract the elements after the head of a vector.
--
-- NOTE: 'tailMayEmpty' return empty vector in the case of an empty vector.
tailMayEmpty :: Vec v a => v a -> v a
{-# INLINE tailMayEmpty #-}
tailMayEmpty :: forall (v :: * -> *) a. Vec v a => v a -> v a
tailMayEmpty (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = forall (v :: * -> *) a. Vec v a => v a
empty
    | Bool
otherwise = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
1) (Int
lforall a. Num a => a -> a -> a
-Int
1)

-- | /O(1)/ Extract the last element of a vector.
lastMaybe :: Vec v a => v a -> Maybe a
{-# INLINE lastMaybe #-}
lastMaybe :: forall (v :: * -> *) a. Vec v a => v a -> Maybe a
lastMaybe (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = forall a. Maybe a
Nothing
    | Bool
otherwise = forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
lforall a. Num a => a -> a -> a
-Int
1)

-- | /O(1)/ Extract the elements before of the last one.
--
-- NOTE: 'initMayEmpty' return empty vector in the case of an empty vector.
initMayEmpty :: Vec v a => v a -> v a
{-# INLINE initMayEmpty #-}
initMayEmpty :: forall (v :: * -> *) a. Vec v a => v a -> v a
initMayEmpty (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = forall (v :: * -> *) a. Vec v a => v a
empty
    | Bool
otherwise = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s (Int
lforall a. Num a => a -> a -> a
-Int
1)

-- | /O(n)/ Return all initial segments of the given vector, empty first.
inits :: Vec v a => v a -> [v a]
{-# INLINE inits #-}
inits :: forall (v :: * -> *) a. Vec v a => v a -> [v a]
inits (Vec IArray v a
arr Int
s Int
l) =  [forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr Int
s Int
n | Int
n <- [Int
0..Int
l]]

-- | /O(n)/ Return all final segments of the given vector, whole vector first.
tails :: Vec v a => v a -> [v a]
{-# INLINE tails #-}
tails :: forall (v :: * -> *) a. Vec v a => v a -> [v a]
tails (Vec IArray v a
arr Int
s Int
l) = [forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
n) (Int
lforall a. Num a => a -> a -> a
-Int
n) | Int
n <- [Int
0..Int
l]]

-- | /O(1)/ 'take' @n@, applied to a vector @xs@, returns the prefix
-- of @xs@ of length @n@, or @xs@ itself if @n > 'length' xs@.
take :: Vec v a => Int -> v a -> v a
{-# INLINE take #-}
take :: forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
take Int
n v :: v a
v@(Vec IArray v a
arr Int
s Int
l)
    | Int
n forall a. Ord a => a -> a -> Bool
<= Int
0    = forall (v :: * -> *) a. Vec v a => v a
empty
    | Int
n forall a. Ord a => a -> a -> Bool
>= Int
l    = v a
v
    | Bool
otherwise = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s Int
n

-- | /O(1)/ 'takeR' @n@, applied to a vector @xs@, returns the suffix
-- of @xs@ of length @n@, or @xs@ itself if @n > 'length' xs@.
takeR :: Vec v a => Int -> v a -> v a
{-# INLINE takeR #-}
takeR :: forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
takeR Int
n v :: v a
v@(Vec IArray v a
arr Int
s Int
l)
    | Int
n forall a. Ord a => a -> a -> Bool
<= Int
0    = forall (v :: * -> *) a. Vec v a => v a
empty
    | Int
n forall a. Ord a => a -> a -> Bool
>= Int
l    = v a
v
    | Bool
otherwise = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
lforall a. Num a => a -> a -> a
-Int
n) Int
n

-- | /O(1)/ 'drop' @n xs@ returns the suffix of @xs@ after the first @n@
-- elements, or @[]@ if @n > 'length' xs@.
drop :: Vec v a => Int -> v a -> v a
{-# INLINE drop #-}
drop :: forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
drop Int
n v :: v a
v@(Vec IArray v a
arr Int
s Int
l)
    | Int
n forall a. Ord a => a -> a -> Bool
<= Int
0    = v a
v
    | Int
n forall a. Ord a => a -> a -> Bool
>= Int
l    = forall (v :: * -> *) a. Vec v a => v a
empty
    | Bool
otherwise = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
n) (Int
lforall a. Num a => a -> a -> a
-Int
n)

-- | /O(1)/ 'dropR' @n xs@ returns the prefix of @xs@ before the last @n@
-- elements, or @[]@ if @n > 'length' xs@.
dropR :: Vec v a => Int -> v a -> v a
{-# INLINE dropR #-}
dropR :: forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
dropR Int
n v :: v a
v@(Vec IArray v a
arr Int
s Int
l)
    | Int
n forall a. Ord a => a -> a -> Bool
<= Int
0    = v a
v
    | Int
n forall a. Ord a => a -> a -> Bool
>= Int
l    = forall (v :: * -> *) a. Vec v a => v a
empty
    | Bool
otherwise = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s (Int
lforall a. Num a => a -> a -> a
-Int
n)

-- | /O(1)/ Extract a sub-range vector with give start index and length.
--
-- This function is a total function just like 'take/drop', index/length
-- exceeds range will be ingored, e.g.
--
-- @
-- slice 1 3 "hello"   == "ell"
-- slice -1 -1 "hello" == ""
-- slice -2 2 "hello"  == ""
-- slice 2 10 "hello"  == "llo"
-- @
--
-- This holds for all x y: @slice x y vs == drop x . take (x+y) vs@
slice :: Vec v a => Int     -- ^ slice beginning index
                 -> Int     -- ^ slice length
                 -> v a -> v a
{-# INLINE slice #-}
slice :: forall (v :: * -> *) a. Vec v a => Int -> Int -> v a -> v a
slice Int
x Int
y = forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
drop Int
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
take (Int
xforall a. Num a => a -> a -> a
+Int
y)

-- | /O(1)/ 'splitAt' @n xs@ is equivalent to @('take' n xs, 'drop' n xs)@.
splitAt :: Vec v a => Int -> v a -> (v a, v a)
{-# INLINE splitAt #-}
splitAt :: forall (v :: * -> *) a. Vec v a => Int -> v a -> (v a, v a)
splitAt Int
z (Vec IArray v a
arr Int
s Int
l) = let !v1 :: v a
v1 = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s Int
z'
                              !v2 :: v a
v2 = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
z') (Int
lforall a. Num a => a -> a -> a
-Int
z')
                          in (v a
v1, v a
v2)
  where z' :: Int
z' = Int -> Int -> Int -> Int
rangeCut Int
z Int
0 Int
l

-- | /O(n)/ Applied to a predicate @p@ and a vector @vs@,
-- returns the longest prefix (possibly empty) of @vs@ of elements that
-- satisfy @p@.
takeWhile :: Vec v a => (a -> Bool) -> v a -> v a
{-# INLINE [1] takeWhile #-}
{-# RULES "takeWhile/breakEq1" forall w. takeWhile (w `neWord8`) = fst . break (w `eqWord8`) #-}
{-# RULES "takeWhile/breakEq2" forall w. takeWhile (`neWord8` w) = fst . break (`eqWord8` w) #-}
takeWhile :: forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> v a
takeWhile a -> Bool
f v :: v a
v@(Vec IArray v a
arr Int
s Int
_) =
    case forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Int
findIndex (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
f) v a
v of
        Int
0  -> forall (v :: * -> *) a. Vec v a => v a
empty
        Int
i  -> forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr Int
s Int
i

-- | /O(n)/ Applied to a predicate @p@ and a vector @vs@,
-- returns the longest suffix (possibly empty) of @vs@ of elements that
-- satisfy @p@.
takeWhileR :: Vec v a => (a -> Bool) -> v a -> v a
{-# INLINE [1] takeWhileR #-}
{-# RULES "takeWhileR/breakREq1" forall w. takeWhileR (w `neWord8`) = snd . breakR (w `eqWord8`) #-}
{-# RULES "takeWhileR/breakREq2" forall w. takeWhileR (`neWord8` w) = snd . breakR (`eqWord8` w) #-}
takeWhileR :: forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> v a
takeWhileR a -> Bool
f v :: v a
v@(Vec IArray v a
arr Int
s Int
l) =
    case forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Int
findIndexR (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
f) v a
v of
        -1 -> v a
v
        Int
i  -> forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
iforall a. Num a => a -> a -> a
+Int
1) (Int
lforall a. Num a => a -> a -> a
-Int
iforall a. Num a => a -> a -> a
-Int
1)

-- | /O(n)/ Applied to a predicate @p@ and a vector @vs@,
-- returns the suffix (possibly empty) remaining after 'takeWhile' @p vs@.
dropWhile :: Vec v a => (a -> Bool) -> v a -> v a
{-# INLINE [1] dropWhile #-}
{-# RULES "dropWhile/breakEq1" forall w. dropWhile (w `neWord8`) = snd . break (w `eqWord8`) #-}
{-# RULES "dropWhile/breakEq2" forall w. dropWhile (`neWord8` w) = snd . break (`eqWord8` w) #-}
dropWhile :: forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> v a
dropWhile a -> Bool
f v :: v a
v@(Vec IArray v a
arr Int
s Int
l) =
    case forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Int
findIndex (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
f) v a
v of
        Int
i | Int
i forall a. Eq a => a -> a -> Bool
== Int
l     -> forall (v :: * -> *) a. Vec v a => v a
empty
          | Bool
otherwise  -> forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
i) (Int
lforall a. Num a => a -> a -> a
-Int
i)

-- | /O(n)/ Applied to a predicate @p@ and a vector @vs@,
-- returns the prefix (possibly empty) remaining before 'takeWhileR' @p vs@.
dropWhileR :: Vec v a => (a -> Bool) -> v a -> v a
{-# INLINE [1] dropWhileR #-}
{-# RULES "dropWhileR/breakEq1" forall w. dropWhileR (w `neWord8`) = fst . breakR (w `eqWord8`) #-}
{-# RULES "dropWhileR/breakEq2" forall w. dropWhileR (`neWord8` w) = fst . breakR (`eqWord8` w) #-}
dropWhileR :: forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> v a
dropWhileR a -> Bool
f v :: v a
v@(Vec IArray v a
arr Int
s Int
_) =
    case forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Int
findIndexR (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
f) v a
v of
        -1 -> forall (v :: * -> *) a. Vec v a => v a
empty
        Int
i  -> forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr Int
s (Int
iforall a. Num a => a -> a -> a
+Int
1)

-- | /O(n)/ @dropAround f = dropWhile f . dropWhileR f@
dropAround :: Vec v a => (a -> Bool) -> v a -> v a
{-# INLINE dropAround #-}
dropAround :: forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> v a
dropAround a -> Bool
f = forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> v a
dropWhile a -> Bool
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> v a
dropWhileR a -> Bool
f


-- | /O(n)/ Split the vector into the longest prefix of elements that do not satisfy the predicate and the rest without copying.
--
-- @break (==x)@ will be rewritten using a @memchr@.
break :: Vec v a => (a -> Bool) -> v a -> (v a, v a)
{-# INLINE break #-}
break :: forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> (v a, v a)
break a -> Bool
f vs :: v a
vs@(Vec IArray v a
arr Int
s Int
l) =
    let !n :: Int
n =  forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Int
findIndex a -> Bool
f v a
vs
        !v1 :: v a
v1 = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr Int
s Int
n
        !v2 :: v a
v2 = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
n) (Int
lforall a. Num a => a -> a -> a
-Int
n)
    in (v a
v1, v a
v2)

-- | /O(n)/ Split the vector into the longest prefix of elements that satisfy the predicate and the rest without copying.
--
-- @span (/=x)@ will be rewritten using a @memchr@.
span :: Vec v a => (a -> Bool) -> v a -> (v a, v a)
{-# INLINE [1] span #-}
{-# RULES "spanNEq/breakEq1" forall w. span (w `neWord8`) = break (w `eqWord8`) #-}
{-# RULES "spanNEq/breakEq2" forall w. span (`neWord8` w) = break (`eqWord8` w) #-}
span :: forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> (v a, v a)
span a -> Bool
f = forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> (v a, v a)
break (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
f)

-- | 'breakR' behaves like 'break' but apply predictor from the end of the vector.
--
-- @breakR p == spanR (not.p)@
breakR :: Vec v a => (a -> Bool) -> v a -> (v a, v a)
{-# INLINE breakR #-}
breakR :: forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> (v a, v a)
breakR a -> Bool
f vs :: v a
vs@(Vec IArray v a
arr Int
s Int
l) =
    let !n :: Int
n = forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Int
findIndexR a -> Bool
f v a
vs
        !v1 :: v a
v1 = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr Int
s (Int
nforall a. Num a => a -> a -> a
+Int
1)
        !v2 :: v a
v2 = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
nforall a. Num a => a -> a -> a
+Int
1) (Int
lforall a. Num a => a -> a -> a
-Int
1forall a. Num a => a -> a -> a
-Int
n)
    in (v a
v1, v a
v2)

-- | 'spanR' behaves like 'span' but from the end of the vector.
spanR :: Vec v a => (a -> Bool) -> v a -> (v a, v a)
{-# INLINE [1]  spanR #-}
{-# RULES "spanNEq/breakREq1" forall w. spanR (w `neWord8`) = breakR (w `eqWord8`) #-}
{-# RULES "spanNEq/breakREq2" forall w. spanR (`neWord8` w) = breakR (`eqWord8` w) #-}
spanR :: forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> (v a, v a)
spanR a -> Bool
f = forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> (v a, v a)
breakR (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
f)

-- | Break a vector on a subvector, returning a pair of the part of the
-- vector prior to the match, and the rest of the vector, e.g.
--
-- > break "wor" "hello, world" = ("hello, ", "world")
--
breakOn :: (Vec v a, Eq a) => v a -> v a -> (v a, v a)
{-# INLINABLE breakOn #-}
breakOn :: forall (v :: * -> *) a. (Vec v a, Eq a) => v a -> v a -> (v a, v a)
breakOn v a
needle = \ haystack :: v a
haystack@(Vec IArray v a
arr Int
s Int
l) ->
    case v a -> Bool -> [Int]
search v a
haystack Bool
False of
        (Int
i:[Int]
_) -> let !v1 :: v a
v1 = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr Int
s Int
i
                     !v2 :: v a
v2 = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
i) (Int
lforall a. Num a => a -> a -> a
-Int
i)
                 in (v a
v1, v a
v2)
        [Int]
_     -> (v a
haystack, forall (v :: * -> *) a. Vec v a => v a
empty)
  where search :: v a -> Bool -> [Int]
search = forall (v :: * -> *) a.
(Vec v a, Eq a) =>
v a -> v a -> Bool -> [Int]
indices v a
needle


group :: (Vec v a, Eq a) => v a -> [v a]
{-# INLINABLE group #-}
group :: forall (v :: * -> *) a. (Vec v a, Eq a) => v a -> [v a]
group = forall (v :: * -> *) a. Vec v a => (a -> a -> Bool) -> v a -> [v a]
groupBy forall a. Eq a => a -> a -> Bool
(==)

groupBy :: forall v a. Vec v a =>  (a -> a -> Bool) -> v a -> [v a]
{-# INLINABLE groupBy #-}
groupBy :: forall (v :: * -> *) a. Vec v a => (a -> a -> Bool) -> v a -> [v a]
groupBy a -> a -> Bool
f (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Eq a => a -> a -> Bool
== Int
0    = []
    | Bool
otherwise = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr Int
s Int
n forall a. a -> [a] -> [a]
: forall (v :: * -> *) a. Vec v a => (a -> a -> Bool) -> v a -> [v a]
groupBy a -> a -> Bool
f (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
n) (Int
lforall a. Num a => a -> a -> a
-Int
n))
  where
    n :: Int
n = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
s of
        (# a
x #) -> Int
1 forall a. Num a => a -> a -> a
+ forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Int
findIndex @v (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a -> Bool
f a
x) (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
1) (Int
lforall a. Num a => a -> a -> a
-Int
1))

-- | /O(n)/ The 'stripPrefix' function takes two vectors and returns 'Just'
-- the remainder of the second iff the first is its prefix, and otherwise
-- 'Nothing'.
--
stripPrefix :: (Vec v a, Eq (v a))
            => v a      -- ^ the prefix to be tested
            -> v a -> Maybe (v a)
{-# INLINABLE stripPrefix #-}
stripPrefix :: forall (v :: * -> *) a.
(Vec v a, Eq (v a)) =>
v a -> v a -> Maybe (v a)
stripPrefix v1 :: v a
v1@(Vec IArray v a
_ Int
_ Int
l1) v2 :: v a
v2@(Vec IArray v a
arr Int
s Int
l2)
   | v a
v1 forall (v :: * -> *) a. (Vec v a, Eq (v a)) => v a -> v a -> Bool
`isPrefixOf` v a
v2 = forall a. a -> Maybe a
Just (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
l1) (Int
l2forall a. Num a => a -> a -> a
-Int
l1))
   | Bool
otherwise = forall a. Maybe a
Nothing

-- | The 'isPrefix' function returns 'True' if the first argument is a prefix of the second.
isPrefixOf :: forall v a. (Vec v a, Eq (v a))
           => v a       -- ^ the prefix to be tested
           -> v a -> Bool
{-# INLINABLE isPrefixOf #-}
isPrefixOf :: forall (v :: * -> *) a. (Vec v a, Eq (v a)) => v a -> v a -> Bool
isPrefixOf (Vec IArray v a
arrA Int
sA Int
lA) (Vec IArray v a
arrB Int
sB Int
lB)
    | Int
lA forall a. Eq a => a -> a -> Bool
== Int
0 = Bool
True
    | Int
lA forall a. Ord a => a -> a -> Bool
> Int
lB = Bool
False
    | Bool
otherwise = forall a. Eq a => a -> a -> Bool
(==) @(v a) (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arrA Int
sA Int
lA) (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arrB Int
sB Int
lA)

-- | /O(n)/ Find the longest non-empty common prefix of two strings
-- and return it, along with the suffixes of each string at which they
-- no longer match. e.g.
--
-- >>> commonPrefix "foobar" "fooquux"
-- ("foo","bar","quux")
--
-- >>> commonPrefix "veeble" "fetzer"
-- ("","veeble","fetzer")
commonPrefix :: (Vec v a, Eq a) => v a -> v a -> (v a, v a, v a)
{-# INLINABLE commonPrefix #-}
commonPrefix :: forall (v :: * -> *) a.
(Vec v a, Eq a) =>
v a -> v a -> (v a, v a, v a)
commonPrefix vA :: v a
vA@(Vec IArray v a
arrA Int
sA Int
lA) vB :: v a
vB@(Vec IArray v a
arrB Int
sB Int
lB) = Int -> Int -> (v a, v a, v a)
go Int
sA Int
sB
  where
    !endA :: Int
endA = Int
sA forall a. Num a => a -> a -> a
+ Int
lA
    !endB :: Int
endB = Int
sB forall a. Num a => a -> a -> a
+ Int
lB
    go :: Int -> Int -> (v a, v a, v a)
go !Int
i !Int
j | Int
i forall a. Ord a => a -> a -> Bool
>= Int
endA = let !vB' :: v a
vB' = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arrB (Int
sBforall a. Num a => a -> a -> a
+Int
iforall a. Num a => a -> a -> a
-Int
sA) (Int
lBforall a. Num a => a -> a -> a
-Int
iforall a. Num a => a -> a -> a
+Int
sA) in (v a
vA, forall (v :: * -> *) a. Vec v a => v a
empty, v a
vB')
             | Int
j forall a. Ord a => a -> a -> Bool
>= Int
endB = let !vA' :: v a
vA' = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arrA (Int
sAforall a. Num a => a -> a -> a
+Int
jforall a. Num a => a -> a -> a
-Int
sB) (Int
lAforall a. Num a => a -> a -> a
-Int
jforall a. Num a => a -> a -> a
+Int
sB) in (v a
vB, v a
vA', forall (v :: * -> *) a. Vec v a => v a
empty)
             | forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> a
indexArr IArray v a
arrA Int
i forall a. Eq a => a -> a -> Bool
== forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> a
indexArr IArray v a
arrB Int
j = Int -> Int -> (v a, v a, v a)
go (Int
iforall a. Num a => a -> a -> a
+Int
1) (Int
jforall a. Num a => a -> a -> a
+Int
1)
             | Bool
otherwise =
                let !vB' :: v a
vB' = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arrB (Int
sBforall a. Num a => a -> a -> a
+Int
iforall a. Num a => a -> a -> a
-Int
sA) (Int
lBforall a. Num a => a -> a -> a
-Int
iforall a. Num a => a -> a -> a
+Int
sA)
                    !vA' :: v a
vA' = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arrA (Int
sAforall a. Num a => a -> a -> a
+Int
jforall a. Num a => a -> a -> a
-Int
sB) (Int
lAforall a. Num a => a -> a -> a
-Int
jforall a. Num a => a -> a -> a
+Int
sB)
                    !vC :: v a
vC  = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arrA Int
sA (Int
iforall a. Num a => a -> a -> a
-Int
sA)
                in (v a
vC, v a
vA', v a
vB')

-- | O(n) The 'stripSuffix' function takes two vectors and returns Just the remainder of the second iff the first is its suffix, and otherwise Nothing.
stripSuffix :: (Vec v a, Eq (v a)) => v a -> v a -> Maybe (v a)
{-# INLINABLE stripSuffix #-}
stripSuffix :: forall (v :: * -> *) a.
(Vec v a, Eq (v a)) =>
v a -> v a -> Maybe (v a)
stripSuffix v1 :: v a
v1@(Vec IArray v a
_ Int
_ Int
l1) v2 :: v a
v2@(Vec IArray v a
arr Int
s Int
l2)
   | v a
v1 forall (v :: * -> *) a. (Vec v a, Eq (v a)) => v a -> v a -> Bool
`isSuffixOf` v a
v2 = forall a. a -> Maybe a
Just (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr Int
s (Int
l2forall a. Num a => a -> a -> a
-Int
l1))
   | Bool
otherwise = forall a. Maybe a
Nothing

-- | /O(n)/ The 'isSuffixOf' function takes two vectors and returns 'True'
-- if the first is a suffix of the second.
isSuffixOf :: forall v a. (Vec v a, Eq (v a)) => v a -> v a -> Bool
{-# INLINABLE isSuffixOf #-}
isSuffixOf :: forall (v :: * -> *) a. (Vec v a, Eq (v a)) => v a -> v a -> Bool
isSuffixOf (Vec IArray v a
arrA Int
sA Int
lA) (Vec IArray v a
arrB Int
sB Int
lB)
    | Int
lA forall a. Eq a => a -> a -> Bool
== Int
0 = Bool
True
    | Int
lA forall a. Ord a => a -> a -> Bool
> Int
lB = Bool
False
    | Bool
otherwise = forall a. Eq a => a -> a -> Bool
(==) @(v a) (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arrA Int
sA Int
lA) (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arrB (Int
sBforall a. Num a => a -> a -> a
+Int
lBforall a. Num a => a -> a -> a
-Int
lA) Int
lA)

-- | Check whether one vector is a subvector of another.
--
-- @needle `isInfixOf` haystack === null haystack || indices needle haystake /= []@.
isInfixOf :: (Vec v a, Eq a) => v a -> v a -> Bool
{-# INLINABLE isInfixOf #-}
isInfixOf :: forall (v :: * -> *) a. (Vec v a, Eq a) => v a -> v a -> Bool
isInfixOf v a
needle = \ v a
haystack -> forall (v :: * -> *) a. Vec v a => v a -> Bool
null v a
haystack Bool -> Bool -> Bool
|| v a -> Bool -> [Int]
search v a
haystack Bool
False forall a. Eq a => a -> a -> Bool
/= []
  where search :: v a -> Bool -> [Int]
search = forall (v :: * -> *) a.
(Vec v a, Eq a) =>
v a -> v a -> Bool -> [Int]
indices v a
needle

-- | /O(n)/ Break a vector into pieces separated by the delimiter element
-- consuming the delimiter. I.e.
--
-- > split '\n' "a\nb\nd\ne" == ["a","b","d","e"]
-- > split 'a'  "aXaXaXa"    == ["","X","X","X",""]
-- > split 'x'  "x"          == ["",""]
--
-- and
--
-- > intercalate [c] . split c == id
-- > split == splitWith . (==)
--
-- NOTE, this function behavior different with bytestring's. see
-- <https://github.com/haskell/bytestring/issues/56 #56>.
split :: (Vec v a, Eq a) => a -> v a -> [v a]
{-# INLINABLE split #-}
split :: forall (v :: * -> *) a. (Vec v a, Eq a) => a -> v a -> [v a]
split a
x = forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> [v a]
splitWith (forall a. Eq a => a -> a -> Bool
==a
x)

-- | /O(m+n)/ Break haystack into pieces separated by needle.
--
-- Note: An empty needle will essentially split haystack element
-- by element.
--
-- Examples:
--
-- >>> splitOn "\r\n" "a\r\nb\r\nd\r\ne"
-- ["a","b","d","e"]
--
-- >>> splitOn "aaa"  "aaaXaaaXaaaXaaa"
-- ["","X","X","X",""]
--
-- >>> splitOn "x"  "x"
-- ["",""]
--
-- and
--
-- > intercalate s . splitOn s         == id
-- > splitOn (singleton c)             == split (==c)
splitOn :: (Vec v a, Eq a) => v a -> v a -> [v a]
{-# INLINABLE splitOn #-}
splitOn :: forall (v :: * -> *) a. (Vec v a, Eq a) => v a -> v a -> [v a]
splitOn v a
needle = v a -> [v a]
splitBySearch
  where
    splitBySearch :: v a -> [v a]
splitBySearch haystack :: v a
haystack@(Vec IArray v a
arr Int
s Int
l) = Int -> [Int] -> [v a]
go Int
s (v a -> Bool -> [Int]
search v a
haystack Bool
False)
      where
        !l' :: Int
l' = forall (v :: * -> *) a. Vec v a => v a -> Int
length v a
needle
        !end :: Int
end = Int
sforall a. Num a => a -> a -> a
+Int
l
        search :: v a -> Bool -> [Int]
search = forall (v :: * -> *) a.
(Vec v a, Eq a) =>
v a -> v a -> Bool -> [Int]
indices v a
needle
        go :: Int -> [Int] -> [v a]
go !Int
s' (Int
i:[Int]
is) = let !v :: v a
v = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s' (Int
iforall a. Num a => a -> a -> a
+Int
sforall a. Num a => a -> a -> a
-Int
s')
                               in v a
v forall a. a -> [a] -> [a]
: Int -> [Int] -> [v a]
go (Int
iforall a. Num a => a -> a -> a
+Int
l') [Int]
is
        go !Int
s' [Int]
_      = let !v :: v a
v = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s' (Int
endforall a. Num a => a -> a -> a
-Int
s') in [v a
v]

-- | /O(n)/ Splits a vector into components delimited by
-- separators, where the predicate returns True for a separator element.
-- The resulting components do not contain the separators.  Two adjacent
-- separators result in an empty component in the output.  eg.
--
-- > splitWith (=='a') "aabbaca" == ["","","bb","c",""]
-- > splitWith (=='a') []        == [""]
--
-- NOTE, this function behavior different with bytestring's. see
-- <https://github.com/haskell/bytestring/issues/56 #56>.
splitWith :: Vec v a => (a -> Bool) -> v a -> [v a]
{-# INLINABLE splitWith #-}
splitWith :: forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> [v a]
splitWith a -> Bool
f = v a -> [v a]
go
  where
    go :: v a -> [v a]
go v :: v a
v@(Vec IArray v a
_ Int
_ Int
l)
        | Int
l forall a. Eq a => a -> a -> Bool
== Int
0    = [forall (v :: * -> *) a. Vec v a => v a
empty]
        | Bool
otherwise =
            let n :: Int
n = forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Int
findIndex a -> Bool
f v a
v
            in if Int
n forall a. Eq a => a -> a -> Bool
== Int
l
                then [v a
v]
                else forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
unsafeTake Int
n v a
v forall a. a -> [a] -> [a]
: v a -> [v a]
go (forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
unsafeDrop (Int
nforall a. Num a => a -> a -> a
+Int
1) v a
v)

-- | /O(n)/ Breaks a 'Bytes' up into a list of words, delimited by ascii space.
words ::  Bytes -> [Bytes]
{-# INLINABLE words #-}
words :: Bytes -> [Bytes]
words (Vec IArray PrimVector Word8
arr Int
s Int
l) = Int -> Int -> [Bytes]
go Int
s Int
s
  where
    !end :: Int
end = Int
s forall a. Num a => a -> a -> a
+ Int
l
    go :: Int -> Int -> [Bytes]
    go :: Int -> Int -> [Bytes]
go !Int
s' !Int
i | Int
i forall a. Ord a => a -> a -> Bool
>= Int
end =
                    if Int
s' forall a. Eq a => a -> a -> Bool
== Int
end
                    then []
                    else let !v :: Bytes
v = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray PrimVector Word8
arr Int
s' (Int
endforall a. Num a => a -> a -> a
-Int
s') in [Bytes
v]
              | Word8 -> Bool
isSpace (forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> a
indexArr IArray PrimVector Word8
arr Int
i) =
                    if Int
s' forall a. Eq a => a -> a -> Bool
== Int
i
                    then Int -> Int -> [Bytes]
go (Int
iforall a. Num a => a -> a -> a
+Int
1) (Int
iforall a. Num a => a -> a -> a
+Int
1)
                    else
                    let !v :: Bytes
v = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray PrimVector Word8
arr Int
s' (Int
iforall a. Num a => a -> a -> a
-Int
s') in Bytes
v forall a. a -> [a] -> [a]
: Int -> Int -> [Bytes]
go (Int
iforall a. Num a => a -> a -> a
+Int
1) (Int
iforall a. Num a => a -> a -> a
+Int
1)
              | Bool
otherwise = Int -> Int -> [Bytes]
go Int
s' (Int
iforall a. Num a => a -> a -> a
+Int
1)

-- | /O(n)/ Breaks a 'Bytes' up into a list of lines, delimited by ascii @\n@,
-- The resulting strings do not contain newlines.
--
--  Note that it __does not__ regard CR (@'\\r'@) as a newline character.
lines ::  Bytes -> [Bytes]
{-# INLINABLE lines #-}
lines :: Bytes -> [Bytes]
lines Bytes
v
    | forall (v :: * -> *) a. Vec v a => v a -> Bool
null Bytes
v = []
    | Bool
otherwise = case forall (v :: * -> *) a. (Vec v a, Eq a) => a -> v a -> Maybe Int
elemIndex Word8
10 Bytes
v of
         Maybe Int
Nothing -> [Bytes
v]
         Just Int
n  -> forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
unsafeTake Int
n Bytes
v forall a. a -> [a] -> [a]
: Bytes -> [Bytes]
lines (forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
unsafeDrop (Int
nforall a. Num a => a -> a -> a
+Int
1) Bytes
v)

-- | /O(n)/ Joins words with ascii space.
unwords :: [Bytes] -> Bytes
{-# INLINABLE unwords #-}
unwords :: [Bytes] -> Bytes
unwords = forall (v :: * -> *) a. Vec v a => a -> [v a] -> v a
intercalateElem Word8
32

-- | /O(n)/ Joins lines with ascii @\n@.
--
-- NOTE: This functions is different from 'Prelude.unlines', it DOES NOT add a trailing @\n@.
unlines :: [Bytes] -> Bytes
{-# INLINABLE unlines #-}
unlines :: [Bytes] -> Bytes
unlines = forall (v :: * -> *) a. Vec v a => a -> [v a] -> v a
intercalateElem Word8
10

-- | Add padding to the left so that the whole vector's length is at least n.
padLeft :: Vec v a => Int -> a -> v a -> v a
{-# INLINABLE padLeft #-}
padLeft :: forall (v :: * -> *) a. Vec v a => Int -> a -> v a -> v a
padLeft Int
n a
x v :: v a
v@(Vec IArray v a
arr Int
s Int
l) | Int
n forall a. Ord a => a -> a -> Bool
<= Int
l = v a
v
                            | Bool
otherwise = forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create Int
n (\ MArr (IArray v) s a
marr -> do
                                    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> Int -> a -> m ()
setArr MArr (IArray v) s a
marr Int
0 (Int
nforall a. Num a => a -> a -> a
-Int
l) a
x
                                    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> arr a -> Int -> Int -> m ()
copyArr MArr (IArray v) s a
marr (Int
nforall a. Num a => a -> a -> a
-Int
l) IArray v a
arr Int
s Int
l)

-- | Add padding to the right so that the whole vector's length is at least n.
padRight :: Vec v a => Int -> a -> v a -> v a
{-# INLINABLE padRight #-}
padRight :: forall (v :: * -> *) a. Vec v a => Int -> a -> v a -> v a
padRight Int
n a
x v :: v a
v@(Vec IArray v a
arr Int
s Int
l) | Int
n forall a. Ord a => a -> a -> Bool
<= Int
l = v a
v
                             | Bool
otherwise = forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create Int
n (\ MArr (IArray v) s a
marr -> do
                                    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> arr a -> Int -> Int -> m ()
copyArr MArr (IArray v) s a
marr Int
0 IArray v a
arr Int
s Int
l
                                    forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> Int -> a -> m ()
setArr MArr (IArray v) s a
marr Int
l (Int
nforall a. Num a => a -> a -> a
-Int
l) a
x)

--------------------------------------------------------------------------------
-- Transform

-- | /O(n)/ 'reverse' @vs@ efficiently returns the elements of @xs@ in reverse order.
--
reverse :: forall v a. (Vec v a) => v a -> v a
{-# INLINABLE reverse #-}
reverse :: forall (v :: * -> *) a. Vec v a => v a -> v a
reverse (Vec IArray v a
arr Int
s Int
l) = forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create Int
l (forall s. Int -> Int -> MArr (IArray v) s a -> ST s ()
go Int
s (Int
lforall a. Num a => a -> a -> a
-Int
1))
  where
    go :: Int -> Int -> MArr (IArray v) s a -> ST s ()
    go :: forall s. Int -> Int -> MArr (IArray v) s a -> ST s ()
go !Int
i !Int
j !MArr (IArray v) s a
marr | Int
j forall a. Ord a => a -> a -> Bool
< Int
0 = forall (m :: * -> *) a. Monad m => a -> m a
return ()
                   | Int
j forall a. Ord a => a -> a -> Bool
>= Int
3 = do  -- a bit of loop unrolling here
                        forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray v a
arr Int
i forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
j
                        forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray v a
arr (Int
iforall a. Num a => a -> a -> a
+Int
1) forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jforall a. Num a => a -> a -> a
-Int
1)
                        forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray v a
arr (Int
iforall a. Num a => a -> a -> a
+Int
2) forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jforall a. Num a => a -> a -> a
-Int
2)
                        forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray v a
arr (Int
iforall a. Num a => a -> a -> a
+Int
3) forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jforall a. Num a => a -> a -> a
-Int
3)
                        forall s. Int -> Int -> MArr (IArray v) s a -> ST s ()
go (Int
iforall a. Num a => a -> a -> a
+Int
4) (Int
jforall a. Num a => a -> a -> a
-Int
4) MArr (IArray v) s a
marr
                   | Bool
otherwise = do
                        forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray v a
arr Int
i forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
j
                        forall s. Int -> Int -> MArr (IArray v) s a -> ST s ()
go (Int
iforall a. Num a => a -> a -> a
+Int
1) (Int
jforall a. Num a => a -> a -> a
-Int
1) MArr (IArray v) s a
marr

-- | /O(n)/ The 'intersperse' function takes an element and a
-- vector and \`intersperses\' that element between the elements of
-- the vector.  It is analogous to the intersperse function on
-- Lists.
--
intersperse :: forall v a. Vec v a => a -> v a -> v a
{-# INLINE [1] intersperse #-}
{-# RULES "intersperse/Bytes" intersperse = intersperseBytes #-}
intersperse :: forall (v :: * -> *) a. Vec v a => a -> v a -> v a
intersperse a
x v :: v a
v@(Vec IArray v a
arr Int
s Int
l) | Int
l forall a. Ord a => a -> a -> Bool
<= Int
1 = v a
v
                              | Bool
otherwise = forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create (Int
2forall a. Num a => a -> a -> a
*Int
lforall a. Num a => a -> a -> a
-Int
1) (forall s. Int -> Int -> MArr (IArray v) s a -> ST s ()
go Int
s Int
0)
   where
    !end :: Int
end = Int
sforall a. Num a => a -> a -> a
+Int
lforall a. Num a => a -> a -> a
-Int
1
    go :: Int         -- the reading index of orginal bytes
       -> Int         -- the writing index of new buf
       -> MArr (IArray v) s a -- the new buf
       -> ST s ()
    go :: forall s. Int -> Int -> MArr (IArray v) s a -> ST s ()
go !Int
i !Int
j !MArr (IArray v) s a
marr
        | Int
i forall a. Ord a => a -> a -> Bool
>= Int
end = forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
j forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray v a
arr Int
i
        | Int
i forall a. Ord a => a -> a -> Bool
<= Int
end forall a. Num a => a -> a -> a
- Int
4 = do -- a bit of loop unrolling
            forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
j forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray v a
arr Int
i
            forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jforall a. Num a => a -> a -> a
+Int
1) a
x
            forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jforall a. Num a => a -> a -> a
+Int
2) forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray v a
arr (Int
iforall a. Num a => a -> a -> a
+Int
1)
            forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jforall a. Num a => a -> a -> a
+Int
3) a
x
            forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jforall a. Num a => a -> a -> a
+Int
4) forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray v a
arr (Int
iforall a. Num a => a -> a -> a
+Int
2)
            forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jforall a. Num a => a -> a -> a
+Int
5) a
x
            forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jforall a. Num a => a -> a -> a
+Int
6) forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray v a
arr (Int
iforall a. Num a => a -> a -> a
+Int
3)
            forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jforall a. Num a => a -> a -> a
+Int
7) a
x
            forall s. Int -> Int -> MArr (IArray v) s a -> ST s ()
go (Int
iforall a. Num a => a -> a -> a
+Int
4) (Int
jforall a. Num a => a -> a -> a
+Int
8) MArr (IArray v) s a
marr
        | Bool
otherwise = do
            forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
j forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray v a
arr Int
i
            forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jforall a. Num a => a -> a -> a
+Int
1) a
x
            forall s. Int -> Int -> MArr (IArray v) s a -> ST s ()
go (Int
iforall a. Num a => a -> a -> a
+Int
1) (Int
jforall a. Num a => a -> a -> a
+Int
2) MArr (IArray v) s a
marr

-- | /O(n)/ Special 'intersperse' for 'Bytes' using SIMD
intersperseBytes :: Word8 -> Bytes -> Bytes
{-# INLINABLE intersperseBytes #-}
intersperseBytes :: Word8 -> Bytes -> Bytes
intersperseBytes Word8
c v :: Bytes
v@(PrimVector (PrimArray ByteArray#
ba#) Int
offset Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
1 = Bytes
v
    | Bool
otherwise = forall a. IO a -> a
unsafeDupablePerformIO forall a b. (a -> b) -> a -> b
$ do
        mba :: MutableByteArray RealWorld
mba@(MutableByteArray MutableByteArray# RealWorld
mba#) <- forall (m :: * -> *).
PrimMonad m =>
Int -> m (MutableByteArray (PrimState m))
newByteArray Int
n
        MutableByteArray# RealWorld
-> ByteArray# -> Int -> Int -> Word8 -> IO ()
c_intersperse MutableByteArray# RealWorld
mba# ByteArray#
ba# Int
offset Int
l Word8
c
        (ByteArray ByteArray#
ba'#) <- forall (m :: * -> *).
PrimMonad m =>
MutableByteArray (PrimState m) -> m ByteArray
unsafeFreezeByteArray MutableByteArray RealWorld
mba
        forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. PrimArray a -> Int -> Int -> PrimVector a
PrimVector (forall a. ByteArray# -> PrimArray a
PrimArray ByteArray#
ba'#) Int
0 Int
n)
  where n :: Int
n = Int
2forall a. Num a => a -> a -> a
*Int
lforall a. Num a => a -> a -> a
-Int
1

-- | /O(n)/ The 'intercalate' function takes a vector and a list of
-- vectors and concatenates the list after interspersing the first
-- argument between each element of the list.
--
-- Note: 'intercalate' will force the entire vector list.
--
intercalate :: Vec v a => v a -> [v a] -> v a
{-# INLINABLE intercalate #-}
intercalate :: forall (v :: * -> *) a. Vec v a => v a -> [v a] -> v a
intercalate v a
s = forall (v :: * -> *) a. Vec v a => [v a] -> v a
concat forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. a -> [a] -> [a]
List.intersperse v a
s

-- | /O(n)/ An efficient way to join vector with an element.
--
intercalateElem :: forall v a. Vec v a => a -> [v a] -> v a
{-# INLINABLE intercalateElem #-}
intercalateElem :: forall (v :: * -> *) a. Vec v a => a -> [v a] -> v a
intercalateElem a
_ [] = forall (v :: * -> *) a. Vec v a => v a
empty
intercalateElem a
_ [v a
v] = v a
v
intercalateElem a
w [v a]
vs = forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create (forall {v :: * -> *} {a}. Vec v a => [v a] -> Int -> Int
len [v a]
vs Int
0) (forall s. Int -> [v a] -> MArr (IArray v) s a -> ST s ()
go Int
0 [v a]
vs)
  where
    len :: [v a] -> Int -> Int
len []             !Int
acc = Int
acc
    len [Vec IArray v a
_ Int
_ Int
l]    !Int
acc = Int
l forall a. Num a => a -> a -> a
+ Int
acc
    len (Vec IArray v a
_ Int
_ Int
l:[v a]
vs') !Int
acc = [v a] -> Int -> Int
len [v a]
vs' (Int
accforall a. Num a => a -> a -> a
+Int
lforall a. Num a => a -> a -> a
+Int
1)
    go :: forall s. Int -> [v a] -> MArr (IArray v) s a -> ST s ()
    go :: forall s. Int -> [v a] -> MArr (IArray v) s a -> ST s ()
go !Int
_ []               !MArr (IArray v) s a
_    = forall (m :: * -> *) a. Monad m => a -> m a
return ()
    go !Int
i (Vec IArray v a
arr Int
s Int
l:[]) !MArr (IArray v) s a
marr = forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> arr a -> Int -> Int -> m ()
copyArr MArr (IArray v) s a
marr Int
i IArray v a
arr Int
s Int
l
    go !Int
i (Vec IArray v a
arr Int
s Int
l:[v a]
vs') !MArr (IArray v) s a
marr = do
        let !i' :: Int
i' = Int
i forall a. Num a => a -> a -> a
+ Int
l
        forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> arr a -> Int -> Int -> m ()
copyArr MArr (IArray v) s a
marr Int
i IArray v a
arr Int
s Int
l
        forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
i' a
w
        forall s. Int -> [v a] -> MArr (IArray v) s a -> ST s ()
go (Int
i'forall a. Num a => a -> a -> a
+Int
1) [v a]
vs' MArr (IArray v) s a
marr

-- | The 'transpose' function transposes the rows and columns of its
-- vector argument.
--
transpose :: Vec v a => [v a] -> [v a]
{-# INLINABLE transpose #-}
transpose :: forall (v :: * -> *) a. Vec v a => [v a] -> [v a]
transpose [v a]
vs =
    forall a b. (a -> b) -> [a] -> [b]
List.map (forall (v :: * -> *) a. Vec v a => Int -> [a] -> v a
packN Int
n) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. [[a]] -> [[a]]
List.transpose forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
List.map forall (v :: * -> *) a. Vec v a => v a -> [a]
unpack forall a b. (a -> b) -> a -> b
$ [v a]
vs
  where n :: Int
n = forall (t :: * -> *) a. Foldable t => t a -> Int
List.length [v a]
vs

--------------------------------------------------------------------------------
--  Zipping

-- | 'zipWith'' zip two vector with a zipping function.
--
-- For example, @'zipWith' (+)@ is applied to two vector to produce
-- a vector of corresponding sums, the result will be evaluated strictly.
zipWith' :: forall v a u b w c. (Vec v a, Vec u b, Vec w c)
         => (a -> b -> c) -> v a -> u b -> w c
{-# INLINABLE zipWith' #-}
zipWith' :: forall (v :: * -> *) a (u :: * -> *) b (w :: * -> *) c.
(Vec v a, Vec u b, Vec w c) =>
(a -> b -> c) -> v a -> u b -> w c
zipWith' a -> b -> c
f (Vec IArray v a
arrA Int
sA Int
lA) (Vec IArray u b
arrB Int
sB Int
lB) = forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create Int
len (forall s. Int -> MArr (IArray w) s c -> ST s ()
go Int
0)
  where
    !len :: Int
len = forall a. Ord a => a -> a -> a
min Int
lA Int
lB
    go :: forall s. Int -> MArr (IArray w) s c -> ST s ()
    go :: forall s. Int -> MArr (IArray w) s c -> ST s ()
go !Int
i !MArr (IArray w) s c
marr
        | Int
i forall a. Ord a => a -> a -> Bool
>= Int
len = forall (m :: * -> *) a. Monad m => a -> m a
return ()
        | Bool
otherwise = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arrA (Int
iforall a. Num a => a -> a -> a
+Int
sA) of
             (# a
a #) -> case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray u b
arrB (Int
iforall a. Num a => a -> a -> a
+Int
sB) of
                 (# b
b #) -> do let !c :: c
c = a -> b -> c
f a
a b
b in forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray w) s c
marr Int
i c
c
                               forall s. Int -> MArr (IArray w) s c -> ST s ()
go (Int
iforall a. Num a => a -> a -> a
+Int
1) MArr (IArray w) s c
marr

-- | 'unzipWith'' disassemble a vector with a disassembling function,
--
-- The results inside tuple will be evaluated strictly.
unzipWith' :: forall v a u b w c. (Vec v a, Vec u b, Vec w c)
           => (a -> (b, c)) -> v a -> (u b, w c)
{-# INLINABLE unzipWith' #-}
unzipWith' :: forall (v :: * -> *) a (u :: * -> *) b (w :: * -> *) c.
(Vec v a, Vec u b, Vec w c) =>
(a -> (b, c)) -> v a -> (u b, w c)
unzipWith' a -> (b, c)
f (Vec IArray v a
arr Int
s Int
l) = forall (v :: * -> *) a (u :: * -> *) b.
(Vec v a, Vec u b, HasCallStack) =>
Int
-> Int
-> (forall s.
    MArr (IArray v) s a -> MArr (IArray u) s b -> ST s (Int, Int))
-> (v a, u b)
createN2 Int
l Int
l (forall s.
Int
-> MArr (IArray u) s b -> MArr (IArray w) s c -> ST s (Int, Int)
go Int
0)
  where
    go :: forall s. Int -> MArr (IArray u) s b -> MArr (IArray w) s c -> ST s (Int, Int)
    go :: forall s.
Int
-> MArr (IArray u) s b -> MArr (IArray w) s c -> ST s (Int, Int)
go !Int
i !MArr (IArray u) s b
marrB !MArr (IArray w) s c
marrC
        | Int
i forall a. Ord a => a -> a -> Bool
>= Int
l = forall (m :: * -> *) a. Monad m => a -> m a
return (Int
l,Int
l)
        | Bool
otherwise = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr (Int
iforall a. Num a => a -> a -> a
+Int
s) of
            (# a
a #) -> do let (!b
b, !c
c) = a -> (b, c)
f a
a
                          forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray u) s b
marrB Int
i b
b
                          forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray w) s c
marrC Int
i c
c
                          forall s.
Int
-> MArr (IArray u) s b -> MArr (IArray w) s c -> ST s (Int, Int)
go (Int
iforall a. Num a => a -> a -> a
+Int
1) MArr (IArray u) s b
marrB MArr (IArray w) s c
marrC

--------------------------------------------------------------------------------
-- Scans

-- | 'scanl'' is similar to 'foldl', but returns a list of successive
-- reduced values from the left.
--
-- > scanl' f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
--
-- Note that
--
-- > lastM (scanl' f z xs) == Just (foldl f z xs).
--
scanl' :: forall v u a b. (Vec v a, Vec u b) => (b -> a -> b) -> b -> v a -> u b
{-# INLINABLE scanl' #-}
scanl' :: forall (v :: * -> *) (u :: * -> *) a b.
(Vec v a, Vec u b) =>
(b -> a -> b) -> b -> v a -> u b
scanl' b -> a -> b
f b
z (Vec IArray v a
arr Int
s Int
l) =
    forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create (Int
lforall a. Num a => a -> a -> a
+Int
1) (\ MArr (IArray u) s b
marr -> forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray u) s b
marr Int
0 b
z forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> forall s. b -> Int -> Int -> MArr (IArray u) s b -> ST s ()
go b
z Int
s Int
1 MArr (IArray u) s b
marr)
  where
    go :: b  -> Int -> Int -> MArr (IArray u) s b -> ST s ()
    go :: forall s. b -> Int -> Int -> MArr (IArray u) s b -> ST s ()
go !b
acc !Int
i !Int
j !MArr (IArray u) s b
marr
        | Int
j forall a. Ord a => a -> a -> Bool
> Int
l = forall (m :: * -> *) a. Monad m => a -> m a
return ()
        | Bool
otherwise = do
            a
x <- forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray v a
arr Int
i
            let !acc' :: b
acc' = b
acc b -> a -> b
`f` a
x
            forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray u) s b
marr Int
j b
acc'
            forall s. b -> Int -> Int -> MArr (IArray u) s b -> ST s ()
go b
acc' (Int
iforall a. Num a => a -> a -> a
+Int
1) (Int
jforall a. Num a => a -> a -> a
+Int
1) MArr (IArray u) s b
marr

-- | 'scanl1\'' is a variant of 'scanl' that has no starting value argument.
--
-- > scanl1' f [x1, x2, ...] == [x1, x1 `f` x2, ...]
-- > scanl1' f [] == []
--
scanl1' :: forall v a. Vec v a => (a -> a -> a) -> v a -> v a
{-# INLINABLE scanl1' #-}
scanl1' :: forall (v :: * -> *) a. Vec v a => (a -> a -> a) -> v a -> v a
scanl1' a -> a -> a
f (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = forall (v :: * -> *) a. Vec v a => v a
empty
    | Bool
otherwise = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
s of
                    (# a
x0 #) -> forall (v :: * -> *) (u :: * -> *) a b.
(Vec v a, Vec u b) =>
(b -> a -> b) -> b -> v a -> u b
scanl' a -> a -> a
f a
x0 (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
1) (Int
lforall a. Num a => a -> a -> a
-Int
1) :: v a)

-- | scanr' is the right-to-left dual of scanl'.
--
scanr' :: forall v u a b. (Vec v a, Vec u b) => (a -> b -> b) -> b -> v a -> u b
{-# INLINABLE scanr' #-}
scanr' :: forall (v :: * -> *) (u :: * -> *) a b.
(Vec v a, Vec u b) =>
(a -> b -> b) -> b -> v a -> u b
scanr' a -> b -> b
f b
z (Vec IArray v a
arr Int
s Int
l) =
    forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create (Int
lforall a. Num a => a -> a -> a
+Int
1) (\ MArr (IArray u) s b
marr -> forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray u) s b
marr Int
l b
z forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> forall s. b -> Int -> Int -> MArr (IArray u) s b -> ST s ()
go b
z (Int
sforall a. Num a => a -> a -> a
+Int
lforall a. Num a => a -> a -> a
-Int
1) (Int
lforall a. Num a => a -> a -> a
-Int
1) MArr (IArray u) s b
marr)
  where
    go :: b -> Int -> Int -> MArr (IArray u) s b -> ST s ()
    go :: forall s. b -> Int -> Int -> MArr (IArray u) s b -> ST s ()
go !b
acc !Int
i !Int
j !MArr (IArray u) s b
marr
        | Int
j forall a. Ord a => a -> a -> Bool
< Int
0 = forall (m :: * -> *) a. Monad m => a -> m a
return ()
        | Bool
otherwise = do
            a
x <- forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray v a
arr Int
i
            let !acc' :: b
acc' = a
x a -> b -> b
`f` b
acc
            forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s, HasCallStack) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray u) s b
marr Int
j b
acc'
            forall s. b -> Int -> Int -> MArr (IArray u) s b -> ST s ()
go b
acc' (Int
iforall a. Num a => a -> a -> a
-Int
1) (Int
jforall a. Num a => a -> a -> a
-Int
1) MArr (IArray u) s b
marr

-- | 'scanr1'' is a variant of 'scanr' that has no starting value argument.
scanr1' :: forall v a. Vec v a => (a -> a -> a) -> v a -> v a
{-# INLINABLE scanr1' #-}
scanr1' :: forall (v :: * -> *) a. Vec v a => (a -> a -> a) -> v a -> v a
scanr1' a -> a -> a
f (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = forall (v :: * -> *) a. Vec v a => v a
empty
    | Bool
otherwise = case forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> (# a #)
indexArr' IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
lforall a. Num a => a -> a -> a
-Int
1) of
                    (# a
x0 #) -> forall (v :: * -> *) (u :: * -> *) a b.
(Vec v a, Vec u b) =>
(a -> b -> b) -> b -> v a -> u b
scanr' a -> a -> a
f a
x0 (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s (Int
lforall a. Num a => a -> a -> a
-Int
1) :: v a)

--------------------------------------------------------------------------------
-- Misc

-- | @x' = rangeCut x min max@ limit @x'@ 's range to @min@ ~ @max@.
rangeCut :: Int -> Int -> Int -> Int
{-# INLINABLE rangeCut #-}
rangeCut :: Int -> Int -> Int -> Int
rangeCut !Int
r !Int
min' !Int
max' | Int
r forall a. Ord a => a -> a -> Bool
< Int
min' = Int
min'
                        | Int
r forall a. Ord a => a -> a -> Bool
> Int
max' = Int
max'
                        | Bool
otherwise = Int
r


--------------------------------------------------------------------------------

-- | /O(1)/ Extract the first element of a vector.
--
-- Throw 'EmptyVector' if vector is empty.
head :: (Vec v a, HasCallStack) => v a -> a
{-# INLINE head #-}
head :: forall (v :: * -> *) a. (Vec v a, HasCallStack) => v a -> a
head (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = forall a. HasCallStack => a
errorEmptyVector
    | Bool
otherwise = forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> a
indexArr IArray v a
arr Int
s

-- | /O(1)/ Extract the elements after the head of a vector.
--
-- Throw 'EmptyVector' if vector is empty.
tail :: (Vec v a, HasCallStack) => v a -> v a
{-# INLINE tail #-}
tail :: forall (v :: * -> *) a. (Vec v a, HasCallStack) => v a -> v a
tail (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = forall a. HasCallStack => a
errorEmptyVector
    | Bool
otherwise = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
1) (Int
lforall a. Num a => a -> a -> a
-Int
1)

-- | /O(1)/ Extract the elements before of the last one.
--
-- Throw 'EmptyVector' if vector is empty.
init :: (Vec v a, HasCallStack) => v a -> v a
{-# INLINE init #-}
init :: forall (v :: * -> *) a. (Vec v a, HasCallStack) => v a -> v a
init (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = forall a. HasCallStack => a
errorEmptyVector
    | Bool
otherwise = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s (Int
lforall a. Num a => a -> a -> a
-Int
1)

-- | /O(1)/ Extract the last element of a vector.
--
-- Throw 'EmptyVector' if vector is empty.
last :: (Vec v a, HasCallStack) => v a -> a
{-# INLINE last #-}
last :: forall (v :: * -> *) a. (Vec v a, HasCallStack) => v a -> a
last (Vec IArray v a
arr Int
s Int
l)
    | Int
l forall a. Ord a => a -> a -> Bool
<= Int
0    = forall a. HasCallStack => a
errorEmptyVector
    | Bool
otherwise = forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> a
indexArr IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
lforall a. Num a => a -> a -> a
-Int
1)

-- | /O(1)/ Index array element.
--
-- Throw 'IndexOutOfVectorRange' if index outside of the vector.
index :: (Vec v a, HasCallStack) => v a -> Int -> a
{-# INLINE index #-}
index :: forall (v :: * -> *) a. (Vec v a, HasCallStack) => v a -> Int -> a
index (Vec IArray v a
arr Int
s Int
l) Int
i | Int
i forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i forall a. Ord a => a -> a -> Bool
>= Int
l = forall a. HasCallStack => Int -> a
errorOutRange Int
i
                      | Bool
otherwise       = IArray v a
arr forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> a
`indexArr` (Int
s forall a. Num a => a -> a -> a
+ Int
i)

-- | /O(1)/ Index array element.
--
-- Throw 'IndexOutOfVectorRange' if index outside of the vector.
indexM :: (Vec v a, Monad m, HasCallStack) => v a -> Int -> m a
{-# INLINE indexM #-}
indexM :: forall (v :: * -> *) a (m :: * -> *).
(Vec v a, Monad m, HasCallStack) =>
v a -> Int -> m a
indexM (Vec IArray v a
arr Int
s Int
l) Int
i | Int
i forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i forall a. Ord a => a -> a -> Bool
>= Int
l = forall a. HasCallStack => Int -> a
errorOutRange Int
i
                       | Bool
otherwise       = IArray v a
arr forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
`indexArrM` (Int
s forall a. Num a => a -> a -> a
+ Int
i)

-- | /O(n)/ Modify vector's element under given index.
--
-- Throw 'IndexOutOfVectorRange' if index outside of the vector.
--
modifyIndex :: (Vec v a, HasCallStack) => v a -> Int -> (a -> a) -> v a
{-# INLINE modifyIndex #-}
modifyIndex :: forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
v a -> Int -> (a -> a) -> v a
modifyIndex v :: v a
v@(Vec IArray v a
_ Int
_ Int
l) Int
i a -> a
f | Int
i forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i forall a. Ord a => a -> a -> Bool
>= Int
l = forall a. HasCallStack => Int -> a
errorOutRange Int
i
                         | Bool
otherwise       = forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
v a -> Int -> (a -> a) -> v a
unsafeModifyIndex v a
v Int
i a -> a
f

-- | /O(n)/ Modify vector's element under given index.
--
-- Return original vector if index outside of the vector.
--
modifyIndexMaybe :: (Vec v a, HasCallStack) => v a -> Int -> (a -> a) -> v a
{-# INLINE modifyIndexMaybe #-}
modifyIndexMaybe :: forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
v a -> Int -> (a -> a) -> v a
modifyIndexMaybe v :: v a
v@(Vec IArray v a
_ Int
_ Int
l) Int
i a -> a
f | Int
i forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i forall a. Ord a => a -> a -> Bool
>= Int
l = v a
v
                                   | Bool
otherwise       = forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
v a -> Int -> (a -> a) -> v a
unsafeModifyIndex v a
v Int
i a -> a
f

-- | /O(n)/ insert element to vector under given index.
--
-- Throw 'IndexOutOfVectorRange' if index outside of the vector.
--
insertIndex :: (Vec v a, HasCallStack) => v a -> Int -> a -> v a
{-# INLINE insertIndex #-}
insertIndex :: forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
v a -> Int -> a -> v a
insertIndex v :: v a
v@(Vec IArray v a
_ Int
_ Int
l) Int
i a
x | Int
i forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i forall a. Ord a => a -> a -> Bool
> Int
l = forall a. HasCallStack => Int -> a
errorOutRange Int
i
                              | Bool
otherwise      = forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
v a -> Int -> a -> v a
unsafeInsertIndex v a
v Int
i a
x

-- | /O(n)/ insert element to vector under given index.
--
-- Return original vector if index outside of the vector.
--
insertIndexMaybe :: (Vec v a, HasCallStack) => v a -> Int -> a -> v a
{-# INLINE insertIndexMaybe #-}
insertIndexMaybe :: forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
v a -> Int -> a -> v a
insertIndexMaybe v :: v a
v@(Vec IArray v a
_ Int
_ Int
l) Int
i a
x | Int
i forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i forall a. Ord a => a -> a -> Bool
> Int
l = v a
v
                                   | Bool
otherwise      = forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
v a -> Int -> a -> v a
unsafeInsertIndex v a
v Int
i a
x

-- | /O(n)/ Delete vector's element under given index.
--
-- Throw 'IndexOutOfVectorRange' if index outside of the vector.
--
deleteIndex :: (Vec v a, HasCallStack) => v a -> Int -> v a
{-# INLINE deleteIndex #-}
deleteIndex :: forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
v a -> Int -> v a
deleteIndex v :: v a
v@(Vec IArray v a
_ Int
_ Int
l) Int
i | Int
i forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i forall a. Ord a => a -> a -> Bool
>= Int
l = forall a. HasCallStack => Int -> a
errorOutRange Int
i
                            | Bool
otherwise       = forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
v a -> Int -> v a
unsafeDeleteIndex v a
v Int
i

-- | /O(n)/ Delete vector's element under given index.
--
-- Return original vector if index outside of the vector.
--
deleteIndexMaybe :: (Vec v a, HasCallStack) => v a -> Int -> v a
{-# INLINE deleteIndexMaybe #-}
deleteIndexMaybe :: forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
v a -> Int -> v a
deleteIndexMaybe v :: v a
v@(Vec IArray v a
_ Int
_ Int
l) Int
i | Int
i forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i forall a. Ord a => a -> a -> Bool
>= Int
l = v a
v
                                 | Bool
otherwise       = forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
v a -> Int -> v a
unsafeDeleteIndex v a
v Int
i


-- | /O(1)/ Extract the first element of a vector.
--
-- Make sure vector is non-empty, otherwise segmentation fault await!
unsafeHead  :: Vec v a => v a -> a
{-# INLINE unsafeHead #-}
unsafeHead :: forall (v :: * -> *) a. Vec v a => v a -> a
unsafeHead (Vec IArray v a
arr Int
s Int
l) = forall a. HasCallStack => Bool -> a -> a
assert (Int
l forall a. Ord a => a -> a -> Bool
> Int
0) (forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> a
indexArr IArray v a
arr Int
s)

-- | /O(1)/ Extract the elements after the head of a vector.
--
-- Make sure vector is non-empty, otherwise segmentation fault await!
unsafeTail  :: Vec v a => v a -> v a
{-# INLINE unsafeTail #-}
unsafeTail :: forall (v :: * -> *) a. Vec v a => v a -> v a
unsafeTail (Vec IArray v a
arr Int
s Int
l) = forall a. HasCallStack => Bool -> a -> a
assert (Int
l forall a. Ord a => a -> a -> Bool
> Int
0) (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
1) (Int
lforall a. Num a => a -> a -> a
-Int
1))

-- | /O(1)/ Extract the elements before of the last one.
--
-- Make sure vector is non-empty, otherwise segmentation fault await!
unsafeInit  :: Vec v a => v a -> v a
{-# INLINE unsafeInit #-}
unsafeInit :: forall (v :: * -> *) a. Vec v a => v a -> v a
unsafeInit (Vec IArray v a
arr Int
s Int
l) = forall a. HasCallStack => Bool -> a -> a
assert (Int
l forall a. Ord a => a -> a -> Bool
> Int
0) (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s (Int
lforall a. Num a => a -> a -> a
-Int
1))

-- | /O(1)/ Extract the last element of a vector.
--
-- Make sure vector is non-empty, otherwise segmentation fault await!
unsafeLast  :: Vec v a => v a -> a
{-# INLINE unsafeLast #-}
unsafeLast :: forall (v :: * -> *) a. Vec v a => v a -> a
unsafeLast (Vec IArray v a
arr Int
s Int
l) = forall a. HasCallStack => Bool -> a -> a
assert (Int
l forall a. Ord a => a -> a -> Bool
> Int
0) (forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> a
indexArr IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
lforall a. Num a => a -> a -> a
-Int
1))

-- | /O(1)/ Index array element.
--
-- Make sure index is in bound, otherwise segmentation fault await!
unsafeIndex :: Vec v a => v a -> Int -> a
{-# INLINE unsafeIndex #-}
unsafeIndex :: forall (v :: * -> *) a. Vec v a => v a -> Int -> a
unsafeIndex (Vec IArray v a
arr Int
s Int
_) Int
i = forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> a
indexArr IArray v a
arr (Int
s forall a. Num a => a -> a -> a
+ Int
i)

-- | /O(1)/ Index array element.
--
-- Make sure index is in bound, otherwise segmentation fault await!
unsafeIndexM :: (Vec v a, Monad m) => v a -> Int -> m a
{-# INLINE unsafeIndexM #-}
unsafeIndexM :: forall (v :: * -> *) a (m :: * -> *).
(Vec v a, Monad m) =>
v a -> Int -> m a
unsafeIndexM (Vec IArray v a
arr Int
s Int
_) Int
i = forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m, HasCallStack) =>
arr a -> Int -> m a
indexArrM IArray v a
arr (Int
s forall a. Num a => a -> a -> a
+ Int
i)

-- | /O(n)/ Modify vector's element under given index.
--
-- Make sure index is in bound, otherwise segmentation fault await!
unsafeModifyIndex :: (Vec v a, HasCallStack) => v a -> Int -> (a -> a) -> v a
{-# INLINE unsafeModifyIndex #-}
unsafeModifyIndex :: forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
v a -> Int -> (a -> a) -> v a
unsafeModifyIndex (Vec IArray v a
arr Int
s Int
l) Int
i a -> a
f = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec (forall (arr :: * -> *) a.
(Arr arr a, HasCallStack) =>
arr a -> Int -> Int -> Int -> (a -> a) -> arr a
modifyIndexArr IArray v a
arr Int
s Int
l Int
i a -> a
f) Int
0 Int
l

-- | /O(n)/ Insert element to vector under given index.
--
-- Make sure index is in bound, otherwise segmentation fault await!
unsafeInsertIndex :: (Vec v a, HasCallStack) => v a -> Int -> a -> v a
{-# INLINE unsafeInsertIndex #-}
unsafeInsertIndex :: forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
v a -> Int -> a -> v a
unsafeInsertIndex (Vec IArray v a
arr Int
s Int
l) Int
i a
x = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec (forall (arr :: * -> *) a.
Arr arr a =>
arr a -> Int -> Int -> Int -> a -> arr a
insertIndexArr IArray v a
arr Int
s Int
l Int
i a
x) Int
0 (Int
lforall a. Num a => a -> a -> a
+Int
1)

-- | /O(n)/ Delete vector's element under given index.
--
-- Make sure index is in bound, otherwise segmentation fault await!
unsafeDeleteIndex :: (Vec v a, HasCallStack) => v a -> Int -> v a
{-# INLINE unsafeDeleteIndex #-}
unsafeDeleteIndex :: forall (v :: * -> *) a.
(Vec v a, HasCallStack) =>
v a -> Int -> v a
unsafeDeleteIndex (Vec IArray v a
arr Int
s Int
l) Int
i = forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec (forall (arr :: * -> *) a.
Arr arr a =>
arr a -> Int -> Int -> Int -> arr a
deleteIndexArr IArray v a
arr Int
s Int
l Int
i) Int
0 (Int
lforall a. Num a => a -> a -> a
-Int
1)

-- | /O(1)/ 'take' @n@, applied to a vector @xs@, returns the prefix
-- of @xs@ of length @n@.
--
-- Make sure n is smaller than vector's length, otherwise segmentation fault await!
unsafeTake :: Vec v a => Int -> v a -> v a
{-# INLINE unsafeTake #-}
unsafeTake :: forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
unsafeTake Int
n (Vec IArray v a
arr Int
s Int
l) = forall a. HasCallStack => Bool -> a -> a
assert (Int
0 forall a. Ord a => a -> a -> Bool
<= Int
n Bool -> Bool -> Bool
&& Int
n forall a. Ord a => a -> a -> Bool
<= Int
l) (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s Int
n)

-- | /O(1)/ 'drop' @n xs@ returns the suffix of @xs@ after the first @n@
-- elements.
--
-- Make sure n is smaller than vector's length, otherwise segmentation fault await!
unsafeDrop :: Vec v a => Int -> v a -> v a
{-# INLINE unsafeDrop #-}
unsafeDrop :: forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
unsafeDrop Int
n (Vec IArray v a
arr Int
s Int
l) = forall a. HasCallStack => Bool -> a -> a
assert (Int
0 forall a. Ord a => a -> a -> Bool
<= Int
n Bool -> Bool -> Bool
&& Int
n forall a. Ord a => a -> a -> Bool
<= Int
l) (forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sforall a. Num a => a -> a -> a
+Int
n) (Int
lforall a. Num a => a -> a -> a
-Int
n))

--------------------------------------------------------------------------------

foreign import ccall unsafe "hs_intersperse" c_intersperse ::
    MutableByteArray# RealWorld -> ByteArray# -> Int -> Int -> Word8 -> IO ()