(* ---------- *)
(* Partie 1.1 *)
(* ---------- *)

(* Exercice 1 *)

let taille (liste : 'a list) : int =
  let rec aux (acc : int) = function
    | [] -> acc
    | _ :: q -> aux (acc + 1) q
  in aux 0 liste
;;

taille [];;
taille [1];;
taille [1;2;3];;


(* Exercice 2 *)

let miroir (liste : 'a list) : 'a list =
  let rec aux (acc : 'a list) = function
    | [] -> acc
    | t :: q -> aux (t :: acc) q
  in aux [] liste
;;

miroir [];;
miroir [1];;
miroir [1;2;3];;


(* Exercice 3 *)

(* attention file est à comprendre en francais, pas en anglais, ce n'est pas un fichier "file" *)
type 'a file = 'a list * 'a list;;

let new_file () : 'a file =
  ([], [])
;;


(* Exercice 4 *)

let est_vide_liste (liste : 'a list) : bool =
  (List.length liste) = 0
;;

let est_vide (f : 'a file) : bool =
  let arrive, repart = f in
  est_vide_liste arrive && est_vide_liste repart
;;

let file_vide = new_file ();;
est_vide file_vide;;


(* Exercice 5 *)

let enfile (e : 'a) (f : 'a file) : 'a file =
  let arrive, repart = f in
  (e :: arrive, repart)
;;


(* Exercice 6 *)

let defile (f : 'a file) : 'a * 'a file =
  let arrive, repart = f in
  match repart with
  | [] -> begin
    let new_repart = miroir arrive in
    match new_repart with
    | [] -> failwith "File vide, aucun element a defiler"
    | t :: q -> t, ([], q)
  end
  | t :: q -> t, (arrive, q)
;;

let tete_file_sans_changer (f : 'a file) : 'a =
  let arrive, repart = f in
  match repart with
  | [] -> begin
    let new_repart = miroir arrive in
    match new_repart with
    | [] -> failwith "File vide, aucun element a defiler"
    | t :: _ -> t
  end
  | t :: _ -> t
;;


(* Exercice 7 *)

let f1 = enfile 4 (enfile 5 (enfile 3 (new_file ())));;
let (x1, f2) = defile f1;;
let (x2, f3) = defile (enfile 8 f2);;
let (x3, f4) = defile f3;;
let (x4, f5) = defile f4;;


(* Exercice 8 *)

let longueur (f : 'a file) : int =
  let arrive, repart = f in
  (List.length arrive) + (List.length repart)
;;

longueur f1;;
longueur f2;;
longueur f3;;
longueur f4;;
longueur f5;;

(* Exercice 9 *)

let elements_list (f : 'a file) : 'a list =
  let rec aux (acc : 'a list) (f : 'a file) : 'a list =
    if est_vide f then acc
    else begin
      let e, f2 = defile f in
      aux (e :: acc) f2
    end
  in miroir (aux [] f);
;;

elements_list f1;;
elements_list f2;;
elements_list f3;;
elements_list f4;;
elements_list f5;;

let elements (f : 'a file) : string =
  String.concat ">>>" (List.map string_of_int (elements_list f))
;;

print_endline (elements f1);;
print_endline (elements f2);;
print_endline (elements f3);;
print_endline (elements f4);;
print_endline (elements f5);;


(* ---------- *)
(* Partie 1.2 *)
(* ---------- *)

type 'a arbre = V | N of 'a arbre * 'a * 'a arbre;;

let f (x : 'a) : 'a arbre = N(V, x, V);;

(* Exercice 10 *)

let arbre_ex = N(
  N(f 2, 15, f 22), 28, f 41
);;


(* Exercice 11 *)

let rec hauteur (t : 'a arbre) : int =
  match t with
  | V -> -1
  | N(g, _, d) -> 1 + max (hauteur g) (hauteur d)
;;

hauteur arbre_ex;;

let rec taille (t : 'a arbre) : int =
  match t with
  | V -> 0
  | N(g, _, d) -> 1 + (taille g) + (taille d)
;;

taille arbre_ex;;

(* Exercice 12 *)

let rec somme (t : int arbre) : int =
  match t with
  | V -> 0
  | N(g, x, d) -> (somme g) + x + (somme d)
;;

somme arbre_ex;;


(* Exercice 13 *)

let rec liste_etiquettes (t : 'a arbre) : 'a list =
  match t with
  | V -> []
  | N(g, x, d) -> x :: (liste_etiquettes g) @ (liste_etiquettes d)
;;

liste_etiquettes arbre_ex;;


(* Exercice 14 *)

let rec descendants (x : 'a) (t : 'a arbre) =
  match t with
  | V -> []
  | N(g, y, d) when y = x -> y :: (liste_etiquettes g) @ (liste_etiquettes d)
  | N(g, _, d) -> (descendants x g) @ (descendants x d)
;;

descendants 2 arbre_ex;;
descendants 22 arbre_ex;;
descendants 41 arbre_ex;;
descendants 15 arbre_ex;;
descendants 28 arbre_ex;;


(* ---------- *)
(* Partie 2.1 *)
(* ---------- *)

(* Exercice 15 *)

(* C'est un peu verbeux, mais c'est simple a suivre *)
let hamming (n : int) : int list =
  let h2 = ref (enfile 1 (new_file ())) in
  let h3 = ref (enfile 1 (new_file ())) in
  let h5 = ref (enfile 1 (new_file ())) in
  let resultat = Array.make n 0 in
  for i = 0 to n-1 do
    (* on prend les tetes des files *)
    let m2 = tete_file_sans_changer !h2 in
    let m3 = tete_file_sans_changer !h3 in
    let m5 = tete_file_sans_changer !h5 in
    (* on prend le minimum *)
    let e = min m2 (min m3 m5) in
    (* on change les files qui commence par ce e *)
    if m2 = e then h2 := snd (defile !h2);
    if m3 = e then h3 := snd (defile !h3);
    if m5 = e then h5 := snd (defile !h5);
    (* on ajoute e au results *)
    resultat.(i) <- e;
    (* on enfile 2e, 3e, 5e *)
    h2 := enfile (2*e) !h2;
    h3 := enfile (3*e) !h3;
    h5 := enfile (5*e) !h5;
  done;
  Array.to_list resultat
;;

hamming 30;;


(* ---------- *)
(* Partie 2.2 *)
(* ---------- *)

type dict = char arbre;;

let exemple_dict = N (N (N (N (V, '$', N (N (V, '$', V), 'r', V)), 'e',
N (N (V, '$', N (N (V, '$', V), 's', V)), 'i', V)), 'm', N (N (N (V, '$', N (N (V,
'$', V), 's', V)), 'e', V), 'n', V)), 'a', V)
;;

(* Exercice 16 *)

type dict = char arbre;;

let rec estDansDictBin mot (db : dict) = match (mot, db) with
  | (_, V) -> false
  | ([], N (gauche, lettre, droit)) -> lettre = '$'
  | (l::fin_mot, N (gauche, lettre, droit)) ->
      if l = lettre then estDansDictBin fin_mot gauche
      else estDansDictBin mot droit
;;

let contenuDict (db : dict) =
  let rec parcours prefixe = function
    | V -> []
    | N (gauche, lettre, droit) ->
        if lettre = '$'
        then (miroir prefixe)::(parcours prefixe droit)
        else (parcours (lettre::prefixe) gauche) @ (parcours prefixe droit)
  in parcours [] db
;;

let rec ajoutDict mot (db : dict) : dict =
  match mot, db with
  | ([], V) -> N (V, '$', V)
  | ([], N (gauche, lettre, droit)) ->
     if lettre = '$' then db else N (V, n, db)
  | (car::fin_mot, V) -> N (ajoutDict fin_mot V, car, V)
  | (car::fin_mot, N (gauche, lettre, droit)) ->
     if lettre = car
     then N (ajoutDict fin_mot gauche, lettre, droit)
     else N (gauche, lettre, ajoutDict mot droit)
;;