{-# 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 {
forall a. Queue a -> Int
outsz :: Int,
forall a. Queue a -> [a]
outs :: [a],
forall a. Queue a -> Int
insz :: Int,
forall a. Queue a -> [a]
ins :: [a]
} deriving stock Queue a -> Queue a -> Bool
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 :: forall a. Queue a
empty = forall a. Int -> [a] -> Int -> [a] -> Queue a
Queue Int
0 [] Int
0 []
enqueue :: a -> Queue a -> Queue a
enqueue :: forall a. a -> Queue a -> Queue a
enqueue a
x Queue a
q = Queue a
q {insz :: Int
insz = forall a. Queue a -> Int
insz Queue a
q forall a. Num a => a -> a -> a
+ Int
1, ins :: [a]
ins = a
x forall a. a -> [a] -> [a]
: forall a. Queue a -> [a]
ins Queue a
q}
enqueueAll :: [a] -> Queue a -> Queue a
enqueueAll :: forall a. [a] -> Queue a -> Queue a
enqueueAll [a]
xs Queue a
q = Queue a
q { insz :: Int
insz = forall a. Queue a -> Int
insz Queue a
q forall a. Num a => a -> a -> a
+ forall (t :: Type -> Type) a. Foldable t => t a -> Int
length [a]
xs, ins :: [a]
ins = forall (t :: Type -> Type) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (forall a b c. (a -> b -> c) -> b -> a -> c
flip (:)) (forall a. Queue a -> [a]
ins Queue a
q) [a]
xs }
dequeue :: Queue a -> (a, Queue a)
dequeue :: forall a. Queue a -> (a, Queue a)
dequeue q :: Queue a
q@(forall a. Queue a -> [a]
outs -> (a
x:[a]
outs')) = (a
x, Queue a
q {outsz :: Int
outsz = forall a. Queue a -> Int
outsz Queue a
q forall a. Num a => a -> a -> a
- Int
1, outs :: [a]
outs = [a]
outs'})
dequeue q :: Queue a
q@(forall a. Queue a -> [a]
outs -> [])
| forall a. Queue a -> Int
insz Queue a
q forall a. Eq a => a -> a -> Bool
/= Int
0 = forall a. Queue a -> (a, Queue a)
dequeue (forall a. Int -> [a] -> Int -> [a] -> Queue a
Queue (forall a. Queue a -> Int
insz Queue a
q) (forall a. [a] -> [a]
reverse (forall a. Queue a -> [a]
ins Queue a
q)) Int
0 [])
| Bool
otherwise = forall a. HasCallStack => [Char] -> a
error [Char]
"dequeue of empty queue"
poke :: (a -> a) -> Queue a -> (a, Queue a)
poke :: forall a. (a -> a) -> Queue a -> (a, Queue a)
poke a -> a
f q :: Queue a
q@(forall a. Queue a -> [a]
outs -> (a
x:[a]
outs')) = (a
x, Queue a
q {outs :: [a]
outs = a -> a
f a
x forall a. a -> [a] -> [a]
: [a]
outs'})
poke a -> a
f q :: Queue a
q@(forall a. Queue a -> [a]
outs -> [])
| forall a. Queue a -> Int
insz Queue a
q forall a. Eq a => a -> a -> Bool
/= Int
0 = forall a. (a -> a) -> Queue a -> (a, Queue a)
poke a -> a
f (forall a. Int -> [a] -> Int -> [a] -> Queue a
Queue (forall a. Queue a -> Int
insz Queue a
q) (forall a. [a] -> [a]
reverse (forall a. Queue a -> [a]
ins Queue a
q)) Int
0 [])
| Bool
otherwise = forall a. HasCallStack => [Char] -> a
error [Char]
"poke of empty queue"
null :: Queue a -> Bool
null :: forall a. Queue a -> Bool
null (Queue Int
0 [] Int
0 []) = Bool
True
null Queue a
_ = Bool
False
size :: Queue a -> Int
size :: forall a. Queue a -> Int
size Queue a
q = forall a. Queue a -> Int
insz Queue a
q forall a. Num a => a -> a -> a
+ forall a. Queue a -> Int
outsz Queue a
q
foldr :: (a -> b -> b) -> b -> Queue a -> b
foldr :: forall a b. (a -> b -> b) -> b -> Queue a -> b
foldr a -> b -> b
f b
k = forall (t :: Type -> Type) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Prelude.foldr a -> b -> b
f b
k forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Queue a -> [a]
toList
instance Show a => Show (Queue a) where
show :: Queue a -> [Char]
show = forall a. Show a => a -> [Char]
show forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Queue a -> [a]
toList
toList :: Queue a -> [a]
toList :: forall a. Queue a -> [a]
toList Queue a
q = forall a. Queue a -> [a]
outs Queue a
q forall a. [a] -> [a] -> [a]
++ forall a. [a] -> [a]
reverse (forall a. Queue a -> [a]
ins Queue a
q)