module Data.Graph.Inductive.Internal.Queue(
    -- * Type
    Queue(..),
    -- * Operations
    mkQueue, queuePut, queuePutList, queueGet, queueEmpty
) where

import Data.List (foldl')

data Queue a = MkQueue [a] [a]

mkQueue :: Queue a
mkQueue :: Queue a
mkQueue = [a] -> [a] -> Queue a
forall a. [a] -> [a] -> Queue a
MkQueue [] []

queuePut :: a -> Queue a -> Queue a
queuePut :: a -> Queue a -> Queue a
queuePut a
item (MkQueue [a]
ins [a]
outs) = [a] -> [a] -> Queue a
forall a. [a] -> [a] -> Queue a
MkQueue (a
itema -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ins) [a]
outs

queuePutList :: [a] -> Queue a -> Queue a
queuePutList :: [a] -> Queue a -> Queue a
queuePutList [a]
xs Queue a
q = (Queue a -> a -> Queue a) -> Queue a -> [a] -> Queue a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((a -> Queue a -> Queue a) -> Queue a -> a -> Queue a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> Queue a -> Queue a
forall a. a -> Queue a -> Queue a
queuePut) Queue a
q [a]
xs

queueGet :: Queue a -> (a, Queue a)
queueGet :: Queue a -> (a, Queue a)
queueGet (MkQueue [a]
ins (a
item:[a]
rest)) = (a
item, [a] -> [a] -> Queue a
forall a. [a] -> [a] -> Queue a
MkQueue [a]
ins [a]
rest)
queueGet (MkQueue [a]
ins []) = Queue a -> (a, Queue a)
forall a. Queue a -> (a, Queue a)
queueGet ([a] -> [a] -> Queue a
forall a. [a] -> [a] -> Queue a
MkQueue [] ([a] -> [a]
forall a. [a] -> [a]
reverse [a]
ins))

queueEmpty :: Queue a -> Bool
queueEmpty :: Queue a -> Bool
queueEmpty (MkQueue [a]
ins [a]
outs) = [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [a]
ins Bool -> Bool -> Bool
&& [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [a]
outs