Voir la source de 20131021:TP:OCaml:More:Records

[[category:EPITA:TP:20132014]]

== Implémentation des files ==

Pour cette première partie, nous allons implémenter des files FIFO en se basant sur la structure classique des listes circulaires.

Pour ce faire, nous aurons besoin de:

* d'une structure de liste modifiables;
* de valeur qui se référencent elles même.

Pour toute la section courante (file) nous travaillerons dans un module que nous nommerons <tt>MyQueue</tt> et dont voici le fichier d'interface (<tt>myQueue.mli</tt>):

<source lang="ocaml">
(* Interface for module MyQueue *)

(* Opaque Abstract Type *)
type 'a queue

(* Operations *)
val create : unit -> 'a queue
val is_empty : 'a queue -> bool
val length : 'a queue -> int
val push : 'a queue -> 'a -> unit
val take : 'a queue -> 'a
</source>

=== Bases ===

Voici un type pour des listes modifiables (structurellement, nous n'avons pas besoin de changer le contenu):

<source lang="ocaml">
type 'a cell = {
  content : 'a;
  mutable next : 'a cell;
}
</source>

Le type est polymorphe et le champ <tt>next</tt> est modifiable. Par contre, nous ne pouvons pas représenter une liste vide avec ce type. Comme la liste vide n'existe pas, on ne peut représenter que des listes circulaires avec.

Voici maintenant des exemples de listes circulaires construites avec ce type:

<source lang="ocaml">
(* une liste de 1 element *)
let rec l1 = {
  content = 42;
  next = l1;
}

(* une liste a 2 elements *)
let rec l2 = {
  content = 1;
  next = {
    content = 2;
    next = l2;
  };
}
</source>

À titre d'exercice, on va écrire une fonction qui prend une ''liste classique'' et renvoie une liste circulaire avec les mêmes éléments.

* '''Écrire la fonction suivante:'''
<source lang="ocaml">
val build_circular : 'a list -> 'a cell
</source>

=== Des files ===

Pour la construction des files, nous allons ajouter une sentinelle avec la taille et on utilisera le type <tt>'a option</tt> pour régler le problème de la file vide. Voici le type avec la fonction de création:

<source lang="ocaml">
type 'a queue = {
  mutable size : int;
  mutable cell : 'a cell option;
}

let create () = {
  size = 0;
  cell = None;
}
</source>

''Le type <tt>'a option</tt> est un type prédéfini très simpe, permettant de renvoyer rien ou quelque chose. Voici sa définition:''

<source lang="OCaml">
type 'a option =
  | None
  | Some of 'a
</source>

On rappelle la construction des files:

* les éléments sont chaînées dans l'ordre d'arrivée, chaque élément (sauf le plus récent) pointe sur l'élément arrivé après lui;
* l'entrée de la liste pointe sur l'élément le plus récent (celui-ci pointe sur le plus ancien, la liste est circulaire);
* l'ajout d'élément se fait entre l'élément le plus récent (le point d'entrée) et le plus ancien (le suivant du point d'entrée);
* l'élément partant est toujours le suivant du point d'entrée (c'est le plus ancien).

Voici une version en pseudo code des deux opérations principales:

<pre>
push(q, x) {
  q.size <- q.size + 1;
  if q is empty then {
    q.cell <- new circular cell with x;
  } else {
    q.cell.next <- new cell with x and q.cell.next;
    q.cell <- q.cell.next;
  }
}

// precondition: q.size > 0
take(q) {
  res = q.cell.next.content;
  q.size <- q.size - 1;
  if q.size = 0 then {
    q.cell <- empty cell;
  } else {
    q.cell.next <- q.cell.next.next;
  }
  return res;
}
</pre>

Vous pouvez maintenant adapter ces opérations à notre type (attention le champ <tt>cell</tt> est un type option !)

* '''Écrire les fonctions suvantes:'''
<source lang="ocaml">
val is_empty : 'a queue -> bool
val length : 'a queue -> int
val push : 'a queue -> 'a -> unit
val take : 'a queue -> 'a
</source>

=== Test simple ===

Pour tester une file, le plus simple est d'y insérer une série de valeurs (dont l'ordre est facile à retrouver) et de les re-sortir pour vérifier l'ordre.

Voici un petit module de test (à mettre dans le fichier <tt>test_MyQueue.ml</tt> pour valider votre module <tt>MyQueue</tt>.

<source lang="ocaml">
(* Testing MyQueue *)
(* file: test_MyQueue.ml *)

let main () =
  let q = MyQueue.create () in
    begin
      for i=0 to 10 do
        MyQueue.push q i
      done;
      while not (MyQueue.is_empty q) do
        Printf.printf "%d\n" (MyQueue.take q)
      done;
      exit 0;
    end

let _ = main ()
</source>

Maintenant, vous devriez pouvoir compiler et tester (voici un exemple avec <tt>ocamlbuild</tt>):

<pre>
unshell> ls
myQueue.ml    myQueue.mli    test_MyQueue.ml
unshell> ocamlbuild test_MyQueue.native
[compiler doing its job]
unshell> ./test_MyQueue.native
0
1
2
3
4
5
6
7
8
9
10
unshell>
</pre>

== Indexation de caractères ==

Notre objectif maintenant est d'indexer les caractères apparaissant dans un text: nous voulons stocker, dans un tableau de files, la suite des positions occupées par chaque caractère.

Dans ce tableau d'index, l'on doit trouver à la case <tt>i</tt> la file contenant les positions du caractère de code ASCII <tt>i</tt>.

* '''Écrire les fonctions suivantes:'''
<source lang="ocaml">
(* build an empty index (array 256 cell with an empty queue) *)
val create_index : unit -> 'a MyQueue.queue array
(* add_entry index c pos : add pos to the queue for char c *)
val add_entry : 'a MyQueue.queue array -> char -> 'a -> unit
(* build_index s : traverse the string s and return the index with pos for all char *)
val build_index : string -> int MyQueue.queue array
</source>

Voici un peu de code pour un test simple:

<source lang="ocaml">
(* char_index.ml *)

let create_index () =
  (* FIX ME *)

let add_entry index c pos =
  (* FIX ME *)

let build_index text =
  (* FIX ME *)

let read_file name =
  let rec reader accu cin =
    try
      reader (accu ^ (input_line cin) ^ "\n") cin
    with
      | End_of_file -> accu
  in
  reader "" (open_in name)

let simple_output index =
  begin
    Format.printf "@[<b>";
    for i = 0 to 255 do
      Format.printf "| %-7s : %3d@;"
        (Printf.sprintf "%C" (Char.chr i))
        (MyQueue.length index.(i))
    done;
    Format.printf "@]@.";
  end

let main () =
  begin
    if Array.length Sys.argv < 2 then
      begin
        Printf.eprintf "Need a file name\n";
        exit 1;
      end;
    let index = build_index (read_file Sys.argv.(1)) in
    simple_output index;
    exit 0
  end

let _ = main ()
</source>


Et maintenant, testez :

<pre>
unshell> ls
_build/ char_index.ml myQueue.ml myQueue.mli test_MyQueue.ml test_MyQueue.native
unshell> ocamlbuild -clean
Finished, 0 targets (0 cached) in 00:00:00.
00:00:00 0    (0   ) STARTING
unshell> ocamlbuild char_index.native
Finished, 8 targets (0 cached) in 00:00:00
unshell> ./char_index.native myQueue.mli
| '\000'  :   0 | '\001'  :   0 | '\002'  :   0 | '\003'  :   0
| '\004'  :   0 | '\005'  :   0 | '\006'  :   0 | '\007'  :   0
| '\b'    :   0 | '\t'    :   0 | '\n'    :  11 | '\011'  :   0
| '\012'  :   0 | '\r'    :   0 | '\014'  :   0 | '\015'  :   0
| '\016'  :   0 | '\017'  :   0 | '\018'  :   0 | '\019'  :   0
| '\020'  :   0 | '\021'  :   0 | '\022'  :   0 | '\023'  :   0
| '\024'  :   0 | '\025'  :   0 | '\026'  :   0 | '\027'  :   0
| '\028'  :   0 | '\029'  :   0 | '\030'  :   0 | '\031'  :   0
| ' '     :  45 | '!'     :   0 | '"'     :   0 | '#'     :   0
| '$'     :   0 | '%'     :   0 | '&'     :   0 | '\''    :   8
| '('     :   3 | ')'     :   3 | '*'     :   6 | '+'     :   0
| ','     :   0 | '-'     :   6 | '.'     :   0 | '/'     :   0
| '0'     :   0 | '1'     :   0 | '2'     :   0 | '3'     :   0
| '4'     :   0 | '5'     :   0 | '6'     :   0 | '7'     :   0
| '8'     :   0 | '9'     :   0 | ':'     :   5 | ';'     :   0
| '<'     :   0 | '='     :   0 | '>'     :   6 | '?'     :   0
| '@'     :   0 | 'A'     :   1 | 'B'     :   0 | 'C'     :   0
| 'D'     :   0 | 'E'     :   0 | 'F'     :   0 | 'G'     :   0
| 'H'     :   0 | 'I'     :   1 | 'J'     :   0 | 'K'     :   0
| 'L'     :   0 | 'M'     :   1 | 'N'     :   0 | 'O'     :   2
| 'P'     :   0 | 'Q'     :   1 | 'R'     :   0 | 'S'     :   0
| 'T'     :   1 | 'U'     :   0 | 'V'     :   0 | 'W'     :   0
| 'X'     :   0 | 'Y'     :   0 | 'Z'     :   0 | '['     :   0
| '\\'    :   0 | ']'     :   0 | '^'     :   0 | '_'     :   1
| '`'     :   0 | 'a'     :  19 | 'b'     :   2 | 'c'     :   3
| 'd'     :   1 | 'e'     :  26 | 'f'     :   2 | 'g'     :   1
| 'h'     :   2 | 'i'     :   5 | 'j'     :   0 | 'k'     :   1
| 'l'     :   8 | 'm'     :   2 | 'n'     :   6 | 'o'     :   5
| 'p'     :   6 | 'q'     :   7 | 'r'     :   5 | 's'     :   4
| 't'     :  12 | 'u'     :  19 | 'v'     :   5 | 'w'     :   0
| 'x'     :   0 | 'y'     :   4 | 'z'     :   0 | '{'     :   0
| '|'     :   0 | '}'     :   0 | '~'     :   0 | '\127'  :   0
| '\128'  :   0 | '\129'  :   0 | '\130'  :   0 | '\131'  :   0
| '\132'  :   0 | '\133'  :   0 | '\134'  :   0 | '\135'  :   0
| '\136'  :   0 | '\137'  :   0 | '\138'  :   0 | '\139'  :   0
| '\140'  :   0 | '\141'  :   0 | '\142'  :   0 | '\143'  :   0
| '\144'  :   0 | '\145'  :   0 | '\146'  :   0 | '\147'  :   0
| '\148'  :   0 | '\149'  :   0 | '\150'  :   0 | '\151'  :   0
| '\152'  :   0 | '\153'  :   0 | '\154'  :   0 | '\155'  :   0
| '\156'  :   0 | '\157'  :   0 | '\158'  :   0 | '\159'  :   0
| '\160'  :   0 | '\161'  :   0 | '\162'  :   0 | '\163'  :   0
| '\164'  :   0 | '\165'  :   0 | '\166'  :   0 | '\167'  :   0
| '\168'  :   0 | '\169'  :   0 | '\170'  :   0 | '\171'  :   0
| '\172'  :   0 | '\173'  :   0 | '\174'  :   0 | '\175'  :   0
| '\176'  :   0 | '\177'  :   0 | '\178'  :   0 | '\179'  :   0
| '\180'  :   0 | '\181'  :   0 | '\182'  :   0 | '\183'  :   0
| '\184'  :   0 | '\185'  :   0 | '\186'  :   0 | '\187'  :   0
| '\188'  :   0 | '\189'  :   0 | '\190'  :   0 | '\191'  :   0
| '\192'  :   0 | '\193'  :   0 | '\194'  :   0 | '\195'  :   0
| '\196'  :   0 | '\197'  :   0 | '\198'  :   0 | '\199'  :   0
| '\200'  :   0 | '\201'  :   0 | '\202'  :   0 | '\203'  :   0
| '\204'  :   0 | '\205'  :   0 | '\206'  :   0 | '\207'  :   0
| '\208'  :   0 | '\209'  :   0 | '\210'  :   0 | '\211'  :   0
| '\212'  :   0 | '\213'  :   0 | '\214'  :   0 | '\215'  :   0
| '\216'  :   0 | '\217'  :   0 | '\218'  :   0 | '\219'  :   0
| '\220'  :   0 | '\221'  :   0 | '\222'  :   0 | '\223'  :   0
| '\224'  :   0 | '\225'  :   0 | '\226'  :   0 | '\227'  :   0
| '\228'  :   0 | '\229'  :   0 | '\230'  :   0 | '\231'  :   0
| '\232'  :   0 | '\233'  :   0 | '\234'  :   0 | '\235'  :   0
| '\236'  :   0 | '\237'  :   0 | '\238'  :   0 | '\239'  :   0
| '\240'  :   0 | '\241'  :   0 | '\242'  :   0 | '\243'  :   0
| '\244'  :   0 | '\245'  :   0 | '\246'  :   0 | '\247'  :   0
| '\248'  :   0 | '\249'  :   0 | '\250'  :   0 | '\251'  :   0
| '\252'  :   0 | '\253'  :   0 | '\254'  :   0 | '\255'  :   0 
unshell>
</pre>