module Data.Queue.Queue (Queue) where
import Data.Maybe
import Data.Queue.Class
import Data.Monoid
data Queue e = Queue !Int [e] [e] [e]
instance Queuelike (Queue e) where
type QueueKey (Queue e) = e
singleton x = Queue 1 [x] [] [x]
empty = Queue 0 [] [] []
isEmpty = (==0) . size
size (Queue n _ _ _) = n
x `insert` Queue n l r a = mkQ (Queue (n+1) l (x:r) a)
peek (Queue _ l _ _) = listToMaybe l
delete (Queue (n+1) (_:l) r a) = Just (mkQ (Queue n l r a))
delete _ = Nothing
mkQ :: Queue e -> Queue e
mkQ (Queue n l r (_:as)) = Queue n l r as
mkQ (Queue n ll rr []) = let rot ls ~(r:rs) a = case ls of
[] -> r:a
(l:ls) -> l:rot ls rs (r:a)
l' = rot ll rr [] in Queue n l' [] l'
instance Monoid (Queue e) where
mempty = empty
mappend = merge