112 lines
3.2 KiB
OCaml
Executable file
112 lines
3.2 KiB
OCaml
Executable file
open Util
|
||
open Mem
|
||
|
||
(*
|
||
get_assoc:
|
||
int -> (int * char) list -> char -> char
|
||
Description:
|
||
Retourne la valeur associée à la clef e dans la liste l,
|
||
ou la valeur fournie def si la clef n’existe pas.
|
||
Paramètres:
|
||
- e : la clé dont on cherche la valeur associée
|
||
- l : la liste que l'on va chercher
|
||
- def : élement par défaut si l'on ne trouve rien
|
||
Renvoie:
|
||
la valeur associée à la clé, ou def
|
||
Préconditions:
|
||
- True
|
||
Postconditions:
|
||
- True
|
||
Exceptions:
|
||
- None
|
||
*)
|
||
let rec get_assoc e l def =
|
||
match l with
|
||
| [] -> def
|
||
| (k,v)::q -> if k=e then v else (get_assoc e q def)
|
||
|
||
(* Tests unitaires *)
|
||
let liste_test = [ (0, 'a'); (1, 'b'); (2, 'c') ]
|
||
let%test _ = get_assoc 0 liste_test '0' = 'a'
|
||
let%test _ = get_assoc 1 liste_test '0' = 'b'
|
||
let%test _ = get_assoc 2 liste_test '0' = 'c'
|
||
let%test _ = get_assoc 3 liste_test '0' = '0'
|
||
|
||
(*
|
||
set_assoc:
|
||
int -> (int * char) list -> char -> (int * char) list
|
||
Description:
|
||
Remplace la valeur associée à la clef e dans la liste l par x,
|
||
ou ajoute le couple (e, x) si la clef n’existe pas déjà.
|
||
Paramètres:
|
||
- e : la clé dont on veut remplacer la valeur associée
|
||
- l : la liste que l'on va modifier
|
||
- x : nouvelle valeur associée à e
|
||
Renvoie:
|
||
La nouvelle liste modifiée
|
||
Préconditions:
|
||
- True
|
||
Postconditions:
|
||
- True
|
||
Exceptions:
|
||
- None
|
||
*)
|
||
let rec set_assoc e l x =
|
||
match l with
|
||
| [] -> l@[(e,x)]
|
||
| (k,v)::q -> if k=e then (k,x)::q else (k,v)::(set_assoc e q x)
|
||
|
||
(* Tests unitaires *)
|
||
let liste_test = [ (0, 'a'); (1, 'b'); (2, 'c') ]
|
||
let%test _ = set_assoc 0 liste_test 'd' = [ (0, 'd'); (1, 'b'); (2, 'c') ]
|
||
let%test _ = set_assoc 1 liste_test 'e' = [ (0, 'a'); (1, 'e'); (2, 'c') ]
|
||
let%test _ = set_assoc 2 liste_test 'f' = [ (0, 'a'); (1, 'b'); (2, 'f') ]
|
||
let%test _ = set_assoc 3 liste_test 'g' = [ (0, 'a'); (1, 'b'); (2, 'c'); (3, 'g') ]
|
||
|
||
|
||
module AssocMemory : Memory =
|
||
struct
|
||
(* Type = liste qui associe des adresses (entiers) à des valeurs (caractères) *)
|
||
type mem_type = (int * char) list
|
||
|
||
(* Un type qui contient la mémoire + la taille de son bus d'adressage *)
|
||
type mem = int * mem_type
|
||
|
||
(* Nom de l'implémentation *)
|
||
let name = "assoc"
|
||
|
||
(* Taille du bus d'adressage *)
|
||
let bussize (bs, _) = bs
|
||
|
||
(* Taille maximale de la mémoire *)
|
||
let size (bs, _) = pow2 bs
|
||
|
||
(* Taille de la mémoire en mémoire *)
|
||
let allocsize (_, m) =
|
||
List.fold_right (fun _ res_q -> 1 + res_q) m 0
|
||
|
||
(* Nombre de cases utilisées *)
|
||
let busyness (_, m) =
|
||
List.fold_right (
|
||
fun (_,v) res_q -> if v != _0 then 1 + res_q else res_q
|
||
) m 0
|
||
|
||
(* Construire une mémoire vide *)
|
||
let clear bs = (bs, [])
|
||
|
||
(* Lire une valeur *)
|
||
let read (bs, m) addr =
|
||
if addr > (size (bs, m)) then
|
||
raise OutOfBound
|
||
else
|
||
match (get_assoc addr m _0) with
|
||
| v -> v
|
||
|
||
(* Écrire une valeur *)
|
||
let write (bs, m) addr x =
|
||
if addr > (size (bs, m)) then
|
||
raise OutOfBound
|
||
else
|
||
(bs, (set_assoc addr m x))
|
||
end
|