type ('a, 'b) table_hachage = {hache : 'a -> int; donnees : ('a * 'b) list array; largeur : int} ;;

(* Implémentation de la structure de dictionnaire *)
(* 1 *)

let creer (h : 'a -> int) (w : int) : ('a, 'b) table_hachage =
  {hache = h; donnees = Array.make  w []; largeur = w } ;;

(* 2 *)
(* On est obligé d'écrire sa propre fonction d'appartenance d'une clé dans une liste de couple clé-valeur... *)
let rec mem_k (k : 'a) (l : ('a * 'b) list) : bool =
  match l with
  | [] -> false
  | (key, _) :: q -> key = k || mem_k k q ;;

let recherche (t : ('a, 'b) table_hachage) (k : 'a) : bool =
  let i = t.hache k in
  let l = t.donnees.(i) in
  mem_k k l ;;

(* 3 *)
(* De même il faut une fonction pour récupérer la valeur (de type 'b) dans une liste de couple clé-valeur (de type ('a * 'b) list) *) 
let rec assoc (k : 'a) (l : ('a * 'b) list) : 'b =
  match l with
  | [] -> failwith "Élément absent"
  | (key, value) :: q when key = k -> value
  | _ :: q -> assoc k q ;;
  
let element (t : ('a, 'b) table_hachage) (k : 'a) : 'b =
  let i = t.hache k in
  let l = t.donnees.(i) in
  assoc k l ;;

(* 4 *)
let ajout t k e =
  if not (recherche t k) then
      let i = t.hache k in
      t.donnees.(i) <- e :: t.donnees.(i) ;;

(* 5 *)
(* On se donne sa propre fonction de suppression d'un couple clé valeur dans une liste de tels couples, à partir de la clé *)
let rec supp_k k l =
  match l with
  | [] -> [] (* On ne devrait jamais passer ici.. *)
  | (key, _ ) :: q when key = k -> q
  | (key, value) :: q -> (key, value) :: supp_k k q ;;
  
let suppr t k =
  if recherche t k then
      let i = t.hache k in
      t.donnees.(i) <- supp_k k t.donnees.(i) ;;

(* Étude de la complexité de la recherche d'un élément *)  
(* 6 *)
(* Chaque alvéole contient en moyenne alpha données, d'où O(1 + alpha) (car alpha peut être égal à 0 ... *)

(* 7 *)
(* Si on prend une clé, chaque autre clé a une probabilité 1/w de se trouver dans la même alvéole.
 L'espérance de la taille de cette alvéole est donc 1 + (n - 1)/w <= 1 + alpha.
 D'où complexité encore en O(1+alpha)
Autre approche :  comme on l'a vu en moyenne chaque alvéole contient alpha données. Dès lors pour la recherche dans la liste d'une clé présente
les coûts seront (1 + 2 + 3 + .... alpha) / alpha = (alpha + 1) / 2.

Encore mieux : le calcul précédent montre que pour une liste de taille m la recherche a pour coût moyen 1/m + 2/m + 3/m + m/m = m (m + 1) / (2 m) = (m + 1) / 2 = (m + 1) / 2.

Donc la valeur moyenne de la recherche d'une clé est égale à la valeur moyenne de (m + 1) / 2 où m est la taille d'une des listes, soit par définition de alpha (alpha + 1) / 2. 
On total on a donc un coût également en O(1+alpha). Ici on peut même écrire O(alpha) puisque la table n'est pas vide *)
 *)

(* I.3 Table de hachage dynamique *)
type ('a, 'b) table_dyn = {hache : int -> 'a -> int; mutable taille : int; mutable donnees : ('a * 'b) list array; mutable largeur :int} ;;
(* 8 *)
let cree_dyn h = {hache = h; taille = 0; donnees = Array.make 1 []; largeur = 1 };;  
  
(* 9 *)
(* Il faut bien sûr recréer un nouveau tableau avec la bonne taille et faire le transfert d'un tableau vers l'autre. Pour cela on utilise une fonction auxiliaire récursive ajout qui fait le transfert du contenu d'une alvéole *)
let reaarange t w2 = let w = t.largeur in
                     t.donnees <- Array.make w2 [] ;
                     t.largeur <- w2 ;
                     let rec transfert l =
                       match l with
                       | [] -> ()
                       | (key, value) :: q -> let j = t.hache w2 key in
                                              let alveole = t.donnees.(j) in
                                              t.donnees.(j) <- (key, value) :: alveole ;
                                              transfert q in
                     (* On parcourt l'ancien tableau pour faire le transfert des couples (key, values) *)
                     for i = 0 to w - 1 do
                       transfert t.donnees.(i)
                     done ;;
                       
(* La complexité de création du tableau de listes est O(w2). La fonction ajout a une complexité linéaire en la
taille de la liste. La boucle inconditionnelle est de taille w, et la complexité totale est de l'ordre de la somme des tailles de
toutes les listes, c’est-à-dire O(n). On en déduit une complexité totale en O(n + w + w2 ). *)

(* 10 *)
(* On suppose disposer d'une fonction recherche_dyn pour savoir si la clé est déjà présente ou pas *)  
let ajout_dyn t k e =
  if not (recherche_dyn t k) then begin
      let i = t.hache t.largeur k in
      t.donnees.(i) <- (k, e) :: t.donnees.(i);
      t.taille <- t.taille + 1
    end;
  (* Si après insersion la taille est supérieure à trois fois la largeur on réarrange la table *)
  if t.taille > 3 * t.largeur then
    rearrange_dyn t (3 * t.largeur);;