(* TP PF sujet n°2 *)

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

(* I *)

(* (a) *)

type couleur = 
     Coeur 
   | Carreau
   | Pique
   | Trefle;;

type carte =
     As of couleur 
   | Roi of couleur
   | Dame of couleur
   | Valet of couleur
   | Basse of int * couleur;;

(* (b) *)

type paquet_de_carte = 
     Derniere of carte
   | Dessus of carte * paquet_de_carte;;

(* (c) *)

Dessus ((As Coeur), 
       Dessus ((Roi Trefle), 
              Derniere (Basse (10,Carreau))));;

(* (d) *)

let rec appartient_carte ca p = 
(* détermine si la carte ca appartient au paquet p *) 
     match(p) with
      Derniere c   -> (c=ca)
    | Dessus (c,p) -> (c=ca) or (appartient_carte ca p);;

let rec contient_quatre_as p =
(* détermine si le paquet contient les 4 as *)
      (appartient_carte (As Coeur)   p)
    & (appartient_carte (As Carreau) p)
    & (appartient_carte (As Pique)   p)
    & (appartient_carte (As Trefle)  p);;
 
(* (e) *)


let rec couleur_carte c =
(* retourne la couleur d'une carte c *)
    match(c) with
      As co -> co 
    | Roi co -> co 
    | Dame co -> co 
    | Valet co -> co 
    | Basse (n,co) -> co;;


let rec valeur_carte c =
(* retourne une valeur pour la carte c (fonction utilisée pour le tri) *)
    match(couleur_carte(c)) with
      Coeur -> 1
    | Carreau -> 2
    | Pique -> 3
    | Trefle -> 4;;


let rec insere_carte ca p = 
(* insere la carte ca dans le paquet trié p *)
     match(p) with
      Derniere c   -> if valeur_carte(ca)<valeur_carte(c) 
                         then Dessus(ca, Derniere c)
                         else Dessus(c, Derniere ca)
    | Dessus (c,p) -> if valeur_carte(ca)<valeur_carte(c) 
                         then Dessus(ca, (insere_carte c p))
                         else Dessus(c, (insere_carte ca p));;


let rec tri_paquet p = 
(* tri le paquet de cartes p *)
     match(p) with
      Derniere c   -> Derniere c
    | Dessus (c,p) -> insere_carte c (tri_paquet p);;

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

(* II *)

(* 1. *)

(* (a) *)


(* avec les listes prédéfinies en Ocaml *)

let rec longueur l = 
  match(l) with
    [] -> 0
  | t::r -> 1+(longueur r);;

let tete l = 
  match(l) with
    [] -> invalid_arg "tete"
  | t::r -> t;;

let reste l = 
  match(l) with
    [] -> invalid_arg "reste"
  | t::r -> r;;
 
let rec nieme n l = 
  match(l) with
    [] -> invalid_arg "nieme"
  | t::r -> if n=0 then t else nieme (n-1) r;;

let rec concat l1 l2 = 
  match(l1) with
    [] -> l2
  | t::r -> t::(concat r l2);;

let rec inverse l = 
  match(l) with
    [] -> []
  | t::r -> concat (inverse r) (t::[]);;


(* (b) *)

let rec union e1 e2 = e1 @ e2;;

let rec appartient x e = 
(* appartenance d'un element x dans un ensemble e *)
  match(e) with
    []     -> false
  | x0::e0 -> (x=x0) or (appartient x e0);;

let rec intersection e1 e2 = 
  match(e1) with
    []   -> []
  | x::e0 -> if (appartient x e2) 
                then x::(intersection e0 e2)
                else (intersection e0 e2);;
 
let rec inclus e1 e2 =
   match(e1) with
    []   -> true
  | x::e0 -> (appartient x e2) & (inclus e0 e2);; 

let rec difference e1 e2 =
   match(e1) with
    []   -> []
  | x::e0 -> if (appartient x e2) 
                then difference e0 e2
                else x::(difference e0 e2);; 

let rec egal e1 e2 = 
    (inclus e1 e2) & (inclus e2 e1);;


(* (d) *)

let rec deplacer (n, de, a, par) =
    if n=0
       then []
       else (deplacer(n-1,de,par,a)) @ [(de,a)] @ 
            (deplacer(n-1,par,a,de));;
 
(* 2. *)

(* (a) *)

type 'a tree = Vide | Racine of 'a tree * 'a * 'a tree;;

(* (b) *)

Racine(Racine(Vide,3,Racine(Vide,2,Vide)),1,Racine(Vide,4,Vide));;

(* (c) *)

let rec size t =
    match(t) with 
      Vide -> 0
    | Racine(l,v,r) -> size(l)+1+size(r);;

(* (d) *)

let rec max(a,b) = if a>b then a else b;;

let rec height t = 
    match(t) with 
      Vide -> 0
    | Racine(l,v,r) -> 1+max(height(l),height(r));;

(* (e) *)

let rec max_tree t = 
    match(t) with 
      Vide -> invalid_arg "max_tree"
    | Racine(Vide,v,Vide) 
                    -> v
    | Racine(l,v,Vide) 
                    -> let ml = max_tree(l) in
                           max(v,ml)
    | Racine(Vide,v,r) 
                    -> let mr = max_tree(r) in
                           max(v,mr)
    | Racine(l,v,r) 
                    -> let ml = max_tree(l) in
                       let mr = max_tree(r) in
                           max(v,max(ml,mr));;