{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}

-- | A basic first-in, first-out queue implementation implementing the 'Queuelike' abstraction.
module Data.Queue.Queue (Queue) where

import Data.Maybe
import Data.Queue.Class
import Data.Monoid

data Queue e = Queue {-# UNPACK #-} !Int [e] [e] [e]

instance Queuelike (Queue e) e where
	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 (a:as)) = Queue n l r as
mkQ (Queue n l r []) = let	rot ls ~(r:rs) a = case ls of
					[]	-> r:a
					(l:ls)	-> l:rot ls rs (r:a)
				l' = rot l r [] in Queue n l' [] l'

instance Monoid (Queue e) where
	mempty = empty
	mappend = merge