(* Utilisation du module Hashtbl *)
let mon_dico = Hashtbl.create 10 ;;
Hashtbl.find mon_dico "toto" ;;
Hashtbl.mem mon_dico "toto" ;;
mon_dico ;; 
Hashtbl.add mon_dico "toto" 10 ;; 
mon_dico ;;
Hashtbl.add mon_dico "titi" 5 ;;  
Hashtbl.add mon_dico "tata" (-6) ;; 
Hashtbl.add mon_dico "tata" (-4) ;; 
Hashtbl.mem mon_dico "tata" ;;
Hashtbl.find mon_dico "tata" ;;
    
Hashtbl.mem mon_dico "toto" ;;
Hashtbl.find mon_dico "toto" ;;

Hashtbl.replace mon_dico "toto" 9;;
Hashtbl.find mon_dico "toto" ;;

Hashtbl.find mon_dico "tot" ;;
Hashtbl.replace mon_dico "tot" 7;;
Hashtbl.find mon_dico "tot" ;;

Hashtbl.remove mon_dico "tot" ;;
Hashtbl.find mon_dico "tot" ;;
Hashtbl.remove mon_dico "tot" ;;


(* Implémentation impérative d'un dictionnaire à l'aide d'un tableau. Noms des fonctions volontairement différents de celles du module Hashtbl *)
type utilisation = Utilise | Libre ;;
type ('a, 'b) donnee = {cle : 'a; valeur : 'b} ;;
type ('a, 'b) dictionnaire = {taille : int; table : (utilisation * ('a, 'b) donnee) array; mutable nb : int } ;;

let new_dictionnaire (cle : 'a) (valeur : 'b) (taille : int) : ('a, 'b) dictionnaire =
{taille = taille; table = Array.make taille (Libre, {cle = cle; valeur = valeur}); nb = 0 } ;;

let mon_dico = new_dictionnaire "" 0 10 ;;

exception CleAbsente ;;
exception CleDejaPresente ;;
exception DictionnairePlein ;;

let is_in (cle : 'a) (dico : ('a, 'b) dictionnaire) : bool =
  let n = dico.taille in
  let trouve = ref false in
  let i = ref 0 in
  while (not !trouve) && !i < n do
    let element = dico.table.(!i) in
    if fst element = Utilise then
      trouve := (snd element).cle = cle ;
    i := !i + 1  
  done;
  !trouve ;;

let find (cle : 'a) (dico : ('a, 'b) dictionnaire) : 'b  =
  let n = dico.taille in
  let trouve = ref false in
  let rep = ref (snd dico.table.(0)).valeur in (* On pourrait/devrait protéger ça par n > 0 *)
  let i = ref 0 in
  while (not !trouve) && !i < n do
    let element = dico.table.(!i) in
    if fst element = Utilise then
      if (snd element).cle = cle then
        begin
        trouve := true ;
        rep := (snd element).valeur
        end ;
    i := !i + 1  
  done;
  if !trouve then
    !rep
  else raise CleAbsente ;;

  
find "toto" mon_dico ;;

is_in "toto" mon_dico ;;

let insert (cle : 'a) (valeur : 'b) (dico : ('a, 'b) dictionnaire) : unit = 
  if is_in cle dico then raise CleDejaPresente
  else if dico.taille = dico.nb then raise DictionnairePlein
  else
   begin
   let insere = ref false in
   let i = ref 0 in
   while not !insere do
     let element = dico.table.(!i) in
     if (fst element) = Libre then
       begin
       dico.table.(!i) <- (Utilise, {cle = cle; valeur = valeur}) ;        
       insere := true ;
       dico.nb <- dico.nb + 1 
       end ;
     i := !i + 1
   done
   end ;;

mon_dico ;; 
insert "toto" 10 mon_dico ;; 
mon_dico ;;
insert "titi" 5 mon_dico ;;  
mon_dico ;;
insert "tata" (-6) mon_dico ;; 
mon_dico ;;
insert "tata" (-6) mon_dico ;;
    
is_in "toto" mon_dico ;;
find "toto" mon_dico ;;
is_in "tut" mon_dico ;;
find "tut" mon_dico ;;

let modify (cle : 'a) (valeur : 'b) (dico : ('a, 'b) dictionnaire) : unit  =
  let n = dico.taille in
  let trouve = ref false in
  let i = ref 0 in
  while (not !trouve) && !i < n do
    let element = dico.table.(!i) in
    if fst element = Utilise then
      if (snd element).cle = cle then
        begin
        trouve := true ;
        dico.table.(!i) <- (Utilise, {cle = cle ; valeur = valeur})
        end ;
    i := !i + 1  
  done;
  if not !trouve then raise CleAbsente ;;
    

modify "toto" 9 mon_dico ;;
mon_dico ;;    
modify "tot" 7 mon_dico ;;
mon_dico ;;
    
let remove (cle : 'a) (dico : ('a, 'b) dictionnaire) : unit  = 
  let n = dico.taille in
  let trouve = ref false in
  let i = ref 0 in
  while (not !trouve) && !i < n do
    let element = dico.table.(!i) in
    if (fst element) = Utilise then
      begin
      let cle_lue = (snd element).cle and valeur_lue = (snd element).valeur in
      if cle_lue = cle then
        begin
        trouve := true ;
        dico.table.(!i) <- (Libre, {cle = cle_lue; valeur = valeur_lue}) ; (* Ou (Libre, snd element) *)
        dico.nb <- dico.nb - 1 
        end ;
      end ;
    i := !i + 1 ;
  done;
  if not !trouve then raise CleAbsente ;;

mon_dico ;;
remove "toto" mon_dico ;;
mon_dico ;;
remove "titi" mon_dico ;;
mon_dico ;;
insert "titi"  8 mon_dico ;;
mon_dico ;;
remove "tit" mon_dico ;;
mon_dico ;;


(* Une autre implémentation persistante d'un dictionnaire avec une liste, pas au programme *)

type ('a, 'b) donnee = {cle : 'a; valeur : 'b} ;;
type ('a, 'b) dictionnaire = {mutable table : ('a, 'b) donnee list } ;;

exception CleAbsente ;;
exception CleDejaPresente ;;

let new_dictionnaire () = {table = []} ;;

let est_presente cle dico = 
  let rec est_presente_aux l =
    match l with
    | [] -> false
    | t :: q -> if t.cle = cle then true else est_presente_aux q in
    est_presente_aux dico.table ;; 

let recherche cle dico = 
  let rec recherche_aux l =
    match l with
    | [] -> raise CleAbsente
    | t :: q -> if t.cle = cle then t.valeur else recherche_aux q in
    recherche_aux dico.table ;; 

let ajoute cle valeur dico = 
  if est_presente cle dico then raise CleDejaPresente
  else dico.table <- {cle = cle; valeur = valeur} :: dico.table ;;

let modifie cle valeur dico = 
  let rec modifie_aux l =
    match l with
    | [] -> raise CleAbsente
    | t :: q -> if t.cle = cle then {cle = cle; valeur = valeur} :: q else t :: modifie_aux q in
    dico.table <- modifie_aux  dico.table ;; 

let retrait cle dico =
  let rec retrait_aux l =
    match l with
    | [] -> raise CleAbsente
    | t :: q -> if t.cle = cle then q else t :: retrait_aux q in
    dico.table <- retrait_aux  dico.table ;; 

let dico1 = new_dictionnaire () ;;

ajoute "toto" 10 dico1 ;;
dico1 ;; 
ajoute "titi" 20 dico1 ;;
est_presente "tutu" dico1 ;;
est_presente "titi" dico1 ;;
recherche "titi" dico1 ;;
recherche "toto" dico1 ;;
recherche "tutu" dico1 ;;
modifie "titi" 40 dico1 ;;
dico1 ;; 
ajoute "tata" 60 dico1 ;;
retrait "tyty" dico1 ;;
retrait "tutu" dico1 ;;
retrait "titi" dico1 ;;
dico1 ;;