(*
 * queue.fs
 * Author: Angel Rosario - 841127893
 * Date: November 23, 2014
 * Source (implementation) file for a generic queue.
 * This is the implementation (source) file of the data structure Queue.
 *)

// Indicates the namespace that contains the Queue module.
namespace FunctionalCollections

// Defines the EmptyQueue exception.
exception EmptyQueue of string


// Declares the Queue module.
module Queue =
    // Declares the queue data type.
    type 'a queue = QueueList of 'a list * 'a list

    // Returns a new empty queue.
    let empty = QueueList([], [])

    // Determines whether a queue is empty.
    let isEmpty = function
        | QueueList([], []) -> true
        |_ -> false

    // Adds an element to the front of a queue.
    let add elem (QueueList (remElems, addElems)) = QueueList (remElems, elem::addElems)

    let rec fillLeftList (QueueList (remElems, addElems)) =
        match remElems, addElems with
        | _, [] -> QueueList (remElems, [])
        | rem, hd::tail -> fillLeftList (QueueList (hd::rem, tail) )


    // Removes the element at the front of a queue.
    // Raises EmptyQueue exception if needed.      QueueList([1;2;3],[])
    let rec remove = function
        | QueueList([], []) -> raise (EmptyQueue "queue is empty")
        | QueueList([], elems) -> remove (fillLeftList (QueueList([], elems)))
        | QueueList(_::tl, elems) -> QueueList (tl, elems)


    // Returns the element at the top of a queue.
    // Raises EmptyQueue exception if needed.
    let rec peek = function
        | QueueList([], []) -> raise (EmptyQueue "queue is empty")
        | QueueList([], elem) -> peek (fillLeftList (QueueList([], elem)))
        | QueueList (hd::_,_) -> hd

    // Iterates through a queue using a visit function.
    let rec iter visit = function
        | QueueList ([],[]) -> ()
        | QueueList ([], elems) -> iter visit (fillLeftList (QueueList ([], elems)))
        | QueueList (hd::tl, elems) -> visit hd
                                       iter visit (QueueList (tl, elems))