-- Taken from
--   Purely Functional Data Structures
--   Chris Okasaki
--   Cambridge University Press, 1998
--
-- Translated from ML to Haskell
-- with exports and type signatures simplified for casual use by
-- Albert Y.C. Lai

module ScheduledQueue(ScheduledQueue, empty, isEmpty, snoc, hd, tl) where

data ScheduledQueue a = SQ [a] [a] [a]

rotate [] (y:_) a      = y : a
rotate (x:xs) (y:ys) a = x : rotate xs ys (y:a)

exec f r (x:xs) = SQ f r xs
exec f r []     = let f' = rotate f r [] in SQ f' [] f'

empty = SQ [] [] []

isEmpty (SQ [] _ _) = True
isEmpty _           = False

snoc (SQ f r s) x = exec f (x:r) s

hd (SQ (x:f) r s) = x
hd _              = error "ScheduledQueue.hd: empty queue"

tl (SQ (x:f) r s) = exec f r s
tl _              = error "ScheduledQueue.tl: empty queue"