(*Élements de correction du tp3 de LP2*)
(*Laure Gonnord et Mathias Peron*)
(*Mars 2007*)

open Format

(*Module Complexe*)
module type TComplex = sig
  type t
  val zero : t
  val cons : float -> float -> t
  val oppose : t -> t
  val plus : t -> t -> t
  val modu : t -> float
  val print : t -> unit
end

module Complex : TComplex = struct
  type t = float * float
  let zero = (0.,0.)
  let cons r i = (r,i)
  let oppose (r,i) = (-.r,-.i)
  let plus (r_1,i_1) (r_2,i_2) = (r_1+.r_2,i_1+.i_2)
  let modu (r,i) = sqrt (r*.r +. i*.i)
  let print (r,i) = printf "%f + %f I" r i 
end

let jeu () = 
  (
    let c1 = Complex.cons 3.14 2.0 and
	c2 = Complex.cons 6.17 (-2.7) in
    let c3 = Complex.plus c1 c2 and
	modulc2 = Complex.modu c2 in
      printf "%f" modulc2; 
      print_newline(); 
      Complex.print c3;
      print_newline();
  )



(*module Pile*)

module type TPile = sig
  type 'a t
  exception Pile_Vide
  val pile_vide : 'a t
  val est_vide : 'a t -> bool
  val push : 'a t -> 'a -> 'a t
  val pop : 'a t -> 'a * 'a t
end


module Pile : TPile = struct
  type 'a t = 'a list
  exception Pile_Vide
    
  let pile_vide = []
    
  let est_vide = function
    | [] -> true
    | _ -> false
	
  let push p e = e :: p
    
  let pop = function
    | [] -> raise Pile_Vide
    | e :: l -> (e,l)
end

exception Pasdedans

let rec reconnaisseur (liste:char list) =
  try (
    let p = ref Pile.pile_vide and fini_a = ref false in
      List.iter (
	fun el -> match el with
	    'a' -> if (!fini_a) then raise Pasdedans else p:=(Pile.push !p 'a') 
 	  | 'b' ->  
	      fini_a :=  true ; 
	      let (ee,p2) = Pile.pop (!p) in 
		if (ee = 'a') then p:=p2 else raise Pasdedans
	  | _ -> raise Pasdedans
      )
	liste;
      Pile.est_vide !p;
  )
  with
      Pasdedans -> false
    | _ -> failwith "souci"


(*Foncteurs de tris*)

module type TypeOrdonne = sig
  type t
  val plus_grand : t -> t -> bool
end

module type TTri = functor (E : TypeOrdonne) -> sig
  val trier : E.t list -> E.t list
end

(*bien utiliser le type ordonné passé en argument, sinon*)
    (*ce n'est pas générique*)


module QuickSort : TTri = functor (E : TypeOrdonne) ->
struct
  let rec partition p = function
    | [] -> [],[]
    | x :: l ->
	let u,v = partition p l in
          if E.plus_grand p x then (x::u),v else u,(x::v)
	    
  let rec qaux l w = match l with
    | [] -> w
    | p :: l ->
	let u,v = partition p l in
          qaux u (p :: qaux v w)
	    
  let trier l = qaux l []
end
  
module Entiers = struct
  type t = int
  let plus_grand x y = (x >= y)
end

module TriEntier1 = QuickSort(Entiers)
  
module ABRSort : TTri = functor (E : TypeOrdonne) ->
struct
  type abr = Vide | Arbre of abr * E.t * abr
    
  let rec ajout arbre e = match arbre with
    | Vide -> Arbre(Vide,e,Vide)
    | Arbre (g,r,d) when E.plus_grand e r ->
	let new_d = ajout d e in Arbre(g,r,new_d)
    | Arbre (g,r,d) ->
	let new_g = ajout g e in Arbre(new_g,r,d)
				   
  let rec construire_liste arbre acc = 
    match arbre with
      | Vide -> acc
      | Arbre (g,r,d) -> 
	  let acc2 = construire_liste d acc in
	    construire_liste g (r::acc2)
	      
  let trier l =
    let arbre = List.fold_left ajout Vide l in
      construire_liste arbre []
  end

module TriEntier2 = ABRSort(Entiers)

(*Tri sur les complexes*)

module Complexes = struct
    type t = Complex.t
    let plus_grand c_1 c_2 =
      (Complex.modu c_1) > (Complex.modu c_2)
  end
  
module TriComplexes = ABRSort(Complexes)

(*imprime un ; de trop mais tant pis*)
(*funp est la fonction d'impression du type 'a de 'a list*)
let imprime_liste l funp = 
  print_string "[";
  List.iter (fun el -> funp el ; print_string " ; ") l;
  print_string "]"

(*realise une liste de complexes a partir d'une liste float*float*)
let make_complex_list ll = 
  List.map (fun el -> Complex.cons (fst el) (snd el)) ll

(*Programme principal TP3*)
let main  = (
  printf  "debut du prog\n";
    
  jeu();
  
  let mot1 = ['a';'a';'a';'b';'b';'b'] 
  and  mot2 = ['a';'b';'a';'b';'a';'b'] in
    if (reconnaisseur mot1) 
    then 
      printf "mot1 dans le langage" 
    else 
      printf "mot1 pas dans le langage ";

    print_newline ();

    if (reconnaisseur mot2) 
    then 
      printf "mot2 dans le langage" 
    else 
      printf "mot2 pas dans le langage ";
    
    print_newline ();

    let res1 = TriEntier1.trier  [3;34;2;1;1;2;6;7] and
	res2 = TriEntier2.trier  [3;34;2;1;1;2;6;7] and
	res3 = TriComplexes.trier 
      (make_complex_list [(0.,0.);(1.,2.);(2.,1.);(3.,0.);(4.,4.)]) in
  
      imprime_liste res1 print_int;
      print_newline();
      imprime_liste res2 print_int;
      print_newline();
      imprime_liste res3 Complex.print;
      print_newline();
      
      printf "fin du prog\n";
      exit 0;
)