    {-# 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 :: 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 :: 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 :: 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 :: m (Deque v (PrimState m) a)
    newDeque = do
        v (PrimState m) a
    v <- Int -> m (v (PrimState m) a)
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    Int -> m (v (PrimState m) a)
    V.new Int
    baseSize
        (MutVar (PrimState m) (DequeState v (PrimState m) a)
     -> Deque v (PrimState m) a)
    -> m (MutVar (PrimState m) (DequeState v (PrimState m) a))
    -> m (Deque v (PrimState m) a)
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM MutVar (PrimState m) (DequeState v (PrimState m) a)
    -> Deque v (PrimState m) a
    forall (v :: * -> * -> *) s a.
    MutVar s (DequeState v s a) -> Deque v s a
    Deque (m (MutVar (PrimState m) (DequeState v (PrimState m) a))
     -> m (Deque v (PrimState m) a))
    -> m (MutVar (PrimState m) (DequeState v (PrimState m) a))
    -> m (Deque v (PrimState m) a)
    forall a b. (a -> b) -> a -> b
    $ DequeState v (PrimState m) a
    -> m (MutVar (PrimState m) (DequeState v (PrimState m) a))
    forall (m :: * -> *) a.
    PrimMonad m =>
    a -> m (MutVar (PrimState m) a)
    newMutVar (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 0 0)
      where
        baseSize :: Int
    baseSize = 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 :: Deque v (PrimState m) a -> m Int
    getDequeSize (Deque var :: MutVar (PrimState m) (DequeState v (PrimState m) a)
    var) = do
      DequeState _ _ size :: Int
    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
      Int -> m Int
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Int
    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 :: Deque v (PrimState m) a -> m (Maybe a)
    popFrontDeque (Deque var :: MutVar (PrimState m) (DequeState v (PrimState m) a)
    var) = do
        DequeState v :: v (PrimState m) a
    v start :: Int
    start size :: Int
    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 Int
    size Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == 0
            then Maybe a -> m (Maybe a)
    forall (m :: * -> *) a. Monad m => a -> m a
    return Maybe a
    forall a. Maybe a
    Nothing
            else do
                a
    x <- 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
    start
                let start' :: Int
    start' = Int
    start Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + 1
                    start'' :: Int
    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 = 0
                        | Bool
    otherwise = Int
    start'
                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)
    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
    - 1)
                Maybe a -> m (Maybe a)
    forall (m :: * -> *) a. Monad m => a -> m a
    return (Maybe a -> m (Maybe a)) -> Maybe a -> m (Maybe a)
    forall a b. (a -> b) -> a -> b
    $! a -> Maybe a
    forall a. a -> Maybe a
    Just a
    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 :: Deque v (PrimState m) a -> m (Maybe a)
    popBackDeque (Deque var :: MutVar (PrimState m) (DequeState v (PrimState m) a)
    var) = do
        DequeState v :: v (PrimState m) a
    v start :: Int
    start size :: Int
    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 Int
    size Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == 0
            then Maybe a -> m (Maybe a)
    forall (m :: * -> *) a. Monad m => a -> m a
    return Maybe a
    forall a. Maybe a
    Nothing
            else do
                let size' :: Int
    size' = Int
    size Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - 1
                    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
                a
    x <- 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
    end'
                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)
    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'
                Maybe a -> m (Maybe a)
    forall (m :: * -> *) a. Monad m => a -> m a
    return (Maybe a -> m (Maybe a)) -> Maybe a -> m (Maybe a)
    forall a b. (a -> b) -> a -> b
    $! a -> Maybe a
    forall a. a -> Maybe a
    Just a
    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 :: Deque v (PrimState m) a -> a -> m ()
    pushFrontDeque (Deque var :: MutVar (PrimState m) (DequeState v (PrimState m) a)
    var) x :: a
    x = do
        DequeState v :: v (PrimState m) a
    v start :: Int
    start size :: Int
    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
        v (PrimState m) a -> Int -> Int -> m ()
    inner v (PrimState m) a
    v Int
    start Int
    size
      where
        inner :: v (PrimState m) a -> Int -> Int -> m ()
    inner v :: v (PrimState m) a
    v start :: Int
    start size :: 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
    + 1
                        start' :: Int
    start' = (Int
    start Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - 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
    < 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)
    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 :: Deque v (PrimState m) a -> a -> m ()
    pushBackDeque (Deque var :: MutVar (PrimState m) (DequeState v (PrimState m) a)
    var) x :: a
    x = do
        DequeState v :: v (PrimState m) a
    v start :: Int
    start size :: Int
    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
        v (PrimState m) a -> Int -> Int -> m ()
    inner v (PrimState m) a
    v Int
    start Int
    size
      where
        inner :: v (PrimState m) a -> Int -> Int -> m ()
    inner v :: v (PrimState m) a
    v start :: Int
    start size :: 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)
    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
    + 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 :: (acc -> a -> m acc) -> acc -> Deque v (PrimState m) a -> m acc
    foldlDeque f :: acc -> a -> m acc
    f acc0 :: acc
    acc0 (Deque var :: MutVar (PrimState m) (DequeState v (PrimState m) a)
    var) = do
      DequeState v :: v (PrimState m) a
    v start :: Int
    start size :: Int
    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 -> acc -> m acc
    loop idx :: Int
    idx acc :: acc
    acc
            | Int
    idx Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    size = acc -> m acc
    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
    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
    acc' <- acc -> a -> m acc
    f acc
    acc a
    a
                Int -> acc -> m acc
    loop (Int
    idx Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + 1) (acc -> m acc) -> acc -> m acc
    forall a b. (a -> b) -> a -> b
    $! acc
    acc'
      Int -> acc -> m acc
    loop 0 acc
    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 :: (a -> acc -> m acc) -> acc -> Deque v (PrimState m) a -> m acc
    foldrDeque f :: a -> acc -> m acc
    f acc0 :: acc
    acc0 (Deque var :: MutVar (PrimState m) (DequeState v (PrimState m) a)
    var) = do
      DequeState v :: v (PrimState m) a
    v start :: Int
    start size :: Int
    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 -> acc -> m acc
    loop idx :: Int
    idx acc :: acc
    acc
            | Int
    idx Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < 0 = acc -> m acc
    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
    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
    acc' <- a -> acc -> m acc
    f a
    a acc
    acc
                Int -> acc -> m acc
    loop (Int
    idx Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - 1) (acc -> m acc) -> acc -> m acc
    forall a b. (a -> b) -> a -> b
    $! acc
    acc'
      Int -> acc -> m acc
    loop (Int
    size Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - 1) acc
    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 :: 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]
    rest -> [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 :: Deque v (PrimState m) a -> m (v' a)
    dequeToVector dq :: Deque v (PrimState m) a
    dq = do
        Int
    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
        Mutable v' (PrimState m) a
    mv <- Int -> m (Mutable v' (PrimState m) a)
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    Int -> m (v (PrimState m) a)
    V.unsafeNew Int
    size
        (Int -> a -> m Int) -> Int -> Deque v (PrimState m) a -> m Int
    forall (v :: * -> * -> *) a (m :: * -> *) acc.
    (MVector v a, PrimMonad m) =>
    (acc -> a -> m acc) -> acc -> Deque v (PrimState m) a -> m acc
    foldlDeque (\i :: Int
    i e :: 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 (m :: * -> *) a b. Monad m => m a -> m b -> m b
    >> Int -> m Int
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (Int
    iInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +1)) 0 Deque v (PrimState m) a
    dq
        Mutable v' (PrimState m) a -> m (v' a)
    forall (m :: * -> *) (v :: * -> *) a.
    (PrimMonad m, Vector v a) =>
    Mutable v (PrimState m) a -> m (v a)
    VG.unsafeFreeze Mutable v' (PrimState m) a
    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 :: v (PrimState m) a
    -> Int -> Int -> (v (PrimState m) a -> Int -> Int -> m b) -> m b
    newVector v :: v (PrimState m) a
    v size2 :: Int
    size2 sizeOrig :: Int
    sizeOrig f :: v (PrimState m) a -> Int -> Int -> m b
    f = Bool -> m b -> m b
    forall a. (?callStack::CallStack) => 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 (PrimState m) a
    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
    * 2)
        let size1 :: Int
    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 (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
    size2 Int
    size1 v (PrimState m) a
    v)
        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)
        v (PrimState m) a -> Int -> Int -> m b
    f v (PrimState m) a
    v' 0 Int
    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 :: Deque (Mutable v) (PrimState m) a -> m (v a)
    freezeDeque (Deque var :: MutVar (PrimState m) (DequeState (Mutable v) (PrimState m) a)
    var) = do
        state :: DequeState (Mutable v) (PrimState m) a
    state@(DequeState v :: Mutable v (PrimState m) a
    v _ size :: Int
    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
        Mutable v (PrimState m) a
    v' <- Int -> m (Mutable v (PrimState m) a)
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    Int -> m (v (PrimState m) a)
    V.unsafeNew Int
    size
        Mutable v (PrimState m) a
    -> DequeState (Mutable v) (PrimState m) a -> m ()
    forall (v :: * -> * -> *) a (m :: * -> *).
    (MVector v a, PrimMonad m) =>
    v (PrimState m) a -> DequeState v (PrimState m) a -> m ()
    makeCopy Mutable v (PrimState m) a
    v' DequeState (Mutable v) (PrimState m) a
    state
        Mutable v (PrimState m) a -> m (v a)
    forall (m :: * -> *) (v :: * -> *) a.
    (PrimMonad m, Vector v a) =>
    Mutable v (PrimState m) a -> m (v a)
    VG.unsafeFreeze Mutable v (PrimState m) a
    v'

    makeCopy ::
         (V.MVector v a, PrimMonad m)
      => v (PrimState m) a
      -> DequeState v (PrimState m) a
      -> m ()
    makeCopy :: v (PrimState m) a -> DequeState v (PrimState m) a -> m ()
    makeCopy v' :: v (PrimState m) a
    v' (DequeState v :: v (PrimState m) a
    v start :: Int
    start size :: 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 #-}