{-# 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 {
  Queue a -> Int
outsz :: Int,
  Queue a -> [a]
outs  :: [a],
  Queue a -> Int
insz  :: Int,
  Queue a -> [a]
ins   :: [a]
} deriving stock Queue a -> Queue a -> Bool
(Queue a -> Queue a -> Bool)
-> (Queue a -> Queue a -> Bool) -> Eq (Queue a)
forall a. Eq a => Queue a -> Queue a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Queue a -> Queue a -> Bool
$c/= :: forall a. Eq a => Queue a -> Queue a -> Bool
== :: Queue a -> Queue a -> Bool
$c== :: forall a. Eq a => Queue a -> Queue a -> Bool
Eq

{-|
Construct an empty queue.

@since 1.5.0.0
-}
empty :: Queue a
empty :: Queue a
empty = Int -> [a] -> Int -> [a] -> Queue a
forall a. Int -> [a] -> Int -> [a] -> Queue a
Queue Int
0 [] Int
0 []

{-|
Adds an element onto the end of the queue.

@since 1.5.0.0
-}
enqueue :: a -> Queue a -> Queue a
enqueue :: a -> Queue a -> Queue a
enqueue a
x Queue a
q = Queue a
q {insz :: Int
insz = Queue a -> Int
forall a. Queue a -> Int
insz Queue a
q Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1, ins :: [a]
ins = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: Queue a -> [a]
forall a. Queue a -> [a]
ins Queue a
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 :: [a] -> Queue a -> Queue a
enqueueAll [a]
xs Queue a
q = Queue a
q { insz :: Int
insz = Queue a -> Int
forall a. Queue a -> Int
insz Queue a
q Int -> Int -> Int
forall a. Num a => a -> a -> a
+ [a] -> Int
forall (t :: Type -> Type) a. Foldable t => t a -> Int
length [a]
xs, ins :: [a]
ins = ([a] -> a -> [a]) -> [a] -> [a] -> [a]
forall (t :: Type -> Type) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((a -> [a] -> [a]) -> [a] -> a -> [a]
forall a b c. (a -> b -> c) -> b -> a -> c
flip (:)) (Queue a -> [a]
forall a. Queue a -> [a]
ins Queue a
q) [a]
xs }

{-|
Removes an element from the front of the queue.

@since 1.5.0.0
-}
dequeue :: Queue a -> (a, Queue a)
dequeue :: Queue a -> (a, Queue a)
dequeue q :: Queue a
q@(Queue a -> [a]
forall a. Queue a -> [a]
outs -> (a
x:[a]
outs')) = (a
x, Queue a
q {outsz :: Int
outsz = Queue a -> Int
forall a. Queue a -> Int
outsz Queue a
q Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1, outs :: [a]
outs = [a]
outs'})
dequeue q :: Queue a
q@(Queue a -> [a]
forall a. Queue a -> [a]
outs -> [])
  | Queue a -> Int
forall a. Queue a -> Int
insz Queue a
q Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
0 = Queue a -> (a, Queue a)
forall a. Queue a -> (a, Queue a)
dequeue (Int -> [a] -> Int -> [a] -> Queue a
forall a. Int -> [a] -> Int -> [a] -> Queue a
Queue (Queue a -> Int
forall a. Queue a -> Int
insz Queue a
q) ([a] -> [a]
forall a. [a] -> [a]
reverse (Queue a -> [a]
forall a. Queue a -> [a]
ins Queue a
q)) Int
0 [])
  | Bool
otherwise   = [Char] -> (a, Queue a)
forall a. HasCallStack => [Char] -> a
error [Char]
"dequeue of empty queue"

{-|
Is the queue empty?

@since 1.5.0.0
-}
null :: Queue a -> Bool
null :: Queue a -> Bool
null (Queue Int
0 [] Int
0 []) = Bool
True
null Queue a
_ = Bool
False

{-|
Returns how many elements are in the queue.

@since 1.5.0.0
-}
size :: Queue a -> Int
size :: Queue a -> Int
size Queue a
q = Queue a -> Int
forall a. Queue a -> Int
insz Queue a
q Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Queue a -> Int
forall a. Queue a -> Int
outsz Queue a
q

{-|
Folds the values in the queue.

@since 1.5.0.0
-}
foldr :: (a -> b -> b) -> b -> Queue a -> b
foldr :: (a -> b -> b) -> b -> Queue a -> b
foldr a -> b -> b
f b
k = (a -> b -> b) -> b -> [a] -> b
forall (t :: Type -> Type) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Prelude.foldr a -> b -> b
f b
k ([a] -> b) -> (Queue a -> [a]) -> Queue a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Queue a -> [a]
forall a. Queue a -> [a]
toList

instance Show a => Show (Queue a) where
  show :: Queue a -> [Char]
show = [a] -> [Char]
forall a. Show a => a -> [Char]
show ([a] -> [Char]) -> (Queue a -> [a]) -> Queue a -> [Char]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Queue a -> [a]
forall a. Queue a -> [a]
toList

{-|
Converts this queue into a list.

@since 1.5.0.0
-}
toList :: Queue a -> [a]
toList :: Queue a -> [a]
toList Queue a
q = Queue a -> [a]
forall a. Queue a -> [a]
outs Queue a
q [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a] -> [a]
forall a. [a] -> [a]
reverse (Queue a -> [a]
forall a. Queue a -> [a]
ins Queue a
q)