(* Exercice 1 *)
type nombre = Entier of int | Infini;;
let add a b = match a,b with
	| Entier(n1),Entier(n2) -> Entier(n1+n2)
	| _ -> Infini;;
let sub a b = match a,b with
	| Entier(n1),Entier(n2) -> Entier(n1-n2)
	| Entier(n1),Infini -> Entier(0)
	| Infini,Entier(n2) -> Infini
	| _ -> failwith "Indetermination";;

let mul a b = match a,b with
	| Entier(n1),Entier(n2) -> Entier(n1*n2)
	| _ -> Infini;;
let divE a b = match a,b with
	| Entier(n1),Entier(n2) -> Entier(n1/n2)
	| Entier(n1),Infini -> Entier(0)
	| Infini,Entier(n2) -> Infini
	| _ -> failwith "Indetermination";;

let gt a b = match a,b with
	| Entier(a),Entier(b) -> a<b
	| Entier(a),Infini -> false
	| _ -> true;;
	
	
(* Exercice 2 *)
type 'a file = {mutable debut : 'a list; mutable fin : 'a list};;

exception EmptyException;;
exception FullException;;

let file_vide () = {debut=[];fin=[]};;

let est_vide f = f.debut=[] && f.fin=[];;

let reverse l = 
	let rec aux l v = match l with
		| [] -> !v
		| e::s -> v := e::!v;aux s v
	in aux l (ref []);;
	
let hd f = match f with
	| e::s -> e
	| [] -> raise EmptyException;;

let normalise f = if f.debut=[] then begin
		f.debut <- reverse f.fin;
		f.fin <- []
	end;;

let premier f =
	normalise f;
	hd f.debut;;
	
let enfile e f = f.fin <- e::f.fin;;

let defile f =
	normalise f;
	match f.debut with
		| [] -> raise EmptyException
		| e::s -> f.debut <- s;e;;


let x = file_vide ();;
est_vide (x);;
enfile 1 x;;
enfile 2 x;;
premier x;;
enfile 3 x;;
enfile 4 x;;
defile x;;
premier x;;
defile x;;
premier x;;
defile x;;
premier x;;
defile x;;
premier x;;

(* La complexité dans le pire des cas est O(1) pour enfile et O(n) pour defile et premier (à cause de normalise). Mais en pratique, f.debut aura rarement la valeur [] et donc defile, premier et normalise auront une complexité en O(1) *)


(* Exercice 3 *)

type 'a pile = {contenu: 'a list};;

let pilevide () = {contenu=[]};;
let est_videPile p = p.contenu=[];;
let put p e = {contenu=e::p.contenu};;
let top p = hd p.contenu;;
let behead p = match p.contenu with
	| [] -> raise EmptyException
	| e::s -> {contenu=s};;

type 'a file2 = {debut2: 'a pile; fin2: 'a pile};;


let file_vide2 () = {debut2=(pilevide ());fin2=(pilevide ())};;

let est_vide2 f = (est_videPile f.debut2) && (est_videPile f.fin2);;

let reverse2 p = 
	let rec aux l v = match l with
		| [] -> !v
		| e::s -> v := put !v e;aux s v
	in aux p.contenu (ref (pilevide ()));;


let normalise2 f = if f.debut2=(pilevide ()) then
		{debut2 = (reverse2 f.fin2);
		fin2=pilevide ()}
	else f;;

let premier2 f =
	let x = normalise2 f in top x.debut2;;
	
let enfile2 e f = put f.fin2 e;;

let defile2 f =
	normalise f;
	match f.debut with
		| [] -> raise EmptyException
		| e::s -> f.debut <- s;e;;

(* Bon. La complexité est plus souvent en O(1) vu que j'ai utilisé des files et piles immuables*)

type couleur = Bleu | Rouge and assiette = couleur * int;;

let rec separer pile = 
	if est_videPile pile then (pilevide (),pilevide ()) 
	else 
		let (c,i) = top pile in
		let reste = behead pile in
		let p1,p2 = separer reste in
			match c with
				| Bleu -> ((put p1 (c,i)),p2)
				| Rouge -> (p1,(put p2 (c,i)));;

let ranger pile = let p2,p1 = separer pile in 
	let rec adder p1 p2 = if est_videPile p2 then p1 else
		put (adder p1 (behead p2)) (top p2) in
	adder p1 p2;;

let x = {contenu=[(Bleu,0);(Rouge,1);(Bleu,2);(Bleu,3);(Rouge,4);(Bleu,5);(Bleu,6);(Bleu,7);(Rouge,8);(Bleu,9);(Bleu,10);(Rouge,11);(Rouge,12);(Bleu,13)]};;
ranger x;;


(* Exercice 4 *)

type 'a arrayFile = {donnees: 'a array; mutable estVide: bool;mutable debut: int; mutable fin: int};;

(* L'utilisation du champ estVide est nécessaire afin de pouvoir différentier les files vides et pleines, qui vérifieront toutes debut=fin*)
(* On peut contourner le problème en créant un array donnees muable, qui vérifiera dont on doublera la taille lorsque la file est presque pleine. Ainsi, elle ne sera jamais pleine et le problème ne se posera pas*)

let fileVideA taille e = {donnees=Array.make taille e; estVide=true;debut=0;fin=0;};;
let estVideA f = f.estVide;;
let estPleine f = f.debut=f.fin && f.estVide=false;;
let peek f = if f.estVide then raise EmptyException else
	f.donnees.(f.debut);;
let put f e = if estPleine f then raise FullException else
	f.fin <- (f.fin+1) mod (Array.length f.donnees);
	f.estVide <- false;
	f.donnees.(f.fin) <- e;;
let head f = if estVideA f then raise EmptyException else
	let x = f.donnees.(f.debut) in 
		f.debut <- (f.debut+1) mod (Array.length f.donnees);
		f.estVide <- f.debut=f.fin;
		x;;


let f = fileVideA 42 0;;
for i=1 to 42 do put f i done;;
f;;
for i=1 to 30 do print_int (head f);print_newline () done;;
for i=41 to 60 do put f i done;;




(* Exercice 5 *)
type 'a arbre = Nil | N of 'a * 'a arbre * 'a arbre;;

let rec nombre_de_noeuds abre = match abre with
	| Nil -> 0
	| N(e,abr1,abr2) -> 1 + (nombre_de_noeuds abr1) + (nombre_de_noeuds abr2);;

let rec nombre_de_feuilles abre = match abre with
	| Nil -> 1
	| N(e,abr1,abr2) -> (nombre_de_feuilles abr1) + (nombre_de_feuilles abr2);;

let rec hauteur abre = match abre with
	| Nil -> 0
	| N(e,abr1,abr2) -> 1 + (max (hauteur abr1) (hauteur abr2));;

let filiforme n = 
	let rec aux n i =
		if i=n then Nil
		else N(i,aux n (i+1), Nil) 
		(* On peut mettre i+1 si on veut indexer par [[1,n]] *)
	in aux n 0;; 

let rec miroir arbe = match arbe with
	| Nil -> Nil
	| N(e,arb1,arb2) -> N(e,miroir arb2,miroir arb1);;

let a = filiforme 10;;
nombre_de_noeuds a;;
nombre_de_feuilles a;;
hauteur a;;
miroir a;;

(* Exercice 6 *)
let parcours_infixe arbe = 
	let rec aux arbe lst = match arbe with
		| Nil -> lst
		| N(e,arb1,arb2) -> aux arb2 (e::(aux arb1 lst))
	in aux arbe [];;

let parcours_prefixe arbe = 
	let rec aux arbe lst = match arbe with
		| Nil -> lst
		| N(e,arb1,arb2) -> e::(aux arb2 (aux arb1 lst))
	in aux arbe [];;

let parcours_postfixe arbe = 
	let rec aux arbe lst = match arbe with
		| Nil -> lst
		| N(e,arb1,arb2) -> aux arb2 (aux arb1 (e::lst))
	in aux arbe [];;

let rec aux toExplore explored = try match (defile toExplore) with
		| Nil -> aux toExplore explored
		| N(e,arb1,arb2) ->
			begin
				enfile arb1 toExplore;
				enfile arb2 toExplore;
				aux toExplore (e::explored)
			end
		with EmptyException -> explored;;

let parcours_largeur arbe = 
	let rec aux toExplore explored = try match (defile toExplore) with
		| Nil -> aux toExplore explored
		| N(e,arb1,arb2) ->
			begin
				enfile arb1 toExplore;
				enfile arb2 toExplore;
				e::(aux toExplore explored)
			end
		with EmptyException -> explored in
	 let f = file_vide () in enfile arbe f;aux f [];;


let a = N(1,N(2,N(4,N(8,Nil,Nil),N(9,Nil,Nil)),N(5,N(10,Nil,Nil),N(11,Nil,Nil))),N(3,N(6,N(12,Nil,Nil),N(13,Nil,Nil)),N(7,N(14,N(15,Nil,Nil),Nil),Nil)));;

let b = N(1,Nil,N(2,Nil,N(3,Nil,Nil)));;

(* L'infixe réagit bizarrement, mais logiquement*)
parcours_infixe a;;
parcours_prefixe a;;
parcours_postfixe a;;
parcours_largeur a;;


(* Exercice 7 *)
(* Le type arbre ne convient-t'il pas ?*)

exception NotFoundException;;

let test_abr (abre:int arbre) = 
	(* L'arbre est-il valide et ses noeuds compris entre a et b ? *)
	let rec aux abre a b = match abre with
		| Nil -> true
		| N(e,abr1,abr2) -> a<=e && e<=b && (aux abr1 a e) && (aux abr2 e b)
	in aux abre min_int max_int;;

let rec trouve abre n = match abre with
	| Nil -> false
	| N(e,abr1,abr2) -> e=n || (if e>n then trouve abr1 n else trouve abr2 n);;

let rec insere_feuille abre n = match abre with
	| Nil -> N(n,Nil,Nil)
	| N(e,abr1,abr2) -> if e>=n then N(e,insere_feuille abr1 n,abr2)
										 else N(e,abr1,insere_feuille abr2 n);;

let rec extractMax abre = match abre with
	| Nil -> raise EmptyException
	| N(e,a,Nil) -> a,e
	| N(e,a,b) -> extractMax b;;

let rec supprime abre n = match abre with
	| Nil -> raise NotFoundException
	| N(e,abr1,abr2) -> 
		if e=n then	
			match abr1,abr2 with
				| Nil,Nil -> Nil
				| Nil,N(f,a,b) -> N(f,a,b)
				| N(f,a,b),Nil -> N(f,a,b)
				| a,b -> let ax,mx = extractMax a in N(mx,ax,b)
		else if e>n then N(e,supprime abr1 n,abr2)
						 else N(e,abr1,supprime abr2 n);;

let creer_abr l = 
	let rec aux l a = match l with
		| [] -> a
		| e::s -> let na = insere_feuille a e in aux s na
	in aux l Nil;;

let abre = creer_abr [25;36;41;21;33;12;28];;
supprime abre 33;;



(* Exercice 10 *)

type 'a maybe = Blank | Nope | Yep of 'a;;

let rec sizeOnScreen tol abre = match abre with
	| Nil -> raise (Invalid_argument "Nil n'a pas de taille")
	| N(e,Nil,Nil) -> (tol e)+1
	| N(e,a,Nil) | N(e,Nil,a) -> let sa = sizeOnScreen tol a in
		max ((sa/2+1)+(tol e)+3) (sa+1)
	| N(e,a,b) -> let sa = sizeOnScreen tol a and sb = sizeOnScreen tol b in
		max (sa+sb+2) ((tol e)+4+(sa/2)+(sb/2)+2);;

let inttol i= String.length (string_of_int i);;
sizeOnScreen inttol abre;;

let rec smul s i = match i with
	| 0 -> ""
	| 1 -> s
	| n -> s^(smul s (i-1));;

let ( *** ) = fun (s,i) -> smul s i;;

let rec toStringTree tos abre = let tol a = String.length (tos a) in
	match abre with
		| Nil -> raise (Invalid_argument "Nil n'est pas affiché")
		| N(e,Nil,Nil) -> (tos e)^" "
		| N(e,a,Nil) -> 
			let astr = toStringTree a in
			let asz = String.len astr in
			if ((sa/2+1)+(tol e)+3)>sa then
				"."***(sa/2)^"|"^("-"***((sa-(tos e))/2-1))^(tos e)^" "
			else
				(a/2)***"."^"|-"^(tos e)^"."***(max (sa-a/2-2-(tos e)) 1)
		| N(e,Nil,b) -> 			
			let bstr = toStringTree b in
			let bsz = String.len bstr in
			if ((sa/2+1)+(tol e)+3)>sa then
				"."***(sa/2)^"|"^("-"***((sa-(tos e))/2-1))^(tos e)^" "
			else
				(a/2)***"."^"|-"^(tos e)^"."***(max (sa-a/2-2-(tos e)) 1)

		| N(e,a,b) -> "";;