module Queue (
  Q
 ,empty   -- :: Q a
 ,add     -- :: a -> Q a -> Q a
 ,remove  -- :: Q a -> Q a
 ,front   -- :: Q a -> a
 ,isEmpty -- :: Q a -> Bool
  ) where

import Test.QuickCheck

import qualified QueueSlow as Slow


------------------------------------------------------------
-- Interface

empty   :: Q a
add     :: a -> Q a -> Q a
remove  :: Q a -> Q a
front   :: Q a -> a
isEmpty :: Q a -> Bool



------------------------------------------------------------
-- Implementation

data Q a = Q [a] [a]
  deriving (Eq, Show)

empty                     = Q [] []
add a (Q front back)      = fixQ front (a:back)
remove (Q (_:front) back) = fixQ front back
front  (Q (a:_) _)        = a
isEmpty (Q front back)    = null front && null back

fixQ []    back = Q (reverse back) []
fixQ front back = Q front back


-- Test the operations by comparing to the slow queue

contents :: Q Int -> Slow.Q Int
contents (Q front back) = Slow.Q (front ++ reverse back)

prop_invariant :: Q Int -> Bool
prop_invariant (Q front back) = not (null front && not (null back))

prop_add_inv a q =
     prop_invariant $ add a q
prop_empty_inv =
     prop_invariant empty
prop_remove_inv q = not (isEmpty q) ==>
     prop_invariant $ remove q

------------
prop_empty = contents empty == Slow.empty

prop_add x q =
  contents (add x q) == Slow.add x (contents q)

prop_remove q = not (isEmpty q) ==> 
   contents (remove q) == Slow.remove (contents q)

prop_front q = not (isEmpty q) ==> 
    front q == Slow.front (contents q)

prop_isEmpty q =
  isEmpty q == Slow.isEmpty (contents q)

instance Arbitrary a => Arbitrary (Q a) where
  arbitrary = do
      front <- arbitrary
      back <- arbitrary
      return $ if null front then Q back front else Q front back

test_all = do
    quickCheck prop_invariant
    quickCheck prop_empty
    quickCheck prop_add
    quickCheck prop_remove
    quickCheck prop_front
    quickCheck prop_isEmpty
    quickCheck prop_empty_inv
    quickCheck prop_add_inv
    quickCheck prop_remove_inv