(* L'interfaccia di una coda *)

module type QUEUE =
sig
  type 'a queue
  val empty     : 'a queue
  val isEmpty   : 'a queue -> bool
  val snoc      : 'a queue -> 'a -> 'a queue
  val head      : 'a queue -> 'a
  val tail      : 'a queue -> 'a queue
end

exception Empty_Queue

(* Una code divisa in front list e rear list *)

module Queue : QUEUE =
struct

  (* se la front list e' vuota allora anche la rear list deve essere vuota *)
  type 'a queue = 'a list * 'a list

  let empty = ([],[])

  let isEmpty q = match q with
    ([],_) -> true
  | _ -> false

  let snoc q x = match q with
    ([],_) -> ([x],[])
  | (f,r) -> (f,x::r)

  let head q = match q with
    (x::_,_) -> x
  | _ -> raise Empty_Queue

  (* inverte una lista in O(n) usando un accumulatore *)
  let rec reverse_acc lst acc = match lst with
    [] -> acc
  | h::t -> reverse_acc t (h::acc)

  let reverse lst = reverse_acc lst []

  let tail q = match q with
    ([x],r) -> (reverse r,[])
  | (x::f,r) -> (f,r)
  | _ -> raise Empty_Queue

end