(*---------------------------METHODE 0----------------------------------*)


module Methode0 = struct


let taille_buffer = 10;;

let rec enleve_premiers liste = function
  0 -> liste
| n -> enleve_premiers (List.tl liste) (n-1);;

let huit_hd = function
    n1::n2::n3::n4::n5::n6::n7::n8::reste ->  n1::n2::n3::n4::n5::n6::n7::n8::[]
  | _ -> failwith "huit_hd";;

let huit_tl = function
    n1::n2::n3::n4::n5::n6::n7::n8::reste ->  reste
  | _ -> failwith "huit_tl";;


let binary_to_int8 = function
    n1::n2::n3::n4::n5::n6::n7::n8::[] -> n8+n7*2+n6*4+n5*8+n4*16+n3*32+n2*64+n1*128
  |_ -> failwith "binary_to_int8";;

let int_to_binary8 n =
  if (n > 255 || n < 0)
  then failwith "int_to_binary8"
  else
    let temp = ref([])
    and ref_n = ref(n)
    in for i=1 to 8 do
      temp := (!ref_n mod 2) :: !temp;
      ref_n := !ref_n/2;  
    done; 
    !temp;;



let remplit_comp in_channel reste =
  let buffer = ref (List.rev reste)
  and c_ascii = ref [] in
  try
    for i = 1 to taille_buffer do
      c_ascii := int_to_binary8 (input_byte in_channel);
      buffer := (List.rev !c_ascii)@(!buffer);
    done;
    List.rev (!buffer);
  with
    End_of_file -> List.rev (!buffer);;


let rec ecrit_comp in_channel out_channel = function
    n1::n2::n3::n4::n5::n6::n7::n8::reste ->
      (output_byte out_channel (binary_to_int8 (n1::n2::n3::n4::n5::n6::n7::n8::[]));
       ecrit_comp in_channel out_channel reste;)
  | l ->
      let nv_l = remplit_comp in_channel l
      in
      if nv_l = l
      then output_byte out_channel (binary_to_int8 (l@[0;0;0;0;0;0]))
      else ecrit_comp in_channel out_channel nv_l;;
  

let remplit_decomp in_channel reste nb_bits_invalides =
  let buffer = ref (List.rev reste)
  and c_ascii = ref [] in
  try
    for i = 1 to taille_buffer do
      c_ascii := int_to_binary8 (input_byte in_channel);
      buffer := (List.rev !c_ascii)@(!buffer);
    done;
    let ne_sert_a_rien =  input_byte in_channel in
    seek_in in_channel ((pos_in in_channel) - 1);
    List.rev (!buffer);
  with
    End_of_file ->
      if (!buffer = [])
      then []
      else
	begin
	  let derniers_bits = enleve_premiers (huit_hd !buffer) nb_bits_invalides
	  in List.rev (derniers_bits@(huit_tl !buffer));
	end;;


let rec ecrit_decomp in_channel out_channel nb_bits_invalides = function
    n1::n2::n3::n4::n5::n6::n7::n8::reste ->
      (output_byte out_channel (binary_to_int8 (n1::n2::n3::n4::n5::n6::n7::n8::[]));
       ecrit_decomp in_channel out_channel nb_bits_invalides reste;)
  | l ->
      let nv_l = remplit_decomp in_channel l nb_bits_invalides
      in
      if nv_l <> l
      then ecrit_decomp in_channel out_channel nb_bits_invalides nv_l;;



let compresse nom_de_fichier nom_compresse =
  let out_channel = open_out nom_compresse
  and in_channel = open_in nom_de_fichier
  and buffer = ref (0::[0])
  in buffer := remplit_comp in_channel !buffer;
  ecrit_comp in_channel out_channel !buffer;
  close_in in_channel;
  close_out out_channel;;

let decompresse nom_de_fichier nom_decompresse =
  let out_channel = open_out nom_decompresse
  and in_channel  = open_in nom_de_fichier
  in  let buffer = ref (int_to_binary8 (input_byte in_channel)) in
  let bit1 = List.hd !buffer in
  buffer := List.tl !buffer;
  let bit2 = List.hd !buffer in
  buffer := List.tl !buffer;
  if (bit1 <> 0 && bit2 <> 0)
  then failwith "Mauvaise version de compression"
  else
    begin
      buffer := remplit_decomp in_channel !buffer 6;
      ecrit_decomp in_channel out_channel 6 !buffer;
      close_in in_channel;
      close_out out_channel;
    end;;


end


(*---------------------------METHODE 1----------------------------------*)






module Methode1 = struct


let taille_buffer = 30;;

let rec print_list = function
    [] -> print_newline ();
  | a::reste -> (print_int a;
		 print_string " ";
		print_list reste);;
      

    
let rec enleve_premiers liste n = 
  match n with
  0 -> liste
| n -> enleve_premiers (List.tl liste) (n-1);;


let huit_hd = function
    n1::n2::n3::n4::n5::n6::n7::n8::reste ->  n1::n2::n3::n4::n5::n6::n7::n8::[]
  | l -> l;;

let huit_tl = function
    n1::n2::n3::n4::n5::n6::n7::n8::reste ->  reste
  | l -> [];;

										
type arbre =
    Feuille of int
  | Noeud of noeud
and noeud = { fg : arbre ;
	      fd : arbre };;




let suis_je_feuille = function
    Feuille (n) -> true
  | _ -> false;;




let contenu_feuille = function
    Feuille(n) -> n
  | _ -> failwith "contenu_feuille";;



  
type file = (int * arbre) list ;;



  
let rec insere frequence arbre = function
    ([]:file) -> ([frequence, arbre]:file)
  | (f,a)::reste as l -> if f >= frequence
  then (frequence, arbre)::l
  else
       (f,a)::(insere frequence arbre reste);;




	
exception File_singleton;;
exception File_vide;;


	
let extrait_2_min = function
    ([]:file) ->
      raise File_vide    
  |[p] ->
      raise File_singleton
  |p1::p2::reste ->
      (p1, p2, (reste:file));;



	
let tableau_frequence in_channel =
  let res = Array.make 256 0 in
  (try
    while true do
      let c_ascii = int_of_char (input_char in_channel)
      in res.(c_ascii) <- res.(c_ascii) + 1;
    done
  with
    End_of_file -> ());
  res;;
    

    
 
    
    
let creation_arbre tab =
  let file_priorite = ref([]) in
  for i=0 to 255 do
    if (tab.(i) <> 0)   
    then file_priorite := insere tab.(i) (Feuille i) !file_priorite; 
  done;
  let i=ref 0
  in
  try
    while true do
      let ((f1,a1),(f2,a2), reste) = extrait_2_min !file_priorite in
      file_priorite := insere (f1+f2) (Noeud {fg = a1; fd = a2}) reste;
    done;
    Feuille 0; (* pour lui faire plaisir *)
  with
    File_singleton -> 
      snd (List.hd !file_priorite);;
	




	
let tableau_codage arbre =
let res = Array.make 256 []
in match arbre with
  Feuille f ->
    res.(f) <- [0];
    res;
| a ->
    let rec aux temp = function
	Feuille (n) -> res.(n) <- List.rev temp
      | Noeud {fg = a1 ; fd = a2} ->
          (aux (0::temp) a1 ;
           aux (1::temp) a2)
    in aux [] a ;
    res;;



	
let binary_to_int = function
    n1::n2::n3::n4::n5::n6::n7::n8::[] -> n8+n7*2+n6*4+n5*8+n4*16+n3*32+n2*64+n1*128
  |_ -> failwith "binary_to_int";;



	
let int_to_binary n =
  if (n > 255 || n < 0)
  then failwith "int_to_binary"
  else
    let temp = ref([])
    and ref_n = ref(n)
    in for i=1 to 8 do
      temp := (!ref_n mod 2) :: !temp;
      ref_n := !ref_n/2;  
    done; 
    !temp;;




let rec codage_arbre = function
    Feuille n -> 0::(int_to_binary n)
  | Noeud {fg = a1 ; fd = a2} -> 1::(codage_arbre a1)@(codage_arbre a2);;


let remplit_de_input_arbre in_channel reste =
  let buffer = ref (List.rev reste)
  and c_ascii = ref [] in
  try
    for i = 1 to taille_buffer do
      c_ascii := int_to_binary (input_byte in_channel);
      buffer := (List.rev !c_ascii)@(!buffer);
    done;
    List.rev (!buffer);
  with
    End_of_file ->
      List.rev (!buffer);;


let rec decodage_arbre in_channel = function (* renvoie l'arbre et le reste de la liste *)
 (*   [] -> failwith "decodage_arbre"*)
  | 0::n1::n2::n3::n4::n5::n6::n7::n8::reste ->
      (Feuille (binary_to_int (n1::n2::n3::n4::n5::n6::n7::n8::[])), reste)
  | 1::reste ->
      let (a1, reste1) = decodage_arbre in_channel reste
      in let (a2, reste2) = decodage_arbre in_channel reste1
      in (Noeud {fg = a1; fd = a2}, reste2)
  | l ->
      let nv_l = remplit_de_input_arbre in_channel l in
      if (l = nv_l)
      then failwith "decodage_arbre"
      else decodage_arbre in_channel nv_l;;
	





let remplit_de_code in_channel reste tab =
  let buffer = ref (List.rev reste)
  and c_ascii = ref 0 in
  try
    for i = 1 to taille_buffer do
      c_ascii := int_of_char (input_char in_channel);
      buffer := (List.rev tab.(!c_ascii))@(!buffer);
    done;
      List.rev (!buffer);
  with
    End_of_file -> 
       List.rev (!buffer);;





let rec commence_ecrire out_channel = function
    n1::n2::n3::n4::n5::n6::n7::n8::reste ->
      (output_byte out_channel (binary_to_int (n1::n2::n3::n4::n5::n6::n7::n8::[]));
       commence_ecrire out_channel reste;)
  | l -> l;;





let k = ref 0;;

let rec ecrit_codage in_channel out_channel tab = function (* renvoie le nombre de bits de fin non valide *)
    n1::n2::n3::n4::n5::n6::n7::n8::reste ->
      (output_byte out_channel (binary_to_int (n1::n2::n3::n4::n5::n6::n7::n8::[]));
       ecrit_codage in_channel out_channel tab reste;)
  | l ->
      let nv_l = remplit_de_code in_channel l tab in
      if (l = nv_l)
      then
	(
	 match nv_l with
	   [] -> 0
	 |  dernier_l ->
	     (
	      let zero = ref []
	      and res = 8 - (List.length dernier_l)
	      in 
	      for i=1 to res do
		zero := 0 :: !zero
	      done;
	      output_byte out_channel (binary_to_int (dernier_l@(!zero)));
	      res);  
	)
      else ecrit_codage in_channel out_channel tab nv_l;;
	

	           
		



let codage_bit_supp n =
  let res_temp = ref []
  and n_temp = ref n in
  for i=1 to 3 do
    res_temp := (!n_temp mod 2) :: !res_temp;
    n_temp := !n_temp/2;
  done;
  (!res_temp);;





let decodage_bit_supp = function (*renvoie les bits à lire ds le dernier octet et le reste du buffer*)
    n1::n2::n3::reste -> (n3+n2*2+n1*4, reste)
  | _ -> failwith "decodage_bit_supp" ;;






let compresse nom_de_fichier nom_compresse = (* en entête se trouve le nombre de bits invalide *)
  let out_channel = open_out nom_compresse
  and in_channel = open_in nom_de_fichier
  (*Création de l'arbre...*)
  in
  let arbre =  (creation_arbre (tableau_frequence in_channel))
  (*Codage de l'arbre...*)
  in
  let tab = tableau_codage arbre
  in seek_in in_channel 0; 
  let buffer = ref (codage_arbre arbre)
  in buffer := 0::1::0::0::0::(!buffer);
  (*Ecriture dans le fichier du codage de l'arbre...*)
  buffer := commence_ecrire out_channel !buffer;
  (*Codage et écriture du texte dans fichier cible...*)
  buffer := remplit_de_code in_channel !buffer tab;  
  let nb_bits_invalides = ecrit_codage in_channel out_channel tab !buffer in
  (*Flush du tampon d'écriture...*)
  flush (out_channel);
  (*Codage des bits supplémentaires...*)
  let trois_bits = codage_bit_supp nb_bits_invalides in
  (*Lecture du premier octet sur le fichier cible...*)
  let in_channel_cible = open_in nom_compresse
  in  let premier_octet = int_to_binary (int_of_char (input_char in_channel_cible))
  in (*Réécriture du premier octet sur le fichier cible en le complétant par l'entête...*)
  seek_out out_channel 0;
  output_byte out_channel (binary_to_int (0::1::trois_bits@((List.tl(List.tl(List.tl (List.tl (List.tl premier_octet))))))));
  (*Fermeture des fichiers...*)
  close_out out_channel;
  close_in in_channel_cible;
  close_in in_channel;;
  (*Compression effectuée avec succès.*)
  
	
 

let remplit_de_input_corps in_channel nb_bits_invalides =
  let buffer = ref []
  and c_ascii = ref [] in
  try
    for i = 1 to taille_buffer do
      c_ascii := int_to_binary (input_byte in_channel);
      buffer := (List.rev !c_ascii)@(!buffer);
    done;
    let ne_sert_a_rien =  input_byte in_channel in
    seek_in in_channel ((pos_in in_channel) - 1);
    List.rev (!buffer);
  with
    End_of_file ->
      if (!buffer = [])
      then []
      else
	begin
	  let derniers_bits = enleve_premiers (huit_hd !buffer) (nb_bits_invalides)
	  in List.rev (derniers_bits@(huit_tl !buffer));
	end;;
      

let rec decode_texte in_channel out_channel arbre liste nb_bits_invalides = match (arbre,liste) with
  (Feuille f, []) ->
    let nv_l = remplit_de_input_corps in_channel nb_bits_invalides in
    if (nv_l <> [])
    then decode_texte in_channel out_channel (Feuille f) nv_l nb_bits_invalides;
| (Feuille f, 0::reste) ->
    output_char out_channel (char_of_int f);
    decode_texte in_channel out_channel (Feuille f) reste nb_bits_invalides
| (Feuille f, l) -> failwith "decode_texte"
| (arbre, liste) ->  
    let rec aux arbre_temp liste = match (arbre_temp, liste) with
      (Feuille n, l) ->
	(output_char out_channel (char_of_int n);
	 if (l != [])
	 then  aux arbre l
	 else
	   let nv_l = remplit_de_input_corps in_channel nb_bits_invalides in
	   if (nv_l <> [])
	   then aux arbre nv_l;	     
	)
    | (Noeud {fg = a1; fd = a2}, n::reste) ->
	if (n = 0)
	then aux a1 reste
	else aux a2 reste
    | (a, []) -> 
	let nv_l = remplit_de_input_corps in_channel nb_bits_invalides in
	if (nv_l <> [])
	then aux a nv_l
	else failwith "decode_texte"
    in aux arbre liste;;
      




let decompresse nom_de_fichier nom_decompresse =
  (*Ouverture des fichiers...*)
  let out_channel = open_out nom_decompresse
  and in_channel = open_in nom_de_fichier
  in (*Lecture du premier octet...*)
  let premier_octet = ref(int_to_binary (input_byte in_channel)) in
  let bit1 = List.hd !premier_octet in
  premier_octet := List.tl !premier_octet;
  let bit2 = List.hd !premier_octet in
  premier_octet := List.tl !premier_octet;
  if (bit1 <> 0 || bit2 <> 1)
  then failwith "Mauvais format de compression"
  else
    begin
      (*Décodage des 3 premiers bits...*)
      let (nb_bits_invalides, reste1) = decodage_bit_supp !premier_octet in
     (*Lecture et décodage de la partie du fichier source correspondant au codage de l'arbre...*)
      let reste1 = remplit_de_input_arbre in_channel reste1 in
      let (arbre, reste2) = decodage_arbre in_channel reste1 in
    (*Lecture et décodage du corps du fichier source...*)
      let buffer1 = remplit_de_input_corps in_channel nb_bits_invalides in
      let buffer2 = ref (reste2@buffer1) in
      if buffer1 = []
      then
	begin
	  let buffer3 = List.rev !buffer2 in
	  let derniers_bits = enleve_premiers (huit_hd buffer3) nb_bits_invalides
	  in buffer2 := List.rev (derniers_bits@(huit_tl buffer3));
	end; 
      decode_texte in_channel out_channel arbre !buffer2 nb_bits_invalides;
(*Fermeture des fichiers ouverts...*)
      close_out out_channel;
      close_in in_channel;
      (*Décompression effectuée avec succès.*)
    end;;




end;;


(*---------------------------METHODE 2----------------------------------*)


module Methode2 = struct


let rec print_buf = function
    [] -> print_string "liste_vide"; 
  | a::reste ->
      print_int (fst a);
      print_newline();
      print_buf reste;; 

let rec print_list = function
    [] -> print_newline ();
  | a::reste -> (print_int a;
		 print_string " ";
		print_list reste);;


let traitement tab = 
  print_string "Traitement :";
  print_newline ();
  for i = 0 to 255 do
    for j = 0 to 255 do
      if tab.(i).(j) >= 1
      then
        (
         print_char (char_of_int i);
         print_char (char_of_int j);
	 print_string " : ";
         print_int (tab.(i).(j));
         print_newline ();
        )
    done;
   done;;


let taille_buffer = 10;;
let j = ref 0;;



let rec enleve_premiers liste = function
  0 -> liste
| n -> enleve_premiers (List.tl liste) (n-1);;


let huit_hd = function
    n1::n2::n3::n4::n5::n6::n7::n8::reste ->  n1::n2::n3::n4::n5::n6::n7::n8::[]
  | _ -> failwith "huit_hd";;

let huit_tl = function
    n1::n2::n3::n4::n5::n6::n7::n8::reste ->  reste
  | _ -> failwith "huit_tl";;


type arbre =
    Feuille of int
  | Noeud of noeud
and noeud = { fg : arbre ;
	      fd : arbre };;




let suis_je_feuille = function
    Feuille (n) -> true
  | _ -> false;;




let contenu_feuille = function
    Feuille(n) -> n
  | _ -> failwith "contenu_feuille";;



type file = (int * arbre) list ;;


let suis_je_singleton = function
    [a] -> true
  | _ -> false;;


  
let rec insere frequence arbre = function
    ([]:file) -> ([frequence, arbre]:file)
  | (f,a)::reste as l -> if f >= frequence
  then (frequence, arbre)::l
  else
       (f,a)::(insere frequence arbre reste);;




	
exception File_singleton;;
exception File_vide;;


	
let extrait_2_min = function
    ([]:file) ->
      raise File_vide    
  |[p] ->
      raise File_singleton
  |p1::p2::reste ->
      (p1, p2, (reste:file));;

	
let tableau_frequence in_channel =
  let res = Array.make_matrix 256 256 0 in
  let c_ascii1 = ref 0
  and c_ascii2 = ref 0 in
  try
     c_ascii1 := int_of_char (input_char in_channel);
     while true do
       c_ascii2 := int_of_char (input_char in_channel);
       res.(!c_ascii1).(!c_ascii2) <- res.(!c_ascii1).(!c_ascii2) + 1;
       c_ascii1 := !c_ascii2;
     done;
     res;
  with
     End_of_file -> res;;


let creation_tableau_arbre tab =
  let res = Array.make 256 (Feuille (-1))
  and file_priorite = ref [] in
  for i = 0 to 255 do
    file_priorite := [];
    for j = 0 to 255 do
      if tab.(i).(j) <> 0
      then file_priorite := insere tab.(i).(j) (Feuille (j)) !file_priorite;
    done;
    if (suis_je_singleton (!file_priorite))
    then res.(i) <- snd (List.hd !file_priorite)
    else
      if (!file_priorite != [])
      then
	try
	  while true do
	    let ((f1,a1),(f2,a2), reste) = extrait_2_min !file_priorite in
	    file_priorite := insere (f1+f2) (Noeud {fg = a1; fd = a2}) reste;
	  done;
	with
	  File_singleton -> 
	    res.(i) <- snd (List.hd !file_priorite);
  done;
  res;;
    

let tableau_codage tableau_arbre =
  let res = Array.make_matrix 256 256 [] in
  let rec aux temp i = function
      Feuille n -> res.(i).(n) <- (List.rev temp);
    | Noeud {fg = a1 ; fd = a2} ->
	(aux (0::temp) i a1 ;
	 aux (1::temp) i a2)
  in for j = 0 to 255 do
    match tableau_arbre.(j) with
      Feuille (-1) -> ()
    | Feuille (f) ->  res.(j).(f) <- [0];
    | a -> aux [] j a;
  done;
  res;;


let binary_to_int = function
    n1::n2::n3::n4::n5::n6::n7::n8::[] -> n8+n7*2+n6*4+n5*8+n4*16+n3*32+n2*64+n1*128
  |_ -> failwith "binary_to_int";;




let int_to_binary n =
  if (n > 255 || n < 0)
  then failwith "int_to_binary"
  else
    let temp = ref([])
    and ref_n = ref(n)
    in for i=1 to 8 do
      temp := (!ref_n mod 2) :: !temp;
      ref_n := !ref_n/2;  
    done; 
    !temp;;



let rec codage_arbre = function
    Feuille n ->  0::(int_to_binary n)
  | Noeud {fg = a1 ; fd = a2} -> 1::(codage_arbre a1)@(codage_arbre a2);;


let codage_tableau_arbre tab plus31 =
  if plus31
  then
    begin
      let res = ref [1] in
      for i = 0 to 255 do
	if tab.(i) = Feuille (-1)
	then
	  res := 0::(!res)
	else
	  res := (List.rev (codage_arbre tab.(i)))@(1::(!res));
      done;
      List.rev !res;
    end
  else
    begin
      let res = ref [0]
      and nb_char = ref 0 in
      for i = 0 to 255 do
	if tab.(i) <> Feuille (-1)
	then nb_char := !nb_char + 1;
      done;
      res := (List.rev (int_to_binary !nb_char))@(!res);
      for i = 0 to 255 do
	if tab.(i) <> Feuille (-1)
	then res := (List.rev (codage_arbre tab.(i)))@(List.rev (int_to_binary i))@(!res);
      done;
      List.rev !res;
    end;;
	
      
let remplit_de_input_arbre in_channel reste =
  let buffer = ref (List.rev reste)
  and c_ascii = ref [] in
  try
    for i = 1 to taille_buffer do
      c_ascii := int_to_binary (input_byte in_channel);
      buffer := (List.rev !c_ascii)@(!buffer);
    done;
    List.rev (!buffer);
  with
    End_of_file ->
      List.rev (!buffer);;



let rec decodage_arbre in_channel = function (* renvoie l'arbre et le reste de la liste *)
    0::n1::n2::n3::n4::n5::n6::n7::n8::reste ->
      (Feuille (binary_to_int (n1::n2::n3::n4::n5::n6::n7::n8::[])), reste)
  | 1::reste ->
      let (a1, reste1) = decodage_arbre in_channel reste
      in let (a2, reste2) = decodage_arbre in_channel reste1
      in (Noeud {fg = a1; fd = a2}, reste2)
  | l ->
      let nv_l = remplit_de_input_arbre in_channel l in
      if (l = nv_l)
      then failwith "decodage_arbre"
      else decodage_arbre in_channel nv_l;;



let decodage_tableau_arbre in_channel reste1 =
  let res = Array.make 256 (Feuille (-1))
  and paire = ref (Feuille 0, [])
  and reste = ref reste1
  in
  if !reste = []
  then reste := remplit_de_input_arbre in_channel [];
  let plus31 = List.hd !reste in
  reste := List.tl !reste;
  if (plus31 = 1)
  then
    begin
      for i = 0 to 255 do
	if !reste = []
	then reste := remplit_de_input_arbre in_channel [];
	if List.hd !reste = 0
	then reste := List.tl !reste
	else
	  begin
	    paire := decodage_arbre in_channel (List.tl !reste);
	    res.(i) <- fst !paire;
	    reste := snd !paire;
	  end
      done;
      (res, !reste);
    end
  else
    begin
      if (List.length !reste) < 8
      then reste := remplit_de_input_arbre in_channel !reste;
      let nb_char = binary_to_int (huit_hd !reste)
      and c_ascii = ref 0 
      in reste := huit_tl !reste;
      for i = 1 to nb_char do
	if (List.length !reste) < 8
	then reste := remplit_de_input_arbre in_channel !reste;
	c_ascii := binary_to_int (huit_hd !reste);
	reste := huit_tl !reste;
	paire := decodage_arbre in_channel (!reste);
	res.(!c_ascii) <- fst !paire;
	reste := snd !paire;
      done;
      (res, !reste);
    end;;



let rec commence_ecrire out_channel = function
    n1::n2::n3::n4::n5::n6::n7::n8::reste ->
      (output_byte out_channel (binary_to_int (n1::n2::n3::n4::n5::n6::n7::n8::[]));
       commence_ecrire out_channel reste;)
  | l -> l;;





let remplit_de_code in_channel reste tab c_ascii = (* renvoie le buffer et le dernier caractère de ce buffer *)
  let buffer = ref (List.rev reste)
  and c_ascii1 = ref c_ascii
  and c_ascii2 = ref 0 in
  try
    for i = 1 to taille_buffer do
      c_ascii2 := input_byte in_channel;
      buffer := (List.rev tab.(!c_ascii1).(!c_ascii2))@(!buffer);
      c_ascii1 := !c_ascii2;
    done;
    (List.rev (!buffer), !c_ascii2);
  with
    End_of_file -> 
       (List.rev (!buffer), !c_ascii1) ;;


let rec ecrit_codage in_channel out_channel tab c_ascii = function (* renvoie le nombre de bits de fin non valide *)
    n1::n2::n3::n4::n5::n6::n7::n8::reste ->
      (output_byte out_channel (binary_to_int (n1::n2::n3::n4::n5::n6::n7::n8::[]));
       ecrit_codage in_channel out_channel tab c_ascii reste;)
  | l ->
      let paire = remplit_de_code in_channel l tab c_ascii
      in let nv_l = fst paire
      and nv_c_ascii = snd paire
      in
      if (l = nv_l)
      then
	(
	 match nv_l with
	   [] -> 0
	 |  dernier_l ->
	     (
	      let zero = ref []
	      and res = 8 - (List.length dernier_l)
	      in 
	      for i=1 to res do
		zero := 0 :: !zero
	      done;
	      output_byte out_channel (binary_to_int (dernier_l@(!zero)));
	      res);  
	)
      else ecrit_codage in_channel out_channel tab nv_c_ascii nv_l;;



let codage_bit_supp n =
  let res_temp = ref []
  and n_temp = ref n in
  for i=1 to 3 do
    res_temp := (!n_temp mod 2) :: !res_temp;
    n_temp := !n_temp/2;
  done;
  (!res_temp);;





let decodage_bit_supp = function (*renvoie les bits à lire ds le dernier octet et le reste du buffer*)
    n1::n2::n3::reste -> (n3+n2*2+n1*4, reste)
  | _ -> failwith "decodage_bit_supp" ;;







let compresse nom_de_fichier nom_compresse = (* en entête se trouve le nombre de bits invalide *)

  let out_channel = open_out nom_compresse
  and in_channel = open_in nom_de_fichier
  in (*Création du tableau d'arbres...*)
  let tab_arbre =  (creation_tableau_arbre (tableau_frequence in_channel))
  in let nb_char = ref 0
  in for i = 0 to 255 do
    if tab_arbre.(i) <> Feuille (-1)
    then nb_char := !nb_char + 1;
  done;
  let plus31 = (!nb_char >= 31)
  in
(*Création du dictionnaire...*)
  let tab = tableau_codage tab_arbre  
  (*Codage de l'arbre...*) in
  let buffer = ref (codage_tableau_arbre tab_arbre plus31)
  in buffer := 1::0::0::0::0::(!buffer);
(*Ecriture dans le fichier du codage de l'arbre*)
  buffer := commence_ecrire out_channel !buffer;
  (*Lecture puis écriture du premier caractère*)
  seek_in in_channel 0;
  let c_ascii = input_byte in_channel
  in buffer := !buffer@(int_to_binary c_ascii);
  (*Codage et écriture du texte dans fichier cible*)
  let paire = remplit_de_code in_channel !buffer tab c_ascii in
  buffer := fst paire;
  let nv_c_ascii = snd paire in
  let nb_bits_invalides = ecrit_codage in_channel out_channel tab nv_c_ascii !buffer in
  (*Flush du tampon d'écriture*)
  flush out_channel;
  (*Codage des bits supplémentaires*)
  let trois_bits = codage_bit_supp nb_bits_invalides in
(*Lecture du premier octet sur le fichier cible*)
  let in_channel_cible = open_in nom_compresse
  in  let premier_octet = int_to_binary (int_of_char (input_char in_channel_cible))
  in (*Réécriture du premier octet sur le fichier cible en le complétant par l'entête*)
  seek_out out_channel 0;
  output_byte out_channel (binary_to_int (1::0::trois_bits@(List.tl(List.tl(List.tl(List.tl (List.tl premier_octet)))))));
 (*Fermeture des fichiers*)
  close_out out_channel;
  close_in in_channel_cible;
  close_in in_channel;;




let remplit_de_input_corps in_channel nb_bits_invalides =
  let buffer = ref []
  and c_ascii = ref [] in
  try
    for i = 1 to taille_buffer do
      c_ascii := int_to_binary (input_byte in_channel);
      buffer := (List.rev !c_ascii)@(!buffer);
    done;
    let ne_sert_a_rien =  input_byte in_channel in
    seek_in in_channel ((pos_in in_channel) - 1);
    List.rev (!buffer);
  with
    End_of_file ->
     
      if (!buffer = [])
      then []
      else
	begin
	  let derniers_bits = enleve_premiers (huit_hd !buffer) nb_bits_invalides
	  in List.rev (derniers_bits@(huit_tl !buffer));
	end;;
      



let rec decode_texte in_channel out_channel tab_arbre liste nb_bits_invalides i =
  match (tab_arbre.(i), liste) with
    (Feuille f, []) ->
      let nv_l = remplit_de_input_corps in_channel nb_bits_invalides in
      if (nv_l <> [])
      then decode_texte in_channel out_channel tab_arbre nv_l nb_bits_invalides f;
  | (Feuille f, 0::reste) ->
      output_char out_channel (char_of_int f);
      decode_texte in_channel out_channel tab_arbre reste nb_bits_invalides f;
  | (Feuille f, l) -> failwith "decode_texte : feuille"
  | (arbre, liste) ->
      let rec aux arbre_temp liste = match (arbre_temp, liste) with
	(Feuille n, l) ->
	  (
	   output_char out_channel (char_of_int n);
	   if (l != [])
	   then decode_texte in_channel out_channel tab_arbre l nb_bits_invalides n
	   else
	     let nv_l = remplit_de_input_corps in_channel nb_bits_invalides in
	     if (nv_l <> [])
	     then decode_texte in_channel out_channel tab_arbre nv_l nb_bits_invalides n;
	  )
      | (Noeud {fg = a1; fd = a2}, n::reste) ->
	  if (n = 0)
	  then aux a1 reste
	  else aux a2 reste
      | (a, []) -> 
	  let nv_l = remplit_de_input_corps in_channel nb_bits_invalides in
	  if (nv_l <> [])
	  then aux a nv_l
	  else failwith "decode_texte : arbre"
      in aux arbre liste;;
	
	
	
let decompresse nom_de_fichier nom_decompresse =
  (*Ouverture des fichiers...*)
  let out_channel = open_out nom_decompresse
  and in_channel = open_in nom_de_fichier
(*Lecture du premier octet...*)
  in let premier_octet = ref (int_to_binary (input_byte in_channel)) in
  (*Décodage des 3 premiers bits...*)
  let bit1 = List.hd !premier_octet in
  premier_octet := List.tl !premier_octet;
  let bit2 = List.hd !premier_octet in
  premier_octet := List.tl !premier_octet;
  if (bit1 <> 1 || bit2 <>0)
  then failwith "Mauvaise version de compression"
  else
    begin
      let (nb_bits_invalides, reste1) = decodage_bit_supp !premier_octet in
      (*Lecture et décodage de la partie du fichier source correspondant au codage de l'arbre...*)
      let reste1 = remplit_de_input_arbre in_channel reste1 in
      let (tab_arbre, reste2) = decodage_tableau_arbre in_channel reste1
     in (*Lecture et décodage du corps du fichier source...*)
      
      let buffer1 = remplit_de_input_corps in_channel nb_bits_invalides in
      let buffer2 = ref (reste2@buffer1) in
      if buffer1 = []
      then
	begin
	  let buffer3 = List.rev !buffer2 in
	  let derniers_bits = enleve_premiers (huit_hd buffer3) nb_bits_invalides
	  in buffer2 := List.rev (derniers_bits@(huit_tl buffer3));
	end;
      let c_ascii = binary_to_int (huit_hd !buffer2) in
      output_byte out_channel c_ascii;
      decode_texte in_channel out_channel tab_arbre (huit_tl !buffer2) nb_bits_invalides c_ascii;
   (*Fermeture des fichiers ouverts*)
      close_out out_channel;
      close_in in_channel;
    end;;




end;;




(*---------------------------METHODE 3----------------------------------*)


module Methode3 = struct


let rec print_buf = function
    [] -> print_string "liste_vide"; 
  | a::reste ->
      print_int (fst a);
      print_newline();
      print_buf reste;; 

let rec print_list = function
    [] -> print_newline ();
  | a::reste -> (print_int a;
		 print_string " ";
		print_list reste);;


let traitement tab = 
  print_string "Traitement :";
  print_newline ();
  for i = 0 to 255 do
    for j = 0 to 255 do
      if tab.(i).(j) >= 1
      then
        (
         print_char (char_of_int i);
         print_char (char_of_int j);
	 print_string " : ";
         print_int (tab.(i).(j));
         print_newline ();
        )
    done;
   done;;


let taille_buffer = 20;;
let j = ref 0;;



let rec enleve_premiers liste = function
  0 -> liste
| n -> enleve_premiers (List.tl liste) (n-1);;


let huit_hd = function
    n1::n2::n3::n4::n5::n6::n7::n8::reste ->  n1::n2::n3::n4::n5::n6::n7::n8::[]
  | _ -> failwith "huit_hd";;

let huit_tl = function
    n1::n2::n3::n4::n5::n6::n7::n8::reste ->  reste
  | _ -> failwith "huit_tl";;

let seize_hd = function
    n1::n2::n3::n4::n5::n6::n7::n8::n9::n10::n11::n12::n13::n14::n15::n16::reste ->  n1::n2::n3::n4::n5::n6::n7::n8::n9::n10::n11::n12::n13::n14::n15::n16::[]
  | _ -> failwith "seize_hd";;

let seize_tl = function
    n1::n2::n3::n4::n5::n6::n7::n8::n9::n10::n11::n12::n13::n14::n15::n16::reste ->  reste
  | _ -> failwith "seize_tl";;



type arbre =
    Feuille of int
  | Noeud of noeud
and noeud = { fg : arbre ;
	      fd : arbre };;




let suis_je_feuille = function
    Feuille (n) -> true
  | _ -> false;;




let contenu_feuille = function
    Feuille(n) -> n
  | _ -> failwith "contenu_feuille";;



type file = (int * arbre) list ;;


let suis_je_singleton = function
    [a] -> true
  | _ -> false;;


  
let rec insere frequence arbre = function
    ([]:file) -> ([frequence, arbre]:file)
  | (f,a)::reste as l -> if f >= frequence
  then (frequence, arbre)::l
  else
       (f,a)::(insere frequence arbre reste);;



exception Pas_trouve

let rec incremente num = function
    [] -> raise Pas_trouve
  | (num1, occ)::reste ->
      if num1=num
      then (num1, occ+1)::reste
      else (num1, occ)::(incremente num reste);;

let cree_a_1 num liste_paires = (num, 1)::liste_paires;; 

let incremente_ou_cree num liste_paires =
  try
    incremente num liste_paires;
  with
    Pas_trouve -> cree_a_1 num liste_paires;;


let rec trouve_code c_ascii = function
    [] -> failwith "trouve_code"
  | (c, code)::reste ->
      if c = c_ascii
      then code
      else trouve_code c_ascii reste;;
	

exception File_singleton;;
exception File_vide;;


	
let extrait_2_min = function
    ([]:file) ->
      raise File_vide    
  |[p] ->
      raise File_singleton
  |p1::p2::reste ->
      (p1, p2, (reste:file));;

	
let tableau_frequence in_channel =
  let res = Array.make_matrix 256 256 [] in
  let c_ascii1 = ref 0
  and c_ascii2 = ref 0
  and c_ascii3 = ref 0 in
  try
     c_ascii1 := int_of_char (input_char in_channel);
     c_ascii2 := int_of_char (input_char in_channel);
     while true do
       c_ascii3 := int_of_char (input_char in_channel);
       res.(!c_ascii1).(!c_ascii2) <- incremente_ou_cree (!c_ascii3) (res.(!c_ascii1).(!c_ascii2));
       c_ascii1 := !c_ascii2;
       c_ascii2 := !c_ascii3;
     done;
     res;
  with
     End_of_file -> res;;


let creation_tableau_arbre tab =
  let res = Array.make_matrix 256 256 (Feuille (-1))
  and file_priorite = ref []
  and temp = ref []
  and paire = ref (0,0) in
  for i = 0 to 255 do
    for j = 0 to 255 do
      file_priorite := [];
      temp := tab.(i).(j);
      while (!temp <> []) do
        paire := List.hd !temp;
	temp := List.tl !temp;
	file_priorite := insere (snd !paire) (Feuille (fst !paire)) !file_priorite;
      done;
      if (suis_je_singleton (!file_priorite))
      then res.(i).(j) <- snd (List.hd !file_priorite)
      else
	if (!file_priorite != [])
	then
	  try
	  while true do
	    let ((f1,a1),(f2,a2), reste) = extrait_2_min !file_priorite in
	    file_priorite := insere (f1+f2) (Noeud {fg = a1; fd = a2}) reste;
	  done;
	  with
	    File_singleton -> 
	      res.(i).(j) <- snd (List.hd !file_priorite);
    done;
  done;
  res;;
      

let tableau_codage tableau_arbre =
  let res = Array.make_matrix 256 256 [] in
  let rec aux temp i j = function
      Feuille n -> (res.(i).(j) <- (n, List.rev temp)::res.(i).(j))
    | Noeud {fg = a1 ; fd = a2} ->
	(aux (0::temp) i j a1 ;
	 aux (1::temp) i j a2)
  in
  for i = 0 to 255 do
    for j = 0 to 255 do
      match tableau_arbre.(i).(j) with
	Feuille (-1) -> ()
      | Feuille (f) -> (res.(i).(j) <- (f,[0])::res.(i).(j))
      | a -> aux [] i j a;
    done;
  done;
  res;;


let binary_to_int8 = function
    n1::n2::n3::n4::n5::n6::n7::n8::[] -> n8+n7*2+n6*4+n5*8+n4*16+n3*32+n2*64+n1*128
  |_ -> failwith "binary_to_int8";;


let int_to_binary8 n =
  if (n > 255 || n < 0)
  then failwith "int_to_binary8"
  else
    let temp = ref([])
    and ref_n = ref(n)
    in for i=1 to 8 do
      temp := (!ref_n mod 2) :: !temp;
      ref_n := !ref_n/2;  
    done; 
    !temp;;


let binary_to_int16 = function
     n1::n2::n3::n4::n5::n6::n7::n8::n9::n10::n11::n12::n13::n14::n15::n16::[] -> n16+n15*2+n14*4+n13*8+n12*16+n11*32+n10*64+n9*128+n8*256+n7*512+n6*1024+n5*2048+n4*4096+n3*8192+n2*16384+n1*32768
  |_ -> failwith "binary_to_int16";;



let int_to_binary16 n =
  if (n > 65535 || n < 0)
  then failwith "int_to_binary16"
  else
    let temp = ref([])
    and ref_n = ref(n)
    in for i=1 to 16 do
      temp := (!ref_n mod 2) :: !temp;
      ref_n := !ref_n/2;  
    done; 
    !temp;;


let rec codage_arbre = function
    Feuille n ->  0::(int_to_binary8 n)
  | Noeud {fg = a1 ; fd = a2} -> 1::(codage_arbre a1)@(codage_arbre a2);;


let codage_tableau_arbre tab plus4095 =
  if plus4095
  then
    begin
      let res = ref [1] in
      for i = 0 to 255 do
	for j = 0 to 255 do
	  if tab.(i).(j) = Feuille (-1)
	  then
	    res := 0::(!res)
	  else
	    res := (List.rev (codage_arbre tab.(i).(j)))@(1::(!res));
	done;
      done;
      List.rev !res;
    end
  else
    begin
      let res = ref [0]
      and nb_arbres = ref 0 in
      for i = 0 to 255 do
	for j = 0 to 255 do
	  if tab.(i).(j) <> Feuille (-1)
	  then nb_arbres := !nb_arbres + 1;
	done;
      done ;
      res := (List.rev (int_to_binary16 !nb_arbres))@(!res);
      for i = 0 to 255 do
	for j = 0 to 255 do
	  if tab.(i).(j) <> Feuille (-1)
	  then res :=  (List.rev (codage_arbre tab.(i).(j)))@(List.rev (int_to_binary8 j))@(List.rev (int_to_binary8 i))@(!res);
	done;
      done;
      List.rev !res;
    end;;
  
      
    
let remplit_de_input_arbre in_channel reste =
  let buffer = ref (List.rev reste)
  and c_ascii = ref [] in
  try
    for i = 1 to taille_buffer do
      c_ascii := int_to_binary8 (input_byte in_channel);
      buffer := (List.rev !c_ascii)@(!buffer);
    done;
    List.rev (!buffer);
  with
    End_of_file ->
      List.rev (!buffer);;



let rec decodage_arbre in_channel = function (* renvoie l'arbre et le reste de la liste *)
  | 0::n1::n2::n3::n4::n5::n6::n7::n8::reste ->
      (Feuille (binary_to_int8 (n1::n2::n3::n4::n5::n6::n7::n8::[])), reste)
  | 1::reste ->
      let (a1, reste1) = decodage_arbre in_channel reste
      in let (a2, reste2) = decodage_arbre in_channel reste1
      in (Noeud {fg = a1; fd = a2}, reste2)
  | l ->
      let nv_l = remplit_de_input_arbre in_channel l in
      if (l = nv_l)
      then failwith "decodage_arbre"
      else decodage_arbre in_channel nv_l;;


let decodage_tableau_arbre in_channel reste1 =
  let res = Array.make_matrix 256 256 (Feuille (-1))
  and paire = ref (Feuille 0, [])
  and reste = ref reste1
  in
  if !reste = []
  then reste := remplit_de_input_arbre in_channel [];
  let plus4095 = List.hd !reste in
  reste := List.tl !reste;
  if (plus4095 = 1)
  then
    begin
      for i = 0 to 255 do
	for j = 0 to 255 do
	  if !reste = []
	  then reste := remplit_de_input_arbre in_channel [];
	  if List.hd !reste = 0
	  then reste := List.tl !reste
	  else
	    begin
	      paire := decodage_arbre in_channel (List.tl !reste);
	      res.(i).(j) <- fst !paire;
	      reste := snd !paire;
	    end
	done;
      done;
      (res, !reste);
    end
  else
    begin
      if (List.length !reste) < 16
      then reste := remplit_de_input_arbre in_channel !reste;
      let nb_arbres = binary_to_int16 (seize_hd !reste)
      and c_ascii1 = ref 0
      and c_ascii2 = ref 0
      in reste := seize_tl !reste;
      for i = 1 to nb_arbres do
	if (List.length !reste) < 16
	then reste := remplit_de_input_arbre in_channel !reste;
	c_ascii1 := binary_to_int8 (huit_hd !reste);
	reste := huit_tl !reste;
	c_ascii2 := binary_to_int8 (huit_hd !reste);
	reste := huit_tl !reste;
	paire := decodage_arbre in_channel (!reste);
	res.(!c_ascii1).(!c_ascii2) <- fst !paire;
	reste := snd !paire;
      done;
      (res, !reste);
    end;;
    

let rec commence_ecrire out_channel = function
    n1::n2::n3::n4::n5::n6::n7::n8::reste ->
      (output_byte out_channel (binary_to_int8 (n1::n2::n3::n4::n5::n6::n7::n8::[]));
       commence_ecrire out_channel reste;)
  | l -> l;;





let remplit_de_code in_channel reste tab c_asciilu1 c_asciilu2 = (* renvoie le buffer et les 2 derniers caractères de ce buffer *)
  let buffer = ref (List.rev reste)
  and c_ascii1 = ref c_asciilu1
  and c_ascii2 = ref c_asciilu2
  and c_ascii3 = ref 0 in
  try
    for i = 1 to taille_buffer do
      c_ascii3 := input_byte in_channel;
      buffer := (List.rev (trouve_code !c_ascii3 tab.(!c_ascii1).(!c_ascii2)))@(!buffer);
      c_ascii1 := !c_ascii2;
      c_ascii2 := !c_ascii3;
    done;
    (List.rev (!buffer), (!c_ascii1, !c_ascii2));
  with
    End_of_file -> 
       (List.rev (!buffer), (!c_ascii1, !c_ascii2)) ;;


let rec ecrit_codage in_channel out_channel tab c_asciilu1 c_asciilu2 = function (* renvoie le nombre de bits de fin non valide *)
    n1::n2::n3::n4::n5::n6::n7::n8::reste ->
      (output_byte out_channel (binary_to_int8 (n1::n2::n3::n4::n5::n6::n7::n8::[]));
       ecrit_codage in_channel out_channel tab c_asciilu1 c_asciilu2 reste;)
  | l ->
      let paire = remplit_de_code in_channel l tab c_asciilu1 c_asciilu2
      in let nv_l = fst paire
      and nv_paire_ascii = snd paire
      in
      if (l = nv_l)
      then
	(
	 match nv_l with
	   [] -> 0
	 |  dernier_l ->
	     (
	      let zero = ref []
	      and res = 8 - (List.length dernier_l)
	      in 
	      for i=1 to res do
		zero := 0 :: !zero
	      done;
	      output_byte out_channel (binary_to_int8 (dernier_l@(!zero)));
	      res);  
	)
      else ecrit_codage in_channel out_channel tab (fst nv_paire_ascii) (snd nv_paire_ascii) nv_l;;



let codage_bit_supp n =
  let res_temp = ref []
  and n_temp = ref n in
  for i=1 to 3 do
    res_temp := (!n_temp mod 2) :: !res_temp;
    n_temp := !n_temp/2;
  done;
  (!res_temp);;





let decodage_bit_supp = function (*renvoie les bits à lire ds le dernier octet et le reste du buffer*)
    n1::n2::n3::reste -> (n3+n2*2+n1*4, reste)
  | _ -> failwith "decodage_bit_supp" ;;







let compresse nom_de_fichier nom_compresse= (* en entête se trouve le nombre de bits invalide *)

  let out_channel = open_out nom_compresse
  and in_channel = open_in nom_de_fichier
  in (*Création du tableau d'arbres...*)
  let tab_arbre =  (creation_tableau_arbre (tableau_frequence in_channel))
  in let nb_arbre = ref 0
  in for i = 0 to 255 do
    for j = 0 to 255 do
      if tab_arbre.(i).(j) <> Feuille (-1)
      then nb_arbre := !nb_arbre + 1;
    done;
  done;
  let plus4095 = (!nb_arbre >= 4095)
  in (*Création du dictionnaire...*)
  let tab = tableau_codage tab_arbre  
  in (*Codage de l'arbre...*)
  let buffer = ref (codage_tableau_arbre tab_arbre plus4095)
  in buffer := 1::1::0::0::0::(!buffer);
 (*Ecriture dans le fichier du codage de l'arbre*)
  buffer := commence_ecrire out_channel !buffer;
  (*Lecture puis écriture du premier caractère*)
  seek_in in_channel 0;
  let c_ascii1 = input_byte in_channel
  in buffer := !buffer@(int_to_binary8 c_ascii1);
  let c_ascii2 = input_byte in_channel
  in buffer := !buffer@(int_to_binary8 c_ascii2);
  (*Codage et écriture du texte dans fichier cible*)
  let paire = remplit_de_code in_channel !buffer tab c_ascii1 c_ascii2 in
  buffer := fst paire;
  let nv_c_ascii_paire = snd paire in
  let nb_bits_invalides = ecrit_codage in_channel out_channel tab (fst nv_c_ascii_paire) (snd nv_c_ascii_paire) !buffer in
  (*Flush du tampon d'écriture*)
  flush out_channel;
  (*Codage des bits supplémentaires*)
  let trois_bits = codage_bit_supp nb_bits_invalides in
(*Lecture du premier octet sur le fichier cible*)
    let in_channel_cible = open_in nom_compresse
  in  let premier_octet = int_to_binary8 (int_of_char (input_char in_channel_cible))
  in (*Réécriture du premier octet sur le fichier cible en le complétant par l'entête*)
  seek_out out_channel 0;
  output_byte out_channel (binary_to_int8 (1::1::trois_bits@(List.tl(List.tl(List.tl (List.tl (List.tl premier_octet)))))));
  (*Fermeture des fichiers*)
  close_out out_channel;
  close_in in_channel_cible;
  close_in in_channel;;




let remplit_de_input_corps in_channel nb_bits_invalides =
  let buffer = ref []
  and c_ascii = ref [] in
  try
    for i = 1 to taille_buffer do
      c_ascii := int_to_binary8 (input_byte in_channel);
      buffer := (List.rev !c_ascii)@(!buffer);
    done;
    let ne_sert_a_rien =  input_byte in_channel in
    seek_in in_channel ((pos_in in_channel) - 1);
    List.rev (!buffer);
  with
    End_of_file ->
     
      if (!buffer = [])
      then []
      else
	begin
	  let derniers_bits = enleve_premiers (huit_hd !buffer) nb_bits_invalides
	  in List.rev (derniers_bits@(huit_tl !buffer));
	end;;
      



let rec decode_texte in_channel out_channel tab_arbre liste nb_bits_invalides i j =
  match (tab_arbre.(i).(j), liste) with
    (Feuille f, []) ->
      let nv_l = remplit_de_input_corps in_channel nb_bits_invalides in
      if (nv_l <> [])
      then decode_texte in_channel out_channel tab_arbre nv_l nb_bits_invalides j f;
  | (Feuille f, 0::reste) ->
      output_char out_channel (char_of_int f);
      decode_texte in_channel out_channel tab_arbre reste nb_bits_invalides j f;
  | (Feuille f, l) -> failwith "decode_texte"
  | (arbre, liste) ->
      let rec aux arbre_temp liste = match (arbre_temp, liste) with
	(Feuille n, l) ->
	  (
	   output_char out_channel (char_of_int n);
	   if (l != [])
	   then decode_texte in_channel out_channel tab_arbre l nb_bits_invalides j n
	   else
	     let nv_l = remplit_de_input_corps in_channel nb_bits_invalides in
	     if (nv_l <> [])
	     then decode_texte in_channel out_channel tab_arbre nv_l nb_bits_invalides j n;
	  )
      | (Noeud {fg = a1; fd = a2}, n::reste) ->
	  if (n = 0)
	  then aux a1 reste
	  else aux a2 reste
      | (a, []) -> 
	  let nv_l = remplit_de_input_corps in_channel nb_bits_invalides in
	  if (nv_l <> [])
	  then aux a nv_l
	  else failwith "decode_texte"
      in aux arbre liste;;
	
	
	
let decompresse nom_de_fichier nom_decompresse=
  (*Ouverture des fichiers...*)
  let out_channel = open_out nom_decompresse
  and in_channel = open_in nom_de_fichier
  in (*Lecture du premier octet...*)
  let premier_octet = ref (int_to_binary8 (input_byte in_channel)) in
  (*Décodage des 3 premiers bits...*)
  let bit1 = List.hd !premier_octet in
  premier_octet := List.tl !premier_octet;
  let bit2 = List.hd !premier_octet in
  premier_octet := List.tl !premier_octet;
  if (bit1 <> 1 || bit2 <> 1)
  then failwith "Mauvaise version de compression"
  else
    begin 
      let (nb_bits_invalides, reste1) = decodage_bit_supp !premier_octet in
      (*Lecture et décodage de la partie du fichier source correspondant au codage de l'arbre...*)
      let reste1 = remplit_de_input_arbre in_channel reste1 in
      let (tab_arbre, reste2) = decodage_tableau_arbre in_channel reste1
      in (*Lecture et décodage du corps du fichier source...*)
      let buffer1 = remplit_de_input_corps in_channel nb_bits_invalides in
      let buffer2 = ref (reste2@buffer1) in
      if buffer1 = []
      then
	begin
	  let buffer3 = List.rev !buffer2 in
	  let derniers_bits = enleve_premiers (huit_hd buffer3) nb_bits_invalides
	  in buffer2 := List.rev (derniers_bits@(huit_tl buffer3));
    end;
      let c_ascii1 = binary_to_int8 (huit_hd !buffer2) in
      buffer2 := huit_tl !buffer2;
      let c_ascii2 = binary_to_int8 (huit_hd !buffer2) in
      output_byte out_channel c_ascii1;
      output_byte out_channel c_ascii2;
      decode_texte in_channel out_channel tab_arbre (huit_tl !buffer2) nb_bits_invalides c_ascii1 c_ascii2;
      (*Fermeture des fichiers ouverts*)
      close_out out_channel;
      close_in in_channel;
    end;;


end;;






(*-----------------------EXECUTABLE : COMPRESSION---------------------------*)








let _ =
  let argv = Sys.argv in
  if ((Array.length argv) <> 2)
  then failwith "Nombre d'arguments incorrect"
  else let nom_du_fichier = argv.(1) in
  let nom_compresse = nom_du_fichier^"_zip" in
  let in_channel = open_in nom_du_fichier in
  let taille = in_channel_length in_channel in
  if taille < 10
  then
    begin
      print_string "Pourquoi compresser un fichier de si petite taille ?";
      print_newline ();
    end
  else
    begin
      Methode1.compresse nom_du_fichier (nom_compresse^"1");
      let in_channel_compresse1 = open_in (nom_compresse^"1") in
      let taille_compresse1 = in_channel_length in_channel_compresse1
      in
      if taille_compresse1 >  taille
      then
	begin
	  print_string "La méthode 0 est préférable. Le nom du fichier compressé est : ";
	  print_string (nom_compresse^"0");
	  print_newline ();
	  close_in in_channel_compresse1;
	  close_in in_channel;
	  Sys.remove (nom_compresse^"1");
	  Methode0.compresse nom_du_fichier (nom_compresse^"0");
	end
      else
	begin
	  Methode2.compresse nom_du_fichier (nom_compresse^"2");
	  let in_channel_compresse2 = open_in (nom_compresse^"2") in
	  let taille_compresse2 = in_channel_length in_channel_compresse2
	  in
	  if taille_compresse2 >  taille_compresse1
	  then
	    begin
	      print_string "La méthode 1 est préférable. Le nom du fichier compressé est : ";
	      print_string (nom_compresse^"1");
	      print_newline ();
	      close_in in_channel_compresse2;
	      close_in in_channel_compresse1;
	      close_in in_channel;
	      Sys.remove (nom_compresse^"2");
	    end
	  else
	    begin
	      Sys.remove (nom_compresse^"1");
	      Methode3.compresse nom_du_fichier (nom_compresse^"3");
	      let in_channel_compresse3 = open_in (nom_compresse^"3") in
	      let taille_compresse3 = in_channel_length in_channel_compresse3
	      in
	      if taille_compresse3 >  taille_compresse2
	      then
		begin
		  print_string "La méthode 2 est préférable. Le nom du fichier compressé est : ";
		  print_string (nom_compresse^"2");
		  print_newline ();
		  close_in in_channel_compresse3;
		  close_in in_channel_compresse2;
		  close_in in_channel_compresse1;
		  close_in in_channel;
	          Sys.remove (nom_compresse^"3");
		end
	      else
		begin
		  print_string "La méthode 3 est préférable. Le nom du fichier compressé est : ";
		  print_string (nom_compresse^"3");
		  print_newline ();
		  close_in in_channel_compresse3;
		  close_in in_channel_compresse2;
		  close_in in_channel_compresse1;
		  close_in in_channel;
		  Sys.remove (nom_compresse^"2");
		end
	    end
	end	
    end;;