let rd_couple () = Random.float 1000., Random.float 1000. ;;

let rd_nuage n =
  let t= Array.make n (0.,0.) in
  for i = 0 to n-1 do
    t.(i) <- rd_couple ()
  done ;
  t
;;

let tab1 = [|(137.952822280455479, 579.517066764289893);
             (745.24288848465, 673.134497490137164);
             (466.113061566003125, 188.103956342865786);
             (944.098271788395095, 410.935431876780797);
             (186.89530977266773, 283.014495971758549);
             (136.342566575285474, 698.315452710874752);
             (345.004922664389085, 939.068336631267471);
             (891.680623462061476, 287.663161181994212)|]
;;

#require "graphics" ;;

open Graphics ;;

open_graph " 1000x1000" ;;

let round x =
  (* arrondi un flottant a l'entier le plus proche *)
  if x -. (floor x) < 0.5 then int_of_float (floor x) else int_of_float (floor x) + 1
;;

let trace_nuage nuage =
  for i=0 to Array.length nuage - 1 do
    let x,y=nuage.(i) in
    fill_circle (round x) (round y) 3
  done ;;

let coloration p q =
  let x1, y1 = p and x2, y2 = q in
  set_color red ;
  fill_circle (round x1) (round y1) 5 ;
  set_color blue ;
  fill_circle (round x2) (round y2) 5 ;
  set_color black ;
;;

let tab_int = [|2;50;13;8;2;12;48;16;10;46;81;21;30|] ;;

let tab1x = [|(136.342566575285474, 698.315452710874752);
              (137.952822280455479, 579.517066764289893);
              (186.89530977266773, 283.014495971758549);
              (345.004922664389085, 939.068336631267471);
              (466.113061566003125, 188.103956342865786);
              (745.24288848465, 673.134497490137164);
              (891.680623462061476, 287.663161181994212);
              (944.098271788395095, 410.935431876780797)|]
;;

let tab1y =  [|(466.113061566003125, 188.103956342865786);
               (186.89530977266773, 283.014495971758549);
               (891.680623462061476, 287.663161181994212);
               (944.098271788395095, 410.935431876780797);
               (137.952822280455479, 579.517066764289893);
               (745.24288848465, 673.134497490137164);
               (136.342566575285474, 698.315452710874752);
               (345.004922664389085, 939.068336631267471)|]
;;

let tb1 =
  [|(466.113061566003125, 188.103956342865786);
    (345.004922664389085, 939.068336631267471)|]
;;

(* Exercice 1 *)

let distance (x1,y1) (x2,y2) =
  sqrt ((x2 -. x1)**2. +. (y2 -. y1)**2.)
;;

distance tab1.(0) tab1.(1) ;;

let plus_proche_naif t =
  let n = Array.length t in
  if n<2 then failwith "tableau trop petit" ;
  let im = ref 0 and jm = ref 1 in (*indices des points correspondant à dm *)
  let dm = ref (distance t.(!im) t.(!jm)) in
  for i=0 to (n-1) do
    for j=(i+1) to (n-1) do
      let d = distance t.(i) t.(j) in
      if d < !dm then
        begin
          im := i ;
          jm := j ;
          dm := d
        end
    done ;
  done ;
  t.(!im), t.(!jm)
;;

plus_proche_naif tab1 ;;

(* Exercice 2 *)

let fission t =
  let n = Array.length t in
  let m = n/2 in
  (Array.sub t 0 m), (Array.sub t m (n-m))
;;

fission tab_int ;;

let fusion t1 t2 inf =
  let n1 = Array.length t1 in
  let n2 = Array.length t2 in
  if n1+n2=0 then failwith "tableaux vides" ;
  let t = Array.make (n1+n2) t1.(0) in
  let i1 = ref 0 in
  let i2 = ref 0 in
  while !i1<n1 && !i2<n2 do
    if inf t1.(!i1) t2.(!i2) then
      begin
        t.(!i1 + !i2) <- t1.(!i1) ;
        incr i1
      end
    else
      begin
        t.(!i1 + !i2) <- t2.(!i2) ;
        incr i2
      end
  done ;
  (* lorsqu'on arrive ici, on a épuisé l'un des deux tableaux.
   * l'une des deux boucles suivantes ne sert à rien,
   * l'autre va épuiser le tableau restant *)
  while !i1<n1 do
    t.(!i1 + !i2) <- t1.(!i1) ;
    incr i1
  done ;
  while !i2<n2 do
    t.(!i1 + !i2) <- t2.(!i2) ;
    incr i2
  done ;
  t
;;

fusion [|0;2;3;8|] [|1;5;7;9;11|] (fun x y -> x<=y) ;;

fusion [|10;4|] [|5;3;1|] (fun x y -> x>=y) ;;

let rec tri_fusion t inf = match Array.length t with
  | 0 | 1 -> t
  | _ -> let t1,t2 = fission t in
    fusion (tri_fusion t1 inf) (tri_fusion t2 inf) inf
;;

tri_fusion tab_int (fun x y -> x<=y) ;;

tri_fusion tab_int (fun x y -> x>=y) ;;

(* Exercice 3 *)

let inf_x (a,b) (c,d) =
  (a<c) || (a=c && b<=d)
;;

let inf_y (a,b) (c,d) =
  (b<d) || (b=d && a<=c)
;;

tri_fusion tab1 inf_x ;;

tri_fusion tab1 inf_y ;;

(* Exercice 4 *)

let decoupage tx =
  let n = Array.length tx in
  let m = n/2 in
  (Array.sub tx 0 m), (Array.sub tx m (n-m))
;;

decoupage tab1x ;;

(* Exercice 5 *)

let reparti ty c =
  let n = Array.length ty in
  let m = n/2 in
  let tyg, tyd = (Array.make m c), (Array.make (n-m) c) in
  let ig = ref 0 and id = ref 0 in
  for i=0 to (n-1) do
    let a = ty.(i) in
    if inf_x c a then
      begin
        tyd.(!id) <- a ;
        incr id
      end
    else
      begin
        tyg.(!ig) <- a ;
        incr ig
      end
  done ;
  tyg, tyd
;;

reparti tab1y tab1x.(4) ;;

(* Exercice 6 *)

(* version avec ref de liste *)
let extrait_bande ty x0 d =
  let n = Array.length ty in
  let l = ref [] in
  for i=(n-1) downto 0 do
    let x = fst ty.(i) in
    if x0 -. d <= x && x <= x0 +. d
    then l := ty.(i) :: !l
  done ;
  Array.of_list !l
;;

extrait_bande tab1y 400. 100. ;;

(* version avec fonction auxiliaire recursive *)
let extrait_bande ty x0 d =
  let rec aux i l = match i with
  | -1 -> Array.of_list l
  | _ when x0 -. d <= fst ty.(i) && fst ty.(i) <= x0 +. d ->
    aux (i-1) (ty.(i) :: l)
  | _ -> aux (i-1) l
  in aux (Array.length ty -1) []
;;


let parcours_bande tb d =
  let nb = Array.length tb in
  let d2 = ref (d +. 1.) in
  let i = ref 0 and j = ref 1 in
  for k=0 to (nb-1) do
    let k' = ref 1 in
    while !k' <= 7 && k + !k' < nb do (* regarde les 7 prochains éléments *)
      let d' = distance tb.(k) tb.(k + !k') in
      if d' < !d2 then
        begin
          d2 := d' ;
          i := k ;
          j := k + !k'
        end ;
      incr k'
    done ;
  done ;
  (!d2, !i, !j)
;;

parcours_bande tb1 1000. ;;

parcours_bande [||] 100. ;;

(* Exercice 7 *)

let plus_proche_efficace t =
  let rec aux tx ty = match Array.length tx with
    | n when n <= 6 -> plus_proche_naif tx
    | n ->
      let txg, txd = decoupage tx in
      let c = txd.(0) in
      let tyg, tyd = reparti ty c in
      let x0 = (fst txg.(n/2-1) +. fst c) /. 2. in
      let (cg1,cg2) = aux txg tyg in
      let dg = distance cg1 cg2 in
      let (cd1,cd2) = aux txd tyd in
      let dd = distance cd1 cd2 in
      let d = min dg dd in
      let tb = extrait_bande ty x0 d in
      let (d2,i,j) = parcours_bande tb d in
      if d2 < d then
        (tb.(i), tb.(j))
      else if dg < dd then
        (cg1, cg2)
      else
        (cd1, cd2)
  in
  let tx = tri_fusion t inf_x in
  let ty = tri_fusion t inf_y in
  aux tx ty
;;


let egal_couple (x1, y1) (x2, y2) =
  x1 = x2 && y1 = y2 || x1 = y2 && x2 = y1
;;

let temps f x =
  let t = Sys.time() in
  let fx = f x in
  Printf.printf "Temps d'execution: %fs\n" (Sys.time() -. t);
  fx
;;

let test n =
  (* comparaison pour un nuage de taille n *)
  let tab = rd_nuage n in
  clear_graph () ;
  trace_nuage tab ;
  let p, q = temps plus_proche_naif tab in
  coloration p q ;
  egal_couple (p,q) (temps plus_proche_efficace tab) (* verification ! *) 
;;


test 10000 ;;