{-# OPTIONS_GHC -Wno-incomplete-patterns #-}
{-# LANGUAGE DerivingStrategies, ViewPatterns #-}
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)
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
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 []
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}
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 }
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"
null :: Queue a -> Bool
null :: Queue a -> Bool
null (Queue Int
0 [] Int
0 []) = Bool
True
null Queue a
_ = Bool
False
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
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
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)