module Data.Queue
    ( Queue(..)
    , empty
    , isEmpty
    , push
    , pop
    ) where

-- From Okasaki's Purely Functional Data Structures
data Queue a =
    Queue { enqueue :: [a]
          , dequeue :: [a]
          } deriving (Eq, Show)

isEmpty :: Queue a -> Bool
isEmpty xs = length (enqueue xs) == 0
          && length (dequeue xs) == 0

empty :: Queue a
empty = Queue [] []

-- adds an item
push :: a -> Queue a -> Queue a
push x xs = Queue { enqueue = x : (enqueue xs)
                  , dequeue = dequeue xs }

pop :: Queue a -> Maybe (a, Queue a)
pop xs = popFromLists (enqueue xs) (dequeue xs)
    where popFromLists [] [] = Nothing
          popFromLists en (d:de) = Just (d, Queue en de)
          popFromLists en [] = popFromLists [] (reverse en)

-- We’re going to give you less code this time, but your task is to
-- implement the above and write a benchmark comparing it against
-- performing alternating pushes and pops from a queue based on a
-- single list. Alternating so that you can’t take advantage of reversing
-- the list after a long series of pushes in order to perform a long series
-- of pops efficiently.
--
-- Don’t forget to handle the case where the dequeue is empty and
-- you need to shift items from the enqueue to the dequeue. You need
-- to do so without violating “first come, first served”.
-- Lastly, benchmark it against Sequence. Come up with a variety of
-- tests. Add additional operations for your Queue type if you want.