{-|
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 :: a -> v a -> v a
cons a
x (Vec IArray v a
arr Int
s Int
l) = Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create (Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) ((forall s. MArr (IArray v) s a -> ST s ()) -> v a)
-> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
forall a b. (a -> b) -> a -> b
$ \ MArr (IArray v) s a
marr ->
    MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
0 a
x ST s () -> ST s () -> ST s ()
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> MArr (IArray v) s a -> Int -> IArray v a -> Int -> Int -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
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 :: v a -> a -> v a
snoc (Vec IArray v a
arr Int
s Int
l) a
x = Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create (Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) ((forall s. MArr (IArray v) s a -> ST s ()) -> v a)
-> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
forall a b. (a -> b) -> a -> b
$ \ MArr (IArray v) s a
marr ->
    MArr (IArray v) s a -> Int -> IArray v a -> Int -> Int -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
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 ST s () -> ST s () -> ST s ()
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
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 :: v a -> Maybe (a, v a)
uncons (Vec IArray v a
arr Int
s Int
l)
    | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0    = Maybe (a, v a)
forall a. Maybe a
Nothing
    | Bool
otherwise = let !v :: v a
v = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)
                  in case IArray v a -> Int -> (# a #)
forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
s of (# a
x #) -> (a, v a) -> Maybe (a, v a)
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 :: v a -> Maybe (v a, a)
unsnoc (Vec IArray v a
arr Int
s Int
l)
    | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0    = Maybe (v a, a)
forall a. Maybe a
Nothing
    | Bool
otherwise = let !v :: v a
v = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s (Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)
                  in case IArray v a -> Int -> (# a #)
forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> (# a #)
indexArr' IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) of (# a
x #) -> (v a, a) -> Maybe (v a, a)
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 :: v a -> Maybe a
headMaybe (Vec IArray v a
arr Int
s Int
l)
    | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0    = Maybe a
forall a. Maybe a
Nothing
    | Bool
otherwise = IArray v a -> Int -> Maybe a
forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m) =>
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 :: v a -> v a
tailMayEmpty (Vec IArray v a
arr Int
s Int
l)
    | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0    = v a
forall (v :: * -> *) a. Vec v a => v a
empty
    | Bool
otherwise = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
lInt -> Int -> Int
forall 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 :: v a -> Maybe a
lastMaybe (Vec IArray v a
arr Int
s Int
l)
    | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0    = Maybe a
forall a. Maybe a
Nothing
    | Bool
otherwise = IArray v a -> Int -> Maybe a
forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m) =>
arr a -> Int -> m a
indexArrM IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
lInt -> Int -> Int
forall 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 :: v a -> v a
initMayEmpty (Vec IArray v a
arr Int
s Int
l)
    | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0    = v a
forall (v :: * -> *) a. Vec v a => v a
empty
    | Bool
otherwise = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s (Int
lInt -> Int -> Int
forall 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 :: v a -> [v a]
inits (Vec IArray v a
arr Int
s Int
l) =  [IArray v a -> Int -> Int -> v a
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 :: v a -> [v a]
tails (Vec IArray v a
arr Int
s Int
l) = [IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
n) (Int
lInt -> Int -> Int
forall 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 :: Int -> v a -> v a
take Int
n v :: v a
v@(Vec IArray v a
arr Int
s Int
l)
    | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0    = v a
forall (v :: * -> *) a. Vec v a => v a
empty
    | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
l    = v a
v
    | Bool
otherwise = IArray v a -> Int -> Int -> v a
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 :: Int -> v a -> v a
takeR Int
n v :: v a
v@(Vec IArray v a
arr Int
s Int
l)
    | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0    = v a
forall (v :: * -> *) a. Vec v a => v a
empty
    | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
l    = v a
v
    | Bool
otherwise = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
lInt -> Int -> Int
forall 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 :: Int -> v a -> v a
drop Int
n v :: v a
v@(Vec IArray v a
arr Int
s Int
l)
    | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0    = v a
v
    | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
l    = v a
forall (v :: * -> *) a. Vec v a => v a
empty
    | Bool
otherwise = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
n) (Int
lInt -> Int -> Int
forall 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 :: Int -> v a -> v a
dropR Int
n v :: v a
v@(Vec IArray v a
arr Int
s Int
l)
    | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0    = v a
v
    | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
l    = v a
forall (v :: * -> *) a. Vec v a => v a
empty
    | Bool
otherwise = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s (Int
lInt -> Int -> Int
forall 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 :: Int -> Int -> v a -> v a
slice Int
x Int
y = Int -> v a -> v a
forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
drop Int
x (v a -> v a) -> (v a -> v a) -> v a -> v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> v a -> v a
forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
take (Int
xInt -> Int -> Int
forall 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 :: Int -> v a -> (v a, v a)
splitAt Int
z (Vec IArray v a
arr Int
s Int
l) = let !v1 :: v a
v1 = IArray v a -> Int -> Int -> v a
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 = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
z') (Int
lInt -> Int -> Int
forall 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 takeWhile #-}
takeWhile :: (a -> Bool) -> v a -> v a
takeWhile a -> Bool
f v :: v a
v@(Vec IArray v a
arr Int
s Int
_) =
    case (a -> Bool) -> v a -> Int
forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Int
findIndex (Bool -> Bool
not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
f) v a
v of
        Int
0  -> v a
forall (v :: * -> *) a. Vec v a => v a
empty
        Int
i  -> IArray v a -> Int -> Int -> v a
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 takeWhileR #-}
takeWhileR :: (a -> Bool) -> v a -> v a
takeWhileR a -> Bool
f v :: v a
v@(Vec IArray v a
arr Int
s Int
l) =
    case (a -> Bool) -> v a -> Int
forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Int
findIndexR (Bool -> Bool
not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
f) v a
v of
        -1 -> v a
v
        Int
i  -> IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
iInt -> Int -> Int
forall 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 dropWhile #-}
dropWhile :: (a -> Bool) -> v a -> v a
dropWhile a -> Bool
f v :: v a
v@(Vec IArray v a
arr Int
s Int
l) =
    case (a -> Bool) -> v a -> Int
forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Int
findIndex (Bool -> Bool
not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
f) v a
v of
        Int
i | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
l     -> v a
forall (v :: * -> *) a. Vec v a => v a
empty
          | Bool
otherwise  -> IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
i) (Int
lInt -> Int -> Int
forall 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 dropWhileR #-}
dropWhileR :: (a -> Bool) -> v a -> v a
dropWhileR a -> Bool
f v :: v a
v@(Vec IArray v a
arr Int
s Int
_) =
    case (a -> Bool) -> v a -> Int
forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Int
findIndexR (Bool -> Bool
not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
f) v a
v of
        -1 -> v a
forall (v :: * -> *) a. Vec v a => v a
empty
        Int
i  -> IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr Int
s (Int
iInt -> Int -> Int
forall 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 :: (a -> Bool) -> v a -> v a
dropAround a -> Bool
f = (a -> Bool) -> v a -> v a
forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> v a
dropWhile a -> Bool
f (v a -> v a) -> (v a -> v a) -> v a -> v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> v a -> v a
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 :: (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 =  (a -> Bool) -> v a -> Int
forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Int
findIndex a -> Bool
f v a
vs
        !v1 :: v a
v1 = IArray v a -> Int -> Int -> v a
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 = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
n) (Int
lInt -> Int -> Int
forall 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 #-}
span :: (a -> Bool) -> v a -> (v a, v a)
span a -> Bool
f = (a -> Bool) -> v a -> (v a, v a)
forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> (v a, v a)
break (Bool -> Bool
not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
f)
{-# RULES "spanNEq/breakEq1" forall w. span (w `neWord8`) = break (w `eqWord8`) #-}
{-# RULES "spanNEq/breakEq2" forall w. span (`neWord8` w) = break (`eqWord8` w) #-}

-- | 'breakR' behaves like 'break' but 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 :: (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 = (a -> Bool) -> v a -> Int
forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Int
findIndexR a -> Bool
f v a
vs
        !v1 :: v a
v1 = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr Int
s (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
        !v2 :: v a
v2 = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1Int -> Int -> Int
forall 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 spanR #-}
spanR :: (a -> Bool) -> v a -> (v a, v a)
spanR a -> Bool
f = (a -> Bool) -> v a -> (v a, v a)
forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> (v a, v a)
breakR (Bool -> Bool
not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
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)
{-# INLINE breakOn #-}
breakOn :: 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 = IArray v a -> Int -> Int -> v a
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 = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
i) (Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
i)
                 in (v a
v1, v a
v2)
        [Int]
_     -> (v a
haystack, v a
forall (v :: * -> *) a. Vec v a => v a
empty)
  where search :: v a -> Bool -> [Int]
search = v a -> v a -> Bool -> [Int]
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]
{-# INLINE group #-}
group :: v a -> [v a]
group = (a -> a -> Bool) -> v a -> [v a]
forall (v :: * -> *) a. Vec v a => (a -> a -> Bool) -> v a -> [v a]
groupBy a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)

groupBy :: forall v a. Vec v a =>  (a -> a -> Bool) -> v a -> [v a]
{-# INLINE groupBy #-}
groupBy :: (a -> a -> Bool) -> v a -> [v a]
groupBy a -> a -> Bool
f (Vec IArray v a
arr Int
s Int
l)
    | Int
l Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = []
    | Bool
otherwise = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr Int
s Int
n v a -> [v a] -> [v a]
forall a. a -> [a] -> [a]
: (a -> a -> Bool) -> v a -> [v a]
forall (v :: * -> *) a. Vec v a => (a -> a -> Bool) -> v a -> [v a]
groupBy a -> a -> Bool
f (IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
n) (Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
n))
  where
    n :: Int
n = case IArray v a -> Int -> (# a #)
forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
s of
        (# a
x #) -> Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (a -> Bool) -> v a -> Int
forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Int
findIndex @v (Bool -> Bool
not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a -> Bool
f a
x) (IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
lInt -> Int -> Int
forall 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)
{-# INLINE stripPrefix #-}
stripPrefix :: 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 v a -> v a -> Bool
forall (v :: * -> *) a. (Vec v a, Eq (v a)) => v a -> v a -> Bool
`isPrefixOf` v a
v2 = v a -> Maybe (v a)
forall a. a -> Maybe a
Just (IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
l1) (Int
l2Int -> Int -> Int
forall a. Num a => a -> a -> a
-Int
l1))
   | Bool
otherwise = Maybe (v a)
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
{-# INLINE isPrefixOf #-}
isPrefixOf :: 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 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = Bool
True
    | Int
lA Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
lB = Bool
False
    | Bool
otherwise = v a -> v a -> Bool
forall a. Eq a => a -> a -> Bool
(==) @(v a) (IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arrA Int
sA Int
lA) (IArray v a -> Int -> Int -> v a
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)
{-# INLINE commonPrefix #-}
commonPrefix :: 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 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
lA
    !endB :: Int
endB = Int
sB Int -> Int -> Int
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
endA = let !vB' :: v a
vB' = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arrB (Int
sBInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
sA) (Int
lBInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
sA) in (v a
vA, v a
forall (v :: * -> *) a. Vec v a => v a
empty, v a
vB')
             | Int
j Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
endB = let !vA' :: v a
vA' = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arrA (Int
sAInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
sB) (Int
lAInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
sB) in (v a
vB, v a
vA', v a
forall (v :: * -> *) a. Vec v a => v a
empty)
             | IArray v a -> Int -> a
forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> a
indexArr IArray v a
arrA Int
i a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== IArray v a -> Int -> a
forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> a
indexArr IArray v a
arrB Int
j = Int -> Int -> (v a, v a, v a)
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
             | Bool
otherwise =
                let !vB' :: v a
vB' = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arrB (Int
sBInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
sA) (Int
lBInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
sA)
                    !vA' :: v a
vA' = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arrA (Int
sAInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
sB) (Int
lAInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
sB)
                    !vC :: v a
vC  = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arrA Int
sA (Int
iInt -> Int -> Int
forall 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)
{-# INLINE stripSuffix #-}
stripSuffix :: 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 v a -> v a -> Bool
forall (v :: * -> *) a. (Vec v a, Eq (v a)) => v a -> v a -> Bool
`isSuffixOf` v a
v2 = v a -> Maybe (v a)
forall a. a -> Maybe a
Just (IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arr Int
s (Int
l2Int -> Int -> Int
forall a. Num a => a -> a -> a
-Int
l1))
   | Bool
otherwise = Maybe (v a)
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
{-# INLINE isSuffixOf #-}
isSuffixOf :: 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 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = Bool
True
    | Int
lA Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
lB = Bool
False
    | Bool
otherwise = v a -> v a -> Bool
forall a. Eq a => a -> a -> Bool
(==) @(v a) (IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arrA Int
sA Int
lA) (IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec IArray v a
arrB (Int
sBInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
lBInt -> Int -> Int
forall 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
{-# INLINE isInfixOf #-}
isInfixOf :: v a -> v a -> Bool
isInfixOf v a
needle = \ v a
haystack -> v a -> Bool
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 [Int] -> [Int] -> Bool
forall a. Eq a => a -> a -> Bool
/= []
  where search :: v a -> Bool -> [Int]
search = v a -> v a -> Bool -> [Int]
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]
{-# INLINE split #-}
split :: a -> v a -> [v a]
split a
x = (a -> Bool) -> v a -> [v a]
forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> [v a]
splitWith (a -> a -> Bool
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]
{-# INLINE splitOn #-}
splitOn :: 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' = v a -> Int
forall (v :: * -> *) a. Vec v a => v a -> Int
length v a
needle
        !end :: Int
end = Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
l
        search :: v a -> Bool -> [Int]
search = v a -> v a -> Bool -> [Int]
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 = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s' (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
s')
                               in v a
v v a -> [v a] -> [v a]
forall a. a -> [a] -> [a]
: Int -> [Int] -> [v a]
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
l') [Int]
is
        go !Int
s' [Int]
_      = let !v :: v a
v = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s' (Int
endInt -> Int -> Int
forall 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]
{-# INLINE splitWith #-}
splitWith :: (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 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = [v a
forall (v :: * -> *) a. Vec v a => v a
empty]
        | Bool
otherwise =
            let n :: Int
n = (a -> Bool) -> v a -> Int
forall (v :: * -> *) a. Vec v a => (a -> Bool) -> v a -> Int
findIndex a -> Bool
f v a
v
            in if Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
l
                then [v a
v]
                else Int -> v a -> v a
forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
unsafeTake Int
n v a
v v a -> [v a] -> [v a]
forall a. a -> [a] -> [a]
: v a -> [v a]
go (Int -> v a -> v a
forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
unsafeDrop (Int
nInt -> Int -> Int
forall 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]
{-# INLINE 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 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
l
    go :: Int -> Int -> [Bytes]
    go :: Int -> Int -> [Bytes]
go !Int
s' !Int
i | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
end =
                    if Int
s' Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
end
                    then []
                    else let !v :: Bytes
v = IArray PrimVector Word8 -> Int -> Int -> Bytes
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray PrimVector Word8
arr Int
s' (Int
endInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
s') in [Bytes
v]
              | Word8 -> Bool
isSpace (PrimArray Word8 -> Int -> Word8
forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> a
indexArr PrimArray Word8
IArray PrimVector Word8
arr Int
i) =
                    if Int
s' Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
i
                    then Int -> Int -> [Bytes]
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
                    else
                    let !v :: Bytes
v = IArray PrimVector Word8 -> Int -> Int -> Bytes
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray PrimVector Word8
arr Int
s' (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
s') in Bytes
v Bytes -> [Bytes] -> [Bytes]
forall a. a -> [a] -> [a]
: Int -> Int -> [Bytes]
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
              | Bool
otherwise = Int -> Int -> [Bytes]
go Int
s' (Int
iInt -> Int -> Int
forall 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]
{-# INLINE lines #-}
lines :: Bytes -> [Bytes]
lines Bytes
v
    | Bytes -> Bool
forall (v :: * -> *) a. Vec v a => v a -> Bool
null Bytes
v = []
    | Bool
otherwise = case Word8 -> Bytes -> Maybe Int
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  -> Int -> Bytes -> Bytes
forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
unsafeTake Int
n Bytes
v Bytes -> [Bytes] -> [Bytes]
forall a. a -> [a] -> [a]
: Bytes -> [Bytes]
lines (Int -> Bytes -> Bytes
forall (v :: * -> *) a. Vec v a => Int -> v a -> v a
unsafeDrop (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Bytes
v)

-- | /O(n)/ Joins words with ascii space.
unwords :: [Bytes] -> Bytes
{-# INLINE unwords #-}
unwords :: [Bytes] -> Bytes
unwords = Word8 -> [Bytes] -> Bytes
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
{-# INLINE unlines #-}
unlines :: [Bytes] -> Bytes
unlines = Word8 -> [Bytes] -> Bytes
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
{-# INLINE padLeft #-}
padLeft :: 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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
l = v a
v
                            | Bool
otherwise = Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
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
                                    MArr (IArray v) s a -> Int -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> Int -> a -> m ()
setArr MArr (IArray v) s a
marr Int
0 (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
l) a
x
                                    MArr (IArray v) s a -> Int -> IArray v a -> Int -> Int -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> arr a -> Int -> Int -> m ()
copyArr MArr (IArray v) s a
marr (Int
nInt -> Int -> Int
forall 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
{-# INLINE padRight #-}
padRight :: 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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
l = v a
v
                             | Bool
otherwise = Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
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
                                    MArr (IArray v) s a -> Int -> IArray v a -> Int -> Int -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
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
                                    MArr (IArray v) s a -> Int -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> Int -> a -> m ()
setArr MArr (IArray v) s a
marr Int
l (Int
nInt -> Int -> Int
forall 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
{-# INLINE reverse #-}
reverse :: v a -> v a
reverse (Vec IArray v a
arr Int
s Int
l) = Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create Int
l (Int -> Int -> MArr (IArray v) s a -> ST s ()
forall s. Int -> Int -> MArr (IArray v) s a -> ST s ()
go Int
s (Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1))
  where
    go :: Int -> Int -> MArr (IArray v) s a -> ST s ()
    go :: Int -> Int -> MArr (IArray v) s a -> ST s ()
go !Int
i !Int
j !MArr (IArray v) s a
marr | Int
j Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = () -> ST s ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
                   | Int
j Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
3 = do  -- a bit of loop unrolling here
                        IArray v a -> Int -> ST s a
forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m) =>
arr a -> Int -> m a
indexArrM IArray v a
arr Int
i ST s a -> (a -> ST s ()) -> ST s ()
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
j
                        IArray v a -> Int -> ST s a
forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m) =>
arr a -> Int -> m a
indexArrM IArray v a
arr (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) ST s a -> (a -> ST s ()) -> ST s ()
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)
                        IArray v a -> Int -> ST s a
forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m) =>
arr a -> Int -> m a
indexArrM IArray v a
arr (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
2) ST s a -> (a -> ST s ()) -> ST s ()
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
2)
                        IArray v a -> Int -> ST s a
forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m) =>
arr a -> Int -> m a
indexArrM IArray v a
arr (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
3) ST s a -> (a -> ST s ()) -> ST s ()
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
3)
                        Int -> Int -> MArr (IArray v) s a -> ST s ()
forall s. Int -> Int -> MArr (IArray v) s a -> ST s ()
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
4) (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
4) MArr (IArray v) s a
marr
                   | Bool
otherwise = do
                        IArray v a -> Int -> ST s a
forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m) =>
arr a -> Int -> m a
indexArrM IArray v a
arr Int
i ST s a -> (a -> ST s ()) -> ST s ()
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
j
                        Int -> Int -> MArr (IArray v) s a -> ST s ()
forall s. Int -> Int -> MArr (IArray v) s a -> ST s ()
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
jInt -> Int -> Int
forall 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 :: a -> v a -> v a
intersperse a
x v :: v a
v@(Vec IArray v a
arr Int
s Int
l) | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
1 = v a
v
                              | Bool
otherwise = Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create (Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) (Int -> Int -> MArr (IArray v) s a -> ST s ()
forall s. Int -> Int -> MArr (IArray v) s a -> ST s ()
go Int
s Int
0)
   where
    !end :: Int
end = Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
lInt -> Int -> Int
forall 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 :: Int -> Int -> MArr (IArray v) s a -> ST s ()
go !Int
i !Int
j !MArr (IArray v) s a
marr
        | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
end = MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
j (a -> ST s ()) -> ST s a -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< IArray v a -> Int -> ST s a
forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m) =>
arr a -> Int -> m a
indexArrM IArray v a
arr Int
i
        | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
end Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
4 = do -- a bit of loop unrolling
            MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
j (a -> ST s ()) -> ST s a -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< IArray v a -> Int -> ST s a
forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m) =>
arr a -> Int -> m a
indexArrM IArray v a
arr Int
i
            MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) a
x
            MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
2) (a -> ST s ()) -> ST s a -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< IArray v a -> Int -> ST s a
forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m) =>
arr a -> Int -> m a
indexArrM IArray v a
arr (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
            MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
3) a
x
            MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
4) (a -> ST s ()) -> ST s a -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< IArray v a -> Int -> ST s a
forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m) =>
arr a -> Int -> m a
indexArrM IArray v a
arr (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
2)
            MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
5) a
x
            MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
6) (a -> ST s ()) -> ST s a -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< IArray v a -> Int -> ST s a
forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m) =>
arr a -> Int -> m a
indexArrM IArray v a
arr (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
3)
            MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
7) a
x
            Int -> Int -> MArr (IArray v) s a -> ST s ()
forall s. Int -> Int -> MArr (IArray v) s a -> ST s ()
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
4) (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
8) MArr (IArray v) s a
marr
        | Bool
otherwise = do
            MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
j (a -> ST s ()) -> ST s a -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< IArray v a -> Int -> ST s a
forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m) =>
arr a -> Int -> m a
indexArrM IArray v a
arr Int
i
            MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) a
x
            Int -> Int -> MArr (IArray v) s a -> ST s ()
forall s. Int -> Int -> MArr (IArray v) s a -> ST s ()
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
jInt -> Int -> Int
forall 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
{-# INLINE intersperseBytes #-}
intersperseBytes :: Word8 -> Bytes -> Bytes
intersperseBytes Word8
c v :: Bytes
v@(PrimVector (PrimArray ByteArray#
ba#) Int
offset Int
l)
    | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
1 = Bytes
v
    | Bool
otherwise = IO Bytes -> Bytes
forall a. IO a -> a
unsafeDupablePerformIO (IO Bytes -> Bytes) -> IO Bytes -> Bytes
forall a b. (a -> b) -> a -> b
$ do
        mba :: MutableByteArray RealWorld
mba@(MutableByteArray MutableByteArray# RealWorld
mba#) <- Int -> IO (MutableByteArray (PrimState IO))
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'#) <- MutableByteArray (PrimState IO) -> IO ByteArray
forall (m :: * -> *).
PrimMonad m =>
MutableByteArray (PrimState m) -> m ByteArray
unsafeFreezeByteArray MutableByteArray RealWorld
MutableByteArray (PrimState IO)
mba
        Bytes -> IO Bytes
forall (m :: * -> *) a. Monad m => a -> m a
return (PrimArray Word8 -> Int -> Int -> Bytes
forall a. PrimArray a -> Int -> Int -> PrimVector a
PrimVector (ByteArray# -> PrimArray Word8
forall a. ByteArray# -> PrimArray a
PrimArray ByteArray#
ba'#) Int
0 Int
n)
  where n :: Int
n = Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
lInt -> Int -> Int
forall 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
{-# INLINE intercalate #-}
intercalate :: v a -> [v a] -> v a
intercalate v a
s = [v a] -> v a
forall (v :: * -> *) a. Vec v a => [v a] -> v a
concat ([v a] -> v a) -> ([v a] -> [v a]) -> [v a] -> v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v a -> [v a] -> [v a]
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
{-# INLINE intercalateElem #-}
intercalateElem :: a -> [v a] -> v a
intercalateElem a
_ [] = v a
forall (v :: * -> *) a. Vec v a => v a
empty
intercalateElem a
_ [v a
v] = v a
v
intercalateElem a
w [v a]
vs = Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create ([v a] -> Int -> Int
forall (v :: * -> *) a. Vec v a => [v a] -> Int -> Int
len [v a]
vs Int
0) (Int -> [v a] -> MArr (IArray v) s a -> ST s ()
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 Int -> Int -> Int
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
accInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)
    go :: forall s. Int -> [v a] -> MArr (IArray v) s a -> ST s ()
    go :: Int -> [v a] -> MArr (IArray v) s a -> ST s ()
go !Int
_ []               !MArr (IArray v) s a
_    = () -> ST s ()
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 = MArr (IArray v) s a -> Int -> IArray v a -> Int -> Int -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
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 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
l
        MArr (IArray v) s a -> Int -> IArray v a -> Int -> Int -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
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
        MArr (IArray v) s a -> Int -> a -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray v) s a
marr Int
i' a
w
        Int -> [v a] -> MArr (IArray v) s a -> ST s ()
forall s. Int -> [v a] -> MArr (IArray v) s a -> ST s ()
go (Int
i'Int -> Int -> Int
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]
{-# INLINE transpose #-}
transpose :: [v a] -> [v a]
transpose [v a]
vs =
    ([a] -> v a) -> [[a]] -> [v a]
forall a b. (a -> b) -> [a] -> [b]
List.map (Int -> [a] -> v a
forall (v :: * -> *) a. Vec v a => Int -> [a] -> v a
packN Int
n) ([[a]] -> [v a]) -> ([v a] -> [[a]]) -> [v a] -> [v a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[a]] -> [[a]]
forall a. [[a]] -> [[a]]
List.transpose ([[a]] -> [[a]]) -> ([v a] -> [[a]]) -> [v a] -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (v a -> [a]) -> [v a] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
List.map v a -> [a]
forall (v :: * -> *) a. Vec v a => v a -> [a]
unpack ([v a] -> [v a]) -> [v a] -> [v a]
forall a b. (a -> b) -> a -> b
$ [v a]
vs
  where n :: Int
n = [v a] -> Int
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
{-# INLINE zipWith' #-}
zipWith' :: (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) = Int -> (forall s. MArr (IArray w) s c -> ST s ()) -> w c
forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create Int
len (Int -> MArr (IArray w) s c -> ST s ()
forall s. Int -> MArr (IArray w) s c -> ST s ()
go Int
0)
  where
    !len :: Int
len = Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
lA Int
lB
    go :: forall s. Int -> MArr (IArray w) s c -> ST s ()
    go :: Int -> MArr (IArray w) s c -> ST s ()
go !Int
i !MArr (IArray w) s c
marr
        | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
len = () -> ST s ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
        | Bool
otherwise = case IArray v a -> Int -> (# a #)
forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> (# a #)
indexArr' IArray v a
arrA (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
sA) of
             (# a
a #) -> case IArray u b -> Int -> (# b #)
forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> (# a #)
indexArr' IArray u b
arrB (Int
iInt -> Int -> Int
forall 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 MArr (IArray w) s c -> Int -> c -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray w) s c
marr Int
i c
c
                               Int -> MArr (IArray w) s c -> ST s ()
forall s. Int -> MArr (IArray w) s c -> ST s ()
go (Int
iInt -> Int -> Int
forall 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)
{-# INLINE unzipWith' #-}
unzipWith' :: (a -> (b, c)) -> v a -> (u b, w c)
unzipWith' a -> (b, c)
f (Vec IArray v a
arr Int
s Int
l) = Int
-> Int
-> (forall s.
    MArr (IArray u) s b -> MArr (IArray w) s c -> ST s (Int, Int))
-> (u b, w c)
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 (Int
-> MArr (IArray u) s b -> MArr (IArray w) s c -> ST s (Int, Int)
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 :: 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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
l = (Int, Int) -> ST s (Int, Int)
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
l,Int
l)
        | Bool
otherwise = case IArray v a -> Int -> (# a #)
forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> (# a #)
indexArr' IArray v a
arr (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
s) of
            (# a
a #) -> do let (!b
b, !c
c) = a -> (b, c)
f a
a
                          MArr (IArray u) s b -> Int -> b -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray u) s b
marrB Int
i b
b
                          MArr (IArray w) s c -> Int -> c -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray w) s c
marrC Int
i c
c
                          Int
-> MArr (IArray u) s b -> MArr (IArray w) s c -> ST s (Int, Int)
forall s.
Int
-> MArr (IArray u) s b -> MArr (IArray w) s c -> ST s (Int, Int)
go (Int
iInt -> Int -> Int
forall 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
{-# INLINE scanl' #-}
scanl' :: (b -> a -> b) -> b -> v a -> u b
scanl' b -> a -> b
f b
z (Vec IArray v a
arr Int
s Int
l) =
    Int -> (forall s. MArr (IArray u) s b -> ST s ()) -> u b
forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create (Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (\ MArr (IArray u) s b
marr -> MArr (IArray u) s b -> Int -> b -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray u) s b
marr Int
0 b
z ST s () -> ST s () -> ST s ()
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> b -> Int -> Int -> MArr (IArray u) s b -> ST s ()
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 :: 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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
l = () -> ST s ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
        | Bool
otherwise = do
            a
x <- IArray v a -> Int -> ST s a
forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m) =>
arr a -> Int -> m a
indexArrM IArray v a
arr Int
i
            let !acc' :: b
acc' = b
acc b -> a -> b
`f` a
x
            MArr (IArray u) s b -> Int -> b -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray u) s b
marr Int
j b
acc'
            b -> Int -> Int -> MArr (IArray u) s b -> ST s ()
forall s. b -> Int -> Int -> MArr (IArray u) s b -> ST s ()
go b
acc' (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
jInt -> Int -> Int
forall 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
{-# INLINE scanl1' #-}
scanl1' :: (a -> a -> a) -> v a -> v a
scanl1' a -> a -> a
f (Vec IArray v a
arr Int
s Int
l)
    | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0    = v a
forall (v :: * -> *) a. Vec v a => v a
empty
    | Bool
otherwise = case IArray v a -> Int -> (# a #)
forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> (# a #)
indexArr' IArray v a
arr Int
s of
                    (# a
x0 #) -> (a -> a -> a) -> a -> v a -> v a
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 (IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
lInt -> Int -> Int
forall 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
{-# INLINE scanr' #-}
scanr' :: (a -> b -> b) -> b -> v a -> u b
scanr' a -> b -> b
f b
z (Vec IArray v a
arr Int
s Int
l) =
    Int -> (forall s. MArr (IArray u) s b -> ST s ()) -> u b
forall (v :: * -> *) a.
Vec v a =>
Int -> (forall s. MArr (IArray v) s a -> ST s ()) -> v a
create (Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (\ MArr (IArray u) s b
marr -> MArr (IArray u) s b -> Int -> b -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray u) s b
marr Int
l b
z ST s () -> ST s () -> ST s ()
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> b -> Int -> Int -> MArr (IArray u) s b -> ST s ()
forall s. b -> Int -> Int -> MArr (IArray u) s b -> ST s ()
go b
z (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) (Int
lInt -> Int -> Int
forall 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 :: 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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = () -> ST s ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
        | Bool
otherwise = do
            a
x <- IArray v a -> Int -> ST s a
forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m) =>
arr a -> Int -> m a
indexArrM IArray v a
arr Int
i
            let !acc' :: b
acc' = a
x a -> b -> b
`f` b
acc
            MArr (IArray u) s b -> Int -> b -> ST s ()
forall (arr :: * -> *) a (m :: * -> *) s.
(Arr arr a, PrimMonad m, PrimState m ~ s) =>
MArr arr s a -> Int -> a -> m ()
writeArr MArr (IArray u) s b
marr Int
j b
acc'
            b -> Int -> Int -> MArr (IArray u) s b -> ST s ()
forall s. b -> Int -> Int -> MArr (IArray u) s b -> ST s ()
go b
acc' (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) (Int
jInt -> Int -> Int
forall 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
{-# INLINE scanr1' #-}
scanr1' :: (a -> a -> a) -> v a -> v a
scanr1' a -> a -> a
f (Vec IArray v a
arr Int
s Int
l)
    | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0    = v a
forall (v :: * -> *) a. Vec v a => v a
empty
    | Bool
otherwise = case IArray v a -> Int -> (# a #)
forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> (# a #)
indexArr' IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) of
                    (# a
x0 #) -> (a -> a -> a) -> a -> v a -> v a
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 (IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s (Int
lInt -> Int -> Int
forall 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
{-# INLINE rangeCut #-}
rangeCut :: Int -> Int -> Int -> Int
rangeCut !Int
r !Int
min' !Int
max' | Int
r Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
min' = Int
min'
                        | Int
r Int -> Int -> Bool
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 :: v a -> a
head (Vec IArray v a
arr Int
s Int
l)
    | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0    = a
forall a. HasCallStack => a
errorEmptyVector
    | Bool
otherwise = IArray v a -> Int -> a
forall (arr :: * -> *) a. Arr arr a => 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 :: v a -> v a
tail (Vec IArray v a
arr Int
s Int
l)
    | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0    = v a
forall a. HasCallStack => a
errorEmptyVector
    | Bool
otherwise = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
lInt -> Int -> Int
forall 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 :: v a -> v a
init (Vec IArray v a
arr Int
s Int
l)
    | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0    = v a
forall a. HasCallStack => a
errorEmptyVector
    | Bool
otherwise = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s (Int
lInt -> Int -> Int
forall 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 :: v a -> a
last (Vec IArray v a
arr Int
s Int
l)
    | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0    = a
forall a. HasCallStack => a
errorEmptyVector
    | Bool
otherwise = IArray v a -> Int -> a
forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> a
indexArr IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
lInt -> Int -> Int
forall 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 :: v a -> Int -> a
index (Vec IArray v a
arr Int
s Int
l) Int
i | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
l = Int -> a
forall a. HasCallStack => Int -> a
errorOutRange Int
i
                      | Bool
otherwise       = IArray v a
arr IArray v a -> Int -> a
forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> a
`indexArr` (Int
s Int -> Int -> Int
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 :: v a -> Int -> m a
indexM (Vec IArray v a
arr Int
s Int
l) Int
i | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
l = Int -> m a
forall a. HasCallStack => Int -> a
errorOutRange Int
i
                       | Bool
otherwise       = IArray v a
arr IArray v a -> Int -> m a
forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m) =>
arr a -> Int -> m a
`indexArrM` (Int
s Int -> Int -> Int
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 :: 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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
l = Int -> v a
forall a. HasCallStack => Int -> a
errorOutRange Int
i
                         | Bool
otherwise       = v a -> Int -> (a -> a) -> v a
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 :: 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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
l = v a
v
                                   | Bool
otherwise       = v a -> Int -> (a -> a) -> v a
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 :: v a -> Int -> a -> v a
insertIndex v :: v a
v@(Vec IArray v a
_ Int
_ Int
l) Int
i a
x | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
l = Int -> v a
forall a. HasCallStack => Int -> a
errorOutRange Int
i
                              | Bool
otherwise      = v a -> Int -> a -> v a
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 :: v a -> Int -> a -> v a
insertIndexMaybe v :: v a
v@(Vec IArray v a
_ Int
_ Int
l) Int
i a
x | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
l = v a
v
                                   | Bool
otherwise      = v a -> Int -> a -> v a
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 :: v a -> Int -> v a
deleteIndex v :: v a
v@(Vec IArray v a
_ Int
_ Int
l) Int
i | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
l = Int -> v a
forall a. HasCallStack => Int -> a
errorOutRange Int
i
                            | Bool
otherwise       = v a -> Int -> v a
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 :: v a -> Int -> v a
deleteIndexMaybe v :: v a
v@(Vec IArray v a
_ Int
_ Int
l) Int
i | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
l = v a
v
                                 | Bool
otherwise       = v a -> Int -> v a
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 :: v a -> a
unsafeHead (Vec IArray v a
arr Int
s Int
l) = Bool -> a -> a
forall a. HasCallStack => Bool -> a -> a
assert (Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0) (IArray v a -> Int -> a
forall (arr :: * -> *) a. Arr arr a => 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 :: v a -> v a
unsafeTail (Vec IArray v a
arr Int
s Int
l) = Bool -> v a -> v a
forall a. HasCallStack => Bool -> a -> a
assert (Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0) (IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
lInt -> Int -> Int
forall 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 :: v a -> v a
unsafeInit (Vec IArray v a
arr Int
s Int
l) = Bool -> v a -> v a
forall a. HasCallStack => Bool -> a -> a
assert (Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0) (IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr Int
s (Int
lInt -> Int -> Int
forall 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 :: v a -> a
unsafeLast (Vec IArray v a
arr Int
s Int
l) = Bool -> a -> a
forall a. HasCallStack => Bool -> a -> a
assert (Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0) (IArray v a -> Int -> a
forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> a
indexArr IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
lInt -> Int -> Int
forall 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 :: v a -> Int -> a
unsafeIndex (Vec IArray v a
arr Int
s Int
_) Int
i = IArray v a -> Int -> a
forall (arr :: * -> *) a. Arr arr a => arr a -> Int -> a
indexArr IArray v a
arr (Int
s Int -> Int -> Int
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 :: v a -> Int -> m a
unsafeIndexM (Vec IArray v a
arr Int
s Int
_) Int
i = IArray v a -> Int -> m a
forall (arr :: * -> *) a (m :: * -> *).
(Arr arr a, Monad m) =>
arr a -> Int -> m a
indexArrM IArray v a
arr (Int
s Int -> Int -> Int
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 :: v a -> Int -> (a -> a) -> v a
unsafeModifyIndex (Vec IArray v a
arr Int
s Int
l) Int
i a -> a
f = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec (IArray v a -> Int -> Int -> Int -> (a -> a) -> IArray v a
forall (arr :: * -> *) a.
Arr arr a =>
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 :: v a -> Int -> a -> v a
unsafeInsertIndex (Vec IArray v a
arr Int
s Int
l) Int
i a
x = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec (IArray v a -> Int -> Int -> Int -> a -> IArray v a
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
lInt -> Int -> Int
forall 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 :: v a -> Int -> v a
unsafeDeleteIndex (Vec IArray v a
arr Int
s Int
l) Int
i = IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
Vec (IArray v a -> Int -> Int -> Int -> IArray v a
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
lInt -> Int -> Int
forall 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 :: Int -> v a -> v a
unsafeTake Int
n (Vec IArray v a
arr Int
s Int
l) = Bool -> v a -> v a
forall a. HasCallStack => Bool -> a -> a
assert (Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
n Bool -> Bool -> Bool
&& Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
l) (IArray v a -> Int -> Int -> v a
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 :: Int -> v a -> v a
unsafeDrop Int
n (Vec IArray v a
arr Int
s Int
l) = Bool -> v a -> v a
forall a. HasCallStack => Bool -> a -> a
assert (Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
n Bool -> Bool -> Bool
&& Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
l) (IArray v a -> Int -> Int -> v a
forall (v :: * -> *) a. Vec v a => IArray v a -> Int -> Int -> v a
fromArr IArray v a
arr (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
n) (Int
lInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
n))

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

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