    {-# LANGUAGE NoImplicitPrelude #-}
    module RIO.Deque
        ( -- * Types

          Deque
        , UDeque
        , SDeque
        , BDeque
          -- * Operations

        , newDeque
        , getDequeSize
        , popFrontDeque
        , popBackDeque
        , pushFrontDeque
        , pushBackDeque
        , foldlDeque
        , foldrDeque
        , dequeToList
        , dequeToVector
        , freezeDeque
          -- * Inference helpers

        , asUDeque
        , asSDeque
        , asBDeque
        ) where

    import           RIO.Prelude.Reexports
    import           Control.Exception            (assert)
    import           Control.Monad                (liftM)
    import qualified Data.Vector.Generic          as VG
    import qualified Data.Vector.Generic.Mutable  as V
    import qualified Data.Vector.Mutable          as B
    import qualified Data.Vector.Storable.Mutable as S
    import qualified Data.Vector.Unboxed.Mutable  as U
    import           Data.Primitive.MutVar

    data DequeState v s a = DequeState
        !(v s a)
        {-# UNPACK #-} !Int -- start

        {-# UNPACK #-} !Int -- size

    -- | A double-ended queue supporting any underlying vector type and any monad.

    --

    -- This implements a circular double-ended queue with exponential growth.

    --

    -- @since 0.1.9.0

    newtype Deque v s a = Deque (MutVar s (DequeState v s a))

    -- | A 'Deque' specialized to unboxed vectors.

    --

    -- @since 0.1.9.0

    type UDeque = Deque U.MVector

    -- | A 'Deque' specialized to storable vectors.

    --

    -- @since 0.1.9.0

    type SDeque = Deque S.MVector

    -- | A 'Deque' specialized to boxed vectors.

    --

    -- @since 0.1.9.0

    type BDeque = Deque B.MVector

    -- | Helper function to assist with type inference, forcing usage of

    -- an unboxed vector.

    --

    -- @since 0.1.9.0

    asUDeque :: UDeque s a -> UDeque s a
    asUDeque :: forall s a. UDeque s a -> UDeque s a
    asUDeque = UDeque s a -> UDeque s a
    forall a. a -> a
    id

    -- | Helper function to assist with type inference, forcing usage of a

    -- storable vector.

    --

    -- @since 0.1.9.0

    asSDeque :: SDeque s a -> SDeque s a
    asSDeque :: forall s a. SDeque s a -> SDeque s a
    asSDeque = SDeque s a -> SDeque s a
    forall a. a -> a
    id

    -- | Helper function to assist with type inference, forcing usage of a

    -- boxed vector.

    --

    -- @since 0.1.9.0

    asBDeque :: BDeque s a -> BDeque s a
    asBDeque :: forall s a. BDeque s a -> BDeque s a
    asBDeque = BDeque s a -> BDeque s a
    forall a. a -> a
    id

    -- | Create a new, empty 'Deque'

    --

    -- @since 0.1.9.0

    newDeque
      :: (V.MVector v a, PrimMonad m)
      => m (Deque v (PrimState m) a)
    newDeque :: forall (v :: * -> * -> *) a (m :: * -> *).
    (MVector v a, PrimMonad m) =>
    m (Deque v (PrimState m) a)
    newDeque = do
        v <- Int -> m (v (PrimState m) a)
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (HasCallStack, PrimMonad m, MVector v a) =>
    Int -> m (v (PrimState m) a)
    V.new Int
    baseSize
        Deque <$> newMutVar (DequeState v 0 0)
      where
        baseSize :: Int
    baseSize = Int
    32
    {-# INLINE newDeque #-}

    -- | /O(1)/ - Get the number of elements that is currently in the `Deque`

    --

    -- @since 0.1.9.0

    getDequeSize :: PrimMonad m => Deque v (PrimState m) a -> m Int
    getDequeSize :: forall (m :: * -> *) (v :: * -> * -> *) a.
    PrimMonad m =>
    Deque v (PrimState m) a -> m Int
    getDequeSize (Deque MutVar (PrimState m) (DequeState v (PrimState m) a)
    var) = do
      DequeState _ _ size <- MutVar (PrimState m) (DequeState v (PrimState m) a)
    -> m (DequeState v (PrimState m) a)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar MutVar (PrimState m) (DequeState v (PrimState m) a)
    var
      pure size
    {-# INLINE getDequeSize #-}

    -- | Pop the first value from the beginning of the 'Deque'

    --

    -- @since 0.1.9.0

    popFrontDeque
      :: (V.MVector v a, PrimMonad m)
      => Deque v (PrimState m) a
      -> m (Maybe a)
    popFrontDeque :: forall (v :: * -> * -> *) a (m :: * -> *).
    (MVector v a, PrimMonad m) =>
    Deque v (PrimState m) a -> m (Maybe a)
    popFrontDeque (Deque MutVar (PrimState m) (DequeState v (PrimState m) a)
    var) = do
        DequeState v start size <- MutVar (PrimState m) (DequeState v (PrimState m) a)
    -> m (DequeState v (PrimState m) a)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar MutVar (PrimState m) (DequeState v (PrimState m) a)
    var
        if size == 0
            then return Nothing
            else do
                x <- V.unsafeRead v start
                let start' = Int
    start Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1
                    start''
                        | Int
    start' Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= v (PrimState m) a -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    V.length v (PrimState m) a
    v = Int
    0
                        | Bool
    otherwise = Int
    start'
                writeMutVar var $! DequeState v start'' (size - 1)
                return (Just x)
    {-# INLINE popFrontDeque #-}

    -- | Pop the first value from the end of the 'Deque'

    --

    -- @since 0.1.9.0

    popBackDeque
      :: (V.MVector v a, PrimMonad m)
      => Deque v (PrimState m) a
      -> m (Maybe a)
    popBackDeque :: forall (v :: * -> * -> *) a (m :: * -> *).
    (MVector v a, PrimMonad m) =>
    Deque v (PrimState m) a -> m (Maybe a)
    popBackDeque (Deque MutVar (PrimState m) (DequeState v (PrimState m) a)
    var) = do
        DequeState v start size <- MutVar (PrimState m) (DequeState v (PrimState m) a)
    -> m (DequeState v (PrimState m) a)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar MutVar (PrimState m) (DequeState v (PrimState m) a)
    var
        if size == 0
            then return Nothing
            else do
                let size' = Int
    size Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1
                    end = Int
    start Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    size'
                    end'
                        | Int
    end Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= v (PrimState m) a -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    V.length v (PrimState m) a
    v = Int
    end Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - v (PrimState m) a -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    V.length v (PrimState m) a
    v
                        | Bool
    otherwise = Int
    end
                x <- V.unsafeRead v end'
                writeMutVar var $! DequeState v start size'
                return (Just x)
    {-# INLINE popBackDeque #-}

    -- | Push a new value to the beginning of the 'Deque'

    --

    -- @since 0.1.9.0

    pushFrontDeque
      :: (V.MVector v a, PrimMonad m)
      => Deque v (PrimState m) a
      -> a
      -> m ()
    pushFrontDeque :: forall (v :: * -> * -> *) a (m :: * -> *).
    (MVector v a, PrimMonad m) =>
    Deque v (PrimState m) a -> a -> m ()
    pushFrontDeque (Deque MutVar (PrimState m) (DequeState v (PrimState m) a)
    var) a
    x = do
        DequeState v start size <- MutVar (PrimState m) (DequeState v (PrimState m) a)
    -> m (DequeState v (PrimState m) a)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar MutVar (PrimState m) (DequeState v (PrimState m) a)
    var
        inner v start size
      where
        inner :: v (PrimState m) a -> Int -> Int -> m ()
    inner v (PrimState m) a
    v Int
    start Int
    size = do
            if Int
    size Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= v (PrimState m) a -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    V.length v (PrimState m) a
    v
                then v (PrimState m) a
    -> Int -> Int -> (v (PrimState m) a -> Int -> Int -> m ()) -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a b.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a
    -> Int -> Int -> (v (PrimState m) a -> Int -> Int -> m b) -> m b
    newVector v (PrimState m) a
    v Int
    start Int
    size v (PrimState m) a -> Int -> Int -> m ()
    inner
                else do
                    let size' :: Int
    size' = Int
    size Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1
                        start' :: Int
    start' = (Int
    start Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) Int -> Int -> Int
    forall a. Integral a => a -> a -> a
    `rem` v (PrimState m) a -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    V.length v (PrimState m) a
    v
                        start'' :: Int
    start''
                            | Int
    start' Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    0 = v (PrimState m) a -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    V.length v (PrimState m) a
    v Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    start'
                            | Bool
    otherwise = Int
    start'
                    v (PrimState m) a -> Int -> a -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    V.unsafeWrite v (PrimState m) a
    v Int
    start'' a
    x
                    MutVar (PrimState m) (DequeState v (PrimState m) a)
    -> DequeState v (PrimState m) a -> m ()
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> a -> m ()
    writeMutVar MutVar (PrimState m) (DequeState v (PrimState m) a)
    MutVar (PrimState m) (DequeState v (PrimState m) a)
    var (DequeState v (PrimState m) a -> m ())
    -> DequeState v (PrimState m) a -> m ()
    forall a b. (a -> b) -> a -> b
    $! v (PrimState m) a -> Int -> Int -> DequeState v (PrimState m) a
    forall (v :: * -> * -> *) s a.
    v s a -> Int -> Int -> DequeState v s a
    DequeState v (PrimState m) a
    v Int
    start'' Int
    size'
    {-# INLINE pushFrontDeque #-}

    -- | Push a new value to the end of the 'Deque'

    --

    -- @since 0.1.9.0

    pushBackDeque
      :: (V.MVector v a, PrimMonad m)
      => Deque v (PrimState m) a
      -> a
      -> m ()
    pushBackDeque :: forall (v :: * -> * -> *) a (m :: * -> *).
    (MVector v a, PrimMonad m) =>
    Deque v (PrimState m) a -> a -> m ()
    pushBackDeque (Deque MutVar (PrimState m) (DequeState v (PrimState m) a)
    var) a
    x = do
        DequeState v start size <- MutVar (PrimState m) (DequeState v (PrimState m) a)
    -> m (DequeState v (PrimState m) a)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar MutVar (PrimState m) (DequeState v (PrimState m) a)
    var
        inner v start size
      where
        inner :: v (PrimState m) a -> Int -> Int -> m ()
    inner v (PrimState m) a
    v Int
    start Int
    size = do
            if Int
    size Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= v (PrimState m) a -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    V.length v (PrimState m) a
    v
                then v (PrimState m) a
    -> Int -> Int -> (v (PrimState m) a -> Int -> Int -> m ()) -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a b.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a
    -> Int -> Int -> (v (PrimState m) a -> Int -> Int -> m b) -> m b
    newVector v (PrimState m) a
    v Int
    start Int
    size v (PrimState m) a -> Int -> Int -> m ()
    inner
                else do
                    let end :: Int
    end = Int
    start Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    size
                        end' :: Int
    end'
                            | Int
    end Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= v (PrimState m) a -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    V.length v (PrimState m) a
    v = Int
    end Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - v (PrimState m) a -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    V.length v (PrimState m) a
    v
                            | Bool
    otherwise = Int
    end
                    v (PrimState m) a -> Int -> a -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    V.unsafeWrite v (PrimState m) a
    v Int
    end' a
    x
                    MutVar (PrimState m) (DequeState v (PrimState m) a)
    -> DequeState v (PrimState m) a -> m ()
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> a -> m ()
    writeMutVar MutVar (PrimState m) (DequeState v (PrimState m) a)
    MutVar (PrimState m) (DequeState v (PrimState m) a)
    var (DequeState v (PrimState m) a -> m ())
    -> DequeState v (PrimState m) a -> m ()
    forall a b. (a -> b) -> a -> b
    $! v (PrimState m) a -> Int -> Int -> DequeState v (PrimState m) a
    forall (v :: * -> * -> *) s a.
    v s a -> Int -> Int -> DequeState v s a
    DequeState v (PrimState m) a
    v Int
    start (Int
    size Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1)
    {-# INLINE pushBackDeque #-}

    -- | Fold over a 'Deque', starting at the beginning. Does not modify the 'Deque'.

    --

    -- @since 0.1.9.0

    foldlDeque
      :: (V.MVector v a, PrimMonad m)
      => (acc -> a -> m acc)
      -> acc
      -> Deque v (PrimState m) a
      -> m acc
    foldlDeque :: forall (v :: * -> * -> *) a (m :: * -> *) acc.
    (MVector v a, PrimMonad m) =>
    (acc -> a -> m acc) -> acc -> Deque v (PrimState m) a -> m acc
    foldlDeque acc -> a -> m acc
    f acc
    acc0 (Deque MutVar (PrimState m) (DequeState v (PrimState m) a)
    var) = do
      DequeState v start size <- MutVar (PrimState m) (DequeState v (PrimState m) a)
    -> m (DequeState v (PrimState m) a)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar MutVar (PrimState m) (DequeState v (PrimState m) a)
    var
      let loop Int
    idx acc
    acc
            | Int
    idx Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    size = acc -> m acc
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure acc
    acc
            | Bool
    otherwise = do
                let idxPlusStart :: Int
    idxPlusStart = Int
    idx Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    start
                    idx' :: Int
    idx'
                      | Int
    idxPlusStart Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= v (PrimState m) a -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    V.length v (PrimState m) a
    v = Int
    idxPlusStart Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - v (PrimState m) a -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    V.length v (PrimState m) a
    v
                      | Bool
    otherwise = Int
    idxPlusStart
                a <- v (PrimState m) a -> Int -> m a
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> m a
    V.unsafeRead v (PrimState m) a
    v Int
    idx'
                acc' <- f acc a
                loop (idx + 1) $! acc'
      loop 0 acc0

    -- | Fold over a 'Deque', starting at the end. Does not modify the 'Deque'.

    --

    -- @since 0.1.9.0

    foldrDeque
      :: (V.MVector v a, PrimMonad m)
      => (a -> acc -> m acc)
      -> acc
      -> Deque v (PrimState m) a
      -> m acc
    foldrDeque :: forall (v :: * -> * -> *) a (m :: * -> *) acc.
    (MVector v a, PrimMonad m) =>
    (a -> acc -> m acc) -> acc -> Deque v (PrimState m) a -> m acc
    foldrDeque a -> acc -> m acc
    f acc
    acc0 (Deque MutVar (PrimState m) (DequeState v (PrimState m) a)
    var) = do
      DequeState v start size <- MutVar (PrimState m) (DequeState v (PrimState m) a)
    -> m (DequeState v (PrimState m) a)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar MutVar (PrimState m) (DequeState v (PrimState m) a)
    var
      let loop Int
    idx acc
    acc
            | Int
    idx Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    0 = acc -> m acc
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure acc
    acc
            | Bool
    otherwise = do
                let idxPlusStart :: Int
    idxPlusStart = Int
    idx Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    start
                    idx' :: Int
    idx'
                      | Int
    idxPlusStart Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= v (PrimState m) a -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    V.length v (PrimState m) a
    v = Int
    idxPlusStart Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - v (PrimState m) a -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    V.length v (PrimState m) a
    v
                      | Bool
    otherwise = Int
    idxPlusStart
                a <- v (PrimState m) a -> Int -> m a
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> m a
    V.unsafeRead v (PrimState m) a
    v Int
    idx'
                acc' <- f a acc
                loop (idx - 1) $! acc'
      loop (size - 1) acc0

    -- | Convert a 'Deque' into a list. Does not modify the 'Deque'.

    --

    -- @since 0.1.9.0

    dequeToList
      :: (V.MVector v a, PrimMonad m)
      => Deque v (PrimState m) a
      -> m [a]
    dequeToList :: forall (v :: * -> * -> *) a (m :: * -> *).
    (MVector v a, PrimMonad m) =>
    Deque v (PrimState m) a -> m [a]
    dequeToList = (a -> [a] -> m [a]) -> [a] -> Deque v (PrimState m) a -> m [a]
    forall (v :: * -> * -> *) a (m :: * -> *) acc.
    (MVector v a, PrimMonad m) =>
    (a -> acc -> m acc) -> acc -> Deque v (PrimState m) a -> m acc
    foldrDeque (\a
    a [a]
    rest -> [a] -> m [a]
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure ([a] -> m [a]) -> [a] -> m [a]
    forall a b. (a -> b) -> a -> b
    $ a
    a a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : [a]
    rest) []
    {-# INLINE dequeToList #-}

    -- | Convert to an immutable vector of any type. If resulting pure vector corresponds to the mutable

    -- one used by the `Deque`, it will be more efficient to use `freezeDeque` instead.

    --

    -- ==== __Example__

    --

    -- >>> :set -XTypeApplications

    -- >>> import qualified RIO.Vector.Unboxed as U

    -- >>> import qualified RIO.Vector.Storable as S

    -- >>> d <- newDeque @U.MVector @Int

    -- >>> mapM_ (pushFrontDeque d) [0..10]

    -- >>> dequeToVector @S.Vector d

    -- [10,9,8,7,6,5,4,3,2,1,0]

    --

    -- @since 0.1.9.0

    dequeToVector :: (VG.Vector v' a, V.MVector v a, PrimMonad m)
                  => Deque v (PrimState m) a -> m (v' a)
    dequeToVector :: forall (v' :: * -> *) a (v :: * -> * -> *) (m :: * -> *).
    (Vector v' a, MVector v a, PrimMonad m) =>
    Deque v (PrimState m) a -> m (v' a)
    dequeToVector Deque v (PrimState m) a
    dq = do
        size <- Deque v (PrimState m) a -> m Int
    forall (m :: * -> *) (v :: * -> * -> *) a.
    PrimMonad m =>
    Deque v (PrimState m) a -> m Int
    getDequeSize Deque v (PrimState m) a
    dq
        mv <- V.unsafeNew size
        foldlDeque (\Int
    i a
    e -> Mutable v' (PrimState m) a -> Int -> a -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    V.unsafeWrite Mutable v' (PrimState m) a
    mv Int
    i a
    e m () -> m Int -> m Int
    forall a b. m a -> m b -> m b
    forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
    >> Int -> m Int
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (Int
    iInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    1)) 0 dq
        VG.unsafeFreeze mv

    newVector :: (PrimMonad m, V.MVector v a)
              => v (PrimState m) a
              -> Int
              -> Int
              -> (v (PrimState m) a -> Int -> Int -> m b)
              -> m b
    newVector :: forall (m :: * -> *) (v :: * -> * -> *) a b.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a
    -> Int -> Int -> (v (PrimState m) a -> Int -> Int -> m b) -> m b
    newVector v (PrimState m) a
    v Int
    size2 Int
    sizeOrig v (PrimState m) a -> Int -> Int -> m b
    f = Bool -> m b -> m b
    forall a. HasCallStack => Bool -> a -> a
    assert (Int
    sizeOrig Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == v (PrimState m) a -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    V.length v (PrimState m) a
    v) (m b -> m b) -> m b -> m b
    forall a b. (a -> b) -> a -> b
    $ do
        v' <- Int -> m (v (PrimState m) a)
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    Int -> m (v (PrimState m) a)
    V.unsafeNew (v (PrimState m) a -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    V.length v (PrimState m) a
    v Int -> Int -> Int
    forall a. Num a => a -> a -> a
    * Int
    2)
        let size1 = v (PrimState m) a -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    V.length v (PrimState m) a
    v Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    size2
        V.unsafeCopy
            (V.unsafeTake size1 v')
            (V.unsafeSlice size2 size1 v)
        V.unsafeCopy
            (V.unsafeSlice size1 size2 v')
            (V.unsafeTake size2 v)
        f v' 0 sizeOrig
    {-# INLINE newVector #-}

    -- | Yield an immutable copy of the underlying mutable vector. The difference from `dequeToVector`

    -- is that the the copy will be performed with a more efficient @memcpy@, rather than element by

    -- element. The downside is that the resulting vector type must be the one that corresponds to the

    -- mutable one that is used in the `Deque`.

    --

    -- ==== __Example__

    --

    -- >>> :set -XTypeApplications

    -- >>> import qualified RIO.Vector.Unboxed as U

    -- >>> d <- newDeque @U.MVector @Int

    -- >>> mapM_ (pushFrontDeque d) [0..10]

    -- >>> freezeDeque @U.Vector d

    -- [10,9,8,7,6,5,4,3,2,1,0]

    --

    -- @since 0.1.9.0

    freezeDeque ::
         (VG.Vector v a, PrimMonad m)
      => Deque (VG.Mutable v) (PrimState m) a
      -> m (v a)
    freezeDeque :: forall (v :: * -> *) a (m :: * -> *).
    (Vector v a, PrimMonad m) =>
    Deque (Mutable v) (PrimState m) a -> m (v a)
    freezeDeque (Deque MutVar (PrimState m) (DequeState (Mutable v) (PrimState m) a)
    var) = do
        state@(DequeState v _ size) <- MutVar (PrimState m) (DequeState (Mutable v) (PrimState m) a)
    -> m (DequeState (Mutable v) (PrimState m) a)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar MutVar (PrimState m) (DequeState (Mutable v) (PrimState m) a)
    var
        v' <- V.unsafeNew size
        makeCopy v' state
        VG.unsafeFreeze v'

    makeCopy ::
         (V.MVector v a, PrimMonad m)
      => v (PrimState m) a
      -> DequeState v (PrimState m) a
      -> m ()
    makeCopy :: forall (v :: * -> * -> *) a (m :: * -> *).
    (MVector v a, PrimMonad m) =>
    v (PrimState m) a -> DequeState v (PrimState m) a -> m ()
    makeCopy v (PrimState m) a
    v' (DequeState v (PrimState m) a
    v Int
    start Int
    size) = do
        let size1 :: Int
    size1 = Int -> Int -> Int
    forall a. Ord a => a -> a -> a
    min Int
    size (v (PrimState m) a -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    V.length v (PrimState m) a
    v Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    start)
            size2 :: Int
    size2 = Int
    size Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    size1
        v (PrimState m) a -> v (PrimState m) a -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> v (PrimState m) a -> m ()
    V.unsafeCopy
            (Int -> v (PrimState m) a -> v (PrimState m) a
    forall (v :: * -> * -> *) a s. MVector v a => Int -> v s a -> v s a
    V.unsafeTake Int
    size1 v (PrimState m) a
    v')
            (Int -> Int -> v (PrimState m) a -> v (PrimState m) a
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    Int -> Int -> v s a -> v s a
    V.unsafeSlice Int
    start Int
    size1 v (PrimState m) a
    v)
        Bool -> m () -> m ()
    forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
    when (Int
    size Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    size1) (m () -> m ()) -> m () -> m ()
    forall a b. (a -> b) -> a -> b
    $ v (PrimState m) a -> v (PrimState m) a -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> v (PrimState m) a -> m ()
    V.unsafeCopy
            (Int -> Int -> v (PrimState m) a -> v (PrimState m) a
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    Int -> Int -> v s a -> v s a
    V.unsafeSlice Int
    size1 Int
    size2 v (PrimState m) a
    v')
            (Int -> v (PrimState m) a -> v (PrimState m) a
    forall (v :: * -> * -> *) a s. MVector v a => Int -> v s a -> v s a
    V.unsafeTake Int
    size2 v (PrimState m) a
    v)
    {-# INLINE makeCopy #-}