rope.ml

type t = Str of string
       | Node of int * int * t * t

(*
  Fonctions de base

  Il y avait 10 points sur cette partie tout à fait basique.
*)

(* Question 1

   On demande une valeur OCaml bien formée beaucoup d'erreurs de syntaxe simple
   non sanctionnées (guillemets manquants, parenthèses mal fermées), mais aussi des erreurs plus
   grave comme l'oubli de constructeur. On ne peut pas écrire
   Node (1, 2 , "A", "B") car c'est mal typé, les deux derniers arguments ne sont
   pas des ropes mais des chaînes.

   Il faut écrire:
   Node (1, 2, Str "A", Str "B")
*)

let q1 = Node (1, 23, Node(1, 15, Str "tionnell", Str "e, c'es"),
               Str "t super!")

let limit = 10

(* Question 2

   Ici encore de nombreuses erreurs de syntaxe OCaml malgré l'aide mémoire et
   malgré l'indication. Il faut *lire* l'énoncé. L'énoncé indique que la hauteur
   de l'arbre est stockée donc pas besoin de la recalculer et la question
   indique en gras qu'il ne faut pas recalculer. Donc cette fonction doit
   uniquement extraire la hauteur, ou renvoyer 0 si on est sur une feuille.

*)

let height r =
  match r with
    Str _ -> 0
  | Node (h, _, _, _) -> h


(* Question 3
   Même remarque que pour la précédente

*)
let length r = match r with
    Str s -> String.length s
  | Node (_, l, _, _) -> l

(* Question 4:

   ici on demande de reconstruire en utilisant t1 et t2. Il faut aussi être
   malin et réutiliser les fonctions des questions précédentes, afin de
   simplifier le code.

   Il faut aussi savoir calculer la hauteur d'un arbre binaire (vu dans notre
   cours, mais aussi en algo avancé et en OLA de L2, …)
*)

let node r1 r2 =
  (* la nouvelle taille *)
  let l = length r1 + length r2 in
  (* la nouvelle hauteur = 1 + la plus hauteur du plus grand sous arbre. *)
  let h = 1 + max (height r1) (height r2) in
  Node (h, l, r1, r2)

(* Question 5

   première fonction un peu complexe. Ici c'est un parcours d'arbre.

   On donne deux solutions détaillées, on n'en attendait pas autant.

   - concaténer récursivement les listes résultant des sous-arbres, le cas
     de base étant une liste à un élément
     Cette solution a une complexité en O(n^2) dans le pire cas  où n est le
     nombre de feuilles:

       .
      / \
     .   D
    / \
   .   C
   / \
   A   B

   La fonction crée la liste [A] puis [B], puis [A; B]
   puis [C], puis [A;B]@[C]=[A;B;C] (donc on reparcourt [A;B] pendant la concaténation)
   puis [D] puis [A;B;C] @ [D] (donc on reparcourt [A;B;C] ... )

   Mais il y avait quand même tous les points:
*)
let rec collect_bad r =
  match r with
    Str s -> [ s ]
  | Node (_, _, r1, r2) -> (collect_bad r1) @ (collect_bad r2)

(* Il y a une version plus efficace (linéaire) où en parcourt en ajoutant toutes
   les feuilles dans un accumulateur.
   Attention, si on fait un parcours classique gauche droite, alors les feuilles seront
   dans l'ordre inverse, il faut appeler List.rev sur l'accumulateur final.

   Mais on peut aussi parcourir de droite à gauche pour accumuler les feuilles de la plus à droite
   à la plus à gauche directement:
*)


let collect r =
  let rec loop r acc =
    match r with
      Str s -> s::acc
    | Node (_, _, r1, r2) ->
      let acc = loop r2 acc in (* sous arbre droit avant *)
      loop r1 acc
  in
  loop r []

(* Question 6:
   Question triviale sur 0.5 point, juste pour faire lire l'aide mémoire:
   Il suffit d'utiliser un séparateur vide pour String.concat.
*)
let to_string r =
  String.concat "" (collect r)


(* Question 7

   Cette question m'a rendu très triste. J'ai donné dans l'énoncé un algorithme
   qu'il convient de suivre.

   Beaucoup d'étudiants, sous prétexte que je ne note pas la complexité ont écrit du code
   horrible:
   let get r i = (to_string r).[i]

   Ça "marche" mais on perd tout l'intérêt des cordes.
   - l'accès au ième caractère devient en O(|length r|)
   - l'accès au ième caractère alloue toute une grande chaîne
     de caractères temporaire qui est immédiatement jetée.
     Donc oui j'ai mis les points, mais ça m'a fait mal.
*)
let rec get r i =
  match r with
    Str s -> s.[i]
  | Node (_, _, r1, r2) ->
    let l1 = length r1 in
    if i < l1 then get r1 i
    else
      get r2 (i - l1)

(* Question 8

   Ici un itérateur sur les arbres. Attention, il faut penser à itérer sur
   chaque caractère des chaînes trouvant aux feuilles.

   (String.iter existe mais n'était pas dans l'aide mémoire. On peut la remplacer
   par une simple boucle 'for'. )
*)

let rec iter f r =
  match r with
    Str s ->
    (* String.iter f s *)
    for i = 0 to String.length s - 1 do
      f s.[i]
    done
  | Node (_, _, r1, r2) ->
    iter f r1;
    iter f r2

(* Extraction de texte 4.5 points *)
(*
 Un peu plus compliqué, mais ils faut se laisser guider par l'énoncé.

 Il faut aussi lire les types des fonctions demandées.

*)
(* Question 1 Ici, sub doit renvoyer une corde (type rope). Donc on doit
   reconstruire une corde qui n'a peut être pas la même structure que celle de
   départ, donc on utilise la fonction 'node' de la partie 1 (pour ne pas
   recalculer les hauteurs à chaque fois).

   On implémente ensuite l'algorithme de l'énoncé.

   Il est aussi recommandé d'utiliser les mêmes noms de variable que l'énoncé,
   ce qui vous évite de vous embrouiller (et facilite la correction, donc
   l'octroi de points).

   Enfin, IMPORTANT, l'énoncé indique que vous pouvez supposer i et len valides,
   c'est à dire qu'ils ne vont pas dénoter des positions en dehors de la taille
   totale du texte, ce qui vous évite d'écrire de nombreux tests et cas
   d'erreur.
*)

let rec sub r i len =
  match r with
    Str s -> Str (String.sub s i len)
  | Node (h, l, r1, r2) ->
    let len1 = length r1 in (* utilisé plusieurs fois *)
    if i + len <= len1 then sub r1 i len
    else if i >= len1 then 
      (* ici on sait que le caractère i du texte total
         se trouve dans la partie de droite, donc on s'appelle
         sur r2, mais comme on supprime la partie de gauche (r1),
         il faut ajuster l'indice à partir duquel on cherche
         dans r2 en retranchant la taille totale de r1 (car on l'ignore complètement)

         Dit autrement, si r fait une taille 20 et r1 fait une taille 10,
         chercher le 13 caractère de r, c'est comme chercher le 3ème caractère de r2 (car on
         saute r1 qui fait 10 caractères).
      *)
      sub r2 (i-len1) len
    else
      (* ici on applique l'algo proposé dans l'énonce, le lire
         en même temps que le code. *)
      let n = len1 - i in (* le nombre de caractère restant dans r1 après le ième inclus *)
      let res1 = sub r1 i n in
      let res2 = sub r2 0 (len - n) in
      node res1 res2

(* Question 2

      on applique simplement l'algo de l'énoncé.
*)
let insert r i s = 
  let left = sub r 0 i in
  let right = sub r i (length r - i) in
  node left (node s right)
(* ou de façon équivalente: node (node left s) right *)


(* Équilibrage *)


(* Question 1, écrire la fonction récursive était interdit, car
   le calcul pour les valeurs de n demandé ne termineraient pas.
*)
let fib_array n =
  let a = Array.make n 0 in
  a.(1) <- 1;
  (* ici la case 0 contient 0 et la case 1 contient 1 *)
  for i = 2 to n - 1 do
    a.(i) <- a.(i-1) + a.(i-2);
  done;
  a  (* on n'oublie pas de renvoyer le tableau *)

let fib = fib_array 80

(* Question 2
   la définition de l'énoncé
*)
let is_ballanced r =
  let h = height r in
  let l = length r in
  l >= fib.(h+2)

(* Question 3
   la définition de l'énoncé. Encore une fois, on n'oublie
   pas d'utiliser node ici plutot que de reconstruire
   manuellement avec Node(_,_,_,_)
*)

let rec merge tab i j =
  let range = j - i in
  if range = 1 then Str tab.(i)
  else if range = 2 then node (Str tab.(i)) (Str tab.(i+1))
  else
    let mid = i + range / 2 in
    node (merge tab i mid) (merge tab mid j)

(* Question 4 *)
let balance r =
  if is_ballanced r then r else
    let tab = Array.of_list (collect r) in
    merge tab 0 (Array.length tab)