{-# 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 Int
0 Int
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 :: Deque v (PrimState m) a -> m Int
getDequeSize (Deque MutVar (PrimState m) (DequeState v (PrimState m) a)
var) = do
  DequeState v (PrimState m) a
_ Int
_ 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 MutVar (PrimState m) (DequeState v (PrimState m) a)
var) = do
    DequeState v (PrimState m) a
v Int
start 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
== Int
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
+ Int
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 = Int
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
- Int
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 MutVar (PrimState m) (DequeState v (PrimState m) a)
var) = do
    DequeState v (PrimState m) a
v Int
start 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
== Int
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
- Int
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 MutVar (PrimState m) (DequeState v (PrimState m) a)
var) a
x = do
    DequeState v (PrimState m) a
v Int
start 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 (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)
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 MutVar (PrimState m) (DequeState v (PrimState m) a)
var) a
x = do
    DequeState v (PrimState m) a
v Int
start 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 (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)
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 :: (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 (PrimState m) a
v Int
start 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 Int
idx 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
+ Int
1) (acc -> m acc) -> acc -> m acc
forall a b. (a -> b) -> a -> b
$! acc
acc'
  Int -> acc -> m acc
loop Int
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 a -> acc -> m acc
f acc
acc0 (Deque MutVar (PrimState m) (DequeState v (PrimState m) a)
var) = do
  DequeState v (PrimState m) a
v Int
start 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 Int
idx acc
acc
        | Int
idx Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
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
- Int
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
- Int
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] -> 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 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 (\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 (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
+Int
1)) Int
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 (PrimState m) a
v Int
size2 Int
sizeOrig 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
* Int
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' Int
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 MutVar (PrimState m) (DequeState (Mutable v) (PrimState m) a)
var) = do
    state :: DequeState (Mutable v) (PrimState m) a
state@(DequeState Mutable v (PrimState m) a
v Int
_ 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 (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 #-}