(* Exercice 1 *)

type 'a tab_redim = {
  mutable nb: int ;
  mutable tab: 'a array
}

let creer_tab () = {nb = 0; tab = [| |]}

let acces t i =
  if i < t.nb then
    t.tab.(i)
  else
    failwith "depassement d'indice"

let modif t i x =
  if i < t.nb then
    t.tab.(i) <- x
  else
    failwith "depassement d'indice"

let ajout t x =
  if t.nb = Array.length t.tab then
    begin (* on fait grossir le tableau *)
      let u = Array.make (2*t.nb+1) x in 
      for i = 0 to t.nb - 1 do (* on recopie les éléments *)
        u.(i) <- t.tab.(i)
      done ;
      t.nb <- t.nb + 1 ;
      t.tab <- u
    end
  else
    begin
      t.tab.(t.nb) <- x ;
      t.nb <- t.nb + 1
    end

let suppr t =
  if t.nb > 0 then
    begin
      t.nb <- t.nb - 1 ;
      t.tab.(t.nb)
    end
  else
    failwith "tableau vide"

(*test*)
let test_exo1 () =
  let t = creer_tab () in
  for i=0 to 9 do
    ajout t i
  done ;
  Printf.printf "Troisième élément : %d\n" (acces t 3) ;
  for i=0 to 9 do
    print_int (suppr t) ; print_string " "
  done ;
  print_newline () ;
  t

let _ = test_exo1 ()

(* Exercice 2 *)

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

(* Q1 *)
let hachage_entier w k = k mod w

let _ = hachage_entier 14 201

(* Q2 *)
let hachage_chaine w s =
  let x = ref 0 in
  let p = ref 1 in
  for i=0 to String.length s - 1 do
    x:=(!x + (int_of_char s.[i])* !p) mod w ;
    p:= ( !p*128) mod w
  done ;
  !x

let _ = hachage_chaine 12 "Bonjour !"

let _ = hachage_chaine 12 "oh oui youpi dansons la carioca"

(* version schéma de Hörner *)
let hachage_chaine w s =
  let x = ref 0 in
  for i=String.length s - 1 downto 0 do
    x:= ( !x * 128 + int_of_char s.[i]) mod w
  done ;
  !x

let _ = hachage_chaine 12 "Bonjour !"

let _ = hachage_chaine 12 "oh oui youpi dansons la carioca"



(* Exercice 3 *)

(* Q1 *)
let creer_table h w =
  {hache = h ; donnees = Array.make w []}

let _ = creer_table (hachage_entier 5) 5

let petit_exemple = {
    hache = hachage_entier 3;
     donnees =
       [|[(15, "truc"); (468, "ocaml"); (498, "Fenelon"); (144, "TP")];
         [(1, "machin"); (154, "coucou")];
         [(185, "info"); (512, "MP2I")]|]
    }

(* Q2 *)
let recherche t k =
  let rec aux l = match l with
    | [] -> false
    | (k',e)::q -> k'=k || aux q
  in aux t.donnees.(t.hache k)

let _ = recherche petit_exemple 498

let _ = recherche petit_exemple 499

(* Q3 *)
let element t k =
  let rec aux l = match l with
    | [] -> raise Not_found
    | (k',e)::q when k'=k -> e
    | _::q -> aux q
  in aux t.donnees.(t.hache k)

let _ = element petit_exemple 498

let _ = element petit_exemple 499

(* Q4 *)
let ajout t k e =
  if not (recherche t k) then
    let hk=t.hache k in
    t.donnees.(hk) <- (k,e)::t.donnees.(hk)

let _ = ajout petit_exemple 38 "Turing"

let _ = petit_exemple.donnees.(2)

(* Q5 *)
let suppression t k =
  let rec aux q = match q with
    | [] -> []
    | (k',e)::q when k'=k -> q
    | x::q -> x::(aux q)   
  in
  let hk=t.hache k in
  t.donnees.(hk) <- aux t.donnees.(hk) 

let _ = suppression petit_exemple 498

let _ = petit_exemple.donnees.(0)


(* Exercice 4 *)

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

(* Q1 *)
let creer_table_dyn h w =
  {hache = h ;
   taille = 0 ;
   donnees = Array.make w []}

let recherche_dyn t k =
  let rec aux l = match l with
    | [] -> false
    | (k',e)::q -> k'=k || aux q
  in
  let w = Array.length t.donnees in
  let hk = t.hache w k in
  aux t.donnees.(hk)

let element_dyn t k =
  let rec aux l = match l with
    | [] -> raise Not_found
    | (k',e)::q when k'=k -> e
    | _::q -> aux q
  in
  let w = Array.length t.donnees in
  let hk = t.hache w k in
  aux t.donnees.(hk)

(* Q2 *)
let rearrange_dyn t = (* à utliser lorsque qu'il y a trop d'éléments dans la lable *)
  let w = Array.length t.donnees in
  let nv_donnees = Array.make (2*w) [] in
  let nv_h = t.hache (2*w) in
  let rec aux l = match l with (* insère les éléments de l dans le tableau nv_donnees *)
    | [] -> ()
    | (k,e)::q -> nv_donnees.(nv_h k) <- (k,e)::nv_donnees.(nv_h k) ; aux q
  in 
  for i=0 to w-1 do (*appelle aux sur toutes les listes du tableau donnees *)
    aux t.donnees.(i)
  done ;
  t.donnees <- nv_donnees

(* Q3 *)
let ajout_dyn t k e =
  let w = Array.length t.donnees in
  if not (recherche_dyn t k) then
    begin
      let hk = t.hache w k in
      t.donnees.(hk) <- (k,e)::t.donnees.(hk) ;
      t.taille <- t.taille + 1 ;
      if t.taille > 2*w then rearrange_dyn t
    end 

(* Q4 *)
(* En terme de complexité amortie (pour ne pas faire ça trop souvent), il vaut
 * mieux diviser la largeur de la table par 2 lorsque la taille de la table
 * devient inférieure à la moitié de sa largeur *)

let rearrange_bis_dyn t = (* à utliser lorsque qu'il y a trop peu d'éléments dans la lable *)
  let w = Array.length t.donnees in
  let nv_donnees = Array.make (w/2) [] in
  let nv_h = t.hache (w/2) in
  let rec aux l = match l with (* insère les éléments de l dans le tableau nv_donnees *)
    | [] -> ()
    | (k,e)::q -> nv_donnees.(nv_h k) <- (k,e)::nv_donnees.(nv_h k) ; aux q
  in 
  for i=0 to w-1 do (*appelle aux sur toutes les listes du tableau donnees *)
    aux t.donnees.(i)
  done ;
  t.donnees <- nv_donnees

let suppression_dyn t k =
  let w = Array.length t.donnees in
  let hk = t.hache w k in
  let rec aux l = match l with
    | [] -> raise Not_found (* si l'élément n'existe pas, on lève une exception *)
    | (k',e)::q when k'=k -> q
    | x::q -> x::(aux q)
  in try 
     t.donnees.(hk) <- aux t.donnees.(hk) ; (* qui fait sauter directement de cette ligne *)
     t.taille <- t.taille - 1 ; 
     if t.taille < w/2 then rearrange_bis_dyn t
  with Not_found ->  () (* à cette ligne *)