{-# LANGUAGE TypeFamilies, GeneralizedNewtypeDeriving #-}
{-# OPTIONS -fno-warn-name-shadowing #-}

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

import Data.Monoid
import Data.Queue.Class
import Data.Sequence (Seq, ViewL (..), viewl, (|>))
import qualified Data.Sequence as Seq
import qualified Data.Foldable as Fold
import Prelude hiding (null)

newtype Queue e = Queue (Seq e) deriving (Monoid, Fold.Foldable, Functor)

instance IQueue (Queue e) where
	type QueueKey (Queue e) = e
	empty = mempty
	singleton = Queue . Seq.singleton
	fromList = Queue . Seq.fromList
	
	null (Queue q) = Seq.null q
	size (Queue q) = Seq.length q

	x `insert` Queue q = Queue (q |> x)
	extract (Queue q) = case viewl q of
		EmptyL	-> Nothing
		x :< q'	-> Just (x, Queue q')

	merge = mappend
	mergeAll = mconcat

	toList = Fold.toList