module SuperQueue (Queue, empty, enqueue, dequeue) where
import Test.QuickCheck
import Test.QuickCheck.Poly (A)

data Queue a = Queue [a] [a]

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

isEmpty :: Queue a -> Bool
isEmpty (Queue [] []) = True
isEmpty _ = False

enqueue :: a -> Queue a -> Queue a
enqueue x (Queue front kcab) = Queue front (x : kcab)

dequeue :: Queue a -> (a, Queue a)
dequeue (Queue [] kcab) = dequeue (Queue (reverse kcab) [])
dequeue (Queue front kcab) = (head front, Queue (tail front) kcab)

toList :: Queue a -> [a]
toList (Queue front kcab) = front ++ reverse kcab

instance Eq a => Eq (Queue a) where
  q == q' = toList q == toList q'

instance Show a => Show (Queue a) where
  show = show . toList


{- QuickCheck Tests -}

instance Arbitrary a => Arbitrary (Queue a) where
  arbitrary =
    do
      front <- arbitrary
      kcab <- arbitrary
      return $ Queue front kcab

prop_isEmpty_empty = isEmpty empty

prop_isEmpty_enqueue x q = not (isEmpty (enqueue (x :: A) q))

prop_toList_enqueue x q = toList (enqueue x q) == toList q ++ [x :: A]

prop_toList_dequeue x q =
  not (isEmpty q) ==> (x :: A) : toList q' == toList q
  where (x, q') = dequeue q

prop_toList_ext q q' =
  toList q == toList q' ==> (q :: Queue A) == q'