NonEmpty.hs

{-# LANGUAGE NoImplicitPrelude #-}
{-# LANGUAGE Rank2Types #-}
{-# LANGUAGE Trustworthy #-}
-- |
-- Module       : Data.Vector.NonEmpty
-- Copyright 	: (c) 2019-2020 Emily Pillmore
-- License	: BSD-style
--
-- Maintainer	: Emily Pillmore <emilypi@cohomolo.gy>
-- Stability	: Experimental
-- Portability	: DataTypeable, CPP
--
-- A library for non-empty boxed vectors (that is, polymorphic arrays capable of
-- holding any Haskell value). Non-empty vectors come in two flavors:
--
--  * mutable
--
--  * immutable
--
-- This library attempts to provide support for all standard 'Vector' operations
-- in the API, with some slight variation in types and implementation. For example,
-- since 'head' and 'foldr' are always gauranteed to be over a non-empty 'Vector',
-- it is safe to make use of the 'unsafe-*' 'Vector' operations and semigroupal
-- folds available in the API in lieu of the standard implementations.
--
-- In contrast, some operations such as 'filter' may "break out" of a 'NonEmptyVector'
-- due to the fact that there are no guarantees that may be made on the types of
-- 'Bool'-valued functions passed in, hence one could write the following:
--
-- @
-- filter (const false) v
-- @
--
-- which always produces an empty vector. Thus, some operations must return either
-- a 'Maybe' containing a 'NonEmptyVector' or a 'Vector' whenever appropriate. Generally
-- The former is used in initialization and generation operations, and the latter
-- is used in iterative operations where the intent is not to create an instance
-- of 'NonEmptyVector'.
--
-- Credit to Roman Leshchinskiy for the original Vector library  upon which this is based.
--
module Data.Vector.NonEmpty
( -- * Boxed non-empty vectors
  NonEmptyVector

  -- * Accessors

  -- ** Length information
, length

  -- ** Indexing
, head, last, (!), (!?)
, unsafeIndex

  -- ** Monadic Indexing
, headM, lastM, indexM, unsafeIndexM

  -- ** Extracting subvectors (slicing)
, tail, slice, init, take, drop
, uncons, unsnoc, splitAt
, unsafeSlice, unsafeTake, unsafeDrop

  -- * Construction

  -- ** Initialization
, singleton
, replicate, replicate1
, generate, generate1
, iterateN, iterateN1

  -- ** Monad Initialization
, replicateM, replicate1M
, generateM, generate1M
, iterateNM, iterateN1M
, create, unsafeCreate
, createT, unsafeCreateT

  -- ** Unfolding
, unfoldr, unfoldr1
, unfoldrN, unfoldr1N
, unfoldrM, unfoldr1M
, unfoldrNM, unfoldr1NM
, constructN, constructrN

  -- ** Enumeration
, enumFromN, enumFromN1
, enumFromStepN, enumFromStepN1
, enumFromTo, enumFromThenTo

  -- ** Concatenation
, cons, consV, snoc, snocV, (++), concat, concat1

  -- ** Restricting memory usage
, force

  -- * Conversion

  -- ** To/from non-empty lists
, toNonEmpty, fromNonEmpty
, fromNonEmptyN, fromNonEmptyN1
, unsafeFromList

  -- ** To/from vector
, toVector, fromVector, unsafeFromVector

  -- ** To/from list
, toList, fromList, fromListN

  -- * Modifying non-empty vectors

  -- ** Bulk Updates
, (//), update, update_
, unsafeUpd, unsafeUpdate, unsafeUpdate_

  -- * Accumulations
, accum, accumulate, accumulate_
, unsafeAccum, unsafeAccumulate, unsafeAccumulate_

  -- * Permutations
, reverse, backpermute, unsafeBackpermute

  -- * Safe destructive updates
, modify

  -- * Elementwise operations

  -- ** Indexing
, indexed

  -- ** Mapping
, map, imap, concatMap

  -- ** Monadic mapping
, mapM, imapM, mapM_, imapM_
, forM, forM_

  -- ** Zipping
, zipWith, zipWith3, zipWith4, zipWith5, zipWith6
, izipWith, izipWith3, izipWith4, izipWith5, izipWith6
, zip, zip3, zip4, zip5, zip6

  -- ** Monadic Zipping
, zipWithM, zipWithM_, izipWithM, izipWithM_

  -- ** Unzipping
, unzip, unzip3, unzip4, unzip5, unzip6

  -- * Working with predicates

  -- ** Filtering
, uniq, mapMaybe, imapMaybe
, filter, ifilter, filterM, ifilterM
, takeWhile, dropWhile

  -- * Partitioning
, partition, partitionWith, unstablePartition, span, break

  -- * Searching
, elem, notElem, find, findIndex, findIndices, elemIndex
, elemIndices

  -- * Folding
, foldl, foldl1, foldl', foldl1'
, foldr, foldr1, foldr', foldr1'
, ifoldl, ifoldl', ifoldr, ifoldr'

  -- * Specialized folds
, all, any, and, or, sum, product
, maximum, maximumBy, minimum, minimumBy
, maxIndex, maxIndexBy, minIndex, minIndexBy

  -- * Monadic Folds
, foldM, foldM', fold1M, fold1M', foldM_, foldM'_, fold1M_
, fold1M'_, ifoldM, ifoldM', ifoldM_, ifoldM'_

  -- * Monadic Sequencing
, sequence, sequence_

  -- * Prefix sums (scans)
, prescanl, prescanl', postscanl, postscanl'
, scanl, scanl', scanl1, scanl1', iscanl, iscanl'
, prescanr, prescanr', postscanr, postscanr'
, scanr, scanr', scanr1, scanr1', iscanr, iscanr'
) where


import Prelude ( Bool, Eq, Ord, Num, Enum
               , (.), Ordering, max, uncurry, snd)

import Control.Monad (Monad)
import Control.Monad.ST

import qualified Data.Foldable as Foldable
import Data.Either (Either(..))
import Data.Functor
import Data.Int
import Data.List.NonEmpty (NonEmpty(..))
import qualified Data.List.NonEmpty as NonEmpty
import Data.Maybe (Maybe(..))
import Data.Semigroup (Semigroup(..), (<>))
import Data.Traversable (Traversable)
import Data.Vector (Vector)
import qualified Data.Vector as V
import qualified Data.Vector.Generic as G
import Data.Vector.Mutable (MVector)
import Data.Vector.NonEmpty.Internal


-- $setup
-- >>> import Prelude (Int, String, ($), (.), (+), (<), const, return)
-- >>> import Data.Bool
-- >>> import Data.Eq
-- >>> import qualified Prelude as P
-- >>> import qualified Data.Vector as V
-- >>> import Data.List.NonEmpty (NonEmpty(..))
-- >>> import qualified Data.List.NonEmpty as NEL
-- >>> :set -XTypeApplications
-- >>> :set -XScopedTypeVariables

-- ---------------------------------------------------------------------- --
-- Accessors + Indexing

-- | /O(1)/ Length.
--
-- >>> length $ unsafeFromList [1..10]
-- 10
--
length :: NonEmptyVector a -> Int
length = V.length . _neVec
{-# INLINE length #-}

-- | /O(1)/ First element. Since head is gauranteed, bounds checks
-- are bypassed by deferring to 'unsafeHead'.
--
--
-- >>> head $ unsafeFromList [1..10]
-- 1
--
head :: NonEmptyVector a -> a
head = V.unsafeHead . _neVec
{-# INLINE head #-}

-- | /O(1)/ Last element. Since a last element is gauranteed, bounds checks
-- are bypassed by deferring to 'unsafeLast'.
--
--
-- >>> last $ unsafeFromList [1..10]
-- 10
--
last :: NonEmptyVector a -> a
last = V.unsafeLast . _neVec
{-# INLINE last #-}

-- | /O(1)/ Indexing.
--
--
-- >>> (unsafeFromList [1..10]) ! 0
-- 1
--
(!) :: NonEmptyVector a -> Int -> a
(!) (NonEmptyVector as) n = as V.! n
{-# INLINE (!) #-}

-- | /O(1)/ Safe indexing.
--
--
-- >>> (unsafeFromList [1..10]) !? 0
-- Just 1
--
-- >>> (unsafeFromList [1..10]) !? 11
-- Nothing
--
(!?) :: NonEmptyVector a -> Int -> Maybe a
(NonEmptyVector as) !? n = as V.!? n
{-# INLINE (!?) #-}

-- | /O(1)/ Unsafe indexing without bounds checking
--
unsafeIndex :: NonEmptyVector a -> Int -> a
unsafeIndex (NonEmptyVector as) n = V.unsafeIndex as n
{-# INLINE unsafeIndex #-}

-- ---------------------------------------------------------------------- --
-- Monadic Indexing

-- | /O(1)/ Indexing in a monad.
--
-- The monad allows operations to be strict in the non-empty vector when
-- necessary.
--
-- See 'V.indexM' for more details
--
--
-- >>> indexM @[] (unsafeFromList [1..10]) 3
-- [4]
--
indexM :: Monad m => NonEmptyVector a -> Int -> m a
indexM (NonEmptyVector v) n = V.indexM v n
{-# INLINE indexM #-}

-- | /O(1)/ First element of a non-empty vector in a monad.
--
-- See 'V.indexM' for an explanation of why this is useful.
--
-- Note that this function defers to 'unsafeHeadM' since head is
-- gauranteed to be safe by construction.
--
--
-- >>> headM @[] (unsafeFromList [1..10])
-- [1]
--
headM :: Monad m => NonEmptyVector a -> m a
headM (NonEmptyVector v) = V.unsafeHeadM v
{-# INLINE headM #-}

-- | /O(1)/ Last element of a non-empty vector in a monad. See 'V.indexM' for an
-- explanation of why this is useful.
--
-- Note that this function defers to 'unsafeHeadM' since a last element is
-- gauranteed.
--
--
-- >>> lastM @[] (unsafeFromList [1..10])
-- [10]
--
lastM :: Monad m => NonEmptyVector a -> m a
lastM (NonEmptyVector v) = V.unsafeLastM v
{-# INLINE lastM #-}

-- | O(1) Indexing in a monad without bounds checks. See 'indexM' for an
-- explanation of why this is useful.
--
unsafeIndexM :: Monad m => NonEmptyVector a -> Int -> m a
unsafeIndexM (NonEmptyVector v) n = V.unsafeIndexM v n
{-# INLINE unsafeIndexM #-}

-- ---------------------------------------------------------------------- --
-- Extracting subvectors (slicing)

-- | /O(1)/ Yield all but the first element without copying. Since the
-- vector returned may be empty (i.e. input was a singleton), this function
-- returns a normal 'Vector'
--
--
-- >>> tail (unsafeFromList [1..10])
-- [2,3,4,5,6,7,8,9,10]
--
tail :: NonEmptyVector a -> Vector a
tail = V.unsafeTail . _neVec
{-# INLINE tail #-}

-- | /O(1)/ Yield a slice of a non-empty vector without copying at
-- the @0@th and @1@st indices.
--
--
-- >>> uncons (unsafeFromList [1..10])
-- (1,[2,3,4,5,6,7,8,9,10])
--
uncons :: NonEmptyVector a -> (a, Vector a)
uncons v = (head v, tail v)
{-# INLINE uncons #-}

-- | /O(1)/ Yield a slice of a non-empty vector without copying at
-- the @n-1@th and @nth@ indices
--
--
-- >>> unsnoc (unsafeFromList [1..10])
-- ([1,2,3,4,5,6,7,8,9],10)
--
unsnoc :: NonEmptyVector a -> (Vector a, a)
unsnoc v = (init v, last v)
{-# INLINE unsnoc #-}

-- | /O(1)/ Yield a slice of the non-empty vector without copying it.
-- The vector must contain at least i+n elements. Because this is not
-- guaranteed, this function returns a 'Vector' which could be empty
--
--
-- >>> slice 0 3 (unsafeFromList [1..10])
-- [1,2,3]
--
slice :: Int -> Int -> NonEmptyVector a -> Vector a
slice i n = V.slice i n . _neVec
{-# INLINE slice #-}

-- | /O(1)/ Yield all but the last element without copying. Since the
-- vector returned may be empty (i.e. input was a singleton), this function
-- returns a normal 'Vector'
--
--
-- >>> init (unsafeFromList [1..3])
-- [1,2]
--
init :: NonEmptyVector a -> Vector a
init = V.unsafeInit . _neVec
{-# INLINE init #-}

-- | /O(1)/ Yield at the first n elements without copying. The non-empty vector may
-- contain less than n elements in which case it is returned as a vector unchanged.
--
--
-- >>> take 2 (unsafeFromList [1..3])
-- [1,2]
--
take :: Int -> NonEmptyVector a -> Vector a
take n = V.take n . _neVec
{-# INLINE take #-}

-- | /O(1)/ Yield all but the first n elements without copying. The non-empty vector
-- may contain less than n elements in which case an empty vector is returned.
--
--
-- >>> drop 2 (unsafeFromList [1..3])
-- [3]
--
drop :: Int -> NonEmptyVector a -> Vector a
drop n = V.drop n . _neVec
{-# INLINE drop #-}

-- | /O(1)/ Yield the first n elements paired with the remainder without copying.
--
-- This function returns a pair of vectors, as one may slice a (0, n+1).
--
--
-- >>> splitAt 2 (unsafeFromList [1..3])
-- ([1,2],[3])
--
splitAt :: Int -> NonEmptyVector a -> (Vector a, Vector a)
splitAt n = V.splitAt n . _neVec
{-# INLINE splitAt #-}

-- | /O(1)/ Yield a slice of the vector without copying. The vector must contain at
-- least i+n elements but this is not checked.
--
unsafeSlice :: Int -> Int -> NonEmptyVector a -> Vector a
unsafeSlice i n = V.unsafeSlice i n . _neVec
{-# INLINE unsafeSlice #-}

-- | /O(1)/ Yield the first n elements without copying. The vector must contain at
-- least n elements but this is not checked.
--
unsafeTake :: Int -> NonEmptyVector a -> Vector a
unsafeTake n = V.unsafeTake n . _neVec
{-# INLINE unsafeTake #-}

-- | /O(1)/ Yield all but the first n elements without copying. The vector must contain
-- at least n elements but this is not checked.
--
unsafeDrop :: Int -> NonEmptyVector a -> Vector a
unsafeDrop n = V.unsafeDrop n . _neVec
{-# INLINE unsafeDrop #-}

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

-- | /O(1)/ Non-empty vector with exactly one element
--
--
-- >>> singleton "a"
-- ["a"]
--
singleton :: a -> NonEmptyVector a
singleton = NonEmptyVector . V.singleton
{-# INLINE singleton #-}

-- | /O(n)/ Non-empty vector of the given length with the same value in
-- each position.
--
-- When given a index n <= 0, then 'Nothing' is returned, otherwise 'Just'.
--
--
-- >>> replicate 3 "a"
-- Just ["a","a","a"]
--
-- >>> replicate 0 "a"
-- Nothing
--
replicate :: Int -> a -> Maybe (NonEmptyVector a)
replicate n a = fromVector (V.replicate n a)
{-# INLINE replicate #-}

-- | /O(n)/ Non-empty vector of the given length with the same value in
-- each position.
--
-- This variant takes @max n 1@ for the supplied length parameter.
--
--
-- >>> replicate1 3 "a"
-- ["a","a","a"]
--
-- >>> replicate1 0 "a"
-- ["a"]
--
-- >>> replicate1 (-1) "a"
-- ["a"]
--
replicate1 :: Int -> a -> NonEmptyVector a
replicate1 n a = unsafeFromVector (V.replicate (max n 1) a)
{-# INLINE replicate1 #-}

-- | /O(n)/ Construct a vector of the given length by applying the function to
-- each index.
--
-- When given a index n <= 0, then 'Nothing' is returned, otherwise 'Just'.
--
--
-- >>> let f 0 = "a"; f _ = "k"; f :: Int -> String
--
-- >>> generate 1 f
-- Just ["a"]
--
-- >>> generate 0 f
-- Nothing
--
-- >>> generate 2 f
-- Just ["a","k"]
--
generate :: Int -> (Int -> a) -> Maybe (NonEmptyVector a)
generate n f = fromVector (V.generate n f)
{-# INLINE generate #-}

-- | /O(n)/ Construct a vector of the given length by applying the function to
-- each index.
--
-- This variant takes @max n 1@ for the supplied length parameter.
--
--
-- >>> let f 0 = "a"; f _ = "k"; f :: Int -> String
--
-- >>> generate1 2 f
-- ["a","k"]
--
-- >>> generate1 0 f
-- ["a"]
--
-- >>> generate1 (-1) f
-- ["a"]
--
generate1 :: Int -> (Int -> a) -> NonEmptyVector a
generate1 n f = unsafeFromVector (V.generate (max n 1) f)
{-# INLINE generate1 #-}

-- | /O(n)/ Apply function n times to value. Zeroth element is original value.
--
-- When given a index n <= 0, then 'Nothing' is returned, otherwise 'Just'.
--
-- >>> iterateN 3 (+1) 0
-- Just [0,1,2]
--
-- >>> iterateN 0 (+1) 0
-- Nothing
--
-- >>> iterateN (-1) (+1) 0
-- Nothing
--
iterateN :: Int -> (a -> a) -> a -> Maybe (NonEmptyVector a)
iterateN n f a = fromVector (V.iterateN n f a)
{-# INLINE iterateN #-}

-- | /O(n)/ Apply function n times to value. Zeroth element is original value.
--
-- This variant takes @max n 1@ for the supplied length parameter.
--
--
-- >>> iterateN1 3 (+1) 0
-- [0,1,2]
--
-- >>> iterateN1 0 (+1) 0
-- [0]
--
-- >>> iterateN1 (-1) (+1) 0
-- [0]
--
iterateN1 :: Int -> (a -> a) -> a -> NonEmptyVector a
iterateN1 n f a = unsafeFromVector (V.iterateN (max n 1) f a)
{-# INLINE iterateN1 #-}

-- ---------------------------------------------------------------------- --
-- Monadic Initialization

-- | /O(n)/ Execute the monadic action the given number of times and store
-- the results in a vector.
--
-- When given a index n <= 0, then 'Nothing' is returned, otherwise 'Just'.
--
--
-- >>> replicateM @Maybe 3 (Just "a")
-- Just (Just ["a","a","a"])
--
-- >>> replicateM @Maybe 3 Nothing
-- Nothing
--
-- >>> replicateM @Maybe 0 (Just "a")
-- Just Nothing
--
-- >>> replicateM @Maybe (-1) (Just "a")
-- Just Nothing
--
replicateM :: Monad m => Int -> m a -> m (Maybe (NonEmptyVector a))
replicateM n a = fmap fromVector (V.replicateM n a)
{-# INLINE replicateM #-}

-- | /O(n)/ Execute the monadic action the given number of times and store
-- the results in a vector.
--
-- This variant takes @max n 1@ for the supplied length parameter.
--
--
-- >>> replicate1M @Maybe 3 (Just "a")
-- Just ["a","a","a"]
--
-- >>> replicate1M @Maybe 3 Nothing
-- Nothing
--
-- >>> replicate1M @Maybe 0 (Just "a")
-- Just ["a"]
--
-- >>> replicate1M @Maybe (-1) (Just "a")
-- Just ["a"]
--
replicate1M :: Monad m => Int -> m a -> m (NonEmptyVector a)
replicate1M n a = fmap unsafeFromVector (V.replicateM (max n 1) a)
{-# INLINE replicate1M #-}

-- | /O(n)/ Construct a vector of the given length by applying the monadic
-- action to each index
--
-- When given a index n <= 0, then 'Nothing' is returned, otherwise 'Just'.
--
-- >>> generateM 3 (\i -> if i P.< 1 then ["a"] else ["b"])
-- [Just ["a","b","b"]]
--
-- >>> generateM @[] @Int 3 (const [])
-- []
--
-- >>> generateM @[] @Int 0 (const [1])
-- [Nothing]
--
-- >>> generateM @Maybe @Int (-1) (const Nothing)
-- Just Nothing
--
generateM :: Monad m => Int -> (Int -> m a) -> m (Maybe (NonEmptyVector a))
generateM n f = fmap fromVector (V.generateM n f)
{-# INLINE generateM #-}

-- | /O(n)/ Construct a vector of the given length by applying the monadic
-- action to each index
--
-- This variant takes @max n 1@ for the supplied length parameter.
--
-- >>> generate1M 3 (\i -> if i P.< 1 then Just "a" else Just "b")
-- Just ["a","b","b"]
--
-- >>> generate1M 3 (const [])
-- []
--
-- >>> generate1M 0 (const $ Just 1)
-- Just [1]
--
-- >>> generate1M (-1) (const Nothing)
-- Nothing
--
generate1M :: Monad m => Int -> (Int -> m a) -> m (NonEmptyVector a)
generate1M n f = fmap unsafeFromVector (V.generateM (max n 1) f)
{-# INLINE generate1M #-}

-- | /O(n)/ Apply monadic function n times to value. Zeroth element is
-- original value.
--
-- When given a index n <= 0, then 'Nothing' is returned, otherwise 'Just'.
--
--
-- >>> iterateNM @Maybe 3 return "a"
-- Just (Just ["a","a","a"])
--
-- >>> iterateNM @Maybe 3 (const Nothing) "a"
-- Nothing
--
-- >>> iterateNM @Maybe 0 return "a"
-- Just Nothing
--
iterateNM :: Monad m => Int -> (a -> m a) -> a -> m (Maybe (NonEmptyVector a))
iterateNM n f a = fmap fromVector (V.iterateNM n f a)
{-# INLINE iterateNM #-}

-- | /O(n)/ Apply monadic function n times to value. Zeroth element is
-- original value.
--
-- This variant takes @max n 1@ for the supplied length parameter.
--
--
-- >>> iterateN1M @Maybe 3 return "a"
-- Just ["a","a","a"]
--
-- >>> iterateN1M @Maybe 3 (const Nothing) "a"
-- Nothing
--
-- >>> iterateN1M @Maybe 0 return "a"
-- Just ["a"]
--
-- >>> iterateN1M @Maybe (-1) return "a"
-- Just ["a"]
--
iterateN1M :: Monad m => Int -> (a -> m a) -> a -> m (NonEmptyVector a)
iterateN1M n f a = fmap unsafeFromVector (V.iterateNM (max n 1) f a)
{-# INLINE iterateN1M #-}

-- | Execute the monadic action and freeze the resulting non-empty vector.
--
create :: (forall s. ST s (MVector s a)) -> Maybe (NonEmptyVector a)
create p = fromVector (G.create p)
{-# INLINE create #-}

-- | Execute the monadic action and freeze the resulting non-empty vector,
-- bypassing emptiness checks.
--
-- The onus is on the caller to guarantee the created vector is non-empty.
--
unsafeCreate :: (forall s. ST s (MVector s a)) -> NonEmptyVector a
unsafeCreate p = unsafeFromVector (G.create p)
{-# INLINE unsafeCreate #-}

-- | Execute the monadic action and freeze the resulting non-empty vector.
--
createT
    :: Traversable t
    => (forall s. ST s (t (MVector s a)))
    -> t (Maybe (NonEmptyVector a))
createT p = fmap fromVector (G.createT p)
{-# INLINE createT #-}

-- | Execute the monadic action and freeze the resulting non-empty vector.
--
-- The onus is on the caller to guarantee the created vector is non-empty.
--
unsafeCreateT
    :: Traversable t
    => (forall s. ST s (t (MVector s a)))
    -> t (NonEmptyVector a)
unsafeCreateT p = fmap unsafeFromVector (G.createT p)
{-# INLINE unsafeCreateT #-}

-- ---------------------------------------------------------------------- --
-- Unfolding

-- | /O(n)/ Construct a non-empty vector by repeatedly applying the
-- generator function to a seed. The generator function yields 'Just' the
-- next element and the new seed or 'Nothing' if there are no more
-- elements.
--
-- If an unfold does not create meaningful values, 'Nothing' is
-- returned. Otherwise, 'Just' containing a non-empty vector is returned.
--
--
-- >>> unfoldr (\b -> case b of "a" -> Just ("a", "b"); _ ->  Nothing) "a"
-- Just ["a"]
--
-- >>> unfoldr (const Nothing) "a"
-- Nothing
--
unfoldr :: (b -> Maybe (a, b)) -> b -> Maybe (NonEmptyVector a)
unfoldr f b = fromVector (V.unfoldr f b)
{-# INLINE unfoldr #-}

-- | /O(n)/ Construct a non-empty vector by repeatedly applying the
-- generator function to a seed and a first element.
--
-- This variant of 'unfoldr' guarantees the resulting vector is non-
-- empty by supplying an initial element @a@.
--
--
-- >>> unfoldr1 (\b -> case b of "a" -> Just ("a", "b"); _ ->  Nothing) "first" "a"
-- ["first","a"]
--
-- >>> unfoldr1 (const Nothing) "first" "a"
-- ["first"]
--
unfoldr1 :: (b -> Maybe (a, b)) -> a -> b -> NonEmptyVector a
unfoldr1 f a b = cons a (unsafeFromVector (V.unfoldr f b))
{-# INLINE unfoldr1 #-}

-- | /O(n)/ Construct a vector with at most n elements by repeatedly
-- applying the generator function to a seed. The generator function yields
-- 'Just' the next element and the new seed or 'Nothing' if there are no
-- more elements.
--
-- If an unfold does not create meaningful values, 'Nothing' is
-- returned. Otherwise, 'Just' containing a non-empty vector is returned.
--
--
-- >>> unfoldrN 3 (\b -> Just (b+1, b+1)) 0
-- Just [1,2,3]
--
-- >>> unfoldrN 3 (const Nothing) 0
-- Nothing
--
-- >>> unfoldrN 0 (\b -> Just (b+1, b+1)) 0
-- Nothing
--
unfoldrN :: Int -> (b -> Maybe (a, b)) -> b -> Maybe (NonEmptyVector a)
unfoldrN n f b = fromVector (V.unfoldrN n f b)
{-# INLINE unfoldrN #-}

-- | /O(n)/ Construct a vector with at most n elements by repeatedly
-- applying the generator function to a seed. The generator function yields
-- 'Just' the next element and the new seed or 'Nothing' if there are no
-- more elements.
--
-- This variant of 'unfoldrN' guarantees the resulting vector is non-
-- empty by supplying an initial element @a@.
--
--
-- >>> unfoldr1N 3 (\b -> Just (b+1, b+1)) 0 0
-- [0,1,2,3]
--
-- >>> unfoldr1N 3 (const Nothing) 0 0
-- [0]
--
-- >>> unfoldr1N 0 (\b -> Just (b+1, b+1)) 0 0
-- [0]
--
unfoldr1N
    :: Int
    -> (b -> Maybe (a, b))
    -> a
    -> b
    -> NonEmptyVector a
unfoldr1N n f a b = cons a (unsafeFromVector (V.unfoldrN n f b))
{-# INLINE unfoldr1N #-}

-- | /O(n)/ Construct a non-empty vector by repeatedly applying the monadic generator
-- function to a seed. The generator function yields Just the next element
-- and the new seed or Nothing if there are no more elements.
--
-- If an unfold does not create meaningful values, 'Nothing' is
-- returned. Otherwise, 'Just' containing a non-empty vector is returned.
--
unfoldrM
    :: Monad m
    => (b -> m (Maybe (a, b)))
    -> b
    -> m (Maybe (NonEmptyVector a))
unfoldrM f b = fmap fromVector (V.unfoldrM f b)
{-# INLINE unfoldrM #-}

-- | /O(n)/ Construct a non-empty vector by repeatedly applying the monadic generator
-- function to a seed. The generator function yields Just the next element
-- and the new seed or Nothing if there are no more elements.
--
-- This variant of 'unfoldrM' guarantees the resulting vector is non-
-- empty by supplying an initial element @a@.
--
unfoldr1M
    :: Monad m
    => (b -> m (Maybe (a, b)))
    -> a
    -> b
    -> m (NonEmptyVector a)
unfoldr1M f a b = fmap (cons a . unsafeFromVector) (V.unfoldrM f b)
{-# INLINE unfoldr1M #-}

-- | /O(n)/ Construct a non-empty vector by repeatedly applying the monadic generator
-- function to a seed. The generator function yields Just the next element and
-- the new seed or Nothing if there are no more elements.
--
-- If an unfold does not create meaningful values, 'Nothing' is
-- returned. Otherwise, 'Just' containing a non-empty vector is returned.
--
unfoldrNM
    :: Monad m
    => Int
    -> (b -> m (Maybe (a, b)))
    -> b
    -> m (Maybe (NonEmptyVector a))
unfoldrNM n f b = fmap fromVector (V.unfoldrNM n f b)
{-# INLINE unfoldrNM #-}

-- | /O(n)/ Construct a non-empty vector by repeatedly applying the monadic generator
-- function to a seed. The generator function yields Just the next element and
-- the new seed or Nothing if there are no more elements.
--
-- This variant of 'unfoldrNM' guarantees the resulting vector is non-
-- empty by supplying an initial element @a@.
--
unfoldr1NM
    :: Monad m
    => Int
    -> (b -> m (Maybe (a, b)))
    -> a
    -> b
    -> m (NonEmptyVector a)
unfoldr1NM n f a b = fmap (cons a . unsafeFromVector) (V.unfoldrNM n f b)
{-# INLINE unfoldr1NM #-}

-- | /O(n)/ Construct a non-empty vector with n elements by repeatedly applying the
-- generator function to the already constructed part of the vector.
--
-- If 'constructN' does not create meaningful values, 'Nothing' is
-- returned. Otherwise, 'Just' containing a non-empty vector is returned.
--
constructN :: Int -> (Vector a -> a) -> Maybe (NonEmptyVector a)
constructN n f = fromVector (V.constructN n f)
{-# INLINE constructN #-}

-- | /O(n)/ Construct a vector with n elements from right to left by repeatedly
-- applying the generator function to the already constructed part of the vector.
--
-- If 'constructrN' does not create meaningful values, 'Nothing' is
-- returned. Otherwise, 'Just' containing a non-empty vector is returned.
--
constructrN :: Int -> (Vector a -> a) -> Maybe (NonEmptyVector a)
constructrN n f = fromVector (V.constructrN n f)
{-# INLINE constructrN #-}

-- ---------------------------------------------------------------------- --
-- Enumeration

-- | /O(n)/ Yield a non-emptyvector of the given length containing the
-- values x, x+1 etc. This operation is usually more efficient than
-- 'enumFromTo'.
--
-- If an enumeration does not use meaningful indices, 'Nothing' is returned,
-- otherwise, 'Just' containing a non-empty vector.
--
enumFromN :: Num a => a -> Int -> Maybe (NonEmptyVector a)
enumFromN a n = fromVector (V.enumFromN a n)
{-# INLINE enumFromN #-}

-- | /O(n)/ Yield a non-emptyvector of length @max n 1@ containing the
-- values x, x+1 etc. This operation is usually more efficient than
-- 'enumFromTo'.
--
enumFromN1 :: Num a => a -> Int -> NonEmptyVector a
enumFromN1 a n = unsafeFromVector (V.enumFromN a (max n 1))
{-# INLINE enumFromN1 #-}

-- | /O(n)/ Yield a non-empty vector of the given length containing the
-- values x, x+y, x+y+y etc. This operations is usually more efficient than
-- 'enumFromThenTo'.
--
-- If an enumeration does not use meaningful indices, 'Nothing' is returned,
-- otherwise, 'Just' containing a non-empty vector.
--
enumFromStepN :: Num a => a -> a -> Int -> Maybe (NonEmptyVector a)
enumFromStepN a0 a1 n = fromVector (V.enumFromStepN a0 a1 n)
{-# INLINE enumFromStepN #-}

-- | /O(n)/ Yield a non-empty vector of length @max n 1@ containing the
-- values x, x+y, x+y+y etc. This operations is usually more efficient than
-- 'enumFromThenTo'.
--
enumFromStepN1 :: Num a => a -> a -> Int -> NonEmptyVector a
enumFromStepN1 a0 a1 n = unsafeFromVector (V.enumFromStepN a0 a1 (max n 1))
{-# INLINE enumFromStepN1 #-}

-- | /O(n)/ Enumerate values from x to y.
--
-- If an enumeration does not use meaningful indices, 'Nothing' is returned,
-- otherwise, 'Just' containing a non-empty vector.
--
-- /WARNING/: This operation can be very inefficient. If at all possible,
-- use 'enumFromN' instead.
--
--
enumFromTo :: Enum a => a -> a -> Maybe (NonEmptyVector a)
enumFromTo a0 a1 = fromVector (V.enumFromTo a0 a1)
{-# INLINE enumFromTo #-}

-- | /O(n)/ Enumerate values from x to y with a specific step z.
--
-- If an enumeration does not use meaningful indices, 'Nothing' is returned,
-- otherwise, 'Just' containing a non-empty vector.
--
-- /WARNING/: This operation can be very inefficient. If at all possible,
-- use 'enumFromStepN' instead.
enumFromThenTo :: Enum a => a -> a -> a -> Maybe (NonEmptyVector a)
enumFromThenTo a0 a1 a2 = fromVector (V.enumFromThenTo a0 a1 a2)
{-# INLINE enumFromThenTo #-}

-- ---------------------------------------------------------------------- --
-- Concatenation

-- | /O(n)/ Prepend an element
--
-- >>> cons 1 (unsafeFromList [2,3])
-- [1,2,3]
--
cons :: a -> NonEmptyVector a -> NonEmptyVector a
cons a (NonEmptyVector as) = consV a as
{-# INLINE cons #-}

-- | /O(n)/ Prepend an element to a Vector
--
-- >>> consV 1 (V.fromList [2,3])
-- [1,2,3]
--
consV :: a -> Vector a -> NonEmptyVector a
consV a = NonEmptyVector . V.cons a
{-# INLINE consV #-}

-- | /O(n)/ Append an element
--
-- >>> snoc (unsafeFromList [1,2]) 3
-- [1,2,3]
--
snoc :: NonEmptyVector a -> a -> NonEmptyVector a
snoc (NonEmptyVector as) = snocV as
{-# INLINE snoc #-}

-- | /O(n)/ Append an element to a Vector
--
-- >>> snocV (V.fromList [1,2]) 3
-- [1,2,3]
--
snocV :: Vector a -> a -> NonEmptyVector a
snocV as = NonEmptyVector . V.snoc as
{-# INLINE snocV #-}

-- | /O(m+n)/ Concatenate two non-empty vectors
--
-- >>> (unsafeFromList [1..3]) ++ (unsafeFromList [4..6])
-- [1,2,3,4,5,6]
--
(++) :: NonEmptyVector a -> NonEmptyVector a -> NonEmptyVector a
NonEmptyVector v ++ NonEmptyVector v' = NonEmptyVector (v <> v')
{-# INLINE (++) #-}

-- | /O(n)/ Concatenate all non-empty vectors in the list
--
-- If list is empty, 'Nothing' is returned, otherwise 'Just'
-- containing the concatenated non-empty vectors
--
-- >>> concat [(unsafeFromList [1..3]), (unsafeFromList [4..6])]
-- Just [1,2,3,4,5,6]
--
concat :: [NonEmptyVector a] -> Maybe (NonEmptyVector a)
concat [] = Nothing
concat (a:as) = Just (concat1 (a :| as))
{-# INLINE concat #-}

-- | O(n) Concatenate all non-empty vectors in a non-empty list.
--
-- >>> concat1 ((unsafeFromList [1..3]) :| [(unsafeFromList [4..6])])
-- [1,2,3,4,5,6]
--
concat1 :: NonEmpty (NonEmptyVector a) -> NonEmptyVector a
concat1 = NonEmptyVector . Foldable.foldl' go V.empty
  where
    go v (NonEmptyVector a) = v <> a
{-# INLINE concat1 #-}

-- ---------------------------------------------------------------------- --
-- Conversions

-- | /O(n)/ Convert a non-empty vector to a non-empty list.
--
-- >>> toNonEmpty (unsafeFromList [1..3])
-- 1 :| [2,3]
--
toNonEmpty :: NonEmptyVector a -> NonEmpty a
toNonEmpty = NonEmpty.fromList . V.toList . _neVec
{-# INLINE toNonEmpty #-}

-- | O(n) Convert from a non-empty list to a non-empty vector.
--
-- >>> fromNonEmpty (1 :| [2,3])
-- [1,2,3]
--
fromNonEmpty :: NonEmpty a -> NonEmptyVector a
fromNonEmpty = NonEmptyVector . V.fromList . Foldable.toList
{-# INLINE fromNonEmpty #-}

-- | O(n) Convert from the first n-elements of a non-empty list to a
-- non-empty vector.
--
-- Returns 'Nothing' if indices are <= 0, otherwise 'Just' containing
-- the non-empty vector.
--
-- >>> fromNonEmptyN 3 (1 :| [2..5])
-- Just [1,2,3]
--
-- >>> fromNonEmptyN 0 (1 :| [2..5])
-- Nothing
--
fromNonEmptyN :: Int -> NonEmpty a -> Maybe (NonEmptyVector a)
fromNonEmptyN n a = fromVector (V.fromListN n (Foldable.toList a))
{-# INLINE fromNonEmptyN #-}

-- | O(n) Convert from the first n-elements of a non-empty list to a
-- non-empty vector. This is a safe version of `fromNonEmptyN` which
-- takes @max n 1@ of the first n-elements of the non-empty list.
--
--
-- >>> fromNonEmptyN1 3 (1 :| [2..5])
-- [1,2,3]
--
-- >>> fromNonEmptyN1 0 (1 :| [2..5])
-- [1]
--
fromNonEmptyN1 :: Int -> NonEmpty a -> NonEmptyVector a
fromNonEmptyN1 n = unsafeFromVector
    . V.fromListN (max n 1)
    . Foldable.toList
{-# INLINE fromNonEmptyN1 #-}

-- | /O(1)/ Convert from a non-empty vector to a vector.
--
--
-- >>> let nev :: NonEmptyVector Int = unsafeFromList [1..3] in toVector nev
-- [1,2,3]
--
toVector :: NonEmptyVector a -> Vector a
toVector = _neVec
{-# INLINE toVector #-}

-- | /O(1)/ Convert from a vector to a non-empty vector.
--
-- If the vector is empty, then 'Nothing' is returned,
-- otherwise 'Just' containing the non-empty vector.
--
-- >>> fromVector $ V.fromList [1..3]
-- Just [1,2,3]
--
-- >>> fromVector $ V.fromList []
-- Nothing
--
fromVector :: Vector a -> Maybe (NonEmptyVector a)
fromVector v = if V.null v then Nothing else Just (NonEmptyVector v)
{-# INLINE fromVector #-}

-- | /O(1)/ Convert from a vector to a non-empty vector without
-- checking bounds.
--
-- /Warning/: the onus is on the user to ensure that their vector
-- is not empty, otherwise all bets are off!
--
--
-- >>> unsafeFromVector $ V.fromList [1..3]
-- [1,2,3]
--
unsafeFromVector :: Vector a -> NonEmptyVector a
unsafeFromVector = NonEmptyVector
{-# INLINE unsafeFromVector #-}

-- | /O(n)/ Convert from a non-empty vector to a list.
--
--
-- >>> let nev :: NonEmptyVector Int = unsafeFromList [1..3] in toList nev
-- [1,2,3]
--
toList :: NonEmptyVector a -> [a]
toList = V.toList . _neVec
{-# INLINE toList #-}

-- | /O(n)/ Convert from a list to a non-empty vector.
--
--
-- >>> fromList [1..3]
-- Just [1,2,3]
--
-- >>> fromList []
-- Nothing
--
fromList :: [a] -> Maybe (NonEmptyVector a)
fromList = fromVector . V.fromList
{-# INLINE fromList #-}

-- | /O(n)/ Convert from a list to a non-empty vector.
--
-- /Warning/: the onus is on the user to ensure that their vector
-- is not empty, otherwise all bets are off!
--
-- >>> unsafeFromList [1..3]
-- [1,2,3]
--
unsafeFromList :: [a] -> NonEmptyVector a
unsafeFromList = unsafeFromVector . V.fromList
{-# INLINE unsafeFromList #-}

-- | /O(n)/ Convert the first n elements of a list to a non-empty vector.
--
-- If the list is empty or <= 0 elements are chosen, 'Nothing' is
-- returned, otherwise 'Just' containing the non-empty vector
--
-- >>> fromListN 3 [1..5]
-- Just [1,2,3]
--
-- >>> fromListN 3 []
-- Nothing
--
-- >>> fromListN 0 [1..5]
-- Nothing
--
fromListN :: Int -> [a] -> Maybe (NonEmptyVector a)
fromListN n as = fromVector (V.fromListN n as)
{-# INLINE fromListN #-}

-- ---------------------------------------------------------------------- --
-- Restricting memory usage

-- | /O(n)/ Yield the argument but force it not to retain any extra memory,
-- possibly by copying it.
--
force :: NonEmptyVector a -> NonEmptyVector a
force (NonEmptyVector a) = NonEmptyVector (V.force a)
{-# INLINE force #-}

-- ---------------------------------------------------------------------- --
-- Bulk Updates

-- | /O(m+n)/ For each pair (i,a) from the list, replace the non-empty vector
-- element at position i by a.
--
-- >>> unsafeFromList [1..3] // [(2,4)]
-- [1,2,4]
--
-- >>> unsafeFromList [1..3] // []
-- [1,2,3]
--
(//) :: NonEmptyVector a -> [(Int, a)] -> NonEmptyVector a
NonEmptyVector v // us = NonEmptyVector (v V.// us)
{-# INLINE (//) #-}

-- | O(m+n) For each pair (i,a) from the vector of index/value pairs,
-- replace the vector element at position i by a.
--
-- >>> unsafeFromList [1..3] `update` V.fromList [(2,4)]
-- [1,2,4]
--
-- >>> unsafeFromList [1..3] `update` V.empty
-- [1,2,3]
--
update :: NonEmptyVector a -> Vector (Int, a) -> NonEmptyVector a
update (NonEmptyVector v) v' = NonEmptyVector (V.update v v')
{-# INLINE update #-}

-- | /O(m+min(n1,n2))/ For each index i from the index vector and the
-- corresponding value a from the value vector, replace the element of
-- the initial vector at position i by a.
--
--
-- >>> update_ (unsafeFromList [1..3]) (V.fromList [2]) (V.fromList [4])
-- [1,2,4]
--
-- >>> update_ (unsafeFromList [1..3]) V.empty V.empty
-- [1,2,3]
--
update_ :: NonEmptyVector a -> Vector Int -> Vector a -> NonEmptyVector a
update_ (NonEmptyVector v) is as = NonEmptyVector (V.update_ v is as)
{-# INLINE update_ #-}

-- | Same as '(//)' but without bounds checking.
--
unsafeUpd :: NonEmptyVector a -> [(Int, a)] -> NonEmptyVector a
unsafeUpd (NonEmptyVector v) us = NonEmptyVector (V.unsafeUpd v us)
{-# INLINE unsafeUpd #-}

-- | Same as 'update' but without bounds checking.
--
unsafeUpdate :: NonEmptyVector a -> Vector (Int, a) -> NonEmptyVector a
unsafeUpdate (NonEmptyVector v) us = NonEmptyVector (V.unsafeUpdate v us)
{-# INLINE unsafeUpdate #-}

-- | Same as 'update_' but without bounds checking.
--
unsafeUpdate_ :: NonEmptyVector a -> Vector Int -> Vector a -> NonEmptyVector a
unsafeUpdate_ (NonEmptyVector v) is as = NonEmptyVector (V.unsafeUpdate_ v is as)
{-# INLINE unsafeUpdate_ #-}

-- ---------------------------------------------------------------------- --
-- Accumulation

-- | /O(m+n)/ For each pair @(i,b)@ from the non-empty list, replace the
-- non-empty vector element @a@ at position @i@ by @f a b@.
--
--
-- >>> accum (+) (unsafeFromList [1..3]) [(2,10)]
-- [1,2,13]
--
-- >>> accum (+) (unsafeFromList [1..3]) []
-- [1,2,3]
--
accum
    :: (a -> b -> a)
      -- ^ accumulating function @f@
    -> NonEmptyVector a
      -- ^ initial non-empty vector (of length @m@)
    -> [(Int, b)]
      -- ^ list of index/value pairs (of length @n@)
    -> NonEmptyVector a
accum f (NonEmptyVector v) u = NonEmptyVector (V.accum f v u)
{-# INLINE accum #-}

-- | /O(m+n)/ For each pair @(i,b)@ from the vector of pairs, replace the
-- non-empty vector element @a@ at position @i@ by @f a b@.
--
-- >>> accumulate (+) (unsafeFromList [1..3]) (V.fromList [(2,10)])
-- [1,2,13]
--
-- >>> accumulate (+) (unsafeFromList [1..3]) V.empty
-- [1,2,3]
--
accumulate
    :: (a -> b -> a)
      -- ^ accumulating function @f@
    -> NonEmptyVector a
      -- ^ initial non-empty vector (of length @m@)
    -> Vector (Int, b)
      -- ^ vector of index/value pairs (of length @n@)
    -> NonEmptyVector a
accumulate f (NonEmptyVector v) u = NonEmptyVector (V.accumulate f v u)
{-# INLINE accumulate #-}

-- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the
-- corresponding value @b@ from the the value vector, replace the element
-- of the initial non-empty vector at position @i@ by @f a b@.
--
-- >>> accumulate_ (+) (unsafeFromList [1..3]) (V.fromList [2]) (V.fromList [10])
-- [1,2,13]
--
-- >>> accumulate_ (+) (unsafeFromList [1..3]) V.empty V.empty
-- [1,2,3]
--
accumulate_
    :: (a -> b -> a)
      -- ^ accumulating function @f@
    -> NonEmptyVector a
      -- ^ initial non-empty vector (of length @m@)
    -> Vector Int
       -- ^ vector of indices (of length @n1@)
    -> Vector b
       -- ^ vector of values (of length @n2@)
    -> NonEmptyVector a
accumulate_ f (NonEmptyVector v) i b = NonEmptyVector (V.accumulate_ f v i b)
{-# INLINE accumulate_ #-}

-- | Same as 'accum' but without bounds checking.
--
unsafeAccum
    :: (a -> b -> a)
      -- ^ accumulating function @f@
    -> NonEmptyVector a
      -- ^ initial non-empty vector (of length @m@)
    -> [(Int, b)]
      -- ^ list of index/value pairs (of length @n@)
    -> NonEmptyVector a
unsafeAccum f (NonEmptyVector v) u = NonEmptyVector (V.unsafeAccum f v u)
{-# INLINE unsafeAccum #-}

-- | Same as 'accumulate' but without bounds checking.
--
unsafeAccumulate
    :: (a -> b -> a)
      -- ^ accumulating function @f@
    -> NonEmptyVector a
      -- ^ initial non-empty vector (of length @m@)
    -> Vector (Int, b)
      -- ^ vector of index/value pairs (of length @n@)
    -> NonEmptyVector a
unsafeAccumulate f v u = NonEmptyVector (V.unsafeAccumulate f v' u)
  where
    v' = _neVec v
{-# INLINE unsafeAccumulate #-}

-- | Same as 'accumulate_' but without bounds checking.
--
unsafeAccumulate_
    :: (a -> b -> a)
      -- ^ accumulating function @f@
    -> NonEmptyVector a
      -- ^ initial non-empty vector (of length @m@)
    -> Vector Int
      -- ^ vector of indices of length @n1@
    -> Vector b
      -- ^ vector of values (of length @n2@)
    -> NonEmptyVector a
unsafeAccumulate_ f v i b = NonEmptyVector (V.unsafeAccumulate_ f v' i b)
  where
    v' = _neVec v
{-# INLINE unsafeAccumulate_ #-}

-- ---------------------------------------------------------------------- --
-- Permutations

-- | /O(n)/ Reverse a non-empty vector
--
-- >>> reverse $ unsafeFromList [1..3]
-- [3,2,1]
--
reverse :: NonEmptyVector a -> NonEmptyVector a
reverse = NonEmptyVector . V.reverse . _neVec
{-# INLINE reverse #-}

-- | /O(n)/ Yield the non-empty vector obtained by replacing each element
-- @i@ of the non-empty index vector by @xs'!'i@. This is equivalent to
-- @'map' (xs'!') is@ but is often much more efficient.
--
-- >>> backpermute (unsafeFromList [1..3]) (unsafeFromList [2,0])
-- [3,1]
--
backpermute :: NonEmptyVector a -> NonEmptyVector Int -> NonEmptyVector a
backpermute (NonEmptyVector v) (NonEmptyVector i)
    = NonEmptyVector (V.backpermute v i)
{-# INLINE backpermute #-}

-- | Same as 'backpermute' but without bounds checking.
--
unsafeBackpermute
    :: NonEmptyVector a
    -> NonEmptyVector Int
    -> NonEmptyVector a
unsafeBackpermute (NonEmptyVector v) (NonEmptyVector i)
    = NonEmptyVector (V.unsafeBackpermute v i)
{-# INLINE unsafeBackpermute #-}

-- ---------------------------------------------------------------------- --
-- Safe destructive updates

-- | Apply a destructive operation to a non-empty vector. The operation
-- will be performed in place if it is safe to do so and will modify a
-- copy of the non-empty vector otherwise.
--
modify
    :: (forall s. MVector s a -> ST s ())
    -> NonEmptyVector a
    -> NonEmptyVector a
modify p (NonEmptyVector v) = NonEmptyVector (V.modify p v)
{-# INLINE modify #-}

-- ---------------------------------------------------------------------- --
-- Indexing

-- | /O(n)/ Pair each element in a vector with its index.
--
-- >>> indexed $ unsafeFromList ["a","b","c"]
-- [(0,"a"),(1,"b"),(2,"c")]
--
indexed :: NonEmptyVector a -> NonEmptyVector (Int, a)
indexed = NonEmptyVector . V.indexed . _neVec
{-# INLINE indexed #-}

-- ---------------------------------------------------------------------- --
-- Mapping

-- | /O(n)/ Map a function over a non-empty vector.
--
-- >>> map (+1) $ unsafeFromList [1..3]
-- [2,3,4]
--
map :: (a -> b) -> NonEmptyVector a -> NonEmptyVector b
map f = NonEmptyVector . V.map f . _neVec
{-# INLINE map #-}

-- | /O(n)/ Apply a function to every element of a non-empty vector and
-- its index.
--
-- >>> imap (\i a -> if i == 2 then a+1 else a+0) $ unsafeFromList [1..3]
-- [1,2,4]
--
imap :: (Int -> a -> b) -> NonEmptyVector a -> NonEmptyVector b
imap f = NonEmptyVector . V.imap f . _neVec
{-# INLINE imap #-}

-- | Map a function over a vector and concatenate the results.
--
-- >>> concatMap (\a -> unsafeFromList [a,a]) (unsafeFromList [1,2,3])
-- [1,1,2,2,3,3]
--
concatMap
    :: (a -> NonEmptyVector b)
    -> NonEmptyVector a
    -> NonEmptyVector b
concatMap f = NonEmptyVector . V.concatMap (_neVec . f) . _neVec
{-# INLINE concatMap #-}

-- ---------------------------------------------------------------------- --
-- Monadic Mapping

-- | /O(n)/ Apply the monadic action to all elements of the non-empty
-- vector, yielding non-empty vector of results.
--
-- >>> mapM Just (unsafeFromList [1..3])
-- Just [1,2,3]
--
-- >>> mapM (const Nothing) (unsafeFromList [1..3])
-- Nothing
--
mapM :: Monad m => (a -> m b) -> NonEmptyVector a -> m (NonEmptyVector b)
mapM f = fmap NonEmptyVector . V.mapM f . _neVec
{-# INLINE mapM #-}

-- | /O(n)/ Apply the monadic action to every element of a non-empty
-- vector and its index, yielding a non-empty vector of results.
--
-- >>> imapM (\i a -> if i == 1 then Just a else Just 0) (unsafeFromList [1..3])
-- Just [0,2,0]
--
-- >>> imapM (\_ _ -> Nothing) (unsafeFromList [1..3])
-- Nothing
--
imapM
    :: Monad m
    => (Int -> a -> m b)
    -> NonEmptyVector a
    -> m (NonEmptyVector b)
imapM f = fmap NonEmptyVector . V.imapM f . _neVec
{-# INLINE imapM #-}

-- | /O(n)/ Apply the monadic action to all elements of a non-empty vector
-- and ignore the results.
--
-- >>> mapM_ (const $ Just ()) (unsafeFromList [1..3])
-- Just ()
--
-- >>> mapM_ (const Nothing) (unsafeFromList [1..3])
-- Nothing
--
mapM_ :: Monad m => (a -> m b) -> NonEmptyVector a -> m ()
mapM_ f = V.mapM_ f . _neVec
{-# INLINE mapM_ #-}

-- | /O(n)/ Apply the monadic action to every element of a non-emptpy
-- vector and its index, ignoring the results
--
-- >>> imapM_ (\i a -> if i == 1 then P.print a else P.putStrLn "0") (unsafeFromList [1..3])
-- 0
-- 2
-- 0
--
-- >>> imapM_ (\_ _ -> Nothing) (unsafeFromList [1..3])
-- Nothing
--
imapM_ :: Monad m => (Int -> a -> m b) -> NonEmptyVector a -> m ()
imapM_ f = V.imapM_ f . _neVec
{-# INLINE imapM_ #-}

-- | /O(n)/ Apply the monadic action to all elements of the non-empty
-- vector, yielding a  non0empty vector of results.
--
-- Equivalent to @flip 'mapM'@.
--
forM :: Monad m => NonEmptyVector a -> (a -> m b) -> m (NonEmptyVector b)
forM (NonEmptyVector v) f = fmap NonEmptyVector (V.forM v f)
{-# INLINE forM #-}

-- | /O(n)/ Apply the monadic action to all elements of a non-empty
-- vector and ignore the results.
--
-- Equivalent to @flip 'mapM_'@.
--
forM_ :: Monad m => NonEmptyVector a -> (a -> m b) -> m ()
forM_ (NonEmptyVector v) f = V.forM_ v f
{-# INLINE forM_ #-}

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

-- | /O(min(m,n))/ Zip two non-empty vectors with the given function.
--
-- >>> zipWith (+) (unsafeFromList [1..3]) (unsafeFromList [1..3])
-- [2,4,6]
--
zipWith
    :: (a -> b -> c)
    -> NonEmptyVector a
    -> NonEmptyVector b
    -> NonEmptyVector c
zipWith f a b = NonEmptyVector (V.zipWith f a' b')
  where
    a' = _neVec a
    b' = _neVec b
{-# INLINE zipWith #-}

-- | Zip three non-empty vectors with the given function.
--
--
zipWith3
    :: (a -> b -> c -> d)
    -> NonEmptyVector a
    -> NonEmptyVector b
    -> NonEmptyVector c
    -> NonEmptyVector d
zipWith3 f a b c = NonEmptyVector (V.zipWith3 f a' b' c')
  where
    a' = _neVec a
    b' = _neVec b
    c' = _neVec c
{-# INLINE zipWith3 #-}

-- | Zip four non-empty vectors with the given function.
--
zipWith4
    :: (a -> b -> c -> d -> e)
    -> NonEmptyVector a
    -> NonEmptyVector b
    -> NonEmptyVector c
    -> NonEmptyVector d
    -> NonEmptyVector e
zipWith4 f a b c d = NonEmptyVector (V.zipWith4 f a' b' c' d')
  where
    a' = _neVec a
    b' = _neVec b
    c' = _neVec c
    d' = _neVec d
{-# INLINE zipWith4 #-}

-- | Zip five non-empty vectors with the given function.
--
zipWith5
    :: (a -> b -> c -> d -> e -> f)
    -> NonEmptyVector a
    -> NonEmptyVector b
    -> NonEmptyVector c
    -> NonEmptyVector d
    -> NonEmptyVector e
    -> NonEmptyVector f
zipWith5 f a b c d e = NonEmptyVector (V.zipWith5 f a' b' c' d' e')
  where
    a' = _neVec a
    b' = _neVec b
    c' = _neVec c
    d' = _neVec d
    e' = _neVec e
{-# INLINE zipWith5 #-}

-- | Zip six non-empty vectors with the given function.
--
zipWith6
    :: (a -> b -> c -> d -> e -> f -> g)
    -> NonEmptyVector a
    -> NonEmptyVector b
    -> NonEmptyVector c
    -> NonEmptyVector d
    -> NonEmptyVector e
    -> NonEmptyVector f
    -> NonEmptyVector g
zipWith6 k a b c d e f = NonEmptyVector (V.zipWith6 k a' b' c' d' e' f')
  where
    a' = _neVec a
    b' = _neVec b
    c' = _neVec c
    d' = _neVec d
    e' = _neVec e
    f' = _neVec f
{-# INLINE zipWith6 #-}


-- | /O(min(m,n))/ Zip two non-empty vectors with a function that also
-- takes the elements' indices.
--
izipWith
    :: (Int -> a -> b -> c)
    -> NonEmptyVector a
    -> NonEmptyVector b
    -> NonEmptyVector c
izipWith f a b = NonEmptyVector (V.izipWith f a' b')
  where
    a' = _neVec a
    b' = _neVec b
{-# INLINE izipWith #-}

-- | Zip three non-empty vectors and their indices with the given function.
--
izipWith3
    :: (Int -> a -> b -> c -> d)
    -> NonEmptyVector a
    -> NonEmptyVector b
    -> NonEmptyVector c
    -> NonEmptyVector d
izipWith3 f a b c = NonEmptyVector (V.izipWith3 f a' b' c')
  where
    a' = _neVec a
    b' = _neVec b
    c' = _neVec c
{-# INLINE izipWith3 #-}

-- | Zip four non-empty vectors and their indices with the given function.
--
izipWith4
    :: (Int -> a -> b -> c -> d -> e)
    -> NonEmptyVector a
    -> NonEmptyVector b
    -> NonEmptyVector c
    -> NonEmptyVector d
    -> NonEmptyVector e
izipWith4 f a b c d = NonEmptyVector (V.izipWith4 f a' b' c' d')
  where
    a' = _neVec a
    b' = _neVec b
    c' = _neVec c
    d' = _neVec d
{-# INLINE izipWith4 #-}

-- | Zip five non-empty vectors and their indices with the given function.
--
izipWith5
    :: (Int -> a -> b -> c -> d -> e -> f)
    -> NonEmptyVector a
    -> NonEmptyVector b
    -> NonEmptyVector c
    -> NonEmptyVector d
    -> NonEmptyVector e
    -> NonEmptyVector f
izipWith5 f a b c d e = NonEmptyVector (V.izipWith5 f a' b' c' d' e')
  where
    a' = _neVec a
    b' = _neVec b
    c' = _neVec c
    d' = _neVec d
    e' = _neVec e
{-# INLINE izipWith5 #-}

-- | Zip six non-empty vectors and their indices with the given function.
--
izipWith6
    :: (Int -> a -> b -> c -> d -> e -> f -> g)
    -> NonEmptyVector a
    -> NonEmptyVector b
    -> NonEmptyVector c
    -> NonEmptyVector d
    -> NonEmptyVector e
    -> NonEmptyVector f
    -> NonEmptyVector g
izipWith6 k a b c d e f = NonEmptyVector (V.izipWith6 k a' b' c' d' e' f')
  where
    a' = _neVec a
    b' = _neVec b
    c' = _neVec c
    d' = _neVec d
    e' = _neVec e
    f' = _neVec f
{-# INLINE izipWith6 #-}

-- | /O(min(n,m))/ Elementwise pairing of non-empty vector elements. This is a special case
-- of 'zipWith' where the function argument is '(,)'
--
zip :: NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector (a, b)
zip a b = NonEmptyVector (V.zip a' b')
  where
    a' = _neVec a
    b' = _neVec b
{-# INLINE zip #-}

-- | Zip together three non-empty vectors.
--
zip3
    :: NonEmptyVector a
    -> NonEmptyVector b
    -> NonEmptyVector c
    -> NonEmptyVector (a, b, c)
zip3 a b c = NonEmptyVector (V.zip3 a' b' c')
  where
    a' = _neVec a
    b' = _neVec b
    c' = _neVec c
{-# INLINE zip3 #-}

-- | Zip together four non-empty vectors.
--
zip4
    :: NonEmptyVector a
    -> NonEmptyVector b
    -> NonEmptyVector c
    -> NonEmptyVector d
    -> NonEmptyVector (a, b, c, d)
zip4 a b c d = NonEmptyVector (V.zip4 a' b' c' d')
  where
    a' = _neVec a
    b' = _neVec b
    c' = _neVec c
    d' = _neVec d
{-# INLINE zip4 #-}

-- | Zip together five non-empty vectors.
--
zip5
    :: NonEmptyVector a
    -> NonEmptyVector b
    -> NonEmptyVector c
    -> NonEmptyVector d
    -> NonEmptyVector e
    -> NonEmptyVector (a, b, c, d, e)
zip5 a b c d e = NonEmptyVector (V.zip5 a' b' c' d' e')
  where
    a' = _neVec a
    b' = _neVec b
    c' = _neVec c
    d' = _neVec d
    e' = _neVec e
{-# INLINE zip5 #-}

-- | Zip together six non-empty vectors.
--
zip6
    :: NonEmptyVector a
    -> NonEmptyVector b
    -> NonEmptyVector c
    -> NonEmptyVector d
    -> NonEmptyVector e
    -> NonEmptyVector f
    -> NonEmptyVector (a, b, c, d, e, f)
zip6 a b c d e f = NonEmptyVector (V.zip6 a' b' c' d' e' f')
  where
    a' = _neVec a
    b' = _neVec b
    c' = _neVec c
    d' = _neVec d
    e' = _neVec e
    f' = _neVec f
{-# INLINE zip6 #-}

-- ---------------------------------------------------------------------- --
-- Monadic Zipping

-- | /O(min(m,n))/ Zip the two non-empty vectors with the monadic action
-- and yield a non-empty vector of results.
--
zipWithM
    :: Monad m
    => (a -> b -> m c)
    -> NonEmptyVector a
    -> NonEmptyVector b
    -> m (NonEmptyVector c)
zipWithM f a b = fmap NonEmptyVector (V.zipWithM f a' b')
  where
    a' = _neVec a
    b' = _neVec b
{-# INLINE zipWithM #-}

-- | /O(min(m,n))/ Zip the two non-empty vectors with a monadic action
-- that also takes the element index and yield a vector of results.
--
izipWithM
    :: Monad m
    => (Int -> a -> b -> m c)
    -> NonEmptyVector a
    -> NonEmptyVector b
    -> m (NonEmptyVector c)
izipWithM f a b = fmap NonEmptyVector (V.izipWithM f a' b')
  where
    a' = _neVec a
    b' = _neVec b
{-# INLINE izipWithM #-}

-- | /O(min(m,n))/ Zip the two non-empty vectors with the monadic action
-- and ignore the results.
--
zipWithM_
    :: Monad m
    => (a -> b -> m c)
    -> NonEmptyVector a
    -> NonEmptyVector b
    -> m ()
zipWithM_ f a b = V.zipWithM_ f (_neVec a) (_neVec b)
{-# INLINE zipWithM_ #-}

-- | /O(min(m,n))/ Zip the two non-empty vectors with a monadic action
-- that also takes the element index and ignore the results.
--
izipWithM_
    :: Monad m
    => (Int -> a -> b -> m c)
    -> NonEmptyVector a
    -> NonEmptyVector b
    -> m ()
izipWithM_ f a b = V.izipWithM_ f (_neVec a) (_neVec b)
{-# INLINE izipWithM_ #-}

-- ---------------------------------------------------------------------- --
-- Unzipping

-- | /O(min(m,n))/ Unzip a non-empty vector of pairs.
--
unzip :: NonEmptyVector (a, b) -> (NonEmptyVector a, NonEmptyVector b)
unzip (NonEmptyVector v) = case V.unzip v of
    ~(a,b) -> (NonEmptyVector a, NonEmptyVector b)
{-# INLINE unzip #-}

-- | Unzip a non-empty vector of triples.
--
unzip3
    :: NonEmptyVector (a, b, c)
    -> (NonEmptyVector a, NonEmptyVector b, NonEmptyVector c)
unzip3 (NonEmptyVector v) = case V.unzip3 v of
    ~(a,b,c) ->
      ( NonEmptyVector a
      , NonEmptyVector b
      , NonEmptyVector c
      )
{-# INLINE unzip3 #-}

-- | Unzip a non-empty vector of quadruples.
--
unzip4
    :: NonEmptyVector (a, b, c, d)
    -> ( NonEmptyVector a
       , NonEmptyVector b
       , NonEmptyVector c
       , NonEmptyVector d
       )
unzip4 (NonEmptyVector v) = case V.unzip4 v of
    ~(a,b,c,d) ->
      ( NonEmptyVector a
      , NonEmptyVector b
      , NonEmptyVector c
      , NonEmptyVector d
      )
{-# INLINE unzip4 #-}

-- | Unzip a non-empty vector of quintuples.
--
unzip5
    :: NonEmptyVector (a, b, c, d, e)
    -> ( NonEmptyVector a
       , NonEmptyVector b
       , NonEmptyVector c
       , NonEmptyVector d
       , NonEmptyVector e
       )
unzip5 (NonEmptyVector v) = case V.unzip5 v of
    ~(a,b,c,d,e) ->
      ( NonEmptyVector a
      , NonEmptyVector b
      , NonEmptyVector c
      , NonEmptyVector d
      , NonEmptyVector e
      )
{-# INLINE unzip5 #-}

-- | Unzip a non-empty vector of sextuples.
--
unzip6
    :: NonEmptyVector (a, b, c, d, e, f)
    -> ( NonEmptyVector a
       , NonEmptyVector b
       , NonEmptyVector c
       , NonEmptyVector d
       , NonEmptyVector e
       , NonEmptyVector f
       )
unzip6 (NonEmptyVector v) = case V.unzip6 v of
    ~(a,b,c,d,e,f) ->
      ( NonEmptyVector a
      , NonEmptyVector b
      , NonEmptyVector c
      , NonEmptyVector d
      , NonEmptyVector e
      , NonEmptyVector f
      )
{-# INLINE unzip6 #-}

-- ---------------------------------------------------------------------- --
-- Filtering

-- | /O(n)/ Drop elements that do not satisfy the predicate.
--
-- If no elements satisfy the predicate, the resulting vector may be empty.
--
-- >>> filter (\a -> if a == 2 then False else True) (unsafeFromList [1..3])
-- [1,3]
--
-- >>> filter (const False) (unsafeFromList [1..3])
-- []
--
filter :: (a -> Bool) -> NonEmptyVector a -> Vector a
filter f = V.filter f . _neVec
{-# INLINE filter #-}

-- | /O(n)/ Drop elements that do not satisfy the predicate which is
-- applied to values and their indices.
--
-- If no elements satisfy the predicate, the resulting vector may be empty.
--
-- >>> ifilter (\i a -> if a == 2 || i == 0 then False else True) (unsafeFromList [1..3])
-- [3]
--
-- >>> ifilter (\_ _ -> False) (unsafeFromList [1..3])
-- []
--
ifilter
    :: (Int -> a -> Bool)
    -> NonEmptyVector a
    -> Vector a
ifilter f = V.ifilter f . _neVec
{-# INLINE ifilter #-}

-- | /O(n)/ Drop elements that do not satisfy the monadic predicate.
--
-- If no elements satisfy the predicate, the resulting vector may be empty.
--
-- >>> filterM (\a -> if a == 2 then Just False else Just True) (unsafeFromList [1..3])
-- Just [1,3]
--
-- >>> filterM (\a -> if a == 2 then Nothing else Just True) (unsafeFromList [1..3])
-- Nothing
--
-- >>> filterM (const $ Just False) (unsafeFromList [1..3])
-- Just []
--
filterM
    :: Monad m
    => (a -> m Bool)
    -> NonEmptyVector a
    -> m (Vector a)
filterM f = V.filterM f . _neVec
{-# INLINE filterM #-}

-- | /O(n)/ Drop elements that do not satisfy the monadic predicate that is
-- a function of index and value.
--
-- If no elements satisfy the predicate, the resulting vector may be empty.
--
-- TODO: this should be a more efficient function in `vector`.
--
-- >>> ifilterM (\i a -> if a == 2 || i == 0 then Just False else Just True) (unsafeFromList [1..3])
-- Just [3]
--
-- >>> ifilterM (\i a -> if a == 2 || i == 0 then Nothing else Just True) (unsafeFromList [1..3])
-- Nothing
--
-- >>> ifilterM (\_ _ -> Just False) (unsafeFromList [1..3])
-- Just []
--
ifilterM
    :: Monad m
    => (Int -> a -> m Bool)
    -> NonEmptyVector a
    -> m (Vector a)
ifilterM f = fmap (V.map snd)
    . V.filterM (uncurry f)
    . V.indexed
    . _neVec
{-# INLINE ifilterM #-}

-- | /O(n)/ Drop repeated adjacent elements.
--
-- >>> uniq $ unsafeFromList [1,1,2,2,3,3,1]
-- [1,2,3,1]
--
uniq :: Eq a => NonEmptyVector a -> NonEmptyVector a
uniq = NonEmptyVector . V.uniq . _neVec
{-# INLINE uniq #-}

-- | /O(n)/ Drop elements when predicate returns Nothing
--
-- If no elements satisfy the predicate, the resulting vector may be empty.
--
-- >>> mapMaybe (\a -> if a == 2 then Nothing else Just a) (unsafeFromList [1..3])
-- [1,3]
--
mapMaybe
    :: (a -> Maybe b)
    -> NonEmptyVector a
    -> Vector b
mapMaybe f = V.mapMaybe f . _neVec
{-# INLINE mapMaybe #-}

-- | /O(n)/ Drop elements when predicate, applied to index and value, returns Nothing
--
-- If no elements satisfy the predicate, the resulting vector may be empty.
--
-- >>> imapMaybe (\i a -> if a == 2 || i == 2 then Nothing else Just a) (unsafeFromList [1..3])
-- [1]
--
imapMaybe
    :: (Int -> a -> Maybe b)
    -> NonEmptyVector a
    -> Vector b
imapMaybe f = V.imapMaybe f . _neVec
{-# INLINE imapMaybe #-}

-- | /O(n)/ Yield the longest prefix of elements satisfying the predicate
-- without copying.
--
-- If no elements satisfy the predicate, the resulting vector may be empty.
--
-- >>> takeWhile (/= 3) (unsafeFromList [1..3])
-- [1,2]
--
takeWhile :: (a -> Bool) -> NonEmptyVector a -> Vector a
takeWhile f = V.takeWhile f . _neVec
{-# INLINE takeWhile #-}

-- | /O(n)/ Drop the longest prefix of elements that satisfy the predicate
-- without copying.
--
-- If all elements satisfy the predicate, the resulting vector may be empty.
--
-- >>> dropWhile (/= 3) (unsafeFromList [1..3])
-- [3]
--
dropWhile :: (a -> Bool) -> NonEmptyVector a -> Vector a
dropWhile f = V.dropWhile f . _neVec
{-# INLINE dropWhile #-}

-- ---------------------------------------------------------------------- --
-- Partitioning

-- | /O(n)/ Split the non-empty vector in two parts, the first one
-- containing those elements that satisfy the predicate and the second
-- one those that don't. The relative order of the elements is preserved
-- at the cost of a sometimes reduced performance compared to
-- 'unstablePartition'.
--
-- If all or no elements satisfy the predicate, one of the resulting vectors
-- may be empty.
--
-- >>> partition (< 3) (unsafeFromList [1..5])
-- ([1,2],[3,4,5])
--
partition :: (a -> Bool) -> NonEmptyVector a -> (Vector a, Vector a)
partition f = V.partition f . _neVec
{-# INLINE partition #-}

-- | /O(n)/ Split the non-empty vector in two parts, the first one
-- containing the Left elements and the second containing the
-- Right elements. The relative order of the elements is preserved.
--
-- If all elements produce a Left (or Right), one of the
-- resulting vectors may be empty.
--
-- >>> partitionWith (\a -> if a < 3 then Left a else Right (P.show a)) (unsafeFromList [1..5])
-- ([1,2],["3","4","5"])
--
partitionWith :: (a -> Either b c) -> NonEmptyVector a -> (Vector b, Vector c)
partitionWith f = V.partitionWith f . _neVec
{-# INLINE partitionWith #-}

-- | /O(n)/ Split the non-empty vector in two parts, the first one
-- containing those elements that satisfy the predicate and the second
-- one those that don't. The order of the elements is not preserved but
-- the operation is often faster than 'partition'.
--
-- If all or no elements satisfy the predicate, one of the resulting vectors
-- may be empty.
--
unstablePartition
    :: (a -> Bool)
    -> NonEmptyVector a
    -> (Vector a, Vector a)
unstablePartition f = V.unstablePartition f . _neVec
{-# INLINE unstablePartition #-}

-- | /O(n)/ Split the non-empty vector into the longest prefix of elements
-- that satisfy the predicate and the rest without copying.
--
-- If all or no elements satisfy the predicate, one of the resulting vectors
-- may be empty.
--
-- >>> span (== 1) (unsafeFromList [1,1,2,3,1])
-- ([1,1],[2,3,1])
--
span :: (a -> Bool) -> NonEmptyVector a -> (Vector a, Vector a)
span f = V.span f . _neVec
{-# INLINE span #-}

-- | /O(n)/ Split the vector into the longest prefix of elements that do not
-- satisfy the predicate and the rest without copying.
--
-- If all or no elements satisfy the predicate, one of the resulting vectors
-- may be empty.
--
-- >>> break (== 2) (unsafeFromList [1,1,2,3,1])
-- ([1,1],[2,3,1])
--
break :: (a -> Bool) -> NonEmptyVector a -> (Vector a, Vector a)
break f = V.break f . _neVec
{-# INLINE break #-}

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

-- | /O(n)/ Check if the non-empty vector contains an element
--
-- >>> elem 1 $ unsafeFromList [1..3]
-- True
-- >>> elem 4 $ unsafeFromList [1..3]
-- False
--
elem :: Eq a => a -> NonEmptyVector a -> Bool
elem a = V.elem a . _neVec
{-# INLINE elem #-}

-- | /O(n)/ Check if the non-empty vector does not contain an element
-- (inverse of 'elem')
--
-- >>> notElem 1 $ unsafeFromList [1..3]
-- False
--
-- >>> notElem 4 $ unsafeFromList [1..3]
-- True
--
notElem :: Eq a => a -> NonEmptyVector a -> Bool
notElem a = V.notElem a . _neVec
{-# INLINE notElem #-}

-- | /O(n)/ Yield 'Just' the first element matching the predicate or
-- 'Nothing' if no such element exists.
--
-- >>> find (< 2) $ unsafeFromList [1..3]
-- Just 1
--
-- >>> find (< 0) $ unsafeFromList [1..3]
-- Nothing
--
find :: (a -> Bool) -> NonEmptyVector a -> Maybe a
find f = V.find f . _neVec
{-# INLINE find #-}

-- | /O(n)/ Yield 'Just' the index of the first element matching the
-- predicate or 'Nothing' if no such element exists.
--
-- >>> findIndex (< 2) $ unsafeFromList [1..3]
-- Just 0
--
-- >>> findIndex (< 0) $ unsafeFromList [1..3]
-- Nothing
--
findIndex :: (a -> Bool) -> NonEmptyVector a -> Maybe Int
findIndex f = V.findIndex f . _neVec
{-# INLINE findIndex #-}

-- | /O(n)/ Yield the indices of elements satisfying the predicate in
-- ascending order.
--
-- >>> findIndices (< 3) $ unsafeFromList [1..3]
-- [0,1]
--
-- >>> findIndices (< 0) $ unsafeFromList [1..3]
-- []
--
findIndices :: (a -> Bool) -> NonEmptyVector a -> Vector Int
findIndices f = V.findIndices f . _neVec
{-# INLINE findIndices #-}

-- | /O(n)/ Yield 'Just' the index of the first occurence of the given
-- element or 'Nothing' if the non-empty vector does not contain the
-- element. This is a specialised version of 'findIndex'.
--
-- >>> elemIndex 1 $ unsafeFromList [1..3]
-- Just 0
--
-- >>> elemIndex 0 $ unsafeFromList [1..3]
-- Nothing
--
elemIndex :: Eq a => a -> NonEmptyVector a -> Maybe Int
elemIndex a = V.elemIndex a . _neVec
{-# INLINE elemIndex #-}

-- | /O(n)/ Yield the indices of all occurences of the given element in
-- ascending order. This is a specialised version of 'findIndices'.
--
-- >>> elemIndices 1 $ unsafeFromList [1,2,3,1]
-- [0,3]
--
-- >>> elemIndices 0 $ unsafeFromList [1..3]
-- []
--
elemIndices :: Eq a => a -> NonEmptyVector a -> Vector Int
elemIndices a = V.elemIndices a . _neVec
{-# INLINE elemIndices #-}

-- ---------------------------------------------------------------------- --
-- Folding

-- | /O(n)/ Left monoidal fold
--
foldl :: (a -> b -> a) -> a -> NonEmptyVector b -> a
foldl f a = V.foldl f a . _neVec
{-# INLINE foldl #-}

-- | /O(n)/ Left semigroupal fold
--
foldl1 :: (a -> a -> a) -> NonEmptyVector a -> a
foldl1 f = V.foldl1 f . _neVec
{-# INLINE foldl1 #-}

-- | /O(n)/ Strict Left monoidal fold
--
foldl' :: (a -> b -> a) -> a -> NonEmptyVector b -> a
foldl' f a = V.foldl' f a . _neVec
{-# INLINE foldl' #-}

-- | /O(n)/ Strict Left semigroupal fold
--
foldl1' :: (a -> a -> a) -> NonEmptyVector a -> a
foldl1' f = V.foldl1' f . _neVec
{-# INLINE foldl1' #-}

-- | /O(n)/ Right monoidal fold
--
foldr :: (a -> b -> b) -> b -> NonEmptyVector a -> b
foldr f b = V.foldr f b . _neVec
{-# INLINE foldr #-}

-- | /O(n)/ Right semigroupal fold
--
foldr1 :: (a -> a -> a) -> NonEmptyVector a -> a
foldr1 f = V.foldr1 f . _neVec
{-# INLINE foldr1 #-}

-- | /O(n)/ Strict right monoidal fold
--
foldr' :: (a -> b -> b) -> b -> NonEmptyVector a -> b
foldr' f b = V.foldr' f b. _neVec
{-# INLINE foldr' #-}

-- | /O(n)/ Strict right semigroupal fold
--
foldr1' :: (a -> a -> a) -> NonEmptyVector a -> a
foldr1' f = V.foldr1' f . _neVec
{-# INLINE foldr1' #-}

-- | /O(n)/ Left monoidal fold with function applied to each element
-- and its index
--
ifoldl :: (a -> Int -> b -> a) -> a -> NonEmptyVector b -> a
ifoldl f a = V.ifoldl f a . _neVec
{-# INLINE ifoldl #-}

-- | /O(n)/ Strict left monoidal fold with function applied to each element
-- and its index
--
ifoldl' :: (a -> Int -> b -> a) -> a -> NonEmptyVector b -> a
ifoldl' f a = V.ifoldl' f a . _neVec
{-# INLINE ifoldl' #-}

-- | /O(n)/ Right monoidal fold with function applied to each element
-- and its index
--
ifoldr :: (Int -> a -> b -> b) -> b -> NonEmptyVector a -> b
ifoldr f b = V.ifoldr f b . _neVec
{-# INLINE ifoldr #-}

-- | /O(n)/ strict right monoidal fold with function applied to each element
-- and its index
--
ifoldr' :: (Int -> a -> b -> b) -> b -> NonEmptyVector a -> b
ifoldr' f b = V.ifoldr' f b . _neVec
{-# INLINE ifoldr' #-}

-- ---------------------------------------------------------------------- --
-- Specialised folds

-- | /O(n)/ Check if all elements satisfy the predicate.
--
all :: (a -> Bool) -> NonEmptyVector a -> Bool
all f = V.all f . _neVec
{-# INLINE all #-}

-- | /O(n)/ Check if any element satisfies the predicate.
--
any :: (a -> Bool) -> NonEmptyVector a -> Bool
any f = V.any f . _neVec
{-# INLINE any #-}

-- | /O(n)/ Check if all elements are @True@.
--
and :: NonEmptyVector Bool -> Bool
and = V.and . _neVec
{-# INLINE and #-}

-- | /O(n)/ Check if any element is @True@
--
or :: NonEmptyVector Bool -> Bool
or = V.or . _neVec
{-# INLINE or #-}

-- | /O(n)/ Compute the sum of the elements
--
sum :: Num a => NonEmptyVector a -> a
sum = V.sum . _neVec
{-# INLINE sum #-}

-- | /O(n)/ Compute the produce of the elements
--
product :: Num a => NonEmptyVector a -> a
product = V.product . _neVec
{-# INLINE product #-}

-- | /O(n)/ Yield the maximum element of the non-empty vector.
--
maximum :: Ord a => NonEmptyVector a -> a
maximum = V.maximum . _neVec
{-# INLINE maximum #-}

-- | /O(n)/ Yield the maximum element of a non-empty vector
-- according to the given comparison function.
--
maximumBy :: (a -> a -> Ordering) -> NonEmptyVector a -> a
maximumBy f = V.maximumBy f . _neVec
{-# INLINE maximumBy #-}

-- | /O(n)/ Yield the minimum element of the non-empty vector.
--
minimum :: Ord a => NonEmptyVector a -> a
minimum = V.minimum . _neVec
{-# INLINE minimum #-}

-- | /O(n)/ Yield the minimum element of the non-empty vector
-- according to the given comparison function.
--
minimumBy :: (a -> a -> Ordering) -> NonEmptyVector a -> a
minimumBy f = V.minimumBy f . _neVec
{-# INLINE minimumBy #-}

-- | /O(n)/ Yield the index of the minimum element of the
-- non-empty vector.
--
minIndex :: Ord a => NonEmptyVector a -> Int
minIndex = V.minIndex . _neVec
{-# INLINE minIndex #-}

-- | /O(n)/ Yield the index of the minimum element of the vector
-- according to the given comparison function.
--
minIndexBy :: (a -> a -> Ordering) -> NonEmptyVector a -> Int
minIndexBy f = V.minIndexBy f . _neVec
{-# INLINE minIndexBy #-}

-- | /O(n)/ Yield the index of the maximum element of the
-- non-empty vector.
--
maxIndex :: Ord a => NonEmptyVector a -> Int
maxIndex = V.maxIndex . _neVec
{-# INLINE maxIndex #-}

-- | /O(n)/ Yield the index of the maximum element of the vector
-- according to the given comparison function.
--
maxIndexBy :: (a -> a -> Ordering) -> NonEmptyVector a -> Int
maxIndexBy f = V.maxIndexBy f . _neVec
{-# INLINE maxIndexBy #-}

-- ---------------------------------------------------------------------- --
-- Monadic folds

-- | /O(n)/ Monadic fold
--
foldM :: Monad m => (a -> b -> m a) -> a -> NonEmptyVector b -> m a
foldM f a = V.foldM f a . _neVec
{-# INLINE foldM #-}

-- | /O(n)/ Monadic fold (action applied to each element and its index)
--
ifoldM :: Monad m => (a -> Int -> b -> m a) -> a -> NonEmptyVector b -> m a
ifoldM f a = V.ifoldM f a . _neVec
{-# INLINE ifoldM #-}

-- | /O(n)/ Strict monadic fold
--
foldM' :: Monad m => (a -> b -> m a) -> a -> NonEmptyVector b -> m a
foldM' f a = V.foldM' f a . _neVec
{-# INLINE foldM' #-}

-- | /O(n)/ Strict monadic fold (action applied to each element and its index)
--
ifoldM' :: Monad m => (a -> Int -> b -> m a) -> a -> NonEmptyVector b -> m a
ifoldM' f a = V.ifoldM' f a . _neVec
{-# INLINE ifoldM' #-}

-- | /O(n)/ Monadic semigroupal fold
--
fold1M :: Monad m => (a -> a -> m a) -> NonEmptyVector a -> m a
fold1M f = V.fold1M f . _neVec
{-# INLINE fold1M #-}

-- | /O(n)/ Strict monadic semigroupal fold
--
fold1M' :: Monad m => (a -> a -> m a) -> NonEmptyVector a -> m a
fold1M' f = V.fold1M' f . _neVec
{-# INLINE fold1M' #-}

-- | /O(n)/ Monadic fold that discards the result
--
foldM_ :: Monad m => (a -> b -> m a) -> a -> NonEmptyVector b -> m ()
foldM_ f a = V.foldM_ f a . _neVec
{-# INLINE foldM_ #-}

-- | /O(n)/ Monadic fold that discards the result (action applied to each
-- element and its index)
--
ifoldM_ :: Monad m => (a -> Int -> b -> m a) -> a -> NonEmptyVector b -> m ()
ifoldM_ f a = V.ifoldM_ f a . _neVec
{-# INLINE ifoldM_ #-}

-- | /O(n)/ Strict monadic fold that discards the result
--
foldM'_ :: Monad m => (a -> b -> m a) -> a -> NonEmptyVector b -> m ()
foldM'_ f a = V.foldM'_ f a . _neVec
{-# INLINE foldM'_ #-}

-- | /O(n)/ Strict monadic fold that discards the result (action applied to each
-- element and its index)
--
ifoldM'_ :: Monad m => (a -> Int -> b -> m a) -> a -> NonEmptyVector b -> m ()
ifoldM'_ f a = V.ifoldM'_ f a . _neVec
{-# INLINE ifoldM'_ #-}

-- | /O(n)/ Monadic semigroupal fold that discards the result
--
fold1M_ :: Monad m => (a -> a -> m a) -> NonEmptyVector a -> m ()
fold1M_ f = V.fold1M_ f . _neVec
{-# INLINE fold1M_ #-}

-- | /O(n)/ Strict monadic semigroupal fold that discards the result
--
fold1M'_ :: Monad m => (a -> a -> m a) -> NonEmptyVector a -> m ()
fold1M'_ f = V.fold1M'_ f . _neVec
{-# INLINE fold1M'_ #-}

-- ---------------------------------------------------------------------- --
-- Monadic sequencing

-- | Evaluate each action and collect the results
--
sequence :: Monad m => NonEmptyVector (m a) -> m (NonEmptyVector a)
sequence = fmap NonEmptyVector . V.sequence . _neVec
{-# INLINE sequence #-}

-- | Evaluate each action and discard the results
--
sequence_ :: Monad m => NonEmptyVector (m a) -> m ()
sequence_ = V.sequence_ . _neVec
{-# INLINE sequence_ #-}

-- ---------------------------------------------------------------------- --
-- Prefix sums (scans)

-- | /O(n)/ Prescan
--
prescanl :: (a -> b -> a) -> a -> NonEmptyVector b -> NonEmptyVector a
prescanl f a = NonEmptyVector . V.prescanl f a . _neVec
{-# INLINE prescanl #-}

-- | /O(n)/ Prescan with strict accumulator
--
prescanl' :: (a -> b -> a) -> a -> NonEmptyVector b -> NonEmptyVector a
prescanl' f a = NonEmptyVector . V.prescanl' f a . _neVec
{-# INLINE prescanl' #-}

-- | /O(n)/ Scan
--
postscanl :: (a -> b -> a) -> a -> NonEmptyVector b -> NonEmptyVector a
postscanl f a = NonEmptyVector . V.postscanl f a . _neVec
{-# INLINE postscanl #-}

-- | /O(n)/ Scan with a strict accumulator
--
postscanl' :: (a -> b -> a) -> a -> NonEmptyVector b -> NonEmptyVector a
postscanl' f a = NonEmptyVector . V.postscanl' f a . _neVec
{-# INLINE postscanl' #-}

-- | /O(n)/ Haskell-style scan
--
scanl :: (a -> b -> a) -> a -> NonEmptyVector b -> NonEmptyVector a
scanl f a = NonEmptyVector . V.scanl f a . _neVec
{-# INLINE scanl #-}

-- | /O(n)/ Haskell-style scan with strict accumulator
--
scanl' :: (a -> b -> a) -> a -> NonEmptyVector b -> NonEmptyVector a
scanl' f a = NonEmptyVector . V.scanl' f a . _neVec
{-# INLINE scanl' #-}

-- | /O(n)/ Semigroupal left scan
--
scanl1 :: (a -> a -> a) -> NonEmptyVector a -> NonEmptyVector a
scanl1 f = NonEmptyVector . V.scanl1 f . _neVec
{-# INLINE scanl1 #-}

-- | /O(n)/ Strict semigroupal scan
--
scanl1' :: (a -> a -> a) -> NonEmptyVector a -> NonEmptyVector a
scanl1' f = NonEmptyVector . V.scanl1' f . _neVec
{-# INLINE scanl1' #-}

-- | /O(n)/ Scan over a vector with its index
--
iscanl :: (Int -> a -> b -> a) -> a -> NonEmptyVector b -> NonEmptyVector a
iscanl f a = NonEmptyVector . V.iscanl f a . _neVec
{-# INLINE iscanl #-}

-- | /O(n)/ Scan over a vector with its index with strict accumulator
--
iscanl' :: (Int -> a -> b -> a) -> a -> NonEmptyVector b -> NonEmptyVector a
iscanl' f a = NonEmptyVector . V.iscanl' f a . _neVec
{-# INLINE iscanl' #-}

-- | /O(n)/ Right-to-left prescan
--
prescanr :: (a -> b -> b) -> b -> NonEmptyVector a -> NonEmptyVector b
prescanr f b = NonEmptyVector . V.prescanr f b . _neVec
{-# INLINE prescanr #-}

-- | /O(n)/ Right-to-left prescan with strict accumulator
--
prescanr' :: (a -> b -> b) -> b -> NonEmptyVector a -> NonEmptyVector b
prescanr' f b = NonEmptyVector . V.prescanr' f b . _neVec
{-# INLINE prescanr' #-}

-- | /O(n)/ Right-to-left scan
--
postscanr :: (a -> b -> b) -> b -> NonEmptyVector a -> NonEmptyVector b
postscanr f b = NonEmptyVector . V.postscanr f b . _neVec
{-# INLINE postscanr #-}

-- | /O(n)/ Right-to-left scan with strict accumulator
--
postscanr' :: (a -> b -> b) -> b -> NonEmptyVector a -> NonEmptyVector b
postscanr' f b = NonEmptyVector . V.postscanr' f b . _neVec
{-# INLINE postscanr' #-}

-- | /O(n)/ Right-to-left Haskell-style scan
--
scanr :: (a -> b -> b) -> b -> NonEmptyVector a -> NonEmptyVector b
scanr f b = NonEmptyVector . V.scanr f b . _neVec
{-# INLINE scanr #-}

-- | /O(n)/ Right-to-left Haskell-style scan with strict accumulator
--
scanr' :: (a -> b -> b) -> b -> NonEmptyVector a -> NonEmptyVector b
scanr' f b = NonEmptyVector . V.scanr' f b . _neVec
{-# INLINE scanr' #-}

-- | /O(n)/ Right-to-left Haskell-style semigroupal scan
--
scanr1 :: (a -> a -> a) -> NonEmptyVector a -> NonEmptyVector a
scanr1 f = NonEmptyVector . V.scanr1 f . _neVec
{-# INLINE scanr1 #-}

-- | /O(n)/ Right-to-left Haskell-style semigroupal scan with strict accumulator
--
scanr1' :: (a -> a -> a) -> NonEmptyVector a -> NonEmptyVector a
scanr1' f = NonEmptyVector . V.scanr1' f . _neVec
{-# INLINE scanr1' #-}

-- | /O(n)/ Right-to-left scan over a vector with its index
--
iscanr :: (Int -> a -> b -> b) -> b -> NonEmptyVector a -> NonEmptyVector b
iscanr f b = NonEmptyVector . V.iscanr f b . _neVec
{-# INLINE iscanr #-}

-- | /O(n)/ Right-to-left scan over a vector with its index and a strict
-- accumulator
--
iscanr' :: (Int -> a -> b -> b) -> b -> NonEmptyVector a -> NonEmptyVector b
iscanr' f b = NonEmptyVector . V.iscanr' f b . _neVec
{-# INLINE iscanr' #-}