60 lines
2.9 KiB
OCaml
60 lines
2.9 KiB
OCaml
(******************************************************************************)
|
|
(* fonction de recherche dans une liste associative *)
|
|
(* TRIEE par valeur croissante des clés *)
|
|
(* *)
|
|
(* signature : recherche : *)
|
|
(* 'a -> ('a * 'b) list -> 'b option *)
|
|
(* paramètres : - une clé (caractère dans le cas des tries) *)
|
|
(* - une liste d'association (clé / valeur) *)
|
|
(* (branches dans le cas des tries, où la clé est un caractère *)
|
|
(* et la valeur un sous-arbre) *)
|
|
(* résultat : Some (la valeur correspondant à la clé), *)
|
|
(* si elle existe *)
|
|
(* None, sinon *)
|
|
(******************************************************************************)
|
|
let rec recherche c lb =
|
|
match lb with
|
|
| [] -> None
|
|
| (tc, ta)::qlb ->
|
|
if c < tc then None
|
|
else if c = tc then Some ta
|
|
else recherche c qlb
|
|
|
|
(* TEST *)
|
|
let bb = ('b',1)
|
|
let bd = ('d',2)
|
|
let bl = ('l',3)
|
|
let b1 = [bb;bd;bl]
|
|
let%test _ = recherche 'b' b1 = Some 1
|
|
let%test _ = recherche 'd' b1 = Some 2
|
|
let%test _ = recherche 'l' b1 = Some 3
|
|
let%test _ = recherche 'a' b1 = None
|
|
|
|
(******************************************************************************)
|
|
(* fonction d'ajout/mise à jour d'une valeur dans une liste associative *)
|
|
(* TRIEE par valeur croissante des clés *)
|
|
(* *)
|
|
(* signature : maj : *)
|
|
(* 'a -> 'b -> ('a * 'b) list -> ('a * 'b) list *)
|
|
(* paramètres : - une clé (un caractère dans le cas des tries) *)
|
|
(* - le couple (clé,valeur) (la branche dans le cas des tries *)
|
|
(* à ajouter/modifier *)
|
|
(* - la liste associative *)
|
|
(* résultat : la liste associative mise à jour *)
|
|
(******************************************************************************)
|
|
let rec maj c nouvelle_b lb =
|
|
match lb with
|
|
| [] -> [(c,nouvelle_b)]
|
|
| (tc, ta)::qlb ->
|
|
if c < tc then (c,nouvelle_b)::lb
|
|
else if c = tc then (c,nouvelle_b)::qlb
|
|
else (tc, ta)::(maj c nouvelle_b qlb)
|
|
|
|
(* TESTS *)
|
|
|
|
let%test _ = maj 'b' 3 b1 = [('b',3);bd;bl]
|
|
let ba = ('a',4)
|
|
let%test _ = maj 'a' 4 b1 = [ba;bb;bd;bl]
|
|
let bm = ('m',5)
|
|
let%test _ = maj 'm' 5 b1 = [bb;bd;bl;bm]
|