(*
 #############################################################
 ##########    Pour dessiner des arbres du type    ###########
 ##########  string arbre * string * string arbre  ###########
 ##########            2012 P. GONSOLIN            ###########
 #############################################################
licence : http://creativecommons.org/licenses/by-nc/3.0/fr/deed.en

Modifier les paramètres par défaut de trace par votre résolution
sous peine de ne voir qu'une partie de votre arbre
trace : (string arbre) -> (?int) -> (?int) -> unit ()
trace_int : (int arbre) -> (?int) -> (?int) -> unit()
random : int -> string_arbre

Pour faire fonctionner cette librairie vous placez ce fichier dans le même dossier que votre fichier.ml
Dans votre fichier vous faites un " #use "arbre.ml" " puis vous pouvez utiliser les fonctions
*)


type 'a arbre = Feuille of 'a | Noeud of 'a arbre * 'a * 'a arbre;;
#load "graphics.cma";;
open Graphics;;


let rec longueur = function (* longueur d'un arbre binaire *)
  |Feuille _ ->1
  |Noeud(a,_,c) -> 1 + max (longueur a) (longueur c);;

let large_max arbre = (* largeur de la ligne qui contient le plus de noeuds*)
  let tablarge = Array.make (longueur arbre) 0 in
  let rec aux arbre ligne =
    if ligne < Array.length tablarge then begin 
      match arbre with 
          |Feuille _ -> tablarge.(ligne) <- succ tablarge.(ligne) 
          | Noeud(x,_,y) -> tablarge.(ligne) <- succ tablarge.(ligne);aux x (ligne +1) ; aux y (ligne +1) end in aux arbre 0;
  Array.fold_left max 0 tablarge;;

let coord_arbre arbre sizex sizey = (* créer un arbre du type (float,float,string) arbre avec les coordonées pour le dessin*)
  let lg = float_of_int (longueur arbre) -. 1. in
  let pasy = (sizey-.20.)/. lg in 
  let rec aux arbre sizex dec ligne = match arbre with 
    |Feuille d -> Feuille ((2.*.dec +. sizex)/.2.,sizey -. ligne*.pasy ,d)
    |Noeud(a,e,b) -> let aa,bb = float_of_int(large_max a) ,float_of_int( large_max b) in 
                     Noeud((aux a (aa/.(aa+.bb)*.sizex) dec (ligne +. 1.)),
                           (dec +.aa/.(aa+.bb)*.sizex,sizey -. ligne*.pasy -. 8.,e),
                           (aux b (bb/.(aa+.bb)*.sizex) (dec +. aa/.(aa+.bb)*.sizex) (ligne +. 1.))) 
  in aux arbre sizex 0. 0.;;

let trace ?(x=1000) ?(y=930) arbre =  (* la fonction qui trace l'arbre , paramétre correspondant à la taille voulue de la fenêtre. On quitte l'arbre en cliquant sur la fenêtre *)
  open_graph (" " ^string_of_int x ^ "x" ^ string_of_int y);
  let ar = coord_arbre arbre (float_of_int x ) (float_of_int y) in
  match ar with Noeud(_,bbb,_) -> let z,w,_ = bbb in
                                  
  let rec aux arbre coord =
    match arbre with
      |Feuille a -> begin match a with 
          | (c, d,e) -> let cc = int_of_float c and dd = int_of_float d in 
                      Graphics.fill_circle cc dd 3 ;Graphics.moveto (fst coord) (snd coord) ; Graphics.lineto cc dd ; 
                      Graphics.moveto (cc+8) (dd-6) ; Graphics.draw_string e; 
      end;
      |Noeud(g,b,f) -> begin match b with r,t,_ ->  aux (Feuille b) coord ; aux g ( int_of_float r,int_of_float t) ; aux f (int_of_float r,int_of_float t) end; in 
  aux ar (int_of_float z,int_of_float w)
    | Feuille _ ->  Graphics.close_graph () ;failwith "arbre réduit à une feuille";

Graphics.wait_next_event [Button_down];
Graphics.close_graph();;

let random lax = (* crée un arbre aléatoire *)
let rec randomtree nb =
  if (Random.float 1. > 0.7 ||  nb > lax) && nb > 1 then Feuille (string_of_int (Random.int 100))
  else Noeud(randomtree (nb +1),string_of_int (Random.int 100),randomtree (nb +1)) in randomtree 0;;

(*let play el = (* faire défiler des arbres avec la touche 'a' *)
Graphics.open_graph " 1000x930";
while Graphics.read_key () = 'a' do
  trace (random 12)
done;
Graphics.close_graph ();;*)
  

let trace_int ?(x=1000) ?(y=930) arbre =
  let g = begin
    let rec aux = function 
    |Feuille a -> Feuille (string_of_int a)
    |Noeud(c,d,e) -> Noeud(aux c, string_of_int d , aux e) in aux arbre end;  in
trace ?x:(Some x) ?y:(Some y) g;;
    
Printf.printf (" Pour utiliser les fonctions trace et trace_int avec des arguments pour les pixels\n vous devez appeler lma fonction de cette manière : trace arbre ~x:valeurx ~y:valeury\n");;