-- File: src/functional/haskell/Queue.hs
-- Copyright (C) 2010 Gregory D. Weber
-- Queues in Haskell, using the "batched queue" technique
-- described in Chris Okasaki, "Purely Functional Data Structures",
-- Cambridge University Press, 1998.
-- This is very similar to the implementation of queues using
-- a pair of stacks, as described in Drake (exercise ?-??),
-- but instead of explicit stacks, we use a pair of lists
-- and treat them more or less as stacks.
-- If a queue contains N elements, then enqueue or dequeue
-- can take O(N), that is, N steps, in the worst case; but because the worst
-- case happens infrequently, their *average* time is O(1),
-- that is, 1 step per operation.

module Queue where

data Queue a = Queue [a] [a] -- outs, ins
    deriving (Show)

newQueue :: Queue a
newQueue = Queue [] []

isEmpty :: Queue a -> Bool
isEmpty (Queue outs ins) = null outs

enqueue :: a -> Queue a -> Queue a
enqueue x (Queue outs ins) = refill outs (x : ins)

-- refill empty outs from ins
refill :: [a] -> [a] -> Queue a
refill outs ins = 
    if null outs
    then Queue (reverse ins) []
    else Queue outs ins

front :: Queue a -> a
front (Queue [] ins) = error "front: empty queue"
front (Queue (o:os) ins) = o

dequeue :: Queue a -> Queue a
dequeue (Queue [] ins) = error "dequeue: empty queue"
dequeue (Queue (o:os) ins) = refill os ins

dequeue' :: Queue a -> (a, Queue a)
dequeue' q = (front q, dequeue q)

testQ :: Queue Int
testQ = enqueue 23 (enqueue 21 newQueue)

-- An "iterator" for queues
toList :: Queue a -> [a]
toList q =
    if isEmpty q
    then []
    else let (front, q') = dequeue' q
         in front : toList q'

fromList :: [a] -> Queue a
fromList alist = 
    let loop [] q = q
        loop (x:xs) q = loop xs (enqueue x q)
    in loop alist newQueue