(* Nouvelles instructions pour le TP5.
 *
 * Prenez contact avec le sujet, comprenez l'algorithme pour savoir où l'on
 * va, et répondez aux questions deux petites théoriques. Ensuite, sautez
 * les deux questions suivantes: je vous fournis les fonctions demandées,
 * écrites de façon naïve et peu efficace. Vous atteindrez ainsi plus vite le
 * résultat concret.
 * Ensuite, vous pouvez au choix vous attaquer à la recherche de chemin,
 * (problème classique à savoir faire) et/ou l'optimisation de la procédure
 * de génération de labyrinthe (plus subtil) par l'amélioration de
 * la représentation de l'ensemble frontière. L'amélioration peut être
 * l'implémentation proposée dans l'énoncé, ou directement une autre,
 * selon votre curiosité/imagination/envie.. *)

#load "graphics.cma" ;;

type laby = {
  p : int ;
  q : int ;
  h : bool array array ;
  v : bool array array
}

let new_laby p q v =
  let laby =
    {
      p = p ;
      q = q ;
      h = Array.make_matrix p q v ;
      v = Array.make_matrix p q v
    }
  in
    if v=true then begin
      for i=0 to p-1 do
        laby.h.(i).(0) <- false
      done ;
      for j=0 to q-1 do
        laby.v.(0).(j) <- false
      done
    end ;
    laby
                            
(* Module de dessin. *)
module Graph =
struct

  (* Largeur, hauteur et marge *)
  let w = 620
  let h = 620
  let margin = 10

  (* Création de la fenêtre graphique *)
  let _ = Graphics.open_graph (Printf.sprintf ":0 %dx%d" w h)

  (* Attente du prochain clic *)
  let wait () =
    Printf.printf "Cliquez pour continuer...%!" ;
    ignore (Graphics.wait_next_event [Graphics.Button_down]) ;
    Printf.printf "ok.\n%!"

  (* Dessin d'un labyrinthe *)
  let draw laby =
    let lx = (w-2*margin) / laby.p in
    let ly = (h-2*margin) / laby.q in
    let p i j = margin + i*lx, margin + j*ly in
      (* On efface le tableau, et on dessine la grille des cases en gris *)
      Graphics.clear_graph () ;
      Graphics.set_color (Graphics.rgb 242 242 242) ;
      for i = 0 to laby.p-1 do
        Graphics.draw_poly_line [| p i 0 ; p i laby.q |]
      done ;
      for j = 0 to laby.q-1 do
        Graphics.draw_poly_line [| p 0 j ; p laby.p j |]
      done ;
      (* En noir le contour... *)
      Graphics.set_color Graphics.red ;
      Graphics.draw_rect margin margin (laby.p*lx) (laby.q*ly) ;
      Graphics.set_color Graphics.black ;
      (* ... puis les arêtes *)
      for i = 0 to laby.p-1 do
        for j = 0 to laby.q-1 do
          if laby.h.(i).(j) then
            Graphics.draw_poly_line [| p i j ; p (i+1) j |] ;
          if laby.v.(i).(j) then
            Graphics.draw_poly_line [| p i j ; p i (j+1) |]
        done
      done

  (* Selection d'une cellule *)
  let pick laby =
    Printf.printf "Cliquez dans une case...%!" ;
    let status = Graphics.wait_next_event [Graphics.Button_down] in
    let x,y = status.Graphics.mouse_x, status.Graphics.mouse_y in
    let lx = (w-2*margin) / laby.p in
    let ly = (h-2*margin) / laby.q in
      Printf.printf "ok.\n%!" ;
      (x-margin)/lx,(y-margin)/ly

  (* Marquage *)
  let mark laby i j =
    let lx = (w-2*margin) / laby.p in
    let ly = (h-2*margin) / laby.q in
    let p i j = margin + i*lx, margin + j*ly in
      Graphics.set_color Graphics.green ;
      let (i,j) = p i j in
        Graphics.fill_rect (i+1) (j+1) (lx-2) (ly-2)

end ;;

(* Exemple d'utilisation *)
let laby = new_laby 10 10 false ;;
laby.v.(2).(4) <- true ;;
laby.h.(2).(1) <- true ;;
Graph.draw laby ;
let (i,j) = Graph.pick laby in Printf.printf "Choix = %d.%d\n%!" i j ;;

(* Implémentation naïve des opérations sur l'ensemble frontière *)
let set_new n elt = ref []
let set_add set elt = set := elt::!set
let set_remove set i =
  let c = ref (-1) in
    set := List.filter (fun elt -> incr c ; !c=i) !set
let set_pick set = List.nth !set (Random.int (List.length !set))
let set_empty set = !set = []
let set_remove_all set f = set := List.filter (fun x -> not (f x)) !set
;;