module Queue where

import qualified SlowQueue as Slow
import Test.QuickCheck

------------------------------------------------------------------

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

------------------------------------------------------------------

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

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

------------------------------------------------------------------

fixQ :: [a] -> [a] -> Q a
fixQ []    back = Q (reverse back) []
fixQ front back = Q front back

------------------------------------------------------------------

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

------------------------------------------------------------------

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

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

------------------------------------------------------------------

prop_invariant q =
  invariant 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)

------------------------------------------------------------------

prop_empty_inv =
  invariant empty

prop_add_inv x q =
  invariant (add x q)

prop_remove_inv q =
  not (isEmpty q) ==>
    invariant (remove q)

------------------------------------------------------------------

main = 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