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

(* Exercice 0 *)

let rec nombre_noeuds t = match t with
  | Vide -> 0
  | N(_,g,d) -> 1 + (nombre_noeuds g) + (nombre_noeuds d)
;;

let rec hauteur t = match t with
  | Vide -> -1
  | N(_,g,d) -> 1 + max (hauteur g) (hauteur d)
;;

(* Exercice 1 *)

(* Q1 *)

let arbre_ex = N(1,
                 N(2,N(4,Vide,Vide),N(5,Vide,Vide)),
                 N(3,N(6,Vide,Vide),N(7,Vide,Vide)))
;;

(* Q2 *)

let rec enum_prefixe t = match t with
  | Vide -> []
  | N(x,g,d) -> x::(enum_prefixe g)@(enum_prefixe d)
;;

enum_prefixe arbre_ex ;;

let rec enum_postfixe t = match t with
  | Vide -> []
  | N(x,g,d) -> (enum_postfixe g)@(enum_postfixe d)@[x]
;;

enum_postfixe arbre_ex ;;

let rec enum_infixe t = match t with
  | Vide -> []
  | N(x,g,d) -> (enum_infixe g)@(x::enum_infixe d)
;;

enum_infixe arbre_ex ;;

(* Exercice 2 *)

(* Q1 *)

let rec racines l = match l with
  | [] -> []
  | Vide::q -> racines q
  | N(x,_,_)::q -> x::racines q
;;

(* Q2 *)

let rec ss_arbres l = match l with
  | [] -> []
  | Vide::q -> ss_arbres q
  | N(_,g,d)::q -> g::d::ss_arbres q
;;

(* Q3 *)

let enum_largeur t =
  let rec aux foret acc = match foret with
    | [] -> acc
    | _ -> aux (ss_arbres foret) (acc@(racines foret))
  in aux [t] []
;;

enum_largeur arbre_ex ;;

(* Exercice 3 *)

type arbre = Vide | Noeud of (bool * arbre * arbre);;

(* Q1 *)

let arbreEnonce = Noeud(true,
                        Noeud(false, Vide,
                              Noeud(true, Vide, Vide)),
                        Noeud(false, Vide,
                              Noeud(false, Vide,
                                    Noeud(true, Vide, Vide))))
;;

(* Q2 *)

let rec cherche n e = match n,e with
  | 0, Noeud(b,_,_) -> b
  | n, Noeud(_,_,d) when n mod 2 = 1 -> cherche (n/2) d
  | n, Noeud(_,g,_) -> cherche (n/2) g
  | _, Vide -> false
;;

cherche 7 arbreEnonce ;;

(* Q3 *)

let rec ajoute n e =
  if cherche n e then e
  else match n, n mod 2, e with
    |0,_,Vide -> Noeud(true, Vide, Vide)
    |_,0,Vide -> Noeud(false, ajoute (n/2) Vide, Vide)
    |_,_,Vide -> Noeud(false, Vide, ajoute (n/2) Vide)
    |0,_,Noeud(_,g,d) -> Noeud(true, g, d)
    |_,0,Noeud(b,g,d) -> Noeud(b, ajoute (n/2) g, d)
    |_,_,Noeud(b,g,d) -> Noeud(b, g, ajoute (n/2) d);;

ajoute 127 arbreEnonce ;;
    
arbreEnonce ;;

(* Q4 *)

let rec construit liste = match liste with
  |[] -> Vide
  |t::q -> ajoute t (construit q)
;;

construit [0;2;7] ;;

(* Q5 *)

let rec supprime n e = match n,e with
  |_, Vide -> e
  |0, Noeud(b,g,d) -> Noeud(false, g, d)
  |a, Noeud(b,g,d) when a mod 2 = 0 -> Noeud(b, supprime (n/2) g, d)
  |_, Noeud(b,g,d) -> Noeud(b, g, supprime (n/2) d)
;;

(* Cette fonction renvoie un arbre avec potentiellement des branches mortes;
 * c'est à dire avec des false à tous les noeuds *)

construit [2;7] = supprime 0 (construit [0;2;7]) ;;

construit [0;7] = supprime 2 (construit [0;2;7]) ;;

(* Q6 *)

let rec elague e = match e with
  | Vide -> Vide
  | Noeud(b,Vide,Vide) when b = false-> Vide
  | Noeud(b,g,d) when b = true -> Noeud(b, elague g, elague d)
  | Noeud(b,g,d) ->
    if elague g = Vide && elague d = Vide then Vide
    else Noeud(b, elague g, elague d)
;;

construit [0;7] = elague (supprime 2 (construit [0;2;7])) ;;

(* Q7 *)

let rec union e1 e2 = match e1, e2 with
  | Vide, e -> e
  | e, Vide -> e
  | (Noeud (b1, g1, d1)), (Noeud (b2, g2, d2)) ->
    Noeud (b1 || b2, union g1 g2, union d1 d2)
;;

(* Q8 *)

let rec intersection e1 e2 = match e1, e2 with
  | Vide, e -> Vide
  | e, Vide -> Vide
  | (Noeud (b1, g1, d1)), (Noeud (b2, g2, d2)) ->
    Noeud (b1 && b2, intersection g1 g2, intersection d1 d2)
;;

(* Exercice 4 *)

type quaternaire = Blanc
                 | Noir
                 | Noeud of quaternaire * quaternaire * quaternaire * quaternaire ;;

let ex =
  Noeud(
    Noeud(Blanc,Noir,Noir,Blanc),
    Noeud(Noir,Blanc,Noir,Blanc),
    Noeud(Noir,Blanc,Noir,Noir),
    Noeud(Noir,Blanc,Noir,Blanc)) ;;

(* Q1 *)

let damier4 =
  Noeud(
    Noeud(Noir,Blanc,Noir,Blanc),
    Noeud(Noir,Blanc,Noir,Blanc),
    Noeud(Noir,Blanc,Noir,Blanc),
    Noeud(Noir,Blanc,Noir,Blanc)) ;;

(* Q2 *)

let rec damier n = match n with
  | 0 -> failwith "damier vide"
  | 1 -> Noeud(Noir,Blanc,Noir,Blanc)
  | _ -> let t = damier (n-1) in Noeud(t,t,t,t)
;; 

damier 2 = damier4 ;;

open Graphics ;; (* Bibioltèque graphique *)

#load "graphics.cma" ;;

open_graph "";; (* Création d'une fenêtre vide *)

(* Q3 *)

let rec hauteur t = match t with
  | Blanc | Noir -> 0
  | Noeud(t1,t2,t3,t4) ->
    1 + max (hauteur t1) (max (hauteur t2) (max (hauteur t3) (hauteur t4)))
;;

let dessin t =
  clear_graph () ;
  let h = int_of_float (2.**float_of_int (hauteur t))/2 in
  let l = 50 in
  let rec aux t h x y = match t with
    | Blanc -> ()
    | Noir -> fill_rect x y (h*l+l) (h*l+l)
    | Noeud(t1,t2,t3,t4) ->
      aux t1 (h/2) x y ;
      aux t2 (h/2) (x+h*l) y ;
      aux t3 (h/2) (x+h*l) (y+h*l) ;
      aux t4 (h/2) x (y+h*l)
  in aux t h 100 100
;;

hauteur (damier 4) ;;

dessin (damier 4) ;;

dessin ex ;;

(* Exercice 5 *)

(* Q1 *)

let exemple = 
  Noeud(
    Noeud(Blanc,Blanc,Blanc,Blanc),
    Noeud(Noir,Blanc,Noir,Noir),
    Noeud(Blanc,Blanc,Noir,Noir),
    Noeud(Noir,Noir,Noir,Noir)) ;;

let exemple_compresse =
  Noeud(
    Blanc,
    Noeud(Noir,Blanc,Noir,Noir),
    Noeud(Blanc,Blanc,Noir,Noir),
    Noir) ;;

dessin exemple ;;

dessin exemple_compresse ;;

(* Q2 *)

let rec compression t = match t with
  | Noir -> Noir
  | Blanc -> Blanc
  | Noeud(Noir,Noir,Noir,Noir) -> Noir
  | Noeud(Blanc,Blanc,Blanc,Blanc) -> Blanc
  | Noeud(t1,t2,t3,t4) ->
    Noeud(compression t1,compression t2,compression t3,compression t4) 
;;

compression exemple ;;

exemple_compresse = compression exemple ;;