type 'a file_array = {contenu: 'a array; mutable debut : int; mutable fin: int; mutable vide: bool};;

let is_empty1 file =
  file.vide
;;

let is_plein1 file =
  not(file.vide) && (file.debut = file.fin)
;;

let add_tail1 x file = 
	if is_plein1 file
		then failwith "file pleine"
else
	begin
		file.contenu.(file.fin)<-x;
		file.fin <- ((file.fin +1) mod (Array.length (file.contenu)));
		file.vide <- false;
	end;
;;



let pop_head1 file =
  if is_empty1 file
    then failwith "file pleine"
  else
    begin
      file.debut <- (file.debut + 1) mod (Array.length (file.contenu));
      file.vide <- (file.debut=file.fin);
      file
    end;
;;

let length1 file =
  if is_empty1 file
    then 0
else
  let result = (file.fin - file.debut) in
    if result>0 then result
    else result + Array.length file.contenu
;;

let appartenance1 x file = 
  if is_empty1 file 
    then false
  else 
    begin
      let t = (length1 file) and n = Array.length file.contenu in
      let b = ref false and i = ref 0 in
        while !i<t || !b do
          if file.contenu.((file.debut + !i) mod n)=x then b:= true;
          i:=!i+1
        done;
      !b
    end
;;

type 'a file_list = {mutable sortie: 'a list; mutable entree: 'a list}

let is_empty2 file = match (file.sortie,file.entree) with
| ([],[]) -> true
| _-> false
;;

let add_tail2 x file = 
  file.entree <- x::file.entree;
;;

let rec aux file = match file.entree with
| [] -> ()
|t::q -> file.sortie <- t::file.sortie;
  file.entree <- q;
  aux file
;;


let rec normalize file = 
  if file.sortie = [] then aux file
;;

let pop_head2 file =
  normalize file;
    if file.sortie = [] then failwith "liste vide"
    else
      begin
      let t::q = file.sortie in
      file.sortie <- q;
      t
      end
;;