content: {-# OPTIONS_GHC -Wno-incomplete-patterns #-}
  {-# LANGUAGE DerivingStrategies, ViewPatterns #-}
  {-|
  Module      : Parsley.Internal.Common.Queue.Impl
  Description : Implementation of a queue.
  License     : BSD-3-Clause
  Maintainer  : Jamie Willis
  Stability   : experimental
  
  Implementation of a FIFO queue structure, with amortized operations.
  
  @since 1.5.0.0
  -}
  module Parsley.Internal.Common.Queue.Impl (
      module Parsley.Internal.Common.Queue.Impl
    ) where
  
  import Prelude hiding (null, foldr)
  import Data.List (foldl')
  
  import qualified Prelude (foldr)
  
  {-|
  Concrete FIFO Queue, with amortized constant operations.
  
  @since 1.5.0.0
  -}
  data Queue a = Queue {
    outsz :: Int,
    outs  :: [a],
    insz  :: Int,
    ins   :: [a]
  } deriving stock Eq
  
  {-|
  Construct an empty queue.
  
  @since 1.5.0.0
  -}
  empty :: Queue a
  empty = Queue 0 [] 0 []
  
  {-|
  Adds an element onto the end of the queue.
  
  @since 1.5.0.0
  -}
  enqueue :: a -> Queue a -> Queue a
  enqueue x q = q {insz = insz q + 1, ins = x : ins q}
  
  {-|
  Adds each of the elements onto the queue, from left-to-right.
  
  @since 1.5.0.0
  -}
  enqueueAll :: [a] -> Queue a -> Queue a
  enqueueAll xs q = q { insz = insz q + length xs, ins = foldl' (flip (:)) (ins q) xs }
  
  {-|
  Removes an element from the front of the queue.
  
  @since 1.5.0.0
  -}
  dequeue :: Queue a -> (a, Queue a)
  dequeue q@(outs -> (x:outs')) = (x, q {outsz = outsz q - 1, outs = outs'})
  dequeue q@(outs -> [])
    | insz q /= 0 = dequeue (Queue (insz q) (reverse (ins q)) 0 [])
    | otherwise   = error "dequeue of empty queue"
  
  {-|
  modifies the head of the queue, without removal. Returns the old head
  
  @since 2.1.0.0
  -}
  poke :: (a -> a) -> Queue a -> (a, Queue a)
  poke f q@(outs -> (x:outs')) = (x, q {outs = f x : outs'})
  poke f q@(outs -> [])
    | insz q /= 0 = poke f (Queue (insz q) (reverse (ins q)) 0 [])
    | otherwise   = error "poke of empty queue"
  
  {-|
  Is the queue empty?
  
  @since 1.5.0.0
  -}
  null :: Queue a -> Bool
  null (Queue 0 [] 0 []) = True
  null _ = False
  
  {-|
  Returns how many elements are in the queue.
  
  @since 1.5.0.0
  -}
  size :: Queue a -> Int
  size q = insz q + outsz q
  
  {-|
  Folds the values in the queue.
  
  @since 1.5.0.0
  -}
  foldr :: (a -> b -> b) -> b -> Queue a -> b
  foldr f k = Prelude.foldr f k . toList
  
  instance Show a => Show (Queue a) where
    show = show . toList
  
  {-|
  Converts this queue into a list.
  
  @since 1.5.0.0
  -}
  toList :: Queue a -> [a]
  toList q = outs q ++ reverse (ins q)
  