{"cells":[{"metadata":{"trusted":false},"cell_type":"code","source":"type ('a,'b) table_hachage = {\n   hache : 'a -> int;\n   donnees : ('a*'b) list array;\n   largeur : int\n   };;","execution_count":1,"outputs":[{"output_type":"execute_result","execution_count":1,"data":{"text/plain":"type ('a, 'b) table_hachage = {\n  hache : 'a -> int;\n  donnees : ('a * 'b) list array;\n  largeur : int;\n}"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let creer_table h w = {hache = h ; donnees = Array.make w [] ; largeur = w};;","execution_count":2,"outputs":[{"output_type":"execute_result","execution_count":2,"data":{"text/plain":"val creer_table : ('a -> int) -> int -> ('a, 'b) table_hachage = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let recherche t k =\n   let rec aux x l = match l with\n      | [] -> false\n      | tete::queue -> (fst(tete)=x) || aux x queue\n    in aux k (t.donnees.(t.hache k));;","execution_count":8,"outputs":[{"output_type":"execute_result","execution_count":8,"data":{"text/plain":"\nval recherche : ('a, 'b) table_hachage -> 'a -> bool = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let element t k = \n   let rec aux x l = match l with\n      | [] -> failwith \"clé introuvable\"\n      | tete::queue when fst(tete)=x -> snd(tete)\n      | _::queue -> aux x queue\n    in aux k (t.donnees.(t.hache k));;","execution_count":19,"outputs":[{"output_type":"execute_result","execution_count":19,"data":{"text/plain":"\nval element : ('a, 'b) table_hachage -> 'a -> 'b = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let ajout t k e =\n   if not (recherche t k) then\n      t.donnees.(t.hache k) <- (k,e)::t.donnees.(t.hache k);;","execution_count":22,"outputs":[{"output_type":"execute_result","execution_count":22,"data":{"text/plain":"\nval ajout : ('a, 'b) table_hachage -> 'a -> 'b -> unit = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let suppression t k =\n   let rec aux x l = match l with\n      | [] -> []\n      | tete::queue when fst(tete)=x -> queue\n      | tete::queue -> tete::(aux x queue)\n    in t.donnees.(t.hache k)<- aux k t.donnees.(t.hache k);;","execution_count":25,"outputs":[{"output_type":"execute_result","execution_count":25,"data":{"text/plain":"\nval suppression : ('a, 'b) table_hachage -> 'a -> unit = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"type ('a, 'b) table_dyn = {\n   hache : int -> 'a ->int;\n   mutable taille : int;\n   mutable donnees : ('a * 'b) list array;\n   mutable largeur : int\n};;","execution_count":29,"outputs":[{"output_type":"execute_result","execution_count":29,"data":{"text/plain":"\ntype ('a, 'b) table_dyn = {\n  hache : int -> 'a -> int;\n  mutable taille : int;\n  mutable donnees : ('a * 'b) list array;\n  mutable largeur : int;\n}"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let creer_table_dyn h = {hache = h ; taille = 0 ; donnees = Array.make 1 [] ; largeur = 1};;","execution_count":31,"outputs":[{"output_type":"execute_result","execution_count":31,"data":{"text/plain":"\nval creer_table_dyn : (int -> 'a -> int) -> ('a, 'b) table_dyn = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let recherche_dyn t k =\n   let rec aux x l = match l with\n      | [] -> false\n      | tete::queue -> (fst(tete)=x) || aux x queue\n    in aux k (t.donnees.(t.hache (t.largeur) k));;","execution_count":32,"outputs":[{"output_type":"execute_result","execution_count":32,"data":{"text/plain":"\nval recherche_dyn : ('a, 'b) table_dyn -> 'a -> bool = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let element t k = \n   let rec aux x l = match l with\n      | [] -> failwith \"clé introuvable\"\n      | tete::queue when fst(tete)=x -> snd(tete)\n      | _::queue -> aux x queue\n    in aux k (t.donnees.(t.hache (t.largeur) k));;","execution_count":33,"outputs":[{"output_type":"execute_result","execution_count":33,"data":{"text/plain":"\nval element : ('a, 'b) table_dyn -> 'a -> 'b = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let rearrange_dyn t w2 = \n   let tab = Array.make w2 [] in\n   let rec aux l = match l with \n      | []-> ()\n      | tete::queue -> let i = t.hache w2 (fst(tete)) in tab.(i) <- tete::tab.(i); aux queue\n    in \n    for j = 0 to t.taille -1 do\n       aux t.donnees.(j)\n    done;\n    t.donnees <- tab;\n    t.largeur <- w2;;","execution_count":43,"outputs":[{"output_type":"execute_result","execution_count":43,"data":{"text/plain":"\nval rearrange_dyn : ('a, 'b) table_dyn -> int -> unit = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false,"scrolled":true},"cell_type":"code","source":"let ajout_dyn t k e = \n   if not (recherche_dyn t k) then let i = t.hache (t.largeur) k in\n      t.donnees.(i) <- (k,e)::t.donnees.(i);\n    t.taille <- t.taille+1;\n    if t.taille>3*t.largeur then rearrange_dyn t (3*t.largeur);;","execution_count":44,"outputs":[{"output_type":"execute_result","execution_count":44,"data":{"text/plain":"\nval ajout_dyn : ('a, 'b) table_dyn -> 'a -> 'b -> unit = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let suppression t k =\n   let rec aux x l = match l with\n      | [] -> []\n      | tete::queue when fst(tete)=x -> queue\n      | tete::queue -> tete::(aux x queue)\n    in let i = t.hache (t.largeur) k in t.donnees.(i)<- aux k t.donnees.(i);\n    t.taille <- t.taille-1;\n    if t.taille<t.largeur then rearrange_dyn t (t.largeur/3);;","execution_count":48,"outputs":[{"output_type":"execute_result","execution_count":48,"data":{"text/plain":"\nval suppression : ('a, 'b) table_dyn -> 'a -> unit = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"name":"ocaml","display_name":"OCaml","language":"ocaml"}},"nbformat":4,"nbformat_minor":2}