(* ------------------------------------- Toolbox files : FIFO -------------------------------------*)


(* ---- Définition des files et constructeurs ---- *)

type 'a cell = {mutable father:'a ptr ; mutable son:'a ptr ; mutable item: 'a}
and 'a ptr = Nil | Box of 'a cell
and 'a queue = {mutable first:'a ptr ; mutable last: 'a ptr};;

let make_empty_queue ()=
  {first=Nil ; last=Nil};;
(*make_empty_queue : unit -> 'a queue = <fun>*)

let is_empty_queue queue = ((queue.first = Nil) & (queue.last = Nil));;
(*is_empty_queue : 'a queue -> bool = <fun>*)


(* ---- Destructeur ---- *)

let pointed_value=function
	  Box(x) -> x
	| Nil    -> failwith "pointed_value : no Pointed value" ;;
(*pointed_value : 'a ptr -> 'a cell = <fun>*)


(* ---- Traducteur file -> liste ---- *)

let queue2list q=
	let rec aux=function
		  Nil -> []
		| (Box x)->(x.item)::(aux x.son)
	in aux q.first;;
(*queue2list : 'a queue -> 'a list = <fun>*)


(* ---- Fonctions de base : push et pop ---- *)

let push it queue =
  if (is_empty_queue queue)
  then
    begin
      let new_box  = Box{father = Nil ; son = queue.first ; item = it} in
	queue.first <- new_box;
	queue.last  <- new_box
    end
  else
    begin
      let new_box  = Box {father = Nil ; son = queue.first ; item = it} in
	(pointed_value (queue.first)).father <- new_box;
       	queue.first <- new_box
    end;;
(*push : 'a -> 'a queue -> unit = <fun>*)

let pop queue =
  if (is_empty_queue queue)
  then
   failwith "pop : empty queue"
  else
    let pointed = pointed_value queue.last in
    if queue.first=queue.last
    	then
    	begin
    	  queue.first<-Nil;
    	  queue.last <-Nil;
    	  pointed.item
    	end
    	else let previous=pointed_value pointed.father in
    	begin
    	  previous.son <- Nil;
    	  queue.last<-pointed.father;
    	  pointed.item
    	end;;
(*pop : 'a queue -> 'a = <fun>*)