(* == MIAS 24, Types et structures de données
   Examen final: note sur 50
*)

(* == Exo I ((17pts) *)

(* -- Q I.1 (2 pts) *)
let is_dom n m = 
  (-1 < n) && (n < 7) && (-1 < m) && (m < 7)

(* -- Q I.2 (2 pts) *)
let diff_dom n1 m1 n2 m2 =
  ((n1 <> n2) || (m1 <> m2)) && ((n1 <> m2) || (m1 <> n2))

(* .. Variante amusante *)
let diff_dom n1 m1 n2 m2 =
  (n1+m1 <> n2+m2) || ((n1 <> n2) && (n1 <> m2))

(* -- Q I.3 (3 pts) *)
(* NB: j'ai fait preuve d'indulgence pour ceux qui n'ont pas
   tenu compte de la correction "en direct" de l'erreur de
   type dans l'énoncé. *)

(* .. Une belle réponse aurait été: *)
let mem_dom n m nms =
  List.for_all (fun (n',m') -> diff_dom n m n' m') nms

(* j'ai plutot vu des choses comme cela: *)
let rec mem_dom n m nms =
  match nms with
      [] -> false
    | (n', m')::nms'->
	if (diff_dom n m n' m') then 
	  (mem_dom n m nms')
	else
	  true
(* j'ai accepté les réponses du genre: *)
let rec mem_dom n m nms =
  match nms with
      [] -> false
    | n'::m'::nms'->
	if (diff_dom n m n' m') then 
	  (mem_dom n m nms')
	else
	  true

(* -- Q I.4 (4 pts) *)
let rec game_ok nms =
  match nms with
      [] -> true
    | [(n,m)] -> (is_dom n m)
    | (n1,m1)::(n2,m2)::nms' ->
	(is_dom n1 m1) &&
	(diff_dom n1 m1 n2 m2) &&
	(not (mem_dom n1 m1 nms')) &&
        (m1 = n2) &&
        (game_ok ((n2,m2)::nms'))

(* -- Q I.5 (1 pt) *)
(* val game_ok : (int * int) list -> bool *)

(* -- Q I.6 (4 pts) *)
let compact nms =
  match nms with
      [] -> []
    | [(n,m)] -> [n;m]
    | (n,_)::nms' -> n::(compact nms')

(* -- Q I.7 (1 pt) *)
(* compact : (int * int) list -> int list *)

(* == Exo II (9 pts) *)

(* -- Q II.1 (3 pts) *)
let array_concat xss =
  let k = (Array.length xss) - 1 in
  let rec loop i =
    if i = k then xss.(k)
    else Array.append xss.(i) (loop (i+1))
  in
    loop 0

(* .. Version itérative *)
let array_concat xss =
  let k = (Array.length xss) - 1 in
  let r = ref [||] in
    for i = 0 to k do
      r := Array.append !r xss.(i)
    done;
    !r

(* .. Solution rusée *)
let array_concat xss =
  Array.concat (Array.to_list xss)

(* .. Solution compliquée, mais plus économique en
   création de structures. *)
let array_concat xss =
  let len_xss = Array.length xss in
  (* Calcul de la longueur totale du tableau résultat:
     somme des longueurs des éléments de xss *)
  let len_res = 
    let r = ref 0 in
      for i = 0 to len_xss - 1 do
	r := !r + (Array.length xss.(i))
      done;
      !r
  in
  (* Recherche d'une valeur quelconque pour initialisation
     du tableau résultat: déclenche Not_found si tous les
     éléments de xss sont vides *)
  let find_default () =
    let rec loop i =
      if i = len_xss then raise Not_found
      else if (Array.length xss.(i)) = 0 then (loop (i+1))
      else xss.(i).(0)
    in
      loop 0
  in
  (* Création du tableau résultat: attention au cas particulier
     du tableau de tableaux vides. *)
    try
      let default = find_default () in
      let res = Array.create len_res default in
      let k = ref 0 in
	for i = 0 to len_xss - 1 do
	  let xs = xss.(i) in
	    for j = 0 to (Array.length xs) - 1 do
	      res.(!k) <- xs.(j);
	      incr k
	    done
	done;
	res
    with Not_found -> [||]


(* -- Q II.2 (3 pts) *)
(* Il y a eu peu de réponses "attendues" à cette question, cela est dû a
   une ambiguïté d'interprétation du mot "insérer". J'attendais ceci : *)
(** val insert_list : 'a array -> 'a list -> int -> unit 
  [(insert_list t xs i)] copie dans [t] les éléments de [xs]
  à partie de l'indice [i]. Déclenche l'exception [Invalid_argument]
  si [i] n'est pas un indice correct dans [t] ou si la liste [xs] 
  contient trop d'éléments. *)
(* j'ai plutôt eu cela: *)
(** val insert_list : 'a array -> 'a list -> int -> unit 
  [(insert_list t xs i)] crée un tableau contenant les éléments
  de [t] entre les indices 0 et [i-1], puis les éléments de [xs]
  puis les élements de [t] entre [i] et la fin de [t]. Déclenche une
  exception si [i] n'est pas un indice dans [t] ou ... *)
(* je me suis contenté de cette interprétation si le code suivait... *)

(* -- Q II.3 (3 pts) *)

(* .. Solution attendue *)
let insert_list t xs i =
  let rec loop i xs =
    match xs with
	[] -> ()
      | x::xs' -> 
	  (t.(i) <- x; (loop (succ i) xs'))
  in
  let i_last = (Array.length t) - 1 in
  let xs_len = List.length xs in
    if (i < 0) || (i > i_last) || ((i + xs_len) > i_last) then
      invalid_arg "insert_list"
    else
      loop i xs

(* ... Solution obtenue (une des ...) *)
let insert_list t xs i =
  try
    Array.concat                               (* création d'un tableau contenant: *)
      [ Array.sub t 0 i;                       (* - éléments avant i dans t *)
	Array.of_list xs;                      (* - éléments de xs *)
        Array.sub t i ((Array.length t) - i) ] (* - éléments aprés i dans t *)
  with
      Invalid_argument "Array.sub" -> invalid_arg "insert_list"

(* ... Solution moins fonctionnelle. *)
let insert_list t xs i =
  let len_t = Array.length t in
  let len_xs = List.length xs in
  (* Toujours le problème de la valeur par défault *)
  let find_default () = 
    if len_t > 0 then t.(0)
    else if len_xs > 0 then List.hd xs
    else raise Not_found
  in
    if (i < 0) || (len_t <= i) then
      invalid_arg "insert_list"
    else
      try
	let default = find_default () in
	let res = Array.create (len_t + len_xs) default in
	let xs_tab = Array.of_list xs in (* pour récuperer les éléments de xs *)
	let k = ref 0 in (* indice général pour res *)
	  for j = 0 to i - 1 do
	    res.(!k) <- t.(j);
	    incr k
	  done;
	  for j = 0 to len_xs - 1 do 
	    res.(!k) <- xs_tab.(j);
	    incr k
	  done;
	  for j = i to len_t - 1 do
	    res.(!k) <- t.(j);
	    incr k
	  done;
	  res
      with Not_found -> [||]
	

(* == Exo III (26 pts) *)

(* -- Q III.1 (5 pts) *)
let prefix c xs =
  let rec loop xs cs =
    match xs with
        [] -> (List.rev cs),xs
      | x::xs' -> 
        if (c x) then (loop xs' (x::cs))
        else cs,xs
  in
    loop xs []

(* .. Version sans fonction auxiliaire. *)
let rec prefix c xs =
  match xs with
      [] -> ([], [])
    | x::ys ->
	if (c x) then
	  let (cs, zs) = prefix c ys in
	    ((x::cs), zs)
	else
	  ([], xs) 

(* -- Q III.2 (1 pt) *)
(* NON: une ligne vide ne commence pas par un '#' *)

(* -- Q III.3 (2 pts) *)
let is_comment ln = 
  (String.length ln > 0) && (ln.[0] = '#')

(* -- Q III.4 (3 pts) *)
let split_comments lns =
  prefix is_comment lns

let split_regulars lns =
  prefix (fun ln -> not (is_comment ln)) lns

(* -- Q III.5 (1 pt) *)
(*
  val split_comments : string list -> bool
  val split_regulars : string list -> bool
*)

(* -- Q III.6 (5 pts) *)
let rec invert lns =
  match lns with
      [] -> []
    | _ ->
      let cs,lns1 = split_comments lns in
      let rs,lns2 = split_regular lns1 in
        rs::cs::(invert lns2)

(* -- Q III.7 (4 pts) *)
let input_file fname =
  let lns = ref [] in
  let ic = open_in fname in 
    try
      while true do 
	lns := (input_line ic)::!lns
      done 
    with 
	End_of_file -> ( 
	  close_in ic;
	  List.rev !lns 
	) 

(* -- Q III.8 (3 pts) *)
let output_file fname lns =
  let oc = open_out fname in 
    List.iter (fun ln -> output_string ln; output_char '\n') lns; 
    close_out oc

(* -- Q III.9 (2 pts) *)
let invert_file fname1 fname2 =
  output_file fname2 (invert (input_file fname1))