(* I.1 Codage R.L.E. (Run-Length Encoding) *)
let rec decompression (lc : (int * 'a) list) : ('a list) =
  match lc with
  | [] -> []
  | (0, e) :: q -> decompression q
  | (n, e) :: q -> e :: decompression ((n - 1, e) :: q);;

decompression [(3,'a') ; (1,'b') ; (1,'a') ; (2,'b') ] ;;


let rec compression (liste : 'a list) : (int * 'a) list =
  match liste with
  | [] -> []
  | [e] -> [(1,e)]
  | e :: q -> let qc = compression q in
              let (n, f) = List.hd qc in
              if e = f then (n + 1, f) :: List.tl qc
                       else (1, e) :: qc ;;

compression  ['a'; 'a'; 'a'; 'b'; 'a'; 'b'; 'b'] ;;
compression  [true; true; true; false; false; true; true] 


let foldopv (f : 'a -> 'b -> 'a) (a : 'a) (tab : 'b array) : 'a =
  let res = ref a in
  let n = Array.length tab in
  for i = 0 to n - 1 do
    res := f !res tab.(i)
  done ;
  !res ;;

let test = [|1; 2; 3; 4; 5; 6 |] ;;

foldopv (fun x y -> x + y) 0 test ;;
foldopv (fun x y -> x * y) 1 test ;;

let sumv (tab : int array) : int = foldopv (fun x y -> x + y) 0 tab ;;
let prodv (tab : int array) : int = foldopv (fun x y -> x * y) 1 tab ;;

sumv test ;;
prodv test ;;

(* Ou encore grâce aux fonctions partielles *)
let sumv : int array -> int = foldopv (fun x y -> x + y) 0 ;;
let prodv : int array -> int = foldopv (fun x y -> x * y) 1 ;;

sumv test ;;
prodv test ;;

(* Pour la sommation on peut transfomer l'opérateur infixe + en opérateur préfixe par (+), et ainsi écrire *)
let sumv : int array -> int = foldopv (+) 0 ;;

(* I.3 Conversion entre tableaux et listes  *)
let list_to_array (l : 'a list) : 'a array =
  let n = List.length l in
  if n = 0 then [||]
  else if n = 1 then [|List.hd l|]
  else let rep = Array.make n (List.hd l) in
  let rec list_to_array_aux l i =
    match l with
    | [] -> rep
    | t :: q -> rep.(i) <- t; list_to_array_aux q (i + 1)
    in list_to_array_aux l 0;;

list_to_array [];;
list_to_array [1];;
list_to_array [1; 2; 3; 4];;

let array_to_list (t : 'a array) : 'a list =
  let n = Array.length t in
  let rec array_to_list_aux i =
    if i >= n then []
    else t.(i) :: array_to_list_aux (i + 1)
    in array_to_list_aux 0 ;;

array_to_list [||];;
array_to_list [|1|];;
array_to_list [|1; 2; 3; 4|];;

(* II *)
let triangle (x : int) (y : int) : int =
  (x + y ) * (x + y + 1) / 2 + x;;
                                    
triangle 0 0;;
triangle 1 0 ;;
triangle 0 1;;
triangle 2 0;;
triangle 1 1;;
triangle 0 2;;
triangle 3 0;;
triangle 2 1;;
triangle 1 2;;

let rec triangle_rec (x : int) (y : int) : int =
  match x with
  | 0 -> y * (y + 1) / 2
  | _ -> triangle (x - 1) (y + 1) + 1;;

triangle_rec 10 15;;
triangle 10 15;;

  
  
(* III Mediane des médianes *)
(* Fonction de tri de tableaux à 5 éléments au maximum, par un tri par insertion par exemple *)
let tri_insertion (tab : 'a array) : 'a array =
  let n = Array.length tab in
  let rep = Array.sub tab 0 n in
  for i = 1 to n - 1 do
    let x = rep.(i) in
    let j = ref(i) in
    while !j > 0 && rep.(!j - 1) > x do
      rep.(!j) <- rep.(!j - 1) ;
      decr j
    done ;
    rep.(!j) <- x
  done ;
  rep ;;
  
let test = [|2; 1; 3; 0|] ;;
tri_insertion test;;

(* On peut également créer le tableau rep initialisé uniquement avec tab.(0) à condition d'aller chercher T[i] dans tab, et de travailler dans rep *)
let tri_insertion2 (tab : 'a array) : 'a array =
  let n = Array.length tab in
  let rep = Array.make n tab.(0) in
  for i = 1 to n - 1 do
    let x = tab.(i) in
    let j = ref(i) in
    while !j > 0 && rep.(!j - 1) > x do
      rep.(!j) <- rep.(!j - 1) ;
      decr j
    done ;
    rep.(!j) <- x
  done ;
  rep ;;
  
let test = [|2; 1; 3; 0|] ;;
tri_insertion2 test;;
    
(* Séparation du tableau initial en tableaux de 5 éléments plus un éventuel reliquat à 1 2 3 ou 4 éléments *)
let decoupage (tab : 'a array) : 'a array array =
  let n = Array.length tab in
  let m = n / 5 and r = n mod 5 in (* m est le nombre de tableaux à 5 éléments, on évalue avec r s'il y a un reliquat *)
  let nst = m + if r > 0 then 1 else 0 in (* nst est le nombre de sous-tableaux *)
  let res = Array.make nst [||] in
  begin
    for i = 0 to m - 1 do (* on traite ici les sous-tableaux à 5 éléments *)
      let tab_int = Array.sub tab (i * 5) 5 in
      res.(i) <- tab_int
    done ;
    if r > 0 then (* s'il y a du reliquat, on récupère les éléments correspondants *)
      let tab_int = Array.sub tab (m * 5) r in
      res.(nst - 1) <- tab_int
  end ;
  res;;

decoupage [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11 ; 12; 13; 14|] ;;  
decoupage [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11 ; 12; 13; 14; 15|] ;;
decoupage [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11 ; 12; 13; 14; 15; 16; 17|] ;;

(* Version qui ne compilera pas car la fonction selection n'est pas définie !*)  
let tableau_medianes (tab : 'a array array) : 'a array =
  let nst = Array.length tab in
  let rep = Array.make nst tab.(0).(0) in
  for i = 0 to nst - 1 do
    let tab5 = tri_insertion tab.(i) in
    let n = Array.length tab5 in
    rep.(i) <- selection tab5 ((n + 1) / 2)
  done ;
  rep ;;

(* Solution temporaire pour tester la fonction *)  
let tableau_medianes2 (tab : 'a array array) : 'a array =
  let nst = Array.length tab in
  let rep = Array.make nst tab.(0).(0) in
  for i = 0 to nst - 1 do
    let tab5 = tri_insertion tab.(i) in
    let n = Array.length tab5 in
      rep.(i) <- tab5.((n + 1) / 2 - 1)
  done ;
  rep ;;

tableau_medianes2 (decoupage [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11 ; 12; 13; 14; 15|]) ;;
tableau_medianes2 (decoupage [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11 ; 12; 13; 14; 15; 16|]) ;;
tableau_medianes2 (decoupage [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11 ; 12; 13; 14; 15; 16; 17|]) ;;    
tableau_medianes2 (decoupage [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11 ; 12; 13; 14; 15; 16; 17; 18|]) ;;
tableau_medianes2 (decoupage [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11 ; 12; 13; 14; 15; 16; 17; 18; 19|]) ;;

(* L'appel pour récupérer la médiane des médianes sera un appel récursif du genre
select tab_medianes ((Array.length tab_mediane + 1) / 2) *)
  
let partition (tab : 'a array) (e : 'a) : 'a array * 'a array =
  let n = Array.length tab in
  let nb_inf = ref 0 in
  for i = 0 to n - 1 do
    if tab.(i) <= e then incr nb_inf
  done ;
  let tab_inf = Array.make !nb_inf e and tab_sup = Array.make (n - !nb_inf) e in
  let i_inf = ref 0 and i_sup = ref 0 in
  for i = 0 to n - 1 do
    if tab.(i) <= e then
      begin
        tab_inf.(!i_inf) <- tab.(i) ;
        incr i_inf
      end
    else
      begin
        tab_sup.(!i_sup) <- tab.(i) ;
        incr i_sup
      end
  done ;
  tab_inf, tab_sup ;;

partition [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11 ; 12; 13; 14; 15|] 0 ;;        
partition [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11 ; 12; 13; 14; 15|] 10 ;;        
partition [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11 ; 12; 13; 14; 15|] 17 ;;

(* Le dernier appel récursif !*)
(* On dispose maintenant des deux tableaux. Le premier, tab_inf comprend les éléments inférieurs ou égaux à M, l'autre, tab_sup, ceux supérieurs strictement à M
Il suffit de regarder la taille du premier et de la comparer à i (on recherche le i-ème plus petit élément...) pour savoir où et quoi chercher  !
Notons n_inf le nombre d'éléments du tableau des éléments inférieurs, qui contient M avec par ailleurs M qui est le plus grand élément de ce tableau, si n_inf = i  c'est qu'on cherche le plus grand éléments tab_inf, i.e M. On a donc juste à rendre M ! Si i < n_inf on continue à chercher dans le tableau des inférieurs en recherchant encore le i-ème plus petit. En revanche si i > n_inf on cherche dans le tableau des supérieurs, mais on cherche le (i - n_inf) ième plus petit élément ! *)   

(* La fonction complète !! Version dans laquelle on utilise la fonction tab_medianes définie à l'extérieur de cette fonction, et qui donc ne peut appeler récursivement selection *)
let rec selection (tab : 'a array) (i : int) : 'a =
  let n = Array.length tab in
  if n <= 5 then
    begin
      let tab_trie = tri_insertion tab in
      tab_trie.(i - 1)
    end
  else
    begin
      let sous_tab = decoupage tab in
      let tab_medianes = tableau_medianes2 sous_tab in
      let nm = Array.length tab_medianes in
      let m = selection tab_medianes ((nm + 1) / 2) in
      let tab_inf, tab_sup = partition tab m in
      let n_inf, n_sup = Array.length tab_inf, Array.length tab_sup in
      if i = n_inf then m
      else if i < n_inf then selection tab_inf i
           else selection tab_sup (i - n_inf)           
    end ;;

(* Dans ce test on devrait voir afficher les entiers de 1 à 10, puis une exception *)  
for i = 1 to 11 do
  print_newline () ;
  print_string ("*********************\n");
  print_int (selection [|7; 1; 4; 2; 9; 5; 3; 6; 10; 8|] i) ; print_newline () ;
  print_string ("*********************\n");
done ;;

let grostest = [|48; 49; 50; 51; 52; 43; 44; 45; 46; 47; 38; 39; 40; 41; 42; 33; 34; 35; 36; 37; 28; 29; 30; 31; 32; 23; 24; 25; 26; 27; 18; 19; 20; 21; 22; 13; 14; 15; 16; 17; 8; 9; 10; 53; 54|];;

for i = 1 to 45 do print_int (selection grostest i); print_char ' ' done ;;

  
(* Version avec les deux fonctions tableau_medianes et sleection mutuellement récursives *)
let rec tableau_medianes (tab : 'a array array) : 'a array =
  let nst = Array.length tab in
  let rep = Array.make nst tab.(0).(0) in
  for i = 0 to nst - 1 do
    let n = Array.length tab.(i) in
    rep.(i) <- selection tab.(i) ((n + 1) / 2)
  done ;
  rep
and
  selection (tab : 'a array) (i : int) : 'a =
  let n = Array.length tab in
  if n <= 5 then
    begin
      let tab_trie = tri_insertion tab in
      tab_trie.(i - 1)
    end
  else
    begin
      let sous_tab = decoupage tab in
      let tab_medianes = tableau_medianes sous_tab in
      let nm = Array.length tab_medianes in
      let m = selection tab_medianes ((nm + 1) / 2) in
      let tab_inf, tab_sup = partition tab m in
      let n_inf, n_sup = Array.length tab_inf, Array.length tab_sup in
      if i = n_inf then m
      else if i < n_inf then selection tab_inf i
           else selection tab_sup (i - n_inf)           
    end ;;
  

  
(* Dans ce test on devrait voir afficher les entiers de 1 à 10, puis une exception *)  
for i = 1 to 11 do
  print_newline () ;
  print_string ("*********************\n");
  print_int (selection [|7; 1; 4; 2; 9; 5; 3; 6; 10; 8|] i) ; print_newline () ;
  print_string ("*********************\n");
done ;;

let grostest = [|48; 49; 50; 51; 52; 43; 44; 45; 46; 47; 38; 39; 40; 41; 42; 33; 34; 35; 36; 37; 28; 29; 30; 31; 32; 23; 24; 25; 26; 27; 18; 19; 20; 21; 22; 13; 14; 15; 16; 17; 8; 9; 10; 53; 54|];;

for i = 1 to 45 do print_int (selection grostest i); print_char ' ' done ;;

(* Subtilité sur la création du tableau en dehors de la boucle inconditionnelle dans la Q7 *)
let fubar tab =
  let t = Array.make 2 [||] in
  let st = Array.make 5 tab.(0) in
  for i = 0 to 1 do
    for j = 0 to 4 do
      st.(j) <- tab.(5 * i + j)
    done ;
    t.(i) <- st
  done ;
  t ;;

fubar [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10 |] ;;  

let fubar tab =
  let t = Array.make 2 [||] in
  for i = 0 to 1 do
    let st = Array.make 5 tab.(0) in
    for j = 0 to 4 do
      st.(j) <- tab.(5 * i + j)
    done ;
    t.(i) <- st
  done ;
  t ;;

fubar [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10 |] ;;